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

Spacefilling 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 90degree bitmap rotator
 84

 SueKen Yap

Rotation of runlength encoded image data
 86

 Jeff Holt

Adaptative runlength 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 wingededge models
 191

 Andrew S. Glassner

Quadtree / octreetoboundary conversion
 202

 Claudio Montani & Roberto Scopigno

Threedimensional homogeneous clipping of triangle strips
 219

 PatrickGilles Maillot

Interphong shading
 232

 Nadia Magnenat Thalmann, Daniel Thalmann & Hong Tong Minh

Ray Tracing


Fast rayconvex polyhedron intersection
 247

 Eric Haines

Intersecting a ray with an elliptical torus
 251

 Joseph M. Cychosz

Raytriangle intersection using binary recursive subdivision
 257

 Douglas Voorhies & David Kirk

Improved ray tagging for voxelbased 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

Radiosity


Implementing progressive radiosity with userprovided polygon display routines
 295

 Shenchang Eric Chen

A cubic tetrahedral adaptation of the hemicube algorithm
 299

 Jeffrey C. BeranKoehn & 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 pseudoperspective
 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 halfangle 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


Leastsquares 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

 HansPeter Seidel

Geometrically continuous cubic Bézier curves
 428

 HansPeter Seidel

A good straightline approximation of a circular arc
 435

 Christopher J. Musial

Great circle plotting
 440

 Alan W. Paeth

Fast antialiased circle generation
 446

 Xiaolin Wu
