Procedural Elements for Computer Graphics

PROCEDURAL ELEMENTS
FOR

COMPUTER GRAPHICS

Second Edition

David F. Rogers

TABLE of CONTENTS

Preface		xv
Preface to the First Edition		xvii

Chapter 1	Introduction To Computer Graphics	1
1-1	Overview of Computer Graphics	1
	Representing Pictures	2
	Preparing Pictures for Presentation	2
	Presenting Previously Prepared Pictures	3
1-2	Raster Refresh Graphics Displays	6
	Frame Buffers	7
1-3	Cathode Ray Tube Basics	11
	Color CRT Raster Scan Monitors	13
1-4	Video Basics	14
	American Standard Video	14
	High Definition Television	17
1-5	Flat Panel Displays	17
	Flat CRT	17
	Plasma Display	18
	Electroluminescent Display	21
	Liquid Crystal Display	21
1-6	Hardcopy Output Devices	25
	Electrostatic Plotters	25
	Ink Jet Plotters	26
	Thermal Plotters	28
	Dye Sublimation Printers	30
	Pen and Ink Plotters	31
	Laser Printers	34
	Color Film Cameras	36
1-7	Logical Interactive Devices	37
	The Locator Function	38
	The Valuator Function	39
	The Buttom or Choice Function	39
	The Pick Function	39
1-8	Physical Interactive Devices	39
	Tablets	40
	Touch Panels	41
	Control Dials	41
	Joystick	42
	Trackball	42
	Mouse	44
	Function Switches	44
	Light Pen	45
	Spaceball	46
	Data Glove	46
	Simulation of Alternate Devices	47
1-9	Data Generation Devices	49
	Scanners	49
	Three-dimensional Digitizers	50
	Motion Capture	51
1-10	Graphical User Interfaces	52
	Command Line Interface	52
	Cursors	54
	Radio Buttons	55
	Valuators	55
	Scroll Bars	56
	Grids	56
	Dialog Boxes	57
	Menus	58
	Icons	59
	Sketching	60
	3-D Interaction	63
	Summary	64

Chapter 2	Raster Scan Graphics	65
2-1	Line Drawing Algorithms	65
2-2	Digital Differential Analyzer	66
2-3	Bresenham's Algorithm	70
	Integer Bresenham's Algorithm	74
	General Bresenham's Algorithm	75
	Faster Line Rasterization Algorithms	78
2-4	Circle Generation--Bresenham's Algorithm	79
2-5	Ellipse Generation	88
2-6	General Function Rasterization	95
2-7	Scan Conversion--Generation of the Display	97
	Real-time Scan Conversion	97
	A Simple Active Edge List Using Pointers	99
	A Sorted Active Edge List	99
	An Active Edge List Using a Linked List	101
	Updating the Linked List	102
2-8	Image Compression	104
	Run-length Encoding	104
	Area Image Compression	107
2-9	Displaying Lines, Characters and Polygons	111
	Line Display	111
	Character Display	113
	Solid Area Scan Conversion	114
2-10	Polygon Filling	115
	Scan-converting Polygons	115
2-11	A Simple Parity Scan Conversion Algorithm	118
2-12	Ordered Edge List Polygon Scan Conversion	121
	A Simple Ordered Edge List Algorithm	122
	More Efficient Ordered Edge List Algorithms	123
2-13	The Edge Fill Algorithm	126
2-14	The Edge Flag Algorithm	131
2-15	Seed Fill Algorithms	133
	A Simple Seed Fill Algorithm	134
	A Scan Line Seed Fill Algorithm	137
2-16	Fundamentals of Antialiasing	142
	Supersampling	143
	subStraight Lines	144
	subPolygon Interiors	151
	Simple Area Antialiasing	152
	The Convolution Integral and Antialiasing	156
	Filter Functions	159
2-17	Halftoning	161
	Patterning	161
	Thresholding and Error Distribution	165
	Ordered dither	169

Chapter 3	Clipping	175
3-1	Two-dimensional Clipping	175
	A Simple Visibility Algorithm	176
	End Point Codes	177
3-2	Cohen-Sutherland Subdivision Line
	Clipping Algorithm	181
