I''m coding a simple game and I''ve run into a problem: I need to find the nearest point on a rectangular prism to a point in space. If I have a prism defined by 3 vectors, v1,v2,v3 ,and a point, p1,p2,p3, one crappy way of doing it is to calculate the distance between my point and every plane of the prism and pick the point that gives me the shortest. But what if the solution is outside the prism? Someone told me that picking the nearest vertex will then be the nearest point, but I think it''s false. In this case I could work with every line of the prism, but is there a cleaner and more efficient way of solving the entire problem...?

I once had to write an algorithm to find the closest distance between two convex polyhedra. I used a method I called "side projection". In the context of your situation, the first step was to do the basic point-vertex check, seeing how far the point was from each point on the polygon, and storing the minimum distance. What we did next was take each face on the polygon, find it''s boundaries, and then use those boundaries to define planes that lie perpendicular to the surface. Basically, these planes would now bound the face. When we then do is check to see which on of these boundaries the point lies within, and once we find that boundary, we find the points distance from the face associated with those boundaries. This is why the initial point-vertex check is necessary, because the point may not lie within any of these boundaries, in which case it is closest to a vertex of the polygon.

My host is down at the moment so I can''t upload the picture that goes along with that description, so if you need it let me know and I''ll try again later.

Zipster, the method you''re describing does not work, because you''re not handling the case of the point being closest to an edge of the polyhedron (not a vertex, and not a face). I.e. when the point does not lie inside a face Voronoi region (the face Voronoi region being the volume formed by the face and the perpendicular edge boundaries you erect) it doesn''t have to be in a vertex Voronoi region -- it may in fact lie in an edge Voronoi region. You have to handle all three kinds of regions to get a correct result.

Christer Ericson
Sony Computer Entertainment, Santa Monica

my solution would be you calculate the distancs point-to-plane

and check whether the projection of the point onto the plane lies within the polygon if so you have found the shortest distance


if it doesn you could do a sphere-to-edge test for every edge to find out the shortest distance between point and edge

do this for every edge and take the shortest distance of all

Yeah I thought I had the problem solved using a method similar to Zipster''s but as Christer Ericson pointed out (in clearer terms than I could have), the nearest point can be on an edge. Sorry to ask, but what''s a sphere-to-edge test? I know from my basic math classes how to calculate the distance between a point and a line, but edges have boundaries and I''m not sure how to work with that.

A way to do it initially is to calculate the equations of the planes in which each of the faces is contained. Then, you can do distance from point to a plane simply enough by computing the value of abs(Ax + By + Cz + D/sqrt(A^2 + b^2 + c^2). You can get this point by projecting the point onto the plane using the normal vector. Do this for each point. Starting with the plane closest to the point, check to see whether the projection point (point on the plane where a orthogonal line would intersect it going through the known point) is within the polygon. If it is, then you have your nearest point. Iterate through this process until you come across a projection point within the plane, which is your answer. Maybe this isn''t right, but its my shot at the problem.

Brendan

quote:

---

by Punty50

Do this for each point.
(...)
Iterate through this process until you come across a projection point within the plane, which is your answer.

---

Are you saying I should calculate the distance with every point of the nearest plane? I''m using double type coordinates, but even if I used integers, it could get ugly with large objects.
Maybe I got it wrong though, I''m not very good at this.

quote:

---

Zipster, the method you're describing does not work, because you're not handling the case of the point being closest to an edge of the polyhedron (not a vertex, and not a face). I.e. when the point does not lie inside a face Voronoi region (the face Voronoi region being the volume formed by the face and the perpendicular edge boundaries you erect) it doesn't have to be in a vertex Voronoi region -- it may in fact lie in an edge Voronoi region. You have to handle all three kinds of regions to get a correct result.

---

I suppose that's correct. The original algorithm was for checking the distance between convex polyhedra, and given those circumstances it wasn't necessary to calculate the exact distance, just a rough estimate, so that case could be disregarded and a vertex could be used instead, which would generate slightly larger distance, but that was OK. I guess it's not easily adapted

EDIT: Or, maybe just add a point-edge check in addition to the point-vertex check?

[edited by - Zipster on January 14, 2003 9:51:25 PM]

Here''s a method I just made up:

Find the distance of your point from each plane that forms the rectangular prism. The distance to the prism will depend on the number of calculated distances that are positive.

3 positives: The distance from your point to the vertex shared by the 3 planes with positive values

2 positives: The shortest distance from your point to the line shared by the 2 positive planes.

1 positive: The distance to that one positive plane

0 positives: The point is inside the prism

quote:

---

Original post by Seifer
Yeah I thought I had the problem solved using a method similar to Zipster''s but as Christer Ericson pointed out (in clearer terms than I could have), the nearest point can be on an edge. Sorry to ask, but what''s a sphere-to-edge test? I know from my basic math classes how to calculate the distance between a point and a line, but edges have boundaries and I''m not sure how to work with that.

---

you have 2 vertices which determine 1 edge

vertex1-vertex2 =edge

don t normalize the edge vector

now you have the equation x=vertex2+alpha*edge


now make a for loop
with floats

M the origin of the sphere in your case it is your point

d=current distance between d and the point
dsmallest= smallest distance we got til now

for(float i= 0;i<=1;i+=0.1)//for a precision of 0.1 take a smaller value for more precision
{
d=length(m-vertex2+i*edge);
if(ddsmallest=d;
}

that should work and you can determine your own precision

if you are using a lot of difference sized edges you should insert a little check for small, medium and large edges and apply a good value to gaurantee the precision for long edges

i hope that helps instead of testing each edge you could determine which end vertices of an edge are nearest to the sphere and only test those with the loop

so far so good
that should work fine