home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / graphics / 11714 < prev    next >
Encoding:
Text File  |  1992-11-10  |  1.9 KB  |  42 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!ferkel.ucsb.edu!taco!rock!stanford.edu!agate!ames!saimiri.primate.wisc.edu!zaphod.mps.ohio-state.edu!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.002123.27579@kpc.com>
  6. Summary: How I'd approach the problem...
  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>
  11. Date: Wed, 11 Nov 1992 00:21:23 GMT
  12. Lines: 28
  13.  
  14. katkere@engin.umich.edu writes:
  15. | I am looking for code/ideas for finding if two polyhedrons intersect.
  16. | I think that polygon/polygon intersection will be used as a building
  17. | block for this. Is there a better way to do this? Can the sgi
  18. | rendering engine be used in any way to do this? Where can I find
  19. | code for polygon/polygon intersection?
  20.  
  21.     Polyhedron intersection has both trivial accept and trivial reject
  22. conditions.  Let P and Q be two polyhedra, and let Pc and Qc be some
  23. arbitrary "center" of the polyhedron.  Then let Prmin & Qrmin be the
  24. minimum distance from the center to any of the vertices of the polyhedra,
  25. and Prmax & Qrmax be the maximum distances from the polyhedra centers to any
  26. vertex on the corresponding polyhedra.
  27.  
  28.     Trivial Reject:  |Pc - Qc| > (Prmax + Qrmax)
  29.  
  30.     Trivial Accept:  |Pc - Qc| < (Prmin + Qrmin)
  31.  
  32.     If neither of these tests succeed, then you must test each vertex of P
  33. to see if it lies within Q, and then you have to test each vertex of Q to
  34. determine if it lies within P.
  35.  
  36.     This is not all that simple for non-simple polyhedra (e.g. a torus), but
  37. you may just be dealing with simple polyhedra anyway.
  38.  
  39. ______________________________________________________________________________
  40. Steve Hollasch                                   Kubota Pacific Computer, Inc.
  41. hollasch@kpc.com                                 Santa Clara, California
  42.