Hi I've got a project and it requires that I figure out a decent way to determine the (u, v) for the closest point on a bezier surface to any given point in space. An idea that I'm working on: The points on the surface that are going to be the closest are going to be either a point on one of the edges or an internal point who's normal is collinear with the direction from the surface to the given point. This seems correct to me. So I thought I would see how far I could take that idea analytically. I got this equation: du * ( p - o ) + dv * ( p - o ) = 0 Where du and dv are the partial derivatives of the surface, p is the point on the surface and o is the given point in space. If I expand this I get a cubic equation of two variables (surprise) which looks impossible to solve. Am I on the right track here? I do not want to just tesselate the patch and consider each point but I can't think of any other ideas. Sorry for the long post Any help is much appreciated

Performance is a bit of an issue but that's a lot better than just brute force, so thanks

I will look into bezier clipping..

Let the bezier by a function (f(u,v)) returning a point for two parameters
Let P be the point of interest

Calculate Analytically Distance from f(u,v) to P
You can apply a square on both sides of the equation if that simplifies the equation.

the distance (and u and v) are determined by solving for the partial derivatives with respect to u and v are equal to zero.

If there are generally more than one solution, you can compare them...

For the edges, you can similarly fix u or v then differentiate over the other parameter and solving for zero...
More than one solution are handled similarly

If more help is needed, don't hesitate

(No school for four weeks, might have an error or two)

You can also solve (u,v) for the ray starting at f(u,v) pointing in the direction of the normal at the same point, which crosses P
This is because the line from the closest point to P is perpendicular to the surface.

so f(u,v) + normal(f'(u,v))*t = P for some values of u, v and t. Probably more complicated then other suggested methods. Or not. Try it.

Quote:Original post by arithma
Let the bezier by a function (f(u,v)) returning a point for two parameters
Let P be the point of interest

Calculate Analytically Distance from f(u,v) to P
You can apply a square on both sides of the equation if that simplifies the equation.

Ok, I'm with you so far

Quote:
the distance (and u and v) are determined by solving for the partial derivatives with respect to u and v are equal to zero.

If there are generally more than one solution, you can compare them...

I'm not sure what you mean here. I think the distance equation you mentioned will be a function of two variables, both variables having a max exponent of 3. I'm not sure how to solve something like that.

Btw, I implemented Eelco's solution (thx again) and it seems to work pretty well, but like I said performance is an issue so if there is an analytical/better solution I'd definately give it a shot

The deadline for my project is in less than a week however so I won't be able to investigate your suggestion until after that

(The project involves creating a voxel field around a bezier surface)

Let's investigate a simpler example and you can build it up with analogies..

Plane of elements:
Point: P(x0,y0,z0)
Tangent1: T1(u1,v1,w1)
Tangent2: T2(u2,v2,w2)

f(u,v) = P + T1*u + T2*v

To calculate the distance from a point M(x,y,z) we can:

Solve for u and v for minimum distance from M to f(u,v)
M to f(u,v) squared could also be used instead (to get rid of the radicals)
distance^2 = (x-x0-u1*u-u2*v)^2+(y-y0-v1*u-v2*v)^2+(z-z0-w1*u-w2*v)^2

now for the partial derivative you can assume all values other than u to be constant and derive with respect to u. You can repeat the same operation but with v instead. u and v become the the solution of both results equated to zero. eg:

0 = 2*(x-x0-u1*u-u2*v)*(-u1)+2*(y-y0-v1*u-v2*v)*(-v1)+(z-z0-w1*u-w2*v)*(-w1)
0 = 2*(x-x0-u1*u-u2*v)*(-u2)+2*(y-y0-v1*u-v2*v)*(-v2)+(z-z0-w1*u-w2*v)*(-w2)

this system of equations is linear (not the case in bezier)
Moreover, appling this method will return all extrema of the distance (including local maxia). So you must compare them to get a respectable result.

[edit1]
This method is fast (if you can solve the system of equations) and is exact (at least to the precision of your system). If you can't solve the evolved system you should try numerical methods (of which am not currently a good reference)

[edit2]
If the solution is not found analytically, you should investigate whether using the numerical method is faster or not compared to the tesselation (which seems to me as a decent method for finding the desired distance)

See also this article which solves the problem of distance from a point to bezier curve in 2D space (http://www.tinaja.com/glib/bezdist.pdf)