So I read this whitepaper here "http://www.graphicsinterface.org/cgi-bin/DownloadPaper?name=2002/139/paper139.pdf" In the paper they basically use a quad-tree subdivision method to generate points for the new tri's to be added when resolution is upped. The thing I dont get is how they maintain this "uniform grid" When a triangle has to be force-split because of a seam edge. I may be completely missing the usage of the terrain cells altogether but I dont think so...any insights would be appreciated! Oh by the way any one out there familiar with ROAM v 2.0 and the new way of managing things with the diamond? seemed a bit tricky to me as well - R

Quote:Original post by Richard3d
So I read this whitepaper here http://www.graphicsinterface.org/cgi-bin/DownloadPaper?name=2002/139/paper139.pdf In the paper they basically use a quad-tree subdivision method to generate points for the new tri's to be added when resolution is upped. The thing I dont get is how they maintain this "uniform grid" When a triangle has to be force-split because of a seam edge. I may be completely missing the usage of the terrain cells altogether but I dont think so...any insights would be appreciated! Oh by the way any one out there familiar with ROAM v 2.0 and the new way of managing things with the diamond? seemed a bit tricky to me as well - R

Those are two vastly different questions.

The ROAM 2.0 one I can help out with. Would you like it in this thread or another?

As for the idea of keeping a uniform grid when you split triangles: there are several ways to handle the differences that will crop up when you play in the CLOD (Continuous Level of Detail) geometry pool. The Good Old Days (TM) of terrain rendering required a very rigorous system for CLOD mesh management since the goal was to eliminate as many triangles from being sent to the renderer as possible. That said, the paper you're referencing is from 2002. Things have changed since then, and unless you're under force of gunpoint, I don't think you'd be best-served by an algorithm which put that many CPU cycles saving precious triangles that your graphics card could take and eat up like skittles.

Still. Far more friendly ROAM whitepapers: Mark Duchaineau's ROAM stuff and, my favorite ROAM paper.

And, yeah, ROAM 2.0 is nice. I like it. Not as much as I like Thatcher Ulrich's Chunked-LOD sexiness. But I like it. Here's Duchaineau's homepage for ROAM 2.0. I'm on there with my name spelled wrong. So I might be able to offer some help.

[Edited by - mittens on July 25, 2007 10:00:18 PM]

Hey Trent thanks for the reply. I am not interested in ROAM for LOD management but rather as means to subdivide terrain on the fly, to support destrubctible terrain. THere have been algorithms on fracturing patterns for geometry and I plan on using these in conjuction with ROAM to add geometry only when I need to. I am very aware of the triangle munchin' power available on today's hardware ;) Indeed my questions were very different, however You can keep replying answer to both of them here - R

Quote:Original post by Richard3d
Hey Trent thanks for the reply. I am not interested in ROAM for LOD management but rather as means to subdivide terrain on the fly, to support destructible terrain. There have been algorithms on fracturing patterns for geometry and I plan on using these in conjunction with ROAM to add geometry only when I need to. I am very aware of the triangle munchin' power available on today's hardware ;) Indeed my questions were very different, however You can keep replying answer to both of them here - R

Well, while I'm all about turning people onto CLOD algorithms, I don't think this is really the kind of solution you're looking for if your reasoning for an algorithm like ROAM is destructible terrain.

CLOD algorithms are a fantastic way of displaying geometry for terrain meshes (mostly very large ones), but let me tell you: it takes a decent amount of work to make an algorithm like ROAM and, especially, ROAM 2.0 work well with dynamically-changing terrain.

What kind of terrain dataset size are you looking to be rendering?

Hey Trent,

I guess I should have prefaced this whole thread with some of this info: I am looking at rendering a massive terrain. Probably something along the lines of Crysis or Virtual Battle Space 2 / ArmA. I am not a novice to graphics programming but I have little experience in the realm of terrain. Most of my work has been in graphics engine development (shader/post processing piplines, material editing tools, etc). I checked out the Chunk LOD site you sent me but I couldnt find a white paper explaining the algorithm on it. I have done an initial sruvey of techniques and I would like to know your opinion on each one and also which ones would best suit my needs (it will def help me get up to speed). I need an extremely large terrain maybe (50 km x 50km), which ideally would be dynamic/destructible.

Geo mip-mapping: still researching this one - if you knwo more about it ro good links hit me up.

Geo-clipmaps - saw this in GPU gems 2 (I have dealt with texture clip maps, not sure how reasonable this technique is for terrain)

Chunk LOD - seems good for managing a large data set and possibly could be used in conjunction with ROAM for accomplishing what i want.

thanks again - R

Well, to start, the grand-daddy of links to Terrain Rendering can be found over at VTerrain.org or, more specifically, http://vterrain.org/LOD/Papers/index.html. There is a wealth of links there to most of the well-known terrain algorithms which have had whitepapers devoted to them over the course of the last decade or so.

