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

Sunday, October 22, 2006

Curves: Color

I wrote a post about "section radius" recently, which involved drawing curves with a discreet number of anchor points. The application there was a more robust replacement for the Taper attribute of prims. Of course, the usefulness of using a curve instead of one or two numbers is not limited to Taper alonethere are innumerable other uses for them, completely aside from the Object attributes.

One of my backburner obsessions for the past few months has been color. (No surprise there, given that I'm currently enrolled in a color theory class, I suppose.) In particular and with regard to SL, two aspects have been on my mind. The first is using a base color as input to an algorithm to generate related colors (lighter tint, darker shade, blue-shifted, red-shifted, visual complement...). The second is blending between two colors in a smooth and visual appealing fashion.

This is where curves come in.

You see, colors can be represented in a computer program as multidimensional vectors, usually 3-vectors: the x component corresponds to the intensity of the red color channel, the y to the green, and the z to the blue. For example, [1.0, 0.0, 0.0] is pure red, [0.8, 0.5, 0.0] is an orangey color, [1.0, 1.0, 1.0] is pure white, and [0.0, 0.0, 0.0] is pure black.* (In additive color models, such as light, the presence of all colors is white. In subtractive color models, such as pigment or paint, the presence of all colors is black, at least theoretically; in practice, mixing all your paint colors together usually makes a grayish brown.)

* NB: for convenience, I am denoting vectors with square brackets, [ ], instead of the usual angled brackets, < >, which are also used to denote HTML tags, causing the silly Blogger software to interpret my vectors as malformed HTML code. Yes, I am too lazy to search-replace them with the symbol codes.

So suppose we want to blend between, say, [1.0, 0.0, 0.0] red and [0.0, 0.0, 1.0] blue. The simplest way to do this would be a straight linear blend. Since positions in space, like colors, can be represented as 3-vectors, a linear blend is equivalent to moving in a straight line from point A to point B.

We could write an algorithm thusly, with a being the starting color/point, b being the ending point, and t being a number between 0.0 and 1.0, representing our progress moving from a to b (e.g. t = 0.5 means we are exactly halfway between the two; t = 0.25 means we are ¼ of the total distance from a, and so ¾ of the distance from b):

line(t, a, b) = a + t * (b - a)
Here are some sample points using our algorithm to blend between red and blue:
line(0.00, [1,0,0], [0,0,1]) = [1.00, 0.00, 0.00]
line(0.25, [1,0,0], [0,0,1]) = [0.75, 0.00, 0.25]
line(0.50, [1,0,0], [0,0,1]) = [0.50, 0.00, 0.50]
line(0.75, [1,0,0], [0,0,1]) = [0.25, 0.00, 0.75]
line(1.00, [1,0,0], [0,0,1]) = [0.00, 0.00, 1.00]

To be ct'd in Issue #452: Pierre Bézier and Paul de Casteljau unite once more in... O What a Twisted Curve We Weave!! Don't miss it, gang!

Sunday, October 08, 2006

My Agenda

I didn't conciously realize this when I first started writing here, but my feature requests have a very specific agenda. To put it succinctly:

I want Second Life to be more like a high-level 3D modelling application.

My education is in 3D computer modelling and animation, and I have a good understanding of computer programming. Thus, my perspective on Second Life is from the angle of someone who uses high-level modelling and animating tools like Maya and Blender, and high-level programming languages like Ruby, Python, and LISP.

The tools offered in Second Life are technically inferior to just about everything I have used, but it has the definite advantages of being collaborative, interactive, and visible.

By collaborative, I mean that many people can use it and work on a single project at the same time, in the same working space. Rather than many people working separately on their individual parts, we can come together and build something together, watch each other build, and see how our work fits within the whole project.

By interactive, I mean that there is a great degree of communication between the user and the tool, and between the user and other users. You can see the changes you are making as you make them. And not only can you see them, but your partners can see them. This makes Second Life an excellent platform, again, for collaborative work, but also for education and error correction: rather than a teacher seeing only the finished product of a student's work, the teacher can see the student's process and suggest improvements to it.

By visible, I mean that the work exists in a "real" space where audiences can see it. Gallery spaces can be created and work arranged within that space for people to see. Multiple viewers can see it at once, discuss what they see and think about it, and interact with each other and with the artist. This has a definite advantage over a simple web page with several images ordered sequentially. It even has an advantage over a web forum where users can post work and comment on the work of others.

To bring all these points together: the high level 3D modelling applications that I use are missing something which Second Life has; and Second Life is missing something that the modelling applications have.

But there's more to the story than just that.

High-level 3D modelling applications have a lot of features which are not necessary or even useful in the context of Second Life, for reasons technical and otherwise. It is not my agenda to graft unneeded and pointless features onto Second Life. Doing so would waste resources which would be better used on more important things.

Second Life is a lot more than a distributed 3D modelling platform. It has social, commercial, educational, and recreational value, all of which are undeniably important parts of what make Second Life what it is. It is not my agenda to reduce or remove any of these facets of Second Life. They are the reason and purpose for the 3D modelling aspect to exist; without them, Second Life would be pointless.

And yet, just as tools without a purpose would be pointless, a purpose without the tools to fulfill it would be squanderage. The scenery of Second Life is a critical part of its social, commercial, education, and recreational value. It is toward the purpose of fulfilling the potential of Second Life that I propose features and changes. Every feature I suggest, I do so because the benefit towards fulfilling important values would be far greater than the cost of implementing the feature.

I want Second Life to be more like a high-level 3D modelling application...

...because that would facilitate the creation of new, interesting, beautiful, and useful things which would enrich Second Life.