# Nearest point on plane from point - Java-Games

This is a discussion on Nearest point on plane from point - Java-Games ; Hi, [Sorry this post is quite big (but most of it's pseudo code)] I have a point and a plane and I need to find the nearest point on the plane to the point, so I search usenet and find ...

1. ## Nearest point on plane from point

Hi,

[Sorry this post is quite big (but most of it's pseudo code)]

I have a point and a plane and I need to find the nearest point on the plane
to the point, so I search usenet and find two possible solutions...

(where . means dot product)

[1] A=Q-((Q-P).N)N

[2] A=Q+(N.P–N.Q)N

A is my [x,y,z] answer
P is some known [x,y,z] point on the plane
Q is my [x,y,z] point in space away from the plane
N is the [x,y,z] normalised normal of the plane

....I've never really 'got' math - I know (or at least I've heard) that
1+1=2, but I don't know why, (why 2, why not 1.99999..) and formulas like
the above confuse me dearly, which is probably why I have been unable to get
either one to produce a happy result.

I've tried reading the usenet posts real carefully (they probably explain
what is going on (I don't understand)) and I got out my old school math
books and what not, but cannot figure out where I'm going wrong. Could
someone please tell me, (preferable without using math lingo), what in my
following pseudo code is the problem. Note, my plane is a triangle so I'm
using one of it vertices as my know point on the plane...

Function PointNearPlane(triangle, qx, qy, qz)
{
px = getvertex_x(triangle, 0) // 0 = The first vertex in the triangle
py = getvertex_y(triangle, 0)
pz = getvertex_z(triangle, 0)
nx = getnormal_x(triangle)
ny = getnormal_y(triangle)
nz = getnormal_z(triangle)
if method = 1 then // Using solution [1] as specified above
d = DotProduct(qx-px, qy-py, qz-pz, nx, ny, nz)
ax = qx-d*nx
ay = qy-d*ny
az = qz-d*nz
else if method = 2 then // or Using solution [2] as specified above
dp = DotProduct(px, py, pz, nx, ny, nz) // I know the formula above said
N.P (and this is P.N) but the N.P produced results off the chart for me
dq = DotProduct(qx, qy, qz, nx, ny, nz)
ax = qx+(dp-dq)*nx
ay = qy+(dp-dq)*ny
az = qz+(dp-dq)*nz
end if
PositionObject(testobject, ax, ay, az)
}
Function DotProduct(ux, uy, uz, vx, vy, vz)
{
ur = (ux^2+uy^2+uz^2)^0.5
vr = (ux^2+uy^2+uz^2)^0.5
Return Acos((ux*vx+uy*vy+uz*vz)/ur*vr)
}

....I'm absolutely-to-quite certain that the getvertex and getnormal parts in
the code are returning correct values so I haven't added their code. Anyway,
I've animated a rotating plane and tested against some point in space, and
the result is way off. I've been screwing around with these algorithms for a
day now, I don't know what I'm doing wrong. Can anyone help. Oh please do!

Thank you,
Regards,
Eliott

2. ## Re: Nearest point on plane from point

MRe wrote:
> dp = DotProduct(px, py, pz, nx, ny, nz) // I know the formula above said
> N.P (and this is P.N) but the N.P produced results off the chart for me

The dot product operation is commutative. It shouldn't matter what order
you put them into your dot product routine. Make sure your dot product
method is performing correctly.

If you input two unit length vectors 30 degrees apart, then the dot
product should be the cosine of 30 degrees.
(0.8660254, 0.5), (1.0, 0.0)

3. ## Re: Nearest point on plane from point

Sorry, I didn't read far enough:

> Function DotProduct(ux, uy, uz, vx, vy, vz)
> {
> ur = (ux^2+uy^2+uz^2)^0.5
> vr = (ux^2+uy^2+uz^2)^0.5
> Return Acos((ux*vx+uy*vy+uz*vz)/ur*vr)
> }

You are actually calculating the angle between the two vectors.
(Without a divide by zero protection, or range protection on the arc
cosine. Both can cause problems.)

the mathematical dot product is just:

Function DotProduct(ux, uy, uz, vx, vy, vz)
{
return ux*vx+uy*vy+uz*vz;
}

4. ## Re: Nearest point on plane from point

Ah! That's it - yeay. Thank you very much Matthew

Regards,
Eliott

5. ## Re: Nearest point on plane from point

MRe wrote:
> Hi,
>
> [Sorry this post is quite big (but most of it's pseudo code)]
>
> I have a point and a plane and I need to find the nearest point on the plane
> to the point, so I search usenet and find two possible solutions...
>
> (where . means dot product)
>
> [1] A=Q-((Q-P).N)N
>
> [2] A=Q+(N.P–N.Q)N
>
> A is my [x,y,z] answer
> P is some known [x,y,z] point on the plane
> Q is my [x,y,z] point in space away from the plane
> N is the [x,y,z] normalised normal of the plane
>

Hi Elliot,

I agree with Matt's replies but there is something else that bothers me
about the method you are using. Maybe I'm just being a little slow, but
I wanted to clarify. You want to find the point, A, in a *triangle* that
is closest to some arbitrary point in space, Q. If this is the case, I
don't think the formulae you are using work. They work for a *plane*,
i.e. an infinite flat thing, but I do not think they generally work for
a subset of a plane like a triangle.

The formulae above are mathematically equivalent. Basically, they tell
you how far you have to go in the direction of -N to reach the plane. So
you go from Q, in the direction of the normal towards the plane, until
you reach the plane, which will be the point A.

The problem is that A may not be in the triangle. Here's an example to
show you what I mean. Let's use the triangle with vertices
{(0,0,0),(1,0,0),(0,1,0)). Lets make the normal N = (0,0,1) and choose P
= (1,0,0). Now suppose Q = (2,1,1). Using equation [1] gives,

A = (2,1,1) - ((1,1,1).(0,0,1)) * (0,0,1),
= (2,1,1) - 1 * (0,0,1),
= (2,1,0).

A is not in the original triangle, but it does lie in the plane of the
triangle. Unfortunately, I think you're problem is going to require a
better solution than what you found. I don't know the solution off the
top of my head, but if this is the problem that you are trying to solve,
let me know and I'll try to figure something out.

-Josh

6. ## Re: Nearest point on plane from point

Josh wrote:
> MRe wrote:
>
>> Hi,
>>
>> [Sorry this post is quite big (but most of it's pseudo code)]
>>
>> I have a point and a plane and I need to find the nearest point on the
>> plane to the point, so I search usenet and find two possible solutions...
>>
>> (where . means dot product)
>>
>> [1] A=Q-((Q-P).N)N
>>
>> [2] A=Q+(N.P–N.Q)N
>>
>> A is my [x,y,z] answer
>> P is some known [x,y,z] point on the plane
>> Q is my [x,y,z] point in space away from the plane
>> N is the [x,y,z] normalised normal of the plane
>>

>
> Hi Elliot,
>
> I agree with Matt's replies but there is something else that bothers me
> about the method you are using. Maybe I'm just being a little slow, but
> I wanted to clarify. You want to find the point, A, in a *triangle* that
> is closest to some arbitrary point in space, Q. If this is the case, I
> don't think the formulae you are using work. They work for a *plane*,
> i.e. an infinite flat thing, but I do not think they generally work for
> a subset of a plane like a triangle.
>
> The formulae above are mathematically equivalent. Basically, they tell
> you how far you have to go in the direction of -N to reach the plane. So
> you go from Q, in the direction of the normal towards the plane, until
> you reach the plane, which will be the point A.
>
> The problem is that A may not be in the triangle. Here's an example to
> show you what I mean. Let's use the triangle with vertices
> {(0,0,0),(1,0,0),(0,1,0)). Lets make the normal N = (0,0,1) and choose P
> = (1,0,0). Now suppose Q = (2,1,1). Using equation [1] gives,
>
> A = (2,1,1) - ((1,1,1).(0,0,1)) * (0,0,1),
> = (2,1,1) - 1 * (0,0,1),
> = (2,1,0).
>
> A is not in the original triangle, but it does lie in the plane of the
> triangle. Unfortunately, I think you're problem is going to require a
> better solution than what you found. I don't know the solution off the
> top of my head, but if this is the problem that you are trying to solve,
> let me know and I'll try to figure something out.
>
> -Josh
>
>

Ah, how silly of me! If you use this method and find that A is outside
the triangle, then the closest point is going to be on one of the edges
of the triangle. So the problem becomes: (1) determine if the point is
inside the triangle, (2) which edge is A closest to, and (3) which point
along the closest edge is closest to A.

Maybe there is a more efficient way of calculating it, but that one way
of solving the problem.

-Josh

7. ## Re: Nearest point on plane from point

Hi Josh,

Thanking you for the response - I do just need to find the point on the
plane, don't care if it's inside the triangle (my problem wasn't that
exotic, it was actually quite... 'plane'. Hur, hur, hur. My sides!

Thanks again,
Regards
Eliott

8. ## Re: Nearest point on plane from point

Here's the answer, in C++:

//
// PointToPlane -- signed distance from a point to a plane
//
// Outside the plane yields positive values
//
inline double PointToPlane(const vec3& point, const vec4& plane)
{
vec3 planeNormal(plane[0],plane[1],plane[2]);
double dist = point * planeNormal + plane[3];
return(dist);
}

Source is at

http://www.animats.com/source/index.html

from which you need "algebra3.h" and "algebra3aux.h".

A plane is represented by a 4-element vector. The first three
elements are the plane normal (with length 1), and the last
element is the closest distance from the plane to the origin.

The other question, regarding the closest point in a triangle
to an external point, comes up all the time in collision detection
engines. It takes some case ****ysis, but it's straightforward.

Closest distance between two convex meshes can be done incredibly
fast. Look up "GJK".

John Nagle
Animats