I am trying to find the best appropriate way to intersect polyhedra which may be non-convex.
The number of vertices that build the polyhedron is hence always small (up to 20 or so).
The polyhedron is generated by taking a convex polygon and creating copies of its vertices using a prescribed vector field mapped onto these vertices. When the new polygon is created, it is to be used to create the final polyhedron. The mapping is enforced so that every new "swept" vertex is mapped to its origin. From this mapping, the faces of the polyhedron are defined.
Because the prescribed vector field is complex, there may be such situations when the faces of the so created polyhedron are non-planar. For the same reason, the convexity of the polyhedron is not ensured.
The goal is to intersect the resulting polyhedron with a convex polyhedron. This means that I would either need to invent a general algorithm for logical-non-convex polyhedron intersecting another, convex one, or:
- triangulate the faces and use flood and retract algorithm to separate convex patches, for every convex patch, create a set of tetrahedrons (thus separating the non-convex polyhedron into convex polyhedrons)
- intersect the union of tetrahedron with the convex polyhedron (simple, convex-convex algorithms like the one from Muller and Preparata, using BSP trees, separation of axes algorithm in 3D, ... etc)
On this site, I have found a note from professor O'Rourke regarding the splitting of non-convex polyhedra into convex sub-polyhedra (namely, "Strategies for Polyhedral Surface Decomposition: An experimental study", by Chazelle, Dobkin and Shouraboura), but they deal with large polyhedral surface meshes (flood-and-retract algorithm for dividing the surface mesh into convex patches is found to give best results, if I remember).
Now, my question is: which way to choose? How best to do this? This is only a fraction of my work, and the should operate iteratively over up to millions of times for every outer iteration of the code, which is also determined by other factors.... this is why I would like to receive some input on the matter from people with experience in computational geometry, because the other option for me is to implement a lot of different algorithms, optimize them, and choose the best one... which is, well: O_o
How to take a single general (possible non-planar faces) with low number of points (order of 10), convex or non-convex polyhedron, and split it safely and securely into tetrahedrons?
Thanks and best regards, Tomislav
The image shows a polyhedron and a creation of the new polyhedron from one of its faces. The vectors are used at each of the vertices to create their copies by displacement. A blue plane cuts the polyhedron in two parts (clipping and capping algorithm, I'm almost done, and I dare to say that I may have made some improvements... :) ), and the resulting polyhedron created from the face, is to be intersected with one of the parts.
The red face is an example of an invalid polygon, where the vectors that are used to displace the edge vertices of the original polygon, result with a non-planar face. It may be badly drawn...
Links to the images: