Graphics Gems (Vol.2)下载

Foreword By Andrew Glassner xvii Preface xix Mathematical Notation xxi Pseudo-Code xxiii Contributors xxix I I I I I 2 2 2 2 2D GEOMETRY AND ALGORITHMS D GEOMETRY AND ALGORITHMS D GEOMETRY AND ALGORITHMS D GEOMETRY AND ALGORITHMS D GEOMETRY AND ALGORITHMS Introduction 3 1. The Area of a Simple Polygon 5 Jon Rokne 2. Intersection of Line Segments C 7 Mukesh Prasad 3. Distance from a Point to a Line 10 Jack C. Morrison 4. An Easy Bounding Circle 14 Jon Rokneviii 5. The Smallest Circle Containing the Intersection C of Two Circles 17 Jon Rokne 6. Appolonius’s 10th Problem 19 Jon Rokne 7. A Peano Curve Generation Algorithm C 25 Ken Musgrave 8. Space-Filling Curves and a Measure of Coherence C 26 Douglas Voorhies 9. Scanline Coherent Shape Algebra 31 Jonathan E. Steinhart II II II II II I I I I IMAGE PROCESSING MAGE PROCESSING MAGE PROCESSING MAGE PROCESSING MAGE PROCESSING Introduction 49 1. Image Smoothing and Sharpening by Discrete Convolution 50 Dale A. Schumacher 2. A Comparison of Digital Halftoning Techniques C 75 Dale A. Schumacher 3. Color Dithering C 72 Spencer W. Thomas and Rod G. Bogart 4. Fast Anamorphic Image Scaling 78 Dale A. Schumacher 5. Real Pixels 80 Greg Ward 6. A Fast 90-Degree Bitmap Rotator C 84 Sue-Ken Yap CONTENTSix CONTENTS 7. Rotation of Run-Length Encoded Image Data C 86 Jeff Holt 8. Adaptive Run-Length Encoding 89 Andrew S. Glassner 9. Image File Compression Made Easy 93 Alan W. Paeth 10. An Optimal Filter for Image Reconstruction 101 Nelson Max 11. Noise Thresholding in Edge Images 105 John Schlag 12. Computing the Area, the Circumference, and the Genus of a Binary Digital Image C 107 Hanspeter Bieri and Andreas Kohler III III III III III F F F F FRAM RAM RAM RAM RAME E E E E BUFFER TECH BUFFER TECH BUFFER TECH BUFFER TECH BUFFER TECHN N N N NIQUES IQUES IQUES IQUES IQUES Introduction 115 1. Efficient Inverse Color Map Computation C 116 Spencer W. Thomas 2. Efficient Statistical Computations for Optimal Color Quantization 126 Xiaolin Wu 3. A Random Color Map Animation Algorithm C 134 Ken Musgrave 4. A Fast Approach to PHIGS PLUS Pseudo Color 138 Mapping James Hall and Terence Lindgren 5. Mapping RGB Triples onto 16 Distinct Values 143x 6. Television Color Encoding and “Hot” Broadcast Colors C 147 David Martindale and Alan W. Paeth 7. An Inexpensive Method of Setting the Monitor White Point 159 Gary W. Meyer 8. Some Tips for Making Color Hardcopy 163 Ken Musgrave IV IV IV IV IV 3 3 3 3 3D GEOMETRY AND ALGORITHMS D GEOMETRY AND ALGORITHMS D GEOMETRY AND ALGORITHMS D GEOMETRY AND ALGORITHMS D GEOMETRY AND ALGORITHMS Introduction 169 1. Area of Planar Polygons and Volume of Polyhedra 170 Ronald N. Goldman 2. Getting Around on a Sphere 172 Clifford A. Shaffer 3. Exact Dihedral Metrics for Common Polyhedra 174 Alan W. Paeth 4. A Simple Viewing Geometry 179 Andrew S. Glassner 5. View Correlation C 181 Rod G. Bogart 6. Maintaining Winged-Edge Models 191 Andrew S. Glassner 7. Quadtree/Octree-to-Boundary Conversion 202 Claudio Montani and Roberto Scopigno 8. Three-Dimensional Homogeneous Clipping of Triangle Strips C 219 Patrick-Gilles Maillot CONTENTSxi 9. InterPhong Shading C 232 Nadia Magnenat Thalmann, Daniel Thalmann, and Hong Tong Minh V V V V V R R R R RAY TRACING AY TRACING AY TRACING AY TRACING AY TRACING Introduction 245 1. Fast Ray–Convex Polyhedron Intersection C 247 Eric Haines 2. Intersecting a Ray with an Elliptical Torus C 251 Joseph M. Cychosz 3. Ray–Triangle Intersection Using Binary Recursive Subdivision 257 Douglas Voorhies and David Kirk 4. Improved Ray Tagging for Voxel-Based Ray Tracing 264 David Kirk and James Arvo 5. Efficiency Improvements for Hierarchy Traversal in Ray Tracing 267 Eric Haines 6. A Recursive Shadow Voxel Cache for Ray Tracing C 273 Andrew Pearce 7. Avoiding Incorrect Shadow Intersections for Ray Tracing 275 Andrew Pearce 8. A Body Color Model: Absorption of Light through Translucent Media 277 Mark E. Lee and Samuel P. Uselton 9. More Shadow Attenuation for Ray Tracing Transparent or Translucent Objects 283 Mark E. Lee and Samuel P. Uselton CONTENTSxii CONTENTS Vl Vl Vl Vl Vl R R R R RADIOSITY ADIOSITY ADIOSITY ADIOSITY ADIOSITY Introduction 293 1. Implementing Progressive Radiosity with User- Provided Polygon Display Routines C 295 Shenchang Eric Chen 2. A Cubic Tetrahedral Adaptation of the Hemi-Cube Algorithm 299 Jeffrey C. Beran-Koehn and Mark J. Pavicic 3. Fast Vertex Radiosity Update C 303 Filippo Tampieri 4. Radiosity via Ray Tracing 306 Peter Shirley 5. Detection of Shadow Boundaries for Adaptive Meshing in Radiosity 311 François Sillion Vll Vll Vll Vll Vll M M M M MATRIX TECHNIQUES ATRIX TECHNIQUES ATRIX TECHNIQUES ATRIX TECHNIQUES ATRIX TECHNIQUES Introduction 319 1. Decomposing a Matrix into Simple Transformations C 320 Spencer W. Thomas 2. Recovering the Data from the Transformation Matrix 324 Ronald N. Goldman 3. Transformations as Exponentials 332 Ronald N. Goldman 4. More Matrices and Transformations: Shear and Pseudo-Perspective 338 Ronald N. Goldmanxiii 5. Fast Matrix Inversion C 342 Kevin Wu 6. Quaternions and 4 × 4 Matrices 351 Ken Shoemake 7. Random Rotation Matrices C 355 James Arvo 8. Classifying Small Sparse Matrices C 357 James Arvo Vlll Vlll Vlll Vlll Vlll N N N N NUMERICAL AND PROGRAMMING UMERICAL AND PROGRAMMING UMERICAL AND PROGRAMMING UMERICAL AND PROGRAMMING UMERICAL AND PROGRAMMING T T T T TECHNIQUES ECHNIQUES ECHNIQUES ECHNIQUES ECHNIQUES Introduction 365 1. Bit Picking 366 Ken Shoemake 2. Faster Fourier Transform 368 Ken Shoemake 3. Of Integers, Fields, and Bit Counting C 371 Alan W. Paeth and David Schilling 4. Using Geometric Constructions to Interpolate Orientation with Quaternions 377 John Schlag 5. A Half-Angle Identity for Digital Computation: 381 The Joys of the Halved Tangent Alan W. Paeth 6. An Integer Square Root Algorithm C 387 Christopher J. Musial 7. Fast Approximation to the Arctangent 389 Ron Capelli CONTENTSxiv CONTENTS 8. Fast Sign of Cross Product Calculation C 392 Jack Ritter 9. Interval Sampling 394 Ken Shoemake 10.A Recursive Implementation of the Perlin Noise Function C 396 Greg Ward I I I I IX X X X X C C C C CURVES AN URVES AN URVES AN URVES AN URVES AND D D D D SURFACES SURFACES SURFACES SURFACES SURFACES Introduction 405 1. Least-Squares Approximations to Bézier Curves and Surfaces 406 Doug Moore and Joe Warren 2. Beyond Bézier Curves 412 Ken Shoemake 3. A Simple Formulation for Curve Interpolation with Variable Control Point Approximation 417 John Schlag 4. Symmetric Evaluation of Polynomials 420 Terence Lindgren 5. Menelaus’s Theorem 424 Hans-Peter Seidel 6. Geometrically Continuous Cubic Bézier Curves 428 Hans-Peter Siedel 7. A Good Straight-Line Approximation of a Circular Arc C 435 Christopher J. Musial 8. Great Circle Plotting 440 Alan W. Paeth 9. Fast Anti-Aliased Circle Generation 446 Xiaolin Wu