9 ms·
Martini: Real-Time Terrain Mesh Generator
- aerodog 7y agoany raster imagery overlay come with this badboy? mourner is a maps legend - hats off to him
- mourner 7y agoThank 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-terrain-mesh https://observablehq.com/@rzoller/martin-real-time-rtin-terr...
- aerodog 7y agoWow Vladimir. Just wow.
- kuzehanka 7y agoThat 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!
- aerodog 7y agoOne 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-with-three-js-410068138357 https://blog.mapbox.com/bringing-3d-terrain-to-the-browser-w... Is it just faster? Also, is Peter's work FOSS?
- isoprophlex 7y agoThis is a wonderful presentation of results and code, well done! Very nice to read.
- mourner 7y agoAuthor here — thanks for checking this out, everyone! Happy to answer any questions in comments.
- spython 7y agoNot 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-style/ https://adventuresinmapping.com/2018/09/10/middle-earth-map-...
- mourner 7y agoJust open https://studio.mapbox.com 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-4318390ad81c 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/ https://www.mapbox.com/map-design/
- spython 7y agoAwesome, thanks a lot!
- num3ric 7y agoDid 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.]
- colkassad 7y agoThis 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?
- throwaway13337 7y agoVery 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 https://en.m.wikipedia.org/wiki/Quadtree
- Lindenmayer 7y agoI 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 https://en.m.wikipedia.org/wiki/Level_of_detail
- mdiesel 7y agoDid 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 https://github.com/MattDiesel/tftt/releases/tag/1.2
- mourner 7y agoOh 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 https://github.com/mapbox/polylabel
- Uehreka 7y agoThis was a pleasure to play with on an iPad. Excellent work.
- tomcam 7y agoWorked 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.
- doctoboggan 7y agoOut of curiosity, are you running iPadOS 13 with the "Desktop Class" browser?
- layoutIfNeeded 7y agoWorks on my iPhone with iOS 12 too.
- tomcam 7y agoNo. iPad OS 12.3.1 on a 9.7” iPad Pro
- notjtrig 7y agoIt worked on a very low end Android running chrome, runs flawlessly.
- thrax 7y agoThis is slick.
- kmnt 7y agoIs there a method for dealing with seams between RTIN tiles of different levels of detail? It looks like it would be complicated to implement.
- wnkrshm 7y agoI 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-without-skirts-and-b-with-skirts_fig2_235952216 https://www.researchgate.net/figure/A-terrain-chunk-a-withou...
- kmnt 7y agoFunny hack, I would have expected some perfect seam algorithm from google.
- mourner 7y agoThe 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.
- mattlondon 7y agoLots 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
- mourner 7y agoThat's surprising. Does it help to do a hard reload? Are any other WebGL demos working?
- ingenieroariel 7y agoI 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
- _bxg1 7y agoFantastic. Love the demo and the animation.
- pastrami_panda 7y agoCool! 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!
- kuzehanka 7y agoYep. A uniform mesh of flat quads with a vertex shader doing the displacement will perform better.
- mourner 7y agoWould 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)?
- kuzehanka 7y agoIt'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 https://imgur.com/a/51g2bB4
- colechristensen 7y agoIf 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?
- edoo 7y agoI 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.
- mourner 7y agoEveryone's hardware is different, so I've included notes about computational complexity of the algorithm in the notebook too.