Arvo Graphics Gems II

1. Auflage 2013
ISBN: 978-0-08-050754-5
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 672 Seiten, Web PDF

Reihe: Graphics Gems - IBM

Graphics Gems II is a collection of articles shared by a diverse group of people that reflect ideas and approaches in graphics programming which can benefit other computer graphics programmers. This volume presents techniques for doing well-known graphics operations faster or easier. The book contains chapters devoted to topics on two-dimensional and three-dimensional geometry and algorithms, image processing, frame buffer techniques, and ray tracing techniques. The radiosity approach, matrix techniques, and numerical and programming techniques are likewise discussed. Graphics artists and computer programmers will find the book invaluable.

Autoren/Hrsg.

Arvo, James

Inhaltsverzeichnis

1;Front Cover;1
2;Graphics Gems II;4
3;Copyright Page;5
4;Table of Contents;8
5;Foreword;18
6;Preface;20
7;Mathematical Notation;22
8;Pseudo-Code;24
9;Contributors;30
10;CHAPTER I. 2D GEOMETRY AND ALGORITHMS;38
10.1;Introduction;38
10.2;1. The Area of a Simple Polygon;40
10.3;2. Intersection of Line Segments ;42
10.4;3. Distance from a Point to a Line;45
10.5;4. An Easy Bounding Circle;49
10.6;5. The Smallest Circle Containing the Intersection of Two Circles;52
10.7;6. Appolonius's 10th Problem;54
10.8;7. A Peano Curve Generation Algorithm ;60
10.9;8. Space-Filling Curves and a Measure of Coherence ;61
10.10;9. Scanline Coherent Shape Algebra ;66
11;CHAPTER II. IMAGE PROCESSING;84
11.1;Introduction;84
11.2;1. Image Smoothing and Sharpening by Discrete Convolution;85
11.3;2. A Comparison of Digital Halftoning Techniques ;92
11.4;3. Color Dithering ;107
11.5;4. Fast Anamorphic Image Scaling;113
11.6;5. Real Pixels;115
11.7;6. A Fast 90-Degree Bitmap Rotator ;119
11.8;7. Rotation of Run-Length Encoded Image Data ;121
11.9;8. Adaptive Run-Length Encoding;124
11.10;9. Image File Compression Made Easy;128
11.11;10. An Optimal Filter for Image Reconstruction;136
11.12;11. Noise Thresholding in Edge Images;140
11.13;12. Computing the Area, the Circumference, and the Genus of a Binary Digital Image ;142
12;CHAPTER III. FRAME BUFFER TECHNIQUES;150
12.1;Introduction;150
12.2;1. Efficient Inverse Color Map Computation ;151
12.3;2. Efficient Statistical Computations for Optimal Color Quantization;161
12.4;3. A Random Color Map Animation Algorithm;169
12.5;4. A Fast Approach to PHIGS PLUS Pseudo Color Mapping;173
12.6;5. Mapping RGB Triples onto 16 Distinct Values;178
12.7;6. Television Color Encoding and "Hot" Broadcast Colors;182
12.8;7. An Inexpensive Method of Setting the Monitor White Point;194
12.9;8. Some Tips for Making Color Hardcopy;198
13;CHAPTER IV. 3D GEOMETRY AND ALGORITHMS;204
13.1;Introduction;204
13.2;1. Area of Planar Polygons and Volume of Polyhedra;205
13.3;2. Getting Around on a Sphere;207
13.4;3. Exact Dihedral Metrics for Common Polyhedra;209
13.5;4. A Simple Viewing Geometry;214
13.6;5. View Correlation ;216
13.7;6. Maintaining Winged-Edge Models;226
13.8;7. Quadtree/Octree-to-Boundary Conversion;237
13.9;8. Three-Dimensional Homogeneous Clipping of Triangle Strips;254
13.10;9. InterPhong Shading ;267
14;CHAPTER V. RAY TRACING;280
14.1;Introduction;280
14.2;1. Fast Ray-Convex Polyhedron Intersection ;282
14.3;2. Intersecting a Ray with an Elliptical Torus ;286
14.4;3. Ray-Triangle Intersection Using Binary Recursive Subdivision;292
14.5;4. Improved Ray Tagging for Voxel-Based Ray Tracing;299
14.6;5. Efficiency Improvements for Hierarchy Traversal in Ray Tracing;302
14.7;6. A Recursive Shadow Voxel Cache for Ray Tracing ;308
14.8;7. Avoiding Incorrect Shadow Intersections for Ray Tracing;310
14.9;8. A Body Color Model: Absorption of Light through Translucent Media;312
14.10;9. More Shadow Attenuation for Ray Tracing Transparent or Translucent Objects;318
15;CHAPTER VI. RADIOSITY;328
15.1;Introduction;328
15.2;1. Implementing Progressive Radiosity with User- Provided Polygon Display Routines ;330
15.3;2. A Cubic Tetrahedral Adaptation of the Hemi-Cube Algorithm;334
15.4;3. Fast Vertex Radiosity Update ;338
15.5;4. Radiosity via Ray Tracing;341
15.6;5. Detection of Shadow Boundaries for Adaptive Meshing in Radiosity;346
16;CHAPTER VII. MATRIX TECHNIQUES;358
16.1;Introduction;358
16.2;1. Decomposing a Matrix into Simple Transformations ;359
16.3;2. Recovering the Data from the Transformation Matrix;363
16.4;3. Transformations as Exponentials;371
16.5;4. More Matrices and Transformations: Shear and Pseudo-Perspective;377
16.6;5. Fast Matrix Inversion ;381
16.7;6. Quaternions and 4 X 4 Matrices;390
16.8;7. Random Rotation Matrices ;394
16.9;8. Classifying Small Sparse Matrices ;396
17;CHAPTER VIII. NUMERICAL AND PROGRAMMING TECHNIQUES;404
17.1;Introduction;404
17.2;1. Bit Picking;405
17.3;2. Faster Fourier Transform;407
17.4;3. Of Integers, Fields, and Bit Counting ;410
17.5;4. Using Geometric Constructions to Interpolate Orientation with Quaternions;416
17.6;5. A Half-Angle Identity for Digital Computation: The Joys of the Halved Tangent;420
17.7;6. An Integer Square Root Algorithm ;426
17.8;7. Fast Approximation to the Arctangent;428
17.9;8. Fast Sign of Cross Product Calculation ;431
17.10;9. Interval Sampling;433
17.11;10. A Recursive Implementation of the Perlin Noise Function ;435
18;CHAPTER IX. CURVES AND SURFACES;444
18.1;Introduction;444
18.2;1. Least-Squares Approximations to Bézier Curves and Surfaces;445
18.3;2. Beyond Bézier Curves;451
18.4;3. A Simple Formulation for Curve Interpolation with Variable Control Point Approximation;456
18.5;4. Symmetric Evaluation of Polynomials;459
18.6;5. Menelaus's Theorem;463
18.7;6. Geometrically Continuous Cubic Bézier Curves;467
18.8;7. A Good Straight-Line Approximation of a Circular Arc;474
18.9;8. Great Circle Plotting;479
18.10;9. Fast Anti-Aliased Circle Generation;485
19;APPENDIX I: C UTILITIES;492
19.1;Graphics Gems C Header File;494
19.2;2D and 3D Vector C Library—Corrected and Indexed;497
19.3;Useful C Macros for Vector Operations;506
20;APPENDIX II: C IMPLEMENTATIONS;510
20.1;1.2 Intersection of Line Segments;512
20.2;1.7 A Peano Curve Generation Algorithm;516
20.3;1.8 Space-Filling Curves and a Measure of Coherence;524
20.4;1.9 Scanline Coherent Shape Algebra;526
20.5;11.2 A Comparison of Digital Halftoning Techniques;541
20.6;11.3 Color Dithering;548
20.7;II.6 A Fast 90-Degree Bitmap Rotator;553
20.8;II. 7 Rotation of Run-Length Encoded Image Data;555
20.9;11.12 Computing the Area, the Circumference, and the Genus of a Binary Digital Image;564
20.10;III. 1 Efficient Inverse Color Map Computation;567
20.11;III.3 A Random Color Map Animation Algorithm;575
20.12;111.6 Television Color Encoding and "Hot" Broadcast Colors;581
20.13;IV.5 View Correlation;589
20.14;IV.8 Three-Dimensional Homogeneous Clipping of Triangle Strips;602
20.15;IV.9 InterPhong Shading;610
20.16;V.1 Fast Ray-Convex Polyhedron Intersection;614
20.17;V.2 Intersecting a Ray with an Elliptical Torus;616
20.18;V.6 A Recursive Shadow Voxel Cache for Ray Tracing;620
20.19;VI.1 Implementing Progressive Radiosity with User-Provided Polygon Display Routines;622
20.20;VI.3 Fast Vertex Radiosity Update;637
20.21;VII.1 Decomposing a Matrix into Simple Transformations;638
20.22;VII.5 Fast Matrix Inversion;642
20.23;VII.7 Random Rotation Matrices;645
20.24;VII.8 Classifying Small Sparse Matrices;647
20.25;VIII.3 Of Integers, Fields, and Bit Counting;649
20.26;VIII.6 An Integer Square Root Algorithm;651
20.27;VIII.8 Fast Sign of Cross Product Calculation;652
20.28;VIII.IO A Recursive Implementation of the Perlin Noise Function;654
20.29;IX.7 A Good Straight-Line Approximation of a Circular Arc;656
21;References;660
22;Index;674