1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232
/*a Copyright
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
@file lib.rs
@brief Bezier curve library
*/
//a Documentation
#![warn(missing_docs)]
/*!
# Bezier curve library
This library provides linear, quadratic and cubic Bezier curves, using
generic types for the scalar and vectors that they are made up of.
The underlying point type must conform to geo_nd::Vector trait as an
N-dimensional vector of scalars, which must meet the geo_nd::Float
trait.
The simplest such scalar is f32 or f64; the point can be a
geo_nd::FArray<f32 (or f64),N> - for N dimensions (usually 2 or
3). Such a point class is a wrapper around an array around an array
F[f32; N], for example, providing standard arithmetic and assignment
etc.
## Bezier types
A linear Bezier has two points, p0 and p1, and provides points
along the line as:
```text
p(t,u=1-t) = u*p0 + t*p1
```
A quadratic Bezier has three points, p0, c and p1, and provides
points along the curve as:
```text
p(t,u=1-t) = u^2.p0 + 2.t.u.c + t^2.p1
```
or, viewing it is a linear Bezier between two linear Beziers:
```text
p(t) = u(u.p0 + t.c) + t(u.c + t.p1)
```
Cubic Beziers go one step further, being effectively linear Bezier
curves of two quadratic Beziers, but explicitly a point at parameter t
is:
```text
p(t,u=1-t) = u^3.p0 + 3.t.u^2.c0 + 3.u.t^2.c1 + t^3.p1
```
## Overview of Bezier curve type
The Bezier type supports construction and interrogation of the type
instance. The type utilizes a `num_pts` field, which is 2 for linear
Beziers, 3 for quadratic, and 4 for cubic. The type includes an array
of *four* control points for *every* Bezier - the first two points are
the endpoints of the Bezier (p0 and p1, in notation). The third
control point is not used for linear Beziers, and the fourth control
point is only used for cubic Beziers.
The Bezier can be interrogated, to determine any point along the curve
given the parameter `t` (from 0 to 1), as can its tangent (which is a
simple linear combination of the control points - the derivative of
the Bezier function with respect to `t`).
Any portion of a Bezier curve between two values of `t` is also a
Bezier curve of the same type; hence a method is supplied to permit
sectioning of a Bezier into another Bezier.
## Straightness and Bisection
The Bezier curve can be bisected in to two Bezier curves of the same
type (such as cubic); the two halves of a Bezier will be closer
approximations to a straight line, and hence to render a Bezier it is
common to bisect a Bezier recursively until the elements are 'straight
enough'. One can consider a cubic Bezier curve, for example being
mapped to a list of linear Beziers which join end-to-end, which
approximate the original Bezier to within a 'straightness' measure.
This concept can be used not only to render a Bezier as straight line
segments, but also to approximate the length of a Bezier, or to find a
value for the parameter `t` for a particular distance along the
Bezier.
Methods are provided to generate iterators that will yield straight
line segments or points, which approximate a Bezier curve to a
particular straightness; further methods are supplied to calculate the
length of a Bezier, or to find the value of `t` for s distance along
the Bezier.
## Circular arcs and rounding
Bezier curves cannot express circular arcs precisely; they are
different mathematical beasts. However, a circular arc may be
approximated quite closely with a cubic Bezier curve.
It can be useful, when using two-dimensional graphics, to generate
rounded rectangles (or other polygons). For these case the corner
points of the rectangles are known, and the directions of the lines
into the corner are known, and it is useful to generate a Bezier that
represents the arc which can replace this corner. This is another
circular arc, but described by the corner, approach vectors, and
rounding radius.
# Examples
An example using 2-dimensional vectors of f32
```
use geo_nd::Vector;
type Point = geo_nd::FArray<f32,2>;
type Bezier = bezier_nd::Bezier<f32, Point, 2>;
let dx = Point::from_array([1.,0.]);
let dy = Point::from_array([0.,1.]);
let line = Bezier::line( &dx, &dy );
assert_eq!( line.degree(), 1);
assert!( line.is_straight(0.));
// A 30-degree arc of radius 3; has length of PI/2,
// it is fairly close to being a straight line, subjectively...
let arc = Bezier::arc( 30.0f32.to_radians(), 3.0, &Point::from_array([3.,4.]), &dx, &dy, 0.);
assert_eq!( arc.degree(), 3);
assert!(!arc.is_straight(0.));
// Breaking the arc with a large value of straightness yields only 3 points:
assert_eq!( arc.as_points(0.1).count(), 3);
// This is 1.5662874
println!( "Arc length when straightened to '0.1' is {}", arc.length(0.1) );
// Breaking the arc with a small value of straightness yields 33 points!
assert_eq!( arc.as_points(0.01).count(), 33);
// This is 1.5707505 - a lot closer to PI/2 = 1.57079632679
println!( "Arc length when straightened to '0.1' is {}", arc.length(0.1) );
for (a,b) in arc.as_lines(0.05) {
println!("Line from {} to {}\n", a, b);
}
let q = Bezier::quadratic( &Point::from_array([2.,6.]),
&Point::from_array([3.5,8.]),
&Point::from_array([4.,7.]));
assert_eq!( q.borrow_pt(0)[0], 2., "Start point X of Bezier" );
assert_eq!( q.borrow_pt(0)[1], 6., "Start point Y of Bezier" );
assert_eq!( q.borrow_pt(1)[0], 4., "End point X of Bezier" );
assert_eq!( q.borrow_pt(1)[1], 7., "End point Y of Bezier" );
```
An example using 3D vectors of f64
```
use geo_nd::Vector;
type Point = geo_nd::FArray<f64,3>;
type Bezier = bezier_nd::Bezier<f64, Point, 3>;
let c = Bezier::cubic( &Point::from_array([1.,0.,0.]),
&Point::from_array([2.5,0.,-1.]),
&Point::from_array([0.,2.5,1.]),
&Point::from_array([0.,1.,0.]));
// This is just over 3.283
println!( "3D cubic length when straightened to '0.1' is {}", c.length(0.1) );
// But this is just over 3.29
println!( "3D cubic length when straightened to '0.01' is {}", c.length(0.01) );
```
# Circular arc algorithm
There are many papers and articles on constructing Bezier curves that
approximate circular arcs; from an academic perspective these provide
analytical approximation generation. This library is more practical:
it provides an implementation that is simple, fast, and works for all
angles. Effectively it is table-based; in fact, it uses a quartic
polynomial of the square of the sine of the angle of the arc, with the
polynomial matching a table generated from experimental data.
The approach taken was to start with an analytical value for the
coefficient (`lambda`) applied to the corner direction vectors to
generate the two control points, and to determine the
mean-square-error this generated, for a number of points along the
Bezier curve, in the distance from the point to the centre of the arc
compared to the radius of the arc. The value of 'lambda' was adjusted
in small steps, to reach a minimum mean-square-error for the angle of
the arc.
Numerous tables of values of best-lambda compared to different
functions of the angle (such as sin(angle), sin(angle)^2, etc) were
produced, along with reciprocal tables, and a best low-order
polynomial match was sought which would yield a very high correlation
to the table.
This polynomial is encoded in the Bezier function - currently not
particularly well optimized, though. The accuracy of the Bezier curves
produced is compared in regression testing to be within 0.1% (using
the mean-square-error of a number of points along the Bezier).
This is not looking for the worst excursion; no visual comparisons
have been done; the purpose is to provide something that is clean,
works across the range, and is efficient. There is no perfect solution
to this problem!
!*/
/*a Imports
*/
mod curve;
mod line;
mod point;
/*a Exports
*/
pub use self::line::BezierLineIter;
pub use self::point::BezierPointIter;
pub use curve::Bezier;