The maze book for programmers!
mazesforprogrammers.com

Algorithms, circle mazes, hex grids, masking, weaving, braiding, 3D and 4D grids, spheres, and more!

DRM-Free Ebook

The Buckblog

assorted ramblings by Jamis Buck

Sep 2016

Weekly Programming Challenge #9

24 September 2016 — Bezier curves — 5-minute read

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.

Week #8 Recap

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!

  1. Lasse Ebert went all-in this week, again in Elixir. His solution nailed every hard mode requirement, and even went above and beyond and added support for some non-numeric data types, like lists! Check it out, here: https://github.com/lasseebert/jamis_challenge/tree/master/008_calc. He earned a grand total of nine points, and with his support for lists and recursion, easily qualified for “surprise me” mode. Awesome work!
  2. Klas Axell’s solution is in Java, here: https://github.com/axekla/WeeklyProgrammingChallenge-8. He implemented normal mode, and earned one point.
  3. David Rice submitted a solution in Ruby for normal mode, earning one point as well. You can see it here: https://github.com/davidjrice/calculation-parser.

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!

Weekly Challenge #9

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 (a, b, and 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 a, b, and 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. When 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

Where a, b, and 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 P(1.0).

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…

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.

That’s it!

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.

Hard Mode

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:

  1. Implement cubic Bezier curves. Instead of three control points, these accept four, and the formula changes as well, becoming P(t) = a(1-t)^3 + 3bt(1-t)^2 + 3c(1-t)t^2 + dt^3.
  2. Rational Bezier curves. These add adjustable weights to each control point, and can actually be used to represent conic sections like circles. (The concept isn’t hard to understand, but most sources tend to wrap it all mathematics that may be unfamiliar to some. Consider it an opportunity to stretch your math muscles!)
  3. Use de Casteljau’s algorithm to split a curve at an arbitrary value of 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.)
  4. If your environment is amenable, try implementing an interactive system, maybe on an HTML canvas element. Allow control points to be dragged around, showing how the curve changes as the control points change. This option is worth 3 points.

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 jamis@jamisbuck.org.

Weekly Programming Challenge #8

17 September 2016 — Implement a simple parser and interpreter — 5-minute read

Weekly Programming Challenge #7

10 September 2016 — The seventh weekly programming challenge is posted — 1-minute read
Aug 2016

Weekly Programming Challenge #5

27 August 2016 — The fifth weekly programming challenge is posted — 1-minute read
Jul 2016

Weekly Programming Challenges

30 July 2016 — The first of a weekly series, in which readers are encouraged to challenge themselves by implementing the stated requirements — 1-minute read
Jun 2016

Truth: Generating Truth Tables

11 June 2016 — 2-minute read

May 2016

Disrupting Your Comfort Zone

28 May 2016 — 1-minute read

Think You’re Failing? Look Around.

14 May 2016 — 1-minute read

The Minimalist Programmer

7 May 2016 — 1-minute read

Apr 2016

Tapping ActiveRecord Relations

23 April 2016 — 2-minute read

Medium.com

2 April 2016 — 1-minute read

Mar 2016

Introducing the Query Composer

26 March 2016 — 4-minute read

The Poverty of Constraints

19 March 2016 — 1-minute read

Variations on a Theme: "I Becomes We..."

12 March 2016 — 2-minute read

Being a Good Neighbor...

5 March 2016 — 6-minute read

Feb 2016

Implementing a Bloom Effect with Swift+Metal

27 February 2016 — 7-minute read

Don't Feed the Hamster the Whole Stalk

20 February 2016 — 6-minute read

The weakly-flowing stream

13 February 2016 — 4-minute read

Living with Your Eyes Open

6 February 2016 — 6-minute read

Jan 2016

Software Proverbs

30 January 2016 — 4-minute read

Mazes in Swift

23 January 2016 — 4-minute read

A Pretty-Printer for SQL

16 January 2016 — 2-minute read

Don't Assume It's Difficult until It Is

9 January 2016 — 5-minute read

Game Demonstration: Recover the Widgets

2 January 2016 — 6-minute read

Dec 2015

Checking In...

26 December 2015 — 1-minute read

Avoiding "Call Super" with Callbacks

19 December 2015 — 5-minute read

Little Things: Introspecting Block Parameters

12 December 2015 — 1-minute read

Integration API vs. Internal API

5 December 2015 — 3-minute read

Nov 2015

Upsilon Mazes

28 November 2015 — 9-minute read

Representing a Toroidal Grid

21 November 2015 — 11-minute read

Way Back

The Buckblog Archives

Dating to 2004 — Hundreds more articles