home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / graphics / 8081 < prev    next >
Encoding:
Internet Message Format  |  1992-07-23  |  1.8 KB
  1. Path: sparky!uunet!snorkelwacker.mit.edu!ai-lab!fiber-one!sundar
  2. From: sundar@fiber-one.ai.mit.edu (Sundar Narasimhan)
  3. Newsgroups: comp.graphics
  4. Subject: Re: Fast intersection DETECTION for convex polyhedra?
  5. Message-ID: <25764@life.ai.mit.edu>
  6. Date: 23 Jul 92 16:12:48 GMT
  7. References: <1992Jul9.134621.20715@fel.tno.nl> <jqsx0dj@rpi.edu>
  8. Sender: news@ai.mit.edu
  9. Reply-To: sundar@ai.mit.edu
  10. Organization: MIT Artificial Intelligence Laboratory
  11. Lines: 28
  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. %Y Conference
  31. %A Lin, M. C., and Canny, J. F.
  32. %T A Fast Algorithm for Incremental Distance Calculation
  33. %J Proc. IEEE Conference on Robotics and Automation
  34. %P 1008-1014
  35. %X Very clean paper on how to compute closest features. 
  36.    Considers 6 cases. Uses applicability criteria to suggest what the
  37.    next pair of features to consider is. Handles convex objects only.
  38.    Preprocessing necessary for making boundary/coboundaries constant
  39.    size (hence alg. runs in constant time w/ preprocessing). 
  40. %D 1991
  41.