Graphics Gems
Published on 5. January 1994
Book
Hardback
864 pages
978-0-12-286166-6 (ISBN)
Description
"The GRAPHICS GEMS Series" was started in 1990 by Andrew Glassner. The vision and purpose of the Series was - and still is - to provide tips, techniques, and algorithms for graphics programmers. All of the gems are written by programmers who work in the field and are motivated by a common desire to share interesting ideas and tools with their colleagues. Each volume provides a new set of innovative solutions to a variety of programming problems.
More details
Series
Language
English
Place of publication
San Francisco
United States
Publishing group
Elsevier Science & Technology
Target group
Professional and scholarly
Weight
1560 gr
ISBN-13
978-0-12-286166-6 (9780122861666)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions
Person
Andrew Glassner's contributions to computer graphics span 20 years. His work at Microsoft Research, Xerox PARC, the IBM Watson Research Labs, Bell Communications Research, and the Delft University of Technology has produced numerous technical articles on rendering theory and practice, animation, modeling, and new media. He currently creates new computer graphics tools at Microsoft Research. Among his recent work is Chicken Crossing, a 3D animated short film that has been shown internationally at film festivals and on television, and Dead Air, an interactive game for play over the Internet. Dr. Glassner is the author of the two volume bible, Principles of Digital Image Synthesis and 3D Computer Graphics: A Handbook for Artists and Designers. He has also edited An Introduction to Ray Tracing, and created the Graphics Gems series for programmers.
Content
Preface
Introduction
Mathematical Notation
Pseudo-Code
Contributors
1 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 Grid
3 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
4 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
5 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 Tables
7 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
8 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)
9 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)
10 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
11 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)
C 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
C Appendix 2: C Implementations
The C Code Follows the Same Order as the Gems
References
Index
Introduction
Mathematical Notation
Pseudo-Code
Contributors
1 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 Grid
3 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
4 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
5 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 Tables
7 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
8 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)
9 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)
10 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
11 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)
C 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
C Appendix 2: C Implementations
The C Code Follows the Same Order as the Gems
References
Index