home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / graphics / 11756 < prev    next >
Encoding:
Text File  |  1992-11-11  |  3.1 KB  |  64 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!ukma!darwin.sura.net!sgiblab!news.kpc.com!kpc!hollasch
  3. From: hollasch@kpc.com (Steve Hollasch)
  4. Subject: Re: polyhedron/polyhedron intersection
  5. Message-ID: <1992Nov11.193439.20660@kpc.com>
  6. Summary: Trivial accept and reject tests; a defense
  7. Keywords: 3d graphics, intersection
  8. Sender: usenet@kpc.com
  9. Organization: Kubota Pacific Computer, Inc.
  10. References: <1992Nov10.192804.13981@zip.eecs.umich.edu> <1992Nov11.002123.27579@kpc.com> <1992Nov11.041237.9669@cis.uab.edu>
  11. Date: Wed, 11 Nov 1992 19:34:39 GMT
  12. Lines: 50
  13.  
  14. katkere@engin.umich.edu writes:
  15. | I am looking for code/ideas for finding if two polyhedrons intersect.
  16.  
  17. hollasch@kpc.com (Steve Hollasch) writes:
  18. >     Polyhedron intersection has both trivial accept and trivial reject
  19. > conditions.  Let P and Q be two polyhedra, and let Pc and Qc be some
  20. > arbitrary "center" of the polyhedron.  Then let Prmin & Qrmin be the
  21. > minimum distance from the center to any of the vertices of the polyhedra,
  22. > and Prmax & Qrmax be the maximum distances from the polyhedra centers to any
  23. > vertex on the corresponding polyhedra.
  24. >
  25. >    Trivial Reject:  |Pc - Qc| > (Prmax + Qrmax)
  26. >
  27. >    Trivial Accept:  |Pc - Qc| < (Prmin + Qrmin)
  28. >
  29. >     If neither of these tests succeed, then you must test each vertex of P
  30. > to see if it lies within Q, and then you have to test each vertex of Q to
  31. > determine if it lies within P.
  32.  
  33. sloan@cis.uab.edu (Kenneth Sloan) writes:
  34. | Even for simple polyhedra, is it not possible for two polyhedra to
  35. | intersect even though your Trivial Reject fails, your Trivial Accept
  36. | fails, and no vertex lies INSIDE the other polyhedron?  I believe that
  37. | you must also test all edges for intersection with all faces of the
  38. | other polyhedron or triangulate (tetrahedralize) and test all tetrahedra
  39. | in one polyhedron against all tetrahedra in the other..  Testing
  40. | vertices works for polygons - but polyhedra are tougher.
  41.  
  42.     No, the trivial reject is sufficient.  It's basically a test to see if
  43. the bounding spheres can intersect.  If the bounding spheres cannot
  44. intersect, then the objects themselves cannot.
  45.  
  46.     The trivial accept doesn't work though.  Not for the reason you mention,
  47. but because it doesn't properly handle concave polyhedra (e.g. a cylinder
  48. passing through the hole of a torus).  If it's easy to break the polyhedron
  49. into convex components, then this test should work, provided that you are
  50. testing for volume (not just surface) intersection.  This is because an
  51. object wholly enclosed in another object is an intersection of volumes but
  52. not of surfaces.
  53.  
  54.     With respect to rigorous (as opposed to trivial) intersection, I really
  55. just sort of kind of tossed out the vertex containment test without giving
  56. it a great deal of thought.  I now agree that edge-face intersection must
  57. also be considered.  In order to test this, I propose we hold a contest ...
  58.  
  59.     B^)
  60.  
  61. ______________________________________________________________________________
  62. Steve Hollasch                                   Kubota Pacific Computer, Inc.
  63. hollasch@kpc.com                                 Santa Clara, California
  64.