Archived

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

GekkoCube

fast collision detection with my version of a quadtree.

Recommended Posts

Let me see if i can explain this clearly. I have a quadtree. Each node has a set of vertices that makes up a triangle fan. This tree is built after I process all of the vertices from top-left to bottom-right order, row by row and left to right. So for example, i have a 16x16 grid (16x16 vertices) in which i store all its vertices into a simple list. Then as i create my tree, i have this algorithm that will take the proper vertices that are adjacent to each other, effectively setting up each node with its own triangle fan list. This works great, about 70fps for this terrain. And having the original vertex list allows me to do fast collision detection by simply indexing thru it with respect to any (X,Z) coordinate. Now here is the part that has been making my eyes fatigued... I want to draw using triangle strips, not fans. Also, some issues that popup that never was an issue using fans... 1) Drawing a bunch of strips while still using a quadtree (remember, each node has a set of vertices, which used to be a single fan, and i certainly dont want to call a drawprimitive function for each node to be drawn - i need to efficiently batch as many of the nodes'' vertices together so i can call drawprimitive as few times as possible). 2) Before, collision detection was fast and simple using the old indexing into the list thing. But with triangle strips, i think it will be more complicated than just indexing since that list of vertices will not be in a simple linear order (due to the arrangement of triangle strip vertices), they cant left-to-right for each row as that will cause undesirable triangles.) Thats it...I know this sounds confusing and maybe complicated. Then again, perhaps its simple and I am the one making it overly complicated. I just need a fresh pair of eyes (and brain) to view this as I am stuck at this dilema. Eternally grateful.

Share this post


Link to post
Share on other sites
wheres the problem with storing vertices the same way and just change the way you index them? might not be as cache friendly but so what? reading the vertices back all the time for collisions isnt that great for your performance anyway (the only reason why i keep the heightmap in memory is not to touch the vertices more than i have to).

Share this post


Link to post
Share on other sites
Search for the Chuncked LOD algorithm. It has a nice way to deal with rendering terrain with fewer glPrimitive calls. Basically, if the LOD get''s too high (and the amount of triangles too low to render in a single call), it renders the parent node of the quadtree instead of the node itself. The parent node will render it''s four children in one go.

+ less primitive calls. Scales very well
- nodes that have been culled away by the frustum may still get rendered through their parent which tries to optimize the batch

Sander Maréchal
[Lone Wolves Game Development][RoboBlast][Articles][GD Emporium][Webdesign][E-mail]


GSACP: GameDev Society Against Crap Posting
To join: Put these lines in your signature and don''t post crap!

Share this post


Link to post
Share on other sites