home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: comp.graphics
- Path: sparky!uunet!sun-barr!ames!agate!stanford.edu!eos!data.nas.nasa.gov!wk207.nas.nasa.gov!uselton
- From: uselton@wk207.nas.nasa.gov (Samuel P. Uselton)
- Subject: Re: polyhedron/polyhedron intersection
- Keywords: 3d graphics, intersection
- References: <1992Nov10.192804.13981@zip.eecs.umich.edu> <1992Nov11.002123.27579@kpc.com>
- Sender: Sam Uselton
- Organization: NAS, NASA Ames Research Center, Moffett Field, California
- Date: Wed, 11 Nov 92 18:59:59 GMT
- Message-ID: <1992Nov11.185959.515@nas.nasa.gov>
- Summary: Hollasch's suggestion is not sufficient
- Lines: 22
-
-
- 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
-
-