Physics in BSP-Trees: Collision Detection

Physics in BSP-Trees: Collision Detection
Author: Samuel Ranta-Eskola
Description: The article discusses the implementation of physics in BSP-Trees. Topics covered are: Future Position Calculation, Collision Detection, and Collision Handling.

Reply to this post for any comments/suggestions/questions.

cool... third installment !!! very nice ! i'll read it tomorrow !

actually this is the forth installment

Is this actually the last Tutorial covering this theme? :nervous:

Is this actually the last Tutorial covering this theme?

in terms of these articles in the series, yes. But writers might submit related topics in the future...

fourth ? oh sorry... yes fourth, one must have slipped my mind

Hey guys i know there is a full PDF document that covers the whole tutorials. Could anyone please point me to where can i find it?

http://www.gamedev.net/reference/programmi...bsptree/bsp.pdf

Thanks, if you are the author of those tutorials than know that they are really very proffesional. They combine good explanations and sample source. Everything one needs in order to start coding!

Thank you for your kind words

I tried to write the report in a way that would make it easy to "follow in my footsteps".

The main thing with the report is that it should encourage you to think for yourself. The solutions I provide are very basic and aren't fit for larger scale projects. But it will, as you mention, get you started.

Hi. I've found this article helpful, but while attempting to implement this algorithm I have run into some details that don't appear to be covered. I emailed the author a couple weeks ago, but since I have not received a response I am posting here.

In the second phase of collision detection (the first phase being to determine if the object has even crossed the plane of the polygon) the algorithm uses perpendicular planes to check if the object falls within the edges of the polygon. However this test uses "Object.Position" which is not defined or discussed anywhere within the document.

Does anyone have insight into what Object.Position represents? Since the object is in motion it is represented by Object.StartPosition and Object.EndPosition. Thus Object.Position must be some point on that line, but this is not discussed. It should not be the point on the polygon plane where the line segment crosses, because that does not take into account the bounding volume of the ellipsoid. It seems it should be the point on the line that is CALCULATE-COLLISIONRADIUS() units from the polygon plane. Is this correct?

Thanks!

Dan East

I think the email that's in the article is invalid. He recently posted on this thread:
http://www.devmaster.net/forums/index.php?...p?showtopic=532

According to that thread, the email he uses is: krassa at hotmail.com

Just tell him to check this thread, and he'll post it his answer here.

I'll drop him an email.

Originally Posted by Dan East

It seems it should be the point on the line that is CALCULATE-COLLISIONRADIUS() units from the polygon plane. Is this correct?

After thinking about it a bit more, that isn't correct either. However I believe this may be the proper technique:

Find the point p1 on the motion line segment that is CALCULATE-COLLISIONRADIUS() units from the polygon plane.

Find the point p2 where the motion line segment intersects the polygon plane.

The segment (p1, p2) now represents the potential range of collision against the polygon using the ellipsoid volume.

for each edge plane {
 calculate D1 and D2 (the distance from edge plane to p1 and p2)

 if (D1 and D2 are behind edge plane)
  return NO_COLLISION; //no collision occured

 if (D1 and D2 are in front of edge plane)
  continue; //iterate to next edge plane

 set p3 to the point where segment (p1, p2) intersects edge plane

 if (D1 is in front of edge plane and D2 is behind edge plane) {
  p2=p3;
  continue; //iterate to next edge plane
 }

 //Assume D1 is behind edge plane and D2 is in front of edge plane
 p1=p3;
}

//Collision occured
//p1 should be the point where the collision occured.

return COLLISION;

I haven't tested this, but I believe this will yield proper results. I'll post back here after I've implemented it.

Dan East

After reading my article I realized the unclarity regarding Object.Position. When looking at Dan East's solution I find it a more exact way to solve collisions, at a higher cost though.

I think I chose to represent Object.Position as the position where the move crossed the polygon. This can render in some minor problems when passing corners, where a polygon actually would be to close but be discarded since the Position would be outside polygon. But I don't think this will generate and cruel bugs so you can easily go with that solution too. (depending on how much juice want to spend If you want a more exact solution go with Dan East's..

I think the article is good but the author should have provided concrete example and not only pseudo code. I don’t understand how to calculate Object.xzColl and Object.yColl and I think the formula for calculating collision radius should be explained in more details.


CALCULATE-COLLISIONRADIUS (Object, Direction)
1 return Sqrt((Object.xzColl * Direction.x)2 +
(Object.yColl * Direction.y)2 +
(Object.xzColl * Direction.z)2)

Also what is Polygon.Distance?

Hi there.

CALCULATE-COLLISIONRADIUS calculates the radius of the ellipsoid containing the character to perform collision detection on. Object.xzColl is the radius for the ellipsiod in th ex-z plane while Object.yColl is the radius (i.e. half the height of the character) in y space. It was a couple of years since I wrote this and now I've realized there are quite a few ways better to do the collision detection (boxes or just one plain sphere at a predefined height.


Polygon.distance is the d coefficient in the plane equation (x+y+z+d), meaning the distance from origo along the normal -> a plane with the normal <1,0,0> that cuts through the x-axis at x=500 has d=500. To calculate the distance you just input any of the points in the polygon into this formula:

d=-(polygon.point dot polgyon.normal)

Hope I clarified some things for you.

Regards
Samuel Ranta-Eskola

nevertheless i liked the article, its last sentnce scared me, as in other ones

Hi,
I liked the article very much, and I have some further questions.
1. My biggest problem with this algorithm is the sphere can pass through adjecencing triangles if their normals enclose a big angle (more than 90). It is because the sphere can pass the triangles by not passing their shifted planes. Maybe it could be solved by inserting additional triangles to the risky places, but there could be better solutuions too.
2. I think that checking if the collision point of the moving plane and the shifted plane, is inside the perpendicular planes or not is not enough to decide if a collision happend or not. It could be better testing the whole moving line against the shifted perp. planes...
If you think i am not correct or have some solutions, please tell me! If it is not understandable i could send some figures better representing the problems.

Thanks, Gábor

After using Stan Melax's dynamic plane shifting for a while, I want to give a try to this technique...
DPS is extremely picky with the geometry i feed to it, and in many cases not very accurate. This one is probably much slower and CPU hungry though, but i imagine a lot more precise, and shouldn't baffle with not-so-good geometry.