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

_______________________________________________

This is the private VTK discussion list.

Please keep messages on-topic. Check the FAQ at:

http://www.vtk.org/Wiki/VTK_FAQFollow this link to subscribe/unsubscribe:

http://www.vtk.org/mailman/listinfo/vtkusers