# Collision detection woes

• 06-06-2006
joeprogrammer
Collision detection woes
OK, before I start I need to tell you something: I have no experience with linear algebra :( . I am pretty good at programming, and regular algebra, but I am totally clueless about the linear stuff.

I have several flat quads, at 90º angles. I need some balls to bounce off them :)

Here goes: My collision detection just don't work. It's as if it's not there. Let me show you a few code samples:

Definition of some types first:
- point3d holds a 3d point
- plane3d is not really a plane. :) It's got point 3d points[4] for holding a quad, float normal x, y, z for the plane normal, and float distance for the plane distance

My function used for calculating distances:

Code:

```void calculate_plane(plane3d *theplane) {         point3d *v1 = &theplane->points[0];         point3d *v2 = &theplane->points[1];         point3d *v3 = &theplane->points[2];                 theplane->distance = -(v1->x * (v2->y * v3->z - v3->y * v2->z) +                                                   v2->x * (v3->y * v1->z - v1->y * v3->z) +                                                   v3->x * (v1->y * v2->z - v2->y * v1->z)  ); }```
Notice that the code above only calculates the distance of the plane; the plane normals and coordinates are hand-typed. (I probably could've used a loop, but I was too lazy.)

So far, so good, right?

Now I need a function to figure out which side of the plane a point is on:

Code:

```int classify_point(plane3d *plane, point3d *dest_pt ) {         float p = dot_product( &plane->normal, dest_pt ) + plane->distance;         if( p > 0.0f ) return PLANE_FRONT;         else         if( p < 0.0f ) return PLANE_BACK;         return PLANE_COINCIDE; }```
Where PLANE_FRONT, PLANE_BACK, and PLANE_COINCIDE are 99, 100, and 101, repectively. But the values don't really matter; as long as they're different.

Now, I know that the ball will always be inside the walls (the 4 walls enclose the ball), so that means that I can skip the process of finding where exactly the collision point on the plane is, right?

All that is left is to find which wall it hit, and then reverse the correct axis:
Code:

```void ball_collision(ball *theball) {         // note that we don't actually make sure that the collision point is on the quad; because this         // is such a simple game, that's all the checking we need to do :)                 point3d &current_pos = theball->pos;        // grab the ball's current position         point3d dest_pos;                                                // this will hold where the ball would go         // from the current velocity, calculate where the ball would go (its destination)         dest_pos.x = theball->pos.x + theball->vel.x;         dest_pos.y = theball->pos.y + theball->vel.y;         dest_pos.z = theball->pos.z + theball->vel.z;                 // run through each plane in tube         for (int i=0; i<4; i++) {                 int dest_side = classify_point(&tube[i], &dest_pos);                 int current_side = classify_point(&tube[i], &current_pos);                                 // check to see if the destintation point and the current point are on the same sides of the plane (quad)                 if (dest_side != current_side) {                                                 // find which wall it collided into                         if (i == 0 || i == 2) {                                 // ball collided on the y axis, so reverse it                                 theball->pos.y = -theball->pos.y;                                 return;                         }                         else {                                 // ball collided on the x axis                                 theball->pos.x = -theball->pos.x;                                 return;                         }                 }                 // keep going         } }```
Where tube is really plane3d tube[4], and so notice that I check to see which wall of the tube it collided into before reversing the appropriate axis. (tube[0] and tube[2] are the bottom and top, respectively. And of course tube[1] and tube[3] are the left and back, respectively.)

Then I actually run the collision function here:
Code:

```void ball_draw(ball *theball) {         // make sure the ball didn't collide with anything         ball_collision(theball);         glTranslatef(theball->pos.x, theball->pos.y, theball->pos.z);         glColor3f(0.5f, 0.5f, 0.5f);         gluSphere(quadratic, ball_radius, ball_subdiv_x, ball_subdiv_y); }```
But whenever I run the program, the ball keeps going through the walls as if I was never calling the functions. I looked at what the variables are doing, and classify_point always returns PLANE_FRONT, even when the ball is going to fly into the wall.

Can anyone much smarter than me see where I went wrong? :confused:
• 06-06-2006
Perspective
Make sure you normalize the plane.
• 06-06-2006
joeprogrammer
Sure, I did that. Here are my plane normals:

Bottom plane:
(0, 1, 0)
Left plane:
(1, 0, 0)
Top plane:
(0, -1, 0)
Left plane:
(-1, 0, 0)

Is there anything else that could be causing a problem?
• 06-06-2006
skorman00
Code:

` float p = dot_product( &plane->normal, dest_pt ) + plane->distance;`
that doesn't seem right to me. What is the distance exactly; the way you compute it seems to be some sort of variant of a cross product, could you explain the math for me? That aside, you can figure out which side it's on without it:
Code:

``` point3d delta = dest_pt - plane->points[0];  float p = dot_product ( &plane->normal, &delta ); //NOTE: this wont work if dst_pt == plane->points[0]```
If you think of the plane as a giant sheet in space, this gets the point's position relative to the plane, then tests that against the normal instead of the points world position.
• 06-06-2006
joeprogrammer
Well, I'm not really sure what I'm doing myself. I just followed the tutorial found here:
http://www.flipcode.com/articles/art...llisions.shtml
• 06-10-2006
BobMcGee123
This is my collision detection primitives library. AFAIK everything works, not everything is neat or optimized. Some of this might rely on other precompiled constructs which you do not have, I leave you to sort through it.

Code:

```#include        "CollisionDetectionPrimitives.h" /*         For every in_plane, get the distance from the Pos to the sphere                   if(planedist1        <= -(radius_pfast_tol))                 return        FALSE;         else        if(fabs(planedist1) <= radius_pfast_tol)         {                 ++num_intersections;                 if(planedist1        >=        0)                         ++pos_intersections;                } */ BOOL        PointInBSPFace(BSP        *pBSP,int        faceindex,Vector3 & Pos,float        Radius) {         tBSPFace        *pFace = &pBSP->mpFaces[faceindex];         Vector3        dir = pFace->center - Pos;         float        startd_sq = dir.BasicLength();         float        rad_sq = Radius * Radius;         if(startd_sq <= rad_sq)                 return        TRUE;        //intersects with the center of the bspface         dir.Normalize(Faster_Sqrtf(startd_sq));         Vector3        testpoint = Pos + (dir * Radius);                 Plane3        *pPlane = NULL;         float        d(0);         for(int plane = 0; plane < pFace->numInPlanes; plane++)         {                 pPlane = &pFace->mpInplanes[plane];                 d = DotProduct(&pPlane->mNormal,&testpoint) - pPlane->mDist;                 if(d < -FastBSPFacetolerance)                         return        FALSE;         }         return        TRUE; } ... #include        "CollisionDetectionPrimitives.h" extern        std::ofstream        trace; #define        CCWPITDEBUG(x)        //x const        float        globaltolerance        =        2.0f; const        float        fast_tolerance  =  globaltolerance * 1.5f; //Fixme: investigate to see how vector length plays into uncertainty here //Normal x DiffVector = InwardVector //InwardVector Dot Point >= 0 or >= -.0001 BOOL        CCWPointInTri(float        P1X,float        P1Y,float        P1Z,                                           float        P2X,float        P2Y,float        P2Z,                                           float        P3X,float        P3Y,float        P3Z,                                           float        NormalX,float        NormalY,float        NormalZ,                                           float        PointX,float PointY,float        PointZ,float Radius) {         Vector3        Point1(P1X,P1Y,P1Z);        Vector3        Point2(P2X,P2Y,P2Z);        Vector3        Point3(P3X,P3Y,P3Z);         Vector3        Normal(NormalX,NormalY,NormalZ);         Vector3 Point(PointX,PointY,PointZ);         Vector3        LocalPoint = Point - Point1; //The point in local coordintes with respect to a vertex         Vector3        DiffVector        =        Point2 - Point1;         Vector3        InwardVector(0,0,0);         InwardVector        =        CrossProduct(&Normal,&DiffVector);         InwardVector.Normalize();                 int        num_intersections(0);         double        planedist1,planedist2,planedist3;         double        radius_ptol = Radius + globaltolerance;         planedist1        =        DotProduct(&InwardVector,&LocalPoint);         if(planedist1        <= -(radius_ptol))         {                 return        FALSE;         }         else        if(fabs(planedist1) <= radius_ptol)         {                 ++num_intersections;         }         LocalPoint        =        Point  - Point2;         DiffVector        =        Point3 - Point2;         InwardVector        =        CrossProduct(&Normal,&DiffVector);         InwardVector.Normalize();         planedist2        =        DotProduct(&InwardVector,&LocalPoint);         if(planedist2        <= -(radius_ptol))         {                 return        FALSE;         }         else        if(fabs(planedist2) <= radius_ptol)         {                 ++num_intersections;         }         LocalPoint        =        Point  - Point3;         DiffVector        =        Point1 - Point3;         InwardVector        =        CrossProduct(&Normal,&DiffVector);         InwardVector.Normalize();                 planedist3        =        DotProduct(&InwardVector,&LocalPoint);         if(planedist3        <= -(radius_ptol))         {                 return        FALSE;         }         else        if(fabs(planedist3) <= radius_ptol)         {                 ++num_intersections;         }         if(num_intersections > 1)         {                 if(planedist1 >= 0 && planedist2 >= 0 && planedist3 >= 0)                 {                         return TRUE;                 }                 else                 {                         return        FALSE;                 }         }         return        TRUE; } BOOL        CWPointInTri(float        P1X,float        P1Y,float        P1Z,                                           float        P2X,float        P2Y,float        P2Z,                                           float        P3X,float        P3Y,float        P3Z,                                           float        NormalX,float        NormalY,float        NormalZ,                                           float        PointX,float PointY,float        PointZ,float Radius) {         Vector3        Point1(P1X,P1Y,P1Z);        Vector3        Point2(P2X,P2Y,P2Z);        Vector3        Point3(P3X,P3Y,P3Z);         Vector3        Normal(-NormalX,-NormalY,-NormalZ);         Vector3 Point(PointX,PointY,PointZ);         Vector3        LocalPoint = Point - Point1; //The point in local coordintes with respect to a vertex         Vector3        DiffVector        =        Point2 - Point1;         Vector3        InwardVector(0,0,0);         InwardVector        =        CrossProduct(&Normal,&DiffVector);         InwardVector.Normalize();                 int        num_intersections(0);         double        planedist1,planedist2,planedist3;         double        radius_ptol = Radius + globaltolerance;         planedist1        =        DotProduct(&InwardVector,&LocalPoint);         if(planedist1        <= -(radius_ptol))         {                 return        FALSE;         }         else        if(fabs(planedist1) <= radius_ptol)         {                 ++num_intersections;         }         LocalPoint        =        Point  - Point2;         DiffVector        =        Point3 - Point2;         InwardVector        =        CrossProduct(&Normal,&DiffVector);         InwardVector.Normalize();         planedist2        =        DotProduct(&InwardVector,&LocalPoint);         if(planedist2        <= -(radius_ptol))         {                 return        FALSE;         }         else        if(fabs(planedist2) <= radius_ptol)         {                 ++num_intersections;         }         LocalPoint        =        Point  - Point3;         DiffVector        =        Point1 - Point3;         InwardVector        =        CrossProduct(&Normal,&DiffVector);         InwardVector.Normalize();                 planedist3        =        DotProduct(&InwardVector,&LocalPoint);         if(planedist3        <= -(radius_ptol))         {                 return        FALSE;         }         else        if(fabs(planedist3) <= radius_ptol)         {                 ++num_intersections;         }                 if(num_intersections > 1)         {                 if(planedist1 >= 0 && planedist2 >= 0 && planedist3 >= 0)                 {                         return TRUE;                 }                 else                 {                         return        FALSE;                 }         }         return        TRUE; }         /*         The faster point in tri functions just use faster_sqrt   Note that if the sphere intersects 2 or more of the inward planes,         then the exact center of the sphere must lay in front of all planes         Otherwise you get the 'ghost' collisions where the sphere is definitely *not*                 inside of the triangle */ BOOL        FastCWPointInTri(float        P1X,float        P1Y,float        P1Z,                                           float        P2X,float        P2Y,float        P2Z,                                           float        P3X,float        P3Y,float        P3Z,                                           float        NormalX,float        NormalY,float        NormalZ,                                           float        PointX,float PointY,float        PointZ,float Radius) {         Vector3        Point1(P1X,P1Y,P1Z);        Vector3        Point2(P2X,P2Y,P2Z);        Vector3        Point3(P3X,P3Y,P3Z);         Vector3        Normal(-NormalX,-NormalY,-NormalZ);         Vector3 Point(PointX,PointY,PointZ);         Vector3        LocalPoint = Point - Point1; //The point in local coordintes with respect to a vertex         Vector3        DiffVector        =        Point2 - Point1;         Vector3        InwardVector(0,0,0);         InwardVector        =        CrossProduct(&Normal,&DiffVector);         InwardVector.Fast_Normalize();                 int        num_intersections(0);         int        pos_intersections(0);        //how many intersections occur with it on the positive side         double        planedist1,planedist2,planedist3;         double        radius_pfast_tol = Radius + fast_tolerance;         planedist1        =        DotProduct(&InwardVector,&LocalPoint);                         if(planedist1        <= -(radius_pfast_tol))                 return        FALSE;         else        if(fabs(planedist1) <= radius_pfast_tol)         {                 ++num_intersections;                 if(planedist1        >=        0)                         ++pos_intersections;                }                         LocalPoint        =        Point  - Point2;         DiffVector        =        Point3 - Point2;         InwardVector        =        CrossProduct(&Normal,&DiffVector);         InwardVector.Fast_Normalize();         planedist2        =        DotProduct(&InwardVector,&LocalPoint);         if(planedist2        <= -(radius_pfast_tol))                 return        FALSE;         else        if(fabs(planedist2) <= radius_pfast_tol)         {                 ++num_intersections;                 if(planedist2        >=        0)                         ++pos_intersections;                }         LocalPoint        =        Point  - Point3;         DiffVector        =        Point1 - Point3;         InwardVector        =        CrossProduct(&Normal,&DiffVector);         InwardVector.Fast_Normalize();                 planedist3        =        DotProduct(&InwardVector,&LocalPoint);         if(planedist3        <= -(radius_pfast_tol))                 return        FALSE;         else        if(fabs(planedist3) <= radius_pfast_tol)         {                 ++num_intersections;                 if(planedist3        >=        0)                         ++pos_intersections;                }                 if(num_intersections > 1)         {                 /*                 if(planedist1 >= 0 && planedist2 >= 0 && planedist3 >= 0)                 {                         if(num_infront != 3 && num_messages < 1000)                         {                                 trace << "weirdness in pointintri function" << "\n";                         }                         return        TRUE;                 }                 */                                 if(pos_intersections        ==        3)                        {                         return TRUE;                 }                                 else                 {                         return        FALSE;                 }         }         return        TRUE; } BOOL        FastCCWPointInTri(float        P1X,float        P1Y,float        P1Z,                                           float        P2X,float        P2Y,float        P2Z,                                           float        P3X,float        P3Y,float        P3Z,                                           float        NormalX,float        NormalY,float        NormalZ,                                           float        PointX,float PointY,float        PointZ,float Radius) {         Vector3        Point1(P1X,P1Y,P1Z);        Vector3        Point2(P2X,P2Y,P2Z);        Vector3        Point3(P3X,P3Y,P3Z);         Vector3        Normal(NormalX,NormalY,NormalZ);         Vector3 Point(PointX,PointY,PointZ);         Vector3        LocalPoint = Point - Point1; //The point in local coordintes with respect to a vertex         Vector3        DiffVector        =        Point2 - Point1;         Vector3        InwardVector(0,0,0);         InwardVector        =        CrossProduct(&Normal,&DiffVector);         InwardVector.Fast_Normalize();                 int        num_intersections(0);         int        pos_intersections(0);         double        planedist1,planedist2,planedist3;         double        radius_pfast_tol = Radius + fast_tolerance;         planedist1        =        DotProduct(&InwardVector,&LocalPoint);         if(planedist1        <= -(radius_pfast_tol))         {                 return        FALSE;         }         else        if(fabs(planedist1) <= radius_pfast_tol)         {                 ++num_intersections;                                 if(planedist1 >= 0)                         ++pos_intersections;         }         LocalPoint        =        Point  - Point2;         DiffVector        =        Point3 - Point2;         InwardVector        =        CrossProduct(&Normal,&DiffVector);         InwardVector.Fast_Normalize();         planedist2        =        DotProduct(&InwardVector,&LocalPoint);         if(planedist2        <= -(radius_pfast_tol))         {                 return        FALSE;         }         else        if(fabs(planedist2) <= radius_pfast_tol)         {                 ++num_intersections;                 if(planedist2 >= 0)                         ++pos_intersections;         }         LocalPoint        =        Point  - Point3;         DiffVector        =        Point1 - Point3;         InwardVector        =        CrossProduct(&Normal,&DiffVector);         InwardVector.Fast_Normalize();                 planedist3        =        DotProduct(&InwardVector,&LocalPoint);         if(planedist3        <= -(radius_pfast_tol))         {                 return        FALSE;         }         else        if(fabs(planedist3) <= radius_pfast_tol)         {                 ++num_intersections;                                 if(planedist3 >= 0)                         ++pos_intersections;         }         if(num_intersections > 1)         {         //        if(planedist1 >= 0 && planedist2 >= 0 && planedist3 >= 0)                 if(pos_intersections >= 3)                 {                         return TRUE;                 }                 else                 {                         return        FALSE;                 }         }         return        TRUE; } /* //Same thing, different version BOOL        CWPointInTri(float P1X,float P1Y,float P1Z,                                         float P2X,float P2Y,float P2Z,                                         float P3X,float P3Y,float P3Z,                                         float NormalX,float NormalY,float NormalZ,                                         float PointX, float PointY, float PointZ) {         Vector3        P1(P1X,P1Y,P1Z);         Vector3        P2(P2X,P2Y,P2Z);         Vector3        P3(P3X,P3Y,P3Z);         Vector3        Point(PointX,PointY,PointZ);         Vector3        Normal(NormalX,NormalY,NormalZ);         Vector3        Edge1 = P1 - P2;         Vector3        Edge2 = P2 - P3;         Vector3        Edge3 = P3 - P1;         Vector3        PminusP2 = Point - P2;         Vector3        PminusP3 = Point - P3;         Vector3        PminusP1 = Point - P1;         if(DotProduct(&Normal,&CrossProduct(&Edge1,&PminusP2)) >= globaltolerance)         if(DotProduct(&Normal,&CrossProduct(&Edge2,&PminusP3)) >= globaltolerance)         if(DotProduct(&Normal,&CrossProduct(&Edge3,&PminusP1)) >= globaltolerance)                 return true;         return false; } */ ... #include        "CollisionDetectionPrimitives.h" #define        SWEPTSPHEREDEBUG(x)        //x /*         SINGLE        PRECISION IMPLEMENTATION */ /* //NEWTON ITERATION SQRT x87 fpu Number DD ? TestResult DW? Two DD 2.0 MaxRelErr  DD 0.5E-6 Sqrt:   fld1 REPEAT01:   fld ST   fld Number   fdiv ST,ST(1)   fadd ST,ST(1)   fDiv Two   fst ST(2)   fsub   fabs   fld MaxRelErr   fmul ST,ST(2)   fcompp   fstsw TestResult   fwait   mov ax, TestResult   sahf   jna REPEAT01   ret .....         _asm                 {                         FLD        basic; //Put basic length into st(0)                         FSQRT;                //Put SQUARE ROOT of basic into st(0)                         FSTP basic; //Put st(0) into basic and pop that motha                 }         */ //spheres may also be penetrating BOOL        AreSpheresTouching(Vector3        &PointA,Vector3 &PointB,double        SepDist) {         BOOL        retval;         Vector3        Separation = PointA - PointB;         float        SepLenSq  = Separation.BasicLength();         if(SepLenSq > (SepDist * SepDist))         {                 return        FALSE;         }         else         {                 return        TRUE;         } } /*         If (AreSpheresTouching) and AreSpheresGettingCloser, then they've got a collision         This type of collision won't really be picked up by         Normal defined as PointA - PointB         FIXME: does normal need to be normalized?  Don't think so! */ BOOL        AreSpheresGettingCloser(Vector3 &PointA,Vector3 &PointB,                                                         Vector3 &VelA,Vector3 &VelB,                                                         Vector3        &Normal) {         BOOL        retval;         Vector3        RelVel = VelA - VelB;        //relative velocity         float        NormalRelVel = DotProduct(&RelVel,&Normal);        //relative velocity along normal         if(NormalRelVel > .00001f)         {                 return        FALSE;         }         else         {                 return        TRUE;         } } BOOL        DoSpheresCollide(Vector3 &PStart,Vector3 &PEnd,                                                 Vector3 &QStart,Vector3 &QEnd,                                                 float PRadius,float QRadius,float Epsilon) {         BOOL        retval = false;         Vector3        A = PStart - QStart;         Vector3        B = (PEnd - PStart) - (QEnd - QStart); //relative velocity                 double        ASq = A.BasicLength();         double        AdotB = DotProduct(&A,&B);         double        AdotB_sq = AdotB * AdotB;         double        BSq = B.BasicLength();         double        iBSq(0);         if(BSq > .000001f)         {                 iBSq = 1/ BSq;         }         else        //if b_squared is zero, then they cannot collide (both stationary or moving in same direction)         {                 SWEPTSPHEREDEBUG(        trace << "DoSpheresCollide(): BSquared <relative velocity) is zero, setting to 1.0f" << "\n";        )                 return        FALSE;                }         double        closest_dist_squared = (ASq - (AdotB_sq * iBSq));         double        desired_dist_squared = PRadius + QRadius + Epsilon;         desired_dist_squared *= desired_dist_squared;         if(closest_dist_squared > desired_dist_squared)                {                 return        FALSE;         }         else         {                 return        TRUE;         }         return        retval; } double        ClosestSphereSepDistance(Vector3 & PStart,Vector3 &PEnd, Vector3 &QStart,Vector3 &QEnd) {         Vector3        A = PStart - QStart;         Vector3        B = (PEnd - PStart) - (QEnd - QStart); //relative velocity                 double        ASq = A.BasicLength();         double        AdotB = DotProduct(&A,&B);         double        AdotB_sq = AdotB * AdotB;         double        BSq = B.BasicLength();                 double        iBSq(0);//        =        BSq > .0000001f ? (1/BSq) : 1.0f;        //Inverse of |B| squared         if(BSq > .000001f)         {                 iBSq = 1/ BSq;         }         else        //if b_squared is zero, then they cannot collide (both stationary or moving in same direction)         {                 SWEPTSPHEREDEBUG(        trace << "BSquared is zero, setting to 1.0f" << "\n";        )                 return        -3.0f;                //        iBSq        =        1.0f;         }         double        closest_sep_dist_sq = ASq - (AdotB_sq * iBSq);         return        closest_sep_dist_sq; } double        TimeOfSphereIntersection(Vector3 &PStart,Vector3 &PEnd,                                                                 Vector3 &QStart, Vector3 &QEnd,                                                                 float PRadius, float QRadius, float Epsilon) {                 Vector3        A = PStart - QStart;         Vector3        B = (PEnd - PStart) - (QEnd - QStart); //relative velocity                 double        ASq = A.BasicLength();         double        AdotB = DotProduct(&A,&B);         double        AdotB_sq = AdotB * AdotB;         double        BSq = B.BasicLength();                 double        iBSq(0);//        =        BSq > .0000001f ? (1/BSq) : 1.0f;        //Inverse of |B| squared         if(BSq > .000001f)         {                 iBSq = 1/ BSq;         }         else        //if b_squared is zero, then they cannot collide (both stationary or moving in same direction)         {                 SWEPTSPHEREDEBUG(        trace << "BSquared is zero, setting to 1.0f" << "\n";        )                 return        -3.0f;                //        iBSq        =        1.0f;         }         double        sep_dist = PRadius + QRadius + Epsilon;         double        sep_dist_sq = sep_dist * sep_dist;         double        closest_sep_dist_sq = ASq - (AdotB_sq * iBSq);         if(closest_sep_dist_sq > sep_dist_sq)         {                 SWEPTSPHEREDEBUG(        trace << "closest_sep_dist_sq > sep_dist_sq, returning -1" << "\n";        )                 return        -1.0f;         }         double        under_root        =        AdotB_sq - (BSq * (ASq - sep_dist_sq));                 if(under_root        <        0)         {                 SWEPTSPHEREDEBUG(        trace << "negative under radical, no sphere intersection, returning -2" << "\n";        )                 return        -2.0f;         }         double        root = sqrt(under_root);         double        time = (-AdotB - root) * iBSq;                 if(time        >=        1.0f)         {                 SWEPTSPHEREDEBUG(        trace << "Fishy value of time, greater or equal to 1.0f: " << time << "\n";        )                 SWEPTSPHEREDEBUG(        trace << "Root: " << root << "under_root: " << under_root << "AdotB: " << AdotB << "\n\n";        )         }         else         {                 SWEPTSPHEREDEBUG(        trace << "Value of time not fish, good" << "\n";        )         }         return        time; } ... #include        "CollisionDetectionPrimitives.h" extern        std::ofstream        trace; #define        RAYPLANEDEBUG(x)        //x /*         Returns a floating point number between 0 and 1 representing the time that the ray, represented by a start         point and an end point, intersects the plane         Epsilon is zero or close-to-zero (quake3 uses (1/32)) */ float        TimeIntersectsPlane(float NormalX, float NormalY, float NormalZ,                                                           float StartX, float StartY, float StartZ,                                                           float EndX, float EndY, float EndZ,                                                           float PlaneD, float Radius, float Epsilon) {         Vector3        Start(StartX, StartY, StartZ);         Vector3        End(EndX, EndY, EndZ);         Vector3        Normal(NormalX, NormalY, NormalZ);         float        abs_start_dist(0),abs_end_dist(0);                 float        total_dist(0), itotal(0); //Start dist + end dist, and 1/(start_dist + end dist)         abs_start_dist        =        DotProduct(&Start,&Normal) - PlaneD - Radius;         abs_end_dist        =        DotProduct(&End, &Normal) - PlaneD - Radius; RAYPLANEDEBUG(        trace << "PlaneD: " << PlaneD << "\n"; ) RAYPLANEDEBUG( trace << "Radius: " << Radius << "\n"; ) RAYPLANEDEBUG(        trace << "Startdist: " << abs_start_dist << "\n"; ) RAYPLANEDEBUG( trace << "Enddist: " << abs_end_dist << "\n"; )         //FIXME: I probably want a greater tolerance here                if(abs_start_dist >= 0 && abs_end_dist >= 0)                 return        -1;        //both in front of the plane         if(abs_start_dist < 0 && abs_end_dist < 0)                 return        -2;        //both behind the plane         //At this point you know the points span the plane         //but, the math doesn't work if the start point is behind         //so if it is, just swap their values and proceed #if        1         if(abs_start_dist        <        0)         {                 float        temp = abs_end_dist;                 abs_end_dist        =        abs_start_dist;                 abs_start_dist        =        temp;         } #endif                 abs_start_dist        =        fabs(abs_start_dist);         abs_end_dist        =        fabs(abs_end_dist);         total_dist = abs_start_dist + abs_end_dist;                 RAYPLANEDEBUG(trace << "total_dist: " << total_dist << "\n"; )         if(total_dist < .00001f)         {                 RAYPLANEDEBUG(        trace << "Fishy value for total_dist in TimeRayIntersectsPlane function: " << total_dist << "\n";        )                 return        -3;         }         itotal = 1/total_dist;         float        fraction = (abs_start_dist - Epsilon) * itotal;         //FIXME: this would only happen when start_dist less than EPSILON units away from collision position         if(fraction        <        0)                 fraction        =        0.0f;         return        fraction; }```
• 06-10-2006
joeprogrammer
Thanks a million, Bob! This will save me a lot of time programming.... Collision detection is something that I put off until the last moment possible, because I don't understand it that well :)
• 06-10-2006
BobMcGee123
I know I just dumped a mound of crap on you like that, but it seems that, while you claim to not understand it, you've thought about it a bit and are familiar with a bunch of the terminology.

Feel free to ask me more pointed detailed questions about any of those functions. I also have code for doing swept collisions against brushes, but I don't use it anymore. Everything I've posted above can likely be found in tutorials. coldet is something I've got down pretty good, from the implementation side of it. Also, I believe there are coldet libraries out there, nobody would look down upon you for using them (I'm not sure if novodex physics includes coldet). Coldet is one of those nasty required things that is incredibly difficult to actually get to friggin work.
• 06-10-2006
BobMcGee123
this is how I compile the constructs for the first function in the list of functions I posted above (bool PointInBSPFace()). It pre compiles inward pointing planes for each bsp face (which can be comprised of many triangles). It finds the unique edges and generates planes out of them, so if it was a quad made of up 2 render triangles, it would find the outer 4 edges and generate them into planes. I use this instead of brushes.

