Intersection of Two PolyData Surfaces

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Intersection of Two PolyData Surfaces

Cooper, Carlo
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.

I didn't really find many satisfactory answers on the mailing list, or at
least, any good strategies I could go with.  Dave Pont has sent a few people
his vtkImplicitPolyData class (I think that's the one), and am wondering if
that is a robust solution?  

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've tried vtkImplicitDataSet, but don't see how that can work given that if
a point on the data being clipped doesn't lay exactly on the ImplicitDataSet
surface, then the 'outside/off surface' default value is used..

Any assistance would be greatly appreciated.

Regards


Carlo Cooper
_______________________________________________
This is the private VTK discussion list.
Please keep messages on-topic. Check the FAQ at: http://www.vtk.org/Wiki/VTK_FAQ
Follow this link to subscribe/unsubscribe:
http://www.vtk.org/mailman/listinfo/vtkusers
Reply | Threaded
Open this post in threaded view
|

Re: 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
_______________________________________________
This is the private VTK discussion list.
Please keep messages on-topic. Check the FAQ at: http://www.vtk.org/Wiki/VTK_FAQ
Follow this link to subscribe/unsubscribe:
http://www.vtk.org/mailman/listinfo/vtkusers