• Advertisement
Sign in to follow this  

Closest point on a bounded plane

This topic is 2999 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Alright. I need to find the closest point on a bounded plane to a point in space. Currently I can find the distance from the plane to the point and the closest point on the infinite plane. I'm just having trouble when I get to a bounded quad on that plane. So I have a quad that's defined by a position vector (to the center of the quad) and u/v orthonormal vectors that define it's rotation (their cross product being the normal to the plane) and the width and length of the plane. I am really confused on the math I need to check the nearest point on the infinite plane to the nearest point on the quad or if the nearest point on the plane is equal to the one on the quad. Any light shed would be awesome! Normally I'd have a better idea, but I'm using one of my teacher's APIs, which is very confusingly written and aggravates me to no ends with the way it does vector math.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by jyk
Just went over this in some detail here.


vector3 local_point = rect.transform.world_to_local(query_point);

this was in that thread. I think that's the part I'm a little confused about. using the u/v vectors I have how do I convert to local coordinates?

Share this post


Link to post
Share on other sites
Quote:
Original post by way2lazy2care
Quote:
Original post by jyk
Just went over this in some detail here.


vector3 local_point = rect.transform.world_to_local(query_point);

this was in that thread. I think that's the part I'm a little confused about. using the u/v vectors I have how do I convert to local coordinates?


ok... I figured out how to convert it to the plane's coordinates, but I have no idea how to convert back to the world coordinates.

Share this post


Link to post
Share on other sites
Quote:
ok... I figured out how to convert it to the plane's coordinates, but I have no idea how to convert back to the world coordinates.
It'll just be the opposite of what you did to transform the point into the quad's local space. In matrix terms, the world-to-local transform would be effected by multiplying the point by the inverse of the quad's transform matrix, and the local-to-world transform would be effected by multiplying the point by the transform matrix itself.

If that doesn't give you enough info, perhaps you could post the code where you transform the point into the local space of the quad.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
ok... I figured out how to convert it to the plane's coordinates, but I have no idea how to convert back to the world coordinates.
It'll just be the opposite of what you did to transform the point into the quad's local space. In matrix terms, the world-to-local transform would be effected by multiplying the point by the inverse of the quad's transform matrix, and the local-to-world transform would be effected by multiplying the point by the transform matrix itself.

If that doesn't give you enough info, perhaps you could post the code where you transform the point into the local space of the quad.


oooo... I wasn't using a transform to get it there. Just shady maths. Since I have U and V ortho-normal vectors that live in the plane, and each one corresponds to either width or length of the plane, I was just finding the scaler along one of those and the scaler is the local coordinate.

I would like to do it using a transform matrix if you could shed a little light on that for me. I haven't done linear algebra outside of basic vector math in almost 2 years.

Share this post


Link to post
Share on other sites
I think I got it, I just need someone to check this for me.

Projecting the vector P onto a plane defined by a vector U(plane's local X) and a vector V(Plane's local Y).

So I get This

[Px][Ux Uy Uz] [LocalX]
[Py][Vx Vy Vz]= [LocalY]
[Pz]

does that look right to you? I think that might be with the plane centerred at the origin, so I might need to add the global position of the plane's origin?

It looks and sounds right to me. Now I just have to work on the inverse. Do I need to add a row like [0 0 0] to the transformation matrix so I can invert it?

edit:

it has come to my attention that the equation should be:
TRANSFORM*POSITION = LOCAL POSITION instead of:
POSITION*TRANSFORM = LOCAL POSITION

[Edited by - way2lazy2care on December 4, 2009 2:36:18 PM]

Share this post


Link to post
Share on other sites
I didn't follow your example (it's not a valid matrix multiplication, so I'm not sure what the intended result is), but here are a couple more bits of info.

If you think of your quad as having a center C and two basis vectors U and V, you can construct a matrix representing the transform as follows (I'll be using row-vector notation here, so adjust as necessary):
Let W = cross(U,V)

[ U.x U.y U.z 0 ]
[ V.x V.y V.z 0 ]
[ W.x W.y W.z 0 ]
[ C.x C.y C.z 1 ]
To find the inverse, just use a general matrix inversion function (any math library that deals with matrices will have one). You can actually optimize the inverse in this particular case, but I wouldn't bother unless you expect to be performing this operation a lot.

Now that we have our transform and its inverse, we can transform points into and out of local space like this:
local_point = world_point * inverse_transform
world_point = local_point * transform
Note that you will either need to use 4d homogeneous vectors here, or use a 'transform point' function of some sort (which many math libraries have).

You can also do it 'manually', like you were doing, with some simple vector arithmetic (addition/subtraction and a few dot products). I would recommend the matrix method instead though as it's a bit more general.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
I didn't follow your example (it's not a valid matrix multiplication, so I'm not sure what the intended result is), but here are a couple more bits of info.

If you think of your quad as having a center C and two basis vectors U and V, you can construct a matrix representing the transform as follows (I'll be using row-vector notation here, so adjust as necessary):
Let W = cross(U,V)

[ U.x U.y U.z 0 ]
[ V.x V.y V.z 0 ]
[ W.x W.y W.z 0 ]
[ C.x C.y C.z 1 ]
To find the inverse, just use a general matrix inversion function (any math library that deals with matrices will have one). You can actually optimize the inverse in this particular case, but I wouldn't bother unless you expect to be performing this operation a lot.

Now that we have our transform and its inverse, we can transform points into and out of local space like this:
local_point = world_point * inverse_transform
world_point = local_point * transform
Note that you will either need to use 4d homogeneous vectors here, or use a 'transform point' function of some sort (which many math libraries have).

You can also do it 'manually', like you were doing, with some simple vector arithmetic (addition/subtraction and a few dot products). I would recommend the matrix method instead though as it's a bit more general.


alright. I kind of follow. I'm a little confused though. You have a 4X4 transform and I'm looking for a 2 dimensional coordinate at the end. Wouldn't a 4 by 4 give me too many left over bits?

Also, part of the problem I'm having is that the library I'm using is made by the teacher, so it doesn't have all the things most libraries have.

Share this post


Link to post
Share on other sites
Quote:
alright. I kind of follow. I'm a little confused though. You have a 4X4 transform and I'm looking for a 2 dimensional coordinate at the end. Wouldn't a 4 by 4 give me too many left over bits?
It's actually a 3-d coordinate you're looking for. Imagine an arbitrarily oriented quad in 3-d space, and imagine a point somewhere on that quad. You'll most likely need non-zero x, y, and z elements to represent that point, right?

I'm guessing the reason you're thinking 2-d is that once the point is transformed into the local space of the quad and then clamped to the quad extents, the z element will end up being zero. However, this is incidental; immediately afterward you will transform this point back into world space and it will be a 'true' 3-d point again.

So in other words, there really are no 2-d points involved in this particular process - only a transitory 3-d point that happens to have a z value of zero.
Quote:
Also, part of the problem I'm having is that the library I'm using is made by the teacher, so it doesn't have all the things most libraries have.
The things you would need for this operation - matrix-vector multiplication, matrix inverse - are easy to find out about online. However, I'll go ahead and see if I can write out the 'longhand' version for you (no guarantee I'll get it right though):
// Transform world to local:
vector3 local = query_point - quad.center;
float x = dot(local, quad.U);
float y = dot(local, quad.V);

// Clamp (we skipped z because we know it'll end up being zero):
x = clamp(x, -quad.extents[0], quad.extents[0]);
y = clamp(y, -quad.extents[1], quad.extents[1]);

// Transform local to world:
vector3 world = quad.center + x * quad.U + y * quad.V;

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Let W = cross(U,V)

[ U.x U.y U.z 0 ]
[ V.x V.y V.z 0 ]
[ W.x W.y W.z 0 ]
[ C.x C.y C.z 1 ]


Sorry to bump again, but I had one more question about this. In your transform to local coordinates, why is there the Wx, Wy, Wz? wouldn't that give me a non-zero value for my z local coordinate?

That's the only thing I'm caught up on.

Share this post


Link to post
Share on other sites
Quote:
In your transform to local coordinates, why is there the Wx, Wy, Wz? wouldn't that give me a non-zero value for my z local coordinate?
Yes, you're likely to end up with a non-zero z value for the local coordinate. However, the very next step after that is to clamp the x, y, and z elements of the local coordinate to the corresponding extents of the rectangle. The z extent of the rectangle is 0, so you're clamping to [0, 0], which yields zero.

Since you know the z value is just going to get thrown away, you can actually ignore it and skip that part of the computation if you want (this is what the vector-based example I postest earlier does).

Share this post


Link to post
Share on other sites
Quote:
Original post by jykYes, you're likely to end up with a non-zero z value for the local coordinate. However, the very next step after that is to clamp the x, y, and z elements of the local coordinate to the corresponding extents of the rectangle. The z extent of the rectangle is 0, so you're clamping to [0, 0], which yields zero.

Since you know the z value is just going to get thrown away, you can actually ignore it and skip that part of the computation if you want (this is what the vector-based example I postest earlier does).


so what purpose do the W's serve? is it for the transform back to world coordinates?

Share this post


Link to post
Share on other sites
Quote:
Original post by way2lazy2care
Quote:
Original post by jykYes, you're likely to end up with a non-zero z value for the local coordinate. However, the very next step after that is to clamp the x, y, and z elements of the local coordinate to the corresponding extents of the rectangle. The z extent of the rectangle is 0, so you're clamping to [0, 0], which yields zero.

Since you know the z value is just going to get thrown away, you can actually ignore it and skip that part of the computation if you want (this is what the vector-based example I postest earlier does).


so what purpose do the W's serve? is it for the transform back to world coordinates?

Basically, yes, it exists to satisfy the rules of matrix multiplication and transformation. In order to perform the forward and inverse transforms you can't really "throw away" the third dimension entirely, but since the rectangle is coplanar with the local XY plane after the transformation you can set Z to 0. As a matter of fact, W could be any vector you want so long as the matrix remains invertible, since it only serves as a workhorse to help you perform the clamping in a more desirable space; it just so happens that cross(U,V) is the most convenient one to chose because it's guaranteed to satisfy the necessary conditions so long as U and V are valid.

Share this post


Link to post
Share on other sites
I think I worked it out in my head on the way home for class. I was thinking of just how I could get the point transformed to the 2D space, not the 3D space defined by the axes in that 2D space.

I was just super confused by that.

Now one more question. Is it more expensive to do it the long hand way or with matrix multiplication?

I think it might be better to do it with matrix multiplication for the first part, then use the long hand way to convert the point back to the world space. any insight?

Share this post


Link to post
Share on other sites
Quote:
Now one more question. Is it more expensive to do it the long hand way or with matrix multiplication?
Just compare the operations required by the 'longhand' method I posted earlier with the operations required by the matrix-based method, and make an estimate.

I'm guessing the 'longhand' way will be a little less expensive in general, but unless you're performing this operation many, many times per update (or are working on a platform with limited resources), it won't matter.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement