Jump to content
  • Advertisement
Sign in to follow this  
Kwizatz

finding intersection between a plane and convex polyhedron defined by a plane soup?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

So, how to find out if a plane intersects a convex polyhedron made out of planes (the points in the convex are unknown, so I cant just test that all points are on either side of the intersecting plane without first calculating the points on the hull). Each plane is defined in the standard way by its normal and the distance from the origin, as in Doom 3 Map files. Ideas? Thanks in Advance.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Kwizatz
So, how to find out if a plane intersects a convex polyhedron made out of planes (the points in the convex are unknown, so I cant just test that all points are on either side of the intersecting plane without first calculating the points on the hull).
You should probably be a bit more clear here; in the subject line you ask for finding the intersection, but in the body you imply you want to test for an intersection (i.e. get a yes/no answer).

For testing, what you have is equivalent to a linear programming (LP) problem. Your polyhedron is the intersection volume of a number of halfspaces, as defined by the planes. These planes are your LP constraints. The plane you want to test intersection against is yet another constraint (or two, technically, one less-equal and one greater-equal constraint). If this problem has a solution, the plane intersects the polyhedron. Seidel's algorithm can solve this in O(n) time.

Off the top of my head I'm not sure how you would go about finding the intersection in an efficient way (you can obviously do it in a brute-force manner). You may want to study the double-description method for enumerating vertices of polyhedra given as halfspace intersection volumes and see if there's a neat way to enumerate just the vertices in the plane.

Share this post


Link to post
Share on other sites
Hi Christer,

Thanks for your reply, I think I am gonna have to do some research before I entirely understand the information you provided, right now I understand half of it.

To be more precise, I might just need the test, a yes no check, but then I am going to need a minimal depth penetration length and normal, this is so I can add convex shapes to ODE, the way it works there is that you provide functions that check each shape against all other shapes, and if there is a collision, you fill a structure which contains:

The Contact Position (Contact Point?).
The Contact Normal.
The Contact Depth.

I think I can manage using your book for convex-sphere,convex-box,convex-ray,convex-convex and convex-cappedcylinder, but the plane, which is the most basic one, proved to be a chalenge [smile]

now I'll go look for Seidel's algo.

Thanks!

Share this post


Link to post
Share on other sites
Your planes will circumscribe a convex polytope (assuming the area is closed). You can use various mesh building algorithms to build the actual mesh described by these planes, and then test all the vertices (or all axes of separation -- same thing, really) against the plane.

Actually building the mesh out of the planes is somewhat messy, though.

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
Your planes will circumscribe a convex polytope (assuming the area is closed). You can use various mesh building algorithms to build the actual mesh described by these planes, and then test all the vertices (or all axes of separation -- same thing, really) against the plane.

Actually building the mesh out of the planes is somewhat messy, though.


Yes, thats what I call the bruteforce approach, I already have an algorithm to build the faces (I create a huge square parallel to each plane and then cut out the positive half spaces of the other planes), it works, but like you said is messy, so I run it once and store the points for rendering.

In this case, however, I am trying to avoid both the expensive computation of the points each time, and/or the extra storage space needed for the points.

I read the chapter on Christer's book on Linear Programming, if I am correct, it comes down to:

Maximise x,y or z given a series of ax + by + cz + d <= 0 (one per plane) inequalities.
If there is a solution, the plane intersects, if there isn't, it doesnt (since it produces an empty polyhedron).

Share this post


Link to post
Share on other sites
Quote:
Original post by Kwizatz
I read the chapter on Christer's book on Linear Programming, if I am correct, it comes down to:

Maximise x,y or z given a series of ax + by + cz + d <= 0 (one per plane) inequalities.
If there is a solution, the plane intersects, if there isn't, it doesnt (since it produces an empty polyhedron).
That's correct. In a traditional LP problem you are maximizing a linear function of the form Dot(X, C), where C can be thought of as a direction and X is the solution you're seeking. In other words, you're trying to find the point most extreme in direction C that satisfies the constraints.

For this particular problem we don't care what C is, so we pick C to make the problem "easier" so e.g. C = (1,0,0), meaning you're trying to find a point X=(x,y,z) that satisfies the constraints and that has the largest possible x component.

While e.g. Seidel's algorithm will find a solution for you (when one exists), indicating that there is an intersection, it's hard to say whether this really is the solution you want. It would generally be more efficient to work with the polyhedron given in a vertex-representation, I think. Depends on what's the most important thing for you really (saving memory, computational effort, etc).

Hope this helps.

Share this post


Link to post
Share on other sites
So, in the case of testing convex-vs-plane, complicating things a bit, and setting C to be the negative of the intersecting plane normal, will the solution point be the most extreme point in direction C? thats really all I need.

This really peaked my interest, I am going to try and implement it, see how well it performs against the point collection test.

Share this post


Link to post
Share on other sites
Quote:
Original post by Kwizatz
So, in the case of testing convex-vs-plane, complicating things a bit, and setting C to be the negative of the intersecting plane normal, will the solution point be the most extreme point in direction C? thats really all I need.
Well, yes and no. The solution point is the point most extreme in direction C andthat fulfills all the constraints (i.e. lies in the infinitely thin slice of the polyhedron that the plane carves out).

I should also point out that there's a possibility for robustness problems with treating the plane as two (opposite-facing) halfspaces. A more robust solution would involve solving two LP problems, both involving only the halfspaces of the polyhedron as the constraints (which I think is what you're getting at above). First you set C to be the normal of the plane and find a point (vertex) most extreme in direction C. Then in your second LP problem you find an extreme point in direction -C. Last, evaluate the plane equation for the two resulting points. If you get different signs the points lie on different sides of the plane and the plane must therefore intersect the polyhedron.

Share this post


Link to post
Share on other sites
Quote:
Original post by Christer Ericson
Well, yes and no. The solution point is the point most extreme in direction C andthat fulfills all the constraints (i.e. lies in the infinitely thin slice of the polyhedron that the plane carves out).

I should also point out that there's a possibility for robustness problems with treating the plane as two (opposite-facing) halfspaces. A more robust solution would involve solving two LP problems, both involving only the halfspaces of the polyhedron as the constraints (which I think is what you're getting at above). First you set C to be the normal of the plane and find a point (vertex) most extreme in direction C. Then in your second LP problem you find an extreme point in direction -C. Last, evaluate the plane equation for the two resulting points. If you get different signs the points lie on different sides of the plane and the plane must therefore intersect the polyhedron.


Yes, makes sence, some issue came to my mind after I posted regarding whether the point I am looking for is a maximum or a minumum, but I think thats not really an issue.

Now, how do you go down a dimension in the case that V(i-1) is not contained in the plane?

I am thinking (recursively) solving the plane equation for z when x=v(i-1).x and y=v(i-1).y, am I right?

Edit: I think that would give me the maximization of Z. as X and Y would still be the same.

[Edited by - Kwizatz on September 6, 2005 3:16:42 PM]

Share this post


Link to post
Share on other sites
If adding convex shapes to ODE interests you, you might want to check out my recent work in this area: adding gjk convex collision detection to ODE.

Although very early stages, here is a win32 binary and the modified ODE/Bullet sources:
http://207.234.235.180/ftp/pub/test/index.php?dir=physics/

Indeed, if you dont want to use gjk, you can also perform clipping between convex polyhedra. I'm planning to add this to Bullet collision detection and physics library too.

Also I recommend this posting on the convex contact:
http://groups.google.co.uk/group/comp.graphics.algorithms/browse_thread/thread/b6316c1311b726a0/5430568256475ae5

Erwin Coumans
http://www.continuousphysics.com/Bullet/

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!