Bézier- and B-spline techniques. Hartmut Prautzsch Wolfgang Boehm Marco Paluszny - PDF

Bézier- and B-spline techniques Hartmut Prautzsch Wolfgang Boehm Marco Paluszny March 26, To Paul de Faget de Casteljau Preface Computer-aided modeling techniques have been developed since the

Please download to get full document.

View again

of 54
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Entertainment & Humor

Publish on:

Views: 6 | Pages: 54

Extension: PDF | Download: 0

Bézier- and B-spline techniques Hartmut Prautzsch Wolfgang Boehm Marco Paluszny March 26, 2002 2 To Paul de Faget de Casteljau Preface Computer-aided modeling techniques have been developed since the advent of NC milling machines in the late 40 s. Since the early 60 s Bézier and B- spline representations evolved as the major tool to handle curves and surfaces. These representations are geometrically intuitive and meaningful and they lead to constructive numerically robust algorithms. It is the purpose of this book to provide a solid and unified derivation of the various properties of Bézier and B-spline representations and to show the beauty of the underlying rich mathematical structure. The book focuses on the core concepts of Computer-aided Geometric Design (CAGD) with the intent to provide a clear and illustrative presentation of the basic principles as well as a treatment of advanced material, including multivariate splines, some subdivision techniques and constructions of arbitrarily smooth free-form surfaces. In order to keep the book focused, many further CAGD methods are excluded. In particular, rational Bézier and B-spline techniques are not addressed since a rigorous treatment within the appropriate context of projective geometry would have been beyond the scope of this book. The book grew out of several courses taught repeatedly at the graduate and intermediate under-graduate levels by the authors at the Rensselaer Polytechnic Institute, USA, the Universities of Braunschweig and Karlsruhe, Germany, and the Universidad Central de Venezuela. These courses were taught as part of the curricula in mathematics and computer sciences, and they were regularly attended also by students from electrical and mechanical engineering, geophysics and other sciences. For the careful proofreading of parts of the manuscript, we like to thank Stefan Bischoff, Bernhard Garz, Georg Umlauf, Claudia Bangert and Norbert Luscher. Especially, we thank Christoph Pennekamp and Natalie Spinner for preparing the LaTeX file and Bernd Hamann for his critical, thorough and final proofreading. Wolfenbüttel, Caracas, Karlsruhe, Wolfgang Boehm Marco Paluszny Hartmut Prautzsch VII Contents I Curves 1 Geometric fundamentals 1.1 Affine spaces Affine combinations Affine maps Parametric curves and surfaces Problems 7 2 Bézier representation 2.1 Bernstein polynomials Bézier representation The de Casteljau algorithm Derivatives Singular parametrization A tetrahedral algorithm Integration Conversion to Bézier representation Conversion to monomial form Problems 22 3 Bézier techniques 3.1 Symmetric polynomials The main theorem Subdivision Convergence under subdivision Curve generation by subdivision Curve generation by forward differences Intersections The variation diminishing property The symmetric polynomial of the derivative 35 IX X Contents 3.10 Simple C r joints Degree elevation Convergence under degree elevation Problems 40 4 Interpolation and approximation 4.1 Interpolation Lagrange form Newton form Hermite interpolation Piecewise cubic Hermite interpolation Approximation Least squares fitting Improving the parameter Problems 56 5 B-spline representation 5.1 Splines B-splines A recursive definition of B-splines The de Boor algorithm The main theorem in its general form Derivatives and smoothness B-spline properties Conversion to B-spline form The complete de Boor algorithm Conversions between Bézier and B-spline representations B-splines as divided differences Problems 74 6 B-spline techniques 6.1 Knot insertion The Oslo algorithm Convergence under knot insertion A degree elevation algorithm A degree elevation formula Convergence under degree elevation Interpolation Cubic spline interpolation 86 Contents XI 6.9 Problems 88 7 Smooth curves 7.1 Contact of order r Arc length parametrization Gamma-splines Gamma B-splines Nu-splines The Frenet frame Frenet frame continuity Osculants and symmetric polynomials Geometric meaning of the main theorem Splines with arbitrary connection matrices Knot insertion Basis splines Problems Uniform subdivision 8.1 Uniform B-splines Uniform subdivision Repeated subdivision The subdivision matrix Derivatives Stationary subdivision Convergence theorems Computing the difference scheme The four-point scheme Analyzing the four-point scheme Problems 120 II Surfaces 9 Tensor product surfaces 9.1 Tensor products Tensor product Bézier surfaces Tensor product polar forms Conversion to and from monomial form The de Casteljau algorithm Derivatives Simple C r joints 135 XII Contents 9.8 Piecewise bicubic C 1 interpolation Surfaces of arbitrary topology Singular parametrization Bicubic C 1 splines of arbitrary topology Notes and Problems Bézier representation of triangular patches 10.1 Bernstein polynomials Bézier simplices Linear precision The de Casteljau algorithm Derivatives Convexity Limitations of the convexity property Notes and Problems Bézier techniques for triangular patches 11.1 Symmetric polynomials The main theorem Subdivision and reparametrization Convergence under subdivision Surface generation The symmetric polynomial of the derivative Simple C r joints Degree elevation Convergence under degree elevation Conversion to tensor product Bézier representation Conversion to triangular Bézier representation Problems Interpolation 12.1 Triangular Hermite interpolation The Clough-Tocher interpolant The Powell-Sabin interpolant Surfaces of arbitrary topology Singular parametrization Quintic C 1 splines of arbitrary topology Notes and Problems 180 Contents XIII 13 Constructing smooth surfaces 13.1 The general C 1 joint Joining two triangular cubic patches Piper s G 1 interpolant The vertex enclosure problem The parity phenomenon Problems G k -constructions 14.1 The general C k joint G k joints by cross curves G k joints by the chain rule G k surfaces of arbitrary topology Smooth n-sided patches Multi-sided patches in the plane Problems Stationary subdivision for regular nets 15.1 Tensor product schemes General stationary subdivision and masks Convergence theorems Increasing averages Computing the difference schemes Computing the averaging schemes Subdivision for triangular nets Box splines over triangular grids Subdivision for hexagonal nets Half box splines over triangular grids Problems Stationary subdivision for arbitrary nets 16.1 The midpoint scheme The limiting surface The standard parametrization The subdivision matrix Continuity of subdivision surfaces The characteristic map Higher order smoothness Triangular and hexagonal nets 236 XIV Contents 16.9 Problems 237 III Multivariate splines 17 Box splines 17.1 Definition of box splines Box splines as shadows Properties of box splines Properties of box spline surfaces Subdivision for box spline surfaces Convergence under subdivision Half-box splines Half-box spline surfaces Problems Simplex splines 18.1 Shadows of simplices Properties of simplex splines Normalized simplex splines Knot insertion A recurrence relation Derivatives Problems Multivariate splines 19.1 Generalizing de Casteljau s algorithm B-polynomials and B-patches Linear precision Derivatives of a B-patch Multivariate B-splines Linear combinations of B-splines A recurrence relation Derivatives of a spline The main theorem Problems 286 Part I Curves 1 2 Bézier representation 2.1 Bernstein polynomials 2.2 Bézier representation 2.3 The de Casteljau algorithm 2.4 Derivatives 2.5 Singular parametrization 2.6 A tetrahedral algorithm 2.7 Integration 2.8 Conversion to Bézier representation 2.9 Conversion to monomial form 2.10 Problems Every polynomial curve segment can be represented by its so-called Bézier polygon. The curve and its Bézier polygon are closely related. They have common end points and end tangents, the curve segment lies in the convex hull of its Bézier polygon, etc. Furthermore, one of the fastest and numerically most stable algorithm used to render a polynomial curve is based on the Bézier representation. 2.1 Bernstein polynomials Computing the binomial expansion 1 = (u + (1 u)) n = n ( ) n u i (1 u) n i i leads to the Bernstein polynomials of degree n, ( ) n Bi n (u) = u i (1 u) n i, i = 0,..., n, i which are illustrated in Figure 2.1 for n = 4. The following properties of the Bernstein polynomials of degree n are important. They are linearly independent. Namely, dividing n b iu i (1 u) n i = 0 by (1 u) n, and setting s = 9 10 2. Bézier representation Figure 2.1: The Bernstein polynomials of degree 4 over [0, 1]. u/(1 u), gives n b is i = 0, which implies b 0 =... = b n = 0. They are symmetric, B n i (u) = B n n i(1 u). They have roots at 0 and 1 only, { Bi n (0) = Bn i(1) n 1 = 0 for i = 0 i 0. They form a partition of unity, n Bi n (u) = 1, for all u IR. They are positive in (0, 1), B n i (u) 0, for u (0, 1). They satisfy the recursion formula B n+1 i (u) = ub n i 1(u) + (1 u)b n i (u), where B n 1 = B n n+1 = 0 and B 0 0 = 1. This recursion formula follows directly from the identity ( ) ( ) ( ) n + 1 n n = +. i i 1 i 2.2. Bézier representation 11 Remark 1: The computation of the Bernstein polynomials up to degree n can be arranged in a triangular scheme, as shown below, where the recursion is represented by the key on the right: 1 = B 0 0 B 1 0 B 2 0 B n 0 B 1 1 B 2 1 B n 1 B2 2 B2 n.... key u 7 1 u B n n 2.2 Bézier representation A dimension count shows that the n + 1 (linearly independent) Bernstein polynomials Bi n form a basis for all polynomials of degree n. Hence, every polynomial curve b(u) of degree n has a unique nth degree Bézier representation n b(u) = c i Bi n (u). Any affine parameter transformation u = a(1 t) + bt, a b, leaves the degree of the curve b unchanged. Consequently, b(u(t)) has also an nth degree Bézier representation, b(u(t)) = n b i Bi n (t). The coefficients b i are elements of IR d and are called Bézier points. They are the vertices of the Bézier polygon of b(u) over the interval [a, b]. The parameter t is called the local and u the global parameter of b, see Figure 2.2. The properties of Bernstein polynomials summarized in 2.1 are passed on to the Bézier representation of a curve. The symmetry of the Bernstein polynomials implies that b(u) = n b i Bi n (t) = n b n i Bi n (s), 12 2. Bézier representation Figure 2.2: A cubic curve segment with its Bézier polygon over [a, b]. where u = a(1 t) + bt = b(1 s) + as. These two sums define the Bézier representations of b over [a, b] and [b, a], respectively. Thus, by using the oriented intervals [a, b] and [b, a], we can distinguish the two different parameter orientations of a polynomial curve. For the end points of the curve segment b[a, b], one has b(a) = b 0 and b(b) = b n. Since the Bernstein polynomials sum to one, any point b(u) is an affine combination of the Bézier points. As a consequence, the Bézier representation is affinely invariant, i.e., given any affine map Φ, the image curve Φ(b) has the Bézier points Φ(b i ) over [a, b]. Since the Bernstein polynomials are non-negative on [0, 1], one has for every u [a, b] that b(u) is a convex combination of the b i. Hence, the curve segment b[a, b] lies in the convex hull of its Bézier points. This is illustrated in Figure 2.3. Remark 2: Using the convex hull property separately for each coordinate function of the curve b(u), a bounding box is obtained for the curve segment b[a, b], n b[a, b] [ min b n i, max b i], u [a, b], as illustrated in Figure 2.4 for a planar curve. 2.3. The de Casteljau algorithm 13 Figure 2.3: The convex hull of a Bézier polygon. Figure 2.4: Bounding box. 2.3 The de Casteljau algorithm A curve b(u) = n b 0 i Bi n (t), with u = a(1 t) + bt, can be evaluated easily by the so called de Casteljau algorithm [Casteljau 59]. Repeatedly using the recurrence relation of the Bernstein polynomials and collecting terms, one obtains where b(u) = n n 1 b 0 i Bi n (t) = b 1 i B n 1 i (t) = = b k+1 i = (1 t)b k i + t b k i+1. 0 b n i Bi 0 (t) = b n 0, Two examples are shown in Figure 2.5, with t = 0.4 on the left and t = 1.4 on the right side. The intermediate points b k i of the de Casteljau algorithm can be arranged in a triangular array, where each element is computed according to the key 14 2. Bézier representation Figure 2.5: The de Casteljau construction. on the right: b 0 0 b 0 1 b 1 0 b 0 2. b 1 1 b key 1 t 7 t b 0 n b 1 n 1 b 2 n 2 b n 0 Remark 3: If t lies in [0, 1], then the de Casteljau algorithm consists only of convex combinations, which accounts for the numerical stability of this algorithm. Remark 4: Horner s scheme is a very effective method to evaluate a polynomial in monomial form. It can also be used for a curve b(t) = b i Bi n(t) in Bézier form. After writing b(t) as ( n ( ) ( ) ) i n t b(t) = (1 t) n b i, i 1 t one first evaluates the sum in parentheses by Horner s scheme for the value t/(1 t) and then multiplies the result by (1 t) n. This method fails, if t is close to 1. In this, case one can use the relationship ( n ( ) ( ) ) i n 1 t b(t) = t n b n i. i t 2.4. Derivatives Derivatives The derivative of a Bernstein polynomial of degree n is simple to compute. From the definition of the Bernstein polynomials one gets where B n 1 1 d dt Bn i (t) = n(b n 1 i 1 (t) Bn 1 i (t)) for i = 0,..., n, = B n 1 n = 0 as before. Thus, given a curve n b(u) = b i Bi n (t), t = u a b a, one obtains for its derivative b (u) d du b(u) = n n 1 b a b i B n 1 i (t), where b i = b i+1 b i This is illustrated in Figure 2.6. Figure 2.6: Bézier curve and its hodograph (1:3). If the column b(u) is viewed as a point, then b (u) is a vector. One obtains a point again if b (u) is added to a point. In particular, o + b (u) is called the (first) hodograph of b. Applying the derivative formula above repeatedly, one obtains any rth derivative of b, n r b (r) n! (u) = (n r)!(b a) r r b i B n r i (t), where r b i = r 1 b i+1 r 1 b i denotes the rth forward difference of b i. As above one obtains the second and further hodographs. Using the derivative formulas and the endpoint interpolation property of Bézier curves, we obtain a result that was fundamental for Bézier s first 16 2. Bézier representation development. The derivatives of b at t = 0 (or t = 1) up to order r depend only on the first (or last) r + 1 Bézier points, and vice versa. Geometrically, this means that, in general, the tangents of b at t = 0 and 1 are spanned by b 0, b 1 and b n 1, b n, respectively, and that the osculating planes of b at t = 0 and 1 are spanned by b 0, b 1, b 2 and b n 2, b n 1, b n, respectively, and so forth. Figure 2.7 gives an illustration. Figure 2.7: Tangents and osculating planes. Remark 5: Viewing the Bézier polygon of a curve b(u) = b i Bi n (t), where u = (1 t)a + t b, as a piecewise linear function p(u) over [a, b], one gets that the derivative p (u) of the Bézier polygon consists of the Bézier points of b (u). This is illustrated in Figure 2.8 for a functional curve. Figure 2.8: The derivative of a Bézier polygon. 2.5. Singular parametrization Singular parametrization Consider a polynomial curve and its derivative b(t) = n b i Bi n (t) n 1 ḃ(t) = n b i B n 1 i (t), where the dot indicates differentiation with respect to the parameter t. If b 0 = o, then ḃ(t) is zero at t = 0. However, with the singular reparametrization t = s, one gets d ds b(t(0)) = n b 1. Thus, if b 0 = o and b 1 o, then the curve b(t) has a tangent at t = 0 that is directed towards b 2, as illustrated in Figure 2.9. Figure 2.9: Singular parametrization. Remark 6: If b 0 = b 1 = o and b 2 o, then the tangent of b(t) at t = 0 is directed towards b 2, etc. 2.6 A tetrahedral algorithm Computing differences and the affine combinations of de Casteljau s algorithm can be combined. Namely, the rth derivative of a curve b(u) = b 0 i B n i (t), t = u a b a, 18 2. Bézier representation at any u can be computed with de Casteljau s algorithm applied to multiples of the differences k b i. Since the computation of affine combinations of affine combinations is commutative, i.e., αi βj p ij = β j αi p ij, the forward difference operator commutes with the steps of de Casteljau s algorithm. Hence, one can compute the rth derivative also by first computing n r steps of de Casteljau s algorithm, then r differencing steps and, finally, a multiplication by the factor n (n r + 1)/(b a) r. Thus, it follows b (r) (u) = n (n r + 1) (b a) r r b n r 0, In particular, this formula says that the tangent and osculating plane of b at u are spanned by b n 1 0, b n 1 1 and b n 2 0, b n 2 1, b n 2 2, respectively, as illustrated in Figure 2.10 for a cubic. Figure 2.10: Osculating plane and tangent and the de Casteljau scheme. Computing the points r b n k 0 for all k by successive de Casteljau and differencing steps, one also gets the intermediate points k b j i, i + j + k n. All these points can be arranged conveniently in a tetrahedral array, as illustrated in Figure 2.11 for n = 2, where the key represents the recursion c = a(1 t) + bt and d = b a. This is not the only possible way to compute the tetrahedral array. Eliminating a or b, one obtains respectively. c = b + d(t 1) and c = a + dt, 2.7. Integration 19 Figure 2.11: Tetrahedral algorithm. When we use one of these rules, instead of the differencing step, it suffices to compute only the points of the two triangular schemes given by the points on the left and bottom (or right) side of the tetrahedron. Remark 7: It should be noted that differencing is not a numerically stable process, in general. Consequently, computing derivatives is not a numerically stable process either. 2.7 Integration The integral of a polynomial curve in Bézier representation b(u) = n b i Bi n (t), t = u a b a, has the Bézier representation c(u) = b(u)du = n+1 c i B n+1 i (t), where c i = c i 1 + b a n + 1 b i 1 = c 0 + b a n + 1 (b b i 1 ), i = n + 1,..., 1, 20 2. Bézier representation and c 0 is an arbitrary integration constant. This is verified by differentiating c(u). As a consequence of the integration formula and the endpoint interpolation property of the Bézier representation, one obtains b and, in particular, independently of i, a b(u)du = b a n + 1 (b b n ) 1 0 B n i (t)dt = 1 n Conversion to Bézier representation Some older CAD data formats represent curves by monomials. Thus, data conversion between different CAD systems is an application where it is necessary to convert the monomial to the Bézier representation and vice versa. Let n ( ) n b(t) = a i t i i be a curve in monomial form with binomial factors as in the Bézier representation. Since ( ) n t i (1 t + t) n i = i = = one obtains the conversion formula b(t) = n i ( )( ) n n i t i+k (1 t) n i k i n i k k=0 n i ( ) i + k Bi+k n i k=0 n ( ) j Bj n, i j=0 n b j Bj n (t), j=0 where and ( j i) = 0 for j i. b j = n ( ) j a i i 2.8. Conversion to Bézier representation 21 The formula for the conversion to monomial form can be derived similarly by multiplying out the Bernstein polynomials, see Problem 4. In Section 2.9, we present a different derivation of it. Remark 8: If a 2 = = a n = o and a 1 o, then b(t) is a linear polynomial represented over [0, 1] by the Bézier points as illustrated in Figure b j = a 0 + ja 1, Figure 2.12: Equidistant Bézier points on a line. Remark 9: Conversely, if the n + 1 Bézier points b i lie equidistantly on a line, then b(t) is a linear polynomial, which can be written as b(t) = (1 t)b 0 + tb n. This property is referred to as the linear precision of the Bézier representation. Remark 10: As a consequence of Remark 9, the functional curve [ ] t b(t) =, b(t) = b b(t) i Bi n (t), has the Bézier points [i/n b i ] t, as illustrated in Figure The coefficients b i are referred to as the Bézier ordinates of b(t), and i/n as the Bézier abscissae. Figure 2.13: Bézier representation of a functional curve. 22 2. Bézier representation 2.9 Conversion to monomial form Given a polynomial curve in Bézier representation, b(u) = n b i Bi n ( ) u a b a
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks