home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / graphics / 11755 < prev    next >
Encoding:
Text File  |  1992-11-11  |  1.7 KB  |  36 lines

  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!sun-barr!ames!agate!stanford.edu!eos!data.nas.nasa.gov!wk207.nas.nasa.gov!uselton
  3. From: uselton@wk207.nas.nasa.gov (Samuel P. Uselton)
  4. Subject: Re: polyhedron/polyhedron intersection
  5. Keywords: 3d graphics, intersection
  6. References: <1992Nov10.192804.13981@zip.eecs.umich.edu> <1992Nov11.002123.27579@kpc.com>
  7. Sender: Sam Uselton
  8. Organization: NAS, NASA Ames Research Center, Moffett Field, California
  9. Date: Wed, 11 Nov 92 18:59:59 GMT
  10. Message-ID: <1992Nov11.185959.515@nas.nasa.gov>
  11. Summary: Hollasch's suggestion is not sufficient
  12. Lines: 22
  13.  
  14.  
  15. Polyhedra may intersect without either polyhedron containing any VERTICES 
  16. of the other.  Think about modeling a spike through a board.  If they
  17. are both convex, things are relatively well understood and handled.
  18. But if either or both are non-convex, things rapidly get ugly.  Detecting
  19. the existance of an intersection is easier than finding the intersection
  20. exactly.
  21.  
  22. I addressed this problem a bit in my dissertation, around 1981.  You
  23. can usually gain substantial speed-up in finding the intersection
  24. through the use of coherence.  Once a single pair of intersecting polygon
  25. are found, one can follow the line of intersection until it closes back
  26. onto itself.  The bad news is there can be O(n**2) separate polyhedra
  27. resulting from the intersection of two polyhedra.  As an example,
  28. imagine a crude model of a hand, with a variable number of fingers, say j.
  29. My crude model of the hand uses 4j + 4 polygons.  Take two such models
  30. and arrange them at 90 degrees, so that corresponding fingers interpenetrate.
  31. Now make the number of fingers, j, LARGE.  YUK.
  32.  
  33. Sam Uselton        uselton@nas.nasa.gov    
  34. employed by CSC        working for NASA (Ames)     speaking for myself
  35.     
  36.