Newsgroups: comp.graphics
From: katkere@eecs.umich.edu (Arun L. Katkere)
Subject: polyhedron/polyhedron intersection
Reply-To: katkere@engin.umich.edu
Organization: University of Michigan EECS Dept., Ann Arbor, MI
Date: Tue, 10 Nov 1992 19:28:04 GMT
I am looking for code/ideas for finding if two polyhedrons intersect.
I think that polygon/polygon intersection will be used as a building
block for this. Is there a better way to do this? Can the sgi
rendering engine be used in any way to do this? Where can I find
code for polygon/polygon intersection?
I am not a c.g subscriber. But I searched thro' the FAQ, about 1300
subject lines, some ftp sites and couldn't find any info on this. Any
help will be appreciated.
Send replies to katkere@eecs.umich.edu.
Thanks,
-arun
--
+-----------------------------------------------------------------------------+
| Arun Katkere | The University of Michigan AI Lab |
| katkere@engin.umich.edu | 147 ATL, 1101 Beal Avenue |
| O:(313)763-1563 | R:(313)761-9462 | Ann Arbor, MI 48109-2110 |
+-----------------------------------------------------------------------------+
Newsgroups: comp.graphics
From: orourke@sophia.smith.edu (Joseph O'Rourke)
Subject: Re: polyhedron/polyhedron intersection
Organization: Smith College, Northampton, MA, US
Date: Tue, 10 Nov 1992 22:19:43 GMT
katkere@engin.umich.edu writes:
>I am looking for code/ideas for finding if two polyhedrons intersect.
@article{CD
, author = "B. Chazelle and D. P. Dobkin"
, title = "Intersection of convex objects in two and three dimensions"
, journal = "J. ACM"
, volume = 34
, year = 1987
, pages = "1--27"
}
Newsgroups: comp.graphics
From: hollasch@kpc.com (Steve Hollasch)
Subject: Re: polyhedron/polyhedron intersection
Summary: How I'd approach the problem...
Organization: Kubota Pacific Computer, Inc.
Date: Wed, 11 Nov 1992 00:21:23 GMT
katkere@engin.umich.edu writes:
| I am looking for code/ideas for finding if two polyhedrons intersect.
| I think that polygon/polygon intersection will be used as a building
| block for this. Is there a better way to do this? Can the sgi
| rendering engine be used in any way to do this? Where can I find
| code for polygon/polygon intersection?
Polyhedron intersection has both trivial accept and trivial reject
conditions. Let P and Q be two polyhedra, and let Pc and Qc be some
arbitrary "center" of the polyhedron. Then let Prmin & Qrmin be the
minimum distance from the center to any of the vertices of the polyhedra,
and Prmax & Qrmax be the maximum distances from the polyhedra centers to any
vertex on the corresponding polyhedra.
Trivial Reject: |Pc - Qc| > (Prmax + Qrmax)
Trivial Accept: |Pc - Qc| < (Prmin + Qrmin)
If neither of these tests succeed, then you must test each vertex of P
to see if it lies within Q, and then you have to test each vertex of Q to
determine if it lies within P.
This is not all that simple for non-simple polyhedra (e.g. a torus), but
you may just be dealing with simple polyhedra anyway.
______________________________________________________________________________
Steve Hollasch Kubota Pacific Computer, Inc.
hollasch@kpc.com Santa Clara, California
Newsgroups: comp.graphics
From: sloan@cis.uab.edu (Kenneth Sloan)
Subject: Re: polyhedron/polyhedron intersection
Organization: CIS, University of Alabama at Birmingham
Date: Wed, 11 Nov 1992 04:01:42 GMT
orourke@sophia.smith.edu (Joseph O'Rourke) writes:
>katkere@engin.umich.edu writes:
>>I am looking for code/ideas for finding if two polyhedrons intersect.
>
>@article{CD
>, author = "B. Chazelle and D. P. Dobkin"
>, title = "Intersection of convex objects in two and three dimensions"
>, journal = "J. ACM"
>, volume = 34
>, year = 1987
>, pages = "1--27"
>}
But Joe...what if the polyhedra aren't convex?
--
Kenneth Sloan Computer and Information Sciences
sloan@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Newsgroups: comp.graphics
From: sloan@cis.uab.edu (Kenneth Sloan)
Subject: Re: polyhedron/polyhedron intersection
Organization: CIS, University of Alabama at Birmingham
Date: Wed, 11 Nov 1992 04:12:37 GMT
In article <1992Nov11.002123.27579@kpc.com> hollasch@kpc.com (Steve Hollasch) writes:
>katkere@engin.umich.edu writes:
>| I am looking for code/ideas for finding if two polyhedrons intersect.
>| I think that polygon/polygon intersection will be used as a building
>| block for this. Is there a better way to do this? Can the sgi
>| rendering engine be used in any way to do this? Where can I find
>| code for polygon/polygon intersection?
>
> Polyhedron intersection has both trivial accept and trivial reject
>conditions. Let P and Q be two polyhedra, and let Pc and Qc be some
>arbitrary "center" of the polyhedron. Then let Prmin & Qrmin be the
>minimum distance from the center to any of the vertices of the polyhedra,
>and Prmax & Qrmax be the maximum distances from the polyhedra centers to any
>vertex on the corresponding polyhedra.
>
> Trivial Reject: |Pc - Qc| > (Prmax + Qrmax)
>
> Trivial Accept: |Pc - Qc| < (Prmin + Qrmin)
>
> If neither of these tests succeed, then you must test each vertex of P
>to see if it lies within Q, and then you have to test each vertex of Q to
>determine if it lies within P.
>
> This is not all that simple for non-simple polyhedra (e.g. a torus), but
>you may just be dealing with simple polyhedra anyway.
Even for simple polyhedra, is it not possible for two polyhedra to
intersect even though your Trivial Reject fails, your Trivial Accept
fails, and no vertex lies INSIDE the other polyhedron? I believe that
you must also test all edges for intersection with all faces of the
other polyhedron or triangulate (tetrahedralize) and test all tetrahedra
in one polyhedron against all tetrahedra in the other.. Testing
vertices works for polygons - but polyhedra are tougher.
--
Kenneth Sloan Computer and Information Sciences
sloan@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Newsgroups: comp.graphics
From: chuckb@stein.u.washington.edu (Charles Bass)
Subject: Re: polyhedron/polyhedron intersection
Organization: University of Washington
Date: Wed, 11 Nov 1992 07:10:10 GMT
I am using an algorithm developed at the University of
Washington. It has been accepted for publication but as of
today it is not known when it will be published.
I use the routines to detect collisions between solid modeled
objects in a real time simulation program. In general the
routine has proven an improvement over our previous (n^2)
routine. Some details:
1) It requires triangulated polygons.
2) It is well suited for checking collisions between moving
objects (ones that don't overlap very much)
3) In practice the algorithm is very fast although the worst
case looks to run in O((n^2)/2) time
4) Several "speed hacks" have been incorporated. These mostly
are marginal but in the name of efficiency... (and less
readable code ;-))
5) Convex hull information can marginally speed the test.
6) I did *not* implement an engulfment test. I don't have
details on this process but could possibly provide a ref.
For details email me.
Chuck Bass |
College of Forest-Systems Engineering |
University of Washington | FAX (206)-685-3091
Mailstop AR-10 | voice (206)-685-2198
Seattle, WA 98195 | email chuckb@u.washington.edu
Newsgroups: comp.graphics
From: orourke@sophia.smith.edu (Joseph O'Rourke)
Subject: Re: polyhedron/polyhedron intersection
Organization: Smith College, Northampton, MA, US
Date: Wed, 11 Nov 1992 13:51:07 GMT
hollasch@kpc.com (Steve Hollasch) writes:
> ... Trivial Reject ... Trivial Accept ...
> If neither of these tests succeed, then you must test each vertex of P
>to see if it lies within Q, and then you have to test each vertex of Q to
>determine if it lies within P.
These tests are not sufficient to detect intersection, as two
polyhedra may intersect without any vertex of one being inside the other.
Newsgroups: comp.graphics
From: orourke@sophia.smith.edu (Joseph O'Rourke)
Subject: Re: polyhedron/polyhedron intersection
Organization: Smith College, Northampton, MA, US
Date: Wed, 11 Nov 1992 13:57:12 GMT
sloan@cis.uab.edu (Kenneth Sloan) writes:
>I believe that
>you must also test all edges for intersection with all faces of the
>other polyhedron ...
Exactly.
>Testing vertices works for polygons - ...
Nope:
+--+
| |
| |
+------------------+
| | | |
+------------------+
| |
| |
+--+
Newsgroups: comp.graphics
From: hollasch@kpc.com (Steve Hollasch)
Subject: Re: polyhedron/polyhedron intersection
Summary: Trivial accept and reject tests; a defense
Organization: Kubota Pacific Computer, Inc.
Date: Wed, 11 Nov 1992 19:34:39 GMT
katkere@engin.umich.edu writes:
| I am looking for code/ideas for finding if two polyhedrons intersect.
hollasch@kpc.com (Steve Hollasch) writes:
> Polyhedron intersection has both trivial accept and trivial reject
> conditions. Let P and Q be two polyhedra, and let Pc and Qc be some
> arbitrary "center" of the polyhedron. Then let Prmin & Qrmin be the
> minimum distance from the center to any of the vertices of the polyhedra,
> and Prmax & Qrmax be the maximum distances from the polyhedra centers to any
> vertex on the corresponding polyhedra.
>
> Trivial Reject: |Pc - Qc| > (Prmax + Qrmax)
>
> Trivial Accept: |Pc - Qc| < (Prmin + Qrmin)
>
> If neither of these tests succeed, then you must test each vertex of P
> to see if it lies within Q, and then you have to test each vertex of Q to
> determine if it lies within P.
sloan@cis.uab.edu (Kenneth Sloan) writes:
| Even for simple polyhedra, is it not possible for two polyhedra to
| intersect even though your Trivial Reject fails, your Trivial Accept
| fails, and no vertex lies INSIDE the other polyhedron? I believe that
| you must also test all edges for intersection with all faces of the
| other polyhedron or triangulate (tetrahedralize) and test all tetrahedra
| in one polyhedron against all tetrahedra in the other.. Testing
| vertices works for polygons - but polyhedra are tougher.
No, the trivial reject is sufficient. It's basically a test to see if
the bounding spheres can intersect. If the bounding spheres cannot
intersect, then the objects themselves cannot.
The trivial accept doesn't work though. Not for the reason you mention,
but because it doesn't properly handle concave polyhedra (e.g. a cylinder
passing through the hole of a torus). If it's easy to break the polyhedron
into convex components, then this test should work, provided that you are
testing for volume (not just surface) intersection. This is because an
object wholly enclosed in another object is an intersection of volumes but
not of surfaces.
With respect to rigorous (as opposed to trivial) intersection, I really
just sort of kind of tossed out the vertex containment test without giving
it a great deal of thought. I now agree that edge-face intersection must
also be considered. In order to test this, I propose we hold a contest ...
B^)
______________________________________________________________________________
Steve Hollasch Kubota Pacific Computer, Inc.
hollasch@kpc.com Santa Clara, California
Newsgroups: comp.graphics
From: uselton@wk207.nas.nasa.gov (Samuel P. Uselton)
Subject: Re: polyhedron/polyhedron intersection
Organization: NAS, NASA Ames Research Center, Moffett Field, California
Date: Wed, 11 Nov 92 18:59:59 GMT
Summary: Hollasch's suggestion is not sufficient
Polyhedra may intersect without either polyhedron containing any VERTICES
of the other. Think about modeling a spike through a board. If they
are both convex, things are relatively well understood and handled.
But if either or both are non-convex, things rapidly get ugly. Detecting
the existance of an intersection is easier than finding the intersection
exactly.
I addressed this problem a bit in my dissertation, around 1981. You
can usually gain substantial speed-up in finding the intersection
through the use of coherence. Once a single pair of intersecting polygon
are found, one can follow the line of intersection until it closes back
onto itself. The bad news is there can be O(n**2) separate polyhedra
resulting from the intersection of two polyhedra. As an example,
imagine a crude model of a hand, with a variable number of fingers, say j.
My crude model of the hand uses 4j + 4 polygons. Take two such models
and arrange them at 90 degrees, so that corresponding fingers interpenetrate.
Now make the number of fingers, j, LARGE. YUK.
Sam Uselton uselton@nas.nasa.gov
employed by CSC working for NASA (Ames) speaking for myself
From: dfr@usna.navy.mil (PROF D. Rogers (EAS FAC))
Newsgroups: comp.graphics
Subject: Re: polyhedron/polyhedron intersection
Date: 11 Nov 92 15:48:42 GMT
Organization: U. S. Naval Academy
In article <1992Nov11.040142.9570@cis.uab.edu> sloan@cis.uab.edu (Kenneth Sloan) writes:
!In article <1992Nov10.221943.18792@sophia.smith.edu! orourke@sophia.smith.edu (Joseph O'Rourke) writes:
!!In article <1992Nov10.192804.13981@zip.eecs.umich.edu! katkere@engin.umich.edu writes:
!!!I am looking for code/ideas for finding if two polyhedrons intersect.
!!
!!@article{CD
!!, author = "B. Chazelle and D. P. Dobkin"
!!, title = "Intersection of convex objects in two and three dimensions"
!!, journal = "J. ACM"
!!, volume = 34
!!, year = 1987
!!, pages = "1--27"
!!}
!
!But Joe...what if the polyhedra aren't convex?
Make them convex!!
Dave Rogers
From: dfr@usna.navy.mil (PROF D. Rogers (EAS FAC))
Newsgroups: comp.graphics
Subject: Re: polyhedron/polyhedron intersection
Date: 11 Nov 92 15:51:44 GMT
Organization: U. S. Naval Academy
In article <1992Nov11.135107.27052@sophia.smith.edu> orourke@sophia.smith.edu (Joseph O'Rourke) writes:
!In article <1992Nov11.002123.27579@kpc.com! hollasch@kpc.com (Steve Hollasch) writes:
!! ... Trivial Reject ... Trivial Accept ...
!! If neither of these tests succeed, then you must test each vertex of P
!!to see if it lies within Q, and then you have to test each vertex of Q to
!!determine if it lies within P.
!
! These tests are not sufficient to detect intersection, as two
!polyhedra may intersect without any vertex of one being inside the other.
An example might help--either you or Ken Sloan.
Dave Rogers
From: spl@pitstop.ucsd.edu (Steve Lamont)
Newsgroups: comp.graphics
Subject: Re: polyhedron/polyhedron intersection
Date: 12 Nov 92 00:23:51 GMT
Article-I.D.: network.1ds86nINN5or
Organization: University of Calif., San Diego/Microscopy and Imaging Resource
In article <2371@usna.NAVY.MIL> dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) writes:
>In article <1992Nov11.040142.9570@cis.uab.edu> sloan@cis.uab.edu (Kenneth Sloan) writes:
>!But Joe...what if the polyhedra aren't convex?
>
>Make them convex!!
All this reminds me of an old limerick:
There once was a man from Racine
Who built him a sex machine
Concave or convex
It could do either sex
But, oh, what a mother to clean...
Sorry.
spl
--
Steve Lamont, SciViGuy -- (619) 534-7968 -- spl@szechuan.ucsd.edu
UCSD Microscopy and Imaging Resource/UCSD Med School/La Jolla, CA 92093-0608
"Far out, man"
- President George Bush, heard in a stump speech on NPR
Newsgroups: comp.graphics
From: sloan@cis.uab.edu (Kenneth Sloan)
Subject: Re: polyhedron/polyhedron intersection
Organization: CIS, University of Alabama at Birmingham
Date: Thu, 12 Nov 1992 01:19:52 GMT
In article <2371@usna.NAVY.MIL> dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) writes:
>In article <1992Nov11.040142.9570@cis.uab.edu> sloan@cis.uab.edu (Kenneth Sloan) writes:
>!In article <1992Nov10.221943.18792@sophia.smith.edu! orourke@sophia.smith.edu (Joseph O'Rourke) writes:
>!!In article <1992Nov10.192804.13981@zip.eecs.umich.edu! katkere@engin.umich.edu writes:
>!!!I am looking for code/ideas for finding if two polyhedrons intersect.
>!!
>!!@article{CD
>!!, author = "B. Chazelle and D. P. Dobkin"
>!!, title = "Intersection of convex objects in two and three dimensions"
>!!, journal = "J. ACM"
>!!, volume = 34
>!!, year = 1987
>!!, pages = "1--27"
>!!}
>!
>!But Joe...what if the polyhedra aren't convex?
>
>Make them convex!!
Well, PROF Rogers, that may be the Navy way, but it's not the right way.
It's not even the *wrong* way.
Is it possible that someone on comp.graphics has finally posed a
question which cannot be answered by citing an ISBN number?
Here's a nice simple question to keep everyone occupied (sit down Joe -
this one's not for you).
GIVEN an arbitrary, simple polyhedron, P.
FIND the largest (greatest volume) convex polyhedron completely
contained in P.
--
Kenneth Sloan Computer and Information Sciences
sloan@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Newsgroups: comp.graphics
From: sloan@cis.uab.edu (Kenneth Sloan)
Subject: Re: polyhedron/polyhedron intersection
Organization: CIS, University of Alabama at Birmingham
Date: Thu, 12 Nov 1992 01:41:00 GMT
In article <2372@usna.NAVY.MIL> dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) writes:
>In article <1992Nov11.135107.27052@sophia.smith.edu> orourke@sophia.smith.edu (Joseph O'Rourke) writes:
>!In article <1992Nov11.002123.27579@kpc.com! hollasch@kpc.com (Steve Hollasch) writes:
>!! ... Trivial Reject ... Trivial Accept ...
>!! If neither of these tests succeed, then you must test each vertex of P
>!!to see if it lies within Q, and then you have to test each vertex of Q to
>!!determine if it lies within P.
>!
>! These tests are not sufficient to detect intersection, as two
>!polyhedra may intersect without any vertex of one being inside the other.
>
>An example might help--either you or Ken Sloan.
>
>Dave Rogers
>
The one I had in mind was, two tetrahedra T0, and T1, where T1 is simply
a translated version of T0:
T0: 0 0 0 T1: 0.7 0.7 -0.5
1 0 0 1.7 0.7 -0.5
0 1 0 0.7 1.7 -0.5
0 0 1 0.7 0.7 0.5
If my mental 3D modeller is working (always a chancy bet), none of the
vertices of Ti are contained in Tj, yet the two tetrahedra intersect.
If you have a set of blocks handy, pick up two and arrange them so that
they contact in a single point, which happens to be at the midpoint of
two edges (one edge of each block). Now push RealHard (but not
TooHard).
--
Kenneth Sloan Computer and Information Sciences
sloan@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
From: orourke@unix1.cs.umass.edu (Joseph O'Rourke)
Newsgroups: comp.graphics
Subject: Re: polyhedron/polyhedron intersection
Date: 12 Nov 92 02:29:20 GMT
Organization: Smith College, Northampton, MA, US
In article <2372@usna.NAVY.MIL> dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) writes:
>In article <1992Nov11.135107.27052@sophia.smith.edu> orourke@sophia.smith.edu (Joseph O'Rourke) writes:
>!In article <1992Nov11.002123.27579@kpc.com! hollasch@kpc.com (Steve Hollasch) writes:
>!! ... Trivial Reject ... Trivial Accept ...
>!! If neither of these tests succeed, then you must test each vertex of P
>!!to see if it lies within Q, and then you have to test each vertex of Q to
>!!determine if it lies within P.
>!
>! These tests are not sufficient to detect intersection, as two
>!polyhedra may intersect without any vertex of one being inside the other.
>
>An example might help--either you or Ken Sloan.
Zeroth, neither Ken nor I are examples :-).
First, the "Trivial Accept" test does not even work for convex
polygons in the plane. For he defined it in terms of minimum distance
from an interior point to a vertex:
"Then let Prmin & Qrmin be the minimum distance from the
center[s] to any of the vertices of the polyhedra, ...
Trivial Accept: |Pc - Qc| < (Prmin + Qrmin)"
Let P & Q be squares, Pc & Qc their centroids. Prmin & Qrmin are
radii of circumscribing circles. The "Trivial Accept" condition
tests for the intersection of these circles, which clearly does
not imply the intersection of the squares.
Second, Pc and Qc are arbitrary: "let Pc and Qc be ... arbitrary
'center[s]' of the polyhedr[a]." If Pc is very close to a vertex
of P, them Prmin is a fairly meaningless quantity. Let P & Q be
triangles, and choose Pc & Qc to be close to a vertex of each.
Then the circles defined by Prmin and Qrmin are tiny, and it is
easy to arrange the "Trivial Accept" rule to fail without any
vertex of one triangle falling inside the other, and yet the
triangles can intersect. I'd prefer not to draw this in ascii.
If you need an explicit example, draw these two triangles:
(0,0) (1,0) (0,10)
(-1,0) (1,10) (2,10)
Note that the failure of these ideas has nothing to do with
nonconvexity or three-dimensionality, as some have suggested.
Newsgroups: comp.graphics
From: ledwards@leland.Stanford.EDU (Laurence James Edwards)
Subject: Re: polyhedron/polyhedron intersection
Organization: DSG, Stanford University, CA 94305, USA
Date: Thu, 12 Nov 92 09:13:52 GMT
In article <1992Nov12.011952.1154@cis.uab.edu>, sloan@cis.uab.edu (Kenneth Sloan) writes:
|> [......]
|>
|> Here's a nice simple question to keep everyone occupied (sit down Joe -
|> this one's not for you).
|>
|> GIVEN an arbitrary, simple polyhedron, P.
|>
|> FIND the largest (greatest volume) convex polyhedron completely
|> contained in P.
Interesting question ... well it would seem that you'd have to split the
polyhedra with planes containing each concave edge. It would also seem that
to maximize the volume the splitting plane would have to contain a face.
So split the polyhedra up into convex pieces with two splitting planes
at each concave edge, then find the combination of convex pieces that
maximizes the volume and is convex. Not very efficient (and maybe not even
correct) but, as usual, this is just off the top of my head.
Larry Edwards
Newsgroups: comp.graphics
From: seitz@cs.wisc.edu (Steve Seitz)
Subject: Re: polyhedron/polyhedron intersection
Organization: U of Wisconsin CS Dept
Date: Thu, 12 Nov 1992 16:11:17 GMT
In article <1992Nov12.091352.5323@leland.Stanford.EDU>, ledwards@leland.Stanford.EDU (Laurence James Edwards) writes:
|> In article <1992Nov12.011952.1154@cis.uab.edu>, sloan@cis.uab.edu (Kenneth Sloan) writes:
|> |> [......]
|> |>
|> |> Here's a nice simple question to keep everyone occupied (sit down Joe -
|> |> this one's not for you).
|> |>
|> |> GIVEN an arbitrary, simple polyhedron, P.
|> |>
|> |> FIND the largest (greatest volume) convex polyhedron completely
|> |> contained in P.
|>
|> Interesting question ... well it would seem that you'd have to split the
|> polyhedra with planes containing each concave edge. It would also seem that
|> to maximize the volume the splitting plane would have to contain a face.
|> So split the polyhedra up into convex pieces with two splitting planes
|> at each concave edge, then find the combination of convex pieces that
|> maximizes the volume and is convex. Not very efficient (and maybe not even
|> correct) but, as usual, this is just off the top of my head.
|>
I don't think this will work in general (if I understand you correctly).
Try it with this example:
____________________
| |
| |
minute sharp indentation --> > |
| |
|___________________|
Imagine this in 3D by sweeping along the Z axis (through the screen).
If I understand your suggestion, you'll get something like:
____________________
| / |
| / |
\/ |
/\ |
| \ |
|__\________________|
which is obviously suboptimal. The problem gets worse as the corner gets
sharper, in the limit dividing the box in half.
-Steve Seitz
From: dfr@usna.navy.mil (PROF D. Rogers (EAS FAC))
Newsgroups: comp.graphics
Subject: Re: polyhedron/polyhedron intersection
Date: 12 Nov 92 15:55:35 GMT
Organization: U. S. Naval Academy
In article <1992Nov12.011952.1154@cis.uab.edu> sloan@cis.uab.edu (Kenneth Sloan) writes:
!In article <2371@usna.NAVY.MIL! dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) writes:
!!In article <1992Nov11.040142.9570@cis.uab.edu! sloan@cis.uab.edu (Kenneth Sloan) writes:
!!!In article <1992Nov10.221943.18792@sophia.smith.edu! orourke@sophia.smith.edu (Joseph O'Rourke) writes:
!!!!In article <1992Nov10.192804.13981@zip.eecs.umich.edu! katkere@engin.umich.edu writes:
!!!!!I am looking for code/ideas for finding if two polyhedrons intersect.
!!!!
!!!!@article{CD
!!!!, author = "B. Chazelle and D. P. Dobkin"
!!!!, title = "Intersection of convex objects in two and three dimensions"
!!!!, journal = "J. ACM"
!!!!, volume = 34
!!!!, year = 1987
!!!!, pages = "1--27"
!!!!}
!!!
!!!But Joe...what if the polyhedra aren't convex?
!!
!!Make them convex!!
!
!Well, PROF Rogers, that may be the Navy way, but it's not the right way.
!It's not even the *wrong* way.
I don't know about the Navy way since I almost never do ANYTHING
the Navy way, however please explain why it is NOT the RIGHT way
and not even the WRONG way.
!Is it possible that someone on comp.graphics has finally posed a
!question which cannot be answered by citing an ISBN number?
!
!Here's a nice simple question to keep everyone occupied (sit down Joe -
!this one's not for you).
!
!GIVEN an arbitrary, simple polyhedron, P.
!
!FIND the largest (greatest volume) convex polyhedron completely
!contained in P.
It appears to me that this is a rather different problem than
originally posed. In addition, please define exactly what a
simple polyhedron is.
Dave Rogers
From: dfr@usna.navy.mil (PROF D. Rogers (EAS FAC))
Newsgroups: comp.graphics
Subject: Re: polyhedron/polyhedron intersection
Date: 12 Nov 92 15:59:12 GMT
Organization: U. S. Naval Academy
In article <56098@dime.cs.umass.edu> orourke@unix1.cs.umass.edu (Joseph O'Rourke) writes:
!In article <2372@usna.NAVY.MIL! dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) writes:
!!In article <1992Nov11.135107.27052@sophia.smith.edu! orourke@sophia.smith.edu (Joseph O'Rourke) writes:
!!!In article <1992Nov11.002123.27579@kpc.com! hollasch@kpc.com (Steve Hollasch) writes:
!!!! ... Trivial Reject ... Trivial Accept ...
!!!! If neither of these tests succeed, then you must test each vertex of P
!!!!to see if it lies within Q, and then you have to test each vertex of Q to
!!!!determine if it lies within P.
!!!
!!! These tests are not sufficient to detect intersection, as two
!!!polyhedra may intersect without any vertex of one being inside the other.
!!
!!An example might help--either you or Ken Sloan.
!
!Zeroth, neither Ken nor I are examples :-).
You and Ken are both certainly examples of SOMETHING :-}=
(the curly and = are for the old wrinkled ones with beards :-}= )
!
!First, the "Trivial Accept" test does not even work for convex
!polygons in the plane. For he defined it in terms of minimum distance
!from an interior point to a vertex:
!
! "Then let Prmin & Qrmin be the minimum distance from the
! center[s] to any of the vertices of the polyhedra, ...
! Trivial Accept: |Pc - Qc| < (Prmin + Qrmin)"
!
!Let P & Q be squares, Pc & Qc their centroids. Prmin & Qrmin are
!radii of circumscribing circles. The "Trivial Accept" condition
!tests for the intersection of these circles, which clearly does
!not imply the intersection of the squares.
!
!Second, Pc and Qc are arbitrary: "let Pc and Qc be ... arbitrary
!'center[s]' of the polyhedr[a]." If Pc is very close to a vertex
!of P, them Prmin is a fairly meaningless quantity. Let P & Q be
!triangles, and choose Pc & Qc to be close to a vertex of each.
!Then the circles defined by Prmin and Qrmin are tiny, and it is
!easy to arrange the "Trivial Accept" rule to fail without any
!vertex of one triangle falling inside the other, and yet the
!triangles can intersect. I'd prefer not to draw this in ascii.
!If you need an explicit example, draw these two triangles:
!
! (0,0) (1,0) (0,10)
! (-1,0) (1,10) (2,10)
!
!Note that the failure of these ideas has nothing to do with
!nonconvexity or three-dimensionality, as some have suggested.
I didn't need and example but rather thought the net did.
Thanks for providing same.
Dave Rogers
Article 571 of comp.graphics.algorithms:
Newsgroups: comp.graphics.algorithms
Path: kpc!news.kpc.com!decwrl!uunet!brunix!pmh
From: pmh@cs.brown.edu (Philip M. Hubbard)
Subject: Re: Distances Computation between Convex Polyhedra
Message-ID: <1993Aug26.020604.9732@cs.brown.edu>
Sender: news@cs.brown.edu
Organization: Brown University Department of Computer Science
References: <1993Aug20.193315.4283@cs.sfu.ca> <1993Aug20.213446.24249@kpc.com> <1993Aug21.013250.28987@sophia.smith.edu>
Date: Thu, 26 Aug 1993 02:06:04 GMT
Lines: 48
In article <1993Aug21.013250.28987@sophia.smith.edu> orourke@sophia.smith.edu (Joseph O'Rourke) writes:
> I would add that if either polyhedron is convex, or if you know
>that the polyhedra a separable by a plane, then asymptotic improvements
>are possible. For example, the distance from a face of P2 to P1
>can be found in O(logn) time if P1 is convex. So this knocks down
>the naive quadratic computation to O(nlogn) when one polyhedron is
>convex.
> The idea behind this speedup is to use a hierarchical representation
>for the convex polyhedron, a nested collection of polyhedra with
>several nice properties that permit certain queries to be performed
>in logarithmic time.
> Here is the best reference on this; it refers to all earlier
>work.
>
>@inproceedings{Dobkin.Kirkpatrick
>, author = "D. P. Dobkin and D. G. Kirkpatrick"
>, title = "Determining the separation of preprocessed polyhedra -- a unified approach"
>, booktitle = "Proc. 17th Internat. Colloq. Automata Lang. Program."
>, series = "Lecture Notes in Computer Science"
>, volume = 443
>, publisher = "Springer-Verlag"
>, year = 1990
>, pages = "400--413"
>}
I have not read this paper, but there is a more recent one that claims better
performance:
Lin, Ming C. and John F. Canny, "A Fast Algorithm for Incremental Distance
Calculation," Proceedings of the 1991 IEEE International Conference on
Robotics and Automation, April 1991, pp. 1008-1014.
The authors describe an algorithm that tracks the closest distance between
two moving convex polyhedra. According to the abstract,
"Data from numerous experiments tested on a broad set of convex polyhedra
on R^3 shows that the running time is roughly CONSTANT for finding closest
points when nearest points are approximately known and is linear in [the]
total number of vertices if no special initialization is done."
The key idea is that the closest points on the polyhedra at timestep t+1
are closely related to the closest points at timestep t, so little work is
required to update the points. The algorithm is quite straight-forward and
is probably not difficult to implement.
-------------------------------------------------------------------------------
"I ain't broke but I'm badly bent." -- Willie Dixon
Philip Martyn Hubbard: pmh@cs.brown.edu, pmh@browncs.bitnet, uunet!brunix!pmh