Objectives and Features
Shape interrogation is the process of extraction of information from a geometric model. Shape interrogation is a fundamental component of Computer Aided Design and Manufacturing (CAD/CAM) systems and was first used in such context by M. Sabin, one of the pioneers of CAD/CAM, in the late sixties. The term surface interrogation has been used by I. Braid and A. Geisow in the same context. An alternate term nearly equivalent to shape interrogation is geometry processing first used by R. E. Barnhill, another pioneer of this field. In this book we focus on shape interrogation of geometric models bounded by free-form surfaces. Free-form surfaces, also called sculptured surfaces, are widely used in scientific and engineering applications. For example, the hydrodynamic shape of propeller blades has an important role in marine applications, and the aerodynamic shape of turbine blades determines the performance of aircraft engines. Free-form surfaces arise also in the bodies of ships, automobiles and aircraft, which have both functionality and attractive shape requirements. Many electronic devices as well as consumer products are designed with aesthetic shapes, which involve free-form surfaces.
When engineers or stylists design geometric models bounded by free-form surfaces, they need tools for shape interrogation to check whether the designed object satisfies the functionality and aesthetic shape requirements. This book provides the mathematical fundamentals as well as algorithms for various shape interrogation methods including nonlinear polynomial solvers, intersection problems, differential geometry of intersection curves, distance functions, curve and surface interrogation, umbilics and lines of curvature, geodesics, and offset curves and surfaces.
The book can serve as a textbook for teaching advanced topics of geometric modeling for graduate students as well as professionals in industry. It has been used as one of the textbooks for the graduate course ``Computational Geometry'' at the Massachusetts Institute of Technology (MIT). Currently there are several excellent books in the area of geometric modeling and in the area of solid modeling. This book provides a bridge between these two areas. Apart from the differential geometry topics covered, the entire book is based on the unifying concept of recasting all shape interrogation problems to the solution of a nonlinear system.
Structure and Outline
Chapter 1 presents a brief overview of analytical methods for the representation of curves and surfaces in a computer environment. We focus on the parametric representation of curves and surfaces, commonly used in CAD systems for shape specification. We next review the theory of Bernstein polynomials and associated algorithms and their application in the definition and manipulation of Bézier curves and surface patches. Finally in this chapter, we review the theory of B-spline basis functions and associated algorithms and their application in the definition and manipulation of B-spline and Non-Uniform Rational B-spline curves and surface patches. In our development of Bernstein polynomials and B-spline basis functions and the associated curve and surface representations, we do not provide detailed proofs as they are already contained in other existing books on geometric modeling, on which we rely for instructional purposes.
Chapters 2 and 3 provide an overview and introduction into the classical elementary differential geometry of explicit, parametric and implicit curves and surfaces, necessary for the development of the more advanced differential geometry topics that are presented in Chaps. 6, 8, 9 and 10. Much of the material of Chaps. 2 and 3 (except the treatment of curvatures of implicit surfaces) can be generally found in various forms in existing books on differential geometry and is included for convenience of the reader and completeness of our development.
Chapter 4 focuses on the development of geometrically motivated solvers for nonlinear equation systems and the related numerical robustness (reliability) issues. Much of the shape interrogation problems defined and solved in this book can be reduced to solving systems of n nonlinear polynomial equations in l unknowns, each of which varies within a known interval. Much of the development is based on the Interval Projected Polyhedron (IPP) algorithm, developed in our Design Laboratory at MIT in the early nineties. Some shape interrogation problems involve more general nonlinear functions including radicals of polynomials. These are also converted to nonlinear polynomial systems of higher dimensionality via an auxiliary variable method. The fundamental feature of the IPP algorithm is that it allows recasting of continuous shape interrogation problems encountered in geometric modeling and processing of free-form shapes into the discrete problem of computing convex hulls of a set of points in a plane and their intersections with other convex hulls along a particular axis. In this way, a bridge between the largely disparate fields of geometric modeling of free-form shapes (largely based on numerical analysis and approximation theory) and discrete computational geometry (largely based on the theory of algorithms and combinatorics) is established. Another fundamental feature of the IPP algorithm, is the use of rounded interval arithmetic motivated by questions of numerical robustness or reliability, which have high importance in CAD/CAM systems. Interval methods are a special branch of numerical analysis, with great potential for applications in geometric modeling and processing problems. Interval methods have not yet been used extensively in practice, because, if they are applied naively, they lead to interval growth that reduces the possible achievable precision in a numerical computation. However, when combined with geometric modeling algorithms based on convex combinations (as the de Casteljau algorithm), they lead to very minor interval growth and permit effective and high accuracy solutions in practice. The IPP algorithm robustly eliminates subregions of the domain which do not contain roots, thereby allowing effective bracketing of the roots of the nonlinear system within a given box with size typically much smaller than the actual accuracy of the results of current CAD/CAM systems.
Chapter 5 presents the first major shape interrogation problem analyzed in this book. Intersection is a fundamental operation in the creation of geometric models encoded in the Boundary Representation form of solid modeling. Intersection is also very useful in geometric processing for visualization, analysis and manufacturing of solid models. We present a unified methodology for solving intersection problems, which reduces all such problems to solving a system of nonlinear polynomial equations which in turn can be solved using the method of Chap. 4. We also present a novel classification of intersection problems by virtue of their dimensionality, the type of geometric representations involved, and the number system used in problem statement and solution. The point to point, point to curve, point to surface, curve to curve, curve to surface and surface to surface intersection problems are treated in some detail. Various special cases of interest, where the geometric entities involved (points, curves and surfaces) are represented implicitly or parametrically in terms of polynomials, are treated in some depth.
Chapter 6 is motivated by efficient tracing of intersection curves of two surfaces which intersect either transversely or tangentially, and presents the first, second and higher order derivatives of these entities for use in developing efficient and robust tracing algorithms. The surfaces involved may be parametric or implicit in any combination.
Chapter 7 presents methods for the computation of the stationary points of distance functions between points, parametric curves and parametric surface patches (in any combination). The curves and surfaces may be defined by general piecewise rational polynomials. The resulting problems are again reduced to solving systems of nonlinear equations which can be solved using the IPP algorithm developed in Chap. 4. Distance functions are closely related to intersection problems and are also useful in many other applications including feature recognition via medial axis transforms, animation, collision detection, and manufactured object localization and inspection.
Chapter 8 addresses a variety of curve and surface interrogation methods involving their position vectors and several higher order derivatives. Particular emphasis is placed on robust extraction of stationary points of curvature maps and the consequent application in robust contouring of such maps. Again the problem reduces to solving systems of nonlinear equations which can be solved using the IPP algorithm developed in Chap. 4. The interrogation methods analyzed in this chapter have many applications in aesthetic and functional surface design and analysis, in fairing of oscillatory shapes, in meshing of surface patches and in machining automation.
Chapter 9 discusses the problems of umbilics and lines of curvature as methods of shape interrogation and identification. Umbilics are computed via solution of a nonlinear polynomial system following the IPP algorithm of Chap. 4. Curvature lines are computed via integration of a system of differential equations via an adaptive numerical process with specialized treatment near umbilics. The stability problem of umbilics under perturbation of the underlying surface is also analyzed for use in surface identification and feature recognition problems.
Chapter 10 addresses yet another shape interrogation problem involving the geodesics of parametric and implicit surfaces. The classical geodesic equations are reviewed and numerical methods for the effective computation of geodesics between two points on a surface or a point and a curve on a surface are presented. The numerical methods involve iterative solution of a nonlinear boundary value problem via either shooting or relaxation methods. Geodesics have applications in feature recognition via medial axis transforms, in path planning in robotics (for distance minimization), in representation of geodesic offsets for design and in manufacturing.
Chapter 11, the final chapter of this book, focuses on the problem of offset (or parallel) curves and surfaces. Offsets have important applications in NC machining, feature recognition via medial axis transforms and in tolerance region specification. The definition and computation of singularities (and especially self-intersections) of planar offset curves and offset surfaces is treated in depth. The methods developed are in part analytical, and in part numerical relying on the IPP algorithm of Chap. 4 and on integration of systems of nonlinear differential equations. The related concepts of Pythagorean hodographs, general offsets and pipe surfaces, which build on the theory of offset curves and surfaces, are also reviewed and analyzed in some detail.
Problems that instructors can use in developing their own courses are provided immediately after Chapter 11. Many of these problems have been used in our graduate course at MIT.
Software Package: At the end of this hyperbook edition, we provide geometric modeling libraries and programs in C/C++ to implement some of the key algorithms described in this book. These source codes include many fundamental algorithms for shape interrogation in CAD/CAM.
Errors
A book of this size is likely to contain omissions and errors. If you have any constructive suggestions or find errors, please communicate them to N. M. Patrikalakis, MIT Room 5-230A, 77 Massachusetts Avenue, Cambridge, MA 02139-4307, USA (e-mail: nmp@mit.edu); T. Maekawa, Yokohama National University, 79-5 Tokiwadai, Hodogaya, Yokohama 240-8501, Japan (e-mail: maekawa@ynu.ac.jp); and W. Cho, MIT Room 5-426, 77 Massachusetts Avenue, Cambridge, MA 02139-4307, USA (e-mail: wjcho@mit.edu).
Acknowledgements
We wish to recognize the following former and current students who have helped in the development of this book: Panos G. Alourdas, Christian Bliek, Julie S. Chalfant, Donald G. Danmeier, H. Nebi Gursoy, Andreas Hofman, Chun-Yi Hu, Todd R. Jackson, Kwang H. Ko, George A. Kriezis, Hongye Liu, John G. Nace, P. V. Prakash, Guoling Shen, Evan C. Sherbrooke, Stephen Smyth, Krishnan Sriram, Seamus T. Tuohy, Marsette A. Vona, Guoxin Yu and Jingfang Zhou. We also wish to acknowledge Stephen L. Abrams for his assistance with software development and Fred Baker for editorial assistance.
We also thank Chryssostomos Chryssostomidis, David C. Gossard, Malcolm Sabin, Takis Sakkalis, Nickolas S. Sapidis, Franz-Erich Wolter and Xiuzi Ye and several anonymous referees selected by Springer for useful discussions and their comments.
We also wish to acknowledge MIT's funding of this book development (first paper edition) from the Bernard M. Gordon Engineering Curriculum Development Fund via the Dean of the School of Engineering and via additional support from the Department of Ocean Engineering. The development of the second edition of this book in the form of a hyperbook was supported by the Pappalardo Book Series in Mechanical Engineering administered by the MIT Department of Mechanical Engineering and this support is also gratefully acknowledged.
Nicholas M. Patrikalakis,
Takashi Maekawa,
Wonjoon Cho,
December 2009.