Archived

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

drslush

BSP Trees with collision detection

Recommended Posts

drslush    122
I''ve been reading alot in this forum lately about how BSP trees are somewhat obselete for use in rendering, with octrees beeing favored for most types of scenes. However, I was wondering if this presents problems with collision detection. Finding the intersection between a 3d mesh and a ray is fast when using a BSP tree (I think its O(log2 N)). How does this compare with octrees?

Share this post


Link to post
Share on other sites
oliii    2196
for rays, BSP trees are fine. for Comparisions with octrees, I can''t give you any information myself. I would assume BSP trees are as efficient, if not superior to the more general space partitioning systems. However, as far as general collision detections, there are some issues. You need to bevel the sharp corners and edges of your geometry, by adding extra virtual planes. Look at Stan Melax''s Dynamic plane shifting algorithms, abundantely available in Google.

Share this post


Link to post
Share on other sites
smf    122
or better yet do a search for "SamuelRanta-Eskola_BSPTrees.pdf" it is a lot better that melaxs paper

Share this post


Link to post
Share on other sites
drslush    122
Alright, so if I am using Octrees for space partitioning, and I want to do ray intersections, would it make any sense to also have a bsp tree?

Share this post


Link to post
Share on other sites
skremon    122
quote:
Original post by drslush
Alright, so if I am using Octrees for space partitioning, and I want to do ray intersections, would it make any sense to also have a bsp tree?


BSP tree generation takes a lot of time, if you do it in addition to generating Octree it won''t be very feasible IMO.

Share this post


Link to post
Share on other sites