Martini: Real-Time Terrain Mesh Generator | Hacker News Reader

Martini: Real-Time Terrain Mesh Generator

observablehq.com

339 pointsmourner65 comments

Cool! I just want to point out that the urge to generate an irregular mesh can be quite hardware unfriendly if you want to tesselate the terrain dynamically around a moving camera. The well cited papers on Geometry Clipmaps highlight this. The point is that it can be more efficient to focus on feeding the GPU pipeline in an efficient manner instead of focusing on rendering as few triangles as possible. Irregular meshes thrashes the cache if you retriangulate them all the time (since no data can be reused). A uniform grid has many advantages, unless you're only interested in rendering one static view, then irregular meshes are great!

Yep. A uniform mesh of flat quads with a vertex shader doing the displacement will perform better.

Would love to learn more, since it seems counter-intuitive — are there any studies / benchmarks on this for modern hardware? Why would a uniform mesh with, say, 10x more triangles perform better if it's not updated often (e.g. a few times a second)?

It'll come down to how frequently you're doing updates. A few times a second will certainly cost more than a prefab mesh with a texture fetch shader.

If you can precompute various LOD chunks for each tile and cache them, under some circumstances that's optimal, but I don't think any of them are webgl. A typical heightmap based terrain renderer today will consist of several (3-5) prefab LOD meshes deformed by height map textures in shader, like[1]. Swapping a textures in and out of vram is cheaper than swapping geometries, even if those geometries are of lower resolution.

Modern GPUs are almost never bound by the number of triangles on screen. The bottleneck will be the fillrate and bandwidth and pipeline stalls, especially in webgl. If you can throw down more triangles to do less of the other things, it's almost always worth it.

I have a toy mapbox tile renderer based on this approach. I'd love to know if you guys have plans to implement full 3d like google maps any time soon.

[1]: https://imgur.com/a/51g2bB4

I would really love to see your toy Mapbox renderer — please share it, even if unpolished! We'd benefit a lot from fresh ideas on how to improve Mapbox GL performance.

Mainly because GPU throughput is increasing much faster than CPU throughput. Spending cycles removing triangles doesn't matter if the GPU can just churn through them like nothing. In the context of a moving camera you want to reuse as much data as possible between terrain updates. With regular nested grids a ton of data can be reused, only the height needs updating as you move the grids around (and height can be reused between adjacent grids half the time if they have a power of two resolution relationship).

But baking irregular meshes into a tree-structure could be powerful too I suppose, I'm not that familiar with algorithms involving them. All of this is highly dependant on actual size of terrain and LOD requirements, terrain rendering is a deep rabbit hole.

Yeah, it's a thin balance, and to me as someone without years of experience in graphics programming, GPU feels like such a blackbox — hard to predict what will be the actual bottleneck until you implement an approach fully, with real-world loads, and even then it's hard to assess, especially with such variety of GPU performance characteristics on different devices.

So what's simpler / easier to implement in a given system will play an important role, and so are any additional things you want to do with the height data like collision detection, querying, data analysis etc. Anyway, that's a super-exciting topic to learn more about! Thanks a lot for all the thoughtful comments.

GPUs are effectively “magic” and can do particular things hundreds or thousands of times faster than CPUs. Offloading a per-vertex or per-pixel task to the GPU, especially if doing so reduces bandwidth requirements, is almost always a big win.

I think reality is closer to this: GPU rasterization is 20-50 times faster than CPUs and throughput computing maybe 5-20 times faster.

For example consumer Ryzen 3 with 12 cores peaks at 32 FLOPS/core/cycle. So at 3.8 GHz, peak ~1.4 SP TFLOPs (or 0.7 DP TFLOPs). But just 50-60 GB/s memory bandwidth limits it somewhat.

Quick googling says consumer Nvidia RTX 2080 peaks at 10 SP TFLOPs (or 0.314 DP TFLOPs, yes, less than half than the CPU example). Memory bandwidth being at 448 GB/s.

GPUs win massively at rasterization, because they have huge memory bandwidth, a large array of texture samplers with hardware cache locality optimizations (like HW swizzling), texture compression, specialized hardware for z-buffer tests and compression, a ton of latency hiding hardware threads, etc.

But they're definitely not thousands or even hundreds of times faster.

Or even better, couldn’t you use a single quad and a geometry shader?

Geometry shaders seems sort of the bastard child of the graphics pipeline. It was a mess to implement in hardware and the throughput isn't that great when creating tons of triangles. The tesselation stages of the pipeline addresses this and is more suitable for arbitrary subdivision of triangles.

