Geometry for Programmers

By Oleksandr Kaleniuk

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.

Table of Contents

1 Getting started
2 Terminology and jargon
3 The geometry of linear equations
4 Projective geometric transformations
5 The geometry of calculus
6 Polynomial approximation and interpolation
7 Splines
8 Nonlinear transformations and surfaces
9 The geometry of vector algebra
10 Modeling shapes with signed distance functions and surrogates
11 Modeling surfaces with boundary representations and triangle meshes
12 Modeling bodies with images and voxels

• Language: English
• Publisher: Manning
• Release date: Jun 20, 2023
• ISBN: 9781638351924

Oleksandr Kaleniuk

Oleksandr Kaleniuk is the creator of Words and Buttons Online, a collection of interactive tutorials on math and programming. He works for Materialise as a senior software engineer specializing in geometric algorithms.

Book preview

inside front cover

Geometry for Programmers

Oleksandr Kaleniuk

To comment go to liveBook

Manning

Shelter Island

For more information on this and other Manning titles go to

www.manning.com

Copyright

For online information and ordering of these  and other Manning books, please visit www.manning.com. The publisher offers discounts on these books when ordered in quantity.

For more information, please contact

Special Sales Department

Manning Publications Co.

20 Baldwin Road

PO Box 761

Shelter Island, NY 11964

Email: [e-mail]

©2023 by Manning Publications Co. All rights reserved.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by means electronic, mechanical, photocopying, or otherwise, without prior written permission of the publisher.

Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in the book, and Manning Publications was aware of a trademark claim, the designations have been printed in initial caps or all caps.

♾ Recognizing the importance of preserving what has been written, it is Manning’s policy to have the books we publish printed on acid-free paper, and we exert our best efforts to that end. Recognizing also our responsibility to conserve the resources of our planet, Manning books are printed on paper that is at least 15 percent recycled and processed without the use of elemental chlorine.

ISBN: 9781633439603

contents

front matter

preface

acknowledgments

about this book

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

2 Terminology and jargon

2.1 Numbers, points, and vectors

Numbers

Vectors

Section 2.1 summary

2.2 Vertices and triangles

Being pedantic about triangles

Triangle quality

Section 2.2 summary

2.3 Lines, planes, and their equations

Lines and planes

The parametric form for 3D lines

Section 2.3 summary

2.4 Functions and geometric transformations

What is a function?

Function types most commonly used in geometric modeling

Section 2.4 summary

2.5 The shortest possible introduction to matrix algebra

What is algebra?

How does matrix algebra work?

Section 2.5 summary

2.6 Exercises

2.7 Solutions to exercises

3 The geometry of linear equations

3.1 Linear equations as lines and planes

Introducing a hyperplane

A solution is where hyperplanes intersect

Section 3.1 summary

3.2 Overspecified and underspecified systems

Overspecified systems

Underspecified systems

Section 3.2 summary

3.3 A visual example of an interactive linear solver

The basic principle of iteration

Starting point and exit conditions

Convergence and stability

Section 3.3 summary

3.4 Direct solver

Turning an iterative solver into a direct one

Algorithm complexity

Section 3.4 summary

3.5 Linear equations system as matrix multiplication

Matrix equations

What types of matrices we should know about

Things we’re allowed to do with equations

Section 3.5 summary

3.6 Solving linear systems with Gaussian elimination and LU-decomposition

An example of Gaussian elimination

What do elimination and decomposition mean?

Section 3.6 summary

3.7 Which solver fits my problem best?

When to use an elimination-based one

When to use an iterative one

When to use neither

Section 3.7 summary

3.8 Practical example: Does a ray hit a triangle?

The ray-triangle intersection problem

Forming a system

Making the equations into code

Section 3.8 summary

3.9 Exercises

3.10 Solutions to exercises

4 Projective geometric transformations

4.1 Some special cases of geometric transformations

Translation

Scaling

Rotation

Section 4.1 summary

4.2 Generalizations

Linear transformations in Euclidean space

Bundling rotation, scaling, and translation in a single affine transformation

Generalizing affine transformations to projective transformations

An alternative to projective transformations

Section 4.2 summary

4.3 Projective space and homogeneous coordinates

Expanding the whole space with homogeneous coordinates

Making all the transformations a single matrix multiplication: Why?

Section 4.3 summary

4.4 Practical examples

Scanning with a phone

Does a point belong to a triangle?

Section 4.4 summary

4.5 Exercises

4.6 Solutions to exercises

5 The geometry of calculus

5.1 What is a derivative?

Derivative at a point

Derivative as a function

Rules of differentiation

Using SymPy to do differentiation

Section 5.1 summary

5.2 Smooth piecewise parametric curves

Piecewise functions

Smooth parametric curves

Curvature

Section 5.2 summary

5.3 Practical example: Crafting a curve out of lines and circles

The biarc building block

The line segment and arc building block

The combination of both

Section 5.3 summary

5.4 Exercises

5.5 Solutions to exercises

6 Polynomial approximation and interpolation

6.1 What are polynomials?

Axis intersections and roots of polynomial equations

Polynomial derivatives

Section 6.1 summary

6.2 Polynomial approximation

Maclaurin and Taylor series

The method of least squares

Practical example: Showing a trend with approximation

Section 6.2 summary

6.3 Polynomial interpolation

Using Vandermonde matrix to get the interpolating polynomial

What limits polynomial interpolation application to small data only?

How to lessen unwanted oscillations

Lagrange interpolation: Simple, genius, unnecessary

Practical example: Showing the trend with interpolation

Section 6.3 summary

6.4 Practical example: Showing a trend with both approximation and interpolation

The problem

The solution

Section 6.4 summary

6.5 Exercises

6.6 Solutions to exercises

7 Splines

7.1 Going beyond the interpolation

Making polynomial graphs with tangent constraints

Practical example: Approximating the sine function for a space simulator game

Unexpected fact: Explicit polynomial modeling generalizes power series

Section 7.1 summary

7.2 Understanding polynomial splines and Bézier curves

Explicit polynomial parametric curves

Practical example: Crafting a spline for points that aren’t there yet

Bézier curves

Section 7.2 summary

7.3 Understanding NURBS

BS stands for basis spline

NU stands for nonuniform

R stands for rational

Not-so-practical example: Building a circle with NURBS

Section 7.3 summary

7.4 Exercises

7.5 Solutions to exercises

8 Nonlinear transformations and surfaces

8.1 Polynomial transformations in multidimensional space

The straightforward approach to polynomial transformations

The fast and simple approach to polynomial transformations

Practical example: Adding the unbending feature to the scanning app

Section 8.1 summary

8.2 3D surface modeling

A surface is just a 3D transformation of a plane

Practical example: Planting polynomial mushrooms

Section 8.2 summary

8.3 Using nonpolynomial spatial interpolation in geometry

Inverse distance interpolation

Inverse distance interpolation in space

Practical example: Using localized inverse distance method to make a bitmap continuous and smooth

Practical example: Building a deformation field with multivariable interpolation to generate better mushrooms

Section 8.3 summary

8.4 Exercises

8.5 Solutions to exercises

9 The geometry of vector algebra

9.1 Vector addition and scalar multiplication as transformations

9.2 Dot product: Projection and angle

Other names and motivations behind them

Vectors and their dot product in SymPy

Practical example: Using a dot product to light a scene

Section 9.2 summary

9.3 Cross product: Normal vector and the parallelogram area

Other names and motivations behind them

The cross product in SymPy

Practical example: Check whether a triangle contains a point in 2D

Section 9.3 summary

9.4 Triple product: The parallelepiped volume

The geometric sense of the triple product

The triple product in SymPy

Practical example: Distance to a plane

Section 9.4 summary

9.5 Generalization for parallelotopes

The meaning

The math

The code

Section 9.5 summary

9.6 Exercises

9.7 Solutions to exercises

10 Modeling shapes with signed distance functions and surrogates

10.1 What’s an SDF?

Does it have to be an SDF?

How to program SDFs?

Theoretical example: Making an SDF of a triangle mesh

Practical example: Making an SDF of a rectangle in 2D

Section 10.1 summary

10.2 How to work with SDFs

How to translate, rotate, or scale an SDF

How to unite, intersect, and subtract SDFs

How to dilate and erode an SDF

How to hollow an SDF

Section 10.2 summary

10.3 Some techniques of not-really-SDF implicit modeling

Tri-periodic minimal surfaces

Practical example: A gyroid with variable thickness

Metaballs

Practical example: Localizing the metaballs for speed and better governance

Multifocal lemniscates

Practical example: A play button made of a multifocal lemniscate

Section 10.3 summary

10.4 Exercises

10.5 Solutions to exercises

11 Modeling surfaces with boundary representations and triangle meshes

11.1 Smooth curves and surfaces

Data representation

Operations are also data

Section 11.1 summary

11.2 Segments and triangles

Vertices and triangles vs. the half-edge representation

Pros and cons of triangle meshes

Section 11.2 summary

11.3 Practical example: Contouring with marching cubes and dual contouring algorithms

