Started by May 11 2003 12:46 AM

,
13 replies to this topic

Posted 11 May 2003 - 12:46 AM

Does anyone know if it's possible to find a scalar value that gives an indication of the curvature of a Bezier for a given t value along the curve? All the documentation that I've found uses the rate of change of the curve's tangent to approximate how "bendy" the Bezier is. This isn't really good enough as, even for perfectly straight curves, a tangent's length can vary quite dramatically.
Ideally, what I'd like is an equation that describes the rate of change of the normalised tangent of a Bezier. Unfortunately, my maths is nowhere near good enough to work this out.
Any help would be greatly appreciated.
[edited by - tomm on May 14, 2003 6:32:29 AM]

Posted 11 May 2003 - 04:52 AM

I don't know what's the "right" way to do it, but I would use:

b = |f ' '(t) cross f '(t)| / |f '(t)|

That way, straight lines would have b = 0.

I hope that the notation is clear. For reference, |x| is the norm of x, and "cross" is the cross product. f ' '(t) and f '(t) are the derivatives, of course.

Cédric

EDIT, for some reasons, I can't put two apostrophes ' one beside another.

[edited by - cedricl on May 11, 2003 11:56:30 AM]

b = |f ' '(t) cross f '(t)| / |f '(t)|

That way, straight lines would have b = 0.

I hope that the notation is clear. For reference, |x| is the norm of x, and "cross" is the cross product. f ' '(t) and f '(t) are the derivatives, of course.

Cédric

EDIT, for some reasons, I can't put two apostrophes ' one beside another.

[edited by - cedricl on May 11, 2003 11:56:30 AM]

Posted 11 May 2003 - 06:28 AM

The equation for curvature is the magnitude of dT/ds, the rate of change of the unit tangent vector with respect to the arclength.

How do you find T? The equation for the tangent vector is v/|v|, where v is dr/dt, with r the position function.

So you have T. Now, notice this: dT/ds = dT/dt*dt/ds from the chain rule.

Finding dT/dt is easy, the hard part is finding dt/ds. dt/ds is 1/(ds/dt), and ds/dt is the speed, the magnitude of the velocity.

So, to find k, the curvature, as a function of t, do this:

(dr/dt)/(|dr/dt|)=T

|(dT/dt)*(1/|dr/dt|)|=k

Hope that helped.

How do you find T? The equation for the tangent vector is v/|v|, where v is dr/dt, with r the position function.

So you have T. Now, notice this: dT/ds = dT/dt*dt/ds from the chain rule.

Finding dT/dt is easy, the hard part is finding dt/ds. dt/ds is 1/(ds/dt), and ds/dt is the speed, the magnitude of the velocity.

So, to find k, the curvature, as a function of t, do this:

(dr/dt)/(|dr/dt|)=T

|(dT/dt)*(1/|dr/dt|)|=k

Hope that helped.

Posted 11 May 2003 - 11:17 PM

Hi there,

Thanks for replying. Unfortunately I''ve let my maths get rusty over the years and don''t know how to find dT/dt. Sorry for being dense, but I''ve made a couple of attempts and just got horribly confused. Am I missing something?

Thanks for replying. Unfortunately I''ve let my maths get rusty over the years and don''t know how to find dT/dt. Sorry for being dense, but I''ve made a couple of attempts and just got horribly confused. Am I missing something?

Posted 12 May 2003 - 12:16 AM

No, because the second derivative considers both the change in the tangent''s direction AND its length. If you consider a Bezier curve which has zero (or at least very small) tangent vectors at its end points, that''ll give you a pretty much straight line, but the second derivative will be necessarily non-zero along the curve. Consider the following straight Bezier sampled at regular intervals (where the * characters are the sampled points):

*.*..*...*....*...*..*.*

I hope you can see that although the tangent direction never changes, its length does, and this affects the second derivative.

*.*..*...*....*...*..*.*

I hope you can see that although the tangent direction never changes, its length does, and this affects the second derivative.

Posted 12 May 2003 - 11:11 AM

