Newsgroups: comp.graphics From: katkere@eecs.umich.edu (Arun L. Katkere) Subject: polyhedron/polyhedron intersection Reply-To: katkere@engin.umich.edu Organization: University of Michigan EECS Dept., Ann Arbor, MI Date: Tue, 10 Nov 1992 19:28:04 GMT I am looking for code/ideas for finding if two polyhedrons intersect. I think that polygon/polygon intersection will be used as a building block for this. Is there a better way to do this? Can the sgi rendering engine be used in any way to do this? Where can I find code for polygon/polygon intersection? I am not a c.g subscriber. But I searched thro' the FAQ, about 1300 subject lines, some ftp sites and couldn't find any info on this. Any help will be appreciated. Send replies to katkere@eecs.umich.edu. Thanks, -arun -- +-----------------------------------------------------------------------------+ | Arun Katkere | The University of Michigan AI Lab | | katkere@engin.umich.edu | 147 ATL, 1101 Beal Avenue | | O:(313)763-1563 | R:(313)761-9462 | Ann Arbor, MI 48109-2110 | +-----------------------------------------------------------------------------+ Newsgroups: comp.graphics From: orourke@sophia.smith.edu (Joseph O'Rourke) Subject: Re: polyhedron/polyhedron intersection Organization: Smith College, Northampton, MA, US Date: Tue, 10 Nov 1992 22:19:43 GMT katkere@engin.umich.edu writes: >I am looking for code/ideas for finding if two polyhedrons intersect. @article{CD , author = "B. Chazelle and D. P. Dobkin" , title = "Intersection of convex objects in two and three dimensions" , journal = "J. ACM" , volume = 34 , year = 1987 , pages = "1--27" } Newsgroups: comp.graphics From: hollasch@kpc.com (Steve Hollasch) Subject: Re: polyhedron/polyhedron intersection Summary: How I'd approach the problem... Organization: Kubota Pacific Computer, Inc. Date: Wed, 11 Nov 1992 00:21:23 GMT katkere@engin.umich.edu writes: | I am looking for code/ideas for finding if two polyhedrons intersect. | I think that polygon/polygon intersection will be used as a building | block for this. Is there a better way to do this? Can the sgi | rendering engine be used in any way to do this? Where can I find | code for polygon/polygon intersection? Polyhedron intersection has both trivial accept and trivial reject conditions. Let P and Q be two polyhedra, and let Pc and Qc be some arbitrary "center" of the polyhedron. Then let Prmin & Qrmin be the minimum distance from the center to any of the vertices of the polyhedra, and Prmax & Qrmax be the maximum distances from the polyhedra centers to any vertex on the corresponding polyhedra. Trivial Reject: |Pc - Qc| > (Prmax + Qrmax) Trivial Accept: |Pc - Qc| < (Prmin + Qrmin) If neither of these tests succeed, then you must test each vertex of P to see if it lies within Q, and then you have to test each vertex of Q to determine if it lies within P. This is not all that simple for non-simple polyhedra (e.g. a torus), but you may just be dealing with simple polyhedra anyway. ______________________________________________________________________________ Steve Hollasch Kubota Pacific Computer, Inc. hollasch@kpc.com Santa Clara, California Newsgroups: comp.graphics From: sloan@cis.uab.edu (Kenneth Sloan) Subject: Re: polyhedron/polyhedron intersection Organization: CIS, University of Alabama at Birmingham Date: Wed, 11 Nov 1992 04:01:42 GMT orourke@sophia.smith.edu (Joseph O'Rourke) writes: >katkere@engin.umich.edu writes: >>I am looking for code/ideas for finding if two polyhedrons intersect. > >@article{CD >, author = "B. Chazelle and D. P. Dobkin" >, title = "Intersection of convex objects in two and three dimensions" >, journal = "J. ACM" >, volume = 34 >, year = 1987 >, pages = "1--27" >} But Joe...what if the polyhedra aren't convex? -- Kenneth Sloan Computer and Information Sciences sloan@cis.uab.edu University of Alabama at Birmingham (205) 934-2213 115A Campbell Hall, UAB Station (205) 934-5473 FAX Birmingham, AL 35294-1170 Newsgroups: comp.graphics From: sloan@cis.uab.edu (Kenneth Sloan) Subject: Re: polyhedron/polyhedron intersection Organization: CIS, University of Alabama at Birmingham Date: Wed, 11 Nov 1992 04:12:37 GMT In article <1992Nov11.002123.27579@kpc.com> hollasch@kpc.com (Steve Hollasch) writes: >katkere@engin.umich.edu writes: >| I am looking for code/ideas for finding if two polyhedrons intersect. >| I think that polygon/polygon intersection will be used as a building >| block for this. Is there a better way to do this? Can the sgi >| rendering engine be used in any way to do this? Where can I find >| code for polygon/polygon intersection? > > Polyhedron intersection has both trivial accept and trivial reject >conditions. Let P and Q be two polyhedra, and let Pc and Qc be some >arbitrary "center" of the polyhedron. Then let Prmin & Qrmin be the >minimum distance from the center to any of the vertices of the polyhedra, >and Prmax & Qrmax be the maximum distances from the polyhedra centers to any >vertex on the corresponding polyhedra. > > Trivial Reject: |Pc - Qc| > (Prmax + Qrmax) > > Trivial Accept: |Pc - Qc| < (Prmin + Qrmin) > > If neither of these tests succeed, then you must test each vertex of P >to see if it lies within Q, and then you have to test each vertex of Q to >determine if it lies within P. > > This is not all that simple for non-simple polyhedra (e.g. a torus), but >you may just be dealing with simple polyhedra anyway. Even for simple polyhedra, is it not possible for two polyhedra to intersect even though your Trivial Reject fails, your Trivial Accept fails, and no vertex lies INSIDE the other polyhedron? I believe that you must also test all edges for intersection with all faces of the other polyhedron or triangulate (tetrahedralize) and test all tetrahedra in one polyhedron against all tetrahedra in the other.. Testing vertices works for polygons - but polyhedra are tougher. -- Kenneth Sloan Computer and Information Sciences sloan@cis.uab.edu University of Alabama at Birmingham (205) 934-2213 115A Campbell Hall, UAB Station (205) 934-5473 FAX Birmingham, AL 35294-1170 Newsgroups: comp.graphics From: chuckb@stein.u.washington.edu (Charles Bass) Subject: Re: polyhedron/polyhedron intersection Organization: University of Washington Date: Wed, 11 Nov 1992 07:10:10 GMT I am using an algorithm developed at the University of Washington. It has been accepted for publication but as of today it is not known when it will be published. I use the routines to detect collisions between solid modeled objects in a real time simulation program. In general the routine has proven an improvement over our previous (n^2) routine. Some details: 1) It requires triangulated polygons. 2) It is well suited for checking collisions between moving objects (ones that don't overlap very much) 3) In practice the algorithm is very fast although the worst case looks to run in O((n^2)/2) time 4) Several "speed hacks" have been incorporated. These mostly are marginal but in the name of efficiency... (and less readable code ;-)) 5) Convex hull information can marginally speed the test. 6) I did *not* implement an engulfment test. I don't have details on this process but could possibly provide a ref. For details email me. Chuck Bass | College of Forest-Systems Engineering | University of Washington | FAX (206)-685-3091 Mailstop AR-10 | voice (206)-685-2198 Seattle, WA 98195 | email chuckb@u.washington.edu Newsgroups: comp.graphics From: orourke@sophia.smith.edu (Joseph O'Rourke) Subject: Re: polyhedron/polyhedron intersection Organization: Smith College, Northampton, MA, US Date: Wed, 11 Nov 1992 13:51:07 GMT hollasch@kpc.com (Steve Hollasch) writes: > ... Trivial Reject ... Trivial Accept ... > If neither of these tests succeed, then you must test each vertex of P >to see if it lies within Q, and then you have to test each vertex of Q to >determine if it lies within P. These tests are not sufficient to detect intersection, as two polyhedra may intersect without any vertex of one being inside the other. Newsgroups: comp.graphics From: orourke@sophia.smith.edu (Joseph O'Rourke) Subject: Re: polyhedron/polyhedron intersection Organization: Smith College, Northampton, MA, US Date: Wed, 11 Nov 1992 13:57:12 GMT sloan@cis.uab.edu (Kenneth Sloan) writes: >I believe that >you must also test all edges for intersection with all faces of the >other polyhedron ... Exactly. >Testing vertices works for polygons - ... Nope: +--+ | | | | +------------------+ | | | | +------------------+ | | | | +--+ Newsgroups: comp.graphics From: hollasch@kpc.com (Steve Hollasch) Subject: Re: polyhedron/polyhedron intersection Summary: Trivial accept and reject tests; a defense Organization: Kubota Pacific Computer, Inc. Date: Wed, 11 Nov 1992 19:34:39 GMT katkere@engin.umich.edu writes: | I am looking for code/ideas for finding if two polyhedrons intersect. hollasch@kpc.com (Steve Hollasch) writes: > Polyhedron intersection has both trivial accept and trivial reject > conditions. Let P and Q be two polyhedra, and let Pc and Qc be some > arbitrary "center" of the polyhedron. Then let Prmin & Qrmin be the > minimum distance from the center to any of the vertices of the polyhedra, > and Prmax & Qrmax be the maximum distances from the polyhedra centers to any > vertex on the corresponding polyhedra. > > Trivial Reject: |Pc - Qc| > (Prmax + Qrmax) > > Trivial Accept: |Pc - Qc| < (Prmin + Qrmin) > > If neither of these tests succeed, then you must test each vertex of P > to see if it lies within Q, and then you have to test each vertex of Q to > determine if it lies within P. sloan@cis.uab.edu (Kenneth Sloan) writes: | Even for simple polyhedra, is it not possible for two polyhedra to | intersect even though your Trivial Reject fails, your Trivial Accept | fails, and no vertex lies INSIDE the other polyhedron? I believe that | you must also test all edges for intersection with all faces of the | other polyhedron or triangulate (tetrahedralize) and test all tetrahedra | in one polyhedron against all tetrahedra in the other.. Testing | vertices works for polygons - but polyhedra are tougher. No, the trivial reject is sufficient. It's basically a test to see if the bounding spheres can intersect. If the bounding spheres cannot intersect, then the objects themselves cannot. The trivial accept doesn't work though. Not for the reason you mention, but because it doesn't properly handle concave polyhedra (e.g. a cylinder passing through the hole of a torus). If it's easy to break the polyhedron into convex components, then this test should work, provided that you are testing for volume (not just surface) intersection. This is because an object wholly enclosed in another object is an intersection of volumes but not of surfaces. With respect to rigorous (as opposed to trivial) intersection, I really just sort of kind of tossed out the vertex containment test without giving it a great deal of thought. I now agree that edge-face intersection must also be considered. In order to test this, I propose we hold a contest ... B^) ______________________________________________________________________________ Steve Hollasch Kubota Pacific Computer, Inc. hollasch@kpc.com Santa Clara, California Newsgroups: comp.graphics From: uselton@wk207.nas.nasa.gov (Samuel P. Uselton) Subject: Re: polyhedron/polyhedron intersection Organization: NAS, NASA Ames Research Center, Moffett Field, California Date: Wed, 11 Nov 92 18:59:59 GMT Summary: Hollasch's suggestion is not sufficient Polyhedra may intersect without either polyhedron containing any VERTICES of the other. Think about modeling a spike through a board. If they are both convex, things are relatively well understood and handled. But if either or both are non-convex, things rapidly get ugly. Detecting the existance of an intersection is easier than finding the intersection exactly. I addressed this problem a bit in my dissertation, around 1981. You can usually gain substantial speed-up in finding the intersection through the use of coherence. Once a single pair of intersecting polygon are found, one can follow the line of intersection until it closes back onto itself. The bad news is there can be O(n**2) separate polyhedra resulting from the intersection of two polyhedra. As an example, imagine a crude model of a hand, with a variable number of fingers, say j. My crude model of the hand uses 4j + 4 polygons. Take two such models and arrange them at 90 degrees, so that corresponding fingers interpenetrate. Now make the number of fingers, j, LARGE. YUK. Sam Uselton uselton@nas.nasa.gov employed by CSC working for NASA (Ames) speaking for myself From: dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) Newsgroups: comp.graphics Subject: Re: polyhedron/polyhedron intersection Date: 11 Nov 92 15:48:42 GMT Organization: U. S. Naval Academy In article <1992Nov11.040142.9570@cis.uab.edu> sloan@cis.uab.edu (Kenneth Sloan) writes: !In article <1992Nov10.221943.18792@sophia.smith.edu! orourke@sophia.smith.edu (Joseph O'Rourke) writes: !!In article <1992Nov10.192804.13981@zip.eecs.umich.edu! katkere@engin.umich.edu writes: !!!I am looking for code/ideas for finding if two polyhedrons intersect. !! !!@article{CD !!, author = "B. Chazelle and D. P. Dobkin" !!, title = "Intersection of convex objects in two and three dimensions" !!, journal = "J. ACM" !!, volume = 34 !!, year = 1987 !!, pages = "1--27" !!} ! !But Joe...what if the polyhedra aren't convex? Make them convex!! Dave Rogers From: dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) Newsgroups: comp.graphics Subject: Re: polyhedron/polyhedron intersection Date: 11 Nov 92 15:51:44 GMT Organization: U. S. Naval Academy In article <1992Nov11.135107.27052@sophia.smith.edu> orourke@sophia.smith.edu (Joseph O'Rourke) writes: !In article <1992Nov11.002123.27579@kpc.com! hollasch@kpc.com (Steve Hollasch) writes: !! ... Trivial Reject ... Trivial Accept ... !! If neither of these tests succeed, then you must test each vertex of P !!to see if it lies within Q, and then you have to test each vertex of Q to !!determine if it lies within P. ! ! These tests are not sufficient to detect intersection, as two !polyhedra may intersect without any vertex of one being inside the other. An example might help--either you or Ken Sloan. Dave Rogers From: spl@pitstop.ucsd.edu (Steve Lamont) Newsgroups: comp.graphics Subject: Re: polyhedron/polyhedron intersection Date: 12 Nov 92 00:23:51 GMT Article-I.D.: network.1ds86nINN5or Organization: University of Calif., San Diego/Microscopy and Imaging Resource In article <2371@usna.NAVY.MIL> dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) writes: >In article <1992Nov11.040142.9570@cis.uab.edu> sloan@cis.uab.edu (Kenneth Sloan) writes: >!But Joe...what if the polyhedra aren't convex? > >Make them convex!! All this reminds me of an old limerick: There once was a man from Racine Who built him a sex machine Concave or convex It could do either sex But, oh, what a mother to clean... Sorry. spl -- Steve Lamont, SciViGuy -- (619) 534-7968 -- spl@szechuan.ucsd.edu UCSD Microscopy and Imaging Resource/UCSD Med School/La Jolla, CA 92093-0608 "Far out, man" - President George Bush, heard in a stump speech on NPR Newsgroups: comp.graphics From: sloan@cis.uab.edu (Kenneth Sloan) Subject: Re: polyhedron/polyhedron intersection Organization: CIS, University of Alabama at Birmingham Date: Thu, 12 Nov 1992 01:19:52 GMT In article <2371@usna.NAVY.MIL> dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) writes: >In article <1992Nov11.040142.9570@cis.uab.edu> sloan@cis.uab.edu (Kenneth Sloan) writes: >!In article <1992Nov10.221943.18792@sophia.smith.edu! orourke@sophia.smith.edu (Joseph O'Rourke) writes: >!!In article <1992Nov10.192804.13981@zip.eecs.umich.edu! katkere@engin.umich.edu writes: >!!!I am looking for code/ideas for finding if two polyhedrons intersect. >!! >!!@article{CD >!!, author = "B. Chazelle and D. P. Dobkin" >!!, title = "Intersection of convex objects in two and three dimensions" >!!, journal = "J. ACM" >!!, volume = 34 >!!, year = 1987 >!!, pages = "1--27" >!!} >! >!But Joe...what if the polyhedra aren't convex? > >Make them convex!! Well, PROF Rogers, that may be the Navy way, but it's not the right way. It's not even the *wrong* way. Is it possible that someone on comp.graphics has finally posed a question which cannot be answered by citing an ISBN number? Here's a nice simple question to keep everyone occupied (sit down Joe - this one's not for you). GIVEN an arbitrary, simple polyhedron, P. FIND the largest (greatest volume) convex polyhedron completely contained in P. -- Kenneth Sloan Computer and Information Sciences sloan@cis.uab.edu University of Alabama at Birmingham (205) 934-2213 115A Campbell Hall, UAB Station (205) 934-5473 FAX Birmingham, AL 35294-1170 Newsgroups: comp.graphics From: sloan@cis.uab.edu (Kenneth Sloan) Subject: Re: polyhedron/polyhedron intersection Organization: CIS, University of Alabama at Birmingham Date: Thu, 12 Nov 1992 01:41:00 GMT In article <2372@usna.NAVY.MIL> dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) writes: >In article <1992Nov11.135107.27052@sophia.smith.edu> orourke@sophia.smith.edu (Joseph O'Rourke) writes: >!In article <1992Nov11.002123.27579@kpc.com! hollasch@kpc.com (Steve Hollasch) writes: >!! ... Trivial Reject ... Trivial Accept ... >!! If neither of these tests succeed, then you must test each vertex of P >!!to see if it lies within Q, and then you have to test each vertex of Q to >!!determine if it lies within P. >! >! These tests are not sufficient to detect intersection, as two >!polyhedra may intersect without any vertex of one being inside the other. > >An example might help--either you or Ken Sloan. > >Dave Rogers > The one I had in mind was, two tetrahedra T0, and T1, where T1 is simply a translated version of T0: T0: 0 0 0 T1: 0.7 0.7 -0.5 1 0 0 1.7 0.7 -0.5 0 1 0 0.7 1.7 -0.5 0 0 1 0.7 0.7 0.5 If my mental 3D modeller is working (always a chancy bet), none of the vertices of Ti are contained in Tj, yet the two tetrahedra intersect. If you have a set of blocks handy, pick up two and arrange them so that they contact in a single point, which happens to be at the midpoint of two edges (one edge of each block). Now push RealHard (but not TooHard). -- Kenneth Sloan Computer and Information Sciences sloan@cis.uab.edu University of Alabama at Birmingham (205) 934-2213 115A Campbell Hall, UAB Station (205) 934-5473 FAX Birmingham, AL 35294-1170 From: orourke@unix1.cs.umass.edu (Joseph O'Rourke) Newsgroups: comp.graphics Subject: Re: polyhedron/polyhedron intersection Date: 12 Nov 92 02:29:20 GMT Organization: Smith College, Northampton, MA, US In article <2372@usna.NAVY.MIL> dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) writes: >In article <1992Nov11.135107.27052@sophia.smith.edu> orourke@sophia.smith.edu (Joseph O'Rourke) writes: >!In article <1992Nov11.002123.27579@kpc.com! hollasch@kpc.com (Steve Hollasch) writes: >!! ... Trivial Reject ... Trivial Accept ... >!! If neither of these tests succeed, then you must test each vertex of P >!!to see if it lies within Q, and then you have to test each vertex of Q to >!!determine if it lies within P. >! >! These tests are not sufficient to detect intersection, as two >!polyhedra may intersect without any vertex of one being inside the other. > >An example might help--either you or Ken Sloan. Zeroth, neither Ken nor I are examples :-). First, the "Trivial Accept" test does not even work for convex polygons in the plane. For he defined it in terms of minimum distance from an interior point to a vertex: "Then let Prmin & Qrmin be the minimum distance from the center[s] to any of the vertices of the polyhedra, ... Trivial Accept: |Pc - Qc| < (Prmin + Qrmin)" Let P & Q be squares, Pc & Qc their centroids. Prmin & Qrmin are radii of circumscribing circles. The "Trivial Accept" condition tests for the intersection of these circles, which clearly does not imply the intersection of the squares. Second, Pc and Qc are arbitrary: "let Pc and Qc be ... arbitrary 'center[s]' of the polyhedr[a]." If Pc is very close to a vertex of P, them Prmin is a fairly meaningless quantity. Let P & Q be triangles, and choose Pc & Qc to be close to a vertex of each. Then the circles defined by Prmin and Qrmin are tiny, and it is easy to arrange the "Trivial Accept" rule to fail without any vertex of one triangle falling inside the other, and yet the triangles can intersect. I'd prefer not to draw this in ascii. If you need an explicit example, draw these two triangles: (0,0) (1,0) (0,10) (-1,0) (1,10) (2,10) Note that the failure of these ideas has nothing to do with nonconvexity or three-dimensionality, as some have suggested. Newsgroups: comp.graphics From: ledwards@leland.Stanford.EDU (Laurence James Edwards) Subject: Re: polyhedron/polyhedron intersection Organization: DSG, Stanford University, CA 94305, USA Date: Thu, 12 Nov 92 09:13:52 GMT In article <1992Nov12.011952.1154@cis.uab.edu>, sloan@cis.uab.edu (Kenneth Sloan) writes: |> [......] |> |> Here's a nice simple question to keep everyone occupied (sit down Joe - |> this one's not for you). |> |> GIVEN an arbitrary, simple polyhedron, P. |> |> FIND the largest (greatest volume) convex polyhedron completely |> contained in P. Interesting question ... well it would seem that you'd have to split the polyhedra with planes containing each concave edge. It would also seem that to maximize the volume the splitting plane would have to contain a face. So split the polyhedra up into convex pieces with two splitting planes at each concave edge, then find the combination of convex pieces that maximizes the volume and is convex. Not very efficient (and maybe not even correct) but, as usual, this is just off the top of my head. Larry Edwards Newsgroups: comp.graphics From: seitz@cs.wisc.edu (Steve Seitz) Subject: Re: polyhedron/polyhedron intersection Organization: U of Wisconsin CS Dept Date: Thu, 12 Nov 1992 16:11:17 GMT In article <1992Nov12.091352.5323@leland.Stanford.EDU>, ledwards@leland.Stanford.EDU (Laurence James Edwards) writes: |> In article <1992Nov12.011952.1154@cis.uab.edu>, sloan@cis.uab.edu (Kenneth Sloan) writes: |> |> [......] |> |> |> |> Here's a nice simple question to keep everyone occupied (sit down Joe - |> |> this one's not for you). |> |> |> |> GIVEN an arbitrary, simple polyhedron, P. |> |> |> |> FIND the largest (greatest volume) convex polyhedron completely |> |> contained in P. |> |> Interesting question ... well it would seem that you'd have to split the |> polyhedra with planes containing each concave edge. It would also seem that |> to maximize the volume the splitting plane would have to contain a face. |> So split the polyhedra up into convex pieces with two splitting planes |> at each concave edge, then find the combination of convex pieces that |> maximizes the volume and is convex. Not very efficient (and maybe not even |> correct) but, as usual, this is just off the top of my head. |> I don't think this will work in general (if I understand you correctly). Try it with this example: ____________________ | | | | minute sharp indentation --> > | | | |___________________| Imagine this in 3D by sweeping along the Z axis (through the screen). If I understand your suggestion, you'll get something like: ____________________ | / | | / | \/ | /\ | | \ | |__\________________| which is obviously suboptimal. The problem gets worse as the corner gets sharper, in the limit dividing the box in half. -Steve Seitz From: dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) Newsgroups: comp.graphics Subject: Re: polyhedron/polyhedron intersection Date: 12 Nov 92 15:55:35 GMT Organization: U. S. Naval Academy In article <1992Nov12.011952.1154@cis.uab.edu> sloan@cis.uab.edu (Kenneth Sloan) writes: !In article <2371@usna.NAVY.MIL! dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) writes: !!In article <1992Nov11.040142.9570@cis.uab.edu! sloan@cis.uab.edu (Kenneth Sloan) writes: !!!In article <1992Nov10.221943.18792@sophia.smith.edu! orourke@sophia.smith.edu (Joseph O'Rourke) writes: !!!!In article <1992Nov10.192804.13981@zip.eecs.umich.edu! katkere@engin.umich.edu writes: !!!!!I am looking for code/ideas for finding if two polyhedrons intersect. !!!! !!!!@article{CD !!!!, author = "B. Chazelle and D. P. Dobkin" !!!!, title = "Intersection of convex objects in two and three dimensions" !!!!, journal = "J. ACM" !!!!, volume = 34 !!!!, year = 1987 !!!!, pages = "1--27" !!!!} !!! !!!But Joe...what if the polyhedra aren't convex? !! !!Make them convex!! ! !Well, PROF Rogers, that may be the Navy way, but it's not the right way. !It's not even the *wrong* way. I don't know about the Navy way since I almost never do ANYTHING the Navy way, however please explain why it is NOT the RIGHT way and not even the WRONG way. !Is it possible that someone on comp.graphics has finally posed a !question which cannot be answered by citing an ISBN number? ! !Here's a nice simple question to keep everyone occupied (sit down Joe - !this one's not for you). ! !GIVEN an arbitrary, simple polyhedron, P. ! !FIND the largest (greatest volume) convex polyhedron completely !contained in P. It appears to me that this is a rather different problem than originally posed. In addition, please define exactly what a simple polyhedron is. Dave Rogers From: dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) Newsgroups: comp.graphics Subject: Re: polyhedron/polyhedron intersection Date: 12 Nov 92 15:59:12 GMT Organization: U. S. Naval Academy In article <56098@dime.cs.umass.edu> orourke@unix1.cs.umass.edu (Joseph O'Rourke) writes: !In article <2372@usna.NAVY.MIL! dfr@usna.navy.mil (PROF D. Rogers (EAS FAC)) writes: !!In article <1992Nov11.135107.27052@sophia.smith.edu! orourke@sophia.smith.edu (Joseph O'Rourke) writes: !!!In article <1992Nov11.002123.27579@kpc.com! hollasch@kpc.com (Steve Hollasch) writes: !!!! ... Trivial Reject ... Trivial Accept ... !!!! If neither of these tests succeed, then you must test each vertex of P !!!!to see if it lies within Q, and then you have to test each vertex of Q to !!!!determine if it lies within P. !!! !!! These tests are not sufficient to detect intersection, as two !!!polyhedra may intersect without any vertex of one being inside the other. !! !!An example might help--either you or Ken Sloan. ! !Zeroth, neither Ken nor I are examples :-). You and Ken are both certainly examples of SOMETHING :-}= (the curly and = are for the old wrinkled ones with beards :-}= ) ! !First, the "Trivial Accept" test does not even work for convex !polygons in the plane. For he defined it in terms of minimum distance !from an interior point to a vertex: ! ! "Then let Prmin & Qrmin be the minimum distance from the ! center[s] to any of the vertices of the polyhedra, ... ! Trivial Accept: |Pc - Qc| < (Prmin + Qrmin)" ! !Let P & Q be squares, Pc & Qc their centroids. Prmin & Qrmin are !radii of circumscribing circles. The "Trivial Accept" condition !tests for the intersection of these circles, which clearly does !not imply the intersection of the squares. ! !Second, Pc and Qc are arbitrary: "let Pc and Qc be ... arbitrary !'center[s]' of the polyhedr[a]." If Pc is very close to a vertex !of P, them Prmin is a fairly meaningless quantity. Let P & Q be !triangles, and choose Pc & Qc to be close to a vertex of each. !Then the circles defined by Prmin and Qrmin are tiny, and it is !easy to arrange the "Trivial Accept" rule to fail without any !vertex of one triangle falling inside the other, and yet the !triangles can intersect. I'd prefer not to draw this in ascii. !If you need an explicit example, draw these two triangles: ! ! (0,0) (1,0) (0,10) ! (-1,0) (1,10) (2,10) ! !Note that the failure of these ideas has nothing to do with !nonconvexity or three-dimensionality, as some have suggested. I didn't need and example but rather thought the net did. Thanks for providing same. Dave Rogers Article 571 of comp.graphics.algorithms: Newsgroups: comp.graphics.algorithms Path: kpc!news.kpc.com!decwrl!uunet!brunix!pmh From: pmh@cs.brown.edu (Philip M. Hubbard) Subject: Re: Distances Computation between Convex Polyhedra Message-ID: <1993Aug26.020604.9732@cs.brown.edu> Sender: news@cs.brown.edu Organization: Brown University Department of Computer Science References: <1993Aug20.193315.4283@cs.sfu.ca> <1993Aug20.213446.24249@kpc.com> <1993Aug21.013250.28987@sophia.smith.edu> Date: Thu, 26 Aug 1993 02:06:04 GMT Lines: 48 In article <1993Aug21.013250.28987@sophia.smith.edu> orourke@sophia.smith.edu (Joseph O'Rourke) writes: > I would add that if either polyhedron is convex, or if you know >that the polyhedra a separable by a plane, then asymptotic improvements >are possible. For example, the distance from a face of P2 to P1 >can be found in O(logn) time if P1 is convex. So this knocks down >the naive quadratic computation to O(nlogn) when one polyhedron is >convex. > The idea behind this speedup is to use a hierarchical representation >for the convex polyhedron, a nested collection of polyhedra with >several nice properties that permit certain queries to be performed >in logarithmic time. > Here is the best reference on this; it refers to all earlier >work. > >@inproceedings{Dobkin.Kirkpatrick >, author = "D. P. Dobkin and D. G. Kirkpatrick" >, title = "Determining the separation of preprocessed polyhedra -- a unified approach" >, booktitle = "Proc. 17th Internat. Colloq. Automata Lang. Program." >, series = "Lecture Notes in Computer Science" >, volume = 443 >, publisher = "Springer-Verlag" >, year = 1990 >, pages = "400--413" >} I have not read this paper, but there is a more recent one that claims better performance: Lin, Ming C. and John F. Canny, "A Fast Algorithm for Incremental Distance Calculation," Proceedings of the 1991 IEEE International Conference on Robotics and Automation, April 1991, pp. 1008-1014. The authors describe an algorithm that tracks the closest distance between two moving convex polyhedra. According to the abstract, "Data from numerous experiments tested on a broad set of convex polyhedra on R^3 shows that the running time is roughly CONSTANT for finding closest points when nearest points are approximately known and is linear in [the] total number of vertices if no special initialization is done." The key idea is that the closest points on the polyhedra at timestep t+1 are closely related to the closest points at timestep t, so little work is required to update the points. The algorithm is quite straight-forward and is probably not difficult to implement. ------------------------------------------------------------------------------- "I ain't broke but I'm badly bent." -- Willie Dixon Philip Martyn Hubbard: pmh@cs.brown.edu, pmh@browncs.bitnet, uunet!brunix!pmh