Collision Detection

HoverEX uses BSP method to speed up collision detection. Usually, the problem with computational physics is that the collision detection is the bottle neck. This is due to collision checking requires every objects to test for collision with the wall, and everyone else.

Being so, collision detection will go exponentially as more objects are placed into a scene. This cannot be avoided. However, thanks to the BSP algorithm, we could partition our world into smaller sectors which would improve our collision detection.

Read up the BSP FAQ for more informantion on what BSP is.

The current implementation of BSP is not optimized however, as what was coded only just simply split the world into halfs recursively, resulting the BSP to have uneven sectors.

Add image here to describe the lame BSP generation.

Using BSP, we can easily pin point which sector(leaf) we are in.

Add image here to describe the sector detection.

Since a point is not much use for detecting the possible walls that we are going to collide with, we introduce the ray method.

Add image here to describe the ray method.

Being that the ray method is only a straight line from a point to another, we need a way to figure for our circle object since our hovercrafts are “circle”s. Hence, we introduce multi-ray method to get sectors that were intersected given a few lines. With that, HoverEX uses 3 essential ray that does the job needed for getting all the possible colliding wall lines.

Add image here to describe the hoverex collision system.

With that, we cut down the number of lines needed to be tested for each object.

The biggest problem with collsion is the object ⇔ object collision problem. Since they have to check for each and every other objects in the world, the calculation would be very expensive. Hence, come BSP to the rescue.

Since when checking for wall collision, we would have known the possible intersected segment of each object. So if we are able to group these objects into segments of their own, we will be able to cut down the number of checks needed.

Add image here to show how we saperate the objects into their related segments.

1. First, we build a hash table of objects in each segments.
2. We then loop through each object and find the segments they are intersecting.
   1. getting the segments, we get all the possible objects that are intersecting in the same segments using the hash table.
   2. Then we do collision detection with all those objects with an ID greater than our own.

Everything works best with example. Hence, here is an example to prove that this works and also help clarify exactly how we do it.

TODO