Glassner Graphics Gems

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

E-Book, Englisch, 864 Seiten, Web PDF

Reihe: Graphics Gems - IBM

'The GRAPHICS GEMS Series' was started in 1990 by Andrew Glassner. The vision and purpose of the Series was - and still is - to provide tips, techniques, and algorithms for graphics programmers. All of the gems are written by programmers who work in the field and are motivated by a common desire to share interesting ideas and tools with their colleagues. Each volume provides a new set of innovative solutions to a variety of programming problems.

Autoren/Hrsg.

Glassner, Andrew S.

Inhaltsverzeichnis

1;Front Cover;1
2;Graphics Gems;4
3;Copyright Page;5
4;Table of Contents;8
5;Preface;16
6;Introduction;18
7;Mathematical Notation;20
8;Pseudo-Code;22
9;Contributors;27
10;CHAPTER 1. 2D GEOMETRY;32
10.1;Useful 2D Geometry;34
10.2;Trigonometry Summary;43
10.3;Useful Trigonometry;44
10.4;Trigonometric Functions at Select Points;49
10.5;Triangles;51
10.6;Generating Random Points in Triangles;55
10.7;Fast Line–Edge Intersections on a Uniform Grid;60
10.8;Anti-Aliasing Summary;68
10.9;Area of Intersection: Circle and a Half-Plane;69
10.10;Area of Intersection: Circle and a Thick Line;71
10.11;Area of Intersection: Two Circles;74
10.12;Vertical Distance from a Point to a Line;78
10.13;A Fast 2D Point-on-Line Test ;80
10.14;Fast Circle–Rectangle Intersection Checking ;82
11;CHAPTER 2. 2D RENDERING;86
11.1;Circles of Integral Radius on Integer Lattices;88
11.2;Nice Numbers for Graph Labels;92
11.3;Efficient Generation of Sampling Jitter Using Look-up Tables;95
11.4;Scan Conversion Summary;106
11.5;Fast Anti-Aliasing Polygon Scan Conversion ;107
11.6;Generic Convex Polygon Scan Conversion and Clipping ;115
11.7;Concave Polygon Scan Conversion ;118
11.8;Fast Scan Conversion of Arbitrary Polygons;123
11.9;Line-Drawing Summary;129
11.10;Digital Line Drawing;130
11.11;Symmetric Double Step Line Algorithm;132
11.12;Rendering Anti-Aliased Lines ;136
11.13;An Algorithm for Filling in 2D Wide Line Bevel Joints;138
11.14;Rendering Fat Lines on a Raster Grid;145
11.15;Two-Dimensional Clipping: A Vector-Based Approach;152
11.16;Periodic Tilings of the Plane on a Raster Grid;160
12;CHAPTER 3. IMAGE PROCESSING;172
12.1;Anti-Aliasing Filters Summary;174
12.2;Convenient Anti-Aliasing Filters That Minimize "Bumpy" Sampling;175
12.3;Filters for Common Resampling Tasks;178
12.4;Smoothing Enlarged Monochrome Images;197
12.5;Median Finding on a 3 X 3 Grid;202
12.6;Ordered Dithering ;207
12.7;A Fast Algorithm for General Raster Rotation;210
12.8;Useful 1-to-1 Pixel Transforms;227
12.9;Alpha Blending;241
13;CHAPTER 4. FRAME BUFFER TECHNIQUES;244
13.1;Frame Buffers and Color Maps;246
13.2;Reading a Write-Only Write Mask;250
13.3;A Digital "Dissolve" Effect ;252
13.4;Mapping RGB Triples onto Four Bits ;264
13.5;What Are the Coordinates of a Pixel?;277
13.6;Proper Treatment of Pixels as Integers ;280
13.7;Normal Coding;288
13.8;Recording Animation in Binary Order for Progressive Temporal Refinement ;296
13.9;1 -to-1 Pixel Transforms Optimized through Color-Map Manipulation;301
13.10;A Seed Fill Algorithm;306
13.11;Filling a Region in a Frame Buffer;309
13.12;Precalculating Addresses for Fast Fills, Circles, and Lines;316
13.13;A Simple Method for Color Quantization: Octree Quantization;318
14;CHAPTER 5. 3D GEOMETRY;326
14.1;Useful 3D Geometry;328
14.2;An Efficient Bounding Sphere ;332
14.3;Intersection of Two Lines in Three-Space;335
14.4;Intersection of Three Planes;336
14.5;Mapping Summary;337
14.6;Digital Cartography for Computer Graphics;338
14.7;Albers Equal-Area Conic Map Projection;352
14.8;Boxes and Spheres Summary;357
14.9;Spheres-to-Voxels Conversion;358
14.10;A Simple Method for Box-Sphere Intersection Testing ;366
15;CHAPTER 6. 3D RENDERING;372
15.1;3D Grid Hashing Function ;374
15.2;Backface Culling;377
15.3;Fast Dot Products for Shading;379
15.4;Scanline Depth Gradient of a Z-Bufifered Triangle;392
15.5;Simulating Fog and Haze;395
15.6;Interpretation of Texture Map Indices;397
15.7;Multidimensional Sum Tables;407
16;CHAPTER 7. RAY TRACING;414
16.1;A Simple Ray Rejection Test;416
16.2;Ray–Object Intersection Summary;418
16.3;Intersection of a Ray with a Sphere;419
16.4;An Efficient Ray–Polygon Intersection ;421
16.5;Fast Ray–Polygon Intersection;425
16.6;Fast Ray–Box Intersection;426
16.7;Shadow Attenuation for Ray Tracing Transparent Objects;428
17;CHAPTER 8. NUMERICAL AND PROGRAMMING TECHNIQUES;432
17.1;Root Finding Summary;434
17.2;Cubic and Quartic Roots;435
17.3;A Bézier Curve-Based Root-Finder ;439
17.4;Using Sturm Sequences to Bracket Real Roots of Polynomial Equations ;447
17.5;Distance Measures Summary;454
17.6;A High-Speed, Low Precision Square Root;455
17.7;A Fast Approximation to the Hypotenuse;458
17.8;A Fast Approximation to 3D Euclidean Distance;463
17.9;Full-Precision Constants;465
17.10;Converting between Bits and Digits;466
17.11;Storage-free Swapping;467
17.12;Generating Random Integers;469
17.13;Fast 2D–3D Rotation;471
17.14;Bit Patterns for Encoding Angles;473
17.15;Bit Interleaving for Quad- or Octrees ;474
17.16;A Fast HSL-to-RGB Transform;479
18;CHAPTER 9. MATRIX TECHNIQUES;482
18.1;Matrix Identities;484
18.2;Rotation Matrix Methods Summary;486
18.3;Transforming Axes;487
18.4;Fast Matrix Multiplication;491
18.5;A Virtual Trackball;493
18.6;Matrix Orthogonalization;495
18.7;Rotation Tools;496
18.8;Matrix Inversion;501
18.9;Matrices and Transformations;503
18.10;Efficient Post-Concatenation of Transformation Matrices;507
19;CHAPTER 10. MODELING AND TRANSFORMATIONS;514
19.1;Transformation Identities;516
19.2;Fixed-Point Trigonometry with CORDIC Iterations;525
19.3;Using Quaternions for Coding 3D Transformations ;529
19.4;3D Viewing and Rotation Using Orthonormal Bases ;547
19.5;The Use of Coordinate Frames in Computer Graphics;553
19.6;Forms, Vectors, and Transforms ;564
19.7;Properties of Surface-Normal Transformations;570
19.8;Transforming Axis-Aligned Bounding Boxes ;579
19.9;Constructing Shapes Summary;582
19.10;Defining Surfaces from Sampled Data;583
19.11;Defining Surfaces from Contour Data;589
19.12;Computing Surface Normals for 3D Models;593
19.13;Calculation of Reference Frames along a Space Curve;598
20;CHAPTER 11. CURVES AND SURFACES;604
20.1;Planar Cubic Curves;606
20.2;Explicit Cubic Spline Interpolation Formulas;610
20.3;Fast Spline Drawing;616
20.4;Some Properties of Bézier Curves;618
20.5;Tutorial on Forward Differencing;625
20.6;Integration of Bernstein Basis Functions;635
20.7;Solving the Nearest-Point-on-Curve Problem ;638
20.8;An Algorithm for Automatically Fitting Digitized Curves;643
21;APPENDIX I: C UTILITIES;658
21.1;Graphics Gems C Header File;660
21.2;2D and 3D Vector C Library;664
21.3;Memory Allocation in C;674
21.4;Two Useful C Macros;675
21.5;How To Build Circular Structures in C;676
21.6;How To Use C Register Variables to Point to 2D Arrays;677
22;APPENDIX II: C IMPLEMENTATIONS;678
22.1;Generating Random Points in Triangles;680
22.2;A Fast 2D Point-on-Line Test;685
22.3;Fast Circle–Rectangle Intersection Checking;687
22.4;Nice Numbers for Graph Labels;688
22.5;Efficient Generation of Sampling Jitter Using Look-Up Tables;691
22.6;Fast Anti-Aliasing Polygon Scan Conversion;693
22.7;Generic Convex Polygon Scan Conversion and Clipping;698
22.8;Concave Polygon Scan Conversion;712
22.9;Digital Line Drawing;716
22.10;Symmetric Double Step Line Algorithm;717
22.11;Rendering Anti-Aliased Lines;721
22.12;Two-Dimensional Clipping: A Vector-Based Approach;725
22.13;Median Finding on A 3×3 Grid;742
22.14;Ordered Dithering;744
22.15;A Digital "Dissolve" Effect;746
22.16;Mapping Rgb Triples onto Four Bits;749
22.17;Proper Treatment of Pixels as Integers;750
22.18;Recording Animation in Binary Order for Progressive Temporal Refinement;751
22.19;A Seed Fill Algorithm;752
22.20;An Efficient Bounding Sphere;754
22.21;Albers Equal-Area Conic Map Projection;757
22.22;A Simple Method for Box–Sphere Intersection Testing;761
22.23;3D Grid Hashing Function;764
22.24;An Efficient Ray –Polygon Intersection;766
22.25;Fast Ray–Box Intersection;767
22.26;Cubic and Quartic Roots;769
22.27;Using Sturm Sequences to Bracket Real Roots of Polynomial Equations;774
22.28;A High-Speed, Low Precision Square Root;787
22.29;A Fast Approximation to The Hypotenuse;789
22.30;Bit Interleaving for Quad- Or Octrees;790
22.31;A Fast Hsl-To-Rgb Transform;794
22.32;Matrix Orthogonalization;796
22.33;Efficient Post-Concatenation of Transformation Matrices;801
22.34;Fixed-Point Trigonometry with Cordic Iterations;804
22.35;Using Quaternions for Coding 3D Transformations;806
22.36;3D Viewing and Rotation Using Orthonormal Bases;809
22.37;Forms, Vectors, and Transforms;811
22.38;Transforming Axis-Aligned Bounding Boxes;816
22.39;Solving The Nearest-Point-On-Curve Problem and A Bézier Curve-Based Root-Finder;818
22.40;An Algorithm for Automatically Fitting Digitized Curves;828
23;References ;839
24;Index;853