tomm is right. The second derivative is NOT the curvature. tomm, do you know how to find derivatives in general? (not meant to be sarcastic) If you do, I can help you understand how to get dT/dt, but if not, then you should just check out a calculus book, because derivatives are really easy.

If you do know derivatives, and the equations are just confusing you, here''s an example. It''s two-dimensional, but extending to three dimensions is ridiculously easy.

r(t) = [t, t^2] ---- get some vector function.

v(t) = [1, 2t] ---- take the derivative.

|v(t)| = sqrt(1+4t^2) ---- find the length of the vector as a function of t. this is just the pythagorean theorem.

T = v/|v| = [1/sqrt(1+4t^2), 2t/sqrt(1+4t^2)] ---- this is T, since any vector divided by its length is unit vector, and v is always in the direction of travel.

dT/dt = [-4t/(1+4t^2)^(3/2), 2/(1+4t^2)^(3/2)] ---- just use the quotient rule and the chain rule a lot.

dT/dt*(1/|dr/dt|) = [-4t/(1+4t^2)^2, 2/(1+4t^2)^2] ---- pretty simple. dr/dt = v, of course, which we have up there.

|dT/dt*(1/|dr/dt|)|= 2/(4t^2+1)^(3/2) ---- the length of that last vector we found. simple algebra again.

So there you have it. The curvature of a vector function in terms of t. If you use a general function, r(t) = [x(t), y(t), z(t)], you can get a general expression for curvature, and then you can figure out how to get the curvature in terms of your control point coordinates. But that''s your job.

If you do know derivatives, and the equations are just confusing you, here''s an example. It''s two-dimensional, but extending to three dimensions is ridiculously easy.

r(t) = [t, t^2] ---- get some vector function.

v(t) = [1, 2t] ---- take the derivative.

|v(t)| = sqrt(1+4t^2) ---- find the length of the vector as a function of t. this is just the pythagorean theorem.

T = v/|v| = [1/sqrt(1+4t^2), 2t/sqrt(1+4t^2)] ---- this is T, since any vector divided by its length is unit vector, and v is always in the direction of travel.

dT/dt = [-4t/(1+4t^2)^(3/2), 2/(1+4t^2)^(3/2)] ---- just use the quotient rule and the chain rule a lot.

dT/dt*(1/|dr/dt|) = [-4t/(1+4t^2)^2, 2/(1+4t^2)^2] ---- pretty simple. dr/dt = v, of course, which we have up there.

|dT/dt*(1/|dr/dt|)|= 2/(4t^2+1)^(3/2) ---- the length of that last vector we found. simple algebra again.

So there you have it. The curvature of a vector function in terms of t. If you use a general function, r(t) = [x(t), y(t), z(t)], you can get a general expression for curvature, and then you can figure out how to get the curvature in terms of your control point coordinates. But that''s your job.

Posted 13 May 2003 - 03:25 AM

Thanks for all your help vanillacoke, it''s been increadibly useful, The difficulty that I''m having with this problem is that I''ve forgotten all the rules of differentiation in the 6 years since I was taught it. I''ve (hopefully) got to grips with it now and made a few attempts to solve the problem, unfortunately I don''t seem to be getting the correct results. What I''ve got so far is this:

Let a, b, c, d vectors such that:

r = a*t^3 + b*t^2 + c*t + d

v = r''

v = 3*a*t^2 + 2*b*t + c

I split v into it''s (x, y, z) components such that:

x = 3*a.x*t^2 + 2*b.x*t + c.x

y = 3*a.y*t^2 + 2*b.y*t + c.y

z = 3*a.z*t^2 + 2*b.z*t + c.z

|v| = sqrt(x^2 + y^2 + z^2)

T = v / |v|

T'' = (v''*|v| - v*|v|'') / |v|^2

v'' = 6*a*t + 2*b

|v|'' = (1/sqrt(x^2 + y^2 + z^2)) * ((x^2)'' + (y^2)'' + (z^2)'')

