Thread: Collision detection woes

  1. #1
    User
    Join Date
    Jan 2006
    Location
    Canada
    Posts
    499

    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?

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Make sure you normalize the plane.
    Last edited by Perspective; 06-06-2006 at 05:56 PM.

  3. #3
    User
    Join Date
    Jan 2006
    Location
    Canada
    Posts
    499
    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?

  4. #4
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    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.

  5. #5
    User
    Join Date
    Jan 2006
    Location
    Canada
    Posts
    499
    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

  6. #6

    Join Date
    May 2005
    Posts
    1,042
    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;
    }
    I'm not immature, I'm refined in the opposite direction.

  7. #7
    User
    Join Date
    Jan 2006
    Location
    Canada
    Posts
    499
    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

  8. #8

    Join Date
    May 2005
    Posts
    1,042
    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.
    I'm not immature, I'm refined in the opposite direction.

  9. #9

    Join Date
    May 2005
    Posts
    1,042
    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(0mNumFacesi++)
        {
            
    std::vector<shared_face_edge*>    all_edges;
            
    std::vector<shared_face_edge*>    unique_edges;

            
    tBSPFace    *pFace = &mpFaces[i];
            
            
    Vector3    center;

            for(
    int vert 0vert pFace->numOfVertsvert++)
            {
                
    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 0tri mpFaces[i].numMeshVerts 3tri++)
            {
                
    int    vert0 pFace->startVertIndex +    mpIndexArray[pFace->meshVertIndex + (tri)];
                
    int    vert1 pFace->startVertIndex +    mpIndexArray[pFace->meshVertIndex + (tri) + 1];
                
    int    vert2 pFace->startVertIndex +    mpIndexArray[pFace->meshVertIndex + (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 0tri mpFaces[i].numMeshVerts 3tri++)
            {
                
    int    vert0 pFace->startVertIndex +    mpIndexArray[pFace->meshVertIndex + (tri)];
                
    int    vert1 pFace->startVertIndex +    mpIndexArray[pFace->meshVertIndex + (tri) + 1];
                
    int    vert2 pFace->startVertIndex +    mpIndexArray[pFace->meshVertIndex + (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);
        } 
    Last edited by BobMcGee123; 06-10-2006 at 06:28 PM.
    I'm not immature, I'm refined in the opposite direction.

  10. #10
    User
    Join Date
    Jan 2006
    Location
    Canada
    Posts
    499
    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.

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I hate PHP tags. Scroll bars? Ug.


    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12

    Join Date
    May 2005
    Posts
    1,042
    But It's So Many Pretty Colors!!!
    I'm not immature, I'm refined in the opposite direction.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Collision Detection Problems
    By Dark_Phoenix in forum Game Programming
    Replies: 1
    Last Post: 12-17-2006, 03:25 PM
  2. Collision Detection
    By Grantyt3 in forum C++ Programming
    Replies: 3
    Last Post: 09-30-2005, 03:21 PM
  3. bounding box collision detection
    By DavidP in forum Game Programming
    Replies: 7
    Last Post: 07-07-2002, 11:43 PM
  4. collision detection
    By DavidP in forum Game Programming
    Replies: 2
    Last Post: 05-11-2002, 01:31 PM
  5. Replies: 4
    Last Post: 05-03-2002, 09:40 PM