Graphics Gems II (Graphics Gems - IBM) (No. 2)

Cover......Page 1
Copyright......Page 4
About the Cover......Page 5
Contents......Page 7
Foreward......Page 17
Preface......Page 19
Mathmatical Notation......Page 21
Pseudo-Code......Page 23
Contributors......Page 28
I  2D Geometry and Algorithms......Page 32
Introduction......Page 33
1-Area of a Simple Polygon......Page 35
2-Intersection of Line Segments......Page 37
3-Distance from a Point to a Line......Page 40
4-An Easy Bounding Circle......Page 44
5-The Smallest Circle Containing the Intersection of Two Circles......Page 47
6-Appolonius\'s 10th Problem......Page 49
7-A Peano Curve Generation Algorithm......Page 55
8-Space-filling Curves and a Measure of Coherence......Page 57
9-Scanline Coherent Shape Algebra......Page 62
II Image Processing......Page 77
Image Processing Introduction......Page 78
1-Image Smoothing and Sharpening By Discrete Convolution......Page 79
2-A Comparison of Digital Halftoning Techniques......Page 86
3-Color Dithering......Page 101
4-Fast  Anamorphic Image Scaling......Page 107
5-Real Pixels......Page 109
6-A Fast 90-Degree Bitmap Rotator......Page 113
7-Rotation of Run-Length Encoded Image Data......Page 115
8-Adaptive Run-Length Encoding......Page 118
9-Image File Compression Made Easy......Page 122
10-An Optimal Filter For Image Reconstruction......Page 130
11-Noise Threshholding in Edge Images......Page 134
12-Computing the Area, the Circumference, and the Genus of a Binary Digital Image......Page 136
III Frame Buffer Techniques......Page 141
Introduction......Page 142
1-Efficient Inverse Color Map Computation......Page 143
2-Efficient Statistical Computations for Optimal Color Quantization......Page 153
3-A Random Color Map Animation Algorithm......Page 162
4-A  Fast Approach to PHIGS Plus Pseudo Color Mapping......Page 166
5-Mapping RGB Triples Onto 16 Distinct Values......Page 171
6-Television Color Encoding and \"Hot\" Broadcast Colors......Page 176
7-An Inexpensive Method of Setting the Monitor White Point......Page 188
8-Some Tips for Making Color Harcopy......Page 192
IV 3-D Geometry and Algorithms......Page 195
Introduction......Page 196
1-Area of Planar Polygons and Volume of Polyhedra......Page 197
2-Getting Around on a Sphere......Page 199
3-Exact Dihedral Metrics for Common Polyhedra......Page 201
4-A Simple Viewing Geometry......Page 206
5-View Correlation......Page 208
6-Maintaining Winged-Edge Models......Page 218
7-Quadtree/Octree-to-Boundary Conversion......Page 229
8-Three-Dimensional Homogeneous Clipping of Triangle Strips......Page 246
9-InterPhong Shading......Page 259
V Ray Tracing......Page 269
Introduction......Page 270
1-Fast Ray-Convex Polyhedron Intersection......Page 272
2-Intersecting A Ray with an Elliptical Torus......Page 276
3-Ray-Triangle Intersection Using Binary Recursive Subdivision......Page 282
4-Improved Ray Tagging for Voxel-Based Raytracing......Page 289
5-Efficiency  Improvements for Hierarchy Traversal in Ray Tracing......Page 292
6-A Recursive Shadow Voxel Cache for Ray Tracing......Page 298
7-Avoiding Incorrect Shadow Intersections for Ray Tracing......Page 300
8-A Body Color Model: Absorption of Light Through Translucent Media......Page 302
9-More Shadow Attenuation for Ray Tracing Transparent or Translucent Objects......Page 308
VI  Radiosity......Page 315
Introduction......Page 316
1-Implementing Progressive Radiosity with User-Provided Polygon Display Routines......Page 318
2-A Cubic Tetrahedral Adaptation of the Hemi-Cube Algorithm......Page 322
3-Fast Vertex Radiosity Update......Page 326
4-Radiosity Via Ray Tracing......Page 329
5-Detection of Shadow Boundaries for Adaptive Meshing in Radiosity......Page 334
VII Matrix Techniques......Page 341
Introduction......Page 342
1-Decomposing  A Matrix into Simple Transformations......Page 343
2-Recovering the Data from the Transformation Matrix......Page 347
3-Transformations as Exponentials......Page 355
4-More Matrices and Transformations: Shear and Pseudo-Perspective......Page 361
5-Fast Matrix Inversion......Page 365
6-Quaternions and 4x4 Matrices......Page 374
7-Random Rotation Matrices......Page 378
8-Classifying Small Sparse Matrices......Page 380
VIII Numerical and Programming Techniques......Page 385
Introduction......Page 386
1-Bit Picking......Page 387
2-Faster Fourier Transform......Page 389
3-Of Integers, Fields, and Bit Counting......Page 392
4-Using Geometric Constructions to Interpolate Orientation with Quaternions......Page 398
5-A Half-Angle Identity for Digital Computation: The Joys of the Halved Tangent......Page 402
6-An Integer Square Root Algorithm......Page 408
7-Fast Approximation to the Arctangent......Page 410
8-Fast Sign of Cross Product Calculation......Page 413
9-Interval Sampling......Page 415
10-A Recursive Implementation of the Perlin Noise Function......Page 417
IX Curves and Surfaces......Page 423
Introduction......Page 424
1-Least Squares, Approximations to Bézier Curves and Surfaces......Page 425
2-Beyond Bézier Curves......Page 431
3-A Simple Formulation for Curve Interpolation with Variable Control Point Approximation......Page 436
4-Symmetric Evaluation of Polynomials......Page 439
5-Menelaus\'s Theorem......Page 443
6-Geometrically Continuous Cubic Bézier Curves......Page 447
7-A Good Straight-Line Approximation of a Circular Arc......Page 454
8-Great Circle Plotting......Page 459
9-Fast Anti-Aliased Circle Generation......Page 465
References......Page 470
A-B......Page 483
C-D......Page 484
E-H......Page 485
I-L......Page 486
M-N......Page 487
O-Q......Page 488
R-S......Page 489
T......Page 490
U-Z......Page 491