2D Geometry


Useful 2d Geometry
 3

 Andrew S. Glassner

Useful trigonometry
 13

 Andrew S. Glassner

Trigonometric functions at select points
 18

 Alan W. Paeth

Triangles
 20

 Ronald Goldman

Generating random points in triangles
 24

 Greg Turk

Fast lineedge intersections on a uniform grid
 29

 Andrew Shapira

Area of intersection: circle and a halfplane
 38

 Kelvin Thompson

Area of intersection: circle and a thick line
 40

 Kelvin Thompson

Area of intersection: two circles
 43

 Kelvin Thompson

Vertical distance from a point to a line
 47

 Kelvin Thompson

A fast 2d pointonline test
 49

 Alan W. Paeth

Fast circlerectangle intersection checking
 51

 Clifford A. Shaffer

2D Rendering


Circles of integral radius on integer lattices
 57

 Alan W. Paeth

Nice numbers for graph labels
 61

 Paul S. Heckbert

Efficient generation of sampling jitter using lookup tables
 64

 Joseph M. Cychosz

Fast antialiasing polygon scan conversion
 76

 Jack C. Morrison

Generic convec polygon scan conversion and clipping
 84

 Paul S. Heckbert

Concave polygon scan conversion
 87

 Paul S. Heckbert

Fast scan conversion of arbitrary polygons
 92

 Bob Wallis

Digital line drawing
 99

 Paul S. Heckbert

Symmetric double step line algorithm
 101

 Brian Wyvill

Rendering antialiased lines
 105

 Kelvin Thompson

An algorithm for filling in 2d wide line bevek joints
 107

 Jack Ritter

Rendering fat lines on a raster grid
 114

 Bob Wallis

Twodimensional clipping: a vectorbased approach
 121

 Hans J.W. Spoelder & Fons H. Ullings

Periodic tilings of the plane on a raster grid
 129

 Greg Lee, Mike Penk & Bob Wallis

Image Processing


Convenient antialiasing filters that minimize "bumpy" sampling
 144

 Mark J. Pavicic

Filters for common resampling tasks
 147

 Ken Turkowski

Smoothing enlarged monochrome images
 166

 John Olsen

Median Finding on a 3x3 grid
 171

 Alan W. Paeth

Ordered dithering
 176

 Stephen Hawley

A fast algorithm for general raster rotation
 179

 Alan W. Paeth

Useful 1to1 pixel transforms
 196

 Dale Schumacher

Alpha blending
 210

 Kelvin Thompson

Frame Buffer Techniques


Frame Buffers And Color Maps
 215

 Andrew S. Glassner

Reading a writeonly write mask
 219

 Alan W. Paeth

A digital "dissolve" effect
 221

 Mike Morton

Mapping RGB triples on four bits
 233

 Alan W. Paeth

What are the coordinates of a pixel ?
 246

 Paul S. Heckbert

Proper treatment of pixels as integers
 249

 Alan W. Paeth

Normal coding
 257

 Andrew S. Glassner

Recording animation in binary order for progressive temporal refinment
 265

 Paul S. Heckbert

1to1 pixel transforms optimized through colormap manipulation
 270

 Dale Schumacher

A seed fill algorithm
 275

 Paul S. Heckbert

Filling a region in a frame buffer
 278

 Ken Fishkin

Precalculating addresses for fast fills, circles, and lines
 285

 Bill Wallace

A simple method for color quantization: octree quantization
 287

 Michael Gervautz, Werner Purgathofer

3D Geometry


Useful 3d geometry
 297

 Andrew S. Glassner

An efficient bounding sphere
 301

 Jack Ritter

Intersection of two lines in threespace
 304

 Ronald Goldman

Intersection of three planes
 305

 Ronald Goldman

Digital cartography for computer graphics
 307

 Alan W. Paeth

Albers equalarea conic map projection
 321

 Paul D. Bame

Spherestovoxels conversion
 327

 Claudio Montani and Roberto Scopigno

