WIXLIB

xivContents7.4Two-Dimensional Texture Mapping3777.5Texture Mapping in WebGL3847.5.17.5.27.5.37.5.47.5.57.5.67.5.7Texture Objects 384The Texture Image Array 385Texture Coordinates and SamplersTexture Sampling 391Working with Texture Coordinates3D Texture Mapping 397Multitexturing4037.6Environment Maps4077.7Reflection Map Example4127.8Bump Mapping4177.8.17.8.2Finding Bump MapsBump Map Example418421Summary and Notes425Code ExamplesCHAPTER 82019/4/4 11:00427427WORKING WITH FRAMEBUFFERS4298.1Blending Techniques8.1.18.1.28.1.38.1.48.1.58.1.6Opacity and Blending429Image Blending431Blending in WebGL431Antialiasing Revisited 433Back-to-Front and Front-to-Back Rendering435Scene Antialiasing and Multisampling4368.2Image Processing8.2.1Other Multipass Methods8.3GPGPU4398.4Framebuffer Objects4438.5Multi-pass Rendering Techniques4498.5.18.5.2Ambient Occlusion450Deferred Lighting 4518.6Buffer Ping-Ponging4528.7Picking4558.8Shadow Maps4608.9Projective Textures464Summary and NotesAngel 8/e second galleys395427Suggested ReadingsExercises386p. xiv (front)429436438466Windfall Software, PCAZzTEX 17.7

ContentsCode Examples467Suggested ReadingsExercisesCHAPTER 9468468MODELING AND HIERARCHY4719.1Geometries and Instances4729.2Hierarchical Models4749.3A Robot Arm4769.4Trees and Traversal9.4.1A Stack-Based Traversal9.5Use of Tree Data Structures4859.6Animation4899.7Graphical Objects4909.7.19.7.29.7.39.7.49.7.5Methods, Attributes, and Messages 491A Cube Object492Instancing in WebGL496Objects and Hierarchy498Geometric and Nongeometric Objects4999.8Scene Graphs9.9Implementing Scene Graphs9.9.1three.js Examples9.10Other Tree Structures9.10.19.10.29.10.3CSG Trees508BSP Trees510Quadtrees and OctreesCode Examples502504508512514515Suggested ReadingsCHAPTER 10480481500Summary and NotesExercises515516PROCEDURAL METHODS51910.1Algorithmic Models51910.2Physically Based Models and Particle Systems52152210.3Newtonian Particles10.3.110.3.210.3.3Independent Particles524Spring Forces524Attractive and Repulsive Forces10.4Solving Particle Systems52710.5Constraints530Angel 8/e second galleys2019/4/4 11:00xvp. xv (front)526Windfall Software, PCAZzTEX 17.7

xviContents10.5.110.5.2Collisions530Soft Constraints10.6A Simple Particle System10.6.110.6.210.6.310.6.410.6.5Displaying the Particles 534Updating Particle Positions 535Collisions535Forces536Flocking 53710.710.8Agent-Based ModelsUsing Point Sprites53353353854110.9Language-Based Models10.10 Recursive Methods and 545550Rulers and Length551Fractal Dimension552Midpoint Division and Brownian MotionFractal Mountains555The Mandelbrot Set 556Mandelbrot Fragment Shader55955410.11 Procedural NoiseSummary and NotesCode Examples565Suggested ReadingsExercisesCHAPTER 11Angel 8/e second galleys2019/4/4 11:00561563566566CURVES AND SURFACES56911.1Representation of Curves and Surfaces11.1.111.1.211.1.311.1.411.1.5Explicit Representation569Implicit Representations 571Parametric Form 572Parametric Polynomial Curves 573Parametric Polynomial Surfaces 57411.211.311.4Design CriteriaParametric Cubic Polynomial CurvesInterpolation11.4.111.4.2Blending Functions 581The Cubic Interpolating Patch11.5Hermite Curves and Surfaces11.5.111.5.2The Hermite Form 584Geometric and Parametric Continuity11.6Bézier Curves and Surfacesp. xvi (front)569575578579582584587588Windfall Software, PCAZzTEX 17.7

Contents11.6.111.6.2Bézier Curves588Bézier Surface Patches11.7Cubic B-Splines11.7.111.7.211.7.3The Cubic B-Spline CurveB-Splines and Basis597Spline Surfaces59711.8General B-Splines11.8.111.8.211.8.311.8.411.8.5Recursively Defined B-SplinesUniform Splines601Nonuniform B-Splines601NURBS602Catmull-Rom Splines60311.9Rendering Curves and Surfaces11.9.111.9.211.9.311.9.4Polynomial Evaluation Methods605Recursive Subdivision of Bézier Polynomials 606Rendering Other Polynomial Curves by SubdivisionSubdivision of Bézier Surfaces610xvii59159259359859960460911.10 The Utah Teapot61111.11 Algebraic Surfaces61411.11.1 Quadrics61411.11.2 Rendering of Surfaces by Ray Casting61511.12 Subdivision Curves and Surfaces11.12.1 Mesh Subdivision61561611.13 Mesh Generation from Data11.13.1 Height Fields Revisited11.13.2 Delaunay Triangulation11.13.3 Point Clouds62461961962011.14 Graphics API support for Curves and Surfaces62411.14.1 Tessellation Shading62511.14.2 Geometry Shading626Summary and NotesCode Examples627Suggested ReadingsExercisesCHAPTER 12626627627FROM GEOMETRY TO PIXELS63112.1Basic Rendering Strategies63212.2Rendering Pipeline63412.2.112.2.2Modeling634Geometry ProcessingAngel 8/e second galleys2019/4/4 11:00p. xvii (front)635Windfall Software, PCAZzTEX 17.7

xviiiContents12.2.312.2.4Rasterization636Fragment 8Bounding Boxes and VolumesClipping Against Planes 64012.4Rasterization64212.5Polygon Rasterization64512.5.112.5.2Inside–Outside Testing646WebGL and Concave Polygons12.6Hidden-Surface Space and Image-Space Approaches 649Sorting and Hidden-Surface Removal651Scan Line Algorithms651Back-Face Removal 653The z-Buffer Algorithm 655Depth Sort and the Painter’s Algorithm65712.7Hardware Implementations66012.8Antialiasing66312.9Display Considerations66612.9.112.9.212.9.312.9.4Color Systems666The Color Matrix669Gamma Correction671Dithering and Halftoning671672Suggested Readings674CHAPTER 132019/4/4 11:00638Summary and NotesExercisesAngel 8/e second galleys637639647649675ADVANCED RENDERING67913.1Going Beyond Pipeline Rendering67913.2Ray Tracing68068413.3Building a Simple Ray Tracer13.3.113.3.213.3.3Recursive Ray Tracing 685Calculating Intersections 686Ray-Tracing Variations68913.4The Rendering Equation69013.5Global Illumination and Path Tracing69313.6RenderMan69513.7Parallel Rendering696p. xviii (front)Windfall Software, PCAZzTEX 17.7

Contents13.7.113.7.213.7.3Sort-Middle Rendering699Sort-Last Rendering699Sort-First Rendering70313.8Implicit Functions and Contour Maps13.8.113.8.2Marching SquaresMarching Triangles13.9Volume Rendering13.9.113.9.2Volumetric Data Sets711Visualization of Implicit Functions70470470971071213.10 Isosurfaces and Marching Cubes13.11 Marching Tetrahedra71471613.12 Mesh Simplification13.13 Direct Volume gnment of Color and Opacity719Splatting720Volume Ray Tracing722Texture Mapping of Volumes72313.14 Image-Based Rendering72313.14.1 Distance from Stereo Pairs72413.14.2 The Fundamental Matrix72713.15 Virtual, Augmented, and Mixed Reality13.16 A Final ExampleSummary and Notes731Suggested Readings732ExercisesAPPENDIX AA.1A.2727729733INITIALIZING SHADERS735Shaders in the HTML fileReading Shaders from Source Files735738APPENDIX BSPACES741B.1B.2ScalarsVector Spaces741742B.3B.4B.5B.6Affine SpacesEuclidean SpacesProjectionsGram-Schmidt Orthogonalization744747747748Suggested ReadingsExercisesAngel 8/e second galleys2019/4/4 11:00749749p. xix (front)Windfall Software, PCAZzTEX 17.7

xxContentsAPPENDIX CMATRICESC.1C.2C.3C.4DefinitionsMatrix OperationsRow and Column MatricesRank751752753754C.5C.6C.7C.8Change of RepresentationThe Cross ProductEigenvalues and EigenvectorsVector and Matrix Objects755757757759Suggested ReadingsExercisesAPPENDIX DSAMPLING AND ALIASING761D.1D.2Sampling nces2019/4/4 11:00759760Suggested ReadingsAngel 8/e second galleys751p. xx (front)769771Windfall Software, PCAZzTEX 17.7

