Sol's Graphics Tutorial

06 - Primitives and Clipping

This chapter is a bit heavier on the theory side again. As the title says, we'll be covering basics of primitives and something we have avoided so far, clipping.

A primitive is some slightly higher-level object you'd use to draw graphics. Primitives include lines, circles, sprites, polygons, etc. Most modern 3d hardware uses triangles as the primary primitive; even lines are actually drawn using triangles.

All of the primitives still consist of pixels. If you take a pen, some paper, and a ruler, you can draw a more or less perfect line. Now, if you did this on checkered paper and decided to fill out all the quads the line crosses, you'd get something like this..

The dark line is the ideal line that you'd like to draw, but, since the screen consists of pixels, what you actually get is this jaggy thing that doesn't really look like a line at this distance. Make the pixels small enough and you won't see the difference.

That's basically how lines are drawn on computers. There's some fill rules and anti-aliasing in there to make things a bit prettier, but that's the basic idea.

One thing that most common primitives share is that they are convex. As an example, filled circle, triangle and line can all be drawn with horizontal lines so that there's only one horizontal line for each vertical coordinate.

Let's look at the filled circle:

The same idea here. Dark blue is the ideal filled circle (remember, the quads in our "paper" here are the pixels), cross-hatched pixels are the ones that actually get drawn. One horizontal line, or horizontal span, or horizontal scan, is marked with red.

This process is known as scan conversion. So, in order to scan convert a circle, we need to find out the left and right coordinates of every scan line for the circle. This can be done in several ways. You could, for instance, set up a couple of arrays, left_x[] and right_x[], and then play around with the sin() and cos() functions until you have filled them out, and then just draw the horizontal lines between the values.

Or we can play around with math and figure out a formula that spits out the length of a scan based on the y coordinate.

Like width = sqrt(r * r - (r - y) * (r - y)) * 2.

Oo, scary.

Remember hearing someone say that one of the primary skills a programmer needs is math? Well, I don't think so. Don't get me wrong - having strong math helps! Most of the time, however, you just look for a ready algorithm, like the one above, and apply it.

If you wish to know the math you will be needing, look up trigonometry (sines and cosines, etc), boolean algebra (ands, ors, nots and that sort of thing). Additionally you'll - naturally - need basic algebra (plus, minus, multiply, divide, roots and powers). Basic knowledge of vectors is also important. It's useful, but not at all necessary, to understand linear algebra. Most of the time it's enough to know that a "matrix" is this thing you feed vectors to, and you end up with new vectors that were what you wanted.

(I've also written a brief tutorial about Boolean algebra, bit masks and bit modification that you may find useful).

Note that there are better and faster algorithms around (Bresenham), but this'll do for our purposes.

So, to draw a filled circle, all we need is.. (you don't need to copy-paste this anywhere yet)

#define PI 3.1415926535897932384626433832795f

void drawcircle(int x, int y, int r, int c)
{
  int i, j;
  for (i = 0; i < 2 * r; i++)
  {
    int len = (int)(sqrt(r * r - (r - i) * (r - i)) * 2);
    int ofs = (y - r + i) * WINDOW_WIDTH + x - len / 2;
    for (j = 0; j < len; j++)
      gFrameBufer[ofs + j] = c;
  }
}

That's it for the primitive theory for now.

So far, we have had to be very careful not to draw outside the screen. To free ourselves of this limitation, we could take a putpixel() function and check whether the pixel coordinates are valid for each pixel. As I mentioned earlier, this would not be too wise, as we'd be calling this putpixel() a lot. Much better solution is to solve this problem at primitive level, and this is operation is called "clipping".

The filled circle function, with clipping added in, looks something like this:

#define PI 3.1415926535897932384626433832795

void drawcircle(int x, int y, int r, int c)
{
  for (int i = 0; i < 2 * r; i++)
  {
    // vertical clipping: (top and bottom)
    if ((y - r + i) >= 0 && (y - r + i) < WINDOW_HEIGHT)
    {
      int len = (int)(sqrt(r * r - (r - i) * (r - i)) * 2);
      int xofs = x - len / 2;
      
      // left border
      if (xofs < 0)
      {
        len += xofs;
        xofs = 0;
      }
      
      // right border
      if (xofs + len >= WINDOW_WIDTH)
      {
        len -= (xofs + len) - WINDOW_WIDTH;
      }
      int ofs = (y - r + i) * WINDOW_WIDTH + xofs;
      
      // note that len may be 0 at this point, 
      // and no pixels get drawn!
      for (int j = 0; j < len; j++)
        gFrameBuffer[ofs + j] = c;
    }
  }
}

As an example, consider a circle with a radius of 100 that is drawn at (-200, -200). The above function does 200 if:s and no function calls. If we had just replaced our putpixel() with one that checks the coordinate validity, we'd be calling the function over 30000 times, which would then check, every time, whether the pixel is within the screen boundaries or not.

If we knew that most of our circles end up completely outside the screen, we could add checks for that case at the beginning of the function. And yes, that would also accelerate the putpixel version (and would actually make more point there).

Okay, so we have a filled circle function with clipping. What shall we do with it? You can naturally take just about any of the earlier chapters and replace sprite drawing functions with that one, and animate the size as well. Or you can take the snowing example and add some trees and snowmen to the landscape. Or, you can try something new..

Exit the IDE, make a copy of the previous chapter folder and rename it to ch06. Go to the ch06 folder and double-click on the project file to bring up the IDE.

Copy the new cliping-enhanced drawcircle() function to the source, after the update() function. Don't forget the PI. If you get compiler errors with the PI defined, some header you're using is probably defining it as well. In that case you can either add#undef PI before our definition, or just leave our definition out if you trust that the PI that was there is valid. Or we could use M_PI but there's been some confusion with it at some point so let's just go with this.

Add the following two lines near the top of the file (after the #include lines)

#define TREECOUNT 64

float gTreeCoord[TREECOUNT * 2];

Here's a new init() function:

void init()
{
  srand(0x7aa7);
  int i;
  for (i = 0; i < TREECOUNT; i++)
  {   
    int x = rand();
    int y = rand();
    gTreeCoord[i * 2 + 0] = ((x % 10000) - 5000) / 1000.0f;
    gTreeCoord[i * 2 + 1] = ((y % 10000) - 5000) / 1000.0f;
  }
}

The above code generates some random coordinate pairs in the range of -5 to 5, and stores it in the global gTreeCoord[] array. Every second index in the array is the x coordinate, and the other is the y coordinate. We can easily adjust the number of trees with the TREECOUNT define. Did I say trees? Oh, here's the new render() function:

void render(Uint64 aTicks)
{
  // Clear the screen with a green color
  for (int i = 0; i < WINDOW_WIDTH * WINDOW_HEIGHT; i++)
    gFrameBuffer[i] = 0xff005f00;

  float pos_x = (float)sin(aTicks * 0.00037234) * 2;
  float pos_y = (float)cos(aTicks * 0.00057234) * 2;

  for (int i = 0; i < 8; i++)
  {
    for (int j = 0; j < TREECOUNT; j++)
    {
      float x = gTreeCoord[j * 2 + 0] + pos_x;
      float y = gTreeCoord[j * 2 + 1] + pos_y;
      drawcircle((int)(x * (200 + i * 4) + WINDOW_WIDTH / 2),
          (int)(y * (200 + i * 4) + WINDOW_HEIGHT / 2),
          (9 - i) * 5,
          (i * 0x030906 + 0x1f671f) | 0xff000000);
    }
  }
}

Compile and run.

In the render() function we're first clearing the screen with 0xff005f00, which is darkish green. Then, we calculate our "camera position" using time and sin() and cos(). Then we loop through the "trees", drawing each tree with eight filled circles, each smaller and brighter than the last. We adjust the center based on where the circle is on the screen, which generates the 3d effect.

Note how the for-loops around the call to the drawcircle() are nested in the render() function. What happens if you swap the two for-loops? Try it. (Hint: look at trees which are very close to each other. Put things back after you're done. If you have trouble finding problems, add more trees by changing the TREECOUNT).

Hm. But something is missing.. let's add shadows to those trees. Add the following block after the line that defines float pos_y:

float shadow_x = (float)sin(aTicks * 0.0002934872) * 16;
float shadow_y = (float)cos(aTicks * 0.0001813431) * 16;

for (int j = 0; j < TREECOUNT; j++)
{   
  float x = gTreeCoord[j * 2 + 0] + pos_x;
  float y = gTreeCoord[j * 2 + 1] + pos_y;
    
  for (int i = 0; i < 8; i++)
  {   
    drawcircle((int)(x * 200 + WINDOW_WIDTH / 2 + (i + 1) * shadow_x),
               (int)(y * 200 + WINDOW_HEIGHT / 2 + (i + 1) * shadow_y),
               (10 - i) * 5,
               0xff1f4f1f);
  }
}

Mm. Much better. It's too bad that the trees won't cast shadows on each other, but that's a limitation of this rendering method.

The above code draws the shadows using darker filled circles. It doesn't care about where on the screen the trees are, but simply moves the "higher" circles to the direction of the shadow vector.

Additional things to try:

• Adjust the number of trees.
• Try changing the colors.
• Make different sized trees.
• Play with blending - make different blending versions of the circle drawing function, and use those to draw the trees, and the shadows.
• Change the circle drawing function so that you can stretch the circle by x and y axis separately.
• Implement clipping in the sprite drawing function in the earlier chapters.
• Define light source position, and calculate the direction of each shadow separately based on that. Animate the light source position. Render it with a yellow circle.
• What other "pseudo-3d" objects can you make using simple circles? (sheep, people, buildings, clouds..)
• Look up Bresenham's circles and lines.
• Add mouse and/or keyboard control. Control the "camera position" or the light source position, or add a "player character" in, and control that.
• Make a top-down shoot-em-up.

Next up: 07 - Variations of 2d Bitmap Tunnels..

Any comments etc. can be emailed to me.