4

Suppose I have a 2 Polyhedrons, partially overlapping in space. Each is defined by a list of connected Polygons, which in turn are defined by lists of line segments, (which are defined by 2 points). Is there a simple algorithm for creating the polyhedron which is the union of the boundary of these polyhedrons, but removes all the interior pieces?

Likewise after this, I'll be implementing a subtract, and Intersection Method.

I'm contributing to this Open Source Library. Source Code: https://bitbucket.org/Clearspan/geometry-class-library/src/34a2ab5031879d051abb855a828368e397b4f5b6/GeometryClassLibrary/Solids/Polyhedron.cs?at=master

Charles Taylor
  • 686
  • 6
  • 23
  • Are there any constraints about the nature of the intersecting polyhedra? For instance, are they convex? If one or both are non-convex the intersection may not form a connected set which may make things more difficult. – andand May 18 '15 at 14:24
  • We're allowing for nonconvex polyhedra. Besides, even if you start with convex polyhedra the union is likely not convex. The intent is to be able to build more complicated solids from simpler ones. – Charles Taylor May 18 '15 at 15:26
  • As you will work also in subtract and intersection, start with intersection, then subtract it from one polyhedron, and later join the result to the other polyhedron. To find the intersection, a simple approach would be to check every face from one polyhedron to see if intersects with each face of the other polyhedron. – Blas Soriano May 18 '15 at 16:51

2 Answers2

2

This is a known research problem in Computer Graphics to find the Boolean operations on polygonal meshes. You can take a look at some related papers at:

http://arxiv.org/pdf/1308.4434.pdf

http://www.tandfonline.com/doi/abs/10.3722/cadaps.2010.405-415?journalCode=tcad20.

(You can find older works by taking a look at the cited papers)

In general, polygonal meshes are not very effective at Boolean operations. Boolean operations can be easily addressed in implicit modeling in which an object is represented by a function. Later, the object can be converted to a mesh by marching cubes (for example).

Good Luck
  • 1,104
  • 5
  • 12
2

There is quite an extensive literature on the subject. See for example an optimal algorithm for intersecting three dimensional convex polyhedra.

Allowing for non-convex polyhedra makes things much harder. It might be an idea to split your objects into convex shapes and then try to find the intersection.

Rather than considering the faces as points and lines it will be easier to regard them as planes. You can readily find the intersection of the planes.

You ask if there is a simple algorithm. The answer is probably no. There are algorithms but there are many edge cases to consider: what if the two polyhedra meet at a single point? There are also efficiency concerns. A naive approach would intersect each face with every other face. Making the algorithm O(n^2). This will scale badly if the polyhedra have hundreds or thousands of faces, as is quite common in modelling.

Salix alba
  • 7,536
  • 2
  • 32
  • 38
  • Is there a typo in the sentence "Allowing for convex polyhedra makes things much harder"? I would think permitting convex polyhedral makes finding the intersection easier, not harder... though perhaps you're referring to something other aspect to the problem than identifying the intersection? – andand May 19 '15 at 18:41
  • Well spotted. I ment non-convex. – Salix alba May 19 '15 at 20:58