Graphics Gems V (Macintosh Version) (eBook)

Front Cover 1
Graphics Gems 
4 
Copyright Page 5
Table of Contents 6
Foreword 10
Preface 14
Author Index 18
Part I: Algebra and Arithmetic 22
Chapter I.1. Solving Quartics and Cubics for 
24 
Introduction 24
Background 24
Iterative Techniques 25
Quartic Equations 25
The Cubic 32
Conclusion 34
Acknowledgments 35
Bibliography 35
Chapter 
37 
Introduction 37
Description of the Algorithm 37
C Implementation 38
Numerical Accuracy (Empirical Results) 40
Implementation Notes 41
Bibliography 42
Chapter 
43 
Introduction 43
The Algorithm 43
C Implementation 44
Discussion 44
Bibliography 44
Chapter 
46 
Introduction 46
Best Rational Approximations 46
Continued Fraction Calculations 48
Complications 49
Code 50
Bibliography 53
Part II: Computational 
54 
Chapter 
56 
Introduction 56
Background 56
Polygon Area Calculation 58
Polyhedron Volume Calculation 58
Derivations and Proofs 60
Conclusions 62
Bibliography 62
Chapter 
63 
Introduction 63
Method of Solution 63
ANSI C Code 67
Bibliography 70
Chapter 
71 
Introduction 71
The Algorithm 71
Pseudocode Implementation 73
Bibliography 75
Chapter II.4. 
76 
Introduction 76
The N-Dimensional Rolling Ball 76
Controlling the Remaining Rotational Degrees of Freedom 80
Handy Formulas for 
81 
Interpolating 
82 
Acknowledgment 84
Bibliography 84
Chapter II.5. 
86 
Original Problem 86
Geometric Quantization 88
Implementation 90
Related Work 90
Bibliography 91
Chapter 
93 
Matrix Form of a Planar Conic 93
Transformation of Ellipses 93
Intersections of Ellipses 96
Acknowledgments 98
Bibliography 98
Chapter 
99 
Introduction 99
Background 99
Methods of Extension 100
Geometrical Analysis 103
Error Estimation 105
C Implementation 106
Conclusions 107
Bibliography 107
Part III: Modeling and Transformation 110
Chapter 
112 
Introduction 112
Background 112
Optimal Least-Squares Fit 113
Example 116
Conclusions 118
Bibliography 118
Chapter III.2. Surface Models and the 
119 
Introduction 119
Background 119
Static Analysis 120
Interpolation Analysis 122
Summary 124
Bibliography 126
Chapter 
128 
Introduction 128
The Implementation 128
C Code 129
Bibliography 131
Chapter III.4. Transforming Coordinates from One Coordinate Plane to 
132 
Introduction 132
Method 132
C Code 136
Bibliography 141
Chapter 
142 
Introduction 142
Background 142
BSP-Tree Construction 143
BSP-Tree Traversal 146
A Viewer Collision Detection Algorithm 149
Implementation 151
Conclusion 151
Acknowledgments 152
C Code 152
Bibliography 159
Chapter 
160 
Introduction 160
Description 160
Source Files 162
Bibliography 166
Part IV: Curves and Surfaces 168
Chapter 
170 
Introduction 170
Identities for the Bernstein Basis Functions 171
Acknowledgment 182
Bibliography 182
Chapter IV.2. Identities for the B-Spline Basis 
184 
Introduction 184
Notation 184
Algebraic Identities for B-Spline Basis Functions 185
Acknowledgment 188
Bibliography 188
Chapter 
189 
Introduction 189
Derivation 190
Proof 191
C Implementation 191
Discussion 192
Bibliography 193
Chapter 
194 
Introduction 194
Uniform Sampling 194
Adaptive Sampling 194
Applications 197
Implementation 197
Bibliography 198
Chapter 
200 
Introduction 200
Ellipsoid Generation 201
Timing Comparisons 204
Conclusions 206
Acknowledgment 206
An Efficient Implementation in C 206
Bibliography 211
Chapter 
212 
Introduction 212
Solution of Smooth Connections 213
The Computation of the Sparse Connection Polynomial 214
Pseudocode of the Algorithm 217
Bibliography 219
Chapter 
220 
Introduction 220
Background 220
The Algorithms 221
Empirical Tests 223
Implementation 224
Program Code 225
Bibliography 225
Chapter 
227 
Abstract 227
Method 227
Code 228
Bibliography 230
Chapter 
231 
Introduction 231
Curves from Two Points 231
Curves from Three Points 232
Simple Curves from Many Points 236
Blossoms 236
Splines 237
Linear Systems 239
Conclusions 240
Code 241
Bibliography 243
Part V: Ray Tracing and Radiosity 246
Chapter V.1. Computing the Intersection of a 
248 
Introduction 248
Definitions 248
Problem Statement 248
The Algorithm 249
Acknowledgment 251
Bibliography 251
Chapter 
253 
Introduction 253
Triangular Facets 253
Quadrangular Facets 256
Trapezoid 256
Comparison 257
Source Code 258
Bibliography 261
Chapter 
263 
Introduction 263
Spheres 265
Polygons 267
Pseudocode 268
Supersampling 269
Optimizations 270
Acknowledgment 270
Source Code 270
Bibliography 278
Chapter 
279 
Introduction 279
Intersections with a Ray 280
Computation of the Normal 282
Hints 282
C++ Implementation 282
Bibliography 288
Chapter 
289 
Introduction 289
Voronoi Diagrams 290
Computing Multidimensional Voronoi Diagrams 291
Voronoi Subdivision for Ray Tracing 293
Voxel Walking 294
Implementation Details 296
Bibliography 304
Chapter 
306 
Direct Lighting Computations 306
Sampling Cylindrical Luminaires 308
Bibliography 309
Chapter 
311 
Background 311
Illumination Estimation by Ambient Light 312
Illumination Estimation by Directional Light 312
Results 313
Bibliography 314
Part VI: Halftoning and Image Processing 316
Chapter 
318 
Introduction 318
Improved Threshold Matrices 319
Results 324
Bibliography 324
Chapter 
325 
Selective Precipitation 325
Adaptive Clustering 327
C Implementation 329
Bibliography 335
Chapter 
337 
Introduction 337
Algorithm 337
Putting It All Together 341
C Implementation of the Line Clipper 342
Bibliography 345
Chapter 
346 
Introduction 346
Summary of the Problem 346
The New Algorithm 349
Additional Remarks 351
C Code 352
Bibliography 359
Chapter 
361 
Introduction 361
Outline Reconstruction 362
Reconstructing the Jagged Edges 365
C Implementation 365
Bibliography 376
Chapter 
378 
Introduction 378
Pseudocode 378
Details 379
Bibliography 381
Chapter 
382 
Introduction 382
The Experiment 382
Results 383
Conclusions 384
Example Sampling Patterns 385
Bibliography 386
Part VII: Utilities 388
Chapter 
390 
Introduction 390
Noise 390
Description 391
Extensions 391
Source Files 394
Bibliography 397
Chapter VII.2. Fast Polygon–Cube Intersection 
398 
Overview 398
Background 398
Description 398
Polyhedron–Cube 
401 
Conclusions 402
Bibliography 402
Chapter 
403 
Introduction 403
Preliminaries 403
Algorithm 404
Implementation 406
The C++ Code 406
Bibliography 408
Chapter 
409 
The Representation of Polygons 409
The Algorithm 410
Bibliography 416
Chapter 
417 
Introduction 417
Overview of the Triangulation Algorithm 417
Data Structures for Implementation 418
Implementation Notes 419
Bibliography 420
Chapter 
421 
Description 421
Bibliography 422
Chapter 
423 
Overview 423
A Graphics Math Library 424
A Toolbox of Macro Functions 425
Penultimate Vector Macros 427
The C Vector Library in 4D 428
Contributors 428
Bibliography 428
Index 430
Volume l–V 
434