Jump to content
  • Advertisement
Sign in to follow this  
sgdimitris

Intersection of two CONVEX polyhedrons

This topic is 2278 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

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

Share this post


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

Share this post


Link to post
Share on other sites
Thanks for cross posting and reposting.

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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!