O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Graphics Gems V (IBM Version)

Book Description

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

Table of Contents

  1. Cover image
  2. Title page
  3. Table of Contents
  4. The Graphics Gems Series
  5. Copyright
  6. Foreword
  7. Preface
  8. LIMITED WARRANTY AND DISCLAIMER OF LIABILITY
  9. Part I: Algebra and Arithmetic
    1. Introduction to Algebra and Arithmetic
    2. Chapter I.1: Solving Quartics and Cubics for Graphics
      1. Introduction
      2. Background
      3. Iterative Techniques
      4. Quartic Equations
      5. The Cubic
      6. Conclusion
      7. Acknowledgments
    3. Chapter I.2: Computing the Inverse Square Root
      1. Introduction
      2. Description of the Algorithm
      3. C Implementation
      4. Numerical Accuracy (Empirical Results)
      5. Implementation Notes
    4. Chapter I.3: Fixed-Point Square Root
      1. Introduction
      2. The Algorithm
      3. C Implementation
      4. Discussion
    5. Chapter I.4: Rational Approximation
      1. Introduction
      2. Best Rational Approximations
      3. Continued Fraction Calculations
      4. Complications
      5. Code
  10. Part II: Computational Geometry
    1. Introduction to Computational Geometry
    2. Chapter II.1: Efficient Computation of Polygon Area and Polyhedron Volume
      1. Introduction
      2. Background
      3. Polygon Area Calculation
      4. Polyhedron Volume Calculation
      5. Derivations and Proofs
      6. Conclusions
    3. Chapter II.2: Point in Polyhedron Testing Using Spherical Polygons
      1. Introduction
      2. Method of Solution
      3. ANSI C Code
    4. Chapter II.3: Clipping a Concave Polygon
      1. Introduction
      2. The Algorithm
      3. Pseudocode Implementation
    5. Chapter II.4: Rotations for N-Dimensional Graphics
      1. Introduction
      2. The N-Dimensional Rolling Ball
      3. Controlling the Remaining Rotational Degrees of Freedom
      4. Handy Formulas for N-Dimensional Rotations
      5. Interpolating N-Dimensional Orientation Frames
      6. Acknowledgment
    6. Chapter II.5: Parallelohedra and Uniform Quantization
      1. Original Problem
      2. Geometric Quantization
      3. Implementation
      4. Related Work
    7. Chapter II.6: Matrix-based Ellipse Geometry
      1. Matrix Form of a Planar Conic
      2. Transformation of Ellipses
      3. Intersections of Ellipses
      4. Acknowledgments
    8. Chapter II.7: Distance Approximations and Bounding Polyhedra
      1. Introduction
      2. Background
      3. Methods of Extension
      4. Geometrical Analysis
      5. Error Estimation
      6. C Implementation
      7. Conclusions
  11. Part III: Modeling and Transformation
    1. Introduction to Modeling and Transformation
    2. Chapter III.1: The Best Least-Squares Line Fit
      1. Introduction
      2. Background
      3. Optimal Least-Squares Fit
      4. Example
      5. Conclusions
    3. Chapter III.2: Surface Models and the Resolution of N-Dimensional Cell Ambiguity
      1. Introduction
      2. Background
      3. Static Analysis
      4. Interpolation Analysis
      5. Summary
    4. Chapter III.3: Tricubic Interpolation
      1. Introduction
      2. The Implementation
      3. C Code
    5. Chapter III.4: Transforming Coordinates from One Coordinate Plane to Another
      1. Introduction
      2. Method
      3. C Code
    6. Chapter III.5: A Walk through BSP Trees
      1. Introduction
      2. Background
      3. BSP-Tree Construction
      4. BSP-Tree Traversal
      5. A Viewer Collision Detection Algorithm
      6. Implementation
      7. Conclusion
      8. Acknowledgments
      9. C Code
    7. Chapter III.6: Generic Implementation of Axial Deformation Techniques
      1. Introduction
      2. Description
      3. Source Files
  12. Part IV: Curves and Surfaces
    1. Introduction to Curves and Surfaces
    2. Chapter IV.1: Identities for the Univariate and Bivariate Bernstein Basis Functions
      1. Introduction
      2. Identities for the Bernstein Basis Functions
      3. Acknowledgment
    3. Chapter IV.2: Identities for the B-Spline Basis Functions
      1. Introduction
      2. Notation
      3. Algebraic Identities for B-Spline Basis Functions
      4. Acknowledgment
    4. Chapter IV.3: Circular Arc Subdivision
      1. Introduction
      2. Derivation
      3. Proof
      4. C Implementation
      5. Discussion
    5. Chapter IV.4: Adaptive Sampling of Parametric Curves
      1. Introduction
      2. Uniform Sampling
      3. Adaptive Sampling
      4. Applications
      5. Implementation
    6. Chapter IV.5: Fast Generation of Ellipsoids
      1. Introduction
      2. Ellipsoid Generation
      3. Timing Comparisons
      4. Conclusions
      5. Acknowledgment
      6. An Efficient Implementation in C
    7. Chapter IV.6: Sparse Smooth Connection between Bézier/B-Spline Curves
      1. Introduction
      2. Solution of Smooth Connections
      3. The Computation of the Sparse Connection Polynomial
      4. Pseudocode of the Algorithm
    8. Chapter IV.7: The Length of Bézier Curves
      1. Introduction
      2. Background
      3. The Algorithms
      4. Empirical Tests
      5. Implementation
      6. Program Code
    9. Chapter IV.8: Quick and Simple Bézier Curve Drawing
      1. Abstract
      2. Method
      3. Code
    10. Chapter IV.9: Linear Form Curves
      1. Introduction
      2. Curves from Two Points
      3. Curves from Three Points
      4. Simple Curves from Many Points
      5. Blossoms
      6. Splines
      7. Linear Systems
      8. Conclusions
      9. Code
  13. Part V: Ray Tracing and Radiosity
    1. Introduction to Ray Tracing and Radiosity
    2. Chapter V.1: Computing the Intersection of a Line and a Cone
      1. Introduction
      2. Definitions
      3. Problem Statement
      4. The Algorithm
      5. Acknowledgment
    3. Chapter V.2: Ray Intersection of Tessellated Surfaces: Quadrangles versus Triangles
      1. Introduction
      2. Triangular Facets
      3. Quadrangular Facets
      4. Trapezoid
      5. Comparison
      6. Source Code
    4. Chapter V.3: Faster Ray Tracing Using Scanline Rejection
      1. Introduction
      2. Spheres
      3. Polygons
      4. Pseudocode
      5. Supersampling
      6. Optimizations
      7. Acknowledgment
      8. Source Code
    5. Chapter V.4: Ray Tracing a Swept Sphere
      1. Introduction
      2. Intersections with a Ray
      3. Computation of the Normal
      4. Hints
      5. C++ Implementation
    6. Chapter V.5: Acceleration of Ray Tracing via Voronoi Diagrams
      1. Introduction
      2. Voronoi Diagrams
      3. Computing Multidimensional Voronoi Diagrams
      4. Voronoi Subdivision for Ray Tracing
      5. Voxel Walking
      6. Implementation Details
    7. Chapter V.6: Direct Lighting Models for Ray Tracing with Cylindrical Lamps
      1. Direct Lighting Computations
      2. Sampling Cylindrical Luminaires
    8. Chapter V.7: Improving Intermediate Radiosity Images Using Directional Light
      1. Background
      2. Illumination Estimation by Ambient Light
      3. Illumination Estimation by Directional Light
      4. Results
  14. Part VI: Halftoning and Image Processing
    1. Introduction to Halftoning and Image Processing
    2. Chapter VI.1: Improved Threshold Matrices for Ordered Dithering
      1. Introduction
      2. Improved Threshold Matrices
      3. Results
    3. Chapter VI.2: Halftoning with Selective Precipitation and Adaptive Clustering
      1. Selective Precipitation
      2. Adaptive Clustering
      3. C Implementation
    4. Chapter VI.3: Faster “Pixel-Perfect” Line Clipping
      1. Introduction
      2. Algorithm
      3. Putting It All Together
      4. C Implementation of the Line Clipper
    5. Chapter VI.4: Efficient and Robust 2D Shape Vectorization
      1. Introduction
      2. Summary of the Problem
      3. The New Algorithm
      4. Additional Remarks
      5. C Code
    6. Chapter VI.5: Reversible Straight Line Edge Reconstruction
      1. Introduction
      2. Outline Reconstruction
      3. Reconstructing the Jagged Edges
      4. C Implementation
    7. Chapter VI.6: Priority-based Adaptive Image Refinement
      1. Introduction
      2. Pseudocode
      3. Details
    8. Chapter VI.7: Sampling Patterns Optimized for Uniform Distribution of Edges
      1. Introduction
      2. The Experiment
      3. Results
      4. Conclusions
      5. Example Sampling Patterns
  15. Part VII: Utilitie
    1. Introduction to Utilities
    2. Chapter VII.1: Wave Generators for Computer Graphics
      1. Introduction
      2. Noise
      3. Description
      4. Extensions
      5. Source Files
    3. Chapter VII.2: Fast Polygon–Cube Intersection Testing
      1. Overview
      2. Background
      3. Description
      4. Polyhedron–Cube Intersection Testing
      5. Conclusions
    4. Chapter VII.3: Velocity-based Collision Detection
      1. Introduction
      2. Preliminaries
      3. Algorithm
      4. Implementation
      5. The C++ Code
    5. Chapter VII.4: Spatial Partitioning of a Polygon by a Plane
      1. The Representation of Polygons
      2. The Algorithm
    6. Chapter VII.5: Fast Polygon Triangulation Based on Seidel’s Algorithm
      1. Introduction
      2. Overview of the Triangulation Algorithm
      3. Data Structures for Implementation
      4. Implementation Notes
    7. Chapter VII.6: Accurate Z-Buffer Rendering
      1. Description
    8. Chapter VII.7: A Survey of Extended Graphics Libraries
      1. Overview
      2. A Graphics Math Library
      3. A Toolbox of Macro Functions
      4. Penultimate Vector Macros
      5. The C Vector Library in 4D
      6. Contributors
  16. Author Index
  17. Index
  18. Volume I–V Cumulative Index