Geometry for Programmers Version 7

Geometry for Programmers MEAP V07
Copyright
welcome
brief contents
Chapter 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 there forever, why learn it now?
	1.5 It is not a lot to know to get started
	1.6 Meet SymPy, it will do your math for you
	1.7 Summary
Chapter 2: Terminology and jargon
	2.1 Numbers, points, and vectors
		2.1.1 Numbers
		2.1.2 Points
		2.1.3 Vectors
		2.1.4 Summary
	2.2 Vertices and triangles
		2.2.1 Being pedantic with triangles
		2.2.2 Triangle quality
		2.2.3 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 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 Summary
		2.4.4 What is algebra?
		2.4.5 How does matrix algebra work?
		2.4.6 Summary
	2.5 Summary
	2.6 Exercises
	2.7 Solutions for exercises
Chapter 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 Summary
	3.2 Overspecified and underspecified systems
		3.2.1 Overspecified systems
		3.2.2 Underspecified systems
		3.2.3 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 Summary
	3.4 Direct solver
		3.4.1 Turning an iterative solver into a direct one
		3.4.2 Algorithm complexity
		3.4.3 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 Summary
	3.6 Solving linear systems with gaussian elimination and LU-decomposition
		3.6.1 An example
		3.6.2 What do “elimination” and “decomposition” mean exactly?
		3.6.3 Summary
	3.7 Which solver fits my problem the 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 Summary
	3.8 Practical example: does a ray hit a triangle?
		3.8.1 A problem
		3.8.2 Forming a system
		3.8.3 Making the equations into code
		3.8.4 Summary
	3.9 Summary
	3.10 Exercises
	3.11 Solutions for exercises
Chapter 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 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 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 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 Summary
	4.5 Summary
	4.6 Exercises
	4.7 Solutions for exercises
Chapter 5: 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 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 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 Summary
	5.4 Summary
	5.5 Exercises
	5.6 Solutions for exercises
Chapter 6: Polynomial approximation and interpolation
	6.1 What are polynomials?
		6.1.1 Axis intersections and roots of polynomial equations
		6.1.2 Odd and even polynomials
		6.1.3 Polynomial derivatives
		6.1.4 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 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 the unwanted oscillations?
		6.3.4 Lagrange interpolation. Simple, genius, unnecessary
		6.3.5 Practical example: showing the trend with interpolation
		6.3.6 Summary
	6.4 Practical example: showing a trend with a combination of approximation and interpolation
		6.4.1 The problem
		6.4.2 The solution
		6.4.3 Summary
	6.5 Summary
	6.6 Exercises
	6.7 Solutions for exercises
Chapter 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 Summary
	7.2 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.3 Understanding NURBS
		7.3.1 “BS” stands for “basis spline”
		7.3.2 “NU” stands for “non-uniform”
		7.3.3 “R” stands for “rational”
		7.3.4 Not so practical example: building a circle with NURBS
		7.3.5 Summary
	7.4 Summary
	7.5 Exercises
	7.6 Solutions for exercises
Chapter 8: Non-linear transformations and surfaces
	8.1 Polynomial transformations in multi-dimensional 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 Summary
	8.2 3D surfaces modeling
		8.2.1 A surface is just a 3D transformation of a plane
		8.2.2 Practical example: planting polynomial-revoluting mushrooms
		8.2.3 Summary
	8.3 Using non-polynomial spatial interpolation for building surfaces, transformations, and deformation fields
		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 multi-variable interpolation to generate better mushrooms
		8.3.5 Summary
	8.4 Summary
	8.5 Exercises
	8.6 Solutions for exercises
Chapter 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 dot product to light a scene
		9.2.4 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 if a triangle contains a point in 2D
		9.3.4 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 Summary
	9.5 Generalization for parallelotopes
		9.5.1 The meaning
		9.5.2 The math
		9.5.3 The code
		9.5.4 Summary
	9.6 Summary
	9.7 Exercises
	9.8 Solutions for exercises
Chapter 10: Modeling shapes with signed distance functions and alikes
	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 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 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 Summary
	10.4 Summary
	10.5 Exercises
	10.6 Solutions for exercises