The Computer Graphics Manual

1st Edition

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.

From the Preface

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.

Book Cover

Table of Contents

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;

Auxiliary and Extra Material

• 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.

Quotation

This book has been a journey.

Paul R. Walker, The Feud That Sparked the Renaissance, (2003)

Last Updated 23 Sept, 2012