Cover     PROCEDURAL ELEMENTS

FOR

COMPUTER GRAPHICS

Second Edition

by

David F. Rogers

 
 

TABLE of CONTENTS
Prefacexv
Preface to the First Editionxvii
    
Chapter 1 Introduction To Computer Graphics 1
1-1Overview of Computer Graphics1
    Representing Pictures2
    Preparing Pictures for Presentation2
    Presenting Previously Prepared Pictures3
1-2Raster Refresh Graphics Displays6
    Frame Buffers7
1-3Cathode Ray Tube Basics11
    Color CRT Raster Scan Monitors13
1-4Video Basics14
    American Standard Video14
    High Definition Television17
1-5Flat Panel Displays17
    Flat CRT17
    Plasma Display18
    Electroluminescent Display21
    Liquid Crystal Display21
1-6Hardcopy Output Devices25
    Electrostatic Plotters25
    Ink Jet Plotters26
    Thermal Plotters28
    Dye Sublimation Printers30
    Pen and Ink Plotters31
    Laser Printers34
    Color Film Cameras36
1-7Logical Interactive Devices37
    The Locator Function38
    The Valuator Function39
    The Buttom or Choice Function39
    The Pick Function39
1-8Physical Interactive Devices39
    Tablets40
    Touch Panels41
    Control Dials41
    Joystick42
    Trackball42
    Mouse44
    Function Switches44
    Light Pen45
    Spaceball46
    Data Glove46
    Simulation of Alternate Devices47
1-9Data Generation Devices49
    Scanners49
    Three-dimensional Digitizers50
    Motion Capture51
1-10Graphical User Interfaces52
    Command Line Interface52
    Cursors54
    Radio Buttons55
    Valuators55
    Scroll Bars56
    Grids56
    Dialog Boxes57
    Menus58
    Icons59
    Sketching60
    3-D Interaction63
    Summary64
    
Chapter 2 Raster Scan Graphics 65
2-1Line Drawing Algorithms65
2-2Digital Differential Analyzer66
2-3Bresenham's Algorithm70
    Integer Bresenham's Algorithm74
    General Bresenham's Algorithm75
    Faster Line Rasterization Algorithms78
2-4Circle Generation--Bresenham's Algorithm79
2-5Ellipse Generation88
2-6General Function Rasterization95
2-7Scan Conversion--Generation of the Display97
    Real-time Scan Conversion97
    A Simple Active Edge List Using Pointers99
    A Sorted Active Edge List99
    An Active Edge List Using a Linked List101
    Updating the Linked List102
2-8Image Compression104
    Run-length Encoding104
    Area Image Compression107
2-9Displaying Lines, Characters and Polygons111
    Line Display111
    Character Display113
    Solid Area Scan Conversion114
2-10Polygon Filling115
    Scan-converting Polygons115
2-11A Simple Parity Scan Conversion Algorithm118
2-12Ordered Edge List Polygon Scan Conversion121
    A Simple Ordered Edge List Algorithm122
    More Efficient Ordered Edge List Algorithms123
2-13The Edge Fill Algorithm126
2-14The Edge Flag Algorithm131
2-15Seed Fill Algorithms133
A Simple Seed Fill Algorithm134
    A Scan Line Seed Fill Algorithm137
2-16Fundamentals of Antialiasing142
    Supersampling143
    subStraight Lines144
    subPolygon Interiors151
    Simple Area Antialiasing152
    The Convolution Integral and Antialiasing156
    Filter Functions159
2-17Halftoning161
    Patterning161
    Thresholding and Error Distribution165
    Ordered dither169
    
Chapter 3 Clipping 175
3-1Two-dimensional Clipping175
    A Simple Visibility Algorithm176
    End Point Codes177
3-2Cohen-Sutherland Subdivision Line
    Clipping Algorithm181
3-3Midpoint Subdivision Algorithm187
3-4Two-dimensional Line Clipping for
    Convex Boundaries192
    Partially Visible Lines193
3-5Cyrus-Beck Algorithm196
    Partially Visible Lines199
    Totally Visible Lines201
    Totally Invisible Lines201
    Formal Statement of Cyrus-Beck Algorithm203
    Irregular Windows207
3-6Liang-Barsky Two-dimensional Clipping208
    Comparison with the Cyrus-Beck Algorithm212
3-7Nicholl-Lee-Nicholl Two-dimensional Clipping217
3-8Interior and Exterior Clipping221
3-9Identifying Convex Polygons and Determining the
    Inward Normal222
3-10Splitting Concave Polygons225
3-11Three-dimensional Clipping228
3-12Three-dimensional Midpoint Subdivision Algorithm231
3-13Three-dimensional Cyrus-Beck Algorithm233
3-14Liang-Barsky Three-dimensional Clipping239
3-15Clipping in Homogeneous Coordinates243
    The Cyrus-Beck Algorithm243
    The Liang-Barsky Algorithm245
3-16Determining the Inward Normal and
    Three-dimensional Convex Sets248
3-17Splitting Concave Volumes250
3-18Polygon Clipping253
3-19Reentrant Polygon Clipping--
    Sutherland-Hodgman Algorithm253
    Determining the Visibility of a Point355
    Line Intersections257
    The Algorithm258
3-20Liang-Barsky Polygon Clipping265
    Entering and Leaving Vertices265
    Turning Vertices267
    Development of the Algorithm268
    Horizontal and Vertical Edges271
    The Algorithm272
3-21Concave Clipping Regions--
     Weiler-Atherton Algorithm276
    Special Cases282
3-22Character Clipping286
    
Chapter 4 Visible Lines and Visible Surfaces 287
4-1Introduction287
4-2Floating Horizon Algorithm289
    Upper Horizon290
    Lower Horizon290
    Function Interpolation291
    Aliasing295
    The Algorithm295
    Cross-hatching303
4-3Roberts Algorithm303
    Volume Matrices306
    Plane Equations308
    Viewing Transformations and Volume Matrices311
    Self-hidden Planes314
    Lines Hidden by Other Volumes318
    Penetrating Volumes327
    Totally Visible Lines327
    The Algorithm330
4-4Warnock Algorithm343
    Quadtree Data Structure345
    Subdivision Criteria347
    The Relationship of a Polygon to a Window349
    Hierarchical Application of
     Polygon-Window Relations354
    Finding Surrounder Polygons355
    The Basic Algorithm357
4-5Appel's Algorithm363
4-6The Haloed Line Algorithm366
4-7Weiler-Atherton Algorithm370
4-8A Subdivision Algorithm for Curved Surfaces374
4-9Z-Buffer Algorithm375
    Incrementally Calculating the Depth378
    Hierarchical Z-Buffer383
4-10The A-Buffer Algorithm384
4-11List Priority Algorithms387
4-12The Newell-Newell-Sancha Algorithm389
Implementing the Tests390
4-13Binary Space Partitioning393
    The Schumaker Algorithm393
    Binary Space Partition Trees395
    Constructing the BSP Tree395
    BSP Tree Traversal398
    Culling400
    Summary400
4-14Scan Line Algorithms401
4-15Scan Line Z-Buffer Algorithm402
4-16A Spanning Scan Line Algorithm406
    Invisible Coherence415
    An Object Space Scan Line Algorithm416
4-17Scan Line Algorithms for Curved Surfaces417
4-18Octrees421
    Octree Display424
    Linear Octrees426
    Manipulation of Octrees426
    Boolean Operations426
    Finding Neighboring Voxels427
4-19Marching Cubes427
    Ambiguous faces429
4-20A Visible Surface Ray Tracing Algorithm432
    Bounding Volumes435
    Clusters439
    Constructing the Cluster Tree440
    Priority Sort440
    Spatial Subdivision441
    subUniform Spatial Subdivision442
    subNonuniform Spatial Subdivision445
    Ray-Object Intersections447
    Opaque Visible Surface Algorithm451
4-21Summary456
    
Chapter 5 Rendering 457
5-1Introduction457
5-2Illumination Models460
5-3A Simple Illumination Model461
    Specular Reflection462
    The Halfway Vector465
5-4Determining the Surface Normal468
5-5Determining the Reflection Vector470
5-6Gouraud Shading474
5-7Phong Shading476
    Fast Phong Shading482
5-8A Simple Illumination Model with Special Effects483
5-9A Physically Based Illumination Model484
    Energy and Intensity485
    Physically Based Illumination Models487
    The Torrance-Sparrow Surface Model488
    Wavelength Dependence--the Fresnel Term491
    Color Shift492
    Physical Characteristics of Light Sources494
5-10Transparency496
    Refraction Effects in Transparent Materials497
    Simple Transparency Models498
    Z-Buffer Transparency500
    Pseudotransparency501
5-11Shadows502
    The Scan Conversion Shadow Algorithms506
    Multiple-pass Visible Surface
    Shadow Algorithms508
    The Shadow Volume Algorithms509
    Penumbra Shadows514
    Ray Tracing Shadow Algorithms517
5-12Texture517
    Mapping Functions525
    Two-part Texture Mapping528
    Environment Mapping531
    Bump Mapping534
    Procedural Textures536
    Texture Antialiasing539
    Mipmapping (Image Pyramids)542
    Summed Area Tables544
5-13Stochastic Models545
5-14A Global Illumination Model Using Ray Tracing548
5-15A More Complete Global Illumination Model Using
Ray Tracing563
5-16Advances in Ray Tracing565
    Cone Tracing565
    Beam Tracing566
    Pencil Tracing567
    Stochastic Sampling567
    Ray Tracing from the Light Source570
5-17Radiosity571
    Enclosures573
    Form Factors575
    The Hemicube577
    Rendering582
    Substructuring584
    Progressive Refinement585
    Sorting586
    The Ambient Contribution586
    Adaptive Subdivision587
    Hemicube Inaccuracies589
    Alternatives to the Hemicube592
    Hierarchical Radiosity and Clustering594
    Radiosity for Specular Environments596
    The Rendering Equation597
5-18Combined Ray Tracing and Radiosity598
    The Extended Two-pass Algorithm602
5-19Color602
    Chromaticity603
    Tristimulus Theory of Color605
    Color Primary Systems606
    Color Matching Experiment606
    Chromaticity Diagrams609
    The 1931 CIE Chromaticity Diagram611
    Uniform Color Spaces615
    Gamut Limitations616
    Transformations Between Color Systems618
    NTSC Color System621
    Color Cubes622
    The CMYK Color System623
    The Ostwald Color System623
    The HSV Color System624
    The HLS Color System627
    The Munsell Color System630
    The Pantone System631
    Gamma Correction631
5-20Color Image Quantization633
    The Bit Cutting Algorithm634
    The Popularity Algorithm635
    The Median Cut Algorithm637
    Octree Quantization640
    Sequential Scalar Quantization644
    Other Quantization Algorithms647
5-21Color Reproduction648
    Offset Printing649
    Color Separation649
    Tone Reproduction649
    Gray Balance650
    The Black Separation650
    Quantization Effects650
    Calibration650
    Gamut Mapping651
5-22Specialty Rendering Techniques654
    Duotone Printing654
    Rendering Natural Objects656
    Particle Systems656
    
AppendixProblems and Projects657
References665
Index695
 
 Order from www.amazon.com or Barnes & Noble
 
 Back to Books Page


visits since 4/5/99