| |
| |
| Preface | |
| |
| |
| Introduction | |
| |
| |
| Mathematical Notation | |
| |
| |
| Pseudo-Code | |
| |
| |
| Contributors | |
| |
| |
| |
| 2D Geometry | |
| |
| |
| Useful 2D Geometry | |
| |
| |
| Trigonometry Summary | |
| |
| |
| Useful Trigonometry | |
| |
| |
| Trigonometric Functions at Select Points | |
| |
| |
| Triangles | |
| |
| |
| Generating Random Points in Triangles (649) | |
| |
| |
| Fast Line-Edge Intersections on a Uniform Grid (651) | |
| |
| |
| Anti-Aliasing Summary | |
| |
| |
| Area of Intersection: Circle and a Half-Plane | |
| |
| |
| Area of Intersection: Circle and a Thick Line | |
| |
| |
| Area of Intersection: Two Circles | |
| |
| |
| Vertical Distance from a Point to a Line | |
| |
| |
| A Fast 2D Point-on-Line Test (654) | |
| |
| |
| Fast Circle-Rectangle Intersection Checking (656) | |
| |
| |
| |
| 2D Rendering | |
| |
| |
| Circles of Integral Radius on Integer Lattices | |
| |
| |
| Nice Numbers for Graph Labels (657) | |
| |
| |
| Efficient Generation of Sampling Jitter Using Look-up Tables (660) | |
| |
| |
| Scan Conversion Summary | |
| |
| |
| Fast Anti-Aliasing Polygon Scan Conversion (662) | |
| |
| |
| Generic Convex Polygon Scan Conversion and Clipping (667) | |
| |
| |
| Concave Polygon Scan Conversion (681) | |
| |
| |
| Fast Scan Conversion of Arbitrary Polygons | |
| |
| |
| Line-Drawing Summary | |
| |
| |
| Digital Line Drawing (685) | |
| |
| |
| Symmetric Double Step Line Algorithm (686) | |
| |
| |
| Rendering Anti-Aliased Lines (690) | |
| |
| |
| An Algorithm for Filling in 2D Wide Line Bevel Joints | |
| |
| |
| Rendering Fat Lines on a Raster Grid | |
| |
| |
| Two-Dimensional Clipping: A Vector-Based Approach (694) | |
| |
| |
| Periodic Tilings of the Plane on a Raster Grid | |
| |
| |
| |
| Image Processing | |
| |
| |
| Anti-Aliasing Filters Summary | |
| |
| |
| Convenient Anti-Aliasing Filters That Minimize "Bumpy" Sampling | |
| |
| |
| Filters for Common Resampling Tasks | |
| |
| |
| Smoothing Enlarged Monochrome Images | |
| |
| |
| Median Finding on a 3 x 3 Grid (711) | |
| |
| |
| Ordered Dithering (713) | |
| |
| |
| A Fast Algorithm for General Raster Rotation | |
| |
| |
| Useful 1-to-1 Pixel Transforms | |
| |
| |
| Alpha Blending | |
| |
| |
| |
| Frame Buffer Techniques | |
| |
| |
| Frame Buffers and Color Maps | |
| |
| |
| Reading a Write-Only Write Mask | |
| |
| |
| A Digital "Dissolve" Effect (715) | |
| |
| |
| Mapping RGB Triples onto Four Bits (718) | |
| |
| |
| What Are the Coordinates of a Pixel? | |
| |
| |
| Proper Treatment of Pixels as Integers (719) | |
| |
| |
| Normal Coding | |
| |
| |
| Recording Animation in Binary Order for Progressive Temporal Refinement (720) | |
| |
| |
| 1-to-1 Pixel Transforms Optimized through Color-Map Manipulation | |
| |
| |
| A Seed Fill Algorithm (721) | |
| |
| |
| Filling a Region in a Frame Buffer | |
| |
| |
| Precalculating Addresses for Fast Fills, Circles, and Lines | |
| |
| |
| A Simple Method for Color Quantization: Octree Quantization | |
| |
| |
| |
| 3D Geometry | |
| |
| |
| Useful 3D Geometry | |
| |
| |
| An Efficient Bounding Sphere (723) | |
| |
| |
| Intersection of Two Lines in Three-Space | |
| |
| |
| Intersection of Three Planes | |
| |
| |
| Mapping Summary | |
| |
| |
| Digital Cartography for Computer Graphics | |
| |
| |
| Albers Equal-Area Conic Map Projection (726) | |
| |
| |
| Boxes and Spheres Summary | |
| |
| |
| Spheres-to-Voxels Conversion | |
| |
| |
| A Simple Method for Box-Sphere Intersection Testing (730) | |
| |
| |
| |
| 3D Rendering | |
| |
| |
| 3D Grid Hashing Function (733) | |
| |
| |
| Backface Culling | |
| |
| |
| Fast Dot Products for Shading | |
| |
| |
| Scanline Depth Gradient of a Z-Buffered Triangle | |
| |
| |
| Simulating Fog and Haze | |
| |
| |
| Interpretation of Texture Map Indices | |
| |
| |
| Multidimensional Sum Tables | |
| |
| |
| |
| Ray Tracing | |
| |
| |
| A Simple Ray Rejection Test | |
| |
| |
| Ray-Object Intersection Summary | |
| |
| |
| Intersection of a Ray with a Sphere | |
| |
| |
| An Efficient Ray-Polygon Intersection (735) | |
| |
| |
| Fast Ray-Polygon Intersection | |
| |
| |
| Fast Ray-Box Intersection (736) | |
| |
| |
| Shadow Attenuation for Ray Tracing Transparent Objects | |
| |
| |
| |
| Numerical and Programming Techniques | |
| |
| |
| Root Finding Summary | |
| |
| |
| Cubic and Quartic Roots (738) | |
| |
| |
| A Bezier Curve-Based Root-Finder (787) | |
| |
| |
| Using Sturm Sequences to Bracket Real Roots of Polynomial Equations (743) | |
| |
| |
| Distance Measures Summary | |
| |
| |
| A High-Speed, Low Precision Square Root (756) | |
| |
| |
| A Fast Approximation to the Hypotenuse (758) | |
| |
| |
| A Fast Approximation to 3D Euclidean Distance | |
| |
| |
| Full-Precision Constants | |
| |
| |
| Converting between Bits and Digits | |
| |
| |
| Storage-free Swapping | |
| |
| |
| Generating Random Integers | |
| |
| |
| Fast 2D-3D Rotation | |
| |
| |
| Bit Patterns for Encoding Angles | |
| |
| |
| Bit Interleaving for Quad- or Octrees (759) | |
| |
| |
| A Fast HSL-to-RGB Transform (763) | |
| |
| |
| |
| Matrix Techniques | |
| |
| |
| Matrix Identities | |
| |
| |
| Rotation Matrix Methods Summary | |
| |
| |
| Transforming Axes | |
| |
| |
| Fast Matrix Multiplication | |
| |
| |
| A Virtual Trackball | |
| |
| |
| Matrix Orthogonalization (765) | |
| |
| |
| Rotation Tools | |
| |
| |
| Matrix Inversion (766) | |
| |
| |
| Matrices and Transformations | |
| |
| |
| Efficient Post-Concatenation of Transformation Matrices (770) | |
| |
| |
| |
| Modeling and Transformations | |
| |
| |
| Transformation Identities | |
| |
| |
| Fixed-Point Trigonometry with CORDIC Iterations (773) | |
| |
| |
| Using Quaternions for Coding 3D Transformations (775) | |
| |
| |
| 3D Viewing and Rotation Using Orthonormal Bases (778) | |
| |
| |
| The Use of Coordinate Frames in Computer Graphics | |
| |
| |
| Forms, Vectors, and Transforms (780) | |
| |
| |
| Properties of Surface-Normal Transformations | |
| |
| |
| Transforming Axis-Aligned Bounding Boxes (785) | |
| |
| |
| Constructing Shapes Summary | |
| |
| |
| Defining Surfaces from Sampled Data | |
| |
| |
| Defining Surfaces from Contour Data | |
| |
| |
| Computing Surface Normals for 3D Models | |
| |
| |
| Calculation of Reference Frames along a Space Curve | |
| |
| |
| |
| Curves and Surfaces | |
| |
| |
| Planar Cubic Curves | |
| |
| |
| Explicit Cubic Spline Interpolation Formulas | |
| |
| |
| Fast Spline Drawing | |
| |
| |
| Some Properties of Bezier Curves | |
| |
| |
| Tutorial on Forward Differencing | |
| |
| |
| Integration of Bernstein Basis Functions | |
| |
| |
| Solving the Nearest-Point-on-Curve Problem (787) | |
| |
| |
| An Algorithm for Automatically Fitting Digitized Curves (797) | |
| |
| |
| |
| Appendix I: C Utilities | |
| |
| |
| Graphics Gems C Header File | |
| |
| |
| 2D and 3D Vector C Library | |
| |
| |
| Memory Allocation in C | |
| |
| |
| Two Useful C Macros | |
| |
| |
| How To Build Circular Structures in C | |
| |
| |
| How To Use C Register Variables to Point to 2D Arrays | |
| |
| |
| |
| Appendix 2: C Implementations | |
| |
| |
| The C Code follows the same order as the Gems | |
| |
| |
| References | |
| |
| |
| Index | |