Marching cubes

Dual contouring

Is it that simple in practice, too?

Section 11.3 summary

11.4 Practical example: Smooth contouring

The algorithm

The implementation

Section 11.4 summary

11.5 Exercises

11.6 Solutions to exercises

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

Dilation

Erosion

Practical example: Denoising

Boolean operations on voxel models

A few other uses of dilation and erosion

Section 12.3 summary

12.4 Practical example: Image vectorization

Input image

Step 1: Obtain a contour

Step 2: Fit the contour

Step 3: Make the contour smooth

Implementation

Section 12.4 summary

12.5 How voxels, triangles, parametric surfaces, and SDFs work together

12.6 Exercises

12.7 Solutions to exercises

appendix A Sources, references, and further reading

index

front matter

preface

I wasn’t even going to write this book. Well, I do enjoy speaking at programmers’ events, and I do like writing about geometry, especially online, where I can add interactive widgets instead of still illustrations. But a whole book? Aren’t there enough geometry books already? Does anybody read them anyway?

But then I had a chat with Michael Stephens, an associate publisher at Manning, and he convinced me that first of all, people do read books—even the hard ones, even books on the most sophisticated or obscure topics. Second, there’s a specific interest in a book explaining geometrical concepts to practicing programmers. Programmers will read a book about the geometry but there’s a catch: it has to be a good book.

What makes a good Something for Programmers book? Three things:

The book has to be applicable. One should be able to easily try out the explained concepts in practice.

The book has to be approachable. Modern geometry relies heavily on algebra and calculus, and contrary to the popular belief from the 1970s, not every computer programmer is automatically good at math.

The book has to be concise. The programmer’s time is valuable.

To make the book applicable, I gathered a list of practical examples from my own practice and from popular interview questions. Although I write mostly in C++ professionally, I present the source-code samples in Python solely for ease of trying them.

To make the book approachable, I delegated all the tedious math work to SymPy, a Python library that does your algebra and calculus for you. I also introduced some algebra and calculus in the book, but briefly. You don’t have to spend months in training to become good at moving xs and ys around; SymPy, which you can learn in 15 minutes, will take care of that.

To make the book concise, or to let myself be brief with the explanations, I gathered a list of interactive tutorials online and placed references to them all over the book. Now if you find my version of the explanation for something too brief, you can usually find a more detailed version in a nearby reference. Don’t get me wrong: I believe in brief explanations, but I believe in interactive experiences more.

So the book you’re looking at is the product of several major design decisions, some of which may appear to be controversial. A hardcore mathematician, for example, might object to using SymPy instead of pen and paper, because that would be cheating. A hardcore programmer, on the other hand, might object to using Python as a language of examples because mathematical code belongs to Fortran and C++. I recognize these objections as being well justified. The goal of this book, however, is not to be a flawless piece of art, but to help you to get good at geometry. And sometimes, as you’ll see in chapter 11, cutting corners is a valid, desirable strategy for achieving your goal.

acknowledgments

First, I want to thank all the people from Manning who were involved with the book, but especially Elesha Hyde, my wonderful development editor, and Jerry Kuch, and Alain Couniot, who did technical editing and proofing. Thank you for believing in this book, for your everlasting enthusiasm and dedication, and for the hard work that followed.

I also want to thank James Cooper, Tim Biddington, and Volodymyr Anokhin, who were incredibly helpful with their feedback. Thank you for both your support and your honesty. Also, I thank all the reviewers: Aidan Twomey, Andrey Solodov, Anton Herzog, Christian Sutton, Christopher Kardell, Darrin Bishop, David Moskowitz, Dipkumar Patel, Fernando García Sedano, George Thomas, Hal Moroff, Hilde Van Gysel, Jean François Morin, Jedidiah Clemons-Johnson, Jens Hansen, Jeremy Chen, James J. Byleckie, John Guthrie, Jort Rodenburg, Jose San Leandro, Justin J. Vincent, Kent Spillner, Laud Bentil, Maciej Jurkowski, Manoj Reddy, Mark Graham, Mary Anne Thygesen, Matt Gukowsky, Maxim Volgin, Maxime Boillot, Megan Jones, Oliver Korten, Patrick Regan, V. V. Phansalkar, Ranjit Sahai, Rich Yonts, Rodney Weis, Ruben Gonzalez Rubio, Sadhana Ganapathiraju, Samuel Bosch, Sanjeev Kilarapu, Sergio Govoni, Sriram Macharla, Sujith Surendranathan Pillai, Tam Thanh Nguyen, Teresa Abreu, Theo Despoudis, Tim van Deurzen, Vidhya Vinay, Werner Nindl, and Zbigniew Curylo. Your suggestions helped make this book better.