Why not a single quad and a fragment (=pixel) shader? A bit of ray marching, something like this [0].

[0]: http://www.iquilezles.org/www/articles/terrainmarching/terra...

Not very helpful if you need to do collision on the displaced mesh though, I would have thought, since a vertex shader only make it "appear" as if the vertices are not in their original position?

I'm thinking of tracing for foot placement in conjunction with inverse kinematics for walking characters, or vehicle wheels traversing the terrain. I've run into this problem with UE4.

Would it be possible to either compute or approximate the fragment shader's vertex results on segments of the terrain that require collision detection? I bet it wouldn't be feasible to do to check collisions for gun projectiles in a video game, but it might be feasible for something like making sure the player's model doesn't clip beneath the tessellated terrain.

UE4 has adaptive tessellation anyway, and you can scale the tessellation multiplier based on distance with a material function so that the landscape has more triangles closer to the camera and less further away. Beyond a certain distance (where the player wouldn't notice the detail anyway, so there's no point drawing it) you can scale the multiplier to zero to improve performance.

I'm not an expert but honestly in a game engine like UE4 where collision is important, it seems like the adaptive geometry tessellation approach is the way to go, as least from my initial experiments.

I was thinking of a somewhat different use case. I was thinking of a flight simulator where tessellation only occurred close to the camera, to provide the appearance of a more detailed mesh when viewed up close.

The problem is, with a quad mesh where each vertex is 20 or 30 meters apart a plane flying nap of the earth could end up clipping through the tessellated mesh but not actually collide with the non-tessellated terrain quad mesh being used for collision detection. Or worse, the player could collide with the terrain quad mesh but the tessellation makes it visually appear to have not collided with the terrain.

To only two ways I see to solve this are to either not use tessellation up close, or to compute with the CPU the vertices produced by the tessellation and use that mesh for collision.

Good point! I'm coming to this in the context of interactive maps, where pretty much all data is tiled. So we can use tiles for loading the terrain mesh & adjusting level of detail too while avoiding frequent GPU memory updates. But I'm a newbie in 3D rendering, so this is more of an exploratory/learning work than something to use in production — I've heard a lot about geometry clipmaps and would love to explore them too!

Author here — thanks for checking this out, everyone! Happy to answer any questions in comments.

Not a question about the mesh generator, but if I want to create a (leaflet or mapbox) map that uses raster images as textures in vector maps, where do I start?

Similar to the Middle earth style map, but for the web: https://adventuresinmapping.com/2018/09/10/middle-earth-map-...

Just open https://studio.mapbox.com and have a go! It's a really powerful tool with a ton of customization options, including ones related to textures & patterns. Also check out one of the recent tutorials for a textured map: https://blog.mapbox.com/designing-the-treasure-map-style-431... We also have a cool guide for map design: https://www.mapbox.com/map-design/

Awesome, thanks a lot!

Did you leverage this approach to optimize terrain rendering/add detail on devices where hardware tessellation is not supported? Lovely algorithm in any case. [Edit: Just remembered the limitation is with WebGL itself, doh.]

This is awesome. I wrote a Terrain-RGB to greyscale PNG converter and would love to play around with this in a demo map for a 3D preview or something. How are you rendering the mesh in your notebook? Threejs?

All the code is there — browse to the bottom and click on the left side of ThreeJS sections to expand them.

Duh! Thanks!

great work! a little simpler minus the triangle conversion, have you seen the openFrameworks chapter for generating mesh from color saturation values? https://openframeworks.cc/ofBook/chapters/generativemesh.htm...

Haven't seen this, thanks for sharing!

Super neat! I will definitely be checking this lib out.

Firefox looks a bit wacky: https://i.imgur.com/ivLwxyG.png

Vs. Chrome: https://i.imgur.com/Go0mt1K.png

Wow, what OS / device is this on? Looks fine on Firefox 68 / OS X for me.

Firefox 68.0, OS X 10.14.6

Really weird! No idea what could be the culprit. Some GPU bug maybe?

I'm seeing similar results on FF68.0.2 Win10 with a GTX 1060.

On android firefox doesnt seem to work at all. Nor does ff preview. Chrome works.

Worked on my iPad, which is unusual for demos like that. And wicked fast! The article is beautifully written and the information presented with astonishing clarity. Well, well done.

Out of curiosity, are you running iPadOS 13 with the "Desktop Class" browser?

Works on my iPhone with iOS 12 too.

No. iPad OS 12.3.1 on a 9.7” iPad Pro

It worked on a very low end Android running chrome, runs flawlessly.

