Sunday, October 29, 2006

Curves: Color (Part 2)

Attention: Maths ahead! Non-geeks may prefer to avoid the equations, and just look at the pretty colors instead.

Previously, on Jacek Writes: our hero introduced the topic of smoothly blending between two colors algorithmically.

Linear blend from red to blue.
Last time, I defined an equation for blending linearly between two color vectors a and b as time, t, increases from 0 to 1:

line(t, a, b) = a + t * (b - a)

After a little algebra, we can rewrite that function as:

line(t, a, b) = (1-t)(a) + bt

Linear blending looks just fine for blending between two colors, as demonstrated above. Starting from the left, we progress from red to blue, passing through magenta and purples. Looks pretty good, right?

Linear blend from red to blue to green.
The problem arises when we try to add a third color, blending from a to b, then from b to c. As you can see, there is a "spike" at the point where we reach pure blue. To use a spatial analogy, we are driving from point A to point B, then taking a hard right turn and going to point C; it's the spot that we take the turn that ruins the smoothness.

But there are other techniques besides linear blending, which can solve this discontinuity. The technique that I prefer (for its versatility) is Bézier curve blending.

For the uninitiated, Bézier curves are a beautiful and elegant mathematical technique for modelling smooth curves like those used in graphic and industrial design. They are closely related to NURBS (Non-Uniform Rational B-Splines) Surfaces, a modelling technique popular among computer animators for producing smooth, organic shapes. (Although, NURBS surfaces have somewhat fallen out of use in favor of other techniques like Catmull-Clark subdivision surfaces.)

Bézier curves have several properties which are important for our purposes: 1) they are smooth, 2) they are not difficult to compute, and 3) each curve can be defined through a small number of control points, or "knots".

Based on viewing the wonderful animated diagrams on Wikipedia, I set about reverse-engineering Bézier curves. (Sure, I could just find an equation on the web somewhere, but where's the fun in that?)

What I find so elegant about Bézier curves is that the equation can be a fractal, recursively defined. Using our linear blend function defined above, we can define a quadratic Bézier curve which passes through points a and c, with a control point b:

quad(t, a, b, c) = line( t, line(t, a, b), line(t, b, c) )

That may make a mathematician's lips quiver with joy at its simplicity and elegance (especially if you then use that function to define a cubic Bézier curve, as I will do next time), but it has certain redundancies when it comes to evaluating it with a computer (i.e. it takes more separate mathematical operations than necessary).

So, I got out my pencil and pad and expanded the equations by hand, combining terms and simplifying, then using that equation to write an equation for a cubic Bézier curve. In fact, I did so in four different ways (only two of which were novel in the fact that they contained algebra errors so foolish that they would embarrass an English major).

My final equation for a quadratic Bézier curve is as follows:

quad(t, a, b, c) = (1 - t)2(a) + (1 - t)(2bt) + ct2

Quadratic Bézier blend with red, blue, and green control points.
Using this equation to blend between three colors produces the image seen here. As you can see, it is definitely very smooth; it has solved the problem we saw with the linear blend, the spike when we reached blue and make a hard right towards green.

But there is a problem.

It never hits pure blue.

It gets close, there in the middle. We pass near blue. We are definitely in Blue County, Color-ado.

But we never actually see pure blue!!

Have Bézier curves failed our hero? Is this the end?!? Don't miss the shocking conclusion next time, Issue #1397: Crossed Controls & Cubic Curves --JA


Reina Quine said...

Non-NERDS, dammit! As a full-on geek, I resent your falsely-worded warning!

Also...pretty colors! *drool*

Roe said...

"..." Beautiful, just beautiful Jacek

*mind spins*

Akela Talamasca said...

Why are you hurting my brain? Now whenever I see a rainbow, I'm going to curl up in a corner and whimper, while mathematical symbols spin giddily about my reeling head. *whimper*