Hello, my first time on these forums though I've been making 3D engines for 10 years now! I need to find a polyhedron that is the intersection of two convex polyhedra. I've been looking around for three days now but all I've found is tests that return a penetration depth at most, of which Voronoi-Clip seemed like the most promising. On a side note, I found an article on Gamasutra (when two hearts collide) that proposes to find a separating plane in either a face of the polyhedra or a plane made from an edge of one polyhedron and a vertex of the other. Does this work? Because it seems to me that this should be faster than SAT and just as simple. Anyway, I have kind of approached this problem previously, though messily and not really with the same goal in mind (just a debugging tool). Basically, what I did is look for features (vertices and edges) by intersection of the planes of both volumes, discarding those planes that returned no features (just vertices? Can't remember) that weren't discarded by other planes. This seemed to work but I did have precision issues in cases where some planes had similar normals, I'm thinking these could be solved though. I'm wondering if I could not improve on something like this to get what I need. I thought I might approach the problem by first discarding all polygons from either polyhedron that do not intersect the other polyhedron and then derive vertex and edge features from intersection of the remaining face planes. Does this sound valid? Performance is not a big concern, I would choose simplicity and robustness over performance. [Edited by - Madoc on September 25, 2007 8:11:34 AM]

Hmm... Believe it or not, I've always completely ignored BSP, I use portals, octrees and BV hierarchies and have never even read up on BSP (maybe it's time I did). I can't imagine how it might help me.

I suppose the reason why I proposed the above method is because I've found it useful in a number of circumstances. Most of the volumes I work with in this context do not have any explicit features beyond plane equations (though they could be defined) and being able to derive additional features when necessary is quite attractive. I am basically assessing the feasability of a revised implementation of this and I am still not certain what all the requirements are, at this point I am mostly trying to determine what is available to me.

So, excluding the existence of well known solutions, if I were to take the approach I suggest, can you confirm that it is theoretically correct and speculate as to whether the precision issues are surmountable? I am afraid to make mistakes in this planning stage as I can't do any actual testing for quite some time yet.

What are you proposing by "testing every edge vs face"?

Thanks

If you describe each convex polygon as the intersection of a finite family of half-spaces, the union of the two families corresponds to the intersection. Some of these half-spaces will now be redundant (the intersection of all other half-spaces is completely contained in this half-space). I have no idea if this helps you in any way.

Yeah, that much I understand. Problem is, at this point it becomes important that all redundant planes are eliminated (for performance reasons) and also I will require the additional features (vertices and edges). Until this point (component polyhedra), the other features are not important but can be provided at minimal cost.

I considered that it may be most efficient to eliminate the redundant planes in a first step by determining whether they intersect the other polyhedron, then I would perform the union and finally I would derive the missing features.

The first step becomes a matter of performing a number of polygon-polyhedron tests. The polyhedra are simple, averaging 6 to 10 faces. I would appreaciate any reccomendation as to what method may prove most efficient here. I have considered V-Clip but something more brute force may suffice. If the method from the gamasutra article is valid, I may consider using a form of that.

The second step of deriving edge and vertex features from the planes is where I've encountered precision issues in the past. Hopefully I can overcome these probelms, otherwise I may have to look at a method that preserves existing features. I don't like the sound of that.

Dave Eberly's Geometric Tools site has some info here - there's two 2D implementations, and a pdf document (and more info in his books I guess). Ummm.... good luck :)

This falls into the field of constructive solid geometry. That link is to the wikipedia article, and it has links to a few LGPL'd libraries that can do what you want.

Quote:Original post by MrRowl
Dave Eberly's Geometric Tools site has some info here - there's two 2D implementations, and a pdf document (and more info in his books I guess). Ummm.... good luck :)

I do not know what SampleFoundation applications you are referring to. I do not have code for this in Wild Magic 4. I have an implementation for computing the intersection of convex polyhedra in Wild Magic 2 (still downloadable from my website). In the WildMagic2p5.zip file, look at the files in the MagicSoftware/WildMagic2/Source/Geometry folder, specifically WmlConvexPolyhedron3.{h,cpp} and WmlConvexClipper.{h,cpp}. I used this code for some contract work, so it has been pounded on a bit. The relevant supporting documentation is Clipping a Mesh Against a Plane.

I still have not gotten around to porting a lot of the intersection code in WM2 to WM4. Just never enough spare time in a day...

Oooh, Dave Eberly himself! Didn't know where to find your great resources since magic software dissapeared. I see you've basically just changed the name.

Right, clipping a polyhedron against every (negated) face plane of another in turn (given that the latter is convex) would indeed give me the intersection I require. I at least have an alternative solution if the method I suggested doesn't prove worthwhile.

Any idea if that separating plane intersection test from the gamasutra article is valid?

Thanks

Quote:Original post by Madoc
Didn't know where to find your great resources since magic software dissapeared. I see you've basically just changed the name.

The site changed some time ago. Magic Software Enterprises owns the U.S. Registered Trademark for the use of "Magic" regarding computer software, and threatened legal action if I continued to use my domain. As vague a trademark as that is, you would think it would have been rejected. Surprisingly, my application for the registered trademark for "Geometric Tools" was rejected. The USPTO does not have a clue...

Quote:
Any idea if that separating plane intersection test from the
gamasutra article is valid?

You can use the SAT for determining whether two polyhedra intersect, and then go into the finer details of computing the intersection when it exists, but it is not clear this saves you time. The basic operation is testing whether the plane of a face of the first polyhedron intersects the second polyhedron. You can implement this by computing the extreme vertices of the second polyhedron in the plane's normal direction. Extremal Queries Using BSP Trees describes this process. The conclusion is that the simple approach of projecting all the vertices onto the normal lines is fast for small N, but for large N, a BSP tree approach is asymptotically faster.