Determination of 3d collision point
Author
Hey,
I've tried to search these forums and the net for help with this (and have found some excellent resources for calculating response) but it seems difficult to accurately determine point of collision for 3d objects.
Some of Oliii's posted code seems to touch on this but to be honest I'm not sure I understand what's going on. I can appreciate that you have a number of potential different collision types: point-plane, point-point, edge-edge, etc.. but I'm no sure I understand the method to determine exact point of intersection.
Given that I can compute the normal of collision and its depth could someone point me to, or explain the rough method of finding the actual points of collision on the colliding objects?
Thanks
if you have the collision depth and normal, find the set of support points on both objects along the normal. For boxes, for example, it can be 1 point (a corner is the support point), 2 points (the edge vertices are the support points), of 4 (a face vertices are the supporting vertices).
Do that on both objects, and in the end will give you either a edge-edge collision (two support points against two support points on the other object), a point-face (one vertex against 4 vertices on the other object), or a edge-face (two support vertices found against 4 support vertices).
in case of a point-face, the collision points are straight forward. one will be the vertex, the other will be teh projection of the point onto the face.
in case of a edge-edge, the collision points will be the points on both edges the closest to each other (like when doing a edge-edge distance calculation).
in case of an edge and a face, you need to clip the edge to the face, and project the points of the edge onto the face to find the corresponding contact points on the other object.
in case of a face and a face, you need to clip one of the face to the other face, and project the points found onto the other face to find the corresponding contact points on the other object.
you can generalise the face-face and edge-face to general convex polygons, so you can apply it to convex hulls, triangles and other polyhedras.
I can't really explain it more than that :) I guess I'd have to write an example or something...
Do that on both objects, and in the end will give you either a edge-edge collision (two support points against two support points on the other object), a point-face (one vertex against 4 vertices on the other object), or a edge-face (two support vertices found against 4 support vertices).
in case of a point-face, the collision points are straight forward. one will be the vertex, the other will be teh projection of the point onto the face.
in case of a edge-edge, the collision points will be the points on both edges the closest to each other (like when doing a edge-edge distance calculation).
in case of an edge and a face, you need to clip the edge to the face, and project the points of the edge onto the face to find the corresponding contact points on the other object.
in case of a face and a face, you need to clip one of the face to the other face, and project the points found onto the other face to find the corresponding contact points on the other object.
you can generalise the face-face and edge-face to general convex polygons, so you can apply it to convex hulls, triangles and other polyhedras.
I can't really explain it more than that :) I guess I'd have to write an example or something...
Author
Cheers for your reply oliii :-)
Quote:
if you have the collision depth and normal, find the set of support points on both objects along the normal.
How exactly do you go about this? Is it simply a case of comparing all the points of each box to find the closest ones?
If so, how then can you detemine how many points of contact that you have?
Quote:
Do that on both objects, and in the end will give you either a edge-edge collision (two support points against two support points on the other object), a point-face (one vertex against 4 vertices on the other object), or a edge-face (two support vertices found against 4 support vertices).
Although unlikely, couldn't you also have point-point, point-edge, etc? can these be handled in the same manner?
Thanks again for your time
- nroc
a support function could looks like this, for say, a triangle.
so basically, it returns the lowest vertices along the direction you supply, aka your normal of collision, or the oposite for the other object.
say you have two triangles, then
the ConvertSuportPointToContactPoint() takes the list of support points for both objects, and calculate the corrsponding contact points.
as I said in the previous post,
point-face => one contact pair
edge-edge => one contact pair
edge-face => two contact pairs
face-face => up to 6 contact pairs I believe.
I'm assuming you are using a separation axis algorithm, so that would be the only cases, but you can have other cases, like point-edge, or point-point, as you say, if you do it the coll det differently.
then in that case,
point-edge => one contact pair.
point-point=> one contact pair.
so the real sticky part is edge-face and face-face.
in that case, I'd clip one of the face (or the edge) with an extruded version of the other face, basically, build planes perpendicular to the clipping face's edges and the clipping face normal, and cut away the edge of the clipped face. that will give you the contact polygon, then it's simply a matter of projecting the contact patch onto the clipping face's plane to find the corresponding contact points to make pairs.
it sounds complicated, but a drawing would be a lot easier, unfortunately, I can;t be arsed :)
it's a standard 3D convex hull clipping algorithm anyway, so should be easy to find some materials about that.
that's the way I'd do it, obviously, people might disagree :)
[Edited by - oliii on July 6, 2004 5:08:53 PM]
int CTriangle::FindSupportPoints(const Vector& Dir, Vector* Support) const{ float d[3]; d[0] = V[0] * Dir; d[1] = V[1] * Dir; d[2] = V[2] * Dir; float min = min(min(d[0], d[1]), d[2]); const float threshold = 1.0E-6f; int iNumSupport = 0; if (d[0] <= min + threshold) { Support[iNumSupport++] = V[0]; } if (d[1] <= min + threshold) { Support[iNumSupport++] = V[1]; } if (d[2] <= min + threshold) { Support[iNumSupport++] = V[2]; } return iNumSupport;}so basically, it returns the lowest vertices along the direction you supply, aka your normal of collision, or the oposite for the other object.
say you have two triangles, then
int CalculateContacts(const CTriangle& TriA, const CTriangle& TriB, Vector* ContactPointsA, Vector* ContactPointsB){ Vector SupportA[3]; Vector SupportB[3]; int iNumSupportA = TriA.FindSupportPoints( Ncoll, SupportA); int iNumSupportB = TriB.FindSupportPoints(-Ncoll, SupportB); return ConvertSuportPointToContactPoint(SupportA, iNumSupportA, SupportB, iNumSupportB, ContactPointsA, ContactPointsB);}the ConvertSuportPointToContactPoint() takes the list of support points for both objects, and calculate the corrsponding contact points.
as I said in the previous post,
point-face => one contact pair
edge-edge => one contact pair
edge-face => two contact pairs
face-face => up to 6 contact pairs I believe.
I'm assuming you are using a separation axis algorithm, so that would be the only cases, but you can have other cases, like point-edge, or point-point, as you say, if you do it the coll det differently.
then in that case,
point-edge => one contact pair.
point-point=> one contact pair.
so the real sticky part is edge-face and face-face.
in that case, I'd clip one of the face (or the edge) with an extruded version of the other face, basically, build planes perpendicular to the clipping face's edges and the clipping face normal, and cut away the edge of the clipped face. that will give you the contact polygon, then it's simply a matter of projecting the contact patch onto the clipping face's plane to find the corresponding contact points to make pairs.
it sounds complicated, but a drawing would be a lot easier, unfortunately, I can;t be arsed :)
it's a standard 3D convex hull clipping algorithm anyway, so should be easy to find some materials about that.
that's the way I'd do it, obviously, people might disagree :)
[Edited by - oliii on July 6, 2004 5:08:53 PM]
Author
Thanks for the lengthy response!
This clears things up somewhat for me, though I have a few questions for completeness sake ;-)
Re: FindSupportPoints(), I assume the * represents dot product, and I understand that the dot product can be used to find the distance of a plane from the origin, given that planes normal and a point on the plane.. how does that apply here specifically? (i.e. is this what we're trying to find?)
Also, I noted we take the lowest result of above operation then determine how many contact points there are based on other points being (approximately) equal to this lowest point.. is the lowest point the 'closest'?
I am using separating axis tests, based mostly on previous posts found in this forum, and Baraffs papers on the subject.
At this stage I don't need to/intend to do anything than orientated bounding box collision tests, tho I guess as you say the method presented looks like it will hold for 3d bounding boxes?
Apologies for being a bit thick!
- nroc
This clears things up somewhat for me, though I have a few questions for completeness sake ;-)
Re: FindSupportPoints(), I assume the * represents dot product, and I understand that the dot product can be used to find the distance of a plane from the origin, given that planes normal and a point on the plane.. how does that apply here specifically? (i.e. is this what we're trying to find?)
Also, I noted we take the lowest result of above operation then determine how many contact points there are based on other points being (approximately) equal to this lowest point.. is the lowest point the 'closest'?
I am using separating axis tests, based mostly on previous posts found in this forum, and Baraffs papers on the subject.
At this stage I don't need to/intend to do anything than orientated bounding box collision tests, tho I guess as you say the method presented looks like it will hold for 3d bounding boxes?
Apologies for being a bit thick!
- nroc
the dot product is used as a projection. basically, imagine the axis being the X axis (1, 0, 0).
doing the operation I described, you can see that you end up comparing the X values of each point and take the minimums.
Imagine the triangle with normal equal to the X axis. Then in that case, all the three points of the triangle will yield the same X value, and they'll all be a support point.
If the X axis was your normal of collison, then you can see that the part of the triangle that would collide is indeed the face, so it's all consistent.
So basically, the algo returns the parts of a shape that is 'supporting' the shape along an axis. If you collided a box against a table, then the supporting points would be the points with the lowest Y value. For the table, the collision feature would be the uppoer face, the points with the maximum Y value.
You don't need to find the actual closest features of two convex objects colliding, if you already have the collision normal. You merely have to find the points the 'lowest' along the normal on one shape, and the points on the other object the 'highest' along the normal.
If you use the algo for a box, yo uhave to be careful when you extract the vertices of a face. Make sure they are ordered correctly, so they form a convex polygon.
doing the operation I described, you can see that you end up comparing the X values of each point and take the minimums.
Imagine the triangle with normal equal to the X axis. Then in that case, all the three points of the triangle will yield the same X value, and they'll all be a support point.
If the X axis was your normal of collison, then you can see that the part of the triangle that would collide is indeed the face, so it's all consistent.
So basically, the algo returns the parts of a shape that is 'supporting' the shape along an axis. If you collided a box against a table, then the supporting points would be the points with the lowest Y value. For the table, the collision feature would be the uppoer face, the points with the maximum Y value.
You don't need to find the actual closest features of two convex objects colliding, if you already have the collision normal. You merely have to find the points the 'lowest' along the normal on one shape, and the points on the other object the 'highest' along the normal.
If you use the algo for a box, yo uhave to be careful when you extract the vertices of a face. Make sure they are ordered correctly, so they form a convex polygon.
Author
Okie dokie, I think that all makes sense to me now :-) didn't recognise it as vector projection.. will reread my notes on that tonight.
Everything else seems to make sense on that basis, I'll throw together a test this evening - something to show the collision normal and highlight support points maybe - that should help to clarify it.
Thanks again for your help!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
