ph@miro.Berkeley.EDU (Paul Heckbert) (08/03/90)
Here is a table of contents for the book "Graphics Gems" that will be coming out through Academic Press at SIGGRAPH: "Graphics Gems", edited by Andrew Glassner, 833 pages total, 158 page C code appendix. The C code will be available in a few days via anonymous ftp (watch comp.graphics for an announcement). (c) copyright 1990, Academic Press, New York (*) Indicates an implementation in C in Appendix II Preface Introduction Mathematical Notation Pseudo-Code Contributors 1. 2D Geometry Useful 2D Geometry - Andrew Glassner Trigonometry Summary Useful Trigonometry - Andrew Glassner Trigonometric Functions at Select Points - Alan W. Paeth Triangles - Ronald Goldman Generating Random Points in Triangles (*) - Greg Turk Fast Line-Edge Intersections on a Uniform Grid (*) - Andrew Shapira Anti-Aliasing Summary Area of Intersection: Circle and a Half-Plane - Kelvin Thompson Area of Intersection: Circle and a Thick Line - Kelvin Thompson Area of Intersection: Two Circles - Kelvin Thompson Anti-Aliasing Summary Vertical Distance From a Point to a Line - Kelvin Thompson A Fast 2D Point-on-Line Test (*) - Alan W. Paeth Fast Circle-Rectangle Intersection Checking (*) - Clifford A. Shaffer 2. 2D Rendering Circles of Integral Radius on Integer Lattices - Alan W. Paeth Nice Numbers for Graph Labels (*) - Paul S. Heckbert Efficient Generation of Sampling Jitter Using Look-up Tables (*) - Joseph M. Cychosz Scan Conversion Summary Fast Anti-Aliasing Polygon Scan Conversion (*) - Jack C. Morrison Generic Convex Polygon Scan Conversion and Clipping (*) - Paul S. Heckbert Concave Polygon Scan Conversion (*) - Paul S. Heckbert Fast Scan Conversion of Arbitrary Polygons - Bob Wallis Line Drawing Summary Digital Line Drawing (*) - Paul S. Heckbert Symmetric Double Step Line Algorithm (*) - Brian Wyvill Rendering Anti-Aliased Lines (*) - Kelvin Thompson An Algorithm for Filling in 2D Wide Line Bevel Joints - Jack Ritter Rendering Fat Lines on a Raster Grid - Bob Wallis Two-Dimensional Clipping: A Vector-Based Approach (*) - Hans J.W. Spoelder, Fons H. Ullings Periodic Tilings of the Plane on a Raster Grid - Greg Lee, Mike Penk, Bob Wallis 3. Image Processing Anti-Aliasing Filters Summary Convenient Anti-Aliasing Filters That Minimize "Bumpy" Sampling - Mark J. Pavicic FIlters for Common Resampling Tasks - Ken Turkowski Smoothing Enlarged Monochrome Images - John Olsen Median Finding on a 3x3 Grid (*) - Alan W. Paeth Ordered Dithering (*) - Stephen Hawley A Fast Algorithm for General Raster Rotation - Alan W. Paeth Useful 1-to-1 Pixel Transforms - Dale Schumacher Alpha Blending - Kelvin Thompson 4. Frame Buffer Techniques Frame Buffers and Color Maps - Andrew Glassner Reading a Write-Only Write Mask - Alan W. Paeth A Digital "Dissolve" Effect (*) - Mike Morton Mapping RGB Triples onto Four Bits (*) - Alan W. Paeth What Are the Coordinates of a Pixel? - Paul S. Heckbert Proper Treatment of Pixels as Integers (*) - Alan W. Paeth Normal Coding - Andrew Glassner Recording Animation in Binary Order for Progressive Temporal Refinement (*) - Paul S. Heckbert 1-to-1 Pixel Transforms Optimized Through Color Map Manipulations - Dale Schumacher A Seed Fill Algorithm (*) - Paul S. Heckbert Filling a Region in a Frame Buffer - Ken Fishkin Precalculating Addresses for Fast Fills, Circles, and Lines - Bill Wallace A SImple Method for Color Quantization: Octree Quantization - Michael Gervautz, Werner Purgathofer 5. 3D Geometry Useful 3D Geometry - Andrew Glassner An Efficient Bounding Sphere (*) - Jack Ritter Intersection of Two Lines in Three-Space - Ronald Goldman Intersection of Three Planes - Ronald Goldman Mapping Summary Digital Cartography for Computer Graphics - Alan W. Paeth Albers Equal-Area Conic Map Projection (*) - Paul D. Bame Boxes and Spheres Summary Spheres-to-Voxels Conversion - Claudio Montani, Roberto Scopigno A Simple Method for Box-Sphere Intersection Testing (*) - James Arvo 6. 3D Rendering 3D Grid Hashing Function (*) - Brian Wyvill Backface Culling - Jeff Hultquist Fast Dot Products for Shading - Mark Lee Scanline Depth Gradient of a Z-Buffered Triangle - Kelvin Thompson Simulating Fog and Haze - Andrew Glassner Interpretation of Texture Map Indices - Andrew Glassner Multidimensional Sum Tables - Andrew Glassner 7. Ray Tracing A Simple Ray Rejection Test - Jack Ritter Ray-Object Intersection Summary Intersection of a Ray with a Sphere - Jeff Hultquist An Efficient Ray-Polygon Intersection (*) - Didier Badouel Fast Ray-Polygon Intersection - Andrew Woo Fast Ray-Box Intersection (*) - Andrew Woo Shadow Attenuation for Ray Tracing Transparent Objects - Andrew Pearce 8. Numerical and Programming Techniques Root Finding Summary Cubic and Quartic Roots (*) - Jochen Schwarze A Bezier Curve-Based Root Finder - Philip J. Schneider Using Strum Sequences to Bracket Real Roots of Polynomial Equations (*) - D.G. Hook, P.R. McAree Distance Measures Summary A High-Speed, Low Precision Square Root (*) - Paul Lalonde, Robert Dawson A Fast Approximation to the Hypotenuse (*) - Alan W. Paeth A Fast Approximation to 3D Euclidean Distance - Jack Ritter Full-Precision Constants - Kelvin Thompson COnverting between Bits and Digits - Kelvin Thompson Storage-Free Swapping - Brian Wyvill Generating Random Integers - Andrew Glassner Fast 2D-3D Rotation - Jack Ritter Bit Patterns for Encoding Angles - Ken Shoemake Bit Interleaving for Quad- or Octrees (*) - Clifford A. Shaffer A Fast HSL-to-RGB Transform (*) - Ken Fishkin 9. Matrix Techniques Matrix Identities - Kelvin Thompson Rotation Matrix Methods Summary Transforming Axes - Kelvin Thompson Fast Matrix Multiplication - Kelvin Thompson A Virtual Trackball - Jeff Hultquist Matrix Orthogonalization (*) - Eric Raible Rotation Tools - Michael E. Pique Matrix Inversion (*) - Richard Carling Matrices and Transformations - Ronald Goldman Efficient Post-Concatenation of Transformation Matrices (*) - Joseph M. Cychosz 10. Modeling and Transformations Transformation Identities - Ned Greene Fixed-Point Trigonometry with CORDIC Iterations (*) - Ken Turkowski Using Quaternions for Coding 3D Transformations (*) - Patrick-Gilles Maillot 3D Viewing and Rotation Using Orthonormal Bases (*) - Steve Cunningham The Use of Coordinate Frames in Computer Graphics - Ken Turkowski Forms, Vectors, and Transforms (*) - Bob Wallis Properties of Surface-Normal Transformations - Ken Turkowski Transforming Axis-Aligned Bounding Boxes (*) - James Arvo Constructing Shapes Summary Defining Surfaces from Sampled Data - Mark Hall Defining Surfaces from Contour Data - Mark Hall Computing Surface Normals for 3D Models - Andrew Glassner Calculation of Reference Frames along a Space Curve - Jules Bloomenthal 11. Curves and Surfaces Planar Cubic Curves - Andrew Glassner Explicit Cubic Spline Interpolation Formulas - Richard Rasala Fast Spline Drawing - Julian Gomez Some Properties of Bezier Curves - Ronald Goldman Tutorial on Forward Differencing - Bob Wallis Integration of Bernstein Basis Functions - Ronald Goldman Solving the Nearest-Point-on-Curve Problem (*) - Philip J. Schneider An Algorithm for Automatically Fitting Digitized Curves (*) - Philip J. Schneider Appendix I: C Utilities Graphics Gems C Header Files - Andrew Glassner 2D and 3D Vector C Library - Andrew Glassner Memory Allocation in C - Jeff Hultquist Two Useful C Macros - Eric Raible How to Build Circular Structures in C - Kelvin Thompson How to Use C Register Variables to Point to 2D Arrays - Kelvin Thompson Appendix 2: C Implementations The C Code follows the same order as the Gems References Index