Very cool. Seems to have some striking similarity to the quadtree map used for efficient position querying of variably complicated areas.

https://en.m.wikipedia.org/wiki/Quadtree

I guess you refer to the in computer graphics commonly applied concept of Level of Detail(LOD)?

https://en.m.wikipedia.org/wiki/Level_of_detail

Did my masters project on quadtrees, specifically distributed methods for solving differential equations. Using them for mapping and loading adjacent cells is a similar application, as a lot of my work was in trying to maintain locality when flattening the structure. I had a great time writing this up, they're fantastic structures with a lot of potential.

https://github.com/MattDiesel/tftt/releases/tag/1.2

Oh yes, quadtree-like structures come up all the time when you're dealing with maps. E.g. check out this algorithm I came up with for finding pole of inaccessibility of a polygon: https://github.com/mapbox/polylabel

polylabel looks great, thank you

Hey mourner, didn't know you're on HN. Just wanted to say thanks for all the great work on mapbox-gl and the side libraries you've released!

Thank you!

This is a wonderful presentation of results and code, well done! Very nice to read.

This was a pleasure to play with on an iPad. Excellent work.

Lots of errors here on mobile:

RuntimeError: renderer could not be resolved

Browser: Mozilla/5.0 (Linux; Android 9; Nokia 7.1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/75.0.3770.143 Mobile Safari/537.36

That's surprising. Does it help to do a hard reload? Are any other WebGL demos working?

I got an error too but I am running Firefox/Sway/Nixos/AMD GPU and WebGL has never worked:

  Content Security Policy: Couldn’t process unknown directive ‘prefetch-src’
  THREE.WebGLRenderer 107 three.min.js:187:462
  Error: WebGL warning: <SetDimensions>: Failed to create 
  WebGL context: WebGL creation failed: 
  * tryNativeGL
  * Exhausted GL driver options. three.min.js:190:415
  Error: WebGL warning: <SetDimensions>: Failed to create 
  WebGL context: WebGL creation failed: 
  * tryNativeGL
  * Exhausted GL driver options. three.min.js:190:440

I love stuff like this. This is like the 5th or 6th time I've seen 3D techniques from the past become real time relevant. The first one I saw was from the 50's and someone just happened to explore it and it happened to run great on modern hardware. I bet there is a ton of stuff out there like this. I do wish there was more of a benchmarking standard. It is great that it now runs in 20ms on his laptop but that says nothing about the actual computational requirements.

Everyone's hardware is different, so I've included notes about computational complexity of the algorithm in the notebook too.

Is there a method for dealing with seams between RTIN tiles of different levels of detail? It looks like it would be complicated to implement.

I think I've seen a rather pragmatic hack that has been used in Google Earth for their stitching of terrain: They simply add a kind of skirt at the boundary of each square chunk [0], so that there aren't any white/black pixels. There may be some artifacts between LoDs but they soon disappear when the next chunk gets more refined.

Edit: I think the Google terrain skirts were slanted, rather than falling straight down, so two neighbouring skirts intersect in a V.

[0] https://www.researchgate.net/figure/A-terrain-chunk-a-withou...

Funny hack, I would have expected some perfect seam algorithm from google.

The easiest method would be downward "skirts" as mentioned above. A little more complicated one I'm thinking about is reconciling error maps on the border when an adjacent tile loads so that they split at the same point, and updating the corresponding mesh — should be fast enough to do on tile loads.

If you are getting your data from an image, you already have a mesh (a quad mesh from pixels which could be broken down into triangles a few different ways).

Anybody know about best/easy/fast/interesting algorithms for doing the opposite of the post and "compressing" the data eliminating triangles for a prescribed error or some other metric?

any raster imagery overlay come with this badboy? mourner is a maps legend - hats off to him

Thank you! Someone just forked the notebook, adding satellite texturing — that's a really cool aspect of Observable (and I'll probably merge it back): https://observablehq.com/@rzoller/martin-real-time-rtin-terr...

Wow Vladimir. Just wow.

That made it really clear that texture resolution trumps mesh resolution. Dialling down the mesh detail slider results in very little perceptual difference, but the blurry texture always stands out.

The non-textured demo actually looks better. Nothing that can't be fixed by stitching higher resolution sat imagery though!

One more question. How do you see this as effecting much of a different result from Peter Liu's work

https://blog.mapbox.com/bringing-3d-terrain-to-the-browser-w...

Is it just faster? Also, is Peter's work FOSS?

Fantastic. Love the demo and the animation.

This is slick.

Reply on news.ycombinator.com