intersection of convex and non-convex polyhedra 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
 A: 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:

   


   

Image from Discrete and Computational Geometry.


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.
