13.472J/1.128J/2.158J/16.940J COMPUTATIONAL GEOMETRY Lecture 9 N. M. Patrikalakis Massachusetts Institute of Technology Cambridge, MA 02139-4307, USA Copyrightc 2003MassachusettsInstituteofTechnology Contents 9 Blending Surfaces 2 9.1 Examples and motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 9.2 Blending surface approximation in terms of B-splines . . . . . . . . . . . . . . 4 9.2.1 Blend construction through a procedural \lofted" surface . . . . . . . . 5 9.3 Spherical and circular blending in terms of generalized cylinders . . . . . . . . 7 9.4 Blending of implicit algebraic surfaces . . . . . . . . . . . . . . . . . . . . . . . 11 9.5 Blending as a boundary value problem . . . . . . . . . . . . . . . . . . . . . . 12 9.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 9.5.2 Example: 2nd order (Laplace) equation . . . . . . . . . . . . . . . . . . 13 9.5.3 Mapping { boundary value problem . . . . . . . . . . . . . . . . . . . . 17 9.5.4 Position and tangent plane continuity . . . . . . . . . . . . . . . . . . . 19 9.5.5 Curvature continuity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 9.5.6 Multisided blending surfaces . . . . . . . . . . . . . . . . . . . . . . . . 21 Bibliography 24 1 Lecture 9 Blending Surfaces 9.1 Examples and motivation Blending surfaces, providing a smooth connection between various primary or functional sur- faces, are very common in CAD. Examples include blending surfaces between: Fuselage and wings of airplanes Propeller or turbine blade and hub Bulbous bow and ship hull Primary faces of solid models. Blending (or lleting) surfaces are also byproducts of manufacturing processes such as NC milling with a ball or disk cutter. As a result of continuity conditions, blending surfaces are of higher order, or involve a more complex formulation than the underlying surfaces to be joined. For a detailed review, see Woodwark [15], and Hoschek and Lasser [9] (chapter 14). 2 Example Join bicubic patches along arbitrary cubic linkage curves in parametric space (see Figure 9.1). R(u , v )3 3 Q (w , s )3 3 v = v (t )3 u = u (t )3 w = w (t )3 s = s (t )3 Figure 9.1: Bicubic patches joined along arbitrary cubic linkage curves. Linkage curve 1 is: R1(t) R(t) = R(u3;v3) R(t18); if u = u(t3);v = v(t3) (9.1) Similarly, curve 2 is: R2(t) Q(t) = Q(w3;s3) Q(t18); if w = w(t3);s = s(t3) (9.2) So position continuity alone requires a high degree surface in the t parameter direction (of degree 18 in this example). High degree surfaces are expensive to evaluate (e.g. the de Casteljau or Cox-de Boor algorithms have quadratic complexity in the degree of the curve or surface), may lead to greater inaccuracy of evaluation (as the degree increases), and are di cult to process in a solid modeling environment (e.g. through intersections). Consequently, researchers have developed: Approximations of blending surfaces with low order B-spline surfaces Procedural de nitions of blending surfaces (e.g. \lofted" surfaces, generalized cylinders) in order to reduce some of these problems. 3 9.2 Blending surface approximation in terms of B-splines Let us consider two parametric surface patches rm1n1(u;v); rm2n2(x;y) and linkage curves R1(t) = [u(t);v(t)]; R2(t) = [x(t);y(t)] de ned in the parameter spaces of the two patches, respectively. The unit normal to R1 that is tangent to the patch (see Figure 9.2): r1(t) = N S1jN S 1j u = u(t) v = v(t) (9.3) where N = ru rv is the normal to the patch, and S1 = _u(t)ru(u(t);v(t)) + _v(t)rv(u(t);v(t)) where r = rm1n1(u;v). In general, N and S1 are high order polynomials. For example, when the patch is bicubic and the linkage curve is cubic in the parameter space, we have N ru rv u2v3u3v2 u5v5 t30 S1 _uru t2u2v3 t2t6t9 t17 Next, we introduce bias functions b1(t);b2(t) to control the shape of the blending surface and de ne: q1(t) = b1(t)r1(t) (9.4) q2(t) = b2(t)r2(t) (9.5) to be used as parametric derivatives of the patch in the direction between the linkage curves. For details, see Bardis and Patrikalakis [1]. N 1(t)R r 1S 1 Figure 9.2: N, S1 r1 frame 4 9.2.1 Blend construction through a procedural \lofted" surface Here we use cubic Hermite polynomials as blending functions in the direction between the linkage curves: H1(w) = 1 3w2 + 2w3 (9.6) H2(w) = 3w2 2w3 (9.7) H3(w) = w 2w2 +w3 (9.8) H4(w) = w3 w2 (9.9) These obey the following boundary conditions: H1(0) = 1 ; H1(1) = H01(0) = H01(1) = 0 (9.10) H2(1) = 1 ; H2(0) = H02(0) = H02(1) = 0 (9.11) H03(0) = 1 ; H3(0) = H3(1) = H03(1) = 0 (9.12) H04(1) = 1 ; H4(0) = H04(0) = H4(1) = 0 (9.13) Then the blending surface is: B(w;t) = R1(t)H1(w) + R2(t)H2(w) + q1(t)H3(w) + q2(t)H4(w) (9.14) where R1;R2 are evaluated using a composition mapping (due to high degree, explicit expres- sions are avoided, e.g. degree 18 for cubics), and q1;q2 are similarly evaluated procedurally (to avoid explicit expressions), given that: r1 t47= p t47 (9.15) q1 t50= p t47 (9.16) Next, we construct cubic B-spline approximations to R1;R2;q1;q2: R1(t) = nX ‘=0 R(1)‘ N‘;4(t) (9.17) R2(t) = nX ‘=0 R(2)‘ N‘;4(t) (9.18) q1(t) = nX ‘=0 Q(1)‘ N‘;4(t) (9.19) q2(t) = nX ‘=0 Q(2)‘ N‘;4(t) (9.20) where N‘;4(t) are cubic non-uniform B-spline basis functions and the same knot vector and number of control points is used in all four equations. This approximation involves a process for the insertion of knots until errors are less than speci ed tolerances for the previous four vector functions. 5 The equation for the resulting blending surface is: B(w;t) = 3X k=0 nX ‘=0 Bk;‘ B ezierz }| { Bk;4(w) Above B-spline z }| { N‘;4(t) (9.21) Bw(w;t) = 3 nX ‘=0 3X k=1 (Bk;‘ Bk 1;‘)Bk;3(w)N‘;4(t) (9.22) From position and derivative continuity we get: B0;‘ = R(1)‘ (9.23) B3;‘ = R(2)‘ (9.24) B1;‘ = R(1)‘ + Q(1)‘ =3 (9.25) B2;‘ = R(2)‘ Q(2)‘ =3 (9.26) The disadvantage of approximation is the increase in data and the resulting storage re- quirements. The advantage is that the same class of functions is used which makes it easy to include in a geometric modeler and easy to transfer between CAD/CAM systems. Special attention needs to be given to the correspondence of parametrization of linkage curves and this may necessitate reparametrization of linkage curves. See Bardis and Pa- trikalakis [1], and Hansmann [7] for more details on these issues. t t Figure 9.3: Blending surface cross-link curves. 6 9.3 Spherical and circular blending in terms of general- ized cylinders For a detailed reference on this topic, see Pegna [12]. e e e Π ψ φ 1 2 3 O’ O E Ca u Rs Figure 9.4: Model of milling via a spherical ball cutter (3-axis milling) or a disk cutter (5-axis). The center of the sphere (or spherical cutter) moves on the intersection curve of the o sets of the plane and cylinder C of radius Rc by an o set amount equal to Rs, i.e. ellipse E (see Figure 9.4). Let a be a unit vector along the cylinder axis, e3 a unit vector perpendicular to plane , and O the intersection of the cylinder axis and the plane. Also, e1 = e3 aje 3 aj (9.27) e2 = e3 e1 (9.28) a e2 sR O O’ e3 φ Rc R + Rc s eO 2 R ψ e1 (R + R )/cos φs cR + R s c ’ Figure 9.5: De nition of the ellipse. Find the directrix E, an ellipse. The center of E is [0; Rs tan ;Rs] = RO0. The major axis is (Rs +Rc)=cos along e2. The minor axis is Rs +Rc in the direction parallel to e1. a = [0; sin ;cos ] (9.29) 7 The equation of the ellipse is (see Figure 9.5): R( ) = RO0 + e1(RC +Rs) cos + e2Rc +Rscos sin (9.30) The projection of the center of the sphere (or projection of the ellipse) on the plane is: tp = (Rc +Rs) cos e1 + "R c +Rs cos sin Rs tan # e2 (9.31) tc: Projection of R (equation of the ellipse that is the center of the sphere) to the cylinder. P: Projection of R onto the axis a. v = P RjP Rj (unit normal) (9.32) Π a RO’ P tc RsRs R Rc v pt Figure 9.6: Side view. Observe that: P RO0 = ((R RO0) a)a (9.33) = a( 1) tan sin (Rc +Rs) (9.34) P R = (P RO0) (R RO0) (9.35) = (Rc +Rs) tan sin [0; sin ;cos ] (9.36) (Rc +Rs)[cos ; sin cos ;0] (9.37) P R = (Rc +Rs)[ cos ; sin cos ; sin sin ] (9.38) v = P RjP Rj = [cos ;sin cos ;sin sin ] (9.39) Hence, tc = R +Rsv (9.40) 8 where R( ) = " (Rc +Rs) cos ;Rc +Rscos sin Rs tan ;Rs # (9.41) tc = " Rc cos ;Rc sin cos +RS sin cos tan sin cos ! ; (9.42) Rs(1 sin sin ) # which simpli es to tc = " Rc cos ;Rc sin cos +Rs tan (sin sin 1);Rs(1 sin sin ) # (9.43) Notice that v is in the normal plane to the directrix: v R = 0 (9.44) where R = " (Rc +Rs) sin ;Rc +Rscos cos ;0 # (9.45) Hence, the generatrix is the arc of a great circle of the sphere on the plane tc R;tp R between tc and tp. The angle of the arc is = cos 1( e3 v) = cos 1(sin sin ) (9.46) in the local n;b system of the directrix. q(v; ) = Rs[sin vn cos vb] for v 2 [0;1] (9.47) where b = e3 (9.48) t = R jR j (9.49) n = e3 t (9.50) Setting = 2 u for u2 [0;1], the blending surface is: B(u;v) = R( (u)) + q(v; (u)) (9.51) Note that the surface is not a rational polynomial surface. This result generalizes to spherical blends of general surfaces. A schematic diagram of spherical blends of surfaces is shown in Figure 9.7. The implementation is procedural and involves intersections of o set surfaces [11, 10] to de ne the directrix and the projection of a point on a surface to de ne the generatrix [14]. 9 Offsets Intersection of offsets Figure 9.7: Spherical blends of surfaces 10 9.4 Blending of implicit algebraic surfaces For a detailed reference, see Ho mann and Hopcroft [8]. Given the implicit algebraic surfaces G;H de ned as: G(x;y;z) s = 0 H(x;y;z) t = 0 ) potential surfaces (9.52) de ne f(s;t) = 0, e.g: f(s;t) = b2s2 +a2t2 +a2b2 2ab2s 2a2bt+ 2 st (9.53) fs = 2sb2 2ab2 + 2 t (9.54) ft = 2ta2 2ba2 + 2 s (9.55) n = (fs;ft) (9.56) n(a;0) = [0;2 s 2ba2] == t (9.57) b(0;b) = [2 b 2ab2;0] == s (9.58) t s b a Also, f(a;0) = 2b2a2 2a2b2 = 0 (9.59) f(0;b) = 0 (9.60) or f = 0 is tangent to s axis at (a;0) (9.61) f = 0 is tangent to t axis at (0;b) (9.62) Theorem: f(G;H) = 0 is tangent to H = 0 on the curve G a = H = 0, and it is tangent to G = 0 on the curve H b = G = 0. Example: If G;H are quadrics, then the blend is quartic. Higher order continuity can be achieved by selecting appropriate f = 0. Note: For well-formed \elliptical blend" ab< <ab (circle for a = b and = 0). Applicability: Low order algebraics need ray tracing, and generally lack parametrization. 11 9.5 Blending as a boundary value problem 9.5.1 Introduction The motivation for blending surfaces is the need to generate a \secondary" surface as a bridge between primary surfaces, not just for manufacturing purpose, but also for functional, aesthetic, or design purposes. We can view this as a problem where: The boundaries are speci ed; The conditions to be met at the boundaries are also speci ed. We need to nd a smooth surface over some domain that satis es the boundary conditions. In other words, we want a smoothing or averaging process. The problem suggests itself as a boundary value problem in which an elliptic partial dif- ferential equation (PDE) needs to be solved subject to imposed boundary conditions. This approach was proposed and developed by Bloor and Wilson and their students at the Univer- sity of Leeds, UK, [2, 3, 4, 5]. Suppose L is a linear partial di erential operator over the domain shown in Figure 9.8. Lφ = f ? conditions on φ, φn etc. ?n Figure 9.8: Linear partial di erential operator. 12 9.5.2 Example: 2nd order (Laplace) equation (2-D) @ 2 @x2 + @2 @y2 r 2 = 0 (9.63) We can see this as averaging process from analysis. Analytic approach dl ? P φ = φ 0 2φ = 0 ? Figure 9.9: Analytic approach. p = 12 Z @ @G @n 0d‘ (9.64) where = 0 on @ , G is the Green’s function (source like) that satis es (see Figure 9.9): G = 0 on @ (9.65) Except at P, @2G = 0 in (9.66) G lnr at P (9.67) 13 Numerical approach h h X Y φ1 φ2 φ3 φ4 P Cover region with mesh Figure 9.10: Numerical approach. If we use nite di erences to solve Laplace’s equation, then (see Figure 9.10): p = 14( 1 + 2 + 3 + 4) (9.68) Another example PDE is the 4th order biharmonic equation: r4 = 0 (9.69) where r4 = r2(r2 ) = xxxx + 2 xxyy + yyyy which we do not study in these notes. 14 Numerical Example We now give a speci c numerical example, where x;y are independent variables, z is a depen- dent variable ( ), and 0 x 2 : 0 y 2. Z Y X2 2 semi?circles O Figure 9.11: Boundary conditions for Laplace equation example. Boundary conditions - function only (position) because PDE is 2nd order, see Figure 9.11. z = [1 (1 y)2]12 x = 0;0 y 2 (9.70) z = [14 (y 12)2]12 x = 2;0 y 1 (9.71) z = [14 (y 32)2]12 x = 2;1 y 2 (9.72) z = 0 y = 0y = 2 ) 0 x 2 (9.73) Limitations: inappropriate continuity at boundaries multi-valued surfaces would prove di cult (and involve awkward division of region). Higher order continuity =) higher order PDE. The function and 1st normal derivative ! 4th order (tangent plane continuity). The function and 1st and 2nd derivatives ! 6th order (curvature continuity). Rather than use physical coordinates (e.g. x;y) as independent variables, introduce para- metric coordinates u;v embedded in the surface with x;y;z as dependent variables. The surface given parametrically as: x = x(u;v) x = (x;y;z) (9.74) This mapping is determined as a solution to three boundary value problems (one for each coordinate). Note that this mapping is not given explicitly in terms of polynomials or B-splines. 15 Trimlines Primary surface Blend surface u = constant v = constant Physical space mapping Parametric space v u Figure 9.12: Typical blending problem. 16 9.5.3 Mapping { boundary value problem u = constant v= constant u = constant v=constant u = constant u = constant periodic in v Figure 9.13: Diagrammatic representation of trimlines for non-periodic and periodic cases. To determine the mapping we need to specify the partial di erential equation and the boundary conditions. Both depend on degree of continuity required in the blend. Position continuity We specify the value of function x at the boundary. Hence, we require 2nd order PDE. Consider a modi cation of the Laplacian operator: D2 = @ 2 @u2 +a 2 @ 2 @v2 (9.75) At this stage, restrict a to be a constant. This parameter controls relative \smoothing." To obtain the surface in parametric form (mapping), solve: D2x = 0 (9.76) (zero RHS in u;v space ( ) at this stage) subject to x given on boundary @ . Example u = 0 0 1 2pi v u Periodic in V Parameter space cylinder radius 1 z y x u = 1 is x + y = R (R>1) on plane z=0 2 22 R Figure 9.14: Cylinder and plane blending using PDE method. 17 We need x as a function of v on the trimlines. Parameterize on arc length: x(0;v) = 0 B@ cosvsinv H 1 CA x(1;v) = 0 B@ RcosvRsinv 0 1 CA (9.77) Solution by separation of variables: x = 0 BB B@ h coshau+ R coshasinha sinhau i cosv h coshau+ R coshasinha sinhau i sinv H(1 u) 1 CC CA (9.78) E ect of a For small a (see Figure 9.15): [coshau+ R coshasinha sinhau] 1 + (R 1)u+O(a2) (9.79) Figure 9.15: E ect of small a. For large a (see Figure 9.16): [coshau+ R coshasinha sinhau] e au +Rea(u 1) +O(e a) (9.80) Figure 9.16: E ect of large a. Note that for some value of a, the blend is tangent to the cylinder. In fact, this occurs for R = cosha. 18 Figure 9.17: Blends between circular cylinder and inclined plane, with continuity of slope between blend and primary surfaces. Adapted from Bloor and Wilson [2] 9.5.4 Position and tangent plane continuity We know the value of the function x at the boundary and also we know the normal to the surface at the boundary. With x = x(u;v) the normal is xu xv. Hence we impose a normal derivative condition at the boundary in u;v space. Hence, we use a 4th order PDE. In particular, solve D4x = 0 in (9.81) with x = xo on @ (9.82) xn = xno on @ (9.83) where xn is the directional partial derivative of x in the direction normal to the boundary, see Figure 9.18. 19 ? v u x(v) x (v)u x(u), x (u)v Figure 9.18: Normal derivative condition at the boundary. 20 9.5.5 Curvature continuity Surface curvature continuity has been studied theoretically, see Pegna and Wolter [13]. Pegna and Wolter derive a criterion for guaranteeing second-order smoothness or curvature continuity for blending surfaces. Curvature continuity across a linkage curve generally means that the normal curvatures agree in every direction at every point along the linkage curve. They prove the Linkage Curve Theorem which states that two surfaces joined with rst-order or tangent plane continuity along a rst-order continuous linkage curve can be shown to be second-order smooth if the normal curvatures on each surface agree in one direction other than the tangent direction to the linkage curve, see Figure 9.19. N t Figure 9.19: Condition for curvature continuity For a detailed review and a blending surface algorithm for G1 and G2 continuity, see Filkins [6]. 9.5.6 Multisided blending surfaces Blending surfaces do not have to be topologically quadrilateral in shape. The following gures illustrate these general blending surfaces. 21 Figure 9.20: Blends in geometric modelling [15] Figure 9.21: Generating n-sided patches with partial di erential equations [2] 22 Bibliography [1] L. Bardis and N. M. Patrikalakis. Blending rational B-spline surfaces. In Eurographics ’89, European Computer Graphics Conference and Exhibition, pages 453{462, Hamburg, F. R. of Germany, September 1989. [2] M. I. G. Bloor and M. J. Wilson. Generating blend surfaces using partial di erential equations. Computer-Aided Design, 21(3):165{171, 1989. [3] M. I. G. Bloor and M. J. Wilson. Representing pde surfaces in terms of b-splines. Computer-Aided Design, 22(6):324{330, July/August 1990. [4] M. I. G. Bloor and M. J. Wilson. Local control of surfaces generated as the solutions to partial di erential equations. Computers and Graphics, 18(2):161{169, 1994. [5] M. I. G. Bloor, M. J. Wilson, and H. Hagen. The smoothing properties of variational schemes. Computer Aided Geometric Design, 12(4):381{394, 1995. [6] P. C. Filkins, S. T. Tuohy, and N. M. Patrikalakis. Computational methods for blending surface approximation. Engineering with Computers, 9(1):49{61, 1993. [7] W. Hansmann. Interaktiver entwurf und geometrische Beschreibung Glatter Uberg ange zwischen r aumlich gekr ummten Fl achenstrukturen. PhD thesis, University of Hamburg, Germany, 1985. [8] C. Ho mann and J. Hopcroft. The potential method for blending surfaces and corners. In Geometric Modeling: Algorithms and New Trends, pages 347{365. SIAM, 1987. [9] J. Hoschek and D. Lasser. Fundamentals of Computer Aided Geometric Design. A. K. Peters, Wellesley, MA, 1993. Translated by L. L. Schumaker. [10] T. Maekawa. An overview of o set curves and surfaces. Computer-Aided Design, 31(3):165{173, March 1999. [11] T. Maekawa, W. Cho, and N. M. Patrikalakis. Computation of self-intersections of o sets of B ezier surface patches. Journal of Mechanical Design, Transactions of the ASME, 119(2):275{283, June 1997. [12] J. Pegna. Variable Sweep Geometric Modeling. PhD thesis, Stanford University, Stanford, CA, 1987. 23 [13] J. Pegna and F. E. Wolter. Geometrical criteria to guarantee curvature continuity of blend surfaces. Journal of Mechanical Design, Transactions of the ASME, 114(1):201{ 210, March 1992. [14] J. Pegna and F.-E. Wolter. Surface curve design by orthogonal projection of space curves onto free-form surfaces. Journal of Mechanical Design, ASME Transactions, 118(1):45{52, March 1996. [15] J. R. Woodwark. Blends in geometric modelling. In R. R. Martin, editor, The Mathematics of Surfaces II, pages 255{297. Clarendon Press, Oxford, 1987. 24