Better Know an OpenGL

One of the nice things about working at Mozilla is just how much ground there is to cover! Lots of performance problems are due to graphics and reflow issues. Since I didn't know a single thing about either of time, it's a great time to learn. Starting from the bottom up on a whole new topic is a really unique chance, so let's start with Graphics.

I've been starting off by watching these great lectures by UC Davis Professor Ken Joy on computer graphics. The first thing to note is that we need a lot of math to get started, a lot of math. Everything you see on a computer is just a pixel, which translates to a Point in our Cartesian plane. (Hello geometry!) How do we actually draw a curve on a computer?

We mostly use the OpenGL API, which I've learned requires a ton of cruft code. To reduce the cruft code, we use GLUT, which abstracts a lot of the cruft away as well as the platform specific windowing APIs. The ton of cruft code basically tells the OS that we want a window with buttons as well as how big to make the window (800 X 600) etc. The crux of the problem is actually how do we draw shapes and curves on a screen?

In the real world, we can draw curves as a contiguous connected line, creating smooth curves. In computers, we can only represent curves as single points connected by a single line. The fewer points we have, the less "smooth" our curve is. The more points we have, the "smoother" the curve is. Consider a parabola (Excuse me for my horrible handwriting, I should learn matlab or something to draw pretty figures). It is defined by three points [1,1], [2,3], and [4,1], with the peak being at [2,3]. In the analog world, we get a nice clean curve if we draw a parabola with these points:

analog.png

However, in the discrete / OpenGL world, we aren't so lucky. With OpenGL, we can only draw a line between two points, so we draw the same thing but in the discrete world:

discrete.png

What we see looks more like a pyramid than a real curve. To fix the issue, we can add imaginary midpoints between our original 3 points, and draw line segments between these midpoints.

fewerPoints.png

We see that our curve looks a little better, but not quite the same as the analog case. What if we add more points:

morePoints.png

And here is a large crux of the problem with computer graphics. The more midpoints we add, the smoother our curve looks, but the more work our computer has to do. Finding the balance seems to be the key to drawing smooth curves.

Now theoretically, this is great, we just have to find what those midpoints are and we can draw nice clean curves! Essentially, to do 2d curves, we calculate a bunch of points. We feed those points to OpenGL and tell OpenGL to draw lines between them. At the end, we tell OpenGL to draw and voila! A Curve!

Calculating Midpoints

There are tons of different ways of calculating midpoints, mostly named after mathematicians. The one we hear about all the time is a Bezier Curve. A bezier curve is defined by using 4 points, known as the control points. My current understanding of them is that we actually have two sets of two points.

End points - Two points to describe the end points of the curve
Tangent points - Two "invisible" points that pull the curve.

Consider this spline editor. Change the Interpolate from linear to basis and you'll see four points. The two end points where the curve actually goes through determine where the curve starts and ends. The two middle points act almost like gravity, pulling the line towards those points, but not at it.

When we define a bezier curve, we have to define these four points. We can just make them up as we go. Now why is this called a bezier curve? Because once we have these four points, we can plug these numbers into the bezier's formula and we get midpoints! Where do we get bezier's formula? Wikipedia!

B(t) = (1-t^3)P0 + 3(1-t)^2P1 + 3(1-t)t^2P2 + t^3P3

This looks really daunting. What we're really using is what's called a cubic bezier curve since we have 2 tangents (e.g. 2 points in the middle). If you plot y=x^3, you'll see what I mean. It kind of looks like an S rather than x^2. P0 and P3 here are our two end points. P1 and P2 are our two tangent points. Bezier also introduces a new variable t. T is a value between [0-1]. It basically says how many midpoints do we want between our two end points? Plug that number in and we'll get a new midpoint! But t must be between [0-1]. So if we want 20 points, we usually do something like:

1
2
3
4
5
for (int i = 0; i < 20; i++) {
  float t = i / 20.0;
  // Gives us our midpoint
  bezier(P0, P1, P2, P3, t);  
}

Whew that's a lot of math, but now we can finally get some code. Essentially, we have a bezier curve formula, we have 4 points that we made up, and now we just have to decide how many midpoints we want. The more midpoints we have, the smoother the curve. One thing to note is that each point in the bezier curve is actually one axis of the point. So we need to do something like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
GLfloat bezier(float t, GLfloat P0,
                  GLfloat P1, GLfloat P2, GLfloat P3) {
  // Cubic bezier Curve
  GLfloat point = (pow((1-t), 3.0) * P0) +
    (3 * pow((1-t),2) * t * P1) +
    (3 * (1-t) * t * t * P2) +
    (pow(t, 3) * P3);
  return point;
}

void drawStuff() {
  midpoint_x = bezier(P0.x, P1.x, P2.x, P3.x, t);
  midpoint_y = bezier(P0.y, P1.y, P2.y, P3.y, t);

  drawPoint(midpoint_x, midpoint_y);
}

Now for our final concept. OpenGL has the concept of a "current" point. We have to feed OpenGL a list of points, and tell OpenGL to draw lines between each point. We start by giving OpenGL a single point, calculate the next point using our bezier curve (var newMidPoint), then feed the new point to OpenGL. OpenGL automatically draws the line between those two points, but our new "current" point now points to (newMidPoint). So we go through the loop, calculate another new bezier curve point (var secondMidPoint), feed secondMidPoint to OpenGL, and OpenGL draws a line between (newMidPoint -> secondMidPoint), and we do this over and over.

Let's have an experiment. Let's just tell OpenGL to draw only our bezier curve points, not a line between each one, and let's draw 5 points for now:

5Points.png

We have 6 points total, our starting points plus our 5 bezier midpoints. Now if we tell open gl to draw lines between them:

5Line.png

Not too shabby! Let's make it smoother, let's draw 30 points:

30Points.png

And segments between them:

30Line.png

Not too shabby huh. You can see the final code here. You can play with the number of points by changing t on line 63. You can disregard the z points as we're doing only 2d for the moment.

Combining Curves

Well drawing a single curve isn't too fun, but what if we want something more complicated. All complicated pictures are just a bunch of bezier curves hooked together. These are called a bezier spline. Once I finish drawing something useful, I'll update my blog, but it's a good starting point.