Can BSP Trees Be Used for Internal Collision Detection?

[ThreeMarks]

Hi,

I've got a problem with collision detection of which I am struggling to find a solution.

In the simplest case, I would have a sphere whose movement would be constrained inside a closed arbitrarily-shaped object.

I have been looking into BSP trees which split the shape into chunks for fast detection. However, I get the impression that this would only work for sphere outside of the object.

Is it possible that I can un fact still use a bsp setup. Or does anybody know of a way that I can do _internal_ collision detection.

Thanks,

ThreeMarks

 

[QuantumQuest]

The question is very general as it does not specify which is the exact problem to be solved, so it gives no clue as to what is the most efficient way to be followed.

Generally speaking, collision detection is basically a procedure in which we examine if two objects collide - effectively if two geometrical shapes intersect. It is fundamental to Virtual Reality (VR) applications including animations, games and robotics among others. It is part of a collision handling plan along with collision determination (i.e. where exactly is the intersection) and collision response (i.e. how do we handle the situation). We can perform collision detection using rays, BSP trees or using Hierarchical Collision Detection.

For BSP trees in particular, they are spatial data structures for which efficient algorithms performing set operations (union, intersection , (symmetric) difference etc.). exist. BSP trees - and, of course, search trees in general, have been extensively analyzed under worst-case and average-case models and they offer an efficient way to handle a lot of problems in a realistic way. The common approach is attributing equal likelihood to each possible query. Unlike this, an approach which assumes events that happened in the past are more likely to happen in the future and uses Self-Customized BSP trees, is presented in this paper from Princeton.