Archived

This topic is now archived and is closed to further replies.

Keef

ROAM + triangle strips - why not?

Recommended Posts

Keef    122
Hi, I''ve been fooling around with ROAM for the last couple of weeks now. My implementation is _ok_, but not fantastic. To take it to the next level I''D like to speed things up by composing the rendered triangles into triangle strips. The common consensus is that this is a hard thing to well in ROAM. I think that this is related to the recursive nature of the rendering pass. However, I can''t help thinking that this must be doable. At the end of the day ROAM produces a triangle mesh like any other - you don''t _have_ to render it recursively. Can anybody point me to some algorithms for rendering a triangle mesh as triangle strips? I''d like to check this out. Cheers Keef ----------------------- glDisable(WORK); glEnable(GL_CODING);

Share this post


Link to post
Share on other sites
Keef    122

Hmm,

''Why not'' is ''cos composing a triangle mesh into triangle strips is NP-complete.

*shuts big mouth*

However, it might still be possible to get a good improvement using a heuristic algorithm. Has anybody tried this?

Keef


-----------------------
glDisable(WORK);
glEnable(GL_CODING);

Share this post


Link to post
Share on other sites
Keef    122
quote:
Original post by masonium
This is a little off topic, but where did you get information about ROAM implementation?


Most of my information came from the stuff at the virtual terrain project.

http://www.vterrain.org/LOD/Papers/index.html

On here you can find a link to a GamaSutra article that implements a split only ROAM. I''ve adapted this to a frame coherent version (without priority queues).

Cheers

Keef


-----------------------
glDisable(WORK);
glEnable(GL_CODING);

Share this post


Link to post
Share on other sites
xyzzy00    307
Ok.. think of the subdivisions of the terrain as being represented by nodes in a triangle bin-tree. Imagine traversing the tree in depth-first order, making a list of the tessellated polygons. One thing you should notice is that the triangles are all adjacent, and make nice little fan patterns.

This has a couple implications.. 1) fans are hard to trivially convert into strips without introducing all kinds of degenerate vertices.. and 2) if you just draw the triangles as an indexed triangle list, you will get about the same performance as strips, since for every triangle 2 of the last 3 vertices are already in the vertex cache. So.. I wouldn''t worry about triangle strips.. and be happy with indexed triangle lists.

ROAM is a great software algorithm. The thing that kills hardware performance of ROAM is that it requires a new set of vertices to be computed and uploaded to the card each frame.

xyzzy

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
quote:

ROAM is a great software algorithm. The thing that kills hardware performance of ROAM is that it requires a new set of vertices to be computed and uploaded to the card each frame.



That doesn''t kill performance at all, if you now what you are doing. Ever heard of vertex_array_range and NVFence ?

Share this post


Link to post
Share on other sites
D    128
Finding the "best" triangle strip in an arbitrary model is of complexity O(n!), where n is the number of triangles in the model. (at worst).

I found this out when trying to convert a 3ds model to a triangle strip based model format (for my engine), however I soon realised that I''d have to spend hours of prepreocessing (probably an infinite amount of time). (+ Without a nice algorithm).

Also on the other hand I would suggest just generating the triangles each turn - the points, texture coordinates etc (that have changed!), and then sending all that to the renderer in one fell swoop. Also I would make it so the points, once they are no longer required for the one frame be kept in the buffer for a short amount of time, since then the next frame after could possibly contain them. This would mean less reallocation of memory.

Dæmin
(Dominik Grabiec)
sdgrab@eisa.net.au

Share this post


Link to post
Share on other sites
EvilDecl81    360
quote:
Original post by Anonymous Poster

That doesn''t kill performance at all, if you now what you are doing. Ever heard of vertex_array_range and NVFence ?



Naturally, thats why the video cards support HW vertex buffers. Just a useless feature, why should we be spending money on extra UNNECCISARY gates on the Hardware, when it doesn''t have any perf wins? Its a conspiracy I tell you! Just like the programmable shader thing - who needs that? Why can''t all our games look like molded plastic like they used to? Oh, the Humanity!

On a more serious note, touching your vertex buffer is generally a baaaaad thing, bording on evil. SIGGRAPH 2001 there was a great presenation by Muckyfoot? (sorry,err, can''t remember that far back) on why ROAM was a not a good idea on current hardware. After months and months of work there was no evidence of any perf improvement, a simpler algorithm that simply drew more did a better (visual) job because it didn''t have to touch the vertices and construct geometry. There adivice: Precompute everything, put on video card, do not touch by the host CPU.
Its easier. Its faster, it looks better.




EvilDecl81

Share this post


Link to post
Share on other sites