[Ghoser777]

I've been working on a way to make objects in an NSView walk along a bezier path, and all has gone well except for one thing: cubic bezier paths.

lineTo, moveTo, and close operations are easy, but the real trick is curveTo operations.

I have already been able to obtain the four control points, P0 (initial point), P1, P2, and P3 (destination point). I also know of this function:

B(u) = P0*(1-u)^3 + P1*3z*(1-u)^2 + P2*3(z^2)*(1-u) + P3*z^3

That gives me the point for each u in [0,1] on the cubic curve. I'm okay so far.

What I need to be able to do is figure out for what x, the distance between B(x) and B(u) is equal to some distance d. If that distance can't be obtained for some u on some path (you go from u to 1), that's okay. I just need to find out if that is the case.

So, this is tricky because it ends up being a nasty arc length calculus problem of this form:

Integral from u to x of (1 + (F'(u,x))^2)^(1/2)dx = d.

F(u,x) in this case is defined as the distance from B(u) to B(x). This ends up being something like this:

F(x) = ((B(u).x - B(x).x)^2 + (B(u).y - B(x).y)^2)^(1/2)

Okay, and now it becomes painfully apparent that things get REALLY messy.

So my question is, does anyone have a hefty bezier path arc length algorithm on them? Or maybe some motivation on how to attack this problem?

If not, I guess I'll end up thowing this at Mathematica, but its symbolic integrator is going to have to deal with an absolute mess.

Thanks,
Matt Fahrenbacher

[davechen]

I did a google search on bezier curve arc length and found this link

It sounds like what this guy did was to recursively sub-divide the curve until the segments were small enough, and then add up the segment lengths.

[Ghoser777]

Yeah, I ended up doing that, but using a different (and I think better) algorithm for calculating points on a bezier path:

http://www.moshplant.com/direct-or/bezier/math.html

Thanks,
Matt Fahrenbacher

[Detrius]

This is where Calculus 3&4 come in handy. The subdividing of the path is basically just doing the integral by brute force--physically calculating the distance. However, if you have the equation, the integral can be calculated.

The length is simply the integral of the norm of the derivative. This would be in R2, in this case.

I'm not entirely sure I understand how your equations are set up. In your B(u) equation, what is z? What are your independent variables? I am assuming u and z, but that leaves B(u) to be a y value which makes this a 3D curve, which I doubt is what you want. I pulled out my dusty old Cal 4 book for this. With a little more clarification, I may be able to spit out something more useful.


Hank

(Double major in Math and Computer Science, graduating this December, at UNC Charlotte)

[davechen]

Recursive subdivision is the standard way of rendering bezier curves, as opposed to evaluating it at uniform steps in t. With recursion you can have adaptive subdivision. With uniform steps its trickier to pick a step size to guarantee an error bounds.

Also, if I remember correctly, its less computation to do it recursively, although my curved surfaces class was a long time ago.

Note to Detrius, the page at moshplant is simply giving a 2-d bezier curve. x and y are functions of t. For a 3-d curve you'd add another equation for z.

dave

(cs degrees in 88, 91 and 98 )

[Detrius]

Note to Detrius, the page at moshplant is simply giving a 2-d bezier curve. x and y are functions of t. For a 3-d curve you'd add another equation for z.

I thought this was rather obvious. This is just parametric functions. The thing that was not obvious is coming in expecting this and trying to figure out where Ghoser got his functions (going strictly on my math background).

[davechen]

Originally posted by Detrius:


I thought this was rather obvious. This is just parametric functions. The thing that was not obvious is coming in expecting this and trying to figure out where Ghoser got his functions (going strictly on my math background).

Oops, I misread your post. Late night surfing.

[Ghoser777]

Originally posted by Detrius:


I thought this was rather obvious. This is just parametric functions. The thing that was not obvious is coming in expecting this and trying to figure out where Ghoser got his functions (going strictly on my math background).

Some crack pot website. The new functions I found were much easier to understand. u in the original functions I posted was a number between 0 and 1, I believe, so B(u) would yield a point on the bezier path. That definition was funky, and I understand the new equations more.

I'm currently just subdiving the path and adding up the lengths of tangents till I get as far as I want, although its fairly innefficient. Therefore, I'm playing with the integral I've got and I'll post back after I hack it into a better form. This was what I was trying to do originally, but that equation was hideous and unuseful.

Thanks,
Matt Fahrenbacher

(Math major: U of Illinois May 2002)

[Ghoser777]

Actually, finding the arc length of a paramterized curve is pretty easy (sort of), at least in form.

It's just the integral of the square root of the sum of the squares of the derivatives of the components with respect to t, or:

integral(Sqrt((dx/dt)^2 + (dy/dt)^2))dt

I end up with this:

Integral(Sqrt[a*t^4 + b*t^3 + c*t^2 + d*t + f])dt

as the general form. Doesn't look too bad so far, just the square root of a four degree polynomial. But try this:

http://www.integrals.com/ provides a web interface to mathematics symbolic integrator. I know they're not completely accurate, but look at what results you get if you put in the above (removing the integral command and swapping t's and x's). You may have to drag the image elsewhere, as it won't fit in the box that the webpage provides.

So, anyone got at least the right motivation to integrate this baby? Parts? Substitution? Trig forms? Sacrifice?

Matt Fahrenbacher

[The Godfather]

Da-amn, I want to get my hands on my Mac already and apply all my mad vector skills too