# An Integrated Introduction to Computer Graphics and Geometric Modeling

## Preview

## Book Description

Taking a novel, more appealing approach than current texts, **An Integrated Introduction to Computer Graphics and Geometric Modeling** focuses on graphics, modeling, and mathematical methods, including ray tracing, polygon shading, radiosity, fractals, freeform curves and surfaces, vector methods, and transformation techniques. The author begins with fractals, rather than the typical line-drawing algorithms found in many standard texts. He also brings the turtle back from obscurity to introduce several major concepts in computer graphics.

Supplying the mathematical foundations, the book covers linear algebra topics, such as vector geometry and algebra, affine and projective spaces, affine maps, projective transformations, matrices, and quaternions. The main graphics areas explored include reflection and refraction, recursive ray tracing, radiosity, illumination models, polygon shading, and hidden surface procedures. The book also discusses geometric modeling, including planes, polygons, spheres, quadrics, algebraic and parametric curves and surfaces, constructive solid geometry, boundary files, octrees, interpolation, approximation, Bezier and B-spline methods, fractal algorithms, and subdivision techniques.

Making the material accessible and relevant for years to come, the text avoids descriptions of current graphics hardware and special programming languages. Instead, it presents graphics algorithms based on well-established physical models of light and cogent mathematical methods.

## Table of Contents

*Two-Dimensional Computer Graphics: From Common Curves to Intricate Fractals*

**Turtle Graphics**

Turtle Graphics

Turtle Commands

Turtle Programs

**Fractals from Recursive Turtle Programs**

Fractals

Looping Lemmas

Fractal Curves and Recursive Turtle Programs

Programming Projects

**Some Strange Properties of Fractal Curves**

Fractal Strangeness

Dimension

Differentiability

Attraction

**Affine Transformations**

Transformations

Conformal Transformations

Algebra of Affine Transformations

Geometry of Affine Transformations

Affine Coordinates and Affine Matrices

Conformal Transformations: Revisited

General Affine Transformations

**Affine Geometry: A Connect-the-Dots Approach to Two-Dimensional Computer Graphics**

Two Shortcomings of Turtle Graphics

Affine Graphics

**Fractals from Iterated Function Systems**

Generating Fractals by Iterating Transformations

Fractals as Fixed Points of Iterated Function Systems

Fractals as Attractors

Fractals with Condensation Sets

Programming Projects

**Fixed-Point Theorem and Its Consequences**

Fixed Points and Iteration

Trivial Fixed-Point Theorem

Consequences of the Trivial Fixed-Point Theorem

Programming Projects

**Recursive Turtle Programs and Conformal Iterated Function Systems**

Motivating Questions

Effect of Changing the Turtle’s Initial State

Equivalence Theorems

Conversion Algorithms

Bump Fractals

Programming Projects

*Mathematical Methods for Three-Dimensional Computer Graphics*

**Vector Geometry: A Coordinate-Free Approach**

Coordinate-Free Methods

Vectors and Vector Spaces

Points and Affine Spaces

Vector Products

Appendix A: The Nonassociativity of the Cross Product

Appendix B: The Algebra of Points and Vectors

**Coordinate Algebra**

Rectangular Coordinates

Addition, Subtraction, and Scalar Multiplication

Vector Products

**Some Applications of Vector Geometry**

Introduction

Trigonometric Laws

Representations for Lines and Planes

Metric Formulas

Intersection Formulas for Lines and Planes

Spherical Linear Interpolation

Inside-Outside Tests

**Coordinate-Free Formulas for Affine and Projective Transformations**

Transformations for Three-Dimensional Computer Graphics

Affine and Projective Transformations

Rigid Motions

Scaling

Projections

**Matrix Representations for Affine and Projective Transformations**

Matrix Representations for Affine Transformations

Linear Transformation Matrices and Translation Vectors

Rigid Motions

Scaling

Projections

Perspective

Programming Projects

**Projective Space versus the Universal Space of Mass-Points**

Algebra and Geometry

Projective Space: The Standard Model

Mass-Points: The Universal Model

Perspective and Pseudoperspective

**Quaternions: Multiplication in the Space of Mass-Points**

Vector Spaces and Division Algebras

Complex Numbers

Quaternions

