home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / graphics / 8047 < prev    next >
Encoding:
Text File  |  1992-07-22  |  1.2 KB  |  32 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!usc!rpi!wrf
  3. From:  wrf@ecse.rpi.edu (Wm Randolph Franklin)
  4. Subject: Re: Fast intersection DETECTION for convex polyhedra?
  5. Message-ID: <jqsx0dj@rpi.edu>
  6. Sender: wrf@speed.ecse.rpi.edu
  7. Nntp-Posting-Host: speed.ecse.rpi.edu
  8. Organization: Rensselaer Polytechnic Institute, Troy, NY
  9. References: <1992Jul9.134621.20715@fel.tno.nl>
  10. Date: Wed, 22 Jul 1992 22:32:46 GMT
  11. Lines: 19
  12.  
  13.  
  14. In article <1992Jul9.134621.20715@fel.tno.nl> on Thu, 9 Jul 92 13:46:21 GMT,
  15. rxkc2@fel.tno.nl (R. Kiel) writes:
  16.  
  17.   > For a real-time visualisation system I need an algorithm that will
  18.   > tell me whether or not two convex polyhedra intersect.
  19.  
  20. A separating plane for the two polyhedra exists iff they don't
  21. intersect.  This can be formulated as a linear programming problem and
  22. solved.  It should be reasonably fast.
  23.  
  24. This method meets your req to determine the intersectability w/o finding
  25. the intersection, but it may be too complicated.
  26.  
  27. A 2-D version of this might be mentioned somewhere in Preparata and
  28. Shamos.
  29. -- 
  30. Wm. Randolph Franklin,  wrf@ecse.rpi.edu, (518) 276-6077;  Fax: -6261
  31. ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, Troy NY, 12180 USA
  32.