book

Geometry for Programmers

Name: Geometry for Programmers
Author: Oleksandr Kaleniuk
ISBN: 9781633439603

by Oleksandr Kaleniuk

May 2023

Beginner to intermediate

440 pages

12h 55m

English

Manning Publications

Read now

Unlock full access

inside front cover
Geometry for Programmers
Copyright
contents
front matter
prefaceacknowledgmentsabout this bookWho should read this bookHow this book is organizedAbout the codeliveBook discussion forumabout the authorabout 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 start1.6 SymPy will do your math for youSummary
2 Terminology and jargon
2.1 Numbers, points, and vectors2.1.1 Numbers2.1.2 Vectors2.1.3 Section 2.1 summary2.2 Vertices and triangles2.2.1 Being pedantic about triangles2.2.2 Triangle quality2.2.3 Section 2.2 summary2.3 Lines, planes, and their equations2.3.1 Lines and planes2.3.2 The parametric form for 3D lines2.3.3 Section 2.3 summary2.4 Functions and geometric transformations2.4.1 What is a function?2.4.2 Function types most commonly used in geometric modeling2.4.3 Section 2.4 summary2.5 The shortest possible introduction to matrix algebra2.5.1 What is algebra?2.5.2 How does matrix algebra work?2.5.3 Section 2.5 summary2.6 Exercises2.7 Solutions to exercisesSummary
3 The geometry of linear equations
3.1 Linear equations as lines and planes3.1.1 Introducing a hyperplane3.1.2 A solution is where hyperplanes intersect3.1.3 Section 3.1 summary3.2 Overspecified and underspecified systems3.2.1 Overspecified systems3.2.2 Underspecified systems3.2.3 Section 3.2 summary3.3 A visual example of an interactive linear solver3.3.1 The basic principle of iteration3.3.2 Starting point and exit conditions3.3.3 Convergence and stability3.3.4 Section 3.3 summary3.4 Direct solver3.4.1 Turning an iterative solver into a direct one3.4.2 Algorithm complexity3.4.3 Section 3.4 summary3.5 Linear equations system as matrix multiplication3.5.1 Matrix equations3.5.2 What types of matrices we should know about3.5.3 Things we’re allowed to do with equations3.5.4 Section 3.5 summary3.6 Solving linear systems with Gaussian elimination and LU-decomposition3.6.1 An example of Gaussian elimination3.6.2 What do “elimination” and “decomposition” mean?3.6.3 Section 3.6 summary3.7 Which solver fits my problem best?3.7.1 When to use an elimination-based one3.7.2 When to use an iterative one3.7.3 When to use neither3.7.4 Section 3.7 summary3.8 Practical example: Does a ray hit a triangle?3.8.1 The ray-triangle intersection problem3.8.2 Forming a system3.8.3 Making the equations into code3.8.4 Section 3.8 summary3.9 Exercises3.10 Solutions to exercisesSummary
4 Projective geometric transformations
4.1 Some special cases of geometric transformations4.1.1 Translation4.1.2 Scaling4.1.3 Rotation4.1.4 Section 4.1 summary4.2 Generalizations4.2.1 Linear transformations in Euclidean space4.2.2 Bundling rotation, scaling, and translation in a single affine transformation4.2.3 Generalizing affine transformations to projective transformations4.2.4 An alternative to projective transformations4.2.5 Section 4.2 summary4.3 Projective space and homogeneous coordinates4.3.1 Expanding the whole space with homogeneous coordinates4.3.2 Making all the transformations a single matrix multiplication: Why?4.3.3 Section 4.3 summary4.4 Practical examples4.4.1 Scanning with a phone4.4.2 Does a point belong to a triangle?4.4.3 Section 4.4 summary4.5 Exercises4.6 Solutions to exercisesSummary
5 The geometry of calculus
5.1 What is a derivative?5.1.1 Derivative at a point5.1.2 Derivative as a function5.1.3 Rules of differentiation5.1.4 Using SymPy to do differentiation5.1.5 Section 5.1 summary5.2 Smooth piecewise parametric curves5.2.1 Piecewise functions5.2.2 Smooth parametric curves5.2.3 Curvature5.2.4 Section 5.2 summary5.3 Practical example: Crafting a curve out of lines and circles5.3.1 The biarc building block5.3.2 The line segment and arc building block5.3.3 The combination of both5.3.4 Section 5.3 summary5.4 Exercises5.5 Solutions to exercisesSummary

