An Integrated Introduction to Computer Graphics and Geometric Modeling An Integrated Introduction to Computer Graphics and Geometric Modeling Ronald Goldman Boca Raton London New York CRC Press is an imprint of the Taylor & Francis Group, an informa business A CHAPMAN & HALL BOOK CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2009 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U. Government works Version Date: 20131121 International Standard Book Number-13: 978-1-4398-0335-6 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the valid- ity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained.
If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or uti- lized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopy- ing, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.com (http:// www.com/) or contact the Copyright Clearance Center, Inc.
(CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe.
Visit the Taylor & Francis Web site at http://www.com and the CRC Press Web site at http://www.com Contents Foreword xv Dedication xvii Preface xix Author xxix I Two-Dimensional Computer Graphics: From Common Curves to Intricate Fractals 1 Turtle Graphics. 9 2 Fractals from Recursive Turtle Programs .3 Fractal Curves and Recursive Turtle Programs .4 Summary: Fractals—Recursion Made Visible. 23 3 Some Strange Properties of Fractal Curves.2 Computing Fractal Dimension from Recursive Turtle Programs .1 Base Cases for the Sierpinski Gasket .2 Base Cases for the Koch Curve. 37 v vi Contents 4 Affine Transformations .3 The Algebra of Affine Transformations .4 The Geometry of Affine Transformations .5 Affine Coordinates and Affine Matrices.6 Conformal Transformations: Revisited.7 General Affine Transformations .1 Image of One Point and Two Lineary Independent Vectors.3 Image of Three Noncollinear Points .1 Affine Transformations and Affine Coordinates.2 Matrices for Affine Transformations in the Plane.
54 5 Affine Geometry: A Connect-the-Dots Approach to Two-Dimensional Computer Graphics .1 Two Shortcomings of Turtle Graphics .2 Affine Graphics.1 The CODO Language .2 Sample CODO Programs. 67 6 Fractals from Iterated Function Systems .1 Generating Fractals by Iterating Transformations .2 Fractals as Fixed Points of Iterated Function Systems.3 Fractals as Attractors.4 Fractals with Condensation Sets. 79 7 The Fixed-Point Theorem and Its Consequences .1 Fixed Points and Iteration .2 The Trivial Fixed Point Theorem .3 Consequences of the Trivial Fixed-Point Theorem .1 Root Finding Methods .1 Compact Sets and the Haussdorf Metric .2 Contractive Transformations and Iterated Function Systems .3 Fractal Theorem, Fractal Algorithm, and Fractal Strategy. 98 Contents vii 8 Recursive Turtle Programs and Conformal Iterated Function Systems.2 The Effect of Changing the Turtle’s Initial State.
113 II Mathematical Methods for Three-Dimensional Computer Graphics 9 Vector Geometry: A Coordinate-Free Approach .1 Coordinate-Free Methods .2 Vectors and Vector Spaces .3 Points and Affine Spaces. 123 Appendix A: The Nonassociativity of the Cross Product. 124 Appendix B: The Algebra of Points and Vectors .2 Addition, Subtraction, and Scalar Multiplication. 135 11 Some Applications of Vector Geometry.1 Law of Cosines .2 Law of Sines .3 Representations for Lines and Planes .1 Distance between Two Points.2 Distance between a Point and a Line.3 Distance between a Point and a Plane .4 Distance between Two Lines .1 Triangles and Parallelograms .2 Polygons: Newell’s Formula .5 Intersection Formulas for Lines and Planes .1 Intersecting Two Lines.2 Intersecting Three Planes .3 Intersecting Two Planes .6 Spherical Linear Interpolation .7 Inside–Outside Tests.
159 12 Coordinate-Free Formulas for Affine and Projective Transformations.1 Transformations for Three-Dimensional Computer Graphics .2 Affine and Projective Transformations .1 Affine and Projective Transformations without Matrices.2 Formulas for Affine and Projective Transformations. 174 Contents ix 13 Matrix Representations for Affine and Projective Transformations.1 Matrix Representations for Affine Transformations.2 Linear Transformation Matrices and Translation Vectors.1 Linear Transformation Matrices.1 Projective Transformations and Homogeneous Coordinates.2 Matrices for Perspective Projections.1 Matrix Representations for Affine and Projective Transformations.2 Matrices for Affine and Projective Transformations. 199 14 Projective Space versus the Universal Space of Mass-Points .1 Algebra and Geometry.2 Projective Space: The Standard Model.3 Mass-Points: The Universal Model .4 Perspective and Pseudoperspective.1 Perspective and the Law of the Lever .2 Pseudoperspective and Pseudodepth. 219 15 Quaternions: Multiplication in the Space of Mass-Points .1 Vector Spaces and Division Algebras .2 Quaternion Representations for Conformal Transformations.3 Quaternions versus Matrices .5 Key Frame Animation.
245 x Contents III Three-Dimensional Computer Graphics: Realistic Rendering 16 Color and Intensity .2 The RGB Color Model .4 Diffuse Reflection .5 Specular Reflection. 256 17 Recursive Ray Tracing .2 Recursive Ray Tracing. 265 18 Surfaces I: The General Theory.3 Ray–Surface Intersections.4 Mean and Gaussian Curvature. 278 19 Surfaces II: Simple Surfaces .3 Planes and Polygons .1 Intersecting a Line and a Circle .2 Inversion Formulas for the Line .1 Intersecting a Line and an Infinite Cylinder .2 Intersecting a Line and a Bounded Cylinder .4 Ellipsoids, Elliptical Cylinders, and Elliptical Cones.5 General Quadric Surfaces .1 Bounding the Torus .7 Surfaces of Revolution.2 Constructive Solid Geometry (CSG) .1 Newell’s Formula for the Normal to a Polygon .1 Naive Phong Shading.2 Fast Phong Shading and Diffuse Reflection .3 Fast Phong Shading and Specular Reflection .4 Phong Shading and Spherical Linear Interpolation.
339 22 Hidden Surface Algorithms .1 Hidden Surface Algorithms .2 The Heedless Painter .2 The Radiosity Equations.1 The Rendering Equation .2 The Radiosity Equation: Continuous Form .3 The Radiosity Equation: Discrete Form .4 The Radiosity Rendering Algorithm .5 Solving the Radiosity Equations.2 Shooting: Progressive Refinement. 375 IV Geometric Modeling: Freedom Curves and Surfaces 24 Bezier Curves and Surfaces .1 Interpolation and Approximation.2 The de Casteljau Evaluation Algorithm .3 The Bernstein Representation .4 Geometric Properties of Bezier Curves .1 Affine Invariance.2 Convex Hull Property .3 Variation Diminishing Property.4 Interpolation of the First and Last Control Points .5 Differentiating the de Casteljau Algorithm.1 Smoothly Joining Two Bezier Curves.2 Uniqueness of the Bezier Control Points.6 Tensor Product Bezier Patches .1 Divide and Conquer.2 The de Casteljau Subdivision Algorithm.3 Rendering and Intersection Algorithms .1 Rendering and Intersecting Bezier Curves .2 Rendering and Intersecting Bezier Surfaces .4 The Variation Diminishing Property of Bezier Curves .5 Joining Bezier Curves Smoothly. 414 Contents xiii 26 Blossoming .3 Blossoming and the de Casteljau Algorithm .1 Bezier Subdivision from Blossoming .4 Differentiation and the Homogeneous Blossom.1 Homogenization and the Homogeneous Blossom .2 Differentiating the de Casteljau Algorithm.3 Conversion Algorithms between Monomial and Bezier Form. 434 27 B-Spline Curves and Surfaces .2 Blossoming and the Local de Boor Algorithm.3 B-Spline Curves and the Global de Boor Algorithm .5 Labeling and Locality in the Global de Boor Algorithm .6 Every Spline is a B-Spline.7 Geometric Properties of B-Spline Curves .8 Tensor Product B-Spline Surfaces .9 Non-Uniform Rational B-Splines (NURBS).
453 28 Knot Insertion Algorithms for B-Spline Curves and Surfaces .3 Local Knot Insertion Algorithms.1 Boehm’s Knot Insertion Algorithm .2 The Oslo Algorithm .3 Conversion from B-Spline to Piecewise Bezier Form.4 The Variation Diminishing Property for B-Spline Curves .5 Algorithms for Rendering and Intersecting B-Spline Curves and Surfaces .4 Global Knot Insertion Algorithms .1 The Lane–Riesenfeld Algorithm.2 Schaefer’s Knot Insertion Algorithm .3 Convergence of Knot Insertion Algorithms.4 Algorithms for Rendering and Intersecting B-Spline Curves and Surfaces Revisited. 475 29 Subdivision Matrices and Iterated Function Systems .1 Subdivision Algorithms and Fractal Procedures .1 Subdivision Matrices for Bezier Curves .2 Subdivision Matrices for Uniform B-Spline Curves .3 Iterated Function Systems Built from Subdivision Matrices.1 Lifting the Control Points to Higher Dimensions.4 Fractals with Control Points .1 Split and Average.2 A Subdivision Procedure for Box Spline Surfaces.1 Uniform Bicubic B-Spline Surfaces.2 Arbitrary Quadrilateral Meshes.1 Stencils for Uniform B-Splines.2 Stencils for Extraordinary Vertices .1 Centroid Averaging for Triangular Meshes.1 Three-Direction Quartic Box Splines.2 Arbitrary Triangular Meshes.2 Stencils for Triangular Meshes .1 Stencils for Three-Direction Quartic Box Splines .2 Stencils for Extraordinary Vertices .1 Bicubic Tensor Product B-Splines and Three-Direction Quartic Box Splines .1 Split and Average.2 Centroid Averaging for Meshes of Arbitrary Topology.3 Stencils for Extraordinary Vertices. 533 Foreword The field of computer graphics has reached a level of maturity, as evidenced by the graphics capability that is ubiquitous on even entry-level personal computers and by the prevalence of graphics software that is used to create stunning images and animations by artists who need no knowledge of what is going on under the hood. At the same time, the field of computer graphics continues to expand and evolve, as evidenced by the increasing number of research papers written on the topic from one year to the next.
This rapid growth poses a challenge for the author of a new book on computer graphics, who must assess what subset of the ever-expanding body of knowledge will be of greatest benefit to the students, and will have the longest shelf life. Several good books have been written on computer graphics over the years, and many of them are currently available in advanced editions. They span a spectrum from encyclopedic to nuts-and- bolts programming. This book offers a fresh approach.
It is discretized into ‘‘lectures,’’ organized to fill a semester-long introductory course with one chapter for each of the 30 class periods. The topics chosen cover most of the key concepts of computer graphics. The lectures on mathematical foundations and on geometric modeling are particularly strong. The book is void of programming examples, since the transitory nature of graphics languages would soon render such material outdated.
The author has a distinguished career as a developer, researcher, and educator in computer graphics. After earning a PhD in mathematics, he worked for many years in the young computer graphics and computer-aided design (CAD) industries, where he contributed to early graphics software development. While thus employed, he took an interest in mentoring several PhD students at various universities across the country, even though it was not formally part of his job. He did this partly because he loves research, but even more because he loves helping students succeed.
As one of those fortunate students, I can attest to his infectious enthusiasm for his subject matter, his lucid explanations, his noise-free writing style, and his mathematical rigor. Goldman has dedicated the past 20 years of his career to teaching and research as a professor of computer science at the University of Waterloo and Rice University. The pedagogical style of this book has been refined during his many years of teaching this material. He is an excellent mentor of students and I am pleased that his reach will be extended through the publication of this book.
Sederberg Brigham Young University xv To the Logos, –Wordsmith and Mathematician Incarnate– Co-Eternal Consort of the Creator, Who on the First Day spoke the Word and made Light, And saw that it was Good. Let there be Light. Genesis 1:3 Preface Behold, the days come, saith the LORD, that I will make a new covenant .