Archived

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

rgirard413

Collision Detection Problem

Recommended Posts

rgirard413    133
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].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 this post


Link to post
Share on other sites
grhodes_at_work    1385
This isn''t a forum to provide code reviews.

Collision detection is related to math and physics for games, but please restate your request as a specific question.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
quote:
Original post by rgirard413
Ok.. how bout, how do you incorporate collision detection?


Hi rgirard413,

Thanks for restating your request. That certainly is a specific question, but its very general and general questions usually take a lot of effort and time to answer. I actually only have time to give the obvious answer, which is: look at some tutorials on the web. Here are a few links:

http://www.gamasutra.com/features/19991018/Gomez_1.htm
http://www.gamasutra.com/features/20000210/lander_01.htm
http://www.gamasutra.com/features/20000208/lander_01.htm
http://www.gamasutra.com/features/20000203/lander_01.htm
http://www.gamasutra.com/features/20000330/bobic_01.htm
http://www.gamedev.net/reference/articles/article1026.asp

You''ll have to register (free) to get the gamasutra articles, but they are generally pretty good. (They were all published in Game Developer Magazine.)

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
rgirard413    133
hmm, i looked them over. I think i need to ask more directly..

What Im doing is using bounding boxes, and testing if im in it, then if i am, use the triangles that are in that bounding box, but for some reason somewhere there not colliding at all.

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
Yes, okay, this is a better question. But my reply may ramble a bit.

I did a quick glance over your code. Its a lot of code, so lets fix it piece-by-piece. This is just the first step.

My first observation is that there appears to be at least one typo in your code:


...
Poly poly1;
p1.x = box->triangles[0].x;
p1.y = box->triangles[0].y;
p1.z = box->triangles[0].z;
pOrigin = p1;
...


Shouldn''t this be:


...
Poly poly1;
p1.x = box->triangles[0][i].x;
p1.y = box->triangles[0][i].y;
p1.z = box->triangles[0][i].z;
pOrigin = p1;
...


???

My second observation is that your code is a bit hard to read. Why not use tabs? Instead of


if {this and that)
{
do some stuff
do some more stuff
for (some loop)
{
inner loop stuff
}
}


Do this:


if {this and that)
{
do some stuff
do some more stuff
for (some loop)
{
inner loop stuff
}
}


It will be easier to follow the logic that way. Its also a long function, and for debugging purposes (at least), you might consider breaking it into multiple functions with well-defined inputs and outputs. That way, it''ll be easier to find which piece is failing. The failure could be in the inputs or in calculating the outputs.

My third observation is that you''re using very complex logic for the bounding box test. Did you build your logic based on one of the articles you''ve read? Its okay to use complex logic when it works, but the more complex the logic the less likely it is to work. Also be aware that it will be slower than it has to be. I suspect your code is going to be very slow when you get it to work. One way to speed it up (a little bit) is to precalculate the triangle normals rather than calculate them every time you collide against the box. If its an aligned box, then you don''t even have to calculate them since they''ll be either (1,0,0), (0,1,0), or (0,0,1). If you use oriented boxes then you can still precalculate and just transform the normals when you transform the geometry.

Look at this part of your code:


for(int i = 0; i < box->numtriangles; i++)
{
Point pOrigin;
Point p1,p2,p3;
...
// set some points
// calculate normal
// call a function called "intersect"
// maybe call "intersect" again
// maybe call "intersectSphere"
// maybe call "intersect" again
...


Lots of "intersects*"''s in there. Here, it appears that you are walking through the triangles representing the box and checking your intersection point against each of the bounding box triangles. The only reason I see to do this is if your bounding boxes are oriented bounding boxes (OBB''s). Even then this logic is complex. If you are using axis-aligned boxes then I would expect to see some very simple logic such as:


if (sourcePoint.x > box.xmax || sourcePoint.x < box.xmin ||
sourcePoint.x > box.xmax || sourcePoint.x < box.xmin ||
sourcePoint.x > box.xmax || sourcePoint.x < box.xmin)
{
// no collision possible
}
else
{
// mesh did collide with bounding box. did deeper and collide
// point with full meshes.
}


My written logic here is quick-and-dirty and a bit incomplete. I mean, you''d want to test the entire line from sourcePoint to sourcePoint + velocityVector instead of just sourcePoint as I''ve shown. But the idea is to check against the global bounds of the bounding box, not against the individual triangles that represent a mesh of the bounding box. There isn''t really even any need to store a mesh of the bounding box. Just store the bounds and, if its an oriented box, the transformation matrix.

If you do have oriented bounding boxes, then you can still use the simpler logic. But you would have to transform sourcePoint and velocityVector into a coordinate system aligned with the oriented box before testing. But that transformation is simpler than the logic you''re using.

(There is a benefit to checking against bounding box triangles. You are at least already debugging the full triangle mesh collision test you will be doing if there is a collision with the box.)

I don''t immediately see why you are doing anything with ellipsoids and spheres. I suspect you are using a reference that I''m not familiar with.

Why not write out your logic----not your code----and we''ll see if there''s a flaw in your logic?


Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
rgirard413    133
In my code it is tabed, for some reason it didnt tab on here, and I have changed my code a lot and has a lot more functions and the process is different now, but it still does not work properly. The bounding boxes are pre created and i have a function that draws them all out, and then changes the color of the one that your in and outlines all hte polys that are in that one so you can see that its working properly..

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
Hi,

You can force the tabs to display correctly here if you place "[ code]" and "[ /code]" around the source code in your post. So when you type in your post, you might have something that looks like this:

[ code]

for (j = 0; j < num_triangles; j++
{
for (k = 0; k < 3; k++)
{
// do some vertex stuff
}
}

[ /code]

The message board will interpret these markup tags as formatting instructions, and it will leave your tabs intact. You should not have any spaces in the markup tags. I only put them here so the tag names would be displayed. You can also use the tags "[ source]....your code.....[ /source]" to create a white window box around the code. Makes it standout nice.

Your color coding is a good way to check the collision detection.

I would suggest that you also consider drawing additional information to the screen to help debug the broken implementation:

1) the plane intersection points
2) a line between sourcePoint and sourcePoint+velocityVector
3) the ellipsoid intersection points

See if those things are being calculated correctly. Is your new code based on simpler logic?

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites