Sign in to follow this  
Geeman

plane separation for 3d?

Recommended Posts

Geeman    122
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?

Share this post


Link to post
Share on other sites
oliii    2196
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.

Share this post


Link to post
Share on other sites
oliii    2196
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.

Share this post


Link to post
Share on other sites
Geeman    122
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

Share this post


Link to post
Share on other sites
jyk    2094
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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

Share this post


Link to post
Share on other sites
minionx    133
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[i], A)), where v[] are the vertices of the object. Similarly for the minimum.

Share this post


Link to post
Share on other sites
Geeman    122
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

Share this post


Link to post
Share on other sites
Charles B    863
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this