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