Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi everyone,

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:

polyhedron created from a face of another polyhedron

bow tie polyhedron

convex hull of a bow tie polyhedron

share|improve this question
2  
Five comments/questions: (1) No need for "professor"---MO is egalitarian! (2) Your case is quite special, suggesting you avoid general algorithms and exploit the specialness. (3) Are the top & bottom convex polygons congruent? (4) Is each nonplanar face the continuous sweep of an edge between two vertices? (5) An image would help. –  Joseph O'Rourke Jun 16 '11 at 16:58
    
Thank you very much for the advice! My responses: (1) Cool! :) (2) Excellent, I was not sure how to approach this problem, my background is mechanical engineering and I am entering the comp. geometry through fluid mechanics, so I don't have much experience in these things (the usual approach is to do a literature survey, examine the best algorithms, implement some, test, and choose the best one...). (3) They are corresponding only in the mapping (vertex i becomes i'), but the vector field will distort the angles and the lengths of the two polygons (I hope the image helps). –  Tomislav Maric Jun 17 '11 at 12:43
    
(4) The faces are created by creating copies of the edge vertices, by displacing them, so I am not sure if I would call it a continuous sweep... I don't know. (5) The link to the image is above, I have edited the question. Thank you! :) –  Tomislav Maric Jun 17 '11 at 12:45
add comment

1 Answer 1

up vote 5 down vote accepted

This is not a definitive answer, just some thoughts. You start with a convex polygon $A$, and displace its vertices by a vector field to produce $B$, connecting corresponding vertices. First, it is not clear that $B$ is necessarily a planar convex polygon, unless you have special conditions on the vector field. $B$ could be nonplanar; $B$ could be nonconvex. So the resulting polyhedron $P$ seems not well defined. You could define $P$ to be the convex hull of $A$ and the vertices of $B$, but then you lose the property that each vertex of $A$ is connected to its corresponding vertex in $B$.

Let me ignore this, and assume that $B$ is a planar convex polygon. Even for $A$ and $B$ triangles, it may be that under one definition of what constitutes $P$, it is not tetrahedralizable. The famous Schönhardt polyhedron is the simplest example:
   Schoenhardt
Setting aside both of these issues, which may not occur in your data, there are specialized tetrahedralization algorithms. In fact, you might adapt the definition of $P$ so that these algorithms apply. Here is an incomplete tour through some literature.

Goodman and Pollack showed that the region between two convex polyhedra can be tetrahedralized without "Steiner points," unlike the Schönhardt polyhedron. Marshall Bern then showed that sometimes $\Omega(n^2)$ tetrahedra are needed:

(1) "Compatible tetrahedralizations," Marshall Bern, Proceedings of the 9th Annual Symposium on Computational Geometry, 1993, pp.281-7. Fundam. Inform., 1995: 371-384.

Two subsequent papers studied special cases that are easier: e.g., "slabs" in (2):

(2) "Tetrahedralization of Simple and Non-Simple Polyhedra," Godfried T. Toussaint, Clark Verbrugge, Cao An Wang, Binhai Zhu, Canadian Conference on Computational Geometry, pp. 24-29, 1993.

and a slightly more general case in (3) below. I think this work by Palios may be the most relevant for your purposes, because the case he considers can cover a version of your polyhedra $P$, and because he proves that only $O(n)$ tetrahedra are needed in this case:

(3) Leonidas Palios, "Optimal tetrahedralization of the 3D-region “between” a convex polyhedron and a convex polygon," Computational Geometry, Volume 6, Issue 5, September 1996, Pages 263-276.

Once you have $P$ tetrahedralized, then you can focus on intersecting the tetrahedra with the convex polyhedron.

share|improve this answer
    
Thank you very much for the advice, I really appreciate it. The vector field is defined as the velocity field of the flow of a fluid, so I cannot restrict it in any way. It may happen (because of a small vortex in the flow) that a bow-tie polyhedron is created (I added links to new images in the question). In this case, a convex hull of a resulting polyhedron will introduce new volume, which would be non-physical. Otherwise, if the faces are just non planar, but the polyhedron is convex, a convex hull would basically just triangulate the faces, if I got it right... –  Tomislav Maric Jun 18 '11 at 9:10
    
Thank you very much for the links to the literature as well, the field is rather large, and it's easy to go in the wrong direction. I cannot download them from home, but will do so on Monday at the institute. :) I would click "the answer was helpful" arrow above, but I don't have enough experience... Thanks again! –  Tomislav Maric Jun 18 '11 at 9:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.