Developers Planet

Nic February 2016

Uniform discretization of Bezier curve

I need to discretise a 3rd order Bezier curve with points equally distributed along the curve. The curve is defined by four points p0, p1, p2, p3 and a generic point p(t) with 0 < t < 1 is given by:

``````point_t = (1 - t) * (1 - t) * (1 - t) * p0 + 3 * (1 - t) * (1 - t) * t * p1 + 3 * (1 - t) * t * t * p2 + t * t * t * p3;
``````

My first idea was to discretise t = 0, t_1, ... t_n, ..., 1

This doesn't work as, in general, we don't end up with a uniform distance between the discretised points.

To sum up, what I need is an algorithm to discretise the parametric curve so that:

``````|| p(t_n) - p(t_n_+_1) || = d
``````

I thought about recursively halving the Bezier curve with the Casteljau algorithm up to required resolution, but this would require a lot of distance calculations.

Any idea on how to solve this problem analytically?

hkrish February 2016

What you are looking for is also called "arc-length parametrisation".

In general, if you subdivide a bezier curve at fixed interval of the default parametrisation, the resulting curve segments will not have the same arc-length. Here is one way to do it http://pomax.github.io/bezierinfo/#tracing.

A while ago, I was playing around with a bit of code (curvature flow) that needed the points to be as uniformly separated as possible. Here is a comparison (without proper labeling on axes! ;)) using linear interpolation and monotone cubic interpolation from the same set of quadrature samples (I used 20 samples per curve, each evaluated using a 24 point gauss-legendre Quadrature) to reparametrise a cubic curve.

[Please note that, this is compared with another run of the algorithm using a lot more nodes and samples taken as ground truth.]

Here is a