A simple method for boxsphere intersection testing
 335

 James Arvo

3D Rendering


3d grid hashing function
 343

 Brian Wyvill

Backface culling
 346

 Jeff Hultquist

Fast dot products for shading
 348

 Mark Lee

Scanline depth gradient of a zbuffered triangle
 361

 Kelvin Thompson

Simulating fog and haze
 364

 Andrew S. Glassner

Interpretation of texture map indices
 366

 Andrew S. Glassner

Multidimensional sum tables
 376

 Andrew S. Glassner

Ray Tracing


A simple ray rejection test
 385

 Jack Ritter

Intersection of a ray with a sphere
 388

 Jeff Hultquist

An efficient raypolygon intersection
 390

 Didier Badouel

Fast raypolygon intersection
 394

 Andrew Woo

Fast raybox intersection
 395

 Andrew Woo

Shadow attenuation for ray tracing transparent objects
 397

 Andrew Pearce

Numerical and programming techniques


Cubic and quartic roots
 404

 Jochen Schwarze

A Bézier curvebased rootfinder
 408

 Philip J. Schneider

Using Sturm sequences to bracket real roots of polynomial equations
 416

 D.G. Hook & P. R. McAree

A high speed, low precision square root
 424

 Paul Lalonde & Robert Dawson

A fast approximation to the hypotenuse
 427

 Alan W. Paeth

A fast approximation to 3d euclidian distance
 432

 Jack Ritter

Fullprecision constants
 434

 Kelvin Thompson

Converting between bits and digits
 435

 Kelvin Thompson

Storagefree swaping
 436

 Brian Wyvill

Generating random integers
 438

 Andrew S. Glassner

Fast 2d3d rotation
 440

 Jack Ritter

Bit patterns for encoding angles
 442

 Ken Shoemake

Bit interleaving for quad or octrees
 443

 Clifford A. Shaffer

A fast HSLtoRGB transform
 448

 Ken Fishkin

Matrix techniques


Matrix identities
 453

 Kelvin Thompson

Transforming axes
 456

 Kelvin Thompson

Fast Matrix Multiplication
 460

 Kelvin Thompson

A virtual trackball
 462

 Jeff Hultquist

Matrix orthogonalisation
 464

 Eric Raible

Rotation tools
 465

 Michael E. Pique

Matrix inversion
 470

 Richard Carling

Matrices and transformations
 472

 Ronald Goldman

Efficient postconcatenation of transformation matrices
 476

 Joseph M. Cychosz

Modeling and Transformations


Transformation identities
 485

 Ned Greene

Fixedpoint trigonometry with cordic iterations
 494

 Ken Turkowski

Using quaternions for coding 3d transformations
 498

 PatrickGilles Maillot

3d viewing and rotation using orthonormal bases
 516

 Steve Cunningham

The use of coordinate frames in computer graphics
 522

 Ken Turkowski

Forms, vectors and transforms
 533

 Bob Wallis

Properties of surfacenormal transformations
 539

 Ken Turkowski

Transforming axisaligned bounding boxes
 548

 James Arvo

Defining surfaces from sampled data
 552

 Mark Hall

Defining surfaces from contour data
 558

 Mark Hall

Computing surface normals for 3d models
 562

 Andrew S. Glassner

Calculations of reference frames along a space curve
 567

 Jules Bloomenthal

Curves and surfaces


Planar cubic curves
 575

 Andrew S. Glassner

Explicit cubic spline interpolation formulas
 579

 Richard Rasala

Fast spline drawing
 585

 Julian Gomez

Some properties of Bézier curves
 587

 Ronald Goldman

Tutorial on forward differencing
 594

 Bob Wallis

Integration of Bernstein basis function
 604

 Ronald Goldman

Solving the nearestpointoncurve problem
 607

 Philip J. Schneider

An algorithm for automatically fitting digitized curves
 612

 Philip J. Schneider
