# Graphics Gems

## 1st Edition

**Editors:**Andrew Glassner

**eBook ISBN:**9780080507538

**Imprint:**Morgan Kaufmann

**Published Date:**22nd October 2013

**Page Count:**864

**View all volumes in this series:**Graphics Gems - IBM

## Table of Contents

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

References

Index

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

## Details

- No. of pages:
- 864

- Language:
- English

- Copyright:
- © Morgan Kaufmann 1990

- Published:
- 22nd October 2013

- Imprint:
- Morgan Kaufmann

- eBook ISBN:
- 9780080507538

## Ratings and Reviews

## About the Editors

### Andrew Glassner Editor

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

**
**