From: WGERLT@ATL.dnet.ge.com Subject: RE: TECH: collision detection: so far... Date: Thu, 27 Feb 92 10:30:30 EST Hi Dave, At one point in your post, you mention taking the following steps to determine if two polyhedra intersect: 1. See if any of the vertices of P1 (polyhedron 1) are inside P2. 2. See if any of the edges of P1 intersect the polygons in P2. 3. Repeat, switching the roles of P1 and P2. This obviously isn't a *complete* description of what you're doing, but I'll offer some thoughts anyway. You've probably already considered most of these. Except for the case where P1 is completely inside P2, step 1 seems to be unnecessary if you do step 2. Maybe I'm missing something here? I wonder if there is a quick and dirty way of finding out whether one is completely inside another? Then you *could* skip step 1. Or perhaps the calculations in step 1 are easier than those in step 2? If you do step 1, you *could* stop as soon as you find that one vertex is outside P2. That would mean that some edges of P1 will intersect some polygons of P2, if there is any intersection at all. This would be caught be step 2. If you find one vertex is inside P2 and one is outside, then you know you have an intersection. If all you need to know is "is there an intersection?" as opposed to "what is the intersection?", then you can stop. I was recently writing some code to answer the "do they intersect?" question. I didn't really have speed of execution as a requirement, so I didn't worry a great deal about efficiency. I did add a couple of things that helped speed me up a bit. I used a preliminary bounding sphere test. I'm not sure this really helped that much, given that many of my objects were rather close together. I also used bounding circles for the polygons in the polyhedron. That allowed me to do an analogous check when I was checking for edge-polygon intersections. It could be that my edge-polygon intersection test was slow enough to start with that the bounding circle check was only a marginal improvement to a pretty bad method. The edge-polygon test was the heart of my code. I didn't do step 1 mentioned above, so I've got a bug (not detecting one polyhedron being completely inside the other). Basically my algorithm was something like: 1. Calculate the intersection of the line that contains the edge and the plane that contains the polygon. If no intersection, finished. 2. If the intersection point is not on the edge, finished - no intersection. 3. If the intersection point is not in the bounding circle for the polygon, finished - no intersection. I did step 2 before this step because step 2 is fairly trivial. 4. If the intersection point is in the bounding circle, then do the full point in polygon test and return the result. Most of this wasn't too bad, given that I pre-calculated the line, plane, and circle. I also had a pre-calculated point for each polygon that was in the plane of the polygon, but was outside the polygon. I used that in my point-in-polygon test (a variation of draw the line and see how many sides you intersect, trickier than it sounded at first). I didn't find much when I did a literature search either. Nor was I too successful finding any commercial software that would do the trick. I found a couple of references using the graf-bib-server@decwrl.dec.com. I also found out about a piece of software called TurboGraphics from a company called Disk Software (I think the names are correct). They sell lots of graphics/geometry type routines (several hundred, 2D and 3D) including documentation and source code. If you've got some bucks to spend (somewhere between $200 and $500 if I remember correctly), there might be some stuff to leverage in there. Bill wgerlt@atl.ge.com