# Collision detection problems

## Recommended Posts

Hi guys... A few days ago, I wrote a basic collision detector. The problem was that it didn't always work, so I decided to edit my plane intersection function. The problem now is that it works even less of the times. I would love it if somebody can read through this code, and spot my error :). Intersection tester. I guess the problem can be found in this function. The function works not bad on the floor, but with vertical faces it does weird things, like finding an intersection far before the face. Note that the innerProduct is the dot product. Long time ago, I called the function like this and I don't know why.
#define PLANE_FRONT		0x01
#define PLANE_BACK		0x02
#define PLANE_NONE		0x03

#define GETSIDE(a) (a > EPSILON ? PLANE_FRONT : (a < -EPSILON ? PLANE_BACK : PLANE_NONE))
bBool bMath::testIntersection(bMPlane& plane, bVertex3f& oldPos, bVertex3f& newPos, bVertex3f& ray, bDouble& t) {
if(plane.equation == 0.0)
return false;
/* If p1 is higher than 0, and p2 is lower than 0 (or the other way around), we
* are passing a plane. */
bDouble p1 = innerProduct(plane.normal, newPos) + plane.equation;
bDouble p2 = innerProduct(plane.normal, oldPos) + plane.equation;

if(GETSIDE(p1) != GETSIDE(p2)) { // did we pass a plane?
/* Ray is a non-normalized version of the new position minus the old position */
t = -p2 / innerProduct(plane.normal, ray);

return true;
}

return false;
}


plane.equation is calculated as follows:
plane_arr[i].equation = (bFloat) bMath::innerProduct(*plane_arr[i].point, plane_arr[i].normal); // plane_arr[i].point is the origin, plane_arr is an array of planes based on the faces found in the object


The following function creates the sum of the angles from the intersection point towards the vertices of a triangle. I don't think there are any errors in this code, since last time I checked this function returns a good value as long as testIntersection fills in t with a valid value.
bFloat bMath::angleSum(bVertex3f& p, bPoint *v, int n) {
bDouble retVal;

retVal = 0.0;

for(int i = 0; i < n; i++) {
bVertex3f p1 = v[i].vertice;
bVertex3f p2 = v[(i + 1) % n].vertice;
vertexSubstract(p1, p);
vertexSubstract(p2, p);

bDouble m1 = PYTH3D(p1);
bDouble m2 = PYTH3D(p2);
bDouble m1_m2 = m1 * m2;

if(m1_m2 <= EPSILON)
return (bFloat) PI_2;
else
retVal += acos(innerProduct(p1, p2) / m1_m2);
}

return (bFloat) retVal;
}


This is the function where testIntersection and angleSum are combined. Maybe there is a mistake in the calculation of the intersection point?
/* src is the current position, des is the new position, and dir is the new position minus the old position. */
bDouble t;
if(bMath::testIntersection(plane_arr[i], src, des, dir, t)) {
/* Calculate the point where the ray and the plane intersect */
bVertex3f intPoint;

intPoint.x = src.x + (dir.x * t);
intPoint.y = src.y + (dir.y * t);
intPoint.z = src.z + (dir.z * t);

bFloat as = bMath::angleSum(intPoint, &info_arr[i * 3], 3); // info_arr is the list with vertices, normals, etc.
// PI_2 is 2pi
if(as > (PI_2 - 0.08) && as < (PI_2 + 0.08)) {
return true;
}
}


I hope I have commented enough, and thanks a lot for your time. - Polyphemus [Edited by - Polyphemus on March 6, 2006 3:54:24 PM]

##### Share on other sites
Quote:
 bDouble p1 = innerProduct(point.normal, newPos) + plane.equation;

I think you want:

bDouble p1 = innerProduct(point.normal, newPos) - plane.equation;

If the aim is to have p1 = 0 when the point is on the plane. I think you calculate plane.equation as:

plane_arr[i].equation = (bFloat) bMath::innerProduct(*plane_arr[i].point, plane_arr[i].normal);

with the intention that if you calculated p1 for plane_arr[i].point then you'd get 0 because plane_arr[i].point is on the plane. In that case it should be obvious that you want to subtract, not add. I may be confused by this - I don't really follow your comment that "plane_arr[i].point is the origin" as the origin is, informally, the location (0, 0, 0) as far as I'm concerned.

Also, with:

t = -p2 / innerProduct(plane.normal, ray);

I think this may be wrong. Imagine you had the scenario where p1 was 0 and p2 was something large. Then you'd want t to be 0, as you later use it to calculate an intersection point. So I think you actually want:

t = -p1 / innerProduct(plane.normal, ray);

And you can go further and remove a dot product if you change that to:

t = -p1 / (p2 - p1);

Which if you think about, will work fine either logically because of the thing the dot product calculates or in pure maths if you pull apart the dot products terms because multiplication is associative.

In the fictional scenario where p1 was -0.5 and p2 was +1.5 that would give t = 0.25, which is probably the result you want? Beyond that things look fine, although I've not really thought about angleSum as you should confident in it.

EDIT: Okay, I'm new here and I give up on trying to find appropriate tags for the tiny fragments I've written above.

##### Share on other sites
It works! :D:D I had made some mistakes with my for-loop, and I applied your suggestions. Thanks a lot!

Oh, btw, by origin I meant a point in the plane.