COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
Graphics Gems - 1st Edition - ISBN: 9780122861666, 9780080507538

Graphics Gems

1st Edition

Editor: Andrew Glassner
Hardcover ISBN: 9780122861666
eBook ISBN: 9780080507538
Imprint: Morgan Kaufmann
Published Date: 29th June 1993
Page Count: 864
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.

Table of Contents



Mathematical Notation



1 2D Geometry

Useful 2D Geometry

Trigonometry Summary

Useful Trigonometry

Trigonometric Functions at Select Points


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 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 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 Bézier 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




"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.


No. of pages:
© Morgan Kaufmann 2013
29th June 1993
Morgan Kaufmann
Hardcover ISBN:
eBook ISBN:

Ratings and Reviews

About the Editor

Andrew Glassner

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.

Affiliations and Expertise

Xerox PARC, Palo Alto, California