plane separation for 3d?
Author
Hi,
For the past few days I have been reading up on Plane Separation to detect collision and collision point for a set of 2D polygons. Although I have not implemented it myself, I can see how useful this method is.
My question is, will this Plane Separation method work using 3D objects?
My immediate guess is that its not possible because of the projection of the 3D object on a plane (the result wouldn't be a simple 2D line but in fact a 2D polygon).
So I'm wondering if the Plane Separation method is adaptable for 3D objects?
nope, it still works. The trick is still to use separation plane, and project the 3D objects along the normal of that plane, not the plane itself. So you project the vertices of the objects onto a line, which will give you a 1D overlap test, just like in 2D. Like in 2D, you do NOT project along the direction of the edge, but rather, along the direction prependicular to the edge.
For 2D, it's easier to imagine the 2D polygon as extruding through the screen. Then when you do a separation test in 2D, you are testing the plane going through the edges of the polygon and perpendicular to the screen. So effectively, you are projecting along the normal of that plane, exactly like in 3D.
the added part in 3D is the number of planes to test. The planes you have to test are the faces of the objects, as well as the cross product of every edge of one object against every other edge of the other object.
for two cubes, since many edges are parallel, you end up with 3 edge directions to test against 3 other edge direction, bring the total to 9 edge separation planes. THen you add the 3 face directions for each cube, and you have a grand total of 3 + 3 + (3 x 3) = 15 spearation axes to test.
you can see an example here
2D
3D
these are also testing 'swept' volumes, predicting collisions forward in time, so there is some extra code to deal with that.
For 2D, it's easier to imagine the 2D polygon as extruding through the screen. Then when you do a separation test in 2D, you are testing the plane going through the edges of the polygon and perpendicular to the screen. So effectively, you are projecting along the normal of that plane, exactly like in 3D.
the added part in 3D is the number of planes to test. The planes you have to test are the faces of the objects, as well as the cross product of every edge of one object against every other edge of the other object.
for two cubes, since many edges are parallel, you end up with 3 edge directions to test against 3 other edge direction, bring the total to 9 edge separation planes. THen you add the 3 face directions for each cube, and you have a grand total of 3 + 3 + (3 x 3) = 15 spearation axes to test.
you can see an example here
2D
3D
these are also testing 'swept' volumes, predicting collisions forward in time, so there is some extra code to deal with that.
BTW, for swept tests, I worked out a way to remove the extra required fake 'edges' made of the cross product of the edges of the volumes and the velocity vector (looking like an extrusion of the edges).
Now, I just need to bulletproof the code, and write a doc :)
the idea is based on basic ray-tracing technique (mining and maxing the intersection parameters to the lowest interval). For each speration axis you test, instead of looking at doing one volume against another, you look at a point traced against an enlarged volume, which simplifies the algorithm and the thinking a lot. More on that later.
Now, I just need to bulletproof the code, and write a doc :)
the idea is based on basic ray-tracing technique (mining and maxing the intersection parameters to the lowest interval). For each speration axis you test, instead of looking at doing one volume against another, you look at a point traced against an enlarged volume, which simplifies the algorithm and the thinking a lot. More on that later.
Author
Thanks oliii. It was infact that 2D example that got me interested in plane separation checks for collisions.
I'm still kinda new to collision detection but your docs in PollyColly were fantastic, completely inspired to keep digging at 3D collision.
Looking forward to your swept test docs!
Now time to hack away at your 3D code :)
Thanks
I'm still kinda new to collision detection but your docs in PollyColly were fantastic, completely inspired to keep digging at 3D collision.
Looking forward to your swept test docs!
Now time to hack away at your 3D code :)
Thanks
The min/max technique for eliminating velocity cross products is standard and is documented in Dave Eberly's book 'Game Physics', as well as in his .pdf on the separating axis theorem. Eberly did use the velocity cross technique in '3D Game Engine Design', but has since updated to the min/max technique. I believe the application of the min/max technique to the SAT is generally attributed to Ron Levine, who posted it on comp.graphics.algorithm at some point.
Anyway, if you do SAT swept tests, you'll want to incorporate that at some point. It sounds like oliii intends to add that to his docs, so that will be another good reference on the topic.
Anyway, if you do SAT swept tests, you'll want to incorporate that at some point. It sounds like oliii intends to add that to his docs, so that will be another good reference on the topic.
Hi again,
I have been trying to visualize the process, but I am confused about the actual projection onto a plane. I havn't looked deep into oliii's code yet, I want to understand what is happening first.
If I was to project an irregular shaped 3D object onto the separation plane's normal as oliii suggested, I would have the interval that would be used for the overlap test. But wouldn't this depend on the angle you are 'looking' at on the projection?
This is a small movie ~200k that shows what I mean:
http://www.spot4d.co.uk/0x47/projection.mov
You can see that at the end, the two objects have been projected on the normal of the plane, but there a couple of different sized intervals that I can check, depending on the angle I am looking at.
Will this matter? In this example, the two objects overlap on the 1D overlap check, no matter what angle I check against, so could I just pick one and use that for the rest of the polygons?
Thanks
I have been trying to visualize the process, but I am confused about the actual projection onto a plane. I havn't looked deep into oliii's code yet, I want to understand what is happening first.
If I was to project an irregular shaped 3D object onto the separation plane's normal as oliii suggested, I would have the interval that would be used for the overlap test. But wouldn't this depend on the angle you are 'looking' at on the projection?
This is a small movie ~200k that shows what I mean:
http://www.spot4d.co.uk/0x47/projection.mov
You can see that at the end, the two objects have been projected on the normal of the plane, but there a couple of different sized intervals that I can check, depending on the angle I am looking at.
Will this matter? In this example, the two objects overlap on the 1D overlap check, no matter what angle I check against, so could I just pick one and use that for the rest of the polygons?
Thanks
You actually project the objects onto the plane's NORMAL. not a plane defined by the normal and somthing else. So you're projecting a 3d object onto a 1d vector. Jyk explained it to me quite well once when I was asking the same thing you are:
Quote:
in 3D you still project the objects to 1D, i.e. along a single axis.
The formulation of the projection is the same in 2D and 3D, and in fact any dimension. The dot product of two n-dimensional vectors is always a scalar. Geometrically, it is also the length of the projection of one of the vectors onto the other, scaled by the length of the second vector.
For a shape in any dimension, the maximum of the projected interval on an axis A is max(Dot(v, A)), where v[] are the vertices of the object. Similarly for the minimum.
Author
Thanks minionx, I realized what I was doing wrong.
Oliii infact suggested to project the object onto the normal of the plane, but I just mis-read it and was projecting the objects on the plane itself.
I can see now how the object would be projected onto a 1D line
This is one of those times where I wish I actually paid attention in my math class back in school :)
Thanks for your help
Oliii infact suggested to project the object onto the normal of the plane, but I just mis-read it and was projecting the objects on the plane itself.
I can see now how the object would be projected onto a 1D line
This is one of those times where I wish I actually paid attention in my math class back in school :)
Thanks for your help
I think the exact denomination in algorithmic geometry is more "separating hyperplane theorem". Thus it works in any dimension, and should avoid some confusion.
Since the perp. to an hyperplane is always an axis in any dimension, it's easier to memorize what to do in terms of analysis and coding with the vision Oiii mentioned : project the vertices on one axis, then simply 1D comparisons. But hyperplane also helps to visualize the object that is actually separating the two convex objects. I mean see the issue in terms of geometry.
If you can put a thin sheet of paper in between THEN they are separated, and the reverse is also true. Kind of trivial intuitively. Seing it like this later helps to see that (hyper)planes in fact appear everywhere as soon as optimizations come into play in geometric computations.
So this obviously works perfectly and efficiently in 3D. I hope you see why now.
Since the perp. to an hyperplane is always an axis in any dimension, it's easier to memorize what to do in terms of analysis and coding with the vision Oiii mentioned : project the vertices on one axis, then simply 1D comparisons. But hyperplane also helps to visualize the object that is actually separating the two convex objects. I mean see the issue in terms of geometry.
If you can put a thin sheet of paper in between THEN they are separated, and the reverse is also true. Kind of trivial intuitively. Seing it like this later helps to see that (hyper)planes in fact appear everywhere as soon as optimizations come into play in geometric computations.
So this obviously works perfectly and efficiently in 3D. I hope you see why now.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
