Graphics Gems II

Edited by James Arvo.

2D Geometry And Algorithms

The area of a simple polygon 3
     Jon Rokne
Intersection of line segments 7
Mukesh Prasad
Distance from a point to a line 10
Jack C. Morrison
An easy bounding circle 14
Jon Rokne
The smallest circle containing the intersection 17
Jon Rokne
Appolonius's 10th problem 19
Jon Rokne
A Peano curve generation algorithm 25
Ken Musgrave
Space-filling curves and a measure of coherence 26
Douglas Voorhies
Scanline coherent shape algebra 31
Jonathan E. Steinhart

Image Processing

Image smoothing and sharpening by discrete convolution 50
Dale A. Schumacher
A comparison of digital halftoning techniques 57
Dale A. Schumacher
Color dithering 72
Spencer W. Thomas & Rod G. Bogart
Fast anamorphic image scaling 78
Dale A. Schumacher
Real pixels 80
Greg Ward
A fast 90-degree bitmap rotator 84
Sue-Ken Yap
Rotation of run-length encoded image data 86
Jeff Holt
Adaptative run-length encoding 89
Andrew S. Glassner
Image file compression made easy 93
Alan W. Paeth
An optimal filter for image reconstruction 101
Nelson Max
Noise thresholding in edge images 105
John Schlag
Computing the area, circumference, and the genus of a binary digital image 107
Hanspeter Bieri & Andreas Kohler

Frame Buffer Techniques

Efficient inverse colormap computation 115
Spencer W. Thomas
Efficient statistical computations for optimal color quantization 126
Xiaolin Wu
A random color map animation algorithm 134
Ken Musgrave
A fast approach to PHIGS PLUS pseudo color mapping 138
James Hall & Terence Lindgren
Mapping RGB triples onto 16 distinct values 143
Alan W. Paeth
Television color encoding and "hot" broadcast colors 147
David Martindale & Alan W. Paeth
An inexpensive method of setting the monitor white point 159
Gary W. Meyer
Some tips for making color hardcopy 163
Ken Musgrave

3D Geometry and Algorithms

Area of planar polygons and volume of polyhedra 170
Ronald N. Goldman
Getting around on a sphere 172
Clifford A. Shaffer
Exact dihedral metrics for common polyhedra 174
Alan W. Paeth
A simple viewing algorithm 179
Andrew S. Glassner
View correlation 181
Rod G. Bogart
Maintaining winged-edge models 191
Andrew S. Glassner
Quadtree / octree-to-boundary conversion 202
Claudio Montani & Roberto Scopigno
Three-dimensional homogeneous clipping of triangle strips 219
Patrick-Gilles Maillot
Interphong shading 232
Nadia Magnenat Thalmann, Daniel Thalmann & Hong Tong Minh

Ray Tracing

Fast ray-convex polyhedron intersection 247
Eric Haines
Intersecting a ray with an elliptical torus 251
Joseph M. Cychosz
Ray-triangle intersection using binary recursive subdivision 257
Douglas Voorhies & David Kirk
Improved ray tagging for voxel-based ray tracing 264
David Kirk & James Arvo
Efficiency improvements for hierarchy traversal in ray tracing 267
Eric Haines
A recursive shadow voxel cache for ray tracing 273
Andrew Pearce
Avoiding incorrect shadow intersections for ray tracing 275
Andrew Pearce
A body color model: absorption of light through translucent media 277
Mark E. Lee & Samuel P. Uselton
More shadow attenuation for ray tracing transparent or translucent objects 283
Mark E. Lee & Samuel P. Uselton


Implementing progressive radiosity with user-provided polygon display routines 295
Shenchang Eric Chen
A cubic tetrahedral adaptation of the hemi-cube algorithm 299
Jeffrey C. Beran-Koehn & Mark J. Pavicic
Fast vertex radiosity update 303
Filippo Tampieri
Radiosity via ray tracing 306
Peter Shirley
Detection of shadow boundaries for adaptive meshing radiosity 311
François Sillion

Matrix Techniques

Decomposing a matrix into simple transformations 320
Spencer W. Thomas
Recovering the data from the transformation matrix 324
Ronald N. Goldman
Transformations as exponentials 332
Ronald N. Goldman
More matrices and transformations: shear and pseudo-perspective 338
Ronald N. Goldman
Fast matrix inversion 342
Kevin Wu
Quaternions and 4 × 4 matrices 351
Ken Shoemake
Random rotation matrices 355
James Arvo
Classifying small sparse matrices 357
James Arvo

Numerical and Programming Techniques

Bit picking 366
Ken Shoemake
Faster Fourier transform 368
Ken Shoemake
Of integers, fields and bit counting 371
Alan W. Paeth & David Schilling
Using geometric constructions to interpolate orientation with quaternions 377
John Schlag
A half-angle identity for digital computation: the joys of the halved tangent 381
Alan W. Paeth
An integer square root algorithm 387
Christopher J. Musial
Fast approximation to the arctangent 389
Ron Capelli
Fast sign of cross product calculation 392
Jack Ritter
Intercal sampling 394
Ken Shoemake
A recursive implementation of the Perlin noise function 396
Greg Ward

Curves and Surfaces

Least-squares approximations to Bézier curves and surfaces 406
Doug Moore and Joe Warren
Beyond Bézier curves 412
Ken Shoemake
A simple formulation for curve interpolation with variable control point approximation 417
John Schlag
Symmetric evaluation of polynomials 420
Terence Lindgren
Menelaus's theorem 424
Hans-Peter Seidel
Geometrically continuous cubic Bézier curves 428
Hans-Peter Seidel
A good straight-line approximation of a circular arc 435
Christopher J. Musial
Great circle plotting 440
Alan W. Paeth
Fast anti-aliased circle generation 446
Xiaolin Wu

Related topics: Graphics Gems

Christophe Tronche,