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).
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.
highlight, annotate, and bookmark
You can automatically highlight by performing the text selection while keeping the alt/ key pressed.
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.
discuss
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.
settings
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).
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.
highlight, annotate, and bookmark
You can automatically highlight by performing the text selection while keeping the alt/ key pressed.
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?
discuss
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.
settings
Take our tour and find out more about liveBook's features:
- Search - full text search of all our books
- Discussions - ask questions and interact with other readers in the discussion forum.
- Highlight, annotate, or bookmark.
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 you enjoy doing it that way. Professionally, he does math with SymPy, which is a library for symbolic mathematics that aims to become a full-featured computer algebra system.
Both symbolic mathematics and computer algebra may seem too science-y, so let me explain the process the way my friend explained it to me: “You import SymPy; then you feed it your equations and say ‘Solve.’” That’s it.
Let’s try a simple math problem. A train departs from Amsterdam to Paris. Another train, twice as fast, departs from Paris to Amsterdam. The distance between Paris and Amsterdam is 450 km, and the trains meet in an hour. What are the trains’ speeds?
When you rewrite this problem in mathematical notation, you get a pair of equations. Let’s call the speed of the train departing from Amsterdam Va and the speed of the Paris train Vp. Also, let’s store the speeds in kilometers per hour. Now, the fact that these two trains make 450 km in an hour together turns into this line,
Va + Vp = 450
and the fact that the Paris train is two times as fast as the train from Amsterdam turns into this line:
Vp = 2Va
These lines give us a two-piece system of equations. I’m sure you can solve the problem in your head easily, but please don’t. Let SymPy do it for you. You don’t even have to install SymPy on your computer; go to SymPy Live at https://live.sympy.org, and try it all there.
SymPy is an algebra system that does your algebra for you, but it’s also a Python module. Being a Python module, it plays by Python rules, which involve a few implications. First, obviously, you have to import it to use it:
from sympy import *
Next, you have to define symbols. This task wouldn’t be necessary if SymPy had its own language, but it reuses Python syntax, and in Python, you have to define symbols before using them. So we have to play by those rules. Let’s define our speeds as Va for the Amsterdam train and Vp for the Paris train:
Va, Vp = symbols('Va Vp')
Next, let’s write the equations one by one, starting with the one for the speed difference. Again, SymPy is a Python module and in Python, = is the assignment operator, so we can’t write Vp = 2Va. Instead, we write all the equations as though they have 0 on the right side. We move everything from the right side to the left while changing its sign. So Vp = 2Va becomes
Vp - Va * 2,
Va * 1 + Vp * 1 - 450
(You don’t have to write * 1, but let it stay for a while. We’ll substitute it with something else in a minute.)
solution = solve([
Vp - Va * 2,
Va * 1 + Vp * 1 - 450
], (Va, Vp))
We want to know Va and Vp, so after the equations, we write these symbols in a separate tuple. This tuple may look like needless repetition, but we’ll see why it’s necessary when we introduce more symbols.
Finally, we want SymPy to give us the answer. Because it uses Python, we can use a simple print command:
print(solution)
And that’s it. The whole program looks like the following listing (ch_01/meet_sympy_numeric.py in the source code for this book).
Listing 1.1 Numeric solution in SymPy
from sympy import *
Va, Vp = symbols('Va Vp') #1
solution = solve([
Vp - Va * 2,
Va * 1 + Vp * 1 - 450
], (Va, Vp))
print(solution)
{Va: 150, Vp: 300}
Nice. But that result isn’t the math we should be excited about. These are numbers, and we can get numbers with a calculator. What about letters and formulas? Can SymPy produce a generalized equation that will work for any distance, time, and speed ratio?
Yes, it can. SymPy can do math with letters. We’ll give it more symbols and fewer numbers. Let’s change all the constants we have in the code, including 1, to symbols and rerun the program, as shown in listing 1.2 (ch_01/meet_sympy_symbolic.py in the source code for this book).
Listing 1.2 Symbolic solution in SymPy
from sympy import *
Va, Vp, Vpx, D, t = symbols('Va Vp Vpx D t') #1
solution = solve([
Vp - Va * Vpx,
Va * t + Vp * t - D
], (Va, Vp))
print(solution)
Note that writing (Va, Vp) after the equations makes more sense now. We want to compute speeds from time symbolically, but we can also potentially compute time from speed. We have to be explicit about what we’re computing. The symbols in the tuple are the symbols we want to have solved in terms of other symbols. In our case, this solution is
{Va: D/(Vpx*t + t), Vp: D*Vpx/(Vpx*t + t)}
Yes! We have a generalized solution for the two-trains problem. They can travel from New York to Hong Kong now; we wouldn’t care. With symbolic formulas, we have the problem solved for every distance, every time, and every speed proportion!
Now, because we’re programmers, let’s turn the formulas we’ve computed into code. I’m sure you can do this by hand easily, but again, let SymPy do it for you. SymPy has the job covered. If you want SymPy to write code for you, all you need to do is ask! If you need some Python code, use the pycode function
print(pycode(solution))
{Va: D/(Vpx*t + t), Vp: D*Vpx/(Vpx*t + t)}
Well, yes, this result is exactly the same as before, but only because the formulas we had were already valid Python code. If they contained any language-specific operators and functions, this translation feature would have appeared much more impressive.
We can ask SymPy to produce code in JavaScript (jscode), Julia (julia_code), FORTRAN (fcode), C (ccode), Octave and Matlab (octave_code), and even Rust (rust_code).
SEE ALSO
SymPy’s online documentation is great. If you want to learn more about code generation, please visit http://mng.bz/ElmO.
But wait—there’s more! Let’s say you want to publish your equations. Mathematicians love to publish things in LaTeX, so why don’t we try it as well? With SymPy, you don’t have to translate your solution into LaTeX by hand. Use the latex function instead of pycode:
print(latex(solution))
\left\{ Va : \frac{D}{Vpx t + t}, \ Vp : \frac{D Vpx}{Vpx t + t}\right\}
Nice! In this book, however, we’ll use mathematical notation sparingly. Remember, it’s Geometry for Programmers, not Programming for Geometers.
A small recap: SymPy is a Python library that does your math for you. To make it do so, you have to import it, declare the symbols for your equations, combine your equations into a system, and run solve. If possible, SymPy will solve equations numerically; if necessary, it will solve them symbolically, writing a generalized solution with symbols in it. Then you can turn this solution into code in a language of your choice or even into a publishable LaTeX formula.
Now you know most of what you’ll ever need to be prolific with SymPy. You’ll get the rest on the go. Congratulations! You spent maybe 15 minutes reading this introduction, and you can already add a computer algebra system to your résumé. Isn’t that a good start?
- Applied geometry is geometry that has applications in computer graphics, animation, CAD, 3D and 2D printing, augmented and virtual reality, computer vision, and image processing in general.
- You can start learning geometry at any time, but now is probably the best time. Your learning will pay off immediately, if you already work as a programmer of CAD applications or games, or in the future, as a long-term, nonperishable investment in your education.
- SymPy is a Python library that does your math for you. It can do some number-crunching, but its true calling is symbolical computations. It turns formulas you have into formulas you want. Moreover, it can turn formulas into source code in the programming language of your choice and prepare them for publication as a bonus.
- Learning applied geometry doesn’t require rare skills or knowledge. We’ll use SymPy to do our math for us as a shortcut.