# Intersection of 3D objects

Martin Erwig Martin.Erwig at FernUni-Hagen.de
Mon Feb 15 10:56:05 PST 1999

```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