Geometry for Programmers

Geometry for Programmers
brief contents
contents
preface
acknowledgments
about this book
Who should read this book
How this book is organized
About the code
liveBook discussion forum
about the author
about the cover illustration
1 Getting started
1.1 Which parts of programming require geometry?
1.2 What is geometry for programmers?
1.3 Why not let my tools take care of geometry?
1.4 Applied geometry has been around forever; why learn it now?
1.5 You don’t have to know much to start
1.6 SymPy will do your math for you
Summary
2 Terminology and jargon
2.1 Numbers, points, and vectors
2.1.1 Numbers
2.1.2 Vectors
2.1.3 Section 2.1 summary
2.2 Vertices and triangles
2.2.1 Being pedantic about triangles
2.2.2 Triangle quality
2.2.3 Section 2.2 summary
2.3 Lines, planes, and their equations
2.3.1 Lines and planes
2.3.2 The parametric form for 3D lines
2.3.3 Section 2.3 summary
2.4 Functions and geometric transformations
2.4.1 What is a function?
2.4.2 Function types most commonly used in geometric modeling
2.4.3 Section 2.4 summary
2.5 The shortest possible introduction to matrix algebra
2.5.1 What is algebra?
2.5.2 How does matrix algebra work?
2.5.3 Section 2.5 summary
2.6 Exercises
2.7 Solutions to exercises
Summary
3 The geometry of linear equations
3.1 Linear equations as lines and planes
3.1.1 Introducing a hyperplane
3.1.2 A solution is where hyperplanes intersect
3.1.3 Section 3.1 summary
3.2 Overspecified and underspecified systems
3.2.1 Overspecified systems
3.2.2 Underspecified systems
3.2.3 Section 3.2 summary
3.3 A visual example of an interactive linear solver
3.3.1 The basic principle of iteration
3.3.2 Starting point and exit conditions
3.3.3 Convergence and stability
3.3.4 Section 3.3 summary
3.4 Direct solver
3.4.1 Turning an iterative solver into a direct one
3.4.2 Algorithm complexity
3.4.3 Section 3.4 summary
3.5 Linear equations system as matrix multiplication
3.5.1 Matrix equations
3.5.2 What types of matrices we should know about
3.5.3 Things we’re allowed to do with equations
3.5.4 Section 3.5 summary
3.6 Solving linear systems with Gaussian elimination and LU-decomposition
3.6.1 An example of Gaussian elimination
3.6.2 What do “elimination” and “decomposition” mean?
3.6.3 Section 3.6 summary
3.7 Which solver fits my problem best?
3.7.1 When to use an elimination-based one
3.7.2 When to use an iterative one
3.7.3 When to use neither
3.7.4 Section 3.7 summary
3.8 Practical example: Does a ray hit a triangle?
3.8.1 The ray-triangle intersection problem
3.8.2 Forming a system
3.8.3 Making the equations into code
3.8.4 Section 3.8 summary
3.9 Exercises
3.10 Solutions to exercises
Summary
4 Projective geometric transformations
4.1 Some special cases of geometric transformations
4.1.1 Translation
4.1.2 Scaling
4.1.3 Rotation
4.1.4 Section 4.1 summary
4.2 Generalizations
4.2.1 Linear transformations in Euclidean space
4.2.2 Bundling rotation, scaling, and translation in a single affine transformation
4.2.3 Generalizing affine transformations to projective transformations
4.2.4 An alternative to projective transformations
4.2.5 Section 4.2 summary
4.3 Projective space and homogeneous coordinates
4.3.1 Expanding the whole space with homogeneous coordinates
4.3.2 Making all the transformations a single matrix multiplication: Why?
4.3.3 Section 4.3 summary
4.4 Practical examples
4.4.1 Scanning with a phone
4.4.2 Does a point belong to a triangle?
4.4.3 Section 4.4 summary
4.5 Exercises
4.6 Solutions to exercises
Summary
5 The geometry of calculus
5.1 What is a derivative?
5.1.1 Derivative at a point
5.1.2 Derivative as a function
5.1.3 Rules of differentiation
5.1.4 Using SymPy to do differentiation
5.1.5 Section 5.1 summary
5.2 Smooth piecewise parametric curves
5.2.1 Piecewise functions
5.2.2 Smooth parametric curves
5.2.3 Curvature
5.2.4 Section 5.2 summary
5.3 Practical example: Crafting a curve out of lines and circles
5.3.1 The biarc building block
5.3.2 The line segment and arc building block
5.3.3 The combination of both
5.3.4 Section 5.3 summary
5.4 Exercises
5.5 Solutions to exercises
Summary
6 Polynomial approximation and interpolation
6.1 What are polynomials?
6.1.1 Axis intersections and roots of polynomial equations
6.1.2 Polynomial derivatives
6.1.3 Section 6.1 summary
6.2 Polynomial approximation
6.2.1 Maclaurin and Taylor series
6.2.2 The method of least squares
6.2.3 Practical example: Showing a trend with approximation
6.2.4 Section 6.2 summary
6.3 Polynomial interpolation
6.3.1 Using Vandermonde matrix to get the interpolating polynomial
6.3.2 What limits polynomial interpolation application to small data only?
6.3.3 How to lessen unwanted oscillations
6.3.4 Lagrange interpolation: Simple, genius, unnecessary
6.3.5 Practical example: Showing the trend with interpolation
6.3.6 Section 6.3 summary
6.4 Practical example: Showing a trend with both approximation and interpolation
6.4.1 The problem
6.4.2 The solution
6.4.3 Section 6.4 summary
6.5 Exercises
6.6 Solutions to exercises
Summary
7 Splines
7.1 Going beyond the interpolation
7.1.1 Making polynomial graphs with tangent constraints
7.1.2 Practical example: Approximating the sine function for a space simulator game
7.1.3 Unexpected fact: Explicit polynomial modeling generalizes power series
7.1.4 Section 7.1 summary
7.2 Understanding polynomial splines and Bézier curves
7.2.1 Explicit polynomial parametric curves
7.2.2 Practical example: Crafting a spline for points that aren’t there yet
7.2.3 Bézier curves
7.2.4 Section 7.2 summary
7.3 Understanding NURBS
7.3.1 BS stands for “basis spline”
7.3.2 NU stands for “nonuniform”
7.3.3 R stands for “rational”
7.3.4 Not-so-practical example: Building a circle with NURBS
7.3.5 Section 7.3 summary
7.4 Exercises
7.5 Solutions to exercises
Summary
8 Nonlinear transformations and surfaces
8.1 Polynomial transformations in multidimensional space
8.1.1 The straightforward approach to polynomial transformations
8.1.2 The fast and simple approach to polynomial transformations
8.1.3 Practical example: Adding the “unbending” feature to the scanning app
8.1.4 Section 8.1 summary
8.2 3D surface modeling
8.2.1 A surface is just a 3D transformation of a plane
8.2.2 Practical example: Planting polynomial mushrooms
8.2.3 Section 8.2 summary
8.3 Using nonpolynomial spatial interpolation in geometry
8.3.1 Inverse distance interpolation
8.3.2 Inverse distance interpolation in space
8.3.3 Practical example: Using localized inverse distance method to make a bitmap continuous and smooth
8.3.4 Practical example: Building a deformation field with multivariable interpolation to generate better mushrooms
8.3.5 Section 8.3 summary
8.4 Exercises
8.5 Solutions to exercises
Summary
9 The geometry of vector algebra
9.1 Vector addition and scalar multiplication as transformations
9.2 Dot product: Projection and angle
9.2.1 Other names and motivations behind them
9.2.2 Vectors and their dot product in SymPy
9.2.3 Practical example: Using a dot product to light a scene
9.2.4 Section 9.2 summary
9.3 Cross product: Normal vector and the parallelogram area
9.3.1 Other names and motivations behind them
9.3.2 The cross product in SymPy
9.3.3 Practical example: Check whether a triangle contains a point in 2D
9.3.4 Section 9.3 summary
9.4 Triple product: The parallelepiped volume
9.4.1 The geometric sense of the triple product
9.4.2 The triple product in SymPy
9.4.3 Practical example: Distance to a plane
9.4.4 Section 9.4 summary
9.5 Generalization for parallelotopes
9.5.1 The meaning
9.5.2 The math
9.5.3 The code
9.5.4 Section 9.5 summary
9.6 Exercises
9.7 Solutions to exercises
Summary
10 Modeling shapes with signed distance functions and surrogates
10.1 What’s an SDF?
10.1.1 Does it have to be an SDF?
10.1.2 How to program SDFs?
10.1.3 Theoretical example: Making an SDF of a triangle mesh
10.1.4 Practical example: Making an SDF of a rectangle in 2D
10.1.5 Section 10.1 summary
10.2 How to work with SDFs
10.2.1 How to translate, rotate, or scale an SDF
10.2.2 How to unite, intersect, and subtract SDFs
10.2.3 How to dilate and erode an SDF
10.2.4 How to hollow an SDF
10.2.5 Section 10.2 summary
10.3 Some techniques of not-really-SDF implicit modeling
10.3.1 Tri-periodic minimal surfaces
10.3.2 Practical example: A gyroid with variable thickness
10.3.3 Metaballs
10.3.4 Practical example: Localizing the metaballs for speed and better governance
10.3.5 Multifocal lemniscates
10.3.6 Practical example: A play button made of a multifocal lemniscate
10.3.7 Section 10.3 summary
10.4 Exercises
10.5 Solutions to exercises
Summary
11 Modeling surfaces with boundary representations and triangle meshes
11.1 Smooth curves and surfaces
11.1.1 Data representation
11.1.2 Operations are also data
11.1.3 Section 11.1 summary
11.2 Segments and triangles
11.2.1 Vertices and triangles vs. the half-edge representation
11.2.2 Pros and cons of triangle meshes
11.2.3 Section 11.2 summary
11.3 Practical example: Contouring with marching cubes and dual contouring algorithms
11.3.1 Marching cubes
11.3.2 Dual contouring
11.3.3 Is it that simple in practice, too?
11.3.4 Section 11.3 summary
11.4 Practical example: Smooth contouring
11.4.1 The algorithm
11.4.2 The implementation
11.4.3 Section 11.4 summary
11.5 Exercises
11.6 Solutions to exercises
Summary
12 Modeling bodies with images and voxels
12.1 How does computed tomography work?
12.2 Segmentation by a threshold
12.3 Typical operations on 3D images: Dilation, erosion, cavity fill, and Boolean
12.3.1 Dilation
12.3.2 Erosion
12.3.3 Practical example: Denoising
12.3.4 Boolean operations on voxel models
12.3.5 A few other uses of dilation and erosion
12.3.6 Section 12.3 summary
12.4 Practical example: Image vectorization
12.4.1 Input image
12.4.2 Step 1: Obtain a contour
12.4.3 Step 2: Fit the contour
12.4.4 Step 3: Make the contour smooth
12.4.5 Implementation
12.4.6 Section 12.4 summary
12.5 How voxels, triangles, parametric surfaces, and SDFs work together
12.6 Exercises
12.7 Solutions to exercises
Summary
Appendix—Sources, references, and further reading
Books
Papers
Websites
Interactive web pages
index
Symbols
Numerics
A
B
C
D
E
F
G
H
I
L
M
N
O
P
Q
R
S
T
U
V
W