The second edition of this classic computer graphics book represents a major rewrite. Procedural Elements for Computer Graphics is of special interest to students, Programmers and computer graphics professionals.Major new additions include graphical user interfaces, ellipse, imape compression and anialiased line algorithms. Clipping algorithms now include those by Liang-Barsky, Nicholl-Lee-Nicholl as well as the classical Cohen-Sutherland, midpoint, Cyrus-Beck and Sutherland-Hodgman algorithms. In addition to the classical algorithms the visible surface chapter now includes the Apper haloed line, A-buffer, BSP, octree and marching cubes algorithms. The original visible surface ray tracing discussion is much expanded. The rendering chapter now includes additional discussion of physically based illumination models, transparency, shadows, textures, and cone, beam, pencil and stochastic ray tracing. The fundamentals of radiosity are covered in detail. Uniform color spaces and a detailed discussion of gamma correction along with color image quantization and color reproduction for print media are added. However, this edition retains and adds to the many detailed worked examples of the original.
In the preface to the first edition I wrote "Computer graphics is now a mature discipline." Little did I or anyone else aticipate the deVlopments of the last dozen years. Then, ray tracing was an active research topic -- now there axe freey available programs for personal computers; radiosity was just on the horizon today commercially rendering systems commonly use this techniqde; texture was a software application -- today hardware teXture acceleration is common place;color image quatization algorithms were certainly available in the computer graphics community, but today downloading an image from the World Wide Web depends on color image quantization. The list goes on. Computer graphics is thoroughly illtegrated into our daily lives, across fields as diverse as advrtising, entertainment, medicine, education, science, engilleering, navigation, etc. Infact, most computer Programs, including the most popular operating systems,have a graphical user interface.
The present volume represents a major rewrite of the first edition. As a result, it is nearly twice the size of the original volume. Major new additions include a discussion of graphical user interfaces, an expanded discussion of line,circle and ellipse drawing and image compression algorithms. New clipping al gorithms for lines and polygons are preseoted. In particular, the LiangBarsky and Nicholl--Lee--Nicholl clipping algorithms are now discussed along with the classical Cohen--Sutherland, midpoiot, Cyrus--Beck and Sutherland-Hodgman clipping algorithms.
The chapter on visible surface algorithms now includes sections on the Appel,haloed line and A-buffer algorithms, along with discussions of the billary space Partitioning (BSP), octree and marching cubes algorithms. The discussion of the visible surface ray tracing algorithm is considerably expanded.
The rendering chapter is significalltly enhanced. It now includes expanded discussions of physically based illumination modes, transparency, shadows and totures. More recent advances in rny tracing, for example, cone, beam, pencil and stochastic ray tracing, are included along with a dotailed disctalon of the fundamentaJs of radiosity. The section on color is expanded to include uniform color spaces and a more detailed discussion of gamma correction. Sections on color image quantization and color reproduction for prillt media are included.
The book is suitable for use by profeSsional programmers, engineers and scientiSts. A course in compllter graPhics at either the Senior undergradwte or first year graduate level that emphasizes rendering techniques will benefit from the book. Combining it with it8 companion volume, Mathetnatind Elements for Computer Gmphics, allows increasing the scope of the course to include manipulative transformations and curves and surfaces. The book retains the detailed worked examples from the first edition as well as presenting new ones u a total of 90 worked examples. An adequate background is provided by college level mathematics and knowledge of a higherlevel programming language.
No computer graphics book is complete without a1gorithms. There are three types of algorithms presented in the book. The first is a narrative description often presented in list form; the second is a detailed procedural description of the algorithm, while the third is a more formal presedation using pseudocode.
Although many books now present algorithms in C, I resisted this temptation.I believe that acctually implemellting an algorithm yields better understandng and appreciation of the nuances of the algorithm which no book can covr. Fur thermore, as the algorithm is implemented additional efficiencies specific to the implementation language frequently suggest themSeves. For those algorithms presented in pseudocode, the actual implementation is relatively straightforward.
No book is ever written without the assistance of many individuals. Thanks are expressed to my colleagues who read various parts of the manuscript. John Dill and his students read all of Chapter 3 on clipping and made many valuabe comments. Paul Heckbert read both the sections on color image quantization and tedures. Both sections are much the botter for his comments. Maureen Stone lent her expertise on color reproduction. Eric Haines commented extensively on the ray tracing sections. I particularly enjoyed the enSUng discussions. John Wallace read the section on radiosity and set me straight on one or two key points. However, any errors are mine alone.
Special thanks are due my colleagues nanGois Sillion and Peter Kipfer at the iMAGIS prOject in Grenoble, nance, who created the cover image to an impossibly short deadline using hierarchical radiosity software developed under the direction of Fran9ois Sillion and George Drettakis. You eothusiastically made all the changes that I reqdested! It was great working with you.
My editor of more than two and a half decades, B.J. Clark, has now left for other pastures. Without his initial faith in a young academic who wated to do a book on computer graphics, and his gelitle encouragemell over the years,none of this would have happened. Thanks are due ned Eckardt and his crew at Fine Line Illustrations for their efforts in creating the line art.They eventrusted me with the original files. The production crew at McGrawHill - Kari Geltemeyer, Laurie Eatringer and Heather Burbridge--did an outstanding job.Last, but certainly not least, a very special thanks is due tny wife Nancy for not only her long term patience with my need to Laste, but certainly not last,a very special thanks is due my wife Nancy for the outstanding job of copy editing, proof reading and typedting. I think you no+qualify as a TEXpert.
David F. Rogers
Chapter 1 Introduction To Computer Graphics
1--1 Overview of Computer Graphics
Representing Pictures
Preparing Pictures for Presentation
Preseoting Previously Prepared Pictures
1--2 Raster Refresh Graphics Displays
Frame Buffers
1--3 Cathode Ray Tube Basics
Color CRT Raster Scan Monitors
1--4 Video Basics
American Standard Video
High Definition Television
1--5 Flat Panel DisPlays
Flat CRT
Plasma Display
Electroluminescelit Display
Liquid Cristal Displar
1--6 Hardcopy Output Devices
Electndatic Plotters
Ink Jet Plotters
Thermal Plotters
Dye Sublimation Printers
Pen and Ink Plotters
Laser Printers
Color Film Camras
1--7 Logical Interactire Devices
The Locator Thnction
The Valuator Function
The Battom or Choice Funtion
The Pick Function
1--8 Physical Interactive Devices
Tablets
Touch Panels
Control Dials
Joystick
Thackball
Mouse
Function Switches
Light Pen
Spaceball
Data Glove
Simulation of Alternate Devices
1--9 Data Generation Devices
Scanners
Three-dimeusional Digitizers
Motion Capture
1--10 Graphical User Interfaces
Cursors
Radio Buttons
Valuators
Scroll Bars
Grids
Dialog Boxes
Menus
Icons
Sketching
3-D Illteraction
Summary
Chapter 2 Raster Scan Graphics
2--1 Line Drawing Algorithms
2--2 Digital Differentiai Analyzer
2--3 Bresenham's Algorithm
Integer Bresenham's Algorithm
General Bresenham's Algorithm
Faster Line haerization Algorithms
2--4 Circle GenerationBresenham's Algorithm
2--5 Ellipse Generation
2--6 General FunCtion Rasterization
2--7 Scan C onversion--Generation of the Display
Real-time Scan Conversion
A Simple Active Edge List Using Poillters
A Sorted Active Edge List
An Active Edge List Using a Linked List
Updating the Linked List
2--8 Image Compression
Run-length Encoding
Area Image Compression
2--9 Displaying Lines, Characters and Polygons
Line Display
Chazarter Display
Solid Area Scan Convesion
2--10 Polygon Filling
Scanconverting Polygons
2--11 A Simple Parity Scan Conversion Algorithm
2--12 Ordered Edge List Polygon Scan Conversion
A Simple Ordered Edge LiSt Algorithm
More Efficieot Ordered Edge List Algorithms
2--13 The Edge Fill Algorithm
2--14 The Edge Fdag Algorithm
2--15 Seed Fill Algorithms
A Simple Seed Fi1l Algorithm
A Scan Line Seed Fill Algorithm
2-16 Fundamentals of Antialiasing
Supcrsampling
Simple Area Alltialiasing
The Convolution Integral and Antialiasing
Filter Functions
2--17 Halftoning
Patterning
Thresholding and Error Distribution
Ordered dither
Chapter 3 Clipping
3--1 Two-dimensional Clipping
A Simple Visibility AlgorithIn
End Point Codes
3--2 Cohen-Sutherland Subdivision Line
Clipping Algorithm
3--3 Midpoint Subdivision Algorithm
3--4 Two-dimensional Line Clipping for
Convex Boundaries
Parially Visible Lines
3--5 Cyrus--Beck Algorithm
Partially Visible Lines
Totally Visible Lines
Totally Invisible Lines
Formal Statemeot of Cyrus-Beck Algorithm
Irregular Windows
3--6 LiangBarsky Twrvdimensional Clipping
Comparison with the Cyrus--Beck Algorithm
3--7 Nicholl--Lee--Nicholl Two-dimensional Clipping
3--8 Interior and EXterior Clipping
3--9 Identifying Convex Polygons and Dotermining the
Inward Normal
3--10 Splitting Concave Polygons
3--1l Three-dimensional Clipping
3--12 Three-dimensional Midpoillt Subdivision Algorithm
3--13 Three-dimensional CyrusBeck Algorithm
3--l4 LiangBarsky Three-dimensional Clipping
3--15 Clipping in Homogeneous Coordinates
The Cyrus--Beck Algorithm
The Liang-Barsky Algorithm
3--16 Determining the Inward Normal and
Three-dimensional Conve Sots
3--17 Splitting Concave Volumes
3--18 Polygon Clipping
3--19 Reentrant Polygon Clipping
Sutherland-Hodgman Algorithm
Determining the Visibility of a Point
Line Iotersections
The Algorithm
3--20 LiangBarsky Polygon Clipping
Entering and Leaving Vertices
Turning Vertices
Development of the Algorithm
Horizontal and Vertical Edges
The Algorithm
3--21 Concave Clipping Regions
Weiler--Atherton Algorithm
Special Cases
3--22 Character Clipping
Chapter 4 Visible Lines and Visible Surfaces
4--1 Introduction
4--2 Floating Horizon Algorithm
Upper Horizon
Lower Horizon
Function Interpolation
Aliasing
The Alewitha
Cross-hatching
4--3 Roberts Algorithm
Volume Matrices
Plane Equaions
Viewing Transformations and Volume Matrices
Self hidden Plares
Lines Hidden by Other Volumes
Penetrating Volumes
Totally Visible Lines
The Algorithm
4--4 Warnoch Algorithm
Quadree Data Strucure
Subdivision Criteria
The ffelationship of a Polygon to a Window
Hierazchical Appicatbo of
Finding Surrouder Polygons
The Basic Algoithm
4--5 Appel's Algorithm
4--6 The Haloed Line Algorithm
4--7 WeilerAtherton Algorithm
4--8 A Subdivision Algorithm for Curved Surfaces
4--9 Z-Buffer Alsorithm
Incrementally Caiculating the Depth
Hierardscal Z-Buffer
4--10 The A-Buffer Algorithm
4--11 List Priority Algorithms
4--12 The Newell--Newell-Sancha Algorithm
Implementing the Tests
4--13 Binary Space Patitioning
The Schumaker Algorithm
Binary Spare Partition Trees
Constructing the BSP Tree
BSP Tree Thaversal
Culling
Summary
4--14 Scan Line Algorithms
4--15 Scan Line Z-Buffer Algorithm
4--16 A Spanning Scan Line Algorithm
Invisible Coherence
An Object Space Scan Line Algorithm
4--17 Scan Line Algorithms for Curved Surfaces
4--18 Octrees
Octree Display
Linear Octrees
Manipulation of Octrees
Boolean Operations
Finding Neighboring Voxels
4--19 Marching Cubes
Ambiguous faces
4--20 A Visible Surface Ray nacing Algorithm
Bounding Volumes
Clusters
Constructing the Cluster Tree
Priority Sort
Spatial Subdivision
Ray-Object Intersections
Opeque Visible Surface Algorithm
4--21 Summary
Chapter 5 Hendering
5--1 Introduction
5--2 Illumination Models
5--3 A Simple Illumination Model
Specular Reflection
The Halfway Vector
5--4 Determining the Surface Normal
5--5 Determining the Reflection Vector
5--6 Gouraud Shading
5--7 Phong Shading
Fast Phong Shedins
5--8 A Simple Illumination Model with Special Effects
5--9 A Physically Based Illumination Model
Energy and Intensity
Physically Based Illumination Models
The Torrance--Sparrow Surha Model
Wavelength Dependenc-the Fresnel Term
Color Shift
Physical CharaJcteristics of Light Sources
5--10 Thansparency
Refraction Effects in nansParent Materials
Simple nansparency Models
Z-Bther Thansparency
Pseudotransparency
5--11 Shadows
The Scan Conversion Shadow Algorithms
Multiple-pass Visible Surface
The Shfor Volume Algorithms
Penumbra Shadows
Ray Thacing Shadow Algorithms
5--12 Texture
Mapping Functions
Twcrpart Texture Mapping
Environment Mapping
Bump Mapping
Procedural Textures
Texture Alltialiasing
Mipmapping (Image Pyramids)
Summed Area Tables
5--13 Stochastic Models
5--14 A Global Illumination Model Using Ray nacing
5--15 A More Complete Global Illumination Model Usingn Ray Tracing
5--16 Advances in Ray Thacing
Cone Thacing
Beam Thacing
Pencil Tracing
Stochastic Sampling
Ray Thacing from the Light Source
5--17 Radiosity
Enclosures
Form Factors
The Hemicube
Rendering
Substructuring
Progressive Refinement
Sorting
The Ambient Cofitribution
Adaptive Subdivision
Hemicube Inaccuracies
Alternatives to the Hemicube
Hierarchical Radiosity and Clustering
Miosity for Specular Environments
The Rendering Equation
5--18 Combined Ray Tracing and Radiosity
The Extended Two-pass Algorithm
5--19 Color
Chromaticity
Tristimulus Theory of Color
Color Primary Systems
Color Matching Experiment
Chromaticity Diagrams
The 1931 CIE Chromaticity Diagram
Uniform Color Spaces
Gamut Limitations
Thansformations Between Color SyStems
NTSC Color System
Color Cubes
The CMYK Color System
The Ostwald Color System
The HSV Color System
The HLS Color System
The Munsell Color System
The Pantone System
Gamma Correction
5--20 Color Image Quatization
The Bit Cuttins Algnrithm
The Popularity Algorithm
The Median Cut Algorithm
Octree Quatization
Sequential Scalar Quatization
Other Quantization Algorithms
5--21 Color Repoduction
Offset Printing
Color Separation
Tone Reproduction
Gray Balance
The Black Separation
Quatization Effects
Calibeation
Gamut Mapping
5--22 Specialty Rendering Techniques
Duotone Printins
Rendering Natural Objects
Particle Systems
Appendix Problems and Projects
References
Index
无
