NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/graphics/11799

Internet Message Format | 1992-11-12 | 2.8 KB

Path: sparky!uunet!usna!dfr
From: [e-mail] (PROF D. Rogers (EAS FAC))
Newsgroups: comp.graphics
Subject: Re: polyhedron/polyhedron intersection
Keywords: 3d graphics, intersection
Message-ID: <[e-mail]>
Date: 12 Nov 92 15:59:12 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]>
Sender: [e-mail]
Organization: U. S. Naval Academy
Lines: 54

In article <[e-mail]> [e-mail] (Joseph O'Rourke) writes:
!In article <[e-mail]! [e-mail] (PROF D. Rogers (EAS FAC)) writes:
!!In article <[e-mail]! [e-mail] (Joseph O'Rourke) writes:
!!!In article <[e-mail]! [e-mail] (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