P RE FACEThis book is an introduction to computer graphics with an emphasis on applications programming. The first edition, which was published in 1997, was somewhat revolutionary in using OpenGL and a top-down approach. Over the succeeding22 years and seven editions, this approach has been adopted by most introductoryclasses in computer graphics and by virtually all the competing textbooks.A Top-Down ApproachRecent advances and the success of the first seven editions continue to reinforce ourbelief in a top-down, programming-oriented approach to introductory computergraphics. Although many computer science and engineering departments now support more than one course in computer graphics, most students will take only asingle course. Such a course usually is placed in the curriculum after students have already studied programming, data structures, algorithms, software engineering, andbasic mathematics. Consequently, a class in computer graphics allows the instructor to build on these topics in a way that can be both informative and fun. We wantthese students to be programming three-dimensional applications as soon as possible. Low-level algorithms, such as those that draw lines or fill polygons, can be dealtwith later, after students are creating graphics.When asked “why teach programming?,” John Kemeny, a pioneer in computereducation, used a familiar automobile analogy: You don’t have to know what’s underthe hood to be literate, but unless you know how to program, you’ll be sitting in theback seat instead of driving. That same analogy applies to the way we teach computergraphics. One approach—the algorithmic approach—is to teach everything aboutwhat makes a car function: the engine, the transmission, the combustion process.A second approach—the survey approach—is to hire a chauffeur, sit back, and seethe world as a spectator. The third approach—the programming approach that wehave adopted here—is to teach you how to drive and how to take yourself whereveryou want to go. As an old auto rental commercial used to say, “Let us put you in thedriver’s seat.”The sixth and seventh editions reflected the major changes in graphics application development due to advances in graphics hardware. In particular, the sixthedition was fully shader-based, enabling readers to create applications that couldfully exploit the capabilities of modern GPUs. We noted that these changes werepart of OpenGL ES 2.0, which was being used to develop applications for embedded systems and handheld devices, such as cell phones and tablets, and of WebGL,its JavaScript implementation. At the time, we did not anticipate the extraordinaryxxiAngel 8/e second galleys2019/4/4 11:00p. xxi (front)Windfall Software, PCAZzTEX 17.7

xxiiPrefaceinterest in WebGL that began as soon as web browsers became available that support WebGL through HTML5. For the seventh edition, we switched from desktopOpenGL to WebGL.As we noted then, WebGL applications were running everywhere, including onsome of the latest smart phones, and even though WebGL lacks some of the advancedfeatures of the latest versions of OpenGL, the ability to integrate it with HTML5opened up a wealth of new application areas. As an added benefit, we found it muchbetter suited than desktop OpenGL for teaching computer graphics. Our hopes forthe seventh edition were more than fulfilled. WebGL has proven to be excellent APIfor both teaching and developing real applications that run on all platforms.In particular, features of the seventh edition included:WebGL 1.0 was used for all examples and programs.All code was written in JavaScript.All code runs in recent web browsers.A new chapter on interaction was added.Additional material on render-to-texture was added.Additional material on displaying meshes also was added.An efficient matrix–vector package was included.An introduction to agent-based modeling was added.For the eighth edition, building on the success of using WebGL, we have:Updated all examples and programs to WebGL 2.0.Added many additional examples.Switched to a fully electronic version that includes links to examples so theycan be viewed with the code while reading.Expanded coverage of render-to-texture in a separate chapter that includesnew topics, including shadow maps and projective textures.Added coverage of three-dimensional texture mapping.Updated the chapter on modeling to include an introduction to three.js, apopular higher-level JavaScript scene-graph API.Added coverage of point sprites for simulation.Expanded and updated our coverage of rendering.Enhanced discussions of hardware implementation and GPU architectures.Programming with WebGL and JavaScriptWhen Ed began teaching computer graphics 35 years ago, the greatest impedimentto implementing a programming-oriented course, and to writing a textbook for thatcourse, was the lack of a widely accepted graphics library or application programminginterface (API). Difficulties included high cost, limited availability, lack of generality,and high complexity. The development of OpenGL resolved most of the difficultiesAngel 8/e second galleys2019/4/4 11:00p. xxii (front)Windfall Software, PCAZzTEX 17.7