*Three-Dimensional Computer Graphics: Realistic Rendering*

**Color and Intensity**

Introduction

RGB Color Model

Ambient Light

Diffuse Reflection

Specular Reflection

Total Intensity

**Recursive Ray Tracing**

Raster Graphics

Recursive Ray Tracing

Shadows

Reflection

Refraction

**Surfaces I: The General Theory**

Surface Representations

Surface Normals

Ray–Surface Intersections

Mean and Gaussian Curvature

**Surfaces II: Simple Surfaces**

Simple Surfaces

Intersection Strategies

Planes and Polygons

Natural Quadrics

General Quadric Surfaces

Tori

Surfaces of Revolution

Programming Projects

**Solid Modeling**

Solids

Constructive Solid Geometry

Boundary Representations

Octrees

Programming Projects

**Shading**

Polygonal Models

Uniform Shading

Gouraud Shading

Phong Shading

Programming Projects

**Hidden Surface Algorithms**

Hidden Surface Algorithms

The Heedless Painter

*z*-Buffer (Depth Buffer)

Scan Line

Ray Casting

Depth Sort

bsp-Tree

Programming Projects

Radiosity

Radiosity

Radiosity Equations

Form Factors

Radiosity Rendering Algorithm

Solving the Radiosity Equations

Programming Projects

*Geometric Modeling: Freedom Curves and Surfaces*

**Bezier Curves and Surfaces**

Interpolation and Approximation

de Casteljau Evaluation Algorithm

Bernstein Representation

Geometric Properties of Bezier Curves

Differentiating the de Casteljau Algorithm

Tensor Product Bezier Patches

**Bezier Subdivision**

Divide and Conquer

de Casteljau Subdivision Algorithm

Rendering and Intersection Algorithms

Variation Diminishing Property of Bezier Curves

Joining Bezier Curves Smoothly

Programming Projects

**Blossoming **

Motivation

Blossom

Blossoming and the de Casteljau Algorithm

Differentiation and the Homogeneous Blossom

**B-Spline Curves and Surfaces**

Motivation

Blossoming and the Local de Boor Algorithm

B-Spline Curves and the Global de Boor Algorithm

Smoothness

Labeling and Locality in the Global de Boor Algorithm

Every Spline Is a B-Spline

Geometric Properties of B-Spline Curves

Tensor Product B-Spline Surfaces

Nonuniform Rational B-Splines (NURBs)

**Knot Insertion Algorithms for B-Spline Curves and Surfaces**

Motivation

Knot Insertion

Local Knot Insertion Algorithms

Global Knot Insertion Algorithms

Programming Projects

**Subdivision Matrices and Iterated Function Systems**

Subdivision Algorithms and Fractal Procedures

Subdivision Matrices

Iterated Function Systems Built from Subdivision Matrices

Fractals with Control Points

Programming Projects

**Subdivision Surfaces**

Motivation

Box Splines

Quadrilateral Meshes

Triangular Meshes

Programming Projects

**Further Readings **

**Index**

*A Summary and Exercises appear at the end of each chapter.*

## Author(s)

### Biography

**Ron Goldman** is a professor of computer science at Rice University, Houston, Texas. Dr. Goldman’s current research interests encompass the mathematical representation, manipulation, and analysis of shape using computers.

## Reviews

… this book may be the first book on geometric modelling that also covers computer graphics. In addition, it may be the first book on computer graphics that integrates a thorough introduction to ‘freedom’ curves and surfaces and to the mathematical foundations for computer graphics. … the book is well suited for an undergraduate course. … The entire book is very well presented and obviously written by a distinguished and creative researcher and educator. It certainly is a textbook I would recommend. …—Computer-Aided Design, 42, 2010

… Many books concentrate on computer programming and soon become obsolete because of newly emerging developments in software languages and hardware. Thankfully, this text is different! The text is void of programming examples as these would have quickly rendered the book outdated, given the transitory nature of graphics languages. … The author has used his experiences of teaching and research to write a book that will, I am sure, become a valuable reference source for years to come. Each chapter has a number of exercises for further study and many chapters have programming projects which will require further work and implementation in a graphics language.—International Statistical Review, 2010

Dr. 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.—Thomas W. Sederberg, Brigham Young University