Curves and Surfaces for CAGD (Book)
1 (1)
In the French Auto industry both Paul de Castlejau and Pierre Bezier both created equivalent systems to describe the curves on automobiles. At Renault, Bezier developed UNISURF, an early CAD/CAM model.
This chapter provides a bunch of weird analogies for Curves.
Points and Vectors (13)
A point defines a location. Vectors are the result of subtracting points. Vectors can be added, points cannot.
Barycentric (or affine) Combinations allow points to be summed if the scalar coefficients of the expression sum to 1. I like this, it works, even with out addition because
b = b0 + ∑ ai(bi - b0)
which is still the sum of a point and a vector.
If all coefficients are positive, then the center of gravity lies inside the convex hull of the points.
Section on affine maps.
Norm Ellipse... not following this. I'm not clear on what the superscript T is.
Basis function is a function that "chooses", generally for a piecewise function. So
ti is in a set of t, the points where the piecewise functions connect Hi(ti) = 1 Hi(tj) = 0 if tj != ti
Linear Interpolation (25)
A line from a to b can be defined as
x = (1-t)a + t*b
A blossom is a curve formed from linesegments, we say b(t0, t1, ..., tn) where n is the same as the number of segments, we form a piecewise function of one degree lower by taking t0 of each line. This reduce down to a single point. The curve traced by passing in the same value for all arguments is a Bezier curve.
Meneloas theorm: Given piecewise Meneloas theorm says that the order of the arguments doesn't matter.
Page 33 covers the Liebniz formula - I may need to review this further. It's a special case of a blossom.
Discussion of tessalation, Dirichlet (Voronoi) and Delaunay.
The De Castlejau Algorithm (43)
Given 3 points b0, b1, b2
B1,0(t) = (1-t)b0 + t*b1 B1,1(t) = (1-t)b1 + t*b2 B2,0(t) = (1-t)B1,0(t) + t*B1,1(t)
This traces a Bezier parabola.
The polygon formed by the points is the Bezier polygon or Control polygon. The curve over [0, 1] lies within this polygon.
To combine De Castlejau and Bezier in the terms of a Blossom, we define Bezier as B[tn] (where tn means "repeated as an argument n times" not exponentiation). In De Castlejau, for degree 3, this becomes
b0 = B0,0 = B(0,0,0) b1 = B0,1 = B(0,0,1) B1,0 = B(0,0,t) b2 = B0,2 = B(0,1,1) B1,1 = B(0,t,1) B2,0 = B(0,t,t) b3 = B0,3 = B(1,1,1) B1,2 = B(t,1,1) B2,1 = B(t,t,1) B3,0 = B(t,t,t)
So the expression becomes
Bi,j = B(0n-i-j, ti, 1j) = (1-t)B(0n-i-j+1, ti-1, 1j) + t*B(0n-i-j, ti-1, 1j+1)
And if i==0, we are a definition point and if i==n, we're at a Bezier point.
We can get a subdivision of the curve between k and l by creating a new blossom from the points in
B(an-i, bi) for i in 0,n
The Bernstein Form (57)
This is the form I am most familiar with:
B(t) = ∑ Bino(n,i)*ti*(1-t)n-i*bi
Bezier curves are invariant under affine maps but not perspective maps. So an affine map can be applied to the control polygon and the curve computed and it will be correct.
Nice trick, for two curves of the same degree the affine combination for each point produces the affine combination of the two curves.
Derivative of Bezier curve. Difference of control points. The De Castlejau also produces the derivative as a byproduct.
De Castlejau can be used to create a subdivision. Given b0,b1,b2,b3 the control polygon for the first half of the curve will be
c0 = B[0,0,0] c1 = B[0.5,0,0] c2 = B[0.5,0.5,0] c3 = B[0.5,0.5,0.5]
Line intersections can be found with repeated subdivision. If a line does not intersect the control polygon, it does not intersect the curve. If it does intersect the polygon, subdivide and recheck.
Composite Bezier curves can be formed by piecing many curves together. Often these are cubic segments. Given points b0 to b6 forming two composite curves (both containing b3), for the composite to be C1, and
a = t @ b0 b = t @ b3 c = t @ b6 (3/(b-a))*(b3-b2) = (3/(c-b))*(b4-b3)
Polars - not sure about this. The polar with respect to t1 is
p1(t) = b[t1, tn-1]
which (after a lot of math) is also
p1(t) = b(t) + ((t1 - t)/n) * b'(t)
and I thin when t1 = 0, the polar is the Bezier curve itself.
A Bezier curve can also be expressed as a matrix.
Bezier Curve Topics (81)
A curve can be elevated to produce the same curve but with one more control point
bi+1 = (i/(n+1)) * bi-1 + ( 1 - (i/(n+1)) )*bi
Arbitrary degree elevation
bi+r = ∑ bj * bino(n,j) * bino(r, i-j) / bino(n+r, i)
A Bezier curve has no more intersections with a plane than it's control polygons.
Degree reduction is possible with a linear equation solver.
Polynomial Curve Construction (95)
Given an ordered set of points, find a curve that passes through them. We define this as
p(ti) = pi
I'm not going to copy all the formulas on 96 down, but there are several formulas for computed related points, though none of them are completely generalize. So I think the way this works by combining higher polynomials. So for 4 points, we create 3 lines. Those 3 lines (A,B,C) create 2 parabolas (AB, BC) which then creates one degree 3.
Lagrange polynomials provide a more explicit formula. But Lagrange interpolation can produce erratic results.
Cubic Hermite Interpolation. Start with both points and vectors. I'm still skimming this. Lots of math and it seems only partially useful at best.
Point-Normal interpolation.
Least square approximations. We don't need the curve to pass through each point, just pass close. Further, by relaxing the error requirements, we can clean up the control polygon.