home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / graphics / 11724 < prev    next >
Encoding:
Internet Message Format  |  1992-11-10  |  2.4 KB
  1. Path: sparky!uunet!news.tek.com!ogicse!emory!utkcs2!willis1.cis.uab.edu!sloan
  2. From: sloan@cis.uab.edu (Kenneth Sloan)
  3. Newsgroups: comp.graphics
  4. Subject: Re: polyhedron/polyhedron intersection
  5. Keywords: 3d graphics, intersection
  6. Message-ID: <1992Nov11.041237.9669@cis.uab.edu>
  7. Date: 11 Nov 92 04:12:37 GMT
  8. Article-I.D.: cis.1992Nov11.041237.9669
  9. References: <1992Nov10.192804.13981@zip.eecs.umich.edu> <1992Nov11.002123.27579@kpc.com>
  10. Organization: CIS, University of Alabama at Birmingham
  11. Lines: 40
  12.  
  13. In article <1992Nov11.002123.27579@kpc.com> hollasch@kpc.com (Steve Hollasch) writes:
  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. Even for simple polyhedra, is it not possible for two polyhedra to
  40. intersect even though your Trivial Reject fails, your Trivial Accept
  41. fails, and no vertex lies INSIDE the other polyhedron?  I believe that
  42. you must also test all edges for intersection with all faces of the
  43. other polyhedron or triangulate (tetrahedralize) and test all tetrahedra
  44. in one polyhedron against all tetrahedra in the other..  Testing
  45. vertices works for polygons - but polyhedra are tougher.
  46.  
  47.  
  48. -- 
  49. Kenneth Sloan                   Computer and Information Sciences
  50. sloan@cis.uab.edu               University of Alabama at Birmingham
  51. (205) 934-2213                  115A Campbell Hall, UAB Station 
  52. (205) 934-5473 FAX              Birmingham, AL 35294-1170
  53.