How to combine polyhedra?
Suppose I have 2 polyhedra, partially overlapping in space. Each is defined by a list of related polygons, which in turn are defined by lists of line segments (defined by two points). Is there a simple algorithm for creating a polyhedron that is the union of the boundary of these polyhedra, but removes all the interiors?
After that, I will perform the subtraction and intersection method.
I am a contributor to this open source library. Source code: https://bitbucket.org/Clearspan/geometry-class-library/src/34a2ab5031879d051abb855a828368e397b4f5b6/GeometryClassLibrary/Solids/Polyhedron.cs?at=master
source to share
There is a fairly extensive literature on this subject. See, for example, the optimal algorithm for intersecting 3D convex polyhedra .
Allowing non-convex polyhedra makes things that much more difficult. It might be an idea to divide your objects into convex shapes and then try to find the intersection.
Instead of treating faces as points and lines, it’s easier to treat them as planes. You can easily find the intersection of the planes.
Are you asking if there is a simple algorithm. The answer is probably no. Algorithms exist, but there are many edge cases: what if two polyhedra meet at the same point? There are also efficiency issues. A naive approach would cross every face with every other face. Create an O (n ^ 2) algorithm. It will get worse if polyhedrons have hundreds or thousands of faces, which is quite common in simulations.
source to share
This is a known research problem in computer graphics for finding Boolean operations on polygonal meshes. You can take a look at some related docs:
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 looking at the cited articles)
In general, polygonal meshes are not very efficient for boolean operations. Logical operations can be easily eliminated in implicit modeling in which the object is represented by a function. The object can later be transformed into a mesh by marching cubes (for example).
source to share