I want to thank my friends, family members, and colleagues for their patience and understanding. For completely unrelated reasons, this period has been a difficult one for all of us, and I’m deeply sorry if I couldn’t be with you when you needed me most.

Last but not least, I want to thank the armed forces of Ukraine for keeping me, my friends, my family, and my colleagues safe and alive during the past year. Yes, there’s a saying that the greatest books are written by dead people, but I don’t think that this rule applies to technical literature.

about this book

Geometry for Programmers explains the geometry behind video games, computer-aided design (CAD) applications, 3D-printing software, geoinformation systems, virtual and augmented reality, computer vision, computed tomography, and so on. It concerns curves, surfaces, 3D objects, object spatial positioning, object spatial transformations, and several models to represent geometrical data, each with its pros and cons.

Who should read this book

You should read this book if you work with a game engine, a CAD framework, or a 3D-printing software development kit and want to know the math behind your tools of the trade to use them more efficiently. If you want to develop such tools, you should read much more than one book, but this one might be a good start.

How this book is organized

The book consists of 12 chapters:

Chapter 1 shows the relationship between geometry and programming: which programming domains rely on geometry and which part of geometry applies to programming. The chapter showcases SymPy as a tool to do our math for us and provides a brief but good-enough-to-get-started tutorial.

Chapter 2 teaches the basic language of applied geometry, including terms such as near-degenerate triangle, nonmanifold mesh, and continuous transformation.

Chapter 3 discusses linear systems as though they are systems of lines, planes, and hyperplanes. The chapter shows the conditions in which such systems have computable solutions and provides practical guidance on choosing the best algorithm for the job.

Chapter 4 explains how the most common geometric transformation—such as rotation, scale, and translation—are generalized and extended by projective transformation. The chapter also introduces the concept of homogeneous coordinates and explains how using them simplifies programming in practice.

Chapter 5 shows how calculus is connected to the geometric properties of curves and surfaces. The chapter also explains how to use these properties to program curves and surfaces.

Chapter 6 introduces polynomials as a kind of digital clay—a building material for arbitrary functions with requested properties. The chapter also discusses the downsides of polynomial modeling and ways to mitigate them.

Chapter 7 teaches how to craft custom curves with splines. The chapter explains the general idea of splines and proposes a few well-known approaches, such as Bézier splines and NURBS. It also gives you the necessary tool set to design your own polynomial splines with the specific properties you want.

Chapter 8 expands on the discussion of projective transformations in chapter 4, introducing nonlinear transformations. The chapter also shows how to build and modify surfaces with such transformations.

Chapter 9 introduces the basics of vector algebra from the geometric perspective. The chapter explains how vector products work, how they generalize, and how to use their geometric properties to solve real-world problems.

Chapter 10 teaches about signed distance functions as one possible way to represent geometrical data. The chapter presents both the benefits and the drawbacks, explaining how to create a signed distance function from a contour of a triangle mesh and how to do Boolean operations, offsets, and transformations on these functions as though they were geometric objects.

Chapter 11 discusses more popular ways to represent geometric bodies. Like the preceding chapter, chapter 11 discuss benefits, drawbacks, common operations, and conversion techniques for boundary representations and triangle meshes.

Chapter 12 showcases modeling bodies with 3D images and voxels. The chapter also discusses common operations for this representation, along with conversion techniques.

The last three chapters should give you enough guidance to choose the best representation for your practical problem, whichever it might be.

The book progresses from purely theoretical material to the data representations and algorithms used in real-world applications. This progression is gradual, and later chapters rely heavily on earlier ones. I highly advise reading the chapters in their natural order, although if you’re already familiar with calculus, vector algebra, or linear systems, you can safely skip the pertinent chapters; they propose only alternative perspectives on the topics, not unique and exclusive material.

About the code

This book contains many examples of source code both in numbered listings and inline with normal text. In both cases, source code is formatted in a fixed-width font like this to separate it from ordinary text.

In many cases, the original source code has been reformatted; we’ve added line breaks and reworked indentation to accommodate the available page space in the book. In rare cases, even this was not enough, and listings include line-continuation markers (➥). Additionally, comments in the source code were often removed from the listings when the code is described in the text. Code annotations accompany many of the listings, highlighting important concepts.

As the book progresses from theory to applications, the code examples progress from SymPy snippets to full-fledged algorithms:

The SymPy snippets don’t produce any curves or surfaces. They produce formulas, or, alternatively, other snippets of code, this time in a language of your choice. More on that later.

The algorithmic examples do produce curves and surfaces, and as such, they need visualization. The specific details of visualization implementation aren’t important from the geometric standpoint, so in the book itself, all the visualization code is omitted. It exists only in the code examples that you download separately.

All the code is in Python. There are no specific dependencies on modern Python features or obscure libraries, so any generic 3.x Python will do. There are no specific hardware requirements, either.

You can get executable snippets of code from the liveBook (online) version of this book at https://livebook.manning.com/book/geometry-for-programmers. The complete code for the examples in the book is available for download from the Manning website at https://www.manning.com/books/geometry-for-programmers and from GitHub at https://github.com/akalenuk/geometry-for-programmers-code.

liveBook discussion forum

Purchase of Geometry for Programmers includes free access to liveBook, Manning’s online reading platform. Using liveBook’s exclusive discussion features, you can attach comments to the book globally or to specific sections or paragraphs. It’s a snap to make notes for yourself, ask and answer technical questions, and receive help from the author and other users. To access the forum, go to https://livebook.manning.com/book/geometry-for-programmers/discussion. You can also learn more about Manning’s forums and the rules of conduct at https://livebook.manning.com/discussion.

Manning’s commitment to our readers is to provide a venue where meaningful dialogue between individual readers and between readers and the author can take place. It isn’t a commitment to any specific amount of participation on the part of the author, whose contribution to the forum remains voluntary (and unpaid). We suggest that you try asking the author some challenging questions lest his interest stray! The forum and the archives of previous discussions will be accessible on the publisher’s website as long as the book is in print.

about the author

Kaleniuk

Oleksandr Kaleniuk

is the creator of Words and Buttons Online, a collection of interactive tutorials on math and programming. He works for Materialise NV as a senior software engineer specializing in geometric algorithms.

about the cover illustration

The figure on the cover of Geometry for Programmers is Femme de l’isle de Naxia, or Woman of Naxos Island, taken from a collection by Jacques Grasset de Saint-Sauveur, published in 1788. Each illustration is finely drawn and colored by hand.

In those days, it was easy to identify where people lived and what their trade or station in life was by their dress alone. Manning celebrates the inventiveness and initiative of the computer business with book covers based on the rich diversity of regional culture centuries ago, brought back to life by pictures from collections such as this one.

1 Getting started

This chapter covers

Which programming domains rely on geometry

Which part of geometry applies to programming

The reason to start learning geometry today

What you need to know to get started

How to make SymPy do the math for you

Geometry is the branch of mathematics that stands behind game engines, computer-aided design applications, 3D printing frameworks, image processing libraries, and geographic information systems. As soon as there are curves, surfaces, or spaces, geometry is involved.

Normally, you don’t have to be a geometry expert to use an application with curves and surfaces. Don’t worry; this book won’t convert you to one. But just as knowing the mechanics behind your car allows you to make the most of driving it, knowing the mathematics behind your tools will allow you to use them in the most efficient way possible.

How much geometry do you have to know to 3D-print a single model, for example? Well, none; you can figure out how to do that with trial and error. But what if you want to automate a 3D printing process for a continuous flow of models? This task is a programmer’s job, and it brings in programmer considerations. You want your process to be both fast and robust. Every failed printing attempt means that you lose time and money, so trial and error simply won’t cut it.

Normally, to print a model that came from computer-aided design (CAD) software, you need to convert the source model from smooth surfaces to triangles with a special library, ensure that the triangulated model is printable with an analysis algorithm, and turn the model into a list of contours with a slicing function. Only then you can start an actual printing machine. Each part of the process that precedes clicking a switch on a 3D printing machine is geometry wrapped in programming (figure 1.1).

01-01

Figure 1.1 Left to right: A model made of smooth surfaces, the same model made of triangles, and the model made of stacked 2D contours

The most efficient surfaces-to-triangles conversion is one that produces something called a manifold mesh with no need for postprocessing correction. You can rely on automatic algorithms to figure out the process, of course, but you often get better results with manual control. The only downside is that to have this control, you have to understand what on Earth a manifold mesh is.

The algorithms that make meshes printable don’t necessarily guarantee that the resulting triangles will be high-quality. Certainly, you can increase quality afterward, but you have to know how to assess quality and identify the algorithms that rely on it.

Turning a model into a stack of printable contours is an operation that takes time and can introduce errors. If it takes too long, can you trade some precision for speed? You can, but to do so, you have to know your mesh-reducing algorithms.

So although it’s possible to work with modern software without having any considerable knowledge of geometry, every little thing you learn makes you more efficient in your job one way or another. 3D printing is only one example; the same goes for design automation, game programming, image processing, and so on.

1.1 Which parts of programming require geometry?

I’ve already mentioned a few domains that require geometry—game engines, CAD frameworks, and 3D printing toolkits—but the list doesn’t end there. Virtual reality, augmented reality, computer vision systems, computer tomography, 2D graphics and animation, and data visualization all use the same mathematics (although in different quantities). The more you understand the mathematics, the more efficient you’ll be in using and writing code for all those tasks. Generally, knowing the math behind your tools makes you a better programmer in any relevant domain.

But that statement is only a truism. Let’s go through a couple of domains to see where geometry is and isn’t useful:

Game engines—In game engines, geometry is responsible mostly for object positioning, creating smooth transformations, rendering, and modeling physical interaction. Knowing geometry may not make you a better game designer, but programming visual effects in the most efficient way will make your game run smoothly on a wider range of gaming hardware.

Virtual/augmented reality—The situation is more complex in virtual or augmented reality, because now you need to adapt the rendering to each user and consider interactions with real-world objects. Not all these problems are geometric, of course. Rendering calibration for a virtual reality set, for example, is an interdisciplinary problem that involves optics, hardware design, anatomy, and even neurology. Some neurological conditions simply prevent users from following the calibration guides—and in this case, knowing geometry can’t possibly help.

CAD—In computer-aided design, the applied geometry is used for precise surface modeling, computing the intersections of surface-bound bodies, and turning these bodies into sets of small chunks for finite element analysis. Finite element analysis is a way to simulate the models’ physical properties programmatically, thereby saving time and money on real-world crash testing. The process isn’t geometrical per se—it has more to do with differential analysis and computation—but converting models from one representation to another and back is a purely geometrical problem.

3D printing—In 3D printing, geometry does everything but the printing itself: preparing the models, placing them efficiently on a printer’s platform, building the support structure to ensure that the build will succeed, and then turning all the data into a list of printer instructions. In this domain, material science (such as metallurgy for metal printing or plastics chemistry) is every bit as important as mathematics.

Image processing—In image processing, the applied geometry takes care of turning raw pixel data into smooth curves or surfaces, which is called segmentation, and positioning such objects in the image space, which is called registration. Transforming the images themselves and positioning them in space are also geometrical problems. But a lot of discrete mathematics involved aren’t related to geometry.

A topologist would say that because every set of objects and a set of relations between them constitute a topological space, relational databases and even source code are geometric objects. This understanding of geometry, however, is too broad to be practical. In this book, we’ll stay focused on curves, surfaces, and their transformations.

Geometry supports and enables many programming domains. It may not always be the first violin in an orchestra, but it’s often as integral and irreplaceable as a double bass.

1.2 What is geometry for programmers?

We all studied geometry in school. Geometry starts with lines and circles, rulers and compasses, and then moves on to axioms and theorems—lots of theorems. This kind of geometry, called axiomatic, is essentially mental calisthenics and unfortunately has little to do with programming (unless you’re programming an app that teaches axiomatic geometry to children).

Geometry meets programming only when it becomes analytic—when points acquire coordinates, curves and surfaces get their formulas. Even then, some pieces of geometry knowledge remain more relevant to programming than others. Special curves such as cochoid, cissoid, and trisectrix have little significance in modern engineering, for example, because you can model them all with a general thing such as a nonuniform rational basis spline (NURBS for short).

Don’t worry if these terms are unfamiliar. This book is designed to explain unfamiliar terms if you need them and omit them if you don’t. We’ll get back to NURBS in chapter 7, but from now on, you’ll never see those three special curves mentioned anywhere in this book or probably in your professional career.

Analytic geometry is tightly connected to linear algebra—so tightly that you can use geometric intuition to learn about linear systems (chapter 3) or vector algebra (chapter 9). To understand curves and surfaces, you also need a small fraction of calculus. Chapter 5 covers all that you have to know; it introduces derivatives as a pragmatic geometric and not some abstract analytical tool. Similarly, chapter 6 introduces polynomials, which represent the digital clay you’ll use later to sculpt curves and surfaces.

Speaking of curves and surfaces, chapter 7 introduces NURBS, which is currently the most popular tool for modeling curves and surfaces, and also explains the general approach to splines, allowing you to craft your own spline formulas tuned for the best possible performance.

Chapter 8 explains how to generate and deform surfaces, and chapter 4 shows how to translate, rotate, and scale geometric models with a single operation called matrix multiplication.

The last three chapters are dedicated to three ways to model the real world or even imaginary objects with geometry: signed distance functions, boundary representation, and 3D images. Different models work best in different contexts, so to be most efficient with your algorithms, you have to know all three representations, as well as how to convert a model from one representation to another.

To answer the question Which part of geometry applies to programming?, everything that made it into the book applies: lines, planes, curves, surfaces, transformations, deformations, and geometric data representations.

1.3 Why not let my tools take care of geometry?

Often enough, modern engines and frameworks try to isolate you from mathematics. Creating in this environment is like driving a car with the hood welded shut. If something goes wrong, you can’t fix it, and if you want to tune your car to go faster than the competitors’, you’ll have to get your hands dirty.

In 2013, I was working on an image processing tool that unbends curved pages from pictures to make them look flat. I created a prototype in C#, and it was slow. I thought about rewriting it in C++, because common wisdom tells us that C++ is faster than C#. But first, I went through the whole workflow with a profiler and found out that the bottleneck was in the initial image projection (figure 1.2).

01-02

Figure 1.2 In 2D, creating a projection is essentially the same as transforming a quadrilateral into some other quadrilateral.

That discovery was an odd one, because this operation is supposed to be fast. All you need to project a single point is perform nine multiplications and six additions. That’s it. Usually, you can use matrix multiplication to perform all these operations with a single function call (and you’ll see how in chapter 4). Essentially, a geometric transformation is simple number-crunching; it’s supposed to be fast.

But I was using a method from a standard library to do the transformation, and under the hood, it made no fewer than four conversions from one representation of a point to another. The process also had an empty constructor call and a method called CreateInstanceSlow. The computation itself was so fast that it didn’t even show up in a profiler, but the overhead of all the conversions was causing the slowdown.

So I reimplemented the transformation right in the code, and it appeared to be more than a hundred times faster that way. The code was four lines longer, but there were no conversions, no constructors, and no slow instances anymore.

The main takeaway here is that when you know your math, you have the option to bypass inefficient routines you’d have to use otherwise. This option is a competitive advantage on its own. But you could also learn another lesson: distrusting mathematics makes your code slow.

Someone once decided that matrix multiplication is too complex to leave exposed, so they wrapped it with some kind of transformation function. Someone else decided that homogeneous coordinates is not an approachable concept, and they decided to wrap the projective-space point in an affine-space point converter. Then another someone else decided that the words projective and affine should be banned from the system, and they wrote another wrapper over them. All in all, the weight of the wrappers became a hundred times the weight of the thing wrapped. In the candy-bar industry, this result would have been scandalous.

These terms and concepts may seem scary to an unprepared mind, but the truth is, wrapping them with other terms and concepts doesn’t make them go away. In fact, it only introduces more terms and concepts. Wrapping doesn’t make things easier; learning does! Besides, these things aren’t too complex to begin with.

In this book, you’ll learn all you need to know about projective spaces, homogeneous coordinates, and other concepts that are generally considered to be obscure and unapproachable. You’ll come to understand and trust the mathematics behind the code of game engines and CAD frameworks. You’ll become more proficient as a user of geometry-related code, and you’ll also acquire the knowledge to reimplement parts of it by yourself.

1.4 Applied geometry has been around forever; why learn it now?

Two empirical observations explain the technological landscape we live in today. First is Moore’s Law, which says that the number of transistors on a chip roughly doubles every two years. Pragmatically, this observation means that year after year, computers get faster, smaller, and cheaper. This effect is limited in time, of course; there’s a physical limit to how small a transistor could theoretically be, because there’s no such thing as a subatomic transistor. We still observe the effect, though, even if it’s not too pronounced. Moore’s Law doesn’t apply as much to PC central processing units (CPUs) anymore, but mobile devices are still getting faster, and graphics processing units (GPUs) are progressing quite well.

The second observation is Martin’s Lawn. In 2014, Robert C. Martin estimated that for the past 40 years, the total number of programmers in the world doubled every five years. This effect is also limited in time, of course; at this rate, we’d run out of nonprogramming people by the middle of the century.

Note The n in Lawn isn’t a typo. The observation was published in a blog post titled My Lawn at http://blog.cleancoder.com/uncle-bob/2014/06/20/MyLawn.html.

The decline of Moore’s Law means that people now seek other ways to increase performance other than waiting until hardware gets faster. New architectures, devices, and business models are available all the time. NVIDIA’s server-side GPUs, for example, aren’t GPUs at all; they don’t produce graphics so much as crunch numbers at an astonishing rate. Since 2016, Google has produced its own computer, but not a general-purpose one; it’s a tensor-processing unit specialized for work in artificial intelligence. In the finance industry, where low latency is king, most of the super-quick computations are already done in bare metal.

