mirror of
https://github.com/Pomax/BezierInfo-2.git
synced 2025-08-31 20:11:59 +02:00
109 lines
7.2 KiB
Markdown
109 lines
7.2 KiB
Markdown
# The projection identity
|
|
|
|
De Casteljau's algorithm is the pivotal algorithm when it comes to Bézier curves. You can use it not just to split curves, but also to draw them efficiently (especially for high-order Bézier curves), as well as to come up with curves based on three points and a tangent. Particularly this last thing is really useful because it lets us "mold" a curve, by picking it up at some point, and dragging that point around to change the curve's shape.
|
|
|
|
How does that work? Succinctly: we run de Casteljau's algorithm in reverse!
|
|
|
|
In order to run de Casteljau's algorithm in reverse, we need a few basic things: a start and end point, a point on the curve that we want to be moving around, which has an associated *t* value, and a point we've not explicitly talked about before, and as far as I know has no explicit name, but lives one iteration higher in the de Casteljau process then our on-curve point does. I like to call it "A" for reasons that will become obvious.
|
|
|
|
So let's use graphics instead of text to see where this "A" is, because text only gets us so far: move the sliders for the following graphics to see what, given a specific `t` value, our `A` coordinate is. As well as some other coordinates, which taken together let us derive a value that the graphics call "ratio": if you move the curve's points around, A, B, and C will move, what happens to that value?
|
|
|
|
<div class="figure">
|
|
|
|
<graphics-element inline={true} title="Projections in a quadratic Bézier curve" src="./abc.js" data-type="quadratic">
|
|
<input type="range" min="0" max="1" step="0.01" value="0.5" class="slide-control">
|
|
</graphics-element>
|
|
<graphics-element inline={true} title="Projections in a cubic Bézier curve" src="./abc.js" data-type="cubic">
|
|
<input type="range" min="0" max="1" step="0.01" value="0.5" class="slide-control">
|
|
</graphics-element>
|
|
|
|
</div>
|
|
|
|
So these graphics show us several things:
|
|
|
|
1. a point at the tip of the curve construction's "hat": let's call that `A`, as well as
|
|
2. our on-curve point give our chosen `t` value: let's call that `B`, and finally,
|
|
3. a point that we get by projecting A, through B, onto the line between the curve's start and end points: let's call that `C`.
|
|
4. for both quadratic and cubic curves, two points `e1` and `e2`, which represent the single-to-last step in de Casteljau's algorithm: in the last step, we find `B` at `(1-t) * e1 + t * e2`.
|
|
4. for cubic curves, also the points `v1` and `v2`, which together with `A` represent the first step in de Casteljau's algorithm: in the next step, we find `e1` and `e2`.
|
|
|
|
These three values A, B, and C allow us to derive an important identity formula for quadratic and cubic Bézier curves: for any point on the curve with some `t` value, the ratio of distances from A to B and B to C is fixed: if some `t` value sets up a C that is 20% away from the start and 80% away from the end, then _it doesn't matter where the start, end, or control points are_; for that `t` value, `C` will *always* lie at 20% from the start and 80% from the end point. Go ahead, pick an on-curve point in either graphic and then move all the other points around: if you only move the control points, start and end won't move, and so neither will C, and if you move either start or end point, C will move but its relative position will not change.
|
|
|
|
So, how can we compute `C`? We start with our observation that `C` always lies somewhere between the start and end points, so logically `C` will have a function that interpolates between those two coordinates:
|
|
|
|
\[
|
|
C = u(t) \cdot P_{\textit{start}} + (1-u(t)) \cdot P_{\textit{end}}
|
|
\]
|
|
|
|
If we can figure out what the function `u(t)` looks like, we'll be done. Although we do need to remember that this `u(t)` will have a different form depending on whether we're working with quadratic or cubic curves. [Running through the maths](https://mathoverflow.net/questions/122257/finding-the-formula-for-bezier-curve-ratios-hull-point-point-baseline) (with thanks to Boris Zbarsky) shows us the following two formulae:
|
|
|
|
\[
|
|
u(t)_{\textit{quadratic}} = \frac{(1-t)^2}{t^2 + (1-t)^2}
|
|
\]
|
|
|
|
And
|
|
|
|
\[
|
|
u(t)_{\textit{cubic}} = \frac{(1-t)^3}{t^3 + (1-t)^3}
|
|
\]
|
|
|
|
So, if we know the start and end coordinates and the *t* value, we know C without having to calculate the `A` or even `B` coordinates. In fact, we can do the same for the ratio function. As another function of `t`, we technically don't need to know what `A` or `B` or `C` are. It, too, can be expressed as a pure function of `t`.
|
|
|
|
We start by observing that, given `A`, `B`, and `C`, the following always holds:
|
|
|
|
\[
|
|
\textit{ratio}(t) = \frac{\textit{distance}(B,C)}{\textit{distance}(A,B)} = \textit{Constant}
|
|
\]
|
|
|
|
Working out the maths for this, we see the following two formulae for quadratic and cubic curves:
|
|
|
|
\[
|
|
ratio(t)_{\textit{quadratic}} = \left | \frac{t^2 + (1-t)^2 - 1}{t^2 + (1-t)^2} \right |
|
|
\]
|
|
|
|
And
|
|
|
|
\[
|
|
ratio(t)_{\textit{cubic}} = \left | \frac{t^3 + (1-t)^3 - 1}{t^3 + (1-t)^3} \right |
|
|
\]
|
|
|
|
Which now leaves us with some powerful tools: given three points (start, end, and "some point on the curve"), as well as a `t` value, we can _construct_ curves. We can compute `C` using the start and end points and our `u(t)` function, and once we have `C`, we can use our on-curve point (`B`) and the `ratio(t)` function to find `A`:
|
|
|
|
\[
|
|
A = B - \frac{C - B}{\textit{ratio}(t)} = B + \frac{B - C}{\textit{ratio}(t)}
|
|
\]
|
|
|
|
With `A` found, finding `e1` and `e2` for quadratic curves is a matter of running the linear interpolation with `t` between start and `A` to yield `e1`, and between `A` and end to yield `e2`. For cubic curves, there is no single pair of points that can act as `e1` and `e2` (there are infinitely many, because the tangent at B is a free parameter for cubic curves) so as long as the distance ratio between `e1` to `B` and `B` to `e2` is the Bézier ratio `(1-t):t`, we are free to pick any pair, after which we can reverse engineer `v1` and `v2`:
|
|
|
|
\[
|
|
\left \{ \begin{aligned}
|
|
e_1 &= (1-t) \cdot v_1 + t \cdot A \\
|
|
e_2 &= (1-t) \cdot A + t \cdot v_2
|
|
\end{aligned} \right .
|
|
|
|
\Rightarrow
|
|
|
|
\left \{ \begin{aligned}
|
|
v_1 &= \frac{e_1 - t \cdot A}{1-t} \\
|
|
v_2 &= \frac{e_2 - (1-t) \cdot A}{t}
|
|
\end{aligned} \right .
|
|
\]
|
|
|
|
And then reverse engineer the curve's control points:
|
|
|
|
\[
|
|
\left \{ \begin{aligned}
|
|
v_1 &= (1-t) \cdot \textit{start} + t \cdot C_1 \\
|
|
v_2 &= (1-t) \cdot C_2 + t \cdot \textit{end}
|
|
\end{aligned} \right .
|
|
|
|
\Rightarrow
|
|
|
|
\left \{ \begin{aligned}
|
|
C_1 &= \frac{v_1 - (1-t) \cdot \textit{start}}{t} \\
|
|
C_2 &= \frac{v_2 - t \cdot \textit{end}}{1-t}
|
|
\end{aligned} \right .
|
|
\]
|
|
|
|
So: if we have a curve's start and end points, as well as some third point B that we want the curve to pass through, then for any `t` value we implicitly know all the ABC values, which (combined with an educated guess on appropriate `e1` and `e2` coordinates for cubic curves) gives us the necessary information to reconstruct a curve's "de Casteljau skeleton". Which means that we can now do several things: we can "fit" curves using only three points, which means we can also "mold" curves by moving an on-curve point but leaving its start and end points, and then reconstruct the curve based on where we moved the on-curve point to. These are very useful things, and we'll look at both in the next few sections.
|