![]() |
PROCEDURAL ELEMENTS COMPUTER GRAPHICS Second Edition by David F. Rogers |
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 |