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

3 Answers 3

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

See these papers:

share|improve this answer

I suspect the answer you seek differs from the question you asked. Let me consider a few 3-D scenarios (0ne post each).

SCENARIO #1: You load up a 3D program like Blender, and add a Bezier curve to the scene. There are control handles, and the curve is approximated by segments. Increase the resolution of the curve, and the approximation gets better and better. Zoom far away from the curve, and at some point the resolution of your curve will exceed the resolution displayed. It would be nice to cull unnecessary points.

If this is what you mean, you are in luck:
The drawn curve is already a linear approximation. Increase and decreasing the resolution has no effect on the order of the curve. Let us build such a curve.

Let the order be 3, and the given points be A,B,C,D. and let the 3D curve be given by
$(1a)\;\;\;\;\; {\bf x}(t) = A + 3 P t + 3Q t^2 + R t^3, \;\;\;\;\; 0\le t \le 1$
${\small \hspace{60pt} P = (B\!-\!A),\;\; Q = (C\!-\!2B\!+\!A),\;\; R= (D\!-\!3C\!+\!3B\!-\!A)}$
or, immediately in the given points
$(1b)\;\;\;\;\; {\bf x}(t) = A(1\!-\!t)^3 + 3 Bt (1\!-\!t)^2 + 3C t^2 (1\!-\!t) + D t^3 \;\;\;\;\; 0\le t \le 1$

The points A and D are the endpoints of the curve, and if you join segments AB, CD, you will find that these are the familiar handles. Now consider two tasks

1. Change the resolution. How do we draw such a curve? Say we want n segments. Then we will need n+1 t-values:
$\;\;\;\;\;\{t_k\} = 0, \tfrac{1}{n}, \tfrac{2}{n}, ..., \tfrac{n}{n} = 1,\;\;$ or
$\;\;\;\;\;\{t_k\} = {k/n}, \;\;\;k = 0, \ldots, n $
Then evaluate (1a) or (1b) at the n t-values. Join them with straight lines. This curve is your approximation. The distance between points is the straight line distance.

Now let's think this through. Even if this is not what you mean, are you sure you want the arc length? I have two points in space, A, and B. I will know if two points overlap on my screen by checking their ordinary Euclidean distance. The distance between them along the curve is not only much harder to calculate, it doesn't answer the question.

2. Increase the number of control points/handles. High-order polynomials are unruly monsters. Rather than increase the order of the curve, I will concatenate 3rd order curves (let them share common endpoints, and maybe tangents). This has the familiar look: a point on the curve has a handle that extends on both sides. As a general rule, we will use 3rd order curves everywhere, so that between any two control points on the spline, there is a single, 3rd order curve, and the handles give the direction, and strength, of the tangent at that point,
like this.

In both cases, I avoid raising the order, All curves are order 3.


Let me take this implementation seriously. I am not convinced that I need to change the resolution, except by some very general rules (say, based on camera distance and bounding box). Here is why.

Consider representation (1b). You posted in a Game forum, so I'll assume you are willing to use a graphics card or SSE2 to do some vector math. I choose an arbitrary resolution: say, 32 points (31 segments). Let me agree not to change this number, but instead use it everywhere, for all splines displayed on the screen.

Consider the kth point of my spline. I will write it as a vector product:

$\left[\begin{array}{} A & B & C&D \end{array}\right] \left[\begin{array}{} (1\!-\!t_k)^3 \\(1\!-\!t_k)^2 t_k \\ (1\!-\!t_k){t_k}^2\\{t_k}^3 \end{array}\right]\;\;\;$ or, $\left[\begin{array}{} A & B & C&D \end{array}\right] \cdot T_k$,
where Tk is a column vector. Then the 32 poitns on my spline are $\left[\begin{array}{} A & B & C&D \end{array}\right] \left[ \left[\begin{array}{} \;\\ \!T_0 \!\\\; \end{array}\right] \left[\begin{array}{} \;\\ \!T_1\! \\\; \end{array}\right] \left[\begin{array}{} \;\\ \!\ldots \! \\\; \end{array}\right] \left[\begin{array}{} \;\\ \!T_{31}\! \\\; \end{array}\right] \right] $

The 4x32 matrix on the right, containing all the powers of tk, is constant, and will be used for all splines on my screen. The whole problem can be passed to the graphics card (or SSE) as the (partitioned) matrix multiplication of [Pts] $\cdot$ [Constants], and then drawing the straight lines joining points on the same curve.

Being the thing to be done
Onward. (TO DO: EDIT.)

share|improve this answer

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.