home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / graphics / 11728 < prev    next >
Encoding:
Internet Message Format  |  1992-11-10  |  1.8 KB
  1. Path: sparky!uunet!ogicse!news.u.washington.edu!stein.u.washington.edu!chuckb
  2. From: chuckb@stein.u.washington.edu (Charles Bass)
  3. Newsgroups: comp.graphics
  4. Subject: Re: polyhedron/polyhedron intersection
  5. Keywords: 3d graphics, intersection
  6. Message-ID: <1992Nov11.071010.721@u.washington.edu>
  7. Date: 11 Nov 92 07:10:10 GMT
  8. Article-I.D.: u.1992Nov11.071010.721
  9. References: <1992Nov10.192804.13981@zip.eecs.umich.edu> <1992Nov10.221943.18792@sophia.smith.edu> <1992Nov11.040142.9570@cis.uab.edu>
  10. Sender: news@u.washington.edu (USENET News System)
  11. Organization: University of Washington
  12. Lines: 29
  13.  
  14.  
  15. I am using an algorithm developed at the University of
  16. Washington.  It has been accepted for publication but as of
  17. today it is not known when it will be published.
  18.  
  19. I use the routines to detect collisions between solid modeled
  20. objects in a real time simulation program.  In general the
  21. routine has proven an improvement over our previous (n^2)
  22. routine.  Some details:
  23.  
  24. 1) It requires triangulated polygons.
  25. 2) It is well suited for checking collisions between moving
  26.    objects (ones that don't overlap very much)
  27. 3) In practice the algorithm is very fast although the worst
  28.    case looks to run in O((n^2)/2) time
  29. 4) Several "speed hacks" have been incorporated.  These mostly 
  30.    are marginal but in the name of efficiency... (and less
  31.    readable code ;-))
  32. 5) Convex hull information can marginally speed the test.  
  33. 6) I did *not* implement an engulfment test.  I don't have
  34.    details on this process but could possibly provide a ref. 
  35. For details email me.
  36.  
  37.  
  38. Chuck Bass                             |
  39. College of Forest-Systems Engineering  |
  40. University of Washington               | FAX   (206)-685-3091
  41. Mailstop AR-10                         | voice (206)-685-2198
  42. Seattle,  WA  98195                    | email chuckb@u.washington.edu
  43.