Archived

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

Collision detection algo. question

This topic is 5111 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''ve read this article "A real-time algorithm for accurate collision detection for deformable polyhedral objects" and I''m a bit curious if someone has some tips on how to implement the occtree-recursion step without building the tree. According to my calculations it will never fit on the stack.

Share this post


Link to post
Share on other sites
Haven''t read the paper, but i know about octrees, and i''m not sure why you''re trying to avoid building the tree itself. Infact, if you don''t build a tree, then you''re not using an octree (just an "oct"?).

If your worried about octree nodes fitting on the stack, raise the amount of polygons that''ll fit in a node. The higher the poly amount per node, the larger the nodes become, and less of them show up.

Now, if you''re talking about a non-recursive solution to the problem, well, that''s different. Give each node an index value, and have it contain the index value of the children it points to. Radix sort the array of nodes based upon index value (so that the 0th position is the largest node volume). After you check 0, you can check each of it''s children using a while loop, rather than recursion.

~Main

==
Colt "MainRoach" McAnlis
Programmer
www.badheat.com/sinewave

Share this post


Link to post
Share on other sites
The algorithm in the paper "rebuilds" the tree at every update. The thing is that it doesn''t actually have to be build. It says that a recursive function can be used instead. This is my problem, cause then I have to build lists with faces to send further down in the "tree". And those list can be huge, so maybe some indexed system can be used. The thing is that it''s used for collision detection so the recursion stops if a subspace only contains faces from one object.

Share this post


Link to post
Share on other sites