Distance to bezier surface

a simple method:

recursively subdivide your patch, culling away all parts that are guaranteed not to contain the closest point.

easy to implement, and very stable. however i hope performance isnt too big an issue. :).


otherwise you might take a look at bezier clipping. its usually used for raytracing, but it can be adapted to solve about any geometric problem involving beziers.

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)