Archived

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

Mr Grinch

How to draw vertices in terrain patch

Recommended Posts

Mr Grinch    318
Ok, so this seems like it ought to be pretty simple. I currently have a terrain rendering system that uses a quadtree for frustum culling and no LOD. I render the leaf nodes of the quadtree using a display list. Each display list consists of multiple triangle strips, sort of one for each row in heightmap. I am trying to move towards using a vertex array (and eventually maybe a VBO). I am planning on using one interleaved array for all my vertex, normal, and texture coordinate data and giving each leaf node an index array. However, I''m having some trouble figuring out exactly how I should draw the terrain patch (ie leaf node). If each patch only gets one index array, I can''t do the multiple triangle strips like I did before, right? I''ll tell you my current plan, and let me know what you think. Let''s say we have a 3x3 patch, with vertices 0-8 in these locations:
0--1--2
|  |  |
3--4--5
|  |  |
6--7--8
Currently, in my display lists, I draw one strip that is in this order: 0, 3, 1, 4, 2, 5. Then a strip of 3, 6, 4, 7, 5, 8. I was thinking that I could draw on strip for the whole patch in this order: 0, 3, 1, 4, 2, 5, 5, 8, 4, 7, 3, 6. I believe repeating vertex 5 would draw 2 triangles you wouldn''t see and allow the use of one triangle strip. What do you think? Are there better or simpler ways of doing this? I''d be curious to hear how some of you do this. Thanks for the help.
My 3D Pirate Game is in need of a better name, want to help?

Share this post


Link to post
Share on other sites
Mr Grinch    318
I forgot to ask, are triangle strips even worth bothering with? I think using glBegin/End they gave me a big improvement, but maybe with vertex arrays or VBO''s it wouldn''t be as big a deal. It seems like you have a lot of repeated verticies with regular triangles, though. What do you think?


My 3D Pirate Game is in need of a better name, want to help?

Share this post


Link to post
Share on other sites
Lutz    462
Your first question with the generalized triangle strip: I think repeating a vertex should work. You might want to have a look at the SOAR algorithm. I know that they also draw a triangle strip repeating vertices (but for a bintree --> more complicated). See this link.

Your second question:
If you use VBOs, it all depends on how expensive your per-vertex calculation is. Since all the stuff (vertices, normals etc.) is already in VRam, it can't be too expensive to access it. If you don't do lighting and only simple texturing, your per-vertex calculation is cheap and you should be fine with triangles. If you have an expensive vertex-program running doing some atmosphere stuff, then you should use tristrips.

BTW: Why don't you store an index array for every row of your terrain patch? That would work exactly like your tristrips (0,3,1,4,2,5 and 3,6,4,7,5,8), except you don't have to upload vertex/normal/etc. data all the time.

[edited by - Lutz on May 26, 2004 6:55:14 AM]

Share this post


Link to post
Share on other sites
ghauss    140

This is pretty much how Chunked LOD draws terrain patches, using triangle strips and degenerate triangles (repeated vertices).

A terrain patch is tesselated using the Lindstrom-Koller algorithm (from SIGGRAPH ''96 I think) and then a huge tristrip is generated--up to 64k individiual vertices, although I usually keep it down to 20k. The "corner turns" are handling using 1, sometimes 2, repeated vertices to generate degenerate triangles as needed, in order to allow the patch to be represented as one big tristrip.

I works pretty well, but for nasty terrain the ratio of degenerate triangles to actual triangles gets pretty high, maybe 40 percent. So in certain situations you might still be better off using triangles lists instead of triangle strips.

Gary

Share this post


Link to post
Share on other sites
Mr Grinch    318
I got this going, so I thought I''d give an update (if anyone cares). I ended up having to draw two "extra" vertices in order to keep the rows that worked backwards facing the same direction. The opengl face culling would take out those entire rows, otherwise. Going back to my vertices from the original post, I ended up having to draw like this: 0, 3, 1, 4, 2, 5, 5, 5, 8, 4, 7, 3, 6. I guess I haven''t compared performance with the extra vertex to just turning off back face culling, but I feel like I just want it to cull correctly. Maybe I''ll see how it compares.

I''m running a little benchmark now that I wrote to compare the performance to the old display lists method. I think it''s a little bit slower, but not too much. I was going to try glLockArraysEXT, but couldn''t figure out how to get it working (in linux). I didn''t spend more than 5 mins on it though. Perhaps I''ll try out VBO''s now, too.

Does anyone have any thoughts on locked arrays and VBO''s? Any advice or warnings or performance tips before I get started?


My 3D Pirate Game is in need of a better name, want to help?

Share this post


Link to post
Share on other sites