Subscribe to download
Synthetic Vision (Augmented Reality)

Creating triangle mesh with 2.5d delaunay triangulation and shows it on HUD or HMD with augmented reality and flat shading.

Code [github.com]
Microcontroller
A simpler bare-bone setup.


How does it work?
Using an array of laser distance sensor to get points, which is added to a point cloud. For every new point I try to add, I check the distance to the nearest point in the data set that is stored. If the distance is not bigger than a set minimum threshold then I ignore the point. That just makes sure some points are not in the same place or too clumped together.
There's also a distance threshold for when the terrain is flat to better control the triangle density where it wouldn't help to get highere quality mesh.

I use a k-d tree [en.wikipedia.org] structure (and another similar stucture: ball tree) to efficiently search the distance to a nearest point.

Then after getting a point, instead of directly drawing the point cloud like LIDAR, I triangulate it with 2.5D delaunay triangulation, [en.wikipedia.org] this algorithm [en.wikipedia.org] specifically.

The algorithm works with n dimensions, but not that simple to work in 3D, as you get the dimensional simplex [en.wikipedia.org], so tetrahedra. Therefore it's done in 2D, so the height is ignored during triangulation, but used again when drawing, so 2.5D.
The algorithm is incremental, which is to say that I add one point at a time to the mesh, and use the intermediate calculations, so I'm not starting the triangulation over from scratch every time a new point is added.

The color/shading of a triangle is chosen once, which is first determined if it should be water or ground color by if triangle centroid center (average of 3 vertices altitude) is under 0 altitude, then it's colored as water else ground.
Then color is decided using the triangle normal vector Y/up-value and a chosen color gradient (for water or ground) in property setting.
The shading is done with dot product of the triangle normal and a fixed directional light vector.

Then the triangle centroid point (avg. of vertices) is added to a Ball Tree [en.wikipedia.org] data structure, incrementally and self balancing implementation. The data structure is used to spatially partition a batch of 4-7 triangles in spheres, such that it is fast to frustum cull and either accept triangles inside or throw away during tree traversal, without needing to test every triangle inside.
Frustum culling happens every 15 tick unless changed in property setting and work is dynamically split up during those ticks.
During culling then when upon a leaf node where triangles are stored, then the sphere is projected onto the screen and if the size is less than pixel culling threshold it removes some of the triangles in the batch.

Finally with single list of triangles roughly in view after frustum culling then it is first checked per triangle if in infront of camera and within render distance else deleted from list.
And there's a setting to cap max rendered triangles, so it tries to roughly shuffle some of the triangles higher than threshold into the rendered list before removing everything above cap, which roughly results in a terrain mesh with somewhat evenly spaced holes.
If this happens then a good option is to render in wireframe mode as triangles are probably really densely packed anyway.
Triangles in view are then projected to the screen and finally drawn.

Designed for either a monitor or Head Mounted Display with player in compact seat.
Of course more things involved but the most important things explained.


TL;DR:
Laser distance sensor to get points, in which new points are tested if the distance to the closest saved point is bigger than a minimum threshold else ignored.
Then triangulated to a mesh with delaunay triangulation, in which the triangles color/shading is decided upon creation. Triangles are spatially partitioned with a 3D balltree. Balltree gets frustum culled to quickly get triangles roughly in view.
Then before drawing, the triangles are tested if actually in view and finally drawn with augmented reality.



Why a button for isFemale?
There is a height difference depending on gender, so it's to make augmented reality work.


How does it differentiate water?
Checks if the average altitude/height of the 3 vertices that make a triangle is under 0 altitude then it's colored as water else it's over 0 and therefore colored as ground.


Works underwater? Scan the seabed?
Lasers in SW has no issue scanning underwater, therefore it's no issue and works on the seabed.
Colors might not be optimal, so you can change the color gradient. There's also the property which clamps the points min height, which you need to change from default -1 to a large negative number to effectively disable.


Works in caves?
Nope. It is 2.5D, meaning the triangulation happens in 2D, in which the vertices height are ignored, which results in a connected mesh, where if you use the vertices height after triangulation it effectively becomes a heightmap mesh. If you scan something with a roof or in a cave then you get spiky terrain from the ground to roof, becoming unusable.