You are previewing Mathematics for 3D Game Programming and Computer Graphics, Third Edition.
by Eric Lengyel Published by Course Technology PTR
2. Preface
3. 1. The Rendering Pipeline
4. 2. Vectors
5. 3. Matrices
6. 4. Transforms
1. 4.1. Linear Transformations
2. 4.2. Scaling Transforms
3. 4.3. Rotation Transforms
4. 4.4. Homogeneous Coordinates
5. 4.5. Transforming Normal Vectors
6. 4.6. Quaternions
7. Chapter 4 Summary
8. Exercises for Chapter 4
7. 5. Geometry for 3D Engines
1. 5.1. Lines in 3D Space
2. 5.2. Planes in 3D Space
3. 5.3. The View Frustum
4. 5.4. Perspective-Correct Interpolation
5. 5.5. Projections
6. 5.6. Reflections and Oblique Clipping
7. Chapter 5 Summary
8. Exercises for Chapter 5
8. 6. Ray Tracing
1. 6.1. Root Finding
2. 6.2. Surface Intersections
3. 6.3. Normal Vector Calculation
4. 6.4. Reflection and Refraction Vectors
5. Chapter 6 Summary
6. Exercises for Chapter 6
9. 7. Lighting and Shading
1. 7.1. RGB Color
2. 7.2. Light Sources
3. 7.3. Diffuse Reflection
4. 7.4. Specular Reflection
5. 7.5. Texture Mapping
6. 7.6. Emission
7. 7.7. Shading Models
8. 7.8. Bump Mapping
9. 7.9. A Physical Reflection Model
10. Chapter 7 Summary
11. Exercises for Chapter 7
10. 8. Visibility Determination
1. 8.1. Bounding Volume Construction
2. 8.2. Bounding Volume Tests
3. 8.3. Spatial Partitioning
4. 8.4. Portal Systems
5. Chapter 8 Summary
6. Exercises for Chapter 8
11. 9. Polygonal Techniques
1. 9.1. Depth Value Offset
2. 9.2. Decal Application
3. 9.3. Billboarding
4. 9.4. Polygon Reduction
5. 9.5. T-Junction Elimination
6. 9.6. Triangulation
7. Chapter 9 Summary
8. Exercises for Chapter 9
1. 10.1. Shadow Casting Set
2. 10.2. Shadow Mapping
3. 10.3. Stencil Shadows
4. Chapter 10 Summary
5. Exercises for Chapter 10
13. 11. Curves and Surfaces
1. 11.1. Cubic Curves
2. 11.2. Hermite Curves
3. 11.3. Bézier Curves
4. 11.4. Catmull-Rom Splines
5. 11.5. Cubic Splines
6. 11.6. B-Splines
7. 11.7. Bicubic Surfaces
8. 11.8. Curvature and Torsion
9. Chapter 11 Summary
10. Exercises for Chapter 11
14. 12. Collision Detection
1. 12.1. Plane Collisions
2. 12.2. General Sphere Collisions
3. 12.3. Sliding
4. 12.4. Collision of Two Spheres
5. Chapter 12 Summary
6. Exercises for Chapter 12
15. 13. Linear Physics
1. 13.1. Position Functions
2. 13.2. Second-Order Differential Equations
3. 13.3. Projectile Motion
4. 13.4. Resisted Motion
5. 13.5. Friction
6. Chapter 13 Summary
7. Exercises for Chapter 13
16. 14. Rotational Physics
1. 14.1. Rotating Environments
2. 14.2. Rigid Body Motion
3. 14.3. Oscillatory Motion
4. Chapter 14 Summary
5. Exercises for Chapter 14
17. 15. Fluid and Cloth Simulation
1. 15.1. Fluid Simulation
2. 15.2. Cloth Simulation
3. Chapter 15 Summary
4. Exercises for Chapter 15
18. 16. Numerical Methods
1. 16.1. Trigonometric Functions
2. 16.2. Linear Systems
3. 16.3. Eigenvalues and Eigenvectors
4. 16.4. Ordinary Differential Equations
5. Chapter 16 Summary
6. Exercises for Chapter 16
19. A. Complex Numbers
20. B. Trigonometry Reference
21. C. Coordinate Systems
22. D. Taylor Series
23. E. Answers to Exercises

# Chapter 6. Ray Tracing

The term ray tracing refers to any algorithm that follows beams of light to determine with which objects they interact in the world. Applications include light map generation, visibility determination, collision detection, and line-of-sight testing. This chapter describes how the points of intersection where a ray strikes an object can be found and how to alter the path of a ray when it strikes a reflective or refractive surface.

# Root Finding

The problem of finding the points at which a line defined by the equation

Equation 6.1.

intersects a surface generally requires finding the roots of a degree n polynomial in t. For planar ...