Paeth Graphics Gems V (Macintosh Version)

1. Auflage 2014
ISBN: 978-1-4832-9669-2
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 438 Seiten, Web PDF

Reihe: Graphics Gems - Macintosh

Graphics Gems V is the newest volume in The Graphics Gems Series. It is intended to provide the graphics community with a set of practical tools for implementing new ideas and techniques, and to offer working solutions to real programming problems. These tools are written by a wide variety of graphics programmers from industry, academia, and research. The books in the series have become essential, time-saving tools for many programmers.Latest collection of graphics tips in The Graphics Gems Series written by the leading programmers in the field.Contains over 50 new gems displaying some of the most recent and innovative techniques in graphics programming.Includes gems covering ellipses, splines, Bezier curves, and ray tracing.Disk included containing source code from the gems available in both IBM and Macintosh versions.

Alan W. Paeth is a professor of computer science at Okanagan University College in British Columbia. Previously, he was a research scientist specializing in VLSI technology at Xerox PARC. The principle architect of the first operational Pixelplanes silicon, he also fabricated the first Berkeley RISC and SGI Graphics Engine chips. His degrees span three calendar decades and three fields: Engineering, Mathematics, and Computer Science.

Autoren/Hrsg.

Paeth, Alan W.

Inhaltsverzeichnis

