Last post (made almost 4 years ago) revealed an interesting rendering method Voxel Tracing. It was modern, sophisticated, and it supported any viewpoint, arbitrary terrain, including dynamic destruction. It was great, and felt like the end of the road at the time, but then a few downsides showed up:
- Close details were super blocky. Everything was made of cubes.
- Shading was difficult, even linearly interpolating between height cells, and especially deriving the normals from it.
- Slow, and had to account for the traversal budget. It was especially inefficient near the walls, and had grid-aligned weak zones.
- Required WebGPU, couldn’t run on low-end or old devices.
Seeing how other members of the community are trying to replicate Fostral (or create new maps) in Unity or other polygonal engines, where it looks smooth and somewhat better, I couldn’t shake the feeling that nothing stopped us from producing similar results from the original map data directly. I figured that a lot of space is somewhat flat, and if only we could triangulate the terrain, rendering it would be trivial. I investigated different Delaunay triangulators in Rust ecosystem - all of them choked on the vast Fostral data. I looked at GPU algorithms, even played with Radiant Foam, but that seemed very complicated to integrate and maintain. But now I found a solution!
Triangulation
The general idea starts with a 2D height map. We find special points on this map where the terrain changes direction, and we connect all these points with triangles. This picture shows how we can do it with different thresholds controlling how dense those special points should be:
The actual method is using a greedy point insertion from Garland & Heckbert’s [Fast Polygonal Approximation of Terrains and Height Fields][gh] (1995). Apparently, greedy methods are better for this versus just looking at a local curvature at every point, which we wanted to do first.
Vangers terrain is not a simple 2D height map, however. It can store a single layer, or a 2-layer surface with controllable thickness of the top layer. This brings a few complications. First, we are going to split the layers the same way all through. To select the special points, our heuristic would consider all of the layers at the same time, and each layer will be triangulated using the same points. Secondly, we need to place vertical walls in places where the second layer ends abruptly.
Shading
Triangles are nice because that’s been the main GPU primitive for the last 30 years. We can do smooth shading, we could even store and interpolate normals, and it’s all rendered. The actual color is still fetched per pixel in the shader.
Tiling
We can triangulate the whole Fostral, ending up with some 2.3M vertices. Sending all the polygons to the GPU every frame, however, is not the most efficient way to render: many of those triangles would end up small, and the rasterization overhead would dominate. Additionally, if the geometry changes (destructible terrain), we’d have to update the whole mesh. Standard solution to this - cut the terrain in tiles.
We use 128x128 tiles with levels of detail. Delaunay triangulation has a property that coarse sets are prefixes of the fine. So adding new vertices doesn’t require us to invalidate the old ones, although for LODs we are currently re-fitting the data for each level. We select LOD of a tile based on its distance to the camera, producing roughtly constant on-scrren density of triangles.
Tiling also allows us to avoid hitting the maximum buffer size limit. Whole Fostral would require above 300Mb of data, which crosses the minimum guaranteed limit on the Web.
Additionally, we can cull tiles entirely based on the frustum of the camera. First image uses far distance of 1600 with wide view. Second image cuts at 600 and looks narrowly into the canyon.
This beautiful mechanism introduces a new issue: when neighboring tiles have negative LODs, their edge does not match. In practice this leads to a visible seam in the geometry. We address this by stabilizing the edges and keeping their detail level constant across LODs.
Performance
Measured on 1920x1080 frames with AMD Radeon 890M.
Frame time (ms)
| view | sky | RayTraced | RayVoxel | Painter | Mesh q=0.25 | Mesh q=0.75 |
|---|---|---|---|---|---|---|
| tunnel | 9.1% | 0.9 | 14.8 | 24.5 | 0.9 | 0.8 |
| river | 8.4% | 0.9 | 11.3 | 18.8 | 0.9 | 1.0 |
| canyon | 13.4% | 1.1 | 20.7 | 28.9 | 1.0 | 0.9 |
| ridge | 48.7% | 0.6 | 41.3 | 11.8 | 1.0 | 0.9 |
Accuracy: see-through / covers-sky (%)
| view | RayTraced | RayVoxel | Painter | Mesh q=0.25 | Mesh q=0.75 |
|---|---|---|---|---|---|
| tunnel | 42.2 / 0.0 | 6.6 / 9.1 | 10.5 / 9.1 | 7.7 / 9.1 | 7.0 / 9.1 |
| river | 49.9 / 7.4 | 0.3 / 7.7 | 0.6 / 7.6 | 0.3 / 7.7 | 0.3 / 7.7 |
| canyon | 37.1 / 0.0 | 11.0 / 10.9 | 10.9 / 10.9 | 11.0 / 10.9 | 11.2 / 10.9 |
| ridge | 17.8 / 0.1 | 2.8 / 4.3 | 4.1 / 4.3 | 2.9 / 3.2 | 2.8 / 3.5 |
Combined, as in the PR table
| view | RayTraced | RayVoxel | Painter | Mesh q=0.25 | Mesh q=0.75 |
|---|---|---|---|---|---|
| tunnel interior | 0.9 ms / 42.2% | 14.8 ms / 6.6% | 24.5 ms / 10.5% | 0.9 ms / 7.7% | 0.8 ms / 7.0% |
| river below a span | 0.9 ms / 49.9% | 11.3 ms / 0.3% | 18.8 ms / 0.6% | 0.9 ms / 0.3% | 1.0 ms / 0.3% |
| deep canyon | 1.1 ms / 37.1% | 20.7 ms / 11.0% | 28.9 ms / 10.9% | 1.0 ms / 11.0% | 0.9 ms / 11.2% |
| open ridge | 0.6 ms / 17.8% | 41.3 ms / 2.8% | 11.8 ms / 4.1% | 1.0 ms / 2.9% | 0.9 ms / 2.8% |
Visuals
It looks less clunky and more natural, compared to voxel-based methods:
Conclusion
As a result, we have a rendering pipeline that combines the best of all worlds:
- runs on old hardware
- has quality control
- supports dynamic modification
- looks smooth from any viewpoint