home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / graphics / 11795 < prev    next >
Encoding:
Internet Message Format  |  1992-11-12  |  2.6 KB
  1. Path: sparky!uunet!stanford.edu!rutgers!uwvax!cs.wisc.edu!seitz
  2. From: seitz@cs.wisc.edu (Steve Seitz)
  3. Newsgroups: comp.graphics
  4. Subject: Re: polyhedron/polyhedron intersection
  5. Keywords: 3d graphics, intersection
  6. Message-ID: <1992Nov12.161117.24398@cs.wisc.edu>
  7. Date: 12 Nov 92 16:11:17 GMT
  8. References: <1992Nov10.221943.18792@sophia.smith.edu> <1992Nov11.040142.9570@cis.uab.edu> <2371@usna.NAVY.MIL> <1992Nov12.011952.1154@cis.uab.edu> <1992Nov12.091352.5323@leland.Stanford.EDU>
  9. Sender: news@cs.wisc.edu (The News)
  10. Organization: U of Wisconsin CS Dept
  11. Lines: 46
  12.  
  13. In article <1992Nov12.091352.5323@leland.Stanford.EDU>, ledwards@leland.Stanford.EDU (Laurence James Edwards) writes:
  14. |> In article <1992Nov12.011952.1154@cis.uab.edu>, sloan@cis.uab.edu (Kenneth Sloan) writes:
  15. |> |> [......]
  16. |> |> 
  17. |> |> Here's a nice simple question to keep everyone occupied (sit down Joe -
  18. |> |> this one's not for you).  
  19. |> |> 
  20. |> |> GIVEN an arbitrary, simple polyhedron, P.
  21. |> |> 
  22. |> |> FIND the largest (greatest volume) convex polyhedron completely
  23. |> |> contained in P.
  24. |> 
  25. |> Interesting question ... well it would seem that you'd have to split the
  26. |> polyhedra with planes containing each concave edge. It would also seem that
  27. |> to maximize the volume the splitting plane would have to contain a face.
  28. |> So split the polyhedra up into convex pieces with two splitting planes
  29. |> at each concave edge, then find the combination of convex pieces that
  30. |> maximizes the volume and is convex. Not very efficient (and maybe not even
  31. |> correct) but, as usual, this is just off the top of my head.
  32. |> 
  33.  
  34. I don't think this will work in general (if I understand you correctly).
  35. Try it with this example:
  36.  
  37.                                 ____________________
  38.                                 |                   |
  39.                                 |                   |
  40.  minute sharp indentation -->   >                   |  
  41.                                 |                   |
  42.                                 |___________________|
  43.  
  44. Imagine this in 3D by sweeping along the Z axis (through the screen).
  45. If I understand your suggestion, you'll get something like:
  46.  
  47.                                 ____________________
  48.                                 |  /                |
  49.                                 | /                 |
  50.                                 \/                  |
  51.                                 /\                  |
  52.                                 | \                 |
  53.                                 |__\________________|
  54.  
  55. which is obviously suboptimal.  The problem gets worse as the corner gets
  56. sharper, in the limit dividing the box in half.
  57.  
  58. -Steve Seitz
  59.