By David Salomon. Published by Springer (Oct 2011). An ebook version is available for subscribers here. ISBN 978-0-85729-885-0. LCCN unknown. 700 Figures. xiii+1502 pages.
A BibTeX style file and an Errata list are available.
This volume includes content from three older texts as well as much new material.
Overview and Goals
Today (in 2010), the power of computer-generated images is everywhere. Computer graphics has pervaded our lives to such an extent that sometimes we don`t even realize that an image we are watching is artificial. The average person comes into contact with computer graphics mostly in three areas, computers, television, and electronic devices. Current computers and operating systems are based on GUI (graphical user interface). Computer programs often display results graphically. Television programs and commercials employ sophisticated, computer-generated graphics that are often hard to distinguish from the real thing. Many television programs (mostly documentaries) and recent movies mix real actors and artificial imagery to such an extent that the viewer may find it difficult to distinguish a real object or scene from a computer-generated image. (A real actor trying to outrun a computer-generated dinosaur is a common example.) More and more digital cameras, electronic devices, and instruments have small screens that display messages, options, controls, and results in color and are often touch sensitive, enabling the user to enter commands by finger gesturing instead of from the traditional keyboard. Many cell telephones even have two screens, and some new digital cameras also feature two LCD displays.
With this in mind, the goal of this manual is to present the reader with a wide picture of computer graphics, its history and its pioneers, the hardware tools it employs, and most important, the techniques, approaches, and algorithms that are at the core of this field. Thus, this textbook/reference tries to describe as many concepts and algorithms as possible, paying special attention to the important ones.
It would have been nice to include everything in this book and title it, like other texts by the same author, Computer Graphics: The Complete Reference, but computer graphics has grown to a point where I cannot hope to be an authority on the entire field, which is why some readers may not find every topic, term, concept, and algorithm they may be looking for. On the other hand, those same readers may find in this manual-textbook topics they did not know existed, which might serve as compensation.
The many examples and exercises sprinkled throughout the book enhance its usefulness. By paying attention to the examples and working out the exercises, readers will gain deeper understanding of the material.
Organization and Features
This manual is large and is organized in seven parts as follows:
Part I covers the history, basic concepts, and techniques used in computer graphics. The concepts of pixel, vector scan, and raster scan are discussed. It is shown how an image given as a bitmap of pixels can be scaled (zoomed) and rotated. Many important scan-conversion methods are explained and illustrated.
Part II is devoted to transformations and projections. It starts with the important two- and three-dimensional transformations, including translation, rotation, reflection, and shearing. This is followed by the main types of projections, namely parallel, perspective, and nonlinear.
Part III is by far the largest. It includes many methods, algorithms, and techniques employed to construct curves and surfaces, which are the building blocks of solid objects. Six important interpolation and approximation methods for curves and surfaces are included, as well as sweep surfaces and subdivision methods for surface design.
Part IV goes into advanced techniques such as rendering an object, eliminating those parts that are hidden from view, and bringing objects to life (animating them) by interpolation. Several chapters included in this part discuss (1) the nature and properties of light and color, (2) graphics standards and graphics file formats, and (3) fractals.
Part V describes the principles of image compression. It concentrates on two important approaches to this topic, namely orthogonal and subband (wavelet) transforms. The important JPEG image compression standard is described in detail.
Part VI is devoted to many of the important input/output graphics devices. Chapter 26 describes them and explains their operations.
Part VII consists of appendixes, most of which discuss certain mathematical concepts.
The following features enhance the usefulness and appearance of this textbook: The powerful Mathematica and Matlab software systems are used throughout the book to implement many of the concepts discussed. When a figure is computed in one of these programs, the code is listed with the figure. These codes are meant to be readable rather than efficient and fast, and are therefore easy to read and to modify even by inexperienced Mathematica and Matlab users.
The book has many examples. Experience shows that examples are important for a thorough understanding of the kind of material discussed in this manual. The conscientious reader should follow each example carefully and try to work out variations of the examples. Many examples also include Mathematica code.
The many exercises sprinkled in the text are not a cosmetic feature. They deal with important topics, and should be worked out. Answers are provided but they should be consulted only as a last resort.
A quotation is a phrase that reflects its author`s profound thoughts. Quotations and epigrams enliven a book, which is why they have been generously used throughout this manual. I hope that they add to the book and make it more interesting.
This book aims to be practical, not theoretical. After reading and understanding a topic, the reader should be able to design and implement the concepts discussed there. The few mathematical arguments found in the book are simple, and there is no attempt to present an overall theory encompassing the entire field of computer graphics. An important feature of this text is the attention paid to orphans. Those are topics that most texts on computer graphics either mention briefly or disregard completely. Examples are perspective projections, nonlinear projections, nonlinear bitmap transformations, curves, surfaces, I/O devices, and image compression. The reader will find that this manual discusses orphans in great detail, including numerous examples and exercises. Most of the necessary mathematical background (such as vectors and matrices) is covered in the Appendixes. However, some math concepts that are used only once (such as the mediation operator and points vs. vectors) are discussed right where they are introduced.
The Two Volumes
This textbook is big because the discipline of computer graphics is big. There are simply many topics, techniques, and algorithms to discuss, explain, and illustrate by examples. Because of the large number of pages, the book has been produced in two volumes. However, this division of the book into volumes is only technical and the book should be considered a single unit. It is wrong to consider volume I as introductory and volume II as advanced, or to assume that volume I is important while volume II is not. The volumes are simply two halves of a single, large entity.
The Color Plates
This extensive manual features more than 100 color plates, placed at the very beginning, at the end, and between individual parts. They serve to liven up the book and to illustrate many of the topics discussed. It is planned to place information about these plates in the book`s website, for the benefit of readers who want to recreate or extend them. The plates were prepared over several months, using a variety of graphics software. Appendix F has more information about the plates, their content, and the graphics applications used to generate them.
Target Audiences
The material presented here has been developed over many years of teaching computer graphics. It has been revised, updated, and distilled many times, with many figures, examples and exercises added. The text emphasizes the simplicity of the mathematics behind computer graphics and tries to show how graphics software works and how current computer graphics can generate and display realistic-looking curves, surfaces, and solid objects. The key ideas are introduced slowly, are examined, when possible, from several points of view, and are illustrated and illuminated by figures, examples, and (solved) exercises. The discussion must employ mathematics, but it is mostly non-rigorous (no theorems or proofs) and therefore easy to grasp. The mathematical background required includes polynomials, matrices, vector operations, and elementary calculus.
Acknowledgements
A book of this magnitude is generally written with the help, dedicated work, and encouragement of many people, and this large textbook/reference is no exception. First and foremost should be mentioned my editor, Wayne Wheeler and the copyeditor, Francesca White. They made many useful comments and suggestions and pointed out many mistypes, errors, and stylistic blemishes. In addition, I would like to thank H. L. Scott for permission to use Figure 2.82, CH Products for permission to use Figure 26.24b, Andreas Petersik for Figure 6.61, Shinji Araya for Figure 7.27, Dick Termes for many figures and paintings, the authors of Hardy Calculus for the limerick at the end of Chapter 13, Bill Wilburn for many Mathematica notebooks, and Ari Salomon for photos and panoramas in several plates.
I welcome any comments, suggestions and corrections. They should be emailed to [email protected]. An errata list and other information can be found on this page.
Preface vii; Introduction 1; Part I Basic Techniques 7; 1 Historical Notes 9; 1.1 Historical Survey 9; 1.2 History of Curves and Surfaces 13; 1.3 History of Video Games 14; 1.4 Pioneers of Computer Graphics 17; 1.5 Resources For Computer Graphics 19; 2 Raster Graphics 29; 2.1 Pixels 30; 2.2 Graphics Output 32; 2.3 The Source-Target Paradigm 40; 2.4 Interpolation 41; 2.5 Bitmap Scaling 45; 2.6 Bitmap Stretching 46; 2.7 Replicating Pixels 46; 2.8 Scaling Bitmaps with Bresenham 48; 2.9 Pixel Art Scaling 54; 2.10 Pixel Interpolation 56; 2.11 Bilinear Interpolation 57; 2.12 Interpolating Polynomials 58; 2.13 Adaptive Scaling by 2 65; 2.14 The Keystone Problem 73; 2.15 Bitmap Rotation 76; 2.16 Nonlinear Bitmap Transformations 79; 2.17 Circle Inversion 85; 2.18 Polygons (2D) 88; 2.19 Clipping 91; 2.20 Cohen--Sutherland Line Clipping 92; 2.21 Nicholl--Lee--Nicholl Line Clipping 93; 2.22 Cyrus--Beck Line Clipping 95; 2.23 Sutherland--Hodgman Polygon Clipping 97; 2.24 Weiler--Atherton Polygon Clipping 99; 2.25 A Practical Drawing Program 100; 2.26 GUI by Inversion Points 104; 2.27 Halftoning 107; 2.28 Dithering 109; 2.29 Stippling 118; 2.30 Random Numbers 122; 2.31 Image Processing 126; 2.32 The Hough Transform 131; 3 Scan Conversion 135; 3.1 Scan-Converting Lines 135; 3.2 Midpoint Subdivision 136; 3.3 DDA Methods 137; 3.4 Bresenham's Line Method 142; 3.5 Double-Step DDA 147; 3.6 Best-Fit DDA 151; 3.7 Scan-Converting in Parallel 153; 3.8 Scan-Converting Circles 156; 3.9 Filling Polygons 167; 3.10 Pattern Filling 175; 3.11 Thick Curves 177; 3.12 General Considerations 179; 3.13 Antialiasing 180; 3.14 Convolution 192; Part II Transformations and Projections 193; 4 Transformations 199; 4.1 Introduction 201; 4.2 Two-Dimensional Transformations 204; 4.3 Three-Dimensional Coordinate Systems 232; 4.4 Three-Dimensional Transformations 233; 4.5 Transforming the Coordinate System 250; 5 Parallel Projections 251; 5.1 Orthographic Projections 252; 5.2 Axonometric Projections 255; 5.3 Oblique Projections 262; 6 Perspective Projection 267; 6.1 One Two Three $mathinner ... Infinity 269; 6.2 History of Perspective 275; 6.3 Perspective in Curved Objects, I 282; 6.4 Perspective in Curved Objects, II 283; 6.5 The Mathematics of Perspective 294; 6.6 General Perspective 305; 6.7 Transforming the Object 310; 6.8 Viewer at an Arbitrary Location 314; 6.9 A Coordinate-Free Approach: I 322; 6.10 A Coordinate-Free Approach: II 326; 6.11 The Viewing Volume 329; 6.12 Stereoscopic Images 332; 6.13 Creating a Stereoscopic Image 336; 6.14 Viewing a Stereoscopic Image 340; 6.15 Autostereoscopic Displays 351; 7 Nonlinear Projections 355; 7.1 False Perspective 355; 7.2 Fisheye Projection 357; 7.3 Poor Man's Fisheye 369; 7.4 Fisheye Menus 369; 7.5 Panoramic Projections 372; 7.6 Cylindrical Panoramic Projection 373; 7.7 Spherical Panoramic Projection 380; 7.8 Cubic Panoramic Projection 386; 7.9 Six-Point Perspective 389; 7.10 Other Panoramic Projections 391; 7.11 Panoramic Cameras 396; 7.12 Telescopic Projection 402; 7.13 Microscopic Projection 404; 7.14 Anamorphosis 405; 7.15 Map Projections 408; Part III Curves and Surfaces 429; 8 Basic Theory 433; 8.1 Points and Vectors 433; 8.2 Length of Curves 441; 8.3 Example: Area of Planar Polygons 442; 8.4 Example: Volume of Polyhedra 443; 8.5 Parametric Blending 444; 8.6 Parametric Curves 445; 8.7 Properties of Parametric Curves 447; 8.8 PC Curves 453; 8.9 Curvature and Torsion 461; 8.10 Special and Degenerate Curves 469; 8.11 Basic Concepts of Surfaces 470; 8.12 The Cartesian Product 473; 8.13 Connecting Surface Patches 475; 8.14 Fast Computation of a Bicubic Patch 476; 8.15 Subdividing a Surface Patch 478; 8.16 Surface Normals 481; 9 Linear Interpolation 483; 9.1 Straight Segments 483; 9.2 Polygonal Surfaces 487; 9.3 Bilinear Surfaces 493; 9.4 Lofted Surfaces 499; 10 Polynomial Interpolation 505; 10.1 Four Points 506; 10.2 The Lagrange Polynomial 510; 10.3 The Newton Polynomial 519; 10.4 Polynomial Surfaces 521; 10.5 The Biquadratic Surface Patch 521; 10.6 The Bicubic Surface Patch 522; 10.7 Coons Surfaces 527; 10.8 Gordon Surfaces 542; 11 Hermite Interpolation 545; 11.1 Interactive Control 546; 11.2 The Hermite Curve Segment 547; 11.3 Degree-5 Hermite Interpolation 557; 11.4 Controlling the Hermite Segment 558; 11.5 Truncating and Segmenting 562; 11.6 Hermite Straight Segments 564; 11.7 A Variant Hermite Segment 566; 11.8 Ferguson Surfaces 568; 11.9 Bicubic Hermite Patch 571; 11.10 Biquadratic Hermite Patch 573; 12 Spline Interpolation 577; 12.1 The Cubic Spline Curve 578; 12.2 The Akima Spline 599; 12.3 The Quadratic Spline 602; 12.4 The Quintic Spline 604; 12.5 Cardinal Splines 606; 12.6 Parabolic Blending: Catmull--Rom Curves 610; 12.7 Catmull--Rom Surfaces 615; 12.8 Kochanek--Bartels Splines 617; 12.9 Fitting a PC to Experimental Points 624; 13 Bézier Approximation 629; 13.1 The Bézier Curve 630; 13.2 The Bernstein Form of the Bézier Curve 632; 13.3 Fast Calculation of the Curve 639; 13.4 Properties of the Curve 644; 13.5 Connecting Bézier Curves 647; 13.6 The Bézier Curve as a Linear Interpolation 648; 13.7 Blossoming 653; 13.8 Subdividing the Bézier Curve 658; 13.9 Degree Elevation 660; 13.10 Reparametrizing the Curve 663; 13.11 Cubic Bézier Segments with Tension 672; 13.12 An Interpolating Bézier Curve: I 673; 13.13 An Interpolating Bézier Curve: II 676; 13.14 Nonparametric Bézier Curves 684; 13.15 Rational Bézier Curves 684; 13.16 Circles and Bézier Curves 690; 13.17 Rectangular Bézier Surfaces 693; 13.18 Subdividing Rectangular Patches 698; 13.19 Degree Elevation 699; 13.20 Nonparametric Rectangular Patches 701; 13.21 Joining Rectangular Bézier Patches 702; 13.22 An Interpolating Bézier Surface Patch 704; 13.23 A Bézier Sphere 707; 13.24 Rational Bézier Surfaces 707; 13.25 Triangular Bézier Surfaces 709; 13.26 Joining Triangular Bézier Patches 719; 13.27 Reparametrizing the Bézier Surface 723; 13.28 The Gregory Patch 725; Volume II 729; 14 B-Spline Approximation 731; 14.1 The Quadratic Uniform B-Spline 732; 14.2 The Cubic Uniform B-Spline 736; 14.3 Multiple Control Points 743; 14.4 Cubic B-Splines with Tension 745; 14.5 Cubic B-Spline and Bézier Curves 748; 14.6 Higher-Degree Uniform B-Splines 748; 14.7 Interpolating B-Splines 750; 14.8 A Knot Vector-Based Approach 751; 14.9 Recursive Definitions of the B-Spline 760; 14.10 Open Uniform B-Splines 761; 14.11 Nonuniform B-Splines 766; 14.12 Matrix Form of the Nonuniform B-Spline 775; 14.13 Subdividing the B-spline Curve 779; 14.14 Nonuniform Rational B-Splines (NURBS) 782; 14.15 The Cubic B-Spline as a Circle 788; 14.16 Uniform B-Spline Surfaces 792; 14.17 Relation to Other Surfaces 796; 14.18 An Interpolating Bicubic Patch 798; 14.19 The Quadratic-Cubic B-Spline Surface 801; 15 Subdivision Methods 803; 15.1 Introduction 803; 15.2 Chaikin's Refinement Method 804; 15.3 Quadratic Uniform B-Spline by Subdivision 811; 15.4 Cubic Uniform B-Spline by Subdivision 812; 15.5 Biquadratic B-Spline Surface by Subdivision 816; 15.6 Bicubic B-Spline Surface by Subdivision 821; 15.7 Polygonal Surfaces by Subdivision 826; 15.8 Doo Sabin Surfaces 826; 15.9 Catmull--Clark Surfaces 828; 15.10 Loop Surfaces 829; 16 Sweep Surfaces 833; 16.1 Sweep Surfaces 834; 16.2 Surfaces of Revolution 839; 16.3 An Alternative Approach 842; 16.4 Skinned Surfaces 846; Part IV Advanced Techniques 849; 17 Rendering 851; 17.1 Introduction 852; 17.2 A Simple Shading Model 853; 17.3 Gouraud and Phong Shading 864; 17.4 Palette Optimization 866; 17.5 Ray Tracing 867; 17.6 Photon Mapping 876; 17.7 Texturing 877; 17.8 Bump Mapping 879; 17.9 Particle Systems 881; 17.10 Mosaics 883; 18 Visible Surface Determination 891; 18.1 Ray Casting 893; 18.2 Z-Buffer Method 893; 18.3 Explicit Surfaces 895; 18.4 Depth-Sort Method 898; 18.5 Scan-Line Approach 901; 18.6 Warnock's Algorithm 905; 18.7 Octree Methods 907; 18.8 Approaches to Curved Surfaces 910; 19 Computer Animation 911; 19.1 Background 911; 19.2 Interpolating Positions 914; 19.3 Constant Speed: I 915; 19.4 Constant Speed: II 916; 19.5 Interpolating Orientations: I 919; 19.6 SLERP 923; 19.7 Summary 924; 19.8 Interpolating Orientations: II 930; 19.9 Nonuniform Interpolation 937; 19.10 Morphing 943; 19.11 Free-Form Deformations 944; 20 Graphics Standards 947; 20.1 GKS 947; 20.2 IGES 949; 20.3 PHIGS 951; 20.4 OpenGL 954; 20.5 PostScript 956; 20.6 Graphics File Formats 960; 20.7 GIF 961; 20.8 TIFF 963; 20.9 PNG 967; 20.10 CRC 972; 21 Color 975; 21.1 Light 975; 21.2 Color and the Eye 976; 21.3 Color and Human Vision 978; 21.4 The HLS Color Model 982; 21.5 The HSV Color Model 984; 21.6 The RGB Color Space 984; 21.7 Additive and Subtractive Colors 986; 21.8 Complementary Colors 991; 21.9 The Color Wheel 992; 21.10 Spectral Density 994; 21.11 The CIE Standard 997; 21.12 Luminance 1000; 21.13 Converting Color to Grayscale 1001; 22 Fractals 1005; 22.1 Introduction 1006; 22.2 Fractal Landscapes 1009; 22.3 Branching Rules 1013; 22.4 Iterated Function Systems (IFS) 1013; 22.5 Attractors 1017; 22.6 Gaussian Distribution 1021; Part V Image Compression 1025; 23 Compression Techniques 1027; 23.1 Redundancy in Data 1027; 23.2 Image Types 1031; 23.3 Redundancy in Images 1032; 23.4 Approaches to Image Compression 1038; 23.5 Intuitive Methods 1051; 23.6 Variable-Length Codes 1052; 23.7 Codes, Fixed- and Variable-Length 1052; 23.8 Prefix Codes 1055; 23.9 VLCs for Integers 1056; 23.10 Start-Step-Stop Codes 1058; 23.11 Start/Stop Codes 1060; 23.12 Elias Codes 1062; 23.13 Huffman Coding 1069; 24 Transforms and JPEG 1079; 24.1 Image Transforms 1079; 24.2 Orthogonal Transforms 1084; 24.3 The Discrete Cosine Transform 1092; 24.4 Test Images 1128; 24.5 JPEG 1132; 25 The Wavelet Transform 1147; 25.1 The Haar Transform 1148; 25.2 Filter Banks 1166; 25.3 The DWT 1176; 25.4 SPIHT 1188; 25.5 QTCQ 1199; Part VI Graphics Devices 1201; 26 Graphics Devices 1203; 26.1 Displays 1203; 26.2 The CRT 1208; 26.3 LCDs 1213; 26.4 The Digital Camera 1217; 26.5 The Computer Mouse 1236; 26.6 The Trackball 1240; 26.7 The Joystick 1242; 26.8 The Graphics Tablet 1244; 26.9 Scanners 1252; 26.10 Inkjet Printers 1262; 26.11 Solid-Ink Printers 1271; 26.12 Laser Printers 1274; 26.13 Plotters 1279; 26.14 Interactive Devices 1282; Part VII Appendixes 1287; A Vector Products 1289; B Quaternions 1295; C Conic Sections 1299; D Mathematica Notes 1305; E The Resolution of Film 1311; F The Color Plates 1315; References 1321; Answers to Exercises 1339; Index 1469;
• Figure 19.18 (page 943) shows five steps in morphing Bach to Beethoven. The complete video of this morphing can be found here (295KB).
• Paul de Casteljau is mentioned on page 648 (and in other places). Very little is known about this original contributor to the field of computer graphics, which is why the following short articles may be of help to those interested in him: autobiography (37KB) and biography (45KB). These come from the special issue of Computer Assisted Geometric Design (CAGD) journal published in 1999 in his honor (volume 16, issue 7).
• The Mathematica code listed on page 1158 with Figure 25.8 (A Pyramid Wavelet Decomposition), mentions a small image file in raw format. This file is available here (70KB) for those who would like to experiment.
• Several color plates feature graphics generated by MegaPOV (POVray on the Macintosh). The small file available here (12KB) has the source code for these images.
• The many code listings in the book (in Mathematica, Matlab, pseudocode, and C) may be useful to some readers, so they are made available here in PDF (295 KB).
• Bill Wilburn has developed Mathematica notebooks for many of the topics discussed in the book and has graciously made them available to the readers. They can be found here (40MB). If you like them, if you want more, or if you find errors, please let Bill know. These notebooks were developed in version 8.0.1 of Mathematica, but most also run under version 7. If a particular cell refuses to execute, try to copy it and then paste it into a fresh cell. Some notebooks require version 8, and these are located in a separate folder.
• [Sept 2012] The concept of f-stop is mentioned briefly in section 26.4.7 (page 1232). This concept is important in photography but is only peripheral in computer graphics. Nevertheless, many readers wrote to me, asking for more information on f-stops. The result is this short document (PDF, 10 pages, 737 KB). It discusses f-stops, their definition and applications, as well as a few related topics.
This book has been a journey.
Paul R. Walker, The Feud That Sparked the Renaissance, (2003)
Last Updated 23 Sept, 2012