6 Polynomial approximation and interpolation
6.1 What are polynomials?6.1.1 Axis intersections and roots of polynomial equations6.1.2 Polynomial derivatives6.1.3 Section 6.1 summary6.2 Polynomial approximation6.2.1 Maclaurin and Taylor series6.2.2 The method of least squares6.2.3 Practical example: Showing a trend with approximation6.2.4 Section 6.2 summary6.3 Polynomial interpolation6.3.1 Using Vandermonde matrix to get the interpolating polynomial6.3.2 What limits polynomial interpolation application to small data only?6.3.3 How to lessen unwanted oscillations6.3.4 Lagrange interpolation: Simple, genius, unnecessary6.3.5 Practical example: Showing the trend with interpolation6.3.6 Section 6.3 summary6.4 Practical example: Showing a trend with both approximation and interpolation6.4.1 The problem6.4.2 The solution6.4.3 Section 6.4 summary6.5 Exercises6.6 Solutions to exercisesSummary
7 Splines
7.1 Going beyond the interpolation7.1.1 Making polynomial graphs with tangent constraints7.1.2 Practical example: Approximating the sine function for a space simulator game7.1.3 Unexpected fact: Explicit polynomial modeling generalizes power series7.1.4 Section 7.1 summary7.2 Understanding polynomial splines and Bézier curves7.2.1 Explicit polynomial parametric curves7.2.2 Practical example: Crafting a spline for points that aren’t there yet7.2.3 Bézier curves7.2.4 Section 7.2 summary7.3 Understanding NURBS7.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 NURBS7.3.5 Section 7.3 summary7.4 Exercises7.5 Solutions to exercisesSummary
8 Nonlinear transformations and surfaces
8.1 Polynomial transformations in multidimensional space8.1.1 The straightforward approach to polynomial transformations8.1.2 The fast and simple approach to polynomial transformations8.1.3 Practical example: Adding the “unbending” feature to the scanning app8.1.4 Section 8.1 summary8.2 3D surface modeling8.2.1 A surface is just a 3D transformation of a plane8.2.2 Practical example: Planting polynomial mushrooms8.2.3 Section 8.2 summary8.3 Using nonpolynomial spatial interpolation in geometry8.3.1 Inverse distance interpolation8.3.2 Inverse distance interpolation in space8.3.3 Practical example: Using localized inverse distance method to make a bitmap continuous and smooth8.3.4 Practical example: Building a deformation field with multivariable interpolation to generate better mushrooms8.3.5 Section 8.3 summary8.4 Exercises8.5 Solutions to exercisesSummary
9 The geometry of vector algebra
9.1 Vector addition and scalar multiplication as transformations9.2 Dot product: Projection and angle9.2.1 Other names and motivations behind them9.2.2 Vectors and their dot product in SymPy9.2.3 Practical example: Using a dot product to light a scene9.2.4 Section 9.2 summary9.3 Cross product: Normal vector and the parallelogram area9.3.1 Other names and motivations behind them9.3.2 The cross product in SymPy9.3.3 Practical example: Check whether a triangle contains a point in 2D9.3.4 Section 9.3 summary9.4 Triple product: The parallelepiped volume9.4.1 The geometric sense of the triple product9.4.2 The triple product in SymPy9.4.3 Practical example: Distance to a plane9.4.4 Section 9.4 summary9.5 Generalization for parallelotopes9.5.1 The meaning9.5.2 The math9.5.3 The code9.5.4 Section 9.5 summary9.6 Exercises9.7 Solutions to exercisesSummary
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 mesh10.1.4 Practical example: Making an SDF of a rectangle in 2D10.1.5 Section 10.1 summary10.2 How to work with SDFs10.2.1 How to translate, rotate, or scale an SDF10.2.2 How to unite, intersect, and subtract SDFs10.2.3 How to dilate and erode an SDF10.2.4 How to hollow an SDF10.2.5 Section 10.2 summary10.3 Some techniques of not-really-SDF implicit modeling10.3.1 Tri-periodic minimal surfaces10.3.2 Practical example: A gyroid with variable thickness10.3.3 Metaballs10.3.4 Practical example: Localizing the metaballs for speed and better governance10.3.5 Multifocal lemniscates10.3.6 Practical example: A play button made of a multifocal lemniscate10.3.7 Section 10.3 summary10.4 Exercises10.5 Solutions to exercisesSummary
11 Modeling surfaces with boundary representations and triangle meshes
11.1 Smooth curves and surfaces11.1.1 Data representation11.1.2 Operations are also data11.1.3 Section 11.1 summary11.2 Segments and triangles11.2.1 Vertices and triangles vs. the half-edge representation11.2.2 Pros and cons of triangle meshes11.2.3 Section 11.2 summary11.3 Practical example: Contouring with marching cubes and dual contouring algorithms11.3.1 Marching cubes11.3.2 Dual contouring11.3.3 Is it that simple in practice, too?11.3.4 Section 11.3 summary11.4 Practical example: Smooth contouring11.4.1 The algorithm11.4.2 The implementation11.4.3 Section 11.4 summary11.5 Exercises11.6 Solutions to exercisesSummary
12 Modeling bodies with images and voxels
12.1 How does computed tomography work?12.2 Segmentation by a threshold12.3 Typical operations on 3D images: Dilation, erosion, cavity fill, and Boolean12.3.1 Dilation12.3.2 Erosion12.3.3 Practical example: Denoising12.3.4 Boolean operations on voxel models12.3.5 A few other uses of dilation and erosion12.3.6 Section 12.3 summary12.4 Practical example: Image vectorization12.4.1 Input image12.4.2 Step 1: Obtain a contour12.4.3 Step 2: Fit the contour12.4.4 Step 3: Make the contour smooth12.4.5 Implementation12.4.6 Section 12.4 summary12.5 How voxels, triangles, parametric surfaces, and SDFs work together12.6 Exercises12.7 Solutions to exercisesSummary
Appendix. A Sources, references, and further reading
BooksPapersWebsitesInteractive web pages
index
inside back cover

