How to Combine Polyhedra?

Question

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

Answer 1

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).

Answer 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.