As with everything I write it's ugly and hackish, I was probably drunk when I wrote it, and it works.

PHP Code:

``` typedef    struct shared_face_edge {     shared_face_edge()     {         vert0 = vert1 = count = 0;     }     shared_face_edge(shared_face_edge & rhs)     {         vert0 = rhs.vert0;         vert1 = rhs.vert1;         count = rhs.count;     }     int    vert0;     int    vert1;     int    count;    //how many triangles share this edge     bool    operator == (shared_face_edge & rhs)     {         return    (rhs.vert0 == vert0 && rhs.vert1 == vert1 ||                   rhs.vert0 == vert1 && rhs.vert1 == vert0);     } }; ...     /*         Step1:    Add all edges to a vector         Step2:    Go through and count how many triangles have this edge         Step3:    All edges that are only owned by 1 triangle are outside edges,             add these to a separate vector          Step4:  Compute the inward facing planes using the unique outside edges     */          for(i = 0; i < mNumFaces; i++)     {         std::vector<shared_face_edge*>    all_edges;         std::vector<shared_face_edge*>    unique_edges;         tBSPFace    *pFace = &mpFaces[i];                  Vector3    center;         for(int vert = 0; vert < pFace->numOfVerts; vert++)         {             center += mpVertices[pFace->startVertIndex + vert].vPosition;         }                  center    *=    (1.0f / pFace->numOfVerts);         mpFaces[i].center = center;         //Step1: adding all edges to a temporary vector         for(int tri = 0; tri < mpFaces[i].numMeshVerts / 3; tri++)         {             int    vert0 = pFace->startVertIndex +    mpIndexArray[pFace->meshVertIndex + (3 * tri)];             int    vert1 = pFace->startVertIndex +    mpIndexArray[pFace->meshVertIndex + (3 * tri) + 1];             int    vert2 = pFace->startVertIndex +    mpIndexArray[pFace->meshVertIndex + (3 * tri) + 2];             shared_face_edge    edge0,edge1,edge2;             //0 - 1             edge0.vert0 = vert0;             edge0.vert1 = vert1;             //1 - 2             edge1.vert0 = vert1;             edge1.vert1 = vert2;             //2 - 0             edge2.vert0 = vert2;             edge2.vert1 = vert0;                      all_edges.push_back(new shared_face_edge(edge0));             all_edges.push_back(new shared_face_edge(edge1));             all_edges.push_back(new shared_face_edge(edge2));         }              //Step2: count every edge, see how many triangles have this edge         for(tri = 0; tri < mpFaces[i].numMeshVerts / 3; tri++)         {             int    vert0 = pFace->startVertIndex +    mpIndexArray[pFace->meshVertIndex + (3 * tri)];             int    vert1 = pFace->startVertIndex +    mpIndexArray[pFace->meshVertIndex + (3 * tri) + 1];             int    vert2 = pFace->startVertIndex +    mpIndexArray[pFace->meshVertIndex + (3 * tri) + 2];             shared_face_edge    edge0,edge1,edge2;             //0 - 1             edge0.vert0 = vert0;             edge0.vert1 = vert1;             //1 - 2             edge1.vert0 = vert1;             edge1.vert1 = vert2;             //2 - 0             edge2.vert0 = vert2;             edge2.vert1 = vert0;                      std::vector<shared_face_edge*>::iterator    ptr;                 for(ptr = all_edges.begin(); ptr != all_edges.end(); ptr++)             {                 shared_face_edge    *    ref = *ptr;                 if(edge0 == *ref)                     ref->count++;                 else    if(edge1 == *ref)                     ref->count++;                 else    if(edge2 == *ref)                     ref->count++;             }         }                  std::vector<shared_face_edge*>::iterator    ptr;             //Step3: go through and only take the unique edges (count == 1)         for(ptr = all_edges.begin(); ptr != all_edges.end(); ptr++)         {             shared_face_edge    *    ref = *ptr;             if(ref->count == 1)             {                 unique_edges.push_back(new shared_face_edge(*ref));             }         }     //    trace << "This face has: " << pFace->numMeshVerts / 3 << " triangles and it has: " << unique_edges.size() << " unique edges: " << "\n";                  pFace->mpInplanes    =    new    Plane3[unique_edges.size()];         pFace->numInPlanes    =    unique_edges.size();                   //Step4: compute the inward-facing planes          Vector3    *this_vert            = NULL;         Vector3    *next_vert            = NULL;         Vector3    *face_normal        =    &mpFaces[i].vNormal;         Vector3    *plane_normal        = NULL;         Vector3    edge;         int        start_vert_index    =    mpFaces[i].startVertIndex;         int        num_of_verts        =    mpFaces[i].numOfVerts;         int    x = 0;         for(ptr = unique_edges.begin(); ptr != unique_edges.end(); ptr++, x++)         {             shared_face_edge    &    Ref = **ptr;             this_vert            =    &mpVertices[Ref.vert0].vPosition;             next_vert            =    &mpVertices[Ref.vert1].vPosition;             edge            =    *next_vert - *this_vert;             edge.Normalize();             plane_normal    =    &pFace->mpInplanes[x].mNormal;                          *plane_normal    =    CrossProduct(face_normal,&edge) * -1.0f;                 plane_normal->Normalize();             float    DOT = DotProduct(plane_normal,&edge);             mpFaces[i].mpInplanes[x].mDist    =    DotProduct(plane_normal,this_vert);         }         DELETE_MEMORY_AND_ERASE(unique_edges,shared_face_edge);         DELETE_MEMORY_AND_ERASE(all_edges,shared_face_edge);     }  ```
• 06-10-2006
joeprogrammer
Quote:

I know I just dumped a mound of crap on you like that, but it seems that, while you claim to not understand it, you've thought about it a bit and are familiar with a bunch of the terminology.
Well, the extent of my 3D math knowledge has been learned from the Win95GPE and NeHe. So, I can understand things a bit, but I should really take a linear algebra course if I want to get serious about 3D programming.
• 06-10-2006
quzah
I hate PHP tags. Scroll bars? Ug.

Quzah.
• 06-10-2006
BobMcGee123
But It's So Many Pretty Colors!!!