• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

Archived

This topic is now archived and is closed to further replies.

tomm

Curvature of a Bezier *SOLVED*

13 posts in this topic

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]
0

Share this post


Link to post
Share on other sites
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]
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
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.

0

Share this post


Link to post
Share on other sites
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.

0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
|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]
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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)
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites