Nearest point on plane from point - Java-Games

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)

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;
}

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

Regards,
Eliott

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

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

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

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