Terrain Geometry Clip Maps
I don't have any actual implementation experience with this one, but I've seen it in action and have looked over the whitepaper a few times and it seems like a fantastic algorithm -- though I don't believe an implementation of it would be a walk in the park to code up... That said, if you're looking for a very GPU-friendly algorithm, I'd think this is a fantastic one. According to VTerrain, GPU Gems 2 has even more information on this algorithm where the terrain is, and I quote, "stored as a set of vertex textures, thereby offloading nearly all computation to the GPU."

I don't even know what that means, but it was done by a man far smarter than myself, so I'd take that as a truth. If there's anyone who has more familiarity with the implementation details of this algorihtm, I'd love to hear them.

Geomipmapping
Here's an algorithm I actually have a great deal of experience with. It is, fundamentally, based on the same principle set as Thatcher Ulrich's Chunked-LOD algorithm, in that you have "chunks" of vertex data which make up your terrain grid, and each of these chunks has multiple levels of detail which it can switch between based on what is demanded of them. The benefits of the algorithm are as you'd imagine: you have a great deal of flexibility with choosing your LOD and, if you're willing to use up the memory, you can compute the vertex buffers for each chunk's levels of detail as a preprocessing step, and then just swap the various LOD vertex buffers on demand.

The problem with this approach is that, for the most GPU-efficient solution to rendering of a mesh, the memory overhead is a bit of a killer. That said, I'm sure with a little bit of effort, you'd be able to find a nice little happy medium for mesh rendering vs. memory overhead with some clever chunk paging methods. Aside from Willem de Boer's paper (who, if I remember correctly, originally coined the term), there's a book by the name of Graphics Programming Methods where I wrote a chapter on Geomipmapping and ROAM 2.0. It's nothing special, but it's a great book in general, and I had some fantastic input from some of the other authors involved with book in regards to my chapter (one of whom was, actually, Willem de Boer).

Chunked LOD
This may be my favorite terrain rendering algorithm that I've never used. While it may be a bit difficult to track down some decent implementations outside of Thatcher Ulrich's own, I still think this is good solution to rendering very large meshes. Ulrich's homepage should have a great deal of resources available for research into the algorithm and his personal implementation. The downside to this technique is similar to the large dataset downsides for the Geomipmapping idea I gave: the terrain data for paging in at run-time comes with a fairly rough overhead. And, on top of that, the preprocessing steps for a decent implementation of Chunked-LOD are rough -- made worse depending on what kind of visualization management structure you choose to attach to the technique (I believe Ulrich uses a quadtree).

And that's a run down of those algorithms. I would have given more on Chunked-LOD but, as I said, I haven't implemented it, and Ulrich's own homepage should have more than enough resources for you to start researching the technique if it interests you.

Building a ROAM engine is pretty hard, as my experience has taught me. But the results are pretty cool as well. We currently have a spherical ROAM engine up and running which is capable of handling planetary terrain from orbit all the way down to the ground. In theory the engine should also be able to handle changes in the terrain, if kept to a reasonable level. No giant meteors the size of Texas hitting the earth, but artillery shell craters should be no problem.

The mesh generator is fully decoupled from a data-providing component that delivers the elevation data on demand. Texturing and normal-mapping is done using a clip-mapping technique.

Analyzing other methods, I would say that the GPU-based clip-mapping technique is definately the fastest out there if you generate the terrain on the fly. Its only bottleneck when visualizing is the amount of data you need to feed it to keep those maps filled, especially when doing low-altitude or ground-level stuff. Also for 'real' planets, you get into all kinds of trouble when you're near the poles because of their reliance on a rectangular data grid...

If you're not really interested in planetary scale terrain but 'just' a rectangular patch of a few (hundred) square km my advice would be to get the GPU Gems 2 book and read the GPU-based geometry clipmapping article several times.

Hey Everyone thanks for the awesome responses, first of all there was a question about vertex textures. I understand they just mean textures looked up in the vertex shader (not available until SM 3.0). The last poster replied that speed of texture loads in the vertex shader is bound by number tex dimensions i.e. 1d, 2d, indeed I have seen this. Overall I am thinking very long term as to possibilities in Dx 10 for handling dynamic terrain even better. ROAM style splits could be implemented in the g-shader it seems while using vertex texture reads to intially offset geometry? Well just some future thoughts. I will be reading geo-clipmaps this weekend. I will keep posting with my findings. thanks again - Richard

Quote:Original post by El Greco
Analyzing other methods, I would say that the GPU-based clip-mapping technique is definately the fastest out there if you generate the terrain on the fly... Also for 'real' planets, you get into all kinds of trouble when you're near the poles because of their reliance on a rectangular data grid...

You can combat this one by making your planet an 'exploded' cube (I think Infinity is using this approach, among others).