1. ## 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);
}```
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. Make sure you normalize the plane.

3. 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. 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. 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. 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

return	FALSE;
{
++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();

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,
{
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;

planedist1	=	DotProduct(&InwardVector,&LocalPoint);

{
return	FALSE;
}
{
++num_intersections;
}

LocalPoint	=	Point  - Point2;
DiffVector	=	Point3 - Point2;
InwardVector	=	CrossProduct(&Normal,&DiffVector);
InwardVector.Normalize();

planedist2	=	DotProduct(&InwardVector,&LocalPoint);

{
return	FALSE;
}
{
++num_intersections;
}

LocalPoint	=	Point  - Point3;
DiffVector	=	Point1 - Point3;
InwardVector	=	CrossProduct(&Normal,&DiffVector);
InwardVector.Normalize();

planedist3	=	DotProduct(&InwardVector,&LocalPoint);

{
return	FALSE;
}
{
++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,
{
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;

planedist1	=	DotProduct(&InwardVector,&LocalPoint);

{
return	FALSE;
}
{
++num_intersections;
}

LocalPoint	=	Point  - Point2;
DiffVector	=	Point3 - Point2;
InwardVector	=	CrossProduct(&Normal,&DiffVector);
InwardVector.Normalize();

planedist2	=	DotProduct(&InwardVector,&LocalPoint);

{
return	FALSE;
}
{
++num_intersections;
}

LocalPoint	=	Point  - Point3;
DiffVector	=	Point1 - Point3;
InwardVector	=	CrossProduct(&Normal,&DiffVector);
InwardVector.Normalize();

planedist3	=	DotProduct(&InwardVector,&LocalPoint);

{
return	FALSE;
}
{
++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,
{
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;

planedist1	=	DotProduct(&InwardVector,&LocalPoint);

return	FALSE;
{
++num_intersections;
if(planedist1	>=	0)
++pos_intersections;
}

LocalPoint	=	Point  - Point2;
DiffVector	=	Point3 - Point2;
InwardVector	=	CrossProduct(&Normal,&DiffVector);
InwardVector.Fast_Normalize();

planedist2	=	DotProduct(&InwardVector,&LocalPoint);

return	FALSE;
{
++num_intersections;
if(planedist2	>=	0)
++pos_intersections;
}

LocalPoint	=	Point  - Point3;
DiffVector	=	Point1 - Point3;
InwardVector	=	CrossProduct(&Normal,&DiffVector);
InwardVector.Fast_Normalize();

planedist3	=	DotProduct(&InwardVector,&LocalPoint);

return	FALSE;
{
++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,
{
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;

planedist1	=	DotProduct(&InwardVector,&LocalPoint);

{
return	FALSE;
}
{
++num_intersections;

if(planedist1 >= 0)
++pos_intersections;
}

LocalPoint	=	Point  - Point2;
DiffVector	=	Point3 - Point2;
InwardVector	=	CrossProduct(&Normal,&DiffVector);
InwardVector.Fast_Normalize();

planedist2	=	DotProduct(&InwardVector,&LocalPoint);

{
return	FALSE;
}
{
++num_intersections;
if(planedist2 >= 0)
++pos_intersections;
}

LocalPoint	=	Point  - Point3;
DiffVector	=	Point1 - Point3;
InwardVector	=	CrossProduct(&Normal,&DiffVector);
InwardVector.Fast_Normalize();

planedist3	=	DotProduct(&InwardVector,&LocalPoint);

{
return	FALSE;
}
{
++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)
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,
{
BOOL	retval = false;

Vector3	A = PStart - QStart;
Vector3	B = (PEnd - PStart) - (QEnd - QStart); //relative velocity

double	ASq = A.BasicLength();
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));
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	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,
{

Vector3	A = PStart - QStart;
Vector3	B = (PEnd - PStart) - (QEnd - QStart); //relative velocity

double	ASq = A.BasicLength();
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_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 << "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;
}```

7. 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. 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.

9. 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);     }  ```

10. 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. I hate PHP tags. Scroll bars? Ug.

Quzah.

12. But It's So Many Pretty Colors!!!