1;Front Cover;1
2;Graphics Gems
V;4
3;Copyright Page;5
4;Table of Contents;6
5;Foreword;10
6;Preface;14
7;Author Index;18
8;Part I: Algebra and Arithmetic;22
8.1;Chapter I.1. Solving Quartics and Cubics for
Graphics;24
8.1.1;Introduction;24
8.1.2;Background;24
8.1.3;Iterative Techniques;25
8.1.4;Quartic Equations;25
8.1.5;The Cubic;32
8.1.6;Conclusion;34
8.1.7;Acknowledgments;35
8.1.8;Bibliography;35
8.2;Chapter
I.2. Computing the Inverse Square Root;37
8.2.1;Introduction;37
8.2.2;Description of the Algorithm;37
8.2.3;C Implementation;38
8.2.4;Numerical Accuracy (Empirical Results);40
8.2.5;Implementation Notes;41
8.2.6;Bibliography;42
8.3;Chapter
I.3. Fixed-Point Square Root;43
8.3.1;Introduction;43
8.3.2;The Algorithm;43
8.3.3;C Implementation;44
8.3.4;Discussion;44
8.3.5;Bibliography;44
8.4;Chapter
I.4. Rational Approximation;46
8.4.1;Introduction;46
8.4.2;Best Rational Approximations;46
8.4.3;Continued Fraction Calculations;48
8.4.4;Complications;49
8.4.5;Code;50
8.4.6;Bibliography;53
9;Part II: Computational
Geometry;54
9.1;Chapter
II.1. Efficient Computation of Polygon Area and Polyhedron Volume;56
9.1.1;Introduction;56
9.1.2;Background;56
9.1.3;Polygon Area Calculation;58
9.1.4;Polyhedron Volume Calculation;58
9.1.5;Derivations and Proofs;60
9.1.6;Conclusions;62
9.1.7;Bibliography;62
9.2;Chapter
II.2. Point in Polyhedron Testing Using Spherical Polygons;63
9.2.1;Introduction;63
9.2.2;Method of Solution;63
9.2.3;ANSI C Code;67
9.2.4;Bibliography;70
9.3;Chapter
II.3. Clipping a Concave Polygon;71
9.3.1;Introduction;71
9.3.2;The Algorithm;71
9.3.3;Pseudocode Implementation;73
9.3.4;Bibliography;75
9.4;Chapter II.4.
Rotations for N-Dimensional Graphics;76
9.4.1;Introduction;76
9.4.2;The N-Dimensional Rolling Ball;76
9.4.3;Controlling the Remaining Rotational Degrees of Freedom;80
9.4.4;Handy Formulas for
N-Dimensional Rotations;81
9.4.5;Interpolating
N-Dimensional Orientation Frames;82
9.4.6;Acknowledgment;84
9.4.7;Bibliography;84
9.5;Chapter II.5.
Parallelohedra and Uniform Quantization;86
9.5.1;Original Problem;86
9.5.2;Geometric Quantization;88
9.5.3;Implementation;90
9.5.4;Related Work;90
9.5.5;Bibliography;91
9.6;Chapter
II.6. Matrix-based Ellipse Geometry;93
9.6.1;Matrix Form of a Planar Conic;93
9.6.2;Transformation of Ellipses;93
9.6.3;Intersections of Ellipses;96
9.6.4;Acknowledgments;98
9.6.5;Bibliography;98
9.7;Chapter
II.7. Distance Approximations and Bounding Polyhedra;99
9.7.1;Introduction;99
9.7.2;Background;99
9.7.3;Methods of Extension;100
9.7.4;Geometrical Analysis;103
9.7.5;Error Estimation;105
9.7.6;C Implementation;106
9.7.7;Conclusions;107
9.7.8;Bibliography;107
10;Part III: Modeling and Transformation;110
10.1;Chapter
III.1. The Best Least-Squares Line Fit;112
10.1.1;Introduction;112
10.1.2;Background;112
10.1.3;Optimal Least-Squares Fit;113
10.1.4;Example;116
10.1.5;Conclusions;118
10.1.6;Bibliography;118
10.2;Chapter III.2. Surface Models and the
Resolution of N-Dimensional Cell Ambiguity;119
10.2.1;Introduction;119
10.2.2;Background;119
10.2.3;Static Analysis;120
10.2.4;Interpolation Analysis;122
10.2.5;Summary;124
10.2.6;Bibliography;126
10.3;Chapter
III.3. Tricubic Interpolation;128
10.3.1;Introduction;128
10.3.2;The Implementation;128
10.3.3;C Code;129
10.3.4;Bibliography;131
10.4;Chapter III.4. Transforming Coordinates from One Coordinate Plane to
Another;132
10.4.1;Introduction;132
10.4.2;Method;132
10.4.3;C Code;136
10.4.4;Bibliography;141
10.5;Chapter
III.5. A Walk through BSP Trees;142
10.5.1;Introduction;142
10.5.2;Background;142
10.5.3;BSP-Tree Construction;143
10.5.4;BSP-Tree Traversal;146
10.5.5;A Viewer Collision Detection Algorithm;149
10.5.6;Implementation;151
10.5.7;Conclusion;151
10.5.8;Acknowledgments;152
10.5.9;C Code;152
10.5.10;Bibliography;159
10.6;Chapter
III.6. Generic Implementation of Axial Deformation Techniques;160
10.6.1;Introduction;160
10.6.2;Description;160
10.6.3;Source Files;162
10.6.4;Bibliography;166
11;Part IV: Curves and Surfaces;168
11.1;Chapter
IV.1. Identities for the Univariate and Bivariate Bernstein Basis Functions;170
11.1.1;Introduction;170
11.1.2;Identities for the Bernstein Basis Functions;171
11.1.3;Acknowledgment;182
11.1.4;Bibliography;182
11.2;Chapter IV.2. Identities for the B-Spline Basis
Functions;184
11.2.1;Introduction;184
11.2.2;Notation;184
11.2.3;Algebraic Identities for B-Spline Basis Functions;185
11.2.4;Acknowledgment;188
11.2.5;Bibliography;188
11.3;Chapter
lV.3. Circular Arc Subdivision;189
11.3.1;Introduction;189
11.3.2;Derivation;190
11.3.3;Proof;191
11.3.4;C Implementation;191
11.3.5;Discussion;192
11.3.6;Bibliography;193
11.4;Chapter
IV.4. Adaptive Sampling of Parametric Curves;194
11.4.1;Introduction;194
11.4.2;Uniform Sampling;194
11.4.3;Adaptive Sampling;194
11.4.4;Applications;197
11.4.5;Implementation;197
11.4.6;Bibliography;198
11.5;Chapter
IV.5. Fast Generation of Ellipsoids;200
11.5.1;Introduction;200
11.5.2;Ellipsoid Generation;201
11.5.3;Timing Comparisons;204
11.5.4;Conclusions;206
11.5.5;Acknowledgment;206
11.5.6;An Efficient Implementation in C;206
11.5.7;Bibliography;211
11.6;Chapter
IV.6. Sparse Smooth Connection between Bézier/B-Spline Curves;212
11.6.1;Introduction;212
11.6.2;Solution of Smooth Connections;213
11.6.3;The Computation of the Sparse Connection Polynomial;214
11.6.4;Pseudocode of the Algorithm;217
11.6.5;Bibliography;219
11.7;Chapter
lV.7. The Length of Bézier Curves;220
11.7.1;Introduction;220
11.7.2;Background;220
11.7.3;The Algorithms;221
11.7.4;Empirical Tests;223
11.7.5;Implementation;224
11.7.6;Program Code;225
11.7.7;Bibliography;225
11.8;Chapter
lV.8. Quick and Simple Bézier Curve Drawing;227
11.8.1;Abstract;227
11.8.2;Method;227
11.8.3;Code;228
11.8.4;Bibliography;230
11.9;Chapter
lV.9. Linear Form Curves;231
11.9.1;Introduction;231
11.9.2;Curves from Two Points;231
11.9.3;Curves from Three Points;232
11.9.4;Simple Curves from Many Points;236
11.9.5;Blossoms;236
11.9.6;Splines;237
11.9.7;Linear Systems;239
11.9.8;Conclusions;240
11.9.9;Code;241
11.9.10;Bibliography;243
12;Part V: Ray Tracing and Radiosity;246
12.1;Chapter V.1. Computing the Intersection of a
Line and a Cone;248
12.1.1;Introduction;248
12.1.2;Definitions;248
12.1.3;Problem Statement;248
12.1.4;The Algorithm;249
12.1.5;Acknowledgment;251
12.1.6;Bibliography;251
12.2;Chapter
V.2. Ray Intersection of Tessellated Surfaces: Quadrangles versus Triangles;253
12.2.1;Introduction;253
12.2.2;Triangular Facets;253
12.2.3;Quadrangular Facets;256
12.2.4;Trapezoid;256
12.2.5;Comparison;257
12.2.6;Source Code;258
12.2.7;Bibliography;261
12.3;Chapter
V.3. Faster Ray Tracing Scanline Rejection;263
12.3.1;Introduction;263
12.3.2;Spheres;265
12.3.3;Polygons;267
12.3.4;Pseudocode;268
12.3.5;Supersampling;269
12.3.6;Optimizations;270
12.3.7;Acknowledgment;270
12.3.8;Source Code;270
12.3.9;Bibliography;278
12.4;Chapter
V.4. Ray Tracing a Swept Sphere;279
12.4.1;Introduction;279
12.4.2;Intersections with a Ray;280
12.4.3;Computation of the Normal;282
12.4.4;Hints;282
12.4.5;C++ Implementation;282
12.4.6;Bibliography;288
12.5;Chapter
V.5. Acceleration of Ray Tracing via Voronoi Diagrams;289
12.5.1;Introduction;289
12.5.2;Voronoi Diagrams;290
12.5.3;Computing Multidimensional Voronoi Diagrams;291
12.5.4;Voronoi Subdivision for Ray Tracing;293
12.5.5;Voxel Walking;294
12.5.6;Implementation Details;296
12.5.7;Bibliography;304
12.6;Chapter
V.6. Direct Lighting Models for Ray Tracing with Cylindrical Lamps;306
12.6.1;Direct Lighting Computations;306
12.6.2;Sampling Cylindrical Luminaires;308
12.6.3;Bibliography;309
12.7;Chapter
V.7. Improving Intermediate Radiosity Images Using Directional Light;311
12.7.1;Background;311
12.7.2;Illumination Estimation by Ambient Light;312
12.7.3;Illumination Estimation by Directional Light;312
12.7.4;Results;313
12.7.5;Bibliography;314
13;Part VI: Halftoning and Image Processing;316
13.1;Chapter
VI.1. Improved Threshold Matrices for Ordered Dithering;318
13.1.1;Introduction;318
13.1.2;Improved Threshold Matrices;319
13.1.3;Results;324
13.1.4;Bibliography;324
13.2;Chapter
VI.2. Halftoning with Selective Precipitation and Adaptive Clustering;325
13.2.1;Selective Precipitation;325
13.2.2;Adaptive Clustering;327
13.2.3;C Implementation;329
13.2.4;Bibliography;335
13.3;Chapter
VI.3. Faster "Pixel-Perfect" Line Clipping;337
13.3.1;Introduction;337
13.3.2;Algorithm;337
13.3.3;Putting It All Together;341
13.3.4;C Implementation of the Line Clipper;342
13.3.5;Bibliography;345
13.4;Chapter
VI.4. Efficient and Robust 2D Shape Vectorization;346
13.4.1;Introduction;346
13.4.2;Summary of the Problem;346
13.4.3;The New Algorithm;349
13.4.4;Additional Remarks;351
13.4.5;C Code;352
13.4.6;Bibliography;359
13.5;Chapter
VI.5. Reversible Straight Line Edge Reconstruction;361
13.5.1;Introduction;361
13.5.2;Outline Reconstruction;362
13.5.3;Reconstructing the Jagged Edges;365
13.5.4;C Implementation;365
13.5.5;Bibliography;376
13.6;Chapter
VI.6. Priority-based Adaptive Image Refinement;378
13.6.1;Introduction;378
13.6.2;Pseudocode;378
13.6.3;Details;379
13.6.4;Bibliography;381
13.7;Chapter
VI.7. Sampling Patterns Optimized for Uniform Distribution of Edges;382
13.7.1;Introduction;382
13.7.2;The Experiment;382
13.7.3;Results;383
13.7.4;Conclusions;384
13.7.5;Example Sampling Patterns;385
13.7.6;Bibliography;386
14;Part VII: Utilities;388
14.1;Chapter
VII.1. Wave Generators for Computer Graphics;390
14.1.1;Introduction;390
14.1.2;Noise;390
14.1.3;Description;391
14.1.4;Extensions;391
14.1.5;Source Files;394
14.1.6;Bibliography;397
14.2;Chapter VII.2. Fast Polygon–Cube Intersection
Testing;398
14.2.1;Overview;398
14.2.2;Background;398
14.2.3;Description;398
14.2.4;Polyhedron–Cube
Intersection Testing;401
14.2.5;Conclusions;402
14.2.6;Bibliography;402
14.3;Chapter
VII.3. Velocity-based Collision Detection;403
14.3.1;Introduction;403
14.3.2;Preliminaries;403
14.3.3;Algorithm;404
14.3.4;Implementation;406
14.3.5;The C++ Code;406
14.3.6;Bibliography;408
14.4;Chapter
VII.4. Spatial Partitioning of a Polygonby a Plane;409
14.4.1;The Representation of Polygons;409
14.4.2;The Algorithm;410
14.4.3;Bibliography;416
14.5;Chapter
VII.5. Fast Polygon Triangulation Based on Seidel's Algorithm;417
14.5.1;Introduction;417
14.5.2;Overview of the Triangulation Algorithm;417
14.5.3;Data Structures for Implementation;418
14.5.4;Implementation Notes;419
14.5.5;Bibliography;420
14.6;Chapter
VII.6. Accurate Z-Buffer Rendering;421
14.6.1;Description;421
14.6.2;Bibliography;422
14.7;Chapter
VII.7. A Survey of Extended Graphics Libraries;423
14.7.1;Overview;423
14.7.2;A Graphics Math Library;424
14.7.3;A Toolbox of Macro Functions;425
14.7.4;Penultimate Vector Macros;427
14.7.5;The C Vector Library in 4D;428
14.7.6;Contributors;428
14.7.7;Bibliography;428
15;Index;430
16;Volume l–V
Cumulative Index;434