Tell HN: My 3D terrain in Flash just went online
17 comments
What CLOD (continuous level of detail) algorithm did you use? The effect looks a little like the one described by Lindstrom and Pascucci in "Visualization of Large Terrains Made Easy."
Anyway, nice job. When I implemented ROAM and then Lindstrom/Pascucci's algo 8 years ago it ran like a dog on an antiquated SGI - I never would have dreamed something like this would run on the browser some day :)
Edit: Ah - never mind, I see you reference ROAM another comment. If you haven't read the paper referenced above you may enjoy it: http://www.pascucci.org/pdf-papers/vis2001.pdf
Anyway, nice job. When I implemented ROAM and then Lindstrom/Pascucci's algo 8 years ago it ran like a dog on an antiquated SGI - I never would have dreamed something like this would run on the browser some day :)
Edit: Ah - never mind, I see you reference ROAM another comment. If you haven't read the paper referenced above you may enjoy it: http://www.pascucci.org/pdf-papers/vis2001.pdf
Yep, I've read that paper. What I did was actually simpler than any paper I've seen, so I will just describe it here.
The basic data structure is taken from ROAM: a bintree of right triangles. It is regenenerated from scratch on every frame, recursively, starting from several top-level triangles. (So it's technically a multi-tree, I guess.) A triangle is split if the midpoint of the hypotenuse has a screen-space error of more than 10 pixels. Each triangle knows its children and neighbors, so each split can cause neighboring triangles to split to avoid T-junctions. (This was by far the trickiest part of the code, similar in difficulty to balancing a red-black tree.) I also take many not-quite-correct shortcuts, like stopping the splitting process if the triangle lies completely behind the camera or outside the screen bounds.
I believe the main reason my engine looks so good is because it uses satellite photos for textures - they hint at a lot of 3D detail that isn't expressed by the triangles. I render only 1 or 2 thousand triangles per frame, but they pretend to be a lot more, if you don't look at the ridges too closely. Try the m and i keys to look under the hood.
The basic data structure is taken from ROAM: a bintree of right triangles. It is regenenerated from scratch on every frame, recursively, starting from several top-level triangles. (So it's technically a multi-tree, I guess.) A triangle is split if the midpoint of the hypotenuse has a screen-space error of more than 10 pixels. Each triangle knows its children and neighbors, so each split can cause neighboring triangles to split to avoid T-junctions. (This was by far the trickiest part of the code, similar in difficulty to balancing a red-black tree.) I also take many not-quite-correct shortcuts, like stopping the splitting process if the triangle lies completely behind the camera or outside the screen bounds.
I believe the main reason my engine looks so good is because it uses satellite photos for textures - they hint at a lot of 3D detail that isn't expressed by the triangles. I render only 1 or 2 thousand triangles per frame, but they pretend to be a lot more, if you don't look at the ridges too closely. Try the m and i keys to look under the hood.
Thanks for the explanation - very cool!
mousewheel for tilt doesn't work in my MacBook Pro.
Have a look at,
http://www.judahfrangipane.com/blog/?p=237
or
http://brandonaaron.net/code/mousewheel/docs
for ideas on how to solve it.
for ideas on how to solve it.
Thanks! I think I fixed it. Clear your cache and try again.
Nice work. It's working on my MBP now.
http://kosmosnimki.ru/3d/index.html?x=235543&y=5030526
Barcelona, where I live :)
Barcelona, where I live :)
Ooh you're lucky. The inspiration for my previous "fun" project, openphotovr.org, came after I visited Barcelona and saw Sagrada Familia. Here it is: http://openphotovr.org/view.html#a57 :-)
Nice project, you can view different angles and zoom in to see de details :)
I created a similar (but much much less refined) 3D topo view using the national elevation dataset. I used Papervision and I wasn't too happy with the results (it's slow!). Granted, my algorithm for layering a bicycle route on top is not efficient, but just the mesh creation itself is not that great.
Did you try it with more naive mesh code? Meaning, applying a fixed triangle count, not varying the triangles based off the underlying elevation variation? My implementation with a fixed triangle count just bogs down like crazy when I add enough to get good detail in the mountains, and I never got around to a more intelligent method like yours.
Do you have any good links for me to read up, or is this just a large background of computer graphics? I have little computer graphics background, which made implementing a 3D terrain map a two week process for me.
Did you try it with more naive mesh code? Meaning, applying a fixed triangle count, not varying the triangles based off the underlying elevation variation? My implementation with a fixed triangle count just bogs down like crazy when I add enough to get good detail in the mountains, and I never got around to a more intelligent method like yours.
Do you have any good links for me to read up, or is this just a large background of computer graphics? I have little computer graphics background, which made implementing a 3D terrain map a two week process for me.
Yes, I did an experiment with a uniform mesh about a month ago. It turned out to be a choice between awful detail level, miniscule view distance or unusably slow framerate, so I abandoned it after a day. But it was a useful experiment because it really made me understand my triangle budget.
I do have a large background in computer graphics. If I lost the knowledge and had to reconstruct it again, I would begin by writing simple demos in the lowest level environment I could find. Forget Papervision, try making a spinning textured cube by assigning colors to individual pixels using C code. This way you pick up the background awfully fast.
I do have a large background in computer graphics. If I lost the knowledge and had to reconstruct it again, I would begin by writing simple demos in the lowest level environment I could find. Forget Papervision, try making a spinning textured cube by assigning colors to individual pixels using C code. This way you pick up the background awfully fast.
This is really interesting. I work for a company that maps the seabed and generating 3D models is part of the job. We have an application that renders the points into a 3D model. For this, how do you go about rendering the map? Got any tips? Where should I start?
The intermediate steps of development were as follows:
1. Draw a big rectangle of flat-shaded ground (no textures, no heightmaps) tiled into triangles of equal size. Mouse navigation to fly over it.
2. Move the vertices vertically according to a formula - a procedural heightmap - e.g. a sine wave.
3. Add subdivision of triangles into smaller triangles as needed, like in ROAM (http://www.llnl.gov/graphics/ROAM/roam.pdf).
4. Solve hidden surface removal. This is easy because the triangles form a bintree-like structure, treat it as a BSP and draw back to front.
5. Implement loading of texture tiles. (Do you have those?) The scale of the texture to load for each triangle depends on its transformed Z value.
6. Implement loading of heightmaps in your preferred format.
7. Debug, optimize, debug, optimize, debug, optimize.
1. Draw a big rectangle of flat-shaded ground (no textures, no heightmaps) tiled into triangles of equal size. Mouse navigation to fly over it.
2. Move the vertices vertically according to a formula - a procedural heightmap - e.g. a sine wave.
3. Add subdivision of triangles into smaller triangles as needed, like in ROAM (http://www.llnl.gov/graphics/ROAM/roam.pdf).
4. Solve hidden surface removal. This is easy because the triangles form a bintree-like structure, treat it as a BSP and draw back to front.
5. Implement loading of texture tiles. (Do you have those?) The scale of the texture to load for each triangle depends on its transformed Z value.
6. Implement loading of heightmaps in your preferred format.
7. Debug, optimize, debug, optimize, debug, optimize.
Hint: To find any place in the world just browse the map in http://kosmosnimki.ru/ and then click 3D (I can't read cyrillic but fortunately 3D is in latin alphabet)
Really nice! A few months ago I spent some time thinking about the idea of porting my master thesis project (Charack: Pseudo-infinite 3D virtual world generation, http://news.ycombinator.com/item?id=822103) to AS3, but I dropped the idea because of Flash limitations.
You gave me some hope now :)
You gave me some hope now :)
Either the topo data is wrong or something is not rendering right. Take a look at http://kosmosnimki.ru/3d/index.html?x=-13348730&y=472501...
Yep, seems to be a hole in our SRTM dataset. Such things happen. I'd certainly like a better dataset, because the current one is cut off at 60N and excludes a huge part of Russia.
I really like the control scheme: vertical drag to move, horizontal drag to change view heading. It was a bit confusing for the first few seconds but it feels much more intuitive than Google Earth, for example.
Thanks! I looked at the control schemes of all popular 3D maps and decided to make something better :-) It helps that terrain, unlike 2D map data, has a certain natural scale, so tilt can be tied to camera altitude.
Why are urls not linkified in these textual posts?
It's deliberate. I believe pg said it's to stop people effectively giving themselves the top comment on a link. Which is exactly what the submitter is trying to do here. Of course, he's the author of the link so it's fair enough. I guess pg would want him to add his comment like everyone else; or put the comment on the webpage itself; or put up with a unlinkified url.
Personally, I think it's a bit of overkill for a specific problem (and I don't know if it actually occurred in practice, or it was only predicted that it would occur). Maybe the HN community can be trusted to not abuse linkified links? OTOH, it's an extremely minor niggle, and I agree that pg's time is better spent on preventing spam and keeping the community civil etc. That's way more important.
Meta-discussion like this is frowned upon, but I wanted to answer your question and also offer a solution: I solve this problem with a customable dictionary lookup addon for firefox, by adding a rule that just opens the highlighted string directly. I come across unlinkified URLs quite often.
Personally, I think it's a bit of overkill for a specific problem (and I don't know if it actually occurred in practice, or it was only predicted that it would occur). Maybe the HN community can be trusted to not abuse linkified links? OTOH, it's an extremely minor niggle, and I agree that pg's time is better spent on preventing spam and keeping the community civil etc. That's way more important.
Meta-discussion like this is frowned upon, but I wanted to answer your question and also offer a solution: I solve this problem with a customable dictionary lookup addon for firefox, by adding a rule that just opens the highlighted string directly. I come across unlinkified URLs quite often.
Any chance you could release the source code? I'd love to play around with this and add some other datasets.
I'd certainly like to, but this was developed for my employer and would have to be cleared through them. Me and one other guy are trying to make the place more open source friendly, but it's slow.
Does this have any applications for game development?
Game developers today can afford to draw millions of triangles per frame running their terrain engines on their fast GPUs. Flash can't use GPU rasterization yet, so I had to use exceptional cleverness to fit in the budget of 1-2 thousand triangles per frame without visible popping. Maybe this could be useful for Flash games, though.
Mousewheel doesn't work in Chrome / Ubuntu 10.04
ROAM?
Nope. I don't adapt the mesh from frame to frame, I rebuild it completely on every frame. That's the first half of the "msec" diagnostic, so you can see I optimized that part quite a bit. The general idea (bintrees of right triangles, splitting based on screen-space error) is indeed taken from the ROAM paper, but everything else from that paper I threw away and made up my own algos.
Nice, and very fast indeed. Only thing I don't like is the inverse control, maybe because I'm hardwired to maya viewport. Keep up the good work, nice to see flash isn't dying out. Can't wait to see that rumored 3D API.
Nice! But with a loading in progress bar would be even nicer ;)
Flash Player 10 required. Allow for some delays in loading because our servers are in Russia.
Controls: drag to move, mousewheel to tilt. Secret tips for fellow hackers here: i toggles stats, m toggles mesh, t shows textures, s shows strips.
The location is Russian Caucasus, images are from IRS satellite, heightmaps are SRTM.
Actually we (my employer http://kosmosnimki.ru, a Russian online map) have covered the whole land area of the world below the 60th parallel. Changing the x and y parameters in the URL bar allows you to go elsewhere. Numbers are in meters, Mercator projection, WGS84 datum. I especially recommend the Himalayas, the Andes and Kilimanjaro, if you're smart enough to figure out the right numbers :-)
The code was written by me alone from scratch during this week. Two days of scribbling in a notebook until it got clear, then two days of frantic coding. No existing 3D engines like Papervision were used, it's all pure AS3 (well, haXe). About 1000 lines in total.
Any questions are welcome, especially questions about algorithms!