Prefacexxiiimany of us had experienced with other APIs and with the alternative of using homebrewed software. OpenGL today is supported on all platforms and is widely acceptedas the cross-platform standard. WebGL builds on OpenGL’s wide acceptance (it’seffectively the same API), but provides a more accessible development platform usingweb technologies.A graphics class teaches far more than the use of a particular API, but a goodAPI makes it easier to teach key graphics topics, including three-dimensional transformations, lighting and shading, client–server graphics, modeling, and implementation algorithms. We believe that OpenGL’s extensive capabilities and well-definedarchitecture lead to a stronger foundation for teaching both theoretical and practicalaspects of the field and for teaching advanced concepts, including texture mapping,compositing, and programmable shaders.Ed switched his classes to OpenGL about 24 years ago and the results astounded him. By the middle of the semester, every student was able to write amoderately complex three-dimensional application that required understanding ofthree-dimensional viewing and event-driven input. In the previous years of teachingcomputer graphics, he had never come even close to this result. That class led to thefirst edition of this book.This book is a textbook on computer graphics; it is not an OpenGL or WebGLmanual. Consequently, it does not cover all aspects of the WebGL API but ratherexplains only what is necessary for mastering this book’s contents. It presents WebGLat a level that should permit users of other APIs to have little difficulty with thematerial.Unlike earlier editions, this one uses WebGL and JavaScript for all the examples.WebGL 2.0 is a JavaScript implementation of OpenGL ES 3.0 and runs in most recentbrowsers. Because it is supported by HTML5, not only does it provide compatibilitywith other applications but also there are no platform dependences; WebGL runswithin the browser and makes use of the local graphics hardware. Although JavaScriptis not the usual programming language with which we teach most programmingcourses, it is the language of the Web. Over the past few years, JavaScript has becomeincreasingly more powerful, and our experience is that students who are comfortablewith Java, Python, C, or C will have little trouble programming in JavaScript.So that we can continue to support a wide audience with varied backgrounds, wehave kept with a very basic JavaScript requiring only ES5. Students who have moreexperience with JavaScript should have little trouble updating our examples andlibraries to exploit powerful new JavaScript features contained in ES6.All the modern versions of OpenGL, including WebGL, require every application to provide two shaders written in the OpenGL Shading Language (GLSL). GLSLis similar to C but adds vectors and matrices as basic types, along with some C features, such as operator overloading. We provide a JavaScript library, MV.js, thatsupports both our presentation of graphics functions and the types and operationsin GLSL. It also contains many functions that perform operations equivalent to deprecated functions from the earlier fixed-function versions of OpenGL.Angel 8/e second galleys2019/4/4 11:00p. xxiii (front)Windfall Software, PCAZzTEX 17.7

xxivPrefaceIntended AudienceThis book is suitable for advanced undergraduates and first-year graduate studentsin computer science and engineering and for students in other disciplines who havegood programming skills. The book also will be useful to many professionals. Between us, we have taught well over 100 short courses for professionals (includingmany courses presented at the annual SIGGRAPH conferences, two of which areavailable on YouTube within the SIGGRAPH University channel), and even a MassiveOnline Course (MOOC) with Coursera. Our experiences with these nontraditionalstudents have had a great influence on what we chose to include in the book.Prerequisites for the book are good programming skills in JavaScript, Python,C, C , or Java; an understanding of basic data structures (arrays, linked lists, trees);and a rudimentary knowledge of linear algebra and trigonometry. We have found thatthe mathematical backgrounds of computer science students, whether undergraduates or graduates, vary considerably. Hence, we have chosen to integrate into the textmuch of the linear algebra and geometry that is required for fundamental computergraphics.Organization of the BookThe book is organized as follows:Chapter 1 provides an overview of the field and introduces image formationby optical devices; thus, we start with three-dimensional concepts immediately.Chapter 2 introduces programming using WebGL. Although the first exampleprogram that we develop (each chapter has one or more complete programming examples) is two-dimensional, it is embedded in a three-dimensionalsetting and leads to a three-dimensional extension.Chapter 3 introduces interactive graphics and develops event-driven graphicswithin the browser environment.Chapters 4 and 5 concentrate on three-dimensional concepts. Chapter 4is concerned with defining and manipulating three-dimensional objects,whereas Chapter 5 is concerned with viewing them.Chapter 6 introduces light–material interactions and shading.Chapters 7 and 8 introduce many of the new discrete capabilities that are nowsupported in graphics hardware and by WebGL. All these techniques involveworking with various buffers. Chapter 7 focuses on classical texture mappingwith a single texture, whereas Chapter 8 concentrates on texture mappingusing off-screen buffers.These chapters should be covered in order and can be taught in about 10 weeks of a15-we

as a 3D point cloud and mesh, which is calculated and rendered in realtime in the browser using WebGL. Live imagery from mobile phones, public webcams, drones, and satellites is projection mapped onto the pointclouds. Realtime. Earth is currently used on wildfires and other emergency events to give realtime coordinated situational