[vtkusers] Intersection of Two PolyData Surfaces

[Steve M. Robbins]

On Fri, Jan 27, 2006 at 06:57:08AM -0800, Cooper, Carlo wrote:
> I'm sure this question is familiar to long time users - when searching the
> archives, I found numerous references to people asking how to intersect two
> polydata surfaces (made up exclusively of triangles).  I want to find the
> line of intersection - as per vtkCutter , or trim one surface with another
> as in  vtkClipPolyData, or create a closed solid based on the intersection
> of two triangulated meshes.

[...]
 
> Before I go and start writing my own intersection code based in intersecting
> triangles (I guess), has anyone else had any success with this type of
> problem using the standard VTK libraries? 

I haven't done this with VTK.  However, I have written intersection
code using the CGAL library (http://cgm.cs.mcgill.ca/~stever/CGAL/).
Later versions of CGAL (www.cgal.org) include this functionality
(though not my code).

To intersect two triangulated surfaces, you'll generally need to do
some sort of fast rejection test; e.g. quickly discard triangle pairs
whose bounding boxes do not intersect.  Then you need a robust
triangle/triangle intersection computation.

One strategy for the rejection testing is to create a hierarchy of
bounding shapes.  The OBB tree [vtkOBBTree] is one well-known example.
This strategy works well if you can reject the intersection at a high
level (larger bounding boxes) in the tree.  For example, if the two
surfaces bound small volumes that are well separated.

If this does not hold (think of the surface bounding a steering wheel
and the surface bounding a hand clutching the wheel), bounding
hierarchies are not as useful.  In this case, the streaming approach
of Edelsbrunner and Overmars is quite useful.  An implementation of
this was written up by Zomorodian and Edelsbrunner [Fast Software for
Box Intersections, Symp. on Comp. Geometry, 2000] and is now included
in CGAL.

Finally, I'll just mention that the triangle/triangle intersection
test is easy to get wrong due to floating point roundoff
[http://www.sumost.ca/steve/publications/triangle-intersection.ps]
though this may be mitigated by using a bounding box rejection
test.

-Steve