And of course, cloud technology is a big game-changer—not because of the technology itself, but because of its business model. In the PC world, a user pays for a machine and then buys software that fits this machine. As a result, the software makers should prioritize compatibility over performance. The consumer pays for the run time, but if a product doesn’t fit the user’s machine, it won’t sell.

With the cloud, things are a bit different. Now we in the software industry sell services, not software. We sell access to our software, which runs on someone else’s machines. We pay for the machines in the cloud ourselves, so performance is important; the run time is our cost. But we also get to decide what these machines will be. We don’t depend on the user’s choice much anymore. As a result, we’re free to optimize our code for highly specialized devices, and it pays to do so. To optimize algorithms that perform the service you sell, of course, you have to know how they work, and that’s why it’s important to know the math. You also have to be good at programming, and you have to understand the machine, too. But software frameworks will come and go, and hardware architecture will evolve; the only thing that will stand the test of time is mathematics.

To get back to Martin’s Lawn, the demand for competent programmers has been higher than the supply for about half a century. This situation should end at some point. The market will saturate itself, and the competition will become much more serious. To have an advantage in this future competition, you should start learning now.

You can’t learn hardware architecture that doesn’t exist. You can’t get good in a programming language that hasn’t been invented. But you can learn geometry. It’s been around for a few thousand years, and it will stay around for a few thousand more. Unlike with the software or hardware of the future, you can start learning geometry any day, and the sooner, the better. So why not today?

1.5 You don’t have to know much to start

This book is called Geometry for Programmers, not Programming for Geometers, so it doesn’t require any specific knowledge of advanced mathematics. The book doesn’t teach you how to program either. All the code examples in this book are in Python, but you’re more than welcome to use the language of your choice to do exercises or try things yourself. So what should you feel comfortable with to proceed with the book? You should have the following skills:

Reading and understanding snippets of Python code—You don’t have to be particularly good in Python programming. In the first half of the book, the Python snippets you’ll face are essentially formulas in disguise. We’ll use a Python library named SymPy to do the math for us. SymPy is a computer algebra system that, when used correctly, substitutes for years of training in symbolic computation. As we progress toward practical applications, we’ll use Matplotlib to draw pictures and NumPy to do numeric computations. You don’t have to be familiar with any of these libraries; I’ll introduce them briefly later in the book.

Picturing things in your head—The book has pictures, but they’re only pictures. To develop your geometrical intuition properly, you need to see how objects interact and how they respond as their parameters change. The book can give you hints and directions, but to see the final video, you have to use your imagination.

Also, most of the material in the book is accompanied by links to interactive demos and tutorials. You don’t have to rely on reading and programming alone; you can play with the concepts presented in ready-made environments.

Coding in whatever language you prefer—Most chapters have exercises that nudge you to write code in the language of your choice. It doesn’t matter which language you use; the geometry is the same in Python, JavaScript, and Rust.

Understanding elementary math—I’ll teach you some common mathematical concepts as needed in this book, but you’re still expected to understand the basics, such as what equations and coordinate planes are, and what constitutes a function in the mathematical sense.

This book requires no exposure to higher math. If you’re already familiar with linear algebra or calculus, this knowledge will help you in the related chapters, but it isn’t mandatory. The nature of programming geometrical entities, however, implies doing a lot of symbolic computations—turning formulas you know into formulas you want. Normally, this task requires considerable training in algebra, but we’ll cheat by using a computer algebra system. Nowadays, making a computer do your algebra for you is much simpler than it sounds. We’ll get to that task in the following section.

1.6 SymPy will do your math for you

I have one thing to confess: I’m really bad at doing math. I love math, but the feeling isn’t mutual.

I love the language of mathematics; I love its explanatory power; I love the feeling of reinvention when I learn new concepts and try them in practice. But when it comes to doing symbolic computations, I can’t do a dozen in a row without messing up plus and minus at least four times.

I’ve always been this way. When I showed my first academic paper to the editor, he took a brief look, pointed at the first formula, and said, You should have said minus here, not plus. As it turned out, I didn’t mess up the sign only once; I did it several times.

This situation complicated my professional career as an engineer, too. Luckily, a friend who is good at math saw me struggling with my equations and asked, If you hate doing it so much, why do you do it? Well, I’m getting paid for it, I said. Sure, he replied, but why do you do it by hand?

In my friend’s world, doing math by hand is fine only if