# Distance to bezier surface

## Recommended Posts

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

##### Share on other sites
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.

##### Share on other sites
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..

##### Share on other sites
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

##### Share on other sites
(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.

##### Share on other sites
Quote:
 Original post by arithmaLet the bezier by a function (f(u,v)) returning a point for two parametersLet P be the point of interestCalculate Analytically Distance from f(u,v) to PYou 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)

##### Share on other sites
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)

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628356
• Total Posts
2982253

• 10
• 9
• 13
• 24
• 11