Overview

Master the math behind CAD, game engines, GIS, and more! This hands-on book teaches you the geometry used to create simulations, 3D prints, and other models of the physical world.

In Geometry for Programmers you will learn how to:

Speak the language of applied geometry
Compose geometric transformations economically
Craft custom splines for efficient curves and surface generation
Pick and implement the right geometric transformations
Confidently use important algorithms that operate on triangle meshes, distance functions, and voxels

Geometry for Programmers guides you through the math behind graphics and modeling tools. It’s full of practical examples and clear explanations that make sense even if you don’t have a background in advanced math. You’ll learn how basic geometry can help you avoid code layering and repetition, and even how to drive down cloud hosting costs with more efficient runtimes. Cheerful language, charts, illustrations, equations, and Python code help make geometry instantly relevant to your daily work as a developer.

About the Technology
Geometry is at the heart of game engines, robotics, computer-aided design, GIS, and image processing. This book draws back what is for some a mathematical curtain, giving them insight and control over this central tool. You’ll quickly see how a little geometry can help you design realistic simulations, translate the physical world into code, and even reduce your cloud services bill by improving the efficiency of graphics-intensive applications.

About the Book
Geometry for Programmers is both practical and entertaining. Fun illustrations and engaging examples show you how to apply geometry to real programming problems, like changing a scan into a CAD model or developing 3D printing contours from a parametric function. And don’t worry if you aren’t a math expert. There’s no heavy theory, and you’ll learn how to offload most equations to the SymPy computer algebra system.

What's Inside

Speak the language of applied geometry
Compose geometric transformations economically
Craft custom splines for efficient curves and surface generation
Confidently use geometry algorithms

About the Reader
Examples are in Python, and all you need is high school–level math.

About the Author
Oleksandr Kaleniuk is the creator of Words and Buttons Online, a collection of interactive tutorials on math and programming.

Quotes
A one-of-a-kind book covering the practical applications of geometry in programming.
- Maxim Volgin, KLM

Have you ever wondered how game programmers, animators, and car manufacturers model visual reality? This book not only shows you how, it teaches you to understand and enhance the apps they use.
- Ranjit Sahai, RAM Consulting

An insightful tour of geometry using the powerful tool SymPy. You can get behind the scenes and apply these techniques to CAD and much more.
- James J. Byleckie, BH Enterprises

Approaches software development from a new angle!
- Chris Kardell, DEBS

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781633439603Publisher Support Publisher Website Errata Page

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills