Curves
More about curves
Last updated
More about curves
Last updated
This session contains extra materials removed from the introduction to curves for reducing its length. You may follow along to learn some concepts and techniques.
The aim of this section is to construct Bezier curves [] from first principles. We will start from the concept of linear interpolation already presented numerous times and build up to spatial curves.
Let’s now use three points and apply the same interpolation consecutively i.e. use the same “t” parameter for both line segments.
Next we interpolate between the points generated from the prior two interpolations. Again we use the same parameter “t” as before.
Adding more control points has the effect of just expanding the “triangle” shape of repeated interpolations. Geometrically it allow us to create more complex curves. For instance with three control points we can only express curves in the plane spanned by the triangle. While with four points we can create truly spatial curves.
What is very nice about this geometric construction is that the interim products are also useful. For example the last line we interpolate represents the tangent of the curve at that particular parameter.
With two points we define a line “p0 * ( 1 – t ) + p1 * t”; a curve of degree one. With three points we create a quadratic curve of degree two by performing the following operations:
We computed “q0 = p0 * ( 1 – t ) + p1 * t” and “q1 = p1 * ( 1 – t ) + p2 * t” and then performed one more interpolation “q0 * ( 1 – t ) + q1 * t”.
If we eliminate the intermediate values “q0” and “q1” by in place substitution, we obtain “( p0 * ( 1 – t ) + p1 * t ) * ( 1 – t ) + ( p1 * ( 1 – t ) + p2 * t ) * t” which further expands to “p0 * ( 1 – t )2 + 2 * p1 * t * ( 1 – t ) + p2 * t2“.
We may go as far as totally factoring for “t” to obtain a more obvious quadratic form, namely “( p2 – 2 * p1 + p0 ) * t2 + 2 * ( p1 – p0 ) * t + p0“.
Note that the points “p0“, “p1” and “p2” can be considered as constant coefficients in exactly the same manner as the scalar coefficient of the parabola “ax2 + bx + c”. Also note that when “t = 0” we clearly obtain “p0” and when “t = 1” we obtain “p2“.
For example for the cubic curve we can directly expand the expression to obtain the following polynomial: “( 1 – t )3 + 3t( 1 – t )2 + 3t2( 1 – t ) + t3“. All we have to do then is to use a sequence of points as coefficients for each term. It is clear now why the number of points required equals the degree of the polynomial plus one.
The aim of this section is to demonstrate the process of polygonal curve smoothing. This quite useful for time series of real, as in the real world, data. For example we can use this technique to reduce the noise from sensor devices, to smooth stock market fluctuations of prices or epidemic incident curves.
For simplicity we will use the random number generator to produce a range of values in the [0, 1] * 5 interval and plot them in sequential order as seen in the figure.
The logic of this graph is quite simple: For each point “b” in the list of points we select one ahead “c” and one behind “a” and apply the weighted average expression “0.25 * a + 0.5 * b + 0.25 * c”. The components before the expression block are just there to ensure we will not try to index points outside the valid range [0, n-1] as we are selecting points using the “list item” component but included the “-1” and “+1” positions to be extracted. This also means that we lost two points from the original curve, the very first and very last.
You can already see that the new polygonal curve produced is less noisy that the original points. The weighted sum factors “0.25”, “0.5” and “0.25” express the idea of using more of the “current” point and only a smaller fraction of its neighbours. We can apply this operation recursively; unfortunately here using copy and paste.
To understand the effect of neighbour’s influence we may parameterize the weighted sum expression as “0.5 * ( 1 – t ) * a + t * b + 0.5 * ( 1 – t ) * c”, which allow us to choose the amount of weight for the central value, while the neighbours are equally weighted with half of the remainder.
Assuming you are reading this after the “cluster” components, we can package the logic and apply it repeatedly to observe the effect of the central weight factor. The result after just four applications are amazingly smooth. Moreover, interpolating between total and no control for the central points shows that there is a sweet spot before the noise reappears!
Finally we replace the single parameter “t” with a range in [0, 1] using the “series” component. The step parameter uses the “1 / ( x – 1 )” expression for normalization. The approach of evaluating points on curves using repeated linear interpolations is known as the De Casteljau’s algorithm [].
One way to derive the general recipe for all curves given the polynomial degree we wish to achieve is based on the following construction: We can write “1” as the sum of “( 1 – t ) + t”. Then we raise this into a desired power “( ( 1 – t ) + t )n” and expand using Pascal’s triangle [] aka the binomial coefficients [].
The polynomials of this form, also known as Bernstein polynomials [], generalize the idea of blending sequentially between multiple quantities. Here we used them more points, but the idea is broader. If you are interested to learn more about spline curves you may look at “The Nurbs Book” [] or “An Introduction to Nurbs” []
If interested in the topic of smoothing curve transforms [] you may read more on the concept of the moving average [] and Laplacian [] techniques. Note that the same ideas can be applied in 2D for instance to blur images and 3D to smooth mesh geometries.
