ansaurus

Question

Function for returning a list of points on a Bezier curve at equal arclength

Answer 1

A:

It's actually pretty easy.

The formula for a cubic Bézier curve is the following: (image courtesy of the Wikipedia page)

$B(t) = (1-t)^3 * p[0] + 3(1-t)^2 * p[1] + 3(1-t)^2 * p[2] + t^3 * p[3], t in [0, 1]$

Where t is simply the "completion" of the curve: 0 is the beginning and 1 is the end. P variables are simply points. You just have to apply the formula to both coordinates of P to get where it is at a given t. Here's how to evaluate a Bézier curve with a t and 4 points in a C#-ish language (I think it would work as is, but I didn't test):

Point BezierCurve(float t, Point p[4])
{
    float x = Math.Pow(1 - t, 3) * p[0].X
            + 3 * Math.Pow(1 - t, 2) * p[1].X
            + 3 * Math.Pow(1 - t, 2) * p[2].X
            + Math.Pow(t, 3) * p[3].X;

    float y = Math.Pow(1 - t, 3) * p[0].Y
            + 3 * Math.Pow(1 - t, 2) * p[1].Y
            + 3 * Math.Pow(1 - t, 2) * p[2].Y
            + Math.Pow(t, 3) * p[3].Y;

    return new Point(x, y);
}

From what I understand of your question, this could be enough to solve your problem. Depending what you want, you may also want to look de Casteljau's algorithm.

zneak 2010-01-26 23:43:16

unfortunately that's the function that does not produce equal arclengths. You can see what I mean if you do something like set your control points to (0,0) (1,1) (0,1) (1,0) - this creates a loop where most of the points tend to clump.The only solution I've come up with is an approximation, use the above algorithm to create say 100 or 1000 segmentslength = sum the length of all the segments l = length / number of nodes requiredthen "travel" the list of line segments, leaving a node after x distance. This obviously has errors, though, they may be within a reasonable tollerance.

Prozacgod 2010-01-27 00:08:47

@Prozacgod: your real problem is to compute the full arclength of a Bézier curve, is it?

zneak 2010-01-27 00:30:52

@Prozacgod: That is just integration over the line segment. Take a look at some vector calculus resources and you should find your answer --although, yours works fine.

nlucaroni 2010-01-27 16:37:11

Thanks for the help guys - for my purposes this is a "calculated once in a while thing" - so taking that into account, I decided to create about 300 line segments, which is slow and limited because of memory requirements. What I find which is annoying is, when I create that example I gave above and the line segments are created in the loop area. I am pretty much guaranteed to be off from what the point might be on the actual curve an amount that is out side my preferred tolerance (+/- .01 or better +/- .001), right now, I'm going to just "look the other way" and worry about it later.

Prozacgod 2010-01-28 02:19:41

@zneak That is part one of the problem, and then I'd like to divide that up into equal sections to produce points that are on the curve at equal arclengths.

Prozacgod 2010-01-28 02:20:32

if anyone wanted it, I was thinking about illustrating this with an animated gif, I wrote a python app so I could play with some examples, would be trivial to export frames and make it a graphic.

Prozacgod 2010-01-28 02:21:57

ansaurus

tags:

views:

answers:

Function for returning a list of points on a Bezier curve at equal arclength

related questions