home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / graphics / 8092 < prev    next >
Encoding:
Text File  |  1992-07-23  |  1.6 KB  |  38 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!caen!batcomputer!cornell!deb
  3. From: deb@cs.cornell.edu (David Baraff)
  4. Subject: Re: Fast intersection DETECTION for convex polyhedra?
  5. Message-ID: <1992Jul23.213347.29219@cs.cornell.edu>
  6. Organization: Cornell Univ. CS Dept, Ithaca NY 14853
  7. References: <1992Jul9.134621.20715@fel.tno.nl> <jqsx0dj@rpi.edu> <25764@life.ai.mit.edu>
  8. Date: Thu, 23 Jul 1992 21:33:47 GMT
  9. Lines: 27
  10.  
  11. sundar@fiber-one.ai.mit.edu (Sundar Narasimhan) writes:
  12.  
  13. >In article <jqsx0dj@rpi.edu>, wrf@ecse.rpi.edu (Wm Randolph Franklin) writes:
  14. >|> 
  15. >|> In article <1992Jul9.134621.20715@fel.tno.nl> on Thu, 9 Jul 92 13:46:21 GMT,
  16. >|> rxkc2@fel.tno.nl (R. Kiel) writes:
  17. >|> 
  18. >|>   > For a real-time visualisation system I need an algorithm that will
  19. >|>   > tell me whether or not two convex polyhedra intersect.
  20. >|> 
  21. >|> A separating plane for the two polyhedra exists iff they don't
  22. >|> intersect.  This can be formulated as a linear programming problem and
  23. >|> solved.  It should be reasonably fast.
  24. >I don't know if I responded to this already, but Lin and Canny's algorithm
  25. >is the fastest (and easiest to implement) I know of currently.
  26. >I'd like to hear if people know of others. (WRT approximation algs., the
  27. >ellipsoidal approximation of Elon Rimon, and Featherstone's 'swept bubble' 
  28. >sphere approximation should also be pretty fast).
  29.  
  30. At the risk of being self-promoting, check out
  31. the article "Curved Surfaces and Coherence for Non-penetrating
  32. Rigid Body Motion", in the 1990 SIGGRAPH conference proceedings.
  33. A discussion of convex polyhedra is covered in that paper.
  34.  
  35.     David Baraff
  36.     deb@cs.cornell.edu
  37.  
  38.