|v|'' = ((x^2)'' + (y^2)'' + (z^2)'') / |v|

(x^2)'' = 2*(3*a.x*t^2 + 2*b.x*t + c.x) * (6*a.x*t + 2*b.x)

(y^2)'' = 2*(3*a.y*t^2 + 2*b.y*t + c.y) * (6*a.y*t + 2*b.y)

(z^2)'' = 2*(3*a.z*t^2 + 2*b.z*t + c.z) * (6*a.z*t + 2*b.z)

With this information I can easily get dT/ds, but like I said, the result don''t seem to be correct. Can anyone see what I''m doing wrong?

Let a, b, c, d vectors such that:

r = a*t^3 + b*t^2 + c*t + d

v = r''

v = 3*a*t^2 + 2*b*t + c

I split v into it''s (x, y, z) components such that:

x = 3*a.x*t^2 + 2*b.x*t + c.x

y = 3*a.y*t^2 + 2*b.y*t + c.y

z = 3*a.z*t^2 + 2*b.z*t + c.z

|v| = sqrt(x^2 + y^2 + z^2)

T = v / |v|

T'' = (v''*|v| - v*|v|'') / |v|^2

v'' = 6*a*t + 2*b

|v|'' = (1/sqrt(x^2 + y^2 + z^2)) * ((x^2)'' + (y^2)'' + (z^2)'')

|v|'' = ((x^2)'' + (y^2)'' + (z^2)'') / |v|

(x^2)'' = 2*(3*a.x*t^2 + 2*b.x*t + c.x) * (6*a.x*t + 2*b.x)

(y^2)'' = 2*(3*a.y*t^2 + 2*b.y*t + c.y) * (6*a.y*t + 2*b.y)

(z^2)'' = 2*(3*a.z*t^2 + 2*b.z*t + c.z) * (6*a.z*t + 2*b.z)

With this information I can easily get dT/ds, but like I said, the result don''t seem to be correct. Can anyone see what I''m doing wrong?

Posted 13 May 2003 - 09:30 AM

|v|' = ((x^2)' + (y^2)' + (z^2)') / |v| <--- the [x,y,z] here is r(t)

(x^2)' = 2*(3*a.x*t^2 + 2*b.x*t + c.x) * (6*a.x*t + 2*b.x)

(y^2)' = 2*(3*a.y*t^2 + 2*b.y*t + c.y) * (6*a.y*t + 2*b.y)

(z^2)' = 2*(3*a.z*t^2 + 2*b.z*t + c.z) * (6*a.z*t + 2*b.z)

^-- there, they are v(t)

also, I think I noticed a few coefficients that were wrong, but that looks like the biggest problem. The best way to not make mistakes like that is to make sure everything is named correctly and comprehensively, so you should do this:

v.x = 3*a.x*t^2 + 2*b.x*t + c.x

v.y = 3*a.y*t^2 + 2*b.y*t + c.y

v.z = 3*a.z*t^2 + 2*b.z*t + c.z

instead of this:

x = 3*a.x*t^2 + 2*b.x*t + c.x

y = 3*a.y*t^2 + 2*b.y*t + c.y

z = 3*a.z*t^2 + 2*b.z*t + c.z

until you're completely sure that you can keep the variables straight in your head.

Do the last part of that problem again, and I'll do it too, and hopefully we'll get the same answer.

edit: actually, no I think those are correct, but I think the problem is still in the naming. I don't have time right now to go through the whole problem, but I will in about an hour. Post your solution k(t) (that's curvature), in terms of all the coefficients, and then we'll see.

[edited by - vanillacoke on May 13, 2003 4:32:58 PM]

(x^2)' = 2*(3*a.x*t^2 + 2*b.x*t + c.x) * (6*a.x*t + 2*b.x)

(y^2)' = 2*(3*a.y*t^2 + 2*b.y*t + c.y) * (6*a.y*t + 2*b.y)

(z^2)' = 2*(3*a.z*t^2 + 2*b.z*t + c.z) * (6*a.z*t + 2*b.z)

