Hi, I have posted this question before, but I have re-worded the problem so it’s a little clearer. First off, this is a real collision-response question, not some homework assignment or anything like that. Anyway, long story short, I end up with multiple planes, and a single point. I need to calculate the closest point to this point that lies on (or in front of) all planes. Another way: What is the SHORTEST vector to move the point by so that it is no longer behind any of the planes on the list? Now, there can be as few as 1 plane (easy case), or some undetermined maximum number of planes, possibly as high as 32. I did come up with a method to solve this, but it seems very inefficient, and would probably be very slow for more than a few planes. I hope someone can come up with a better way. Anyway, the solution I though up goes like this: Step 1) For each plane, do a bring-to-plane type operation to end up with a point that is on the plane (and closest to the original point). Now test this point against all other planes. If this point is behind any other plane, discard it and start the test with the next plane in the list. Each time a point is found that survives the above test, compare it to the previous result. If it’s closer to the original point than the previous one, this becomes the current candidate. If any point made the tests above, this is the final answer, and the closest point to the problem is on only one plane. Return this point as the final result Step 2) If no solution was found for the above, the point lies where two or more planes intersect. For each pair of planes that intersect, determine the intersection line. Extend this line to both directions by at least some amount that cannot be part of the solution. Now test this line against all remaining planes. If the line is completely behind any plane, discard the line and start with a new pair. If the line is “cut” by any plane, cut it so that both points are on or in front of the plane. If any line survived, do closest-point-to-line test, where the result can be one of the end-points, or any point on the line, whichever is closest. Check this point against all previous results, and only keep the one that’s closest to the original point. Anyway, that’s what I thought up so far. Anyone have a better solution, or at least one that’s faster? Thanks in advance. SS

First you have to eliminate redundant planes. A redundant plane is one which has no effect on the result under any scenerio. Two parallel planes are redundant since being in front of one means you are in front of the other. If it is the same plane it doesn''t matter which you get rid of, but otherwise one is behind the other and that is the one you get rid of. Second two planes intersect in a line and if that line lies in a plane parallel to a third plane and it is in front of the third plane and the two planes point away from the third plane then every point in front of the first two planes is in front of the third and the third plane can be discarded. Finally if three planes intersect in a point in front of a fourth plane and all three planes point away from the fourth plane then the fourth plane is redundant.

I think most of your optimization would have to be done through pre-processing. Specifically eliminating the redundant planes and then doing the following. Build a list of planes intersecting each plane. Each of those defines a line. Then find which other planes in that list intersect that line. Conceptually that creates rays. Some of those rays are sub-rays of other rays. Eliminate the rays for which another ray is a sub-ray. If you have two rays left then there are either points common to both, i.e. a line segment, or no points in common. If it is the later then the intersection with the original plane doesn''t matter since there is no point on both planes that is in front of all other planes. So for each plane you have a list of planes intersecting it and for each of those you have up to two other planes that also intersect it.

Now how you use that is you check the point against each plane. The worst case is that you are in front of all of them so you check every plane. Assuming you are behind at least one then find the point on the plane closest to your point. Then check that point against your list of planes that intersect it. If you are behind any of those then find the point on the line of intersection that is closest to your point. If the line of intersection intersects a third plane then check if you are behind that. If you are then the point at which the three planes intersect is your closest point. If not then if the line of intersection intersects a fourth plane then check if you are in front of that. If you are then you are done, if not then the closest point is the point where those three planes intersect.