which can be rewritten in matrix form as follows b o Co-r Co-y bo 0000 0 Co-y a」Lt3 The maximum degree of t in the above vector is determined by the degree m of the r polynomial and the degree n of the y polynomial, and is given by m+n-1. In this case m+n-1=3 A necessary and sufficient condition for the above system to be solvable is b 0 f(a, y) Co-y bo The equation f(, y)=0 is the implicit equation of the curve. Consequently in an exact arithmetic context, we need to check if f(o, yo)=0, to verify if(o, yo)is on In general, if x=x(t"),y=y(t")→F(x",y")=0 where n is the total degree Inversion: If f(a, y)=0 then we could use the first 3 equations 10.4 o bo ba0」Lt3 v(x0,30) Where o and y are polynomials in to and yo, and To, yo satisfy f(xo,3o)=0 The method is efficient and (usually) accurate for n 3(but no real guaran- tees on accuracy and robustness exist if the method is implemented in Hoating point) Subdivision methods are preferable for higher n, and as we will see later when coupled with rounded interval arithmetic are robust, accurate and efficient Intersection of points(o, yo, zo) and 3D polynomial curves R=R(t) via implicit ivolves a process of projection on y plane and finding to by inversion and verification of z0=i(to) 11
which can be rewritten in matrix form as follows: ⇒ c0 − x b0 a0 0 0 c0 − x b0 a0 c 0 0 − y b 0 0 a 0 0 0 0 c 0 0 − y b 0 0 a 0 0 1 t t 2 t 3 = 0 0 0 0 (10.4) The maximum degree of t in the above vector is determined by the degree m of the x polynomial and the degree n of the y polynomial, and is given by m + n − 1. In this case m + n − 1 = 3. A necessary and sufficient condition for the above system to be solvable is c0 − x b0 a0 0 0 c0 − x b0 a0 c 0 0 − y b 0 0 a 0 0 0 0 c 0 0 − y b 0 0 a 0 0 = f(x, y) = 0 The equation f(x, y) = 0 is the implicit equation of the curve. Consequently in an exact arithmetic context, we need to check if f(x0, y0) = 0, to verify if (x0, y0) is on the initial curve. In general, if x = x(t n ), y = y(t n ) ⇒ F(x n , y n ) = 0 where n is the total degree. • Inversion: If f(x, y) = 0 then we could use the first 3 equations 10.4: b0 a0 0 c0 − x0 b0 a0 b 0 0 a 0 0 0 t t 2 t 3 = − c0 − x0 0 c 0 0 − y0 ⇒ t = φ(x0, y0) ψ(x0, y0) Where φ and ψ are polynomials in x0 and y0, and x0, y0 satisfy f(x0, y0) = 0 – The method is efficient and (usually) accurate for n ≤ 3 (but no real guarantees on accuracy and robustness exist if the method is implemented in floating point). – Subdivision methods are preferable for higher n, and as we will see later when coupled with rounded interval arithmetic are robust, accurate and efficient. Intersection of points (x0, y0, z0) and 3D polynomial curves R = R(t) via implicitization of such curves involves a process of projection on x, y plane and finding t0 by inversion and verification of z0 = z(t0). 11
10.4.3 Point/Procedural parametric (offset, evolute, etc. ) curve intersection Ro∩R=R(t)A≤t≤B In general there is no known and easily computable convex box decreasing arbitrarily with subdivision! An approximate solution method may involve minimization of F(t=R(t-R where tE [A, B]. This would involve Checking end points, ie. if F(A), F(B) are very small - Initial estimate for the possible minima, perhaps using linear approximation of r(t) to start the process However Convergence of the above minimization processes is not guaranteed in general There may exist more than one minima Convergence to local and not global minimum(where F(t)+0)is possible For certain classes of procedural curves such as offsets and evolutes of rational curves involving radicals of polynomials, it is possible to use the"auxiliary variable method"to reduce the point to curve 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 12
10.4.3 Point/Procedural parametric (offset, evolute, etc.) curve intersection R0 ∩ R = R(t) A ≤ t ≤ B • In general there is no known and easily computable convex box decreasing arbitrarily with subdivision! • An approximate solution method may involve minimization of F(t) = |R(t) − R| 2 where t ∈ [A, B]. This would involve – Checking end points, ie. if F(A), F(B) are very small. – Initial estimate for the possible minima, perhaps using linear approximation of R(t) to start the process. However, – Convergence of the above minimization processes is not guaranteed in general. – There may exist more than one minima. – Convergence to local and not global minimum (where F(t) 6= 0 ) is possible. For certain classes of procedural curves such as offsets and evolutes of rational curves involving radicals of polynomials, it is possible to use the “auxiliary variable method” to reduce the point to curve 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. 12
10.5 Point/surface intersection 10.5.1 Point/Implicit(usually algebraic) surface intersection The condition for Ro ntf(r)=0F, where f(R)=0 is an implicit surface If(Ro)/<6,(Ro)l vf(ro) where 6, d are small constants 10.5.2 Point/Rational polynomial surface intersection 1. Implicitization is possible for all such surfaces but computationally expensive and possi bly inaccurate. For a tensor product rational polynomial surface with maximum degrees in u and v equal to m and n, of the form R=R(u,2), the implicit equation is f(x9,y9,29)=0 here q≤2m Therefore,form=m=3→q≤18,m=m=2→q≤8 The above method is useful for special surfaces such as cylindrical and conical ruled surfaces. surfaces of revolution, etc Example (a)Implicitization of a surface of revolution R(t) igure 10.7: Surface of revolution
10.5 Point/surface intersection 10.5.1 Point/Implicit (usually algebraic) surface intersection The condition for R0 ∩ {f(R) = 0}, where f(R) = 0 is an implicit surface, is: |f(R0)| < , |f(R0)| | 5 f(R0)| < δ where , δ are small constants. 10.5.2 Point/Rational polynomial surface intersection 1. Implicitization is possible for all such surfaces but computationally expensive and possibly inaccurate. For a tensor product rational polynomial surface with maximum degrees in u and v equal to m and n, of the form R = R(u m, v n ), the implicit equation is f(x q , y q , z q ) = 0 where q ≤ 2mn Therefore, for m = n = 3 −→ q ≤ 18, m = n = 2 −→ q ≤ 8 The above method is useful for special surfaces such as cylindrical and conical ruled surfaces, surfaces of revolution, etc. Examples: (a) Implicitization of a surface of revolution. y x z r r R(t) Figure 10.7: Surface of revolution. 13
Let us consider a profile curve to be a rational polynomial of degree n, see Figure 10.7 R(t)=[r(t),2(t) By simple implicitization of R=R(t), we get fn(r,2)=0 where n is the maximum total degree of f. Also, 10.6 Next we eliminate r from equations 10.5-10.6 by rewriting equations 10.5-10.6 as follows fn(;,2)=a0(2)rn+a1(2)r2-1+…+an(2)=0 r2+(x2+y2)=0 The resultant of eliminating r from these two equations is 之)a 1(2)an(z) 0 an-2(2)an-1(2)an(z) 0 0 and the degree of D= f(a, y, 2)=0 is 2n. An example is a torus(degree 4 algebraic (b) Implicitization of a cylindrical ruled surface igure 10.8: Cylindrical ruled surface
Let us consider a profile curve to be a rational polynomial of degree n, see Figure 10.7 R(t) = [r(t), z(t)] By simple implicitization of R = R(t), we get: fn(r, z) = 0 (10.5) where n is the maximum total degree of f. Also, r 2 = x 2 + y 2 (10.6) Next we eliminate r from equations 10.5 - 10.6 by rewriting equations 10.5 - 10.6 as follows: fn(r, z) = a0(z)r n + a1(z)r n−1 + · · · + an(z) = 0 ⇒ −r 2 + (x 2 + y 2 ) = 0 The resultant of eliminating r from these two equations is D = a0(z) a1(z) · · · an−1(z) an(z) 0 0 a0(z) · · · an−2(z) an−1(z) an(z) −1 0 x 2 + y 2 · · · −1 0 x 2 + y 2 . . . −1 0 x 2 + y 2 = 0 and the degree of D ≡ f(x, y, z) = 0 is 2n. An example is a torus (degree 4 algebraic surface). (b) Implicitization of a cylindrical ruled surface x y nˆ R(t) tˆ a z Figure 10.8: Cylindrical ruled surface. 14
be a degree n planar rational polynomial curve in the x, y plane. The resulting implicit equation of the curve f(X,Y)=0 is a polynomial of degree n. Let a={a1,a2,a be a direction vector. Then the three equations X+ual describe a cylindrical ruled surface. Hence, the implicit surface equation becomes: 了3 This equation can be transformed to the standard form using a symbolic manipu lation program such as Macsyma (c) Implicitization of a conical ruled surface Figure 10.9: Conical ruled surface be the apex of the conical ruled surface and R(t)=[X(t),Y(t) 15
Let R(t) = [X(t), Y (t)] be a degree n planar rational polynomial curve in the x, y plane. The resulting implicit equation of the curve f(X, Y ) = 0 is a polynomial of degree n. Let a = [a1, a2, a3] be a direction vector. Then the three equations x = X + ua1 y = Y + ua2 z = ua3 describe a cylindrical ruled surface. Hence, the implicit surface equation becomes: f(x − z a3 a1, y − z a3 a2) = 0 This equation can be transformed to the standard form using a symbolic manipulation program such as Macsyma. (c) Implicitization of a conical ruled surface x y z R(t) u R0 tˆ Figure 10.9: Conical ruled surface. Let R0 = [x0, y0, z0] be the apex of the conical ruled surface and R(t) = [X(t), Y (t)] 15