The maze book for programmers!
Algorithms, circle mazes, hex grids, masking, weaving, braiding, 3D and 4D grids, spheres, and more!
Years ago, I toyed with getting a master’s degree in computer science, and while that little experiment didn’t last long, I was able to take some fascinating classes. One of them was CS 557, “Computer Aided Geometric Design”, taught by Professor Tom Sederberg. It introduced me to the wonderful world of curves–Bezier curves, B-splines, surfaces, and more. It was one of those classes that has stuck with me for a long time, though I rarely get the chance to use any of what I learned there.
For this week’s challenge, we’re going to dip our toes into that magnificent mathematical sea, and implement quadratic Bezier curves.
But first, let’s recap week #8.
For the 8th weekly programming challenge, we tackled a parser and interpreter for a simple arithmetic expression grammar. The normal mode was basic–a simple evaluator for arithmetic expressions–but hard mode added some fun (I hope!) extras, like variables, statements, and even functions!
My own solution was in Haskell, here: https://github.com/jamis/weekly-challenges/tree/master/008-calculator. I implemented normal mode, as well as variables, multi-expressions, and exponentiation, and earned four points.
Awesome work, everyone!
Now, I’m not going to lie. There can be (potentially) a lot of math behind Bezier curves, but the good news is that it isn’t hard math. At least, not for the basic stuff. The algorithms for rendering a Bezier curve are iterative, using only basic arithmatic.
For once, Wikipedia kind of lets us down, as it’s article on Bezier curves is fairly dense and kind of intimidating. We’re going to focus just on quadratic Bezier curves for normal mode, here, which simplifies things a bit, but let me see if I can explain the basics here in a way that clarifies rather than intimidates.
A quadratic formula is (essentially) one in which the variable is squared, or raised to the second power. For example:
at^2 + bt + c
That’s a quadratic formula where
t is the variable. The other letters (
c) are just constants, called the coefficients.
For our Bezier curves, the coefficients will be points on a canvas. Each quadratic curve is defined by three control points, corresponding to the
c in our quadratic formula. By moving those control points, you change the shape of the curve. (If you’ve ever played with a curve tool in a program like Photoshop, you’ll know exactly what I mean.)
In other words, you give the formula three control points, and a value of
t that is between 0 and 1, and the formula gives you a point on the line that corresponds to
t is 0, you get the first control point. When
t is 1, you get the third control point. And when
t is in between, you get a point on the curve somewhere between the beginning and the end, depending on the value of the second control point.
For a quadratic Bezier curve, the formula we want is this one:
P(t) = a(1-t)^2 + 2b(1-t)t + ct^2
c are the control points, and
P(t) is the point corresponding to whatever value of
t we give it.
To draw a Bezier curve, then, we just choose how many segements we want to break the curve into, plot that many points along the curve, and connect them with lines. For example, we start at
P(0), connect that with a line to
P(0.1), and then from there to
P(0.2), and so forth all the way to
Does that make sense? If you’d like additional reading, I strongly recommend the text book that my CS 557 professor wrote, and which he has made available for free as a PDF, here: Computer Aided Geometric Design (last updated Sep 2016). It begins with a relatively gentle introduction to mathematical graphics concepts (like vectors, matrices, and parametric, implicit, and explicit equations), and then moves into discussions of Bezier curves and splines. (It’s a pretty fantastic text book, really.)
So, for normal mode…
Your program will need to accept, as input, three points. The program will then emit an image of the quadratic Bezier curve that corresponds to those three points.
Feel free to reuse your graphics library from challenge #4, if you want, although you can use whatever graphics library is handy. All you need is the ability to draw lines between points.
A normal mode submission will earn you one point.
Once you’ve got the basics working, there are some fun things we can do with some more advanced topics. Consider some of these, each worth an additional one point:
P(t) = a(1-t)^3 + 3bt(1-t)^2 + 3c(1-t)t^2 + dt^3.
t. Again, the Wikipedia article is a bit intimidating, but if you skip to the section titled Geometric Interpretation it gives a decent intuitive explanation of the algorithm. (Professor Sederberg’s book gives an even better explanation of it, I think.)
Feel free to shoot for “surprise me” mode, too! It doesn’t have to be any harder than normal mode, but it ought to implement the challenge in some surprising, clever, or otherwise delightful way. See what you can come up with!
This challenge will run until Saturday, October 1st, at 12:00pm MDT (18:00 UTC).
Post a link to your submission in the comments, but please: only link to your solution. Do not post source code in the comments. Comments that post source code directly will be removed. If you have any questions about this challenge, post them in the comments as well and I’ll try to clarify.
If Disqus (the comment system) gives you any grief, please feel free to email your solution to me directly, at email@example.com.