home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / graphics / 11827 < prev    next >
Encoding:
Internet Message Format  |  1992-11-12  |  2.9 KB
  1. Path: sparky!uunet!know!cass.ma02.bull.com!mips2!news.bbn.com!noc.near.net!nic.umass.edu!caen!zaphod.mps.ohio-state.edu!darwin.sura.net!jvnc.net!yale.edu!qt.cs.utexas.edu!cs.utexas.edu!sun-barr!ames!agate!stanford.edu!leland.Stanford.EDU!leland.Stanford.EDU!ledwards
  2. From: ledwards@leland.Stanford.EDU (Laurence James Edwards)
  3. Newsgroups: comp.graphics
  4. Subject: Re: polyhedron/polyhedron intersection
  5. Keywords: 3d graphics, intersection
  6. Message-ID: <1992Nov12.225918.23756@leland.Stanford.EDU>
  7. Date: 12 Nov 92 22:59:18 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> <1992Nov12.161117.24398@cs.wisc.edu>
  9. Sender: news@leland.Stanford.EDU (Mr News)
  10. Organization: DSG, Stanford University, CA 94305, USA
  11. Lines: 44
  12.  
  13. In article <1992Nov12.161117.24398@cs.wisc.edu>, seitz@cs.wisc.edu (Steve Seitz) writes:
  14. |> In article <1992Nov12.091352.5323@leland.Stanford.EDU>, ledwards@leland.Stanford.EDU (Laurence James Edwards) writes:
  15. |> |> In article <1992Nov12.011952.1154@cis.uab.edu>, sloan@cis.uab.edu (Kenneth Sloan) writes:
  16. |> |> |> [......]
  17. |> |> |> 
  18. |> |> |> Here's a nice simple question to keep everyone occupied (sit down Joe -
  19. |> |> |> this one's not for you).  
  20. |> |> |> 
  21. |> |> |> GIVEN an arbitrary, simple polyhedron, P.
  22. |> |> |> 
  23. |> |> |> FIND the largest (greatest volume) convex polyhedron completely
  24. |> |> |> contained in P.
  25. |> |> 
  26. |> |> Interesting question ... well it would seem that you'd have to split the
  27. |> |> polyhedra with planes containing each concave edge. It would also seem that
  28. |> |> to maximize the volume the splitting plane would have to contain a face.
  29. |> |> So split the polyhedra up into convex pieces with two splitting planes
  30. |> |> at each concave edge, then find the combination of convex pieces that
  31. |> |> maximizes the volume and is convex. Not very efficient (and maybe not even
  32. |> |> correct) but, as usual, this is just off the top of my head.
  33. |> |> 
  34. |> 
  35. |> I don't think this will work in general (if I understand you correctly).
  36. |> Try it with this example:
  37. |> 
  38. |>                                 ____________________
  39. |>                                 |                   |
  40. |>                                 |                   |
  41. |>  minute sharp indentation -->   >                   |  
  42. |>                                 |                   |
  43. |>                                 |___________________|
  44. |>  
  45.  
  46. Yep, you are right. It still seems though that any splitting plane must
  47. contain a concave edge ... maybe the thing to do is pick ones that
  48. maximize the volume on one side ... sounds like a linear programming type
  49. problem although we're dealing with concave polyhedra here so I'd guess
  50. one couldn't use LP.
  51.  
  52. This problem sounds vaguely like a problem I saw in a computational geometry
  53. course I took a while ago ... but I can't remember the approach or whether it
  54. was in fact the same problem.
  55.  
  56. Larry Edwards
  57.