Hello to all users,
I need to calculate the intersection of two given CONVEX 3D polyhedrons. How can I do that?
I know the x,y,z, coordinates of each vertex and also the triangles list that I use to draw each polyhedron.
Any help would be very very appreciated.
With regards,
Dimitris

What you're talking about here is called CSG or Constructive Solid Geometry. The standard solution (and as best I can tell after a fair amount of research also simplest and generally fastest) to this is David Laidlaw's paper. Note, however, that this is a seemingly simple algorithm that is very tough to debug and will likely take you weeks if not months to implement properly and efficiently (I spent weeks on polygon merging and postprocessing to minimized geometric clutter alone). There is no specialized approach for convex polyhedra that I know of - CSG handles all closed convex and concave polyhedra of any complexity and gives you same-cost access to all intersection modes: intersection (common volume), union (joint volume) and subtraction (A - B or B - A). Note, though, that one thing you can probably optimize a fair bit is your poly intersection code, which can be generalized if you know your meshes are convex. At the end of the day it's probably easiest to pick up a CSG library, but sadly I can't suggest any to you as I didn't end up trying out any.

Note that if you can get away with an estimate (eg for collision), then I suggest calculating the AABB/sphere of the common volume: raycast all points of A through B and all points of B through A. All points of either object that fall inside the other object form the bounding box of the shared volume (just calculate the extents). You can use your favourite convex hull method to extend this to a shape of any complexity.

Hope this helps.

Thanks for cross posting and reposting.

http://www.gamedev.net/topic/621717-intersection-of-two-3d-polyhedrons/page__pid__4930308#entry4930308

your post was helpful, that's why I gave you points in reputation.
I just wanted to have a second advice, and because the previous topic was in general polyhedron, that's why I posted again.
Cause in the previous post I mentioned that they are convex only in an inside message

That's not what concerns me. You should always give a link to what you have so far to prevent someone else wasting their time, giving the same, similar or less complete answers.

Hello Crowley99,
do you have some links that can help us implement one of the two given algorithms?
Regards,
Dimitris

All I can say is that if you're going to be dealing with any sort of real complexity in your models, do not go with the BSP approach.

PS: click me.

Yeah, fortunately the BSP approach isn't necessary here. The thing that makes convex polyhedra unique is that they can be represented entirely as the intersection of a set of half spaces (constraints), and so can the intersection of an arbitrary set of convex polyhedron. To compute the intersection of two polyhedra, you just need to generate intersection of the union of the set of half-spaces.

The library approach would be to do the following: You start with the convex polyhedrons A and B, convert them to h-reps (set of half-spaces - in 3D, these will just be (oriented) plane equations), hrep(A) and hrep(B), then computer their union and convert back to the v-rep (set of vertices). So intersection(A,B) = vrep( union( hrep(A), hrep(B) ) ). Depending on what the library does, you may need to convert the resulting vertices into a trianguled hull (any convex hull implementation should do this for you).

cdd converts between hreps and vreps ( http://www.ifor.math...home/index.html ). Maybe the newer version also tesselates (I don't know - I used it last 11 years ago). Something like QHull will generate the hull mesh http://www.qhull.org/.

The non-library/direct approach would be to just take polyhedron A, and iteratively refine it, by intersecting it with the half-spaces that make up polyhedron B. So, start with A, then for each triangle of B, compute the correctly oriented plane equation, and intersect A with the half space. The fundamental algorithmic primitive here is "polyhedron-halfspace intersection". This is actually, really easy to do - triangles of A completely on the outside of the half-space, are trivially discarded, triangles of A completely on the inside of the half-space are trivially kept. Triangles that cross the plane need to be clipped.

Triangle-plane clipping is easy, and implementations are widely available. The last piece of the puzzle is to take the new vertices, resulting from the clipping, and generate a "cap" polyhedron out of them. This is also easy, just project a copy of them onto a primary plane (use the largest component of the plane normal to decide which plane to prevent degenerate projections - i..e, if |x| is the largest, then project to the YZ plane), and sort them around their centroid by angle (use atan2).

Once you have the order of vertices, you can generate triangles from one vertex to all the others, and you're done.

Once you have gone through all triangles of B, you will be left with the intersection of A and B.

Thanks Crowley for the advices in general!
I already implement your non-library/direct algorithm and works fine and it is fast!!!
Thanks
All the best

Good to hear it :-)