a degree n planar rational polynomial curve on the a, y plane. Its implicit equation is a degree n polynomial. The equation of the resulting conical ruled surface is x=x0(1-)+Xu +Yu (1-u) Eliminating u=1-2 and solving for x, r yields 0 This equation can be transformed to the standard form using a symbolic manipu- lation program as macsyma 2. Newton's method Solve ro To(u, u), yo= yo(u, U) and verify the third equation. Use a linear approxi- mation to start the process. Preprocessing using convex bounding box should always be used, coupled with some level of subdivision within a rectangular subdomain of the following function(see Figure 10 02U<1 or 3. Convex box and possibly subdivision followed by minimization in0 <u F(u,v)=R(u,t)-Ro2≥0 a point uo u0, vo)=0 yields Figure 10.10: Distance function squared In order to solve this minimization problem, we need to compute of F(u, u)(Fu= F,=0)in do
a degree n planar rational polynomial curve on the x, y plane. Its implicit equation f(x, y) = 0 is a degree n polynomial. The equation of the resulting conical ruled surface is x = x0(1 − u) + Xu y = y0(1 − u) + Y u z = z0(1 − u) Eliminating u = 1 − z z0 and solving for X, Y yields: f z0 z0 − z x − x0 z0 − z z, z0 z0 − z y − y0 z0 − z z = 0 This equation can be transformed to the standard form using a symbolic manipulation program such as Macsyma. 2. Newton’s method: Solve x0 = x0(u, v), y0 = y0(u, v) and verify the third equation. Use a linear approximation to start the process. Preprocessing using convex bounding box should always be used, coupled with some level of subdivision. 3. Convex box and possibly subdivision followed by minimization in 0 ≤ u, v ≤ 1 or within a rectangular subdomain of the following function (see Figure 10.10). F(u, v) = |R(u, v) − R0| 2 ≥ 0 A point u0, v0 where F(u0, v0) = 0 yields the solution. u v F(u,v) O Figure 10.10: Distance function squared In order to solve this minimization problem, we need to compute • Minimum of all local minima of F(u, v) (Fu = Fv = 0) in domain; 16
Minimum of all local minima of boundary "curves"eg. F(0, U)(i.e. Fu=0) Values of F(u, u) at corners, ie. F(0, 0), F(0, 1), F(1,0), F(1,1); and then choose uo, to from above solutions where F(uo, Uo)=0 The disadvantages of a minimization method are. (a) Initial approximation is required; (b) Possibility of divergence (c) No guarantee that all minima are located. (We need to enhance confidence by (d)First and second derivativers of F(a, u) are required Tote: When R= R(u, u) is a polynomial parametric surface patch, it is helpful to reformulate F(u, v)to F(u,0)=∑∑B1k(u)B3m(m) (10.7) If wi>0 for all i, j then there is no solution. We could use wi to construct initial approximations for the various local minima to be computed by usual descent numerical methods. These initial approximation may be obtained by discrete sampling or subdivi- SIc Let F(u, u) be expressed in the Bernstein basis, as in equation(10.7). Then, let us als press Fu, Fu in the Bernstein basis F(u,v)=∑∑AB1k-1(u)B3mn(v) F(u,0)=∑∑BBk(u)B1m-1()=0 (10.8) The equations Fu(u, v)=0 and F,(u, u)=0 represent planar algebraic curves illustrated in Figure 10. 11. Their intersection are the required extrema from which the minima can be selected using elementary calculus a geometrically motivated solution of the system 10.8 is possible using the convex hull property and subdivision to isolate an area where convex hulls intersect Taking G(u, u)= Fu(u, a) and n=k-l for example, we can write G(u,0)=∑∑A3B1n(u)B31m(v) i=0j=0 We can reformulate this "height" function into a parametric surface as follows w={u,,=∑∑LB,m(u)Bn() 17
• Minimum of all local minima of boundary “curves” eg. F(0, v) (i.e. Fv = 0); • Values of F(u, v) at corners, ie. F(0, 0), F(0, 1), F(1, 0), F(1, 1); and then choose u0, v0 from above solutions where F(u0, v0) = 0. The disadvantages of a minimization method are: (a) Initial approximation is required; (b) Possibility of divergence; (c) No guarantee that all minima are located. (We need to enhance confidence by subdivision.) (d) First and second derivativers of F(u, v) are required. Note: When R = R(u, v) is a polynomial parametric surface patch, it is helpful to reformulate F(u, v) to F(u, v) = X k i=0 Xm j=0 wijBi,k(u)Bj,m(n) (10.7) If wij > 0 for all i, j then there is no solution. We could use wij to construct initial approximations for the various local minima to be computed by usual descent numerical methods. These initial approximation may be obtained by discrete sampling or subdivision. Let F(u, v) be expressed in the Bernstein basis, as in equation (10.7). Then, let us also express Fu, Fv in the Bernstein basis: Fu(u, v) = k X−1 i=0 Xm j=0 AijBi,k−1(u)Bj,m(v) = 0 Fv(u, v) = X k i=0 mX−1 j=0 BijBi,k(u)Bj,m−1(v) = 0 (10.8) The equations Fu(u, v) = 0 and Fv(u, v) = 0 represent planar algebraic curves illustrated in Figure 10.11. Their intersection are the required extrema from which the minima can be selected using elementary calculus. A geometrically motivated solution of the system 10.8 is possible using the convex hull property and subdivision to isolate an area where convex hulls intersect. Taking G(u, v) = Fu(u, v) and n = k − 1 for example, we can write w = G(u, v) = Xn i=0 Xm j=0 AijBi,n(u)Bj,m(v) We can reformulate this “height” function into a parametric surface as follows: w = [u, v, G] = XXLijBi,m(u)Bj,n(v) Lij = [ i m , i n , Aij ] 17
F Figure 10.11: Intersection of algebraic curves 2 Figure 10.12: Control net To solve Fu= Fu=0, we find the projection of convex hulls of w(u, u) and of the sponding surface for Fy on the coordinate planes u=0, U=0, then intersect them with the lines w=0, see Figure 10.12 for an example. A more detailed description of this procedure is given in the next section where a nonlinear solver is described
v Fv = 0 Fu = 0 u 1 1 0 0 Figure 10.11: Intersection of algebraic curves. w=0 curve w=1−u −v 2 2 = 0 w u v 1 Figure 10.12: Control net To solve Fu = Fv = 0, we find the projection of convex hulls of w(u, v) and of the corresponding surface for Fv on the coordinate planes u = 0, v = 0 , then intersect them with the lines w = 0, see Figure 10.12 for an example. A more detailed description of this procedure is given in the next section where a nonlinear solver is described. 18
10.5. 3 Point/Procedural surface intersection a procedural surface may be an offset surface or a generalized cylinder surface or a blending surface. The typical solution method is minimization. In this case, no convex box assistance is possible in general, and we need a dense sampling for an initial approximation(which may be expensive)and no rigorous guarantees for the solutions reliability are generally available For certain classes of procedural surfaces such as offsets and evolutes of rational surfaces involving radicals of polynomials, it is possible to use the auxiliary variable method"to reduce the point to surface intersection (or minimum distance) problem to a set of (a larger number of) nonlinear polynomial equations. Such systems can be solved robustly and efficiently using the nonlinear solver describe in the next section
10.5.3 Point/Procedural surface intersection A procedural surface may be an offset surface or a generalized cylinder surface or a blending surface. The typical solution method is minimization. In this case, no convex box assistance is possible in general, and we need a dense sampling for an initial approximation (which may be expensive) and no rigorous guarantees for the solution’s reliability are generally available. For certain classes of procedural surfaces such as offsets and evolutes of rational surfaces involving radicals of polynomials, it is possible to use the “auxiliary variable method” to reduce the point to surface intersection (or minimum distance) problem to a set of (a larger number of) nonlinear polynomial equations. Such systems can be solved robustly and efficiently using the nonlinear solver describe in the next section. 19
10.6 Curve/curve intersection The curve types we will consider can be classified as follows: Rational polynomial parametric(RPP) Procedural parametric(PP) Implicit algebraic(IA) Implicit procedural (IP Procedural curves may be general offsets, evolutes, etc Curve to curve intersection cases are identified in table 10.1 RPP PPIA IF RPP D1 D2 D3 D4 PP D5D6D7 D8 D9 D10 Table 10.1: Curve to curve intersection cases Conceptually, D3(RPP/IA curve intersection) simplest"of the above cases of inter section to describe and use for illustrating various general difficulties of intersection problems 10.6.1 Case D3: RPP/IA curve intersection We start with a planar RPP curve(which is conceptually the simplest case) R()=(),m=(()Y(1 w(t)w(t) Rihi Bin(t) h Bin(t) 0<t<1 where hi>0 are weights and Bi n(t)are Bernstein basis functions The implicit algebraic curve fm(, y)=0 of total degree m is described by f(0)=∑∑ey For convenience, we convert it to homogeneous form, by setting =A, y=>and multiplying fm(X,Y, w) X 0
10.6 Curve/curve intersection The curve types we will consider can be classified as follows: • Rational polynomial parametric (RPP) • Procedural parametric (PP) • Implicit algebraic (IA) • Implicit procedural (IP) Procedural curves may be general offsets, evolutes, etc. Curve to curve intersection cases are identified in table 10.1. RPP PP IA IP RPP D1 D2 D3 D4 PP D5 D6 D7 IA D8 D9 IP D10 Table 10.1: Curve to curve intersection cases Conceptually, D3 (RPP/IA curve intersection) is the “simplest” of the above cases of intersection to describe and use for illustrating various general difficulties of intersection problems. 10.6.1 Case D3: RPP/IA curve intersection We start with a planar RPP curve (which is conceptually the simplest case). R(t) = [x(t), y(t)] = [ X(t) w(t) , Y (t) w(t) ] = Pn i=0 RihiBi,n(t) Pn i=0 hiBi,n(t) 0 ≤ t ≤ 1 where hi > 0 are weights and Bi,n(t) are Bernstein basis functions. The implicit algebraic curve fm(x, y) = 0 of total degree m is described by fm(x, y) = Xm i=0 mX−i j=0 cijx i y j = 0 For convenience, we convert it to homogeneous form, by setting x = X w , y = Y w and multiplying by w m, which leads to fm(X, Y, w) = Xm i=0 mX−i j=0 cijX iY jw m−i−j = 0 20