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 ...

+ Reply to Thread
Results 1 to 8 of 8

Nearest point on plane from point

  1. Default 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.PN.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. Default 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. Default 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. Default Re: Nearest point on plane from point

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

    Regards,
    Eliott



  5. Default 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.PN.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. Default 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.PN.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. Default 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. Default 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

+ Reply to Thread

Similar Threads

  1. find nearest point
    By Application Development in forum Graphics
    Replies: 2
    Last Post: 11-20-2006, 03:07 AM
  2. Replies: 3
    Last Post: 09-18-2006, 02:55 AM
  3. nearest point to triangle,
    By Application Development in forum Graphics
    Replies: 1
    Last Post: 08-17-2006, 08:04 PM
  4. nearest point on box,
    By Application Development in forum Graphics
    Replies: 2
    Last Post: 08-13-2006, 03:18 PM
  5. Find the nearest point on GraphicsPath to a point ?
    By Application Development in forum DOTNET
    Replies: 4
    Last Post: 11-14-2005, 02:22 AM