13472J/1.128J/2158J/16940J COMPUTATIONAL GEOMETRY Lectures 10-12 N.M. Patrikalakis Massachusetts Institute of Technology Cambridge MA 02139-4307 USA Copyright 2003 Massachusetts Institute of Technology Contents 10.1 Overview of intersection problems 10.2 Intersection problem classification 5 10. 2. 1 Classification by dimension 10.2.2 Classification by type of geometr 10.2.3 Classification by number system 6 10.3 Point /point"intersection 7 10.4 Point/curve intersection 10.4.1 Point/Implicit curve intersection 10.4.2 Point /Parametric curve intersection 10.4.3 Point/Procedural parametric (offset, evolute, etc. curve intersection 10.5 Point /surface intersection 10.5.1 Point/Implicit(usually algebraic)surface intersection 10.5.2 Point/Rational polynomial surface intersection 13 10.5.3 Point /Procedural surface intersection 10.6 Curve/curve intersection 20 10.6.1 Case D3: RPP/IA curve intersection 10.6.2 Case D1: RPP/RPP Curve Intersection 10.6.3 Case D2 /D5: RPP/PP and PP/PP Curve Intersections 10.6.4 Case D6: PP/IA Curve Intersection 10.6.5 Case D8: IA/IA Curve Intersection 10.7 Curve/ surface intersection 10.7. 1 Case E3: RPP Curve/IA Surface Intersection 10.7.2 Case El: RPP Curve/RPP Surface Intersection 10.7.3 Case E2/E6: RPP/PP, PP/PP Curve/Surface Intersection 10.7.4 Case E7: PP Curve/IA Surface Intersection
13.472J/1.128J/2.158J/16.940J COMPUTATIONAL GEOMETRY Lectures 10 - 12 N. M. Patrikalakis Massachusetts Institute of Technology Cambridge, MA 02139-4307, USA Copyright c 2003 Massachusetts Institute of Technology Contents 10.1 Overview of intersection problems . . . . . . . . . . . . . . . . . . . . . . . . . 3 10.2 Intersection problem classification . . . . . . . . . . . . . . . . . . . . . . . . . 5 10.2.1 Classification by dimension . . . . . . . . . . . . . . . . . . . . . . . . 5 10.2.2 Classification by type of geometry . . . . . . . . . . . . . . . . . . . . . 5 10.2.3 Classification by number system . . . . . . . . . . . . . . . . . . . . . . 6 10.3 Point/point “intersection” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 10.4 Point/curve intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 10.4.1 Point/Implicit curve intersection . . . . . . . . . . . . . . . . . . . . . 8 10.4.2 Point/Parametric curve intersection . . . . . . . . . . . . . . . . . . . . 10 10.4.3 Point/Procedural parametric (offset, evolute, etc.) curve intersection . 12 10.5 Point/surface intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 10.5.1 Point/Implicit (usually algebraic) surface intersection . . . . . . . . . . 13 10.5.2 Point/Rational polynomial surface intersection . . . . . . . . . . . . . . 13 10.5.3 Point/Procedural surface intersection . . . . . . . . . . . . . . . . . . . 19 10.6 Curve/curve intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 10.6.1 Case D3: RPP/IA curve intersection . . . . . . . . . . . . . . . . . . . 20 10.6.2 Case D1: RPP/RPP Curve Intersection . . . . . . . . . . . . . . . . . 27 10.6.3 Case D2/D5: RPP/PP and PP/PP Curve Intersections . . . . . . . . . 28 10.6.4 Case D6: PP/IA Curve Intersection . . . . . . . . . . . . . . . . . . . . 28 10.6.5 Case D8: IA/IA Curve Intersection . . . . . . . . . . . . . . . . . . . . 29 10.7 Curve/surface intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 10.7.1 Case E3: RPP Curve/IA Surface Intersection . . . . . . . . . . . . . . 30 10.7.2 Case E1: RPP Curve/RPP Surface Intersection . . . . . . . . . . . . . 31 10.7.3 Case E2/E6: RPP/PP, PP/PP Curve/Surface Intersection . . . . . . . 31 10.7.4 Case E7: PP Curve/IA Surface Intersection . . . . . . . . . . . . . . . 31 1
10.7.5 Case Ell: IA Curve/IA Surface Intersection 10.7.6 IA Curve/RPP Surface Intersection 10.8 Surface/Surface Intersections 2333 10.8.1 Case F3: RPP/IA Surface Intersection 10.8.2 Case F1: RPP/RPP Surface Intersection 10.8.3 Case F8: IA/IA Surface Intersection 10.9 Nonlinear Solvers 51 10.9.1 Motivation 10.1OLocal Solution Methods 10.11 Classification of Global Solution Methods 10.12Subdivision Method(Projected Polyhedron Method) 10.13Interval Method 10.13.1 Motivation 60 10.132 Definitions 10. 13. 3 Interval Arithmetic 62 10.13.4 Algebraic Properties 10. 13.5 Rounded Interval Arithmetic and its Implementati 10. 14Interval Projected Polyhedron Algorithm 10.15Interval Newton method Bibliography Reading in the Textbook Chapters 4 and 5, pp. 73-160
10.7.5 Case E11: IA Curve/IA Surface Intersection . . . . . . . . . . . . . . . 32 10.7.6 IA Curve/RPP Surface Intersection . . . . . . . . . . . . . . . . . . . . 33 10.8 Surface/Surface Intersections . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 10.8.1 Case F3: RPP/IA Surface Intersection . . . . . . . . . . . . . . . . . . 34 10.8.2 Case F1: RPP/RPP Surface Intersection . . . . . . . . . . . . . . . . . 42 10.8.3 Case F8: IA/IA Surface Intersection . . . . . . . . . . . . . . . . . . . 46 10.9 Nonlinear Solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 10.9.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 10.10Local Solution Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 10.11Classification of Global Solution Methods . . . . . . . . . . . . . . . . . . . . . 54 10.12Subdivision Method (Projected Polyhedron Method) . . . . . . . . . . . . . . 55 10.13Interval Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 10.13.1Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 10.13.2Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 10.13.3 Interval Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 10.13.4Algebraic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 10.13.5Rounded Interval Arithmetic and its Implementation . . . . . . . . . . 62 10.14Interval Projected Polyhedron Algorithm . . . . . . . . . . . . . . . . . . . . . 65 10.15Interval Newton method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Bibliography 72 Reading in the Textbook • Chapters 4 and 5, pp. 73 - 160 2
Lectures 10-12 Intersection Problems, Nonlinear Solvers and robustness issues 10.1 Overview of intersection problems Intersections are fundamental in computational geometry, geometric modeling and design analysis and manufacturing applications. Examples of intersection problems include Shape interrogation(eg. visualization) through contouring (intersection with a series of parallel planes, coaxial cylinders, and cones etc. Numerical control machining (milling) involving intersection of offset surfaces with a series of parallel planes, to create machining paths for ball(spherical) cutters Representation of complex geometries in the "Boundary Representation"scheme; for example, the description of the internal geometry and of structural members cars airplanes, ships, etc, involves Intersections of free-form parametric surfaces with low order algebraic surfaces planes, quadrics, torii Intersections of low order algebraic surfaces in a process called boundary evaluation, in which the Boundary Representation is cre- ated by "evaluating " the Constructive Solid Geometry model of the object. during this process, intersections of the surfaces of primitives(see Figure 10.1)must be found during Boolean operations Boolean opertations on point sets A, B include(see Figure 10.2) Union:A∪B . Intersection: An B. and Difference:A-B 3
Lectures 10 - 12 Intersection Problems, Nonlinear Solvers and Robustness Issues 10.1 Overview of intersection problems Intersections are fundamental in computational geometry, geometric modeling and design, analysis and manufacturing applications. Examples of intersection problems include: • Shape interrogation (eg. visualization) through contouring (intersection with a series of parallel planes, coaxial cylinders, and cones etc.) • Numerical control machining (milling) involving intersection of offset surfaces with a series of parallel planes, to create machining paths for ball (spherical) cutters. • Representation of complex geometries in the “Boundary Representation” scheme; for example, the description of the internal geometry and of structural members of cars, airplanes, ships, etc, involves – Intersections of free-form parametric surfaces with low order algebraic surfaces (planes, quadrics, torii). – Intersections of low order algebraic surfaces. in a process called boundary evaluation, in which the Boundary Representation is created by “evaluating” the Constructive Solid Geometry model of the object. During this process, intersections of the surfaces of primitives (see Figure 10.1) must be found during Boolean operations. Boolean opertations on point sets A, B include (see Figure 10.2) • Union: A ∪ B, • Intersection: A ∩ B, and • Difference: A − B. 3
Figure 10.1: Primitive solids →→→ Figure 10.2: Example of a Boolean operation: union All such operations involve intersections of surfaces to surfaces. In order to solve general surface to surface intersection problems, the following auxiliary intersection problems(similar to distance computation problems used in CAM for inspection of manufactured objects) need to be considered point/point(P/P) point /curve(P/C) point/surface(P/s) curve/ curve(C/c) curve/surface(C/S) All above types of intersection problems are also useful in geometric modeling, robotics collision avoidance. manufacturing simulation scientific visualization etc When the geometric elements involved in intersections are nonlinear(curved), intersection problems typically reduce to solving complex systems of nonlinear equations, which may be either polynomial or more general in character. Solution of nonlinear systems is a very com plex process in general in numerical analysis and there are specialized textbooks on the topic However, geometric modeling applications pose severe robustness, accuracy, automation, and efficiency requirements on solvers of a nonlinear systems as we will see later. Therefore, geo- metric modeling researchers have developed specialized solvers to address these requirements explicitly using geometric formulations
Figure 10.1: Primitive solids. ⇒ ⇒ ⇒ Figure 10.2: Example of a Boolean operation: union. All such operations involve intersections of surfaces to surfaces. In order to solve general surface to surface intersection problems, the following auxiliary intersection problems (similar to distance computation problems used in CAM for inspection of manufactured objects) need to be considered • point/point (P/P) • point/curve (P/C) • point/surface (P/S) • curve/curve (C/C) • curve/surface (C/S) All above types of intersection problems are also useful in geometric modeling, robotics, collision avoidance, manufacturing simulation, scientific visualization, etc. When the geometric elements involved in intersections are nonlinear (curved), intersection problems typically reduce to solving complex systems of nonlinear equations, which may be either polynomial or more general in character. Solution of nonlinear systems is a very complex process in general in numerical analysis and there are specialized textbooks on the topic. However, geometric modeling applications pose severe robustness, accuracy, automation, and efficiency requirements on solvers of a nonlinear systems as we will see later. Therefore, geometric modeling researchers have developed specialized solvers to address these requirements explicitly using geometric formulations. 4
10.2 Intersection problem classification Intersection problems can be classified according to the dimension of the problems and ac- cording to the type of geometric equations involved in defining the various geometric elements (points, curves and surfaces). The solution of intersection problems can also vary according to the number system in which the input is expressed and the solution algorithm is implemented 10.2.1 Classification by dimension /P, P/C, P/S /C, C/S S/S 10.2.2 Classification by type of geometry Parametric Implicit (eg. R=R(t) (eg.f(x,y)=0.,z=0) Rational Procedural Polynomial (algebraic) Figure 10.3: Curve geometry classification 1. Points plicit: R= Ro; R y, Procedural: Intersection of two procedural curves, procedural curve and surface, or three procedure surfaces, eg. offset or blending surfaces Algebraic: f(R)=g(R)=h(r)=0; where f, 9, and h are polynomials A classification of curves is illustrated in Figure 10.3 ● aranetrio R=R(t)A≤t≤B (a) Rational Polynomials(eg: NURBS, rational Bezier) (b)Procedural, eg: offsets, evolutes, ie. the locus of the centers of curvature of Implicit: These require solution of (usually nonlinear)equations
10.2 Intersection problem classification Intersection problems can be classified according to the dimension of the problems and according to the type of geometric equations involved in defining the various geometric elements (points, curves and surfaces). The solution of intersection problems can also vary according to the number system in which the input is expressed and the solution algorithm is implemented. 10.2.1 Classification by dimension • P/P, P/C, P/S • C/C, C/S • S/S 10.2.2 Classification by type of geometry polynomial Procedural Polynomial (algebraic) (eg. f(x, y) = 0, z = 0) Implicit Rational Parametric (eg. R = R(t) ) Figure 10.3: Curve geometry classification 1. Points • Explicit: R = R0; R = [x, y, z] • Procedural: Intersection of two procedural curves, procedural curve and surface, or three procedure surfaces, eg. offset or blending surfaces. • Algebraic: f(R) = g(R) = h(R) = 0; where f, g, and h are polynomials. 2. Curves A classification of curves is illustrated in Figure 10.3. • Parametric: R = R(t) A ≤ t ≤ B (a) Rational Polynomials (eg: NURBS, rational B´ezier). (b) Procedural, eg: offsets, evolutes, ie. the locus of the centers of curvature of a curve. • Implicit: These require solution of (usually nonlinear) equations 5