Archived

This topic is now archived and is closed to further replies.

Collision Detection Problem

This topic is 6041 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Im working on a 3d rpg engine, and were at collision detection, this is my CD code i have running, but its not properly working, perhaps its either my code or another aspect of code, could anyone look this over and let me know if it looks ok?  void CollideWithWorld(Point &sourcePoint, Vector velocityVector) { float DistanceToTravel; DistanceToTravel = float(sqrt((velocityVector.x * velocityVector.x) + (velocityVector.y * velocityVector.y) + (velocityVector.z * velocityVector.z))); if(DistanceToTravel < EPSILON) { sourcePoint.x += velocityVector.x; sourcePoint.y += velocityVector.y; sourcePoint.z += velocityVector.z; return;//sourcePoint; } Point destinationPoint; destinationPoint.x = sourcePoint.x + velocityVector.x; destinationPoint.y = sourcePoint.y + velocityVector.y; destinationPoint.z = sourcePoint.z + velocityVector.z; //PQBoundingBoxList *list; // pointer to linked list of bounding boxes PQBoundingBox *box; // pointer to bounding box //list = bblist; box = GetPolyList(bblist); if(box == NULL) { sourcePoint.x += velocityVector.x; sourcePoint.y += velocityVector.y; sourcePoint.z += velocityVector.z; return;// sourcePoint; } bool firstTimeThrough = true; float NearDistance = -1.0f; Poly nearestCollider; Point nearestIntersectionPoint; Point nearestPolygonIntersectionPoint; for(int i = 0; i < box->numtriangles; i++) { Point pOrigin; Point p1,p2,p3; Poly poly1; p1.x = box->triangles[0].x; p1.y = box->triangles[0][i].y; p1.z = box->triangles[0][i].z; pOrigin = p1; p2.x = box->triangles[1][i].x; p2.y = box->triangles[1][i].y; p2.z = box->triangles[1][i].z; p3.x = box->triangles[2][i].x; p3.y = box->triangles[2][i].y; p3.z = box->triangles[2][i].z; poly1.c1 = p1; poly1.c2 = p2; poly1.c3 = p3; Vector pNormal = CalculateNormal(p1, p2, p3); Vector pTemp; pTemp.x = -pNormal.x; pTemp.y = -pNormal.y; pTemp.z = -pNormal.z; float pDist = intersect(sourcePoint, pTemp, pOrigin, pNormal); Point planeIntersectionPoint; Point ellipsoidIntersectionPoint; Vector directionalRadius; directionalRadius.x = -pNormal.x * radiusVector.x; directionalRadius.y = -pNormal.y * radiusVector.y; directionalRadius.z = -pNormal.z * radiusVector.z; float radius; radius = float(sqrt((directionalRadius.x * directionalRadius.x) + (directionalRadius.y * directionalRadius.y) + (directionalRadius.z * directionalRadius.z))); if(fabs(pDist) <= radius) { Vector temp; temp.x = -(pNormal.x / pNormal.x) * pDist; temp.y = -(pNormal.y / pNormal.y) * pDist; temp.z = -(pNormal.z / pNormal.z) * pDist; planeIntersectionPoint.x = sourcePoint.x + temp.x; planeIntersectionPoint.y = sourcePoint.y + temp.y; planeIntersectionPoint.z = sourcePoint.z + temp.z; } else { Vector temp; temp.x = -(pNormal.x / pNormal.x) * radius; temp.y = -(pNormal.y / pNormal.y) * radius; temp.z = -(pNormal.z / pNormal.z) * radius; ellipsoidIntersectionPoint.x = sourcePoint.x + temp.x; ellipsoidIntersectionPoint.y = sourcePoint.y + temp.y; ellipsoidIntersectionPoint.z = sourcePoint.z + temp.z; float t = intersect(ellipsoidIntersectionPoint, velocityVector, pOrigin, pNormal); Vector V; V.x = (velocityVector.x / velocityVector.x) * t; V.y = (velocityVector.y / velocityVector.y) * t; V.z = (velocityVector.z / velocityVector.z) * t; } Point polygonIntersectionPoint = planeIntersectionPoint; if(CheckPointInTriangle(planeIntersectionPoint, p1, p2, p3)) { polygonIntersectionPoint = closestPointOnTriangle(p1, p2, p3, planeIntersectionPoint); } Vector negativeVelocityVector; negativeVelocityVector.x = -velocityVector.x; negativeVelocityVector.y = -velocityVector.y; negativeVelocityVector.z = -velocityVector.z; float t = intersectSphere(sourcePoint, radiusVector, polygonIntersectionPoint, negativeVelocityVector); if(t >= 0.0f && t <= DistanceToTravel) { Vector V; V = NormalizeVector(negativeVelocityVector); V.x *= t; V.y *= t; V.z *= t; Vector intersectPoint; intersectPoint.x = polygonIntersectionPoint.x + V.x; intersectPoint.y = polygonIntersectionPoint.y + V.y; intersectPoint.z = polygonIntersectionPoint.z + V.z; if(firstTimeThrough || t < NearDistance) { NearDistance = t; nearestCollider = poly1; nearestIntersectionPoint = intersectPoint; nearestPolygonIntersectionPoint = polygonIntersectionPoint; firstTimeThrough = false; } } } if(firstTimeThrough) { sourcePoint.x += velocityVector.x; sourcePoint.y += velocityVector.y; sourcePoint.z += velocityVector.z; return;// sourcePoint; } Vector V; V = NormalizeVector(velocityVector); V.x *= float(NearDistance - EPSILON); V.y *= float(NearDistance - EPSILON); V.z *= float(NearDistance - EPSILON); sourcePoint.x += V.x; sourcePoint.y += V.y; sourcePoint.z += V.z; Point slidePlaneOrigin = nearestPolygonIntersectionPoint; Vector slidePlaneNormal = nearestPolygonIntersectionPoint; slidePlaneNormal.x -= sourcePoint.x; slidePlaneNormal.y -= sourcePoint.y; slidePlaneNormal.z -= sourcePoint.z; float time = intersect(destinationPoint, slidePlaneNormal, slidePlaneOrigin, slidePlaneNormal); slidePlaneNormal = NormalizeVector(slidePlaneNormal); slidePlaneNormal.x *= time; slidePlaneNormal.y *= time; slidePlaneNormal.z *= time; Vector destinationProjectionNormal = slidePlaneNormal; Point newDestinationPoint = destinationPoint; newDestinationPoint.x += destinationProjectionNormal.x; newDestinationPoint.y += destinationProjectionNormal.y; newDestinationPoint.z += destinationProjectionNormal.z; Vector newVelocityVector = newDestinationPoint; newVelocityVector.x -= nearestPolygonIntersectionPoint.x; newVelocityVector.y -= nearestPolygonIntersectionPoint.y; newVelocityVector.z -= nearestPolygonIntersectionPoint.z; CollideWithWorld(sourcePoint, newVelocityVector); //return sourcePoint; } 

Share on other sites
Oh boy... This is hard to read... Err, got a moment? A *long* moment?

Share on other sites
i cleaned it up alil using operator overloading to save some space. and fixed my normalizing of vector, but it still drops right through the floor and dont collide with anything

Share on other sites
Please post that inside source tags..?! :-)

Share on other sites
You should also indent your source (that''ll make it easier to read.)

Share on other sites
i thought i did indent it, anyway, heres all my collision stuff pretty much..
#define Point Vectorstruct Poly{	Point c1;	Point c2;	Point c3;};#define EPSILON 0.0001#define PI 3.14519Vector radiusVector(0.2f, 0.2f, 0.2f);Point Cross_Product(Point a, Point b){	Point returnValue;	returnValue.x = (a.y * b.z) - (a.z * b.y);	returnValue.y = (a.z * b.x) - (a.x * b.z);	returnValue.z = (a.x * b.y) - (a.y * b.x);	return returnValue;}float Dot_Product(Point a, Point b){	return ((a.x * b.x) + (a.y * b.y) + (a.z * b.z));}float Distance(Point a, Point b){	float x, y, z;	x = a.x - b.x;	y = a.y - b.y;	z = a.z - b.z;	return float(sqrt((x*x) + (y*y) + (z*z)));}Vector NormalizeVector(Vector v){	v.x = v.x / fabs(v.x);	v.y = v.y / fabs(v.y);	v.z = v.z / fabs(v.z);	return v;}bool CheckPointInTriangle(Point p, Point a, Point b, Point c) {    float total_angles = 0.0f;         // make the 3 vectors  Point v1, v2, v3;  v1.x = p.x - a.x;  v1.y = p.y - a.y;  v1.z = p.z - a.z;  v2.x = p.x - b.x;  v2.y = p.y - b.y;  v2.z = p.z - b.z;  v3.x = p.x - c.x;  v3.y = p.y - c.y;  v3.z = p.z - c.z;    v1 = NormalizeVector(v1);  v2 = NormalizeVector(v2);  v3 = NormalizeVector(v3);  total_angles += float(acos(Dot_Product(v1,v2)));     total_angles += float(acos(Dot_Product(v2,v3)));  total_angles += float(acos(Dot_Product(v3,v1)));       // allow a small margin because of the limited precision of  // floating point math.  if (fabs(total_angles-2*PI) <= 0.005)   return (TRUE);       return(FALSE);}float intersect(Point pOrigin, Vector pNormal, Point rOrigin, Vector rVector){   float d = -((pNormal.x * pOrigin.x) + (pNormal.y * pOrigin.y) + (pNormal.z * pOrigin.z));   float numer = ((pNormal.x * rOrigin.x) + (pNormal.y * rOrigin.y) + (pNormal.z * rOrigin.z) + d);   float denom = ((pNormal.x * rVector.x) + (pNormal.y * rVector.y) + (pNormal.z * rVector.z));   return -(numer / denom);}float intersectSphere(Point rO, Vector rV, Point sO, float sR){	Vector Q;	Q.x = sO.x - rO.x;	Q.y = sO.y - rO.y;	Q.z = sO.z - rO.z;	float c = float(sqrt((Q.x * Q.x) + (Q.y * Q.y) + (Q.z * Q.z)));	float v;	v = ((Q.x * rV.x) + (Q.y * rV.y) + (Q.z * rV.z));	float d = (sR * sR) - ((c * c) + (v * v));	// If there was no intersection, return -1	if (d < 0.0) return -1.0;	// Return the distance to the [first] intersecting point	return v - float(sqrt(d));} Point closestPointOnLine(Point a, Point b, Point p){   // Determine t (the length of the vector from ‘a’ to ‘p’)	Vector c = p - a;	Vector V = b - a;	float d = Distance(a, b);	float t = ((V.x * c.x) + (V.y + c.y) + (V.z + c.z));	// Check to see if ‘t’ is beyond the extents of the line segment	if (t < 0) return a;	if (t > 0) return b;	// Return the point between ‘a’ and ‘b’	V = NormalizeVector(V);	V *= t;	V += a;	return V;}Point closestPointOnTriangle(Point a, Point b, Point c, Point p){    Point Rab = closestPointOnLine(a, b, p);    Point Rbc = closestPointOnLine(b, c, p);    Point Rca = closestPointOnLine(c, a, p);	float dab, dbc, dca;	dab = Distance(Rab, p);	dbc = Distance(Rbc, p);	dca = Distance(Rca, p);    	if(dab <= dbc && dab <= dca) return Rab;	if(dbc <= dab && dbc <= dca) return Rbc;	if(dca <= dab && dca <= dbc) return Rca;	return Rab;}Vector CalculateNormal(Point p1, Point p2, Point p3){	float qX, qY, qZ, pX, pY, pZ;	Vector normal;	qX = p2.x - p1.x;	qY = p2.y - p1.y;	qZ = p2.z - p1.z;	pX = p3.x - p1.x;	pY = p3.y - p1.y;	pZ = p3.z - p1.z;	normal.x = (pY * qZ) - (pZ * qY);	normal.y = (pZ * qX) - (pX * qZ);	normal.z = (pX * qY) - (pY * qX);	return normal;}PQBoundingBox *GetPolyList(PQBoundingBoxList *list){	PQBoundingBox *box; 	static PQBoundingBoxList *tmp=NULL;	float x = camera->GetX();	float y = camera->GetY();	float z = camera->GetZ();	if (tmp == NULL)		tmp = list;	while(tmp != NULL)	{		// Get current bounding box from the list		box = tmp->ptr;		tmp = tmp->next;		// Check to see if our location is withing the bb		if ( x >= box->min.x && x <= box->max.x &&			 y >= box->min.y && y <= box->max.y &&			 z >= box->min.z && z <= box->max.z )			return box;	}	return NULL;}void CollideWithWorld(Point &sourcePoint, Vector velocityVector){	float DistanceToTravel = float(sqrt((velocityVector.x * velocityVector.x) +										(velocityVector.y * velocityVector.y) +										(velocityVector.z * velocityVector.z)));	if(DistanceToTravel < EPSILON)	{		sourcePoint += velocityVector;		return;//sourcePoint;	}	Point destinationPoint = sourcePoint + velocityVector;	//PQBoundingBoxList *list; // pointer to linked list of bounding boxes	PQBoundingBox *box;	// pointer to bounding box	//list = bblist;	box = GetPolyList(bblist);	if(box == NULL)	{		sourcePoint += velocityVector;		return;// sourcePoint;	}	bool firstTimeThrough = true;	float NearDistance = -1.0f;	Poly nearestCollider;	Point nearestIntersectionPoint;	Point nearestPolygonIntersectionPoint;	while (box != NULL)	{		for(int i = 0; i < box->numtriangles; i++)		{			Point pOrigin;			Point p1,p2,p3;			Poly poly1;			p1.x = box->triangles[0].x;			p1.y = box->triangles[0][i].y;			p1.z = box->triangles[0][i].z;			pOrigin = p1;			p2.x = box->triangles[1][i].x;			p2.y = box->triangles[1][i].y;			p2.z = box->triangles[1][i].z;			p3.x = box->triangles[2][i].x;			p3.y = box->triangles[2][i].y;			p3.z = box->triangles[2][i].z;			poly1.c1 = p1;			poly1.c2 = p2;			poly1.c3 = p3;			Vector pNormal = CalculateNormal(p1, p2, p3);			float pDist = intersect(sourcePoint, -pNormal, pOrigin, pNormal);			Point planeIntersectionPoint;			Point ellipsoidIntersectionPoint;			Vector directionalRadius = -pNormal * radiusVector;			float radius = float(sqrt((directionalRadius.x * directionalRadius.x) +									  (directionalRadius.y * directionalRadius.y) +									  (directionalRadius.z * directionalRadius.z)));			if(fabs(pDist) <= radius)			{				Vector temp = -pNormal * pDist;				planeIntersectionPoint = sourcePoint + temp;			}			else			{				Vector temp = -pNormal * radius;				ellipsoidIntersectionPoint = sourcePoint + temp;				float t = intersect(ellipsoidIntersectionPoint, velocityVector, pOrigin, pNormal);				Vector V = velocityVector * t;				// Added:  planeIntersectionPoint = ellipsoidIntersectionPoint + V;				planeIntersectionPoint = ellipsoidIntersectionPoint + V;			}			Point polygonIntersectionPoint = planeIntersectionPoint;			if(CheckPointInTriangle(planeIntersectionPoint, p1, p2, p3))			{				polygonIntersectionPoint = closestPointOnTriangle(p1, p2, p3, planeIntersectionPoint);			}			float t = intersectSphere(sourcePoint, radiusVector, polygonIntersectionPoint, radius);			if(t >= 0.0f && t <= DistanceToTravel)			{				Vector V;				V = NormalizeVector(-velocityVector) * t;				Vector intersectPoint = polygonIntersectionPoint + V;				if(firstTimeThrough || t < NearDistance)				{					NearDistance = t;					nearestCollider = poly1;					nearestIntersectionPoint = intersectPoint;					nearestPolygonIntersectionPoint = polygonIntersectionPoint;					firstTimeThrough = false;				}			}		}		box = GetPolyList(bblist);	}	if(firstTimeThrough)	{		sourcePoint += velocityVector;		return;// sourcePoint;	}	Vector V = NormalizeVector(velocityVector);	V *= float(NearDistance - EPSILON);	sourcePoint += V;	Point  slidePlaneOrigin = nearestPolygonIntersectionPoint;	Vector slidePlaneNormal = nearestPolygonIntersectionPoint;	slidePlaneNormal -= sourcePoint;	float time = intersect(destinationPoint, slidePlaneNormal, slidePlaneOrigin, slidePlaneNormal);	slidePlaneNormal = NormalizeVector(slidePlaneNormal) * time;	Vector destinationProjectionNormal = slidePlaneNormal;	Point  newDestinationPoint = destinationPoint + destinationProjectionNormal;	Vector newVelocityVector = newDestinationPoint - nearestPolygonIntersectionPoint;	CollideWithWorld(sourcePoint, newVelocityVector);	//return sourcePoint;}Point Collision_Detection(Point &sourcePoint, Vector velocityVector, Vector gravityVector){	//Point destinationPoint;	//eventually	velocityVector += gravityVector;	CollideWithWorld(sourcePoint, velocityVector);	return sourcePoint;}

Edited by - rgirard413 on November 6, 2001 2:17:04 PM

Edited by - rgirard413 on November 6, 2001 2:17:27 PM

• 17
• 10
• 19
• 14
• 19