The AP Professional graphics CD-ROM

Cover......Page 1
Copyright......Page 3
About the Cover......Page 5
Contents......Page 6
Preface......Page 14
Introduction......Page 16
Mathmatical Notations......Page 18
Pseudo-Code......Page 20
Contributors......Page 25
I  2D Geometry......Page 29
1-Useful 2D Geometry......Page 30
Trig Summary......Page 39
2-Useful Trigonometry......Page 40
3-Trigonometric Functions at Select Points......Page 45
4-Triangles......Page 47
5-Generating Random Points in Triangles......Page 51
6-Fast Line-Edge Intersections on a Uniform Grid......Page 56
Anti-Aliasing Summary......Page 64
7-Area of Intersection......Page 65
8-Area of Intersection: Circle and a Thick Line......Page 67
9-Area of Intersection: Two Circles......Page 70
10-Vertical Distance from a Point to a Line......Page 74
11-A Fast 2D Point-on-Line Test......Page 76
12-Fast Circle-Rectangle Intersection Checking......Page 78
II 2D Rendering......Page 81
1-Circles of Integral Radius on Integer Lattices......Page 82
2-Nice Numbers for Graph Labels......Page 86
3-Efficient Generation of Sampling Jitter Using Look-Up Tables......Page 89
Scan Conversion Summary......Page 100
4-Fast Anti-Aliasing Polygon Scan Conversion......Page 101
5-Generic Convex Polygon Scan Conversion and Clipping......Page 109
6-Concave Polygon Scan Conversion......Page 112
7-Fast Scan Conversion of Arbitrary Polygons......Page 117
Line-Drawing Summary......Page 123
8-Digital Line Drawing......Page 124
9-Symmetric Double Step Line Algorithm......Page 126
10-Rendering Anti-Aliased Lines......Page 130
11-An Algorithm for Filling in 2D Wide Line Bevel Joints......Page 132
12-Rendering Fat Lines on a Raster Grid......Page 139
13-Two-Dimensional Clipping: A Vector-Based Approach......Page 146
14-Periodic Tilings of the Plane on a Raster Grid......Page 154
III Image Processing......Page 165
Anti-Aliasing Filters Summary......Page 166
1-Convenient Anti-Aliasing Filters that Minimize “Bumpy” Sampling......Page 167
2-Filters for Common Resampling Tasks......Page 170
3-Smoothing Enlarged Monochrome Images......Page 189
4-Median Finding on a 3x3 Grid......Page 194
5-Ordered Dithering......Page 199
6-A Fast Algorithm for General Raster Rotation......Page 202
7-Useful 1-to-1 Pixel Transforms......Page 219
8-Alpha Blending......Page 233
IV Frame Buffer Techniques......Page 235
1-Frame Buffers and Color Maps......Page 236
2-Reading a Write-Only Write Mask......Page 240
3-A Digital “Dissolve” Effect......Page 242
4-Mapping RGB Triples Onto Four Bits......Page 254
5-What are the Coordinates of a Pixel?......Page 267
6-Proper Treatment of Pixels as Integers......Page 270
7-Normal Coding......Page 278
8-Recording Anim. in Binary Order for Progressive Temporal Refinement......Page 286
9-1-To-1 Pixel Transforms Optimized Through Color-Map Manipulation......Page 291
10-A Seed Fill Algorithm......Page 296
11-Filling A Region in a Frame Buffer......Page 299
12-Precalculating Addr. for Fast Fills, Circles, and Lines......Page 306
13-Color Quantization: Octree Quantization......Page 308
V 3D Geometry......Page 315
1-Useful 3D Geometry......Page 316
2-An Efficient Bounding Sphere......Page 320
3-Intersection of Two Lines in Three-Space......Page 323
4-Intersection of Three Planes......Page 324
V Mapping Summary......Page 325
5-Digital Cartography for Computer Graphics......Page 326
6-Albers Equal-Area Conic Map Projection......Page 340
Boxes and Spheres Summary......Page 345
7-Spheres-to-Voxels Conversion......Page 346
8-A Simple Method for Box-Sphere Intersection Testing......Page 354
VI 3D Rendering......Page 361
1-3D Grid Hashing Function......Page 362
2-Backface Culling......Page 365
3-Fast Dot Products for Shading......Page 367
4-Scanline Depth Gradient of a Z-Buffered Triangle......Page 380
5-Simulating Fog and Haze......Page 383
6-Interpretation of Texture Map Indices......Page 385
7-Multidimensional Sum Tables......Page 395
VII Ray Tracing......Page 401
1-A Simple Ray Rejection Test......Page 402
VII Ray-Object Intersection Summary......Page 404
2-Intersection of a Ray with a Sphere......Page 405
3-An Efficicent Ray-Polygon Intersection......Page 407
4-Fast Ray-Polygon Intersection......Page 411
5-Fast Ray-Box  Intersection......Page 412
6-Shadow Attenuation for Ray Tracing Transparent Objects......Page 414
VIII Numerical and Programming Techniques......Page 418
Root Finding Summary......Page 419
1-Cubic and Quartic Roots......Page 420
2-A Bézier Curve-based Root-Finder......Page 424
3-Using Sturm Sequences to Bracket Real Roots of Polynomial Equations......Page 432
Distance Measures Summary......Page 439
4-A High Speed, Low Precision Square Root......Page 440
5-A Fast Approximation to the Hypontenuse......Page 443
6-A Fast Approximation to 3D Euclidian Distance......Page 448
7-Full-Precision Constants......Page 450
8-Converting Between Bits and Digits......Page 451
9-Storage-Free Swapping......Page 452
10-Generating Random Integers......Page 454
11-Fast 2D-3D Rotation......Page 456
12-Bit Patterns for Encoding Angles......Page 458
13-Bit Interleaving for Quad- or Octrees......Page 459
14-A Fast HSL-to-RGB Transform......Page 464
IX Matrix Techniques......Page 466
1-Matrix Identities......Page 467
Rotation Matrix Methods Summary......Page 469
2-Transforming Axes......Page 470
3-Fast Matrix Multiplication......Page 474
4-A Virtual Trackball......Page 476
5-Matrix Orthogonalization......Page 478
6-Rotation Tools......Page 479
7-Matrix  Inversion......Page 484
8-Matrices and Transformations......Page 486
9-Efficient Post-Concatention of Transformation Matrices......Page 490
X Modelling and Transformations......Page 498
1-Transformation Identities......Page 499
2-Fixed-Point Trigonometry with Cordic Iterations......Page 508
3-Using Quaternions for Coding 3D Transformations......Page 512
4-3D Viewing and Rotation Using Orthonormal Bases......Page 530
5-The Use of Coordinate Frames in Computer Graphics......Page 536
6-Forms, Vectors, and Transforms......Page 547
7-Properties of Surface-Normal Transformations......Page 553
8-Transforming Axis-Aligned Bounding Boxes......Page 562
Constructing Shapes Summary......Page 565
9-Defining Surfaces from Sampled Data......Page 566
10-Defining Surfaces from Contour Data......Page 572
11-Computing Surface Normals for 3D Models......Page 576
12-Calculation of Reference Frames Along a Space Curve......Page 581
XI Curves and Surfaces......Page 588
1-Planar Cubic Curves......Page 589
2-Explicit Cubic Spline Interpolation Formulas......Page 593
3-Fast Spline Drawing......Page 599
4-Some Properties of Bézier Curves......Page 601
5-Tutorial on Forward Differencing......Page 608
6-Integration of Bernstein Basis Functions......Page 618
7-Solving the Nearest-Point-on-Curve Problem......Page 621
8-An Algorithm for Automatically Fitting Digitized Curves......Page 626
References......Page 641
A......Page 655
B-C......Page 656
C-D......Page 657
D-G......Page 658
G-L......Page 659
L-O......Page 660
O-P......Page 661
P-R......Page 662
R-S......Page 663
S-T......Page 664
T-V......Page 665
W-Z......Page 666