^-- there, they are v(t)

also, I think I noticed a few coefficients that were wrong, but that looks like the biggest problem. The best way to not make mistakes like that is to make sure everything is named correctly and comprehensively, so you should do this:

v.x = 3*a.x*t^2 + 2*b.x*t + c.x

v.y = 3*a.y*t^2 + 2*b.y*t + c.y

v.z = 3*a.z*t^2 + 2*b.z*t + c.z

instead of this:

x = 3*a.x*t^2 + 2*b.x*t + c.x

y = 3*a.y*t^2 + 2*b.y*t + c.y

z = 3*a.z*t^2 + 2*b.z*t + c.z

until you're completely sure that you can keep the variables straight in your head.

Do the last part of that problem again, and I'll do it too, and hopefully we'll get the same answer.

edit: actually, no I think those are correct, but I think the problem is still in the naming. I don't have time right now to go through the whole problem, but I will in about an hour. Post your solution k(t) (that's curvature), in terms of all the coefficients, and then we'll see.

[edited by - vanillacoke on May 13, 2003 4:32:58 PM]

Posted 13 May 2003 - 05:55 PM

Okay, I did a bunch of stupid work & here''s my answer: There is no expression for k(t) solely in terms of r and its derivatives when r is a 3D vector. What I mean is, the way I would find k would be to just write out the entire equation each step, instead of writing things like |v| and such. Or write a program to it for me, which I did.

BTW, what do you need curvature of a bezier for? I''m sure that the exact expression will be really complex, and there is a much simpler expression for centripetal acceleration, which might be useful

BTW, what do you need curvature of a bezier for? I''m sure that the exact expression will be really complex, and there is a much simpler expression for centripetal acceleration, which might be useful

Posted 13 May 2003 - 11:32 PM

I''ve finally managed to solve the problem, it turns out there was an error in the way I calculated |v|'', I was forgetting to divide by 2 when differentiating the square root:

Incorrect equation:

|v|'' = ((v.x^2)'' + (v.y^2)'' + (v.z^2)'') / |v|

Corrected equation:

|v|'' = ((v.x^2)'' + (v.y^2)'' + (v.z^2)'') / (2*|v|)

Everything works just great now.

In the game I''m working on (which I can''t really talk too much about), I have a large number of objects that need to move at a constant speed along Bezier strips. To reduce the number of times I need to sample the curve I split the Beziers into a number of line segments, which are faster to evaluate. Obviously, the lower the curvature of the Bezier, the fewer line segments are needed to represent within some margin of error. Initially I was looking for a good measure of curvature instead of just using a rough heuristic, but in the end the problem started really bugging me and I just had to get it solved.

Thanks for all your help, it realy was greatly appreciated.

Incorrect equation:

|v|'' = ((v.x^2)'' + (v.y^2)'' + (v.z^2)'') / |v|

Corrected equation:

|v|'' = ((v.x^2)'' + (v.y^2)'' + (v.z^2)'') / (2*|v|)

Everything works just great now.

In the game I''m working on (which I can''t really talk too much about), I have a large number of objects that need to move at a constant speed along Bezier strips. To reduce the number of times I need to sample the curve I split the Beziers into a number of line segments, which are faster to evaluate. Obviously, the lower the curvature of the Bezier, the fewer line segments are needed to represent within some margin of error. Initially I was looking for a good measure of curvature instead of just using a rough heuristic, but in the end the problem started really bugging me and I just had to get it solved.

Thanks for all your help, it realy was greatly appreciated.

Posted 14 May 2003 - 12:11 AM

I spent a couple of minutes simplifying the equations and the solution turns out to be quite elegant:

dT/ds = (v'' / |v|^2) - (v * (v.v'') / |v|^4)

dT/ds = (v'' / |v|^2) - (v * (v.v'') / |v|^4)

Posted 14 May 2003 - 04:00 AM

Glad to help. I got that equation too, but I''ve never seen it anywhere else, so I hesitated to use it. I guess it does work, though.