Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I posted this on gamedev.stackexchange.com earlier, but I didn't get any answers... and only a few views. EDIT: I've got two answers there (as of now), and I'm investigating them now.

How can I find out the distance traveled by a Bézier Curve? For example, the distance traveled by a Linear Bézier Curve is:

$distance = \sqrt{(x_1 - x_0)^2 + (y_1 - y_0)^2}$

But what of a Quadratic, Cubic, Nth-Degree Bézier Curve?

My goal is to figure out the "resolution" ($resolution = 1-t$) beforehand, so I don't have to waste time checking if the next point is touching the previous point.

From here:

$$\mathbf{B}(t) = \sum_{i=0}^n {n\choose i}(1-t)^{n-i}t^i\mathbf{P}_i$$

share|improve this question
    
What do you mean by "distance traveled"? Are you referring to the distance traveled along the curve in a given parameterization? –  Alex Troesch Nov 28 '10 at 6:46
7  
The arclength of a Bézier curve can be very complicated; for a quadratic Bézier you have a complicated expression involving logarithms/inverse hyperbolic functions, and for a cubic Bézier one now requires elliptic integrals. –  J. M. Nov 28 '10 at 6:58
2  
If you have Mathematica : Integrate[(Sqrt[#1 . #1] & )[D[Sum[{Subscript[x, i + 1], Subscript[y, i + 1]}*Binomial[2, i]*(1 - u)^(2 - i)*u^i, {i, 0, 2}], u]], u] –  J. M. Nov 28 '10 at 7:16
1  
@muntoo: You'd probably be better off using a numerical quadrature routine here instead of trying to tease out an explicit closed form expression, FWIW. Note that the answer given by Williham in the Game Dev site uses numerical quadrature (Gaussian for one, and a clever subdivision into line segments or essentially a trapezoidal rule for the other) in the page for the cubic case he linked to. –  J. M. Nov 28 '10 at 23:13
3  
From what you write about "resolution", I'm wondering whether you're solving the right problem. As far as I remember, the best way to draw Bézier curves isn't to substitute successive values of $t$, but to recursively divide them in two until the parts can be satisfactorily drawn as lines? –  joriki Sep 4 '11 at 7:01
show 3 more comments

2 Answers

See these papers:

share|improve this answer
add comment

I showed in the comments how to get Mathematica to generate the arclength function for a quadratic Bézier curve; for this answer I'll give an explicit derivation.

Consider the parametrization

$$\begin{align*}x&=(1-u)^2 x_1+2u(1-u) x_2+u^2 x_3 \\ y&=(1-u)^2 y_1+2u(1-u) y_2+u^2 y_3\end{align*}$$

Letting $\Delta x_i=x_{i+1}-x_i$ and similarly for $\Delta y_i$, the arclength integral corresponding to this parametrization is

$\displaystyle \scriptsize 2\int\sqrt{\Delta x_1^2+\Delta y_1^2+2\left(\Delta x_1\left(\Delta x_2-\Delta x_1\right)+\Delta y_1\left(\Delta y_2-\Delta y_1\right)\right)u+\left(\left(\Delta x_2-\Delta x_1\right)^2+\left(\Delta y_2-\Delta y_1\right)^2\right)u^2}\mathrm du$

We let $c=\Delta x_1^2+\Delta y_1^2$, $b=\Delta x_1\left(\Delta x_2-\Delta x_1\right)+\Delta y_1\left(\Delta y_2-\Delta y_1\right)$, and $a=\left(\Delta x_2-\Delta x_1\right)^2+\left(\Delta y_2-\Delta y_1\right)^2$ to further simplify things.

Consider now the integral

$$2\int \sqrt{c+2bu+au^2}\mathrm du$$

Completing the square yields

$$2\sqrt{a}\int \sqrt{\left(u+\frac{b}{a}\right)^2+\frac{ac-b^2}{a^2}}\mathrm du$$

Skipping the details (but see here for how one might derive the answer), the integral evaluates to

$$\sqrt{a}\left(\left(u+\frac{b}{a}\right)\sqrt{\left(u+\frac{b}{a}\right)^2+\frac{ac-b^2}{a^2}}+\left(\frac{ac-b^2}{a^2}\right)\mathrm{arsinh}\left(\frac{au+b}{\sqrt{ac-b^2}}\right)\right)$$

or

$$\left(u+\frac{b}{a}\right)\sqrt{c+2bu+au^2}+\left(\frac{ac-b^2}{a^{3/2}}\right)\mathrm{arsinh}\left(\frac{au+b}{\sqrt{ac-b^2}}\right)$$

As I've mentioned in the comments, the closed form for the quadratic case is quite complicated (even more so for the cubic case), and you're better off with using numerical quadrature to compute the arclength.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.