3-3	Midpoint Subdivision Algorithm	187
3-4	Two-dimensional Line Clipping for
	Convex Boundaries	192
	Partially Visible Lines	193
3-5	Cyrus-Beck Algorithm	196
	Partially Visible Lines	199
	Totally Visible Lines	201
	Totally Invisible Lines	201
	Formal Statement of Cyrus-Beck Algorithm	203
	Irregular Windows	207
3-6	Liang-Barsky Two-dimensional Clipping	208
	Comparison with the Cyrus-Beck Algorithm	212
3-7	Nicholl-Lee-Nicholl Two-dimensional Clipping	217
3-8	Interior and Exterior Clipping	221
3-9	Identifying Convex Polygons and Determining the
	Inward Normal	222
3-10	Splitting Concave Polygons	225
3-11	Three-dimensional Clipping	228
3-12	Three-dimensional Midpoint Subdivision Algorithm	231
3-13	Three-dimensional Cyrus-Beck Algorithm	233
3-14	Liang-Barsky Three-dimensional Clipping	239
3-15	Clipping in Homogeneous Coordinates	243
	The Cyrus-Beck Algorithm	243
	The Liang-Barsky Algorithm	245
3-16	Determining the Inward Normal and
	Three-dimensional Convex Sets	248
3-17	Splitting Concave Volumes	250
3-18	Polygon Clipping	253
3-19	Reentrant Polygon Clipping--
	Sutherland-Hodgman Algorithm	253
	Determining the Visibility of a Point	355
	Line Intersections	257
	The Algorithm	258
3-20	Liang-Barsky Polygon Clipping	265
	Entering and Leaving Vertices	265
	Turning Vertices	267
	Development of the Algorithm	268
	Horizontal and Vertical Edges	271
	The Algorithm	272
3-21	Concave Clipping Regions--
	Weiler-Atherton Algorithm	276
	Special Cases	282
3-22	Character Clipping	286

Chapter 4	Visible Lines and Visible Surfaces	287
4-1	Introduction	287
4-2	Floating Horizon Algorithm	289
	Upper Horizon	290
	Lower Horizon	290
	Function Interpolation	291
	Aliasing	295
	The Algorithm	295
	Cross-hatching	303
4-3	Roberts Algorithm	303
	Volume Matrices	306
	Plane Equations	308
	Viewing Transformations and Volume Matrices	311
	Self-hidden Planes	314
	Lines Hidden by Other Volumes	318
	Penetrating Volumes	327
	Totally Visible Lines	327
	The Algorithm	330
4-4	Warnock Algorithm	343
	Quadtree Data Structure	345
	Subdivision Criteria	347
	The Relationship of a Polygon to a Window	349
	Hierarchical Application of
	Polygon-Window Relations	354
	Finding Surrounder Polygons	355
	The Basic Algorithm	357
4-5	Appel's Algorithm	363
4-6	The Haloed Line Algorithm	366
4-7	Weiler-Atherton Algorithm	370
4-8	A Subdivision Algorithm for Curved Surfaces	374
4-9	Z-Buffer Algorithm	375
	Incrementally Calculating the Depth	378
	Hierarchical Z-Buffer	383
4-10	The A-Buffer Algorithm	384
4-11	List Priority Algorithms	387
4-12	The Newell-Newell-Sancha Algorithm	389
	Implementing the Tests	390
4-13	Binary Space Partitioning	393
	The Schumaker Algorithm	393
	Binary Space Partition Trees	395
	Constructing the BSP Tree	395
	BSP Tree Traversal	398
	Culling	400
	Summary	400
4-14	Scan Line Algorithms	401
4-15	Scan Line Z-Buffer Algorithm	402
4-16	A Spanning Scan Line Algorithm	406
	Invisible Coherence	415
	An Object Space Scan Line Algorithm	416
4-17	Scan Line Algorithms for Curved Surfaces	417
4-18	Octrees	421
	Octree Display	424
	Linear Octrees	426
	Manipulation of Octrees	426
	Boolean Operations	426
	Finding Neighboring Voxels	427
4-19	Marching Cubes	427
	Ambiguous faces	429
4-20	A Visible Surface Ray Tracing Algorithm	432
	Bounding Volumes	435
	Clusters	439
	Constructing the Cluster Tree	440
	Priority Sort	440
	Spatial Subdivision	441
	subUniform Spatial Subdivision	442
	subNonuniform Spatial Subdivision	445
	Ray-Object Intersections	447
	Opaque Visible Surface Algorithm	451
4-21	Summary	456

Chapter 5	Rendering	457
5-1	Introduction	457
5-2	Illumination Models	460
5-3	A Simple Illumination Model	461
	Specular Reflection	462
	The Halfway Vector	465
5-4	Determining the Surface Normal	468
5-5	Determining the Reflection Vector	470
5-6	Gouraud Shading	474
5-7	Phong Shading	476
	Fast Phong Shading	482
5-8	A Simple Illumination Model with Special Effects	483
5-9	A Physically Based Illumination Model	484
	Energy and Intensity	485
	Physically Based Illumination Models	487
	The Torrance-Sparrow Surface Model	488
	Wavelength Dependence--the Fresnel Term	491
	Color Shift	492
	Physical Characteristics of Light Sources	494
5-10	Transparency	496
	Refraction Effects in Transparent Materials	497
	Simple Transparency Models	498
	Z-Buffer Transparency	500
	Pseudotransparency	501
5-11	Shadows	502
	The Scan Conversion Shadow Algorithms	506
	Multiple-pass Visible Surface
	Shadow Algorithms	508
	The Shadow Volume Algorithms	509
	Penumbra Shadows	514
	Ray Tracing Shadow Algorithms	517
5-12	Texture	517
	Mapping Functions	525
	Two-part Texture Mapping	528
	Environment Mapping	531
	Bump Mapping	534
	Procedural Textures	536
	Texture Antialiasing	539
	Mipmapping (Image Pyramids)	542
	Summed Area Tables	544
5-13	Stochastic Models	545
5-14	A Global Illumination Model Using Ray Tracing	548
5-15	A More Complete Global Illumination Model Using
	Ray Tracing	563
5-16	Advances in Ray Tracing	565
	Cone Tracing	565
	Beam Tracing	566
	Pencil Tracing	567
	Stochastic Sampling	567
	Ray Tracing from the Light Source	570
5-17	Radiosity	571
	Enclosures	573
	Form Factors	575
	The Hemicube	577
	Rendering	582
	Substructuring	584
	Progressive Refinement	585
	Sorting	586
	The Ambient Contribution	586
	Adaptive Subdivision	587
	Hemicube Inaccuracies	589
	Alternatives to the Hemicube	592
	Hierarchical Radiosity and Clustering	594
	Radiosity for Specular Environments	596
	The Rendering Equation	597
5-18	Combined Ray Tracing and Radiosity	598
	The Extended Two-pass Algorithm	602
5-19	Color	602
	Chromaticity	603
	Tristimulus Theory of Color	605
	Color Primary Systems	606
	Color Matching Experiment	606
	Chromaticity Diagrams	609
	The 1931 CIE Chromaticity Diagram	611
	Uniform Color Spaces	615
	Gamut Limitations	616
	Transformations Between Color Systems	618
	NTSC Color System	621
	Color Cubes	622
	The CMYK Color System	623
	The Ostwald Color System	623
	The HSV Color System	624
	The HLS Color System	627
	The Munsell Color System	630
	The Pantone System	631
	Gamma Correction	631
5-20	Color Image Quantization	633
	The Bit Cutting Algorithm	634
	The Popularity Algorithm	635
	The Median Cut Algorithm	637
	Octree Quantization	640
	Sequential Scalar Quantization	644
	Other Quantization Algorithms	647
5-21	Color Reproduction	648
	Offset Printing	649
	Color Separation	649
	Tone Reproduction	649
	Gray Balance	650
	The Black Separation	650
	Quantization Effects	650
	Calibration	650
	Gamut Mapping	651
5-22	Specialty Rendering Techniques	654
	Duotone Printing	654
	Rendering Natural Objects	656
	Particle Systems	656

Appendix	Problems and Projects	657
References		665
Index		695

	Order from www.amazon.com or Barnes & Noble

	Back to Books Page

visits since 4/5/99