PrefaceIntroductionMathematical NotationPseudo-CodeContributors1 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)2 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 Grid3 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 Blending4 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 Quantization5 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)6 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 Tables7 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 Objects8 Numerical and Programming Techniques Root Finding Summary Cubic and Quartic Roots (738) A Bézier 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 Transfor