Author Topic:   Priority Queue from ROAM
posted October 05, 1999 04:38 AM            
The ROAM algorithm states the use of a priority queue, like this:

while( nTrianglesDrawn < nTriangleBudget ){

However, you have stated that you don't try to converge on the desired triangle count by adjusting the error; in that case, you don't need a priority queue, right? You just need, say, a stack or a queue, to store triangles:

fErrorForNextFrame = MagicalFormula(fErrorForLastFrame, nTrianglesDrawnInLastFrame);
while( StackNotEmpty() ) {
if( triangle.error > fErrorForNextFrame ){
split(triangle); // pushes children in stack
} else {

I just hit me that I do the expensive priority queue without actually needing it...

btw the TreadMarksDemo2 kicks so much ass...
everyone I show it is wowed


LDA Seumas
posted October 05, 1999 12:26 PM           
Actually, I don't think your second example will work as stated, unless there's something I'm missing. The problem is that you can't just draw a triangle the instant you test it and find its variance is below your split threshold, because it may have a neighbor that is above your split threshold that hasn't been split yet, and will be split yet this frame; if that neighbor split would force your already drawn triangle to split, you have a crack. AFAIK you have to make two passes, no matter how you do things; first split the tree(s), then go through them again and draw them.

If your first pseudo code example is the way that ROAM priority queues work, it does seem like a bit of overkill. Though if you had a totally frame coherent algorithm, with coherent priority queues (and perhaps the trees themselves essentially stored in the priority queues), I can see how it could work.

Glad you like the game.

-- Seumas McNally, Lead Programmer, Longbow Digital Arts


posted October 05, 1999 12:57 PM            
Yes, of course there is a second drawing pass. Sorry for the pseudocode, I hope nobody has taken it seriously
During the second pass I do triangle fan accumulation. Right now I have only one "current" fan, and when I cannot add the next triangle to it, I just output it; I think however about maintaining several "current" fans (or strips?), and discarding (sending to OpenGL, or just adding to a simulated execute buffer) one of them (the shortest? the longest? the one which didn't absorb any triangles for the longest time?). This way I could potentially accumulate much longer strips/fans than the 3.5 average you mentioned a while ago.

In ROAM (I admit I haven't implemented it) you should have two priority queues which work approximately like that: you take the roughest triangles and split them, and you take the smoothest diamonds and merge them. I think that's the way to go, if you high polygon counts - with cards that can easily handle 50 000 tris just for the terrain (in 9 months maybe?), you cannot afford to rebuild the tree every frame.