Intersection of 3D objects

[Martin Erwig]

Hi,

I hope the following is not out of the scope of this mailing list.  I 
am looking for algorithms and their complexities for the following two 
problems:

 (1) Intersection of two 3D volumes
 (2) Intersection of a 3D volume and a 3D line

I have already looked into geombib (a VERY GOOD enterprise!), and some 
papers seem to be relevant, but before getting copies (some are quite
difficult to obtain), I would like to know more precisely where I 
should look at.

Some more details on the above two problems:

 (A) 3D volumes should be sets of (generally non-convex) polyhedra.  
 (ie, volumes need not be connected).  Volumes should be allowed to 
 have holes.  (If there are simpler algorithms for polyhedra without 
 holes, this would also be interesting to know).

 (B) 3D lines are monotonic wrt the z-axis (ie, they can be viewed as 
 functions the z-axis to the x-y-plane).  Lines can be thought of as 
 being given by a collection of straight line segments.  Lines might 
 consists of more than one component.

 (C) We can distinguish different topological relationships between 
 two 3D objects: for volume/line it is possible that they are 
 disjoint, that the line is inside the volume, or that the line runs 
 along the border of the volume.  The algorithm should ideally return 
 an ordered sequence of z-intervals together with the information 
 about the corresponding parts of the volume/of the region (each of 
 which might be undefined), and of their topological relationship.  
 (For each change in the topological relationship, a new interval 
 should be reported.  For topological relationships that hold only for 
 one z-coordinate (here, intersection points) no (degenerated) 
 interval has to be reported, since it can be derived from the 
 other intervals.)
 For two volumes, we have five topological relationships: disjoint, 
 externally tangent, overlap, internally tangent, and inside.

I would appreciate any comments on this problem and, in particular,
pointers to relevant papers.

Thanks a lot,
Martin

-----------------------------------------------------------------------------
Dr. Martin Erwig            Phone: +49 2331 987-4286
FernUniversitaet Hagen      Fax:   +49 2331 987-4278
Praktische Informatik IV    Email: erwig at fernuni-hagen.de
58084 Hagen                        erwig at acm.org
Germany                     URL:   http://www.fernuni-hagen.de/inf/pi4/erwig/
-----------------------------------------------------------------------------

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme