Graphics Gems III (IBM Version)

Graphics Gems III (IBM Version)

by David Kirk
Released December 2012
Publisher(s): Morgan Kaufmann
ISBN: 9780080507552

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

This sequel to Graphics Gems (Academic Press, 1990), and Graphics Gems II (Academic Press, 1991) is a practical collection of computer graphics programming tools and techniques. Graphics Gems III contains a larger percentage of gems related to modeling and rendering, particularly lighting and shading. This new edition also covers image processing, numerical and programming techniques, modeling and transformations, 2D and 3D geometry and algorithms,ray tracing and radiosity, rendering, and more clever new tools and tricks for graphics programming. Volume III also includes a disk containing source codes for either the IBM or Mac versions featuring all code from Volumes I, II, and III.

Author David Kirk lends his expertise to the Graphics Gems series in Volume III with his far-reaching knowledge of modeling and rendering, specifically focusing on the areas of lighting and shading. Volume III includes a disk containing source codes for both the IBM and Mac versions featuring all code from volumes I, II, and III. Graphics Gems I, II, and III are sourcebooks of ideas for graphics programmers. They also serve as toolboxes full of useful tricks and techniques for novice programmers and graphics experts alike. Each volume reflects the personality and particular interests of its respective editor.

  • Includes a disk containing source codes for both the IBM and Mac versions featuring code from volumes I, II, and III
  • Features all new graphics gems
  • Explains techniques for making computer graphics implementations more efficient
  • Emphasizes physically based modeling, rendering, radiosity, and ray tracing
  • Presents techniques for making computer graphics implementations more efficient

Table of contents

  1. Cover image
  2. Title page
  3. Table of Contents
  4. Inside Front Cover
  5. Copyright
  6. About the Cover
  7. FOREWORD
  8. PREFACE
  9. MATHEMATICAL NOTATION
  10. PSEUDO-CODE
  11. CONTRIBUTORS
  12. I: IMAGE PROCESSING
    1. INTRODUCTION TO IMAGE PROCESSING
    2. Chapter 1.1: FAST BITMAP STRETCHING
      1. Publisher Summary
      2. Introduction
      3. The Algorithm
      4. Some Projects Using the Bitmap Stretcher
      5. Further Work
    3. Chapter 1.2: GENERAL FILTERED IMAGE RESCALING
      1. Publisher Summary
    4. Chapter 1.3: OPTIMIZATION OF BITMAP SCALING OPERATIONS
      1. Publisher Summary
    5. Chapter 1.4: A SIMPLE COLOR REDUCTION FILTER
      1. Publisher Summary
      2. Introduction
      3. The Filter
      4. Implementation
      5. Summary
    6. Chapter 1.5: COMPACT ISOCONTOURS FROM SAMPLED DATA
      1. Publisher Summary
      2. Problem
      3. Cube-Based Contouring
      4. Compact Cubes
    7. Chapter 1.6: GENERATING ISOVALUE CONTOURS FROM A PIXMAP
      1. Publisher Summary
    8. Chapter 1.7: COMPOSITING BLACK-AND-WHITE BITMAPS
      1. Publisher Summary
      2. Introduction
      3. Compositing Bitmaps
    9. Chapter 1.8: 2½-D DEPTH-OF-FIELD SIMULATION FOR COMPUTER ANIMATION
      1. Publisher Summary
      2. Introduction
      3. Related Work
      4. The Algorithm
      5. Change-of-Focus Simulation
      6. Acknowledgment and Historical Note
    10. Chapter 1.9: A FAST BOUNDARY GENERATOR FOR COMPOSITED REGIONS
      1. Publisher Summary
      2. Problem
      3. Other Methods
      4. Fast Boundary Generation
      5. Considerations
  13. II: NUMERICAL AND PROGRAMMING TECHNIQUES
    1. INTRODUCTION TO NUMERICAL AND PROGRAMMING TECHNIQUES
    2. Chapter II.1: IEEE FAST SQUARE ROOT
      1. Publisher Summary
    3. Chapter II.2: A SIMPLE FAST MEMORY ALLOCATOR
      1. Publisher Summary
    4. Chapter II.3: THE ROLLING BALL
      1. Publisher Summary
      2. The Rolling-Ball Algorithm
      3. Extensions of the Rolling–Ball Method
      4. Summary
      5. Acknowledgment
    5. Chapter II.4: INTERVAL ARITHMETIC
      1. Publisher Summary
    6. Chapter II.5: FAST GENERATION OF CYCLIC SEQUENCES
      1. Publisher Summary
      2. N = 2 (Review)
      3. N = 3 (Extension)
      4. N =3, 4, 6
      5. N = 6 Derivation
      6. N = 6 (Triggering)
      7. N =7
      8. N = 24
      9. Summary
    7. Chapter II.6: A GENERIC PIXEL SELECTION MECHANISM
      1. Publisher Summary
    8. Chapter II.7: NONUNIFORM RANDOM POINT SETS VIA WARPING
      1. Publisher Summary
    9. Chapter II.8: CROSS PRODUCT IN FOUR DIMENSIONS AND BEYOND
      1. Publisher Summary
      2. Introduction
      3. Tensor Product
      4. Wedge Product
      5. Acknowledgment
    10. Chapter II.9: FACE-CONNECTED LINE SEGMENT GENERATION IN AN n-DIMENSIONAL SPACE
      1. Publisher Summary
  14. III: MODELING AND TRANSFORMATIONS
    1. INTRODUCTION TO MODELING AND TRANSFORMATIONS
    2. Chapter III.1: QUATERNION INTERPOLATION WITH EXTRA SPINS
      1. Publisher Summary
    3. Chapter III.2: DECOMPOSING PROJECTIVE TRANSFORMATIONS
      1. Publisher Summary
      2. Introduction
      3. First Decomposition Algorithm — Perspective in Four Dimensions
      4. Second Decomposition Algorithm — Affine * Projective
      5. Third Decomposition Algorithm — Perspective * Affine
      6. Fourth Decomposition Algorithm — Affine * Perspective
      7. Summary
    4. Chapter III.3: DECOMPOSING LINEAR AND AFFINE TRANSFORMATIONS
      1. Publisher Summary
      2. Goal
      3. Nonsingular Linear Transformations
      4. Singular Linear Transformations
      5. Affine Transformations
    5. Chapter III.4: FAST RANDOM ROTATION MATRICES
      1. Publisher Summary
    6. Chapter III.5: ISSUES AND TECHNIQUES FOR KEYFRAMING TRANSFORMATIONS
      1. Publisher Summary
      2. Introduction
      3. Interpolating in Logarithmic Space
      4. Relative Motion
      5. Linear vs. Splined Interpolation
      6. Subdividing Motion
    7. Chapter III.6: UNIFORM RANDOM ROTATIONS
      1. Publisher Summary
      2. Background
      3. Planar Rotations
      4. Uniform Spherical Distribution
      5. Spatial Rotations
      6. Angles Not Uniform
      7. Uniform Rotations from Gaussians
      8. Subgroup Algorithm
      9. Distribution Check
      10. Acknowledgments
    8. Chapter III.7: INTERPOLATION USING BÉZIER CURVES
      1. Publisher Summary
      2. Introduction
      3. Numeric Solution
      4. Symbolic Solution
      5. Implementation
    9. Chapter III.8: RIGID PHYSICALLY BASED SUPERQUADRICS
      1. Publisher Summary
      2. Introduction
      3. Review of Superquadrics
      4. Rigid Physically Based Superquadric Quantities
      5. Conclusion
      6. Acknowledgment
      7. Appendix A Review of Superquadric Geometric Quantities
      8. Appendix B Some Equations of Rigid-Body Motion
      9. Appendix C How to Compute β(m, n), and Γ(n)
      10. Appendix D Sketch of Derivation of Superquadric Volume, Mass, and Inertia Tensor
  15. IV: 2-D GEOMETRY AND ALGORITHMS
    1. INTRODUCTION TO 2-D GEOMETRY AND ALGORITHMS
    2. Chapter IV.1: A PARAMETRIC ELLIPTICAL ARC ALGORITHM
      1. Publisher Summary
      2. The Algorithm
      3. Digital Generation of Sinusoids
      4. Conjugate Diameters
      5. Simplifying the Computations
    3. Chapter IV.2: SIMPLE CONNECTION ALGORITHM FOR 2-D DRAWING
      1. Publisher Summary
      2. Introduction
      3. Terms and Definitions
      4. Translate and Rotate Algorithm
      5. Overcrossing Correction
      6. Conclusions and Acknowledgments
    4. Chapter IV.3: A FAST CIRCLE CLIPPING ALGORITHM
      1. Publisher Summary
      2. Introduction
      3. Algorithm
      4. Notes
    5. Chapter IV.4: EXACT COMPUTATION OF 2-D INTERSECTIONS
      1. Publisher Summary
    6. Chapter IV.5: JOINING TWO LINES WITH A CIRCULAR ARC FILLET
      1. Publisher Summary
      2. Problem
      3. Method
    7. Chapter IV.6: FASTER LINE SEGMENT INTERSECTION
      1. Publisher Summary
      2. Problem
      3. Algorithm
      4. Timing Measurements/Further Optimizations
      5. Implementation Notes
    8. Chapter IV.7: SOLVING THE PROBLEM OF APOLLONIUS AND OTHER RELATED PROBLEMS
      1. Publisher Summary
  16. V: 3-D GEOMETRY AND ALGORITHMS
    1. INTRODUCTION TO 3-D GEOMETRY AND ALGORITHMS
    2. Chapter V.1: TRIANGLES REVISITED
      1. Publisher Summary
    3. Chapter V.2: PARTITIONING A 3-D CONVEX POLYGON WITH AN ARBITRARY PLANE
      1. Publisher Summary
      2. Introduction
      3. Input
      4. Output
      5. Algorithm Overview
      6. Procedure
      7. Enhancements
      8. Acknowledgments
    4. Chapter V.3: SIGNED DISTANCE FROM POINT TO PLANE
      1. Publisher Summary
    5. Chapter V.4: GROUPING NEARLY COPLANAR POLYGONS INTO COPLANAR SETS
      1. Publisher Summary
      2. Introduction
      3. Applications
      4. Derivation
      5. Comparing Two Planes
    6. Chapter V.5: NEWELL’S METHOD FOR COMPUTING THE PLANE EQUATION OF A POLYGON
      1. Publisher Summary
      2. Newell’s Method
    7. Chapter V.6: PLANE-TO-PLANE INTERSECTION
      1. Publisher Summary
    8. Chapter V.7: TRIANGLE-CUBE INTERSECTION
      1. Publisher Summary
    9. Chapter V.8: FAST n-DIMENSIONAL EXTENT OVERLAP TESTING
      1. Publisher Summary
      2. Using the Class
      3. Implementation
      4. Pseudo-code
    10. Chapter V.9: SUBDIVIDING SIMPLICES
      1. Publisher Summary
      2. Problem
      3. Recursively Subdividing Simplices
      4. Symmetrically Subdividing Simplices
      5. Applications
    11. Chapter V.10: UNDERSTANDING SIMPLOIDS
      1. Publisher Summary
      2. Problem
      3. Simploids
      4. Simploids to Simplices
      5. Splitting Simplices into Simploids
    12. Chapter V.11: CONVERTING BÉZIER TRIANGLES INTO RECTANGULAR PATCHES
      1. Publisher Summary
      2. Converting Quadratic Triangles
      3. Converting Cubic Triangles
    13. Chapter V.12: CURVE TESSELLATION CRITERIA THROUGH SAMPLING
      1. Publisher Summary
  17. VI: RAY TRACING AND RADIOSITY
    1. PART VI: INTRODUCTION TO RAY TRACING AND RADIOSITY
    2. Chapter VI.1: RAY TRACING WITH THE BSP TREE
      1. Publisher Summary
      2. Introduction
      3. Acknowledgments
    3. Chapter VI.2: INTERSECTING A RAY WITH A QUADRIC SURFACE
      1. Publisher Summary
      2. The Equation of a Quadratic Surface
      3. Intersection of a Ray with a Quadric Surface
      4. An Efficient Ray Rejection Test
      5. Determining the Surface Normal of a Quadric Surface
    4. Chapter VI.3: USE OF RESIDENCY MASKS AND OBJECT SPACE PARTITIONING TO ELIMINATE RAY-OBJECT INTERSECTION CALCULATIONS
      1. Publisher Summary
      2. Introduction
      3. Residency Masks
    5. Chapter VI.4: A PANORAMIC VIRTUAL SCREEN FOR RAY TRACING
      1. Publisher Summary
      2. Introduction
      3. Cylindrical Virtual Screen
      4. Vertical Sampling
      5. An Application: Martian Panoramas
      6. Conclusion
    6. Chapter VI.5: RECTANGULAR BOUNDING VOLUMES FOR POPULAR PRIMITIVES
      1. Publisher Summary
      2. Cube
      3. Polygons
      4. Cylinder
      5. Cone
      6. Conic
      7. Sphere
      8. Torus
    7. Chapter VI.6: A LINEAR-TIME SIMPLE BOUNDING VOLUME ALGORITHM
      1. Publisher Summary
    8. Chapter VI.7: PHYSICALLY CORRECT DIRECT LIGHTING FOR DISTRIBUTION RAY TRACING
      1. Publisher Summary
      2. Sampling for Spherical Luminaire
      3. Sampling for Triangular Luminaire
    9. Chapter VI 8: HEMISPHERICAL PROJECTION OF A TRIANGLE
      1. Publisher Summary
    10. Chapter VI 9: LINEAR RADIOSITY APPROXIMATION USING VERTEX-TO-VERTEX FORM FACTORS
      1. Publisher Summary
      2. Acknowledgment
    11. Chapter VI.10: DELTA FORM-FACTOR CALCULATION FOR THE CUBIC TETRAHEDRAL ALGORITHM
      1. Publisher Summary
    12. VI. II: ACCURATE FORM-FACTOR COMPUTATION
      1. Publisher Summary
  18. VII: RENDERING
    1. INTRODUCTION TO RENDERING
    2. Chapter VII.1: THE SHADOW DEPTH MAP REVISITED
      1. Publisher Summary
      2. Introduction
      3. The Shadow Depth Map
      4. The Moiré Pattern Problem
      5. A Boundary Case
      6. Some Optimizations
      7. Conclusions
    3. Chapter VII.2: FAST LINEAR COLOR RENDERING
      1. Publisher Summary
    4. Chapter VII.3: EDGE AND BIT-MASK CALCULATIONS FOR ANTI-ALIASING
      1. Publisher Summary
      2. Introduction
      3. Alternating Bresenham Edge-Calculator
      4. Bit-Mask Calculations
      5. Implementation Details
    5. Chapter VII.4: FAST SPAN CONVERSION: UNROLLING SHORT LOOPS
      1. Publisher Summary
      2. Introduction
      3. Implementation
    6. Chapter VII.5: PROGRESSIVE IMAGE REFINEMENT VIA GRIDDED SAMPLING
      1. Publisher Summary
    7. Chapter VII.6: ACCURATE POLYGON SCAN CONVERSION USING HALF-OPEN INTERVALS
      1. Publisher Summary
      2. Introduction
      3. Derivation
      4. Algorithm
    8. Chapter VII.7: DARKLIGHTS
      1. Publisher Summary
    9. Chapter VII.8: ANTI-ALIASING IN TRIANGULAR PIXELS
      1. Publisher Summary
    10. Chapter VII.9: MOTION BLUR ON GRAPHICS WORKSTATIONS
      1. Publisher Summary
      2. Supersampling in Time
      3. Computing on Fields
      4. Combining Spatial and Temporal Anti-aliasing
      5. Reducing Interlace Artifacts
      6. Other Effects
      7. Implementation Tricks
      8. Examples
    11. Chapter VII.10: THE SHADER CACHE: A RENDERING PIPELINE ACCELERATOR
      1. Publisher Summary
      2. Introduction
      3. Shading Calculations
      4. Implementation
      5. Effectiveness
      6. Results
  19. C: C UTILITIES
    1. Chapter 8.1: GRAPHICS GEMS C HEADER FILE
    2. Chapter 8.2: 2-D AND 3-D VECTOR C LIBRARY: Corrected and Indexed
    3. Chapter 8.3: USEFUL C MACROS FOR VECTOR OPERATIONS
  20. C APPENDIX: C IMPLEMENTATIONS
    1. FAST BITMAP STRETCHING: (page 4)
    2. GENERAL FILTERED IMAGE RESCALING: (page 8)
    3. OPTIMIZATION OF BITMAP SCALING OPERATIONS: (page 17)
    4. A SIMPLE COLOR REDUCTION FILTER: (page 20)
    5. GENERATING ISOVALUE CONTOURS FROM A PIXMAP: (page 29)
    6. A FAST BOUNDARY GENERATOR FOR COMPOSITED REGIONS: (page 39)
    7. IEEE FAST SQUARE ROOT: (page 48)
    8. A SIMPLE FAST MEMORY ALLOCATOR: (page 49)
    9. THE ROLLING BALL: (page 51)
    10. INTERVAL ARITHMETIC: (page 61)
    11. FAST GENERATION OF CYCLIC SEQUENCES: (page 67)
    12. FACE-CONNECTED LINE SEGMENT GENERATION IN AN n-DIMENSIONAL SPACE: (page 89)
    13. QUATERNION INTERPOLATION WITH EXTRA SPINS: (page 96)
    14. FAST RANDOM ROTATION MATRICES: (page 117)
    15. UNIFORM RANDOM ROTATIONS: (page 124)
    16. INTERPOLATION USING BÉZIER CURVES: (page 133)
    17. PHYSICALLY BASED SUPERQUADRICS: (page 137)
    18. A PARAMETRIC ELLIPTICAL ARC ALGORITHM: (page 164)
    19. SIMPLE CONNECTION ALGORITHM FOR 2-D DRAWING: (page 173)
    20. A FAST CIRCLE CLIPPING ALGORITHM: (page 182)
    21. EXACT COMPUTATION OF 2-D INTERSECTIONS: (page 188)
    22. JOINING TWO LINES WITH A CIRCULAR ARC FILLET: (page 193)
    23. FASTER LINE SEGMENT INTERSECTION: (page 199)
    24. PARTITIONING A 3-D CONVEX POLYGON WITH AN ARBITRARY PLANE: (page 219)
    25. SIGNED DISTANCE FROM POINT TO PLANE: (page 223)
    26. GROUPING NEARLY COPLANAR POLYGONS INTO COPLANAR SETS: (page 225)
    27. NEWELL’S METHOD FOR COMPUTING THE PLANE EQUATION OF A POLYGON: (page 231)
    28. PLANE-TO-PLANE INTERSECTION: (page 233)
    29. TRIANGLE–CUBE INTERSECTION: (page 236)
    30. FAST n-DIMENSIONAL EXTENT OVERLAP TESTING: (page 240)
    31. SUBDIVIDING SIMPLICES: (page 244)
    32. CONVERTING BÉZIER TRIANGLES INTO RECTANGULAR PATCHES: (page 256)
    33. RAY TRACING WITH THE BSP TREE: (page 271)
    34. INTERSECTING A RAY WITH A QUADRIC SURFACE: (page 275)
    35. A PANORAMIC VIRTUAL SCREEN FOR RAY TRACING: (page 288)
    36. RECTANGULAR BOUNDING VOLUMES FOR POPULAR PRIMITIVES: (page 295)
    37. PHYSICALLY CORRECT DIRECT LIGHTING FOR DISTRIBUTION RAY TRACING: (page 307)
    38. HEMISPHERICAL PROJECTION OF A TRIANGLE: (page 314)
    39. DELTA FORM-FACTOR CALCULATION FOR THE CUBIC TETRAHEDRAL ALGORITHM: (page 324)
    40. ACCURATE FORM-FACTOR COMPUTATION: (page 329)
    41. THE SHADOW DEPTH MAP REVISITED: (page 338)
    42. FAST LINEAR COLOR RENDERING: (page 343)
    43. EDGE AND BIT-MASK CALCULATIONS FOR ANTI-ALIASING: (page 349)
    44. FAST SPAN CONVERSION: UNROLLING SHORT LOOPS: (page 355)
    45. PROGRESSIVE IMAGE REFINEMENT VIA GRIDDED SAMPLING: (page 358)
    46. ACCURATE POLYGON SCAN CONVERSION USING HALF-OPEN INTERVALS: (page 362)
    47. MOTION BLUR ON GRAPHICS WORKSTATIONS: (page 374)
  21. REFERENCES
  22. INDEX

Product information

  • Title: Graphics Gems III (IBM Version)
  • Author(s): David Kirk
  • Release date: December 2012
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780080507552