Sol's Graphics for Beginners

(ch06.cpp)

(prebuilt win32 exe)

06 - Primitives and Clipping

(last revised 8. August 2005)

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 antialiasing 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 'idealized' 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. There, now you know. So, in order to scan convert a circle, we need to find out the left and right coordinates of every scanline 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.

For this tutorial, I opted to come up with something weird that gives me the circle's width based on the y coordinate.

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.

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

Anyway, I won't get deeper into how I ended up with the function; you'll just have to believe me that when fed with the 'y' coordinate (from 0 to 2*r-1) of a circle with radius 'r', you get the width. Note that there are better and faster algorithms around (Bresenham), but this'll do for our purposes. In C, our little function turns into sqrt(cos(0.5f * PI * (y - r) / r)) * r * 2.

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(cos(0.5f * PI * (i - r) / r)) * r * 2);
    int ofs = (y - r + i) * PITCH + x - len / 2;
    for (j = 0; j < len; j++)
      ((unsigned int*)screen->pixels)[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.1415926535897932384626433832795f

void drawcircle(int x, int y, int r, int c)
{
  int i, j;
  for (i = 0; i < 2 * r; i++)
  {
    // vertical clipping: (top and bottom)
    if ((y - r + i) >= 0 && (y - r + i) < 480)
    {
      int len = (int)(sqrt(cos(0.5f * PI * (i - r) / r)) * r * 2);
      int xofs = x - len / 2;
      
      // left border
      if (xofs < 0)
      {
        len += xofs;
        xofs = 0;
      }
      
      // right border
      if (xofs + len >= 640)
      {
        len -= (xofs + len) - 640;
      }
      int ofs = (y - r + i) * PITCH + xofs;
      
      // note that len may be 0 at this point, 
      // and no pixels get drawn!
      for (j = 0; j < len; j++)
        ((unsigned int*)screen->pixels)[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 versions 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 ch04 or ch05 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, under the "#define PITCH" line. 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.

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

#define TREECOUNT 64

float xy[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();
    xy[i * 2 + 0] = ((x % 10000) - 5000) / 1000.0f;
    xy[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 xy array. 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()
{   
  // Lock surface if needed
  if (SDL_MUSTLOCK(screen))
    if (SDL_LockSurface(screen) < 0) 
      return;

  // Clear the screen with a green color
  int i, j;
  for (i = 0; i < 480; i++)
  {
    for (j = 0; j < 640; j++)
    {
      *(((unsigned long*)screen->pixels) + i * PITCH + j) = 0x005f00;
    }
  }
         
  // Ask SDL for the time in milliseconds
  int tick = SDL_GetTicks();
  
  float pos_x = (float)sin(tick * 0.00037234f) * 2;
  float pos_y = (float)cos(tick * 0.00057234f) * 2;
 
  for (i = 0; i < 8; i++)
  {   
    for (j = 0; j < TREECOUNT; j++)
    {
      float x = xy[j * 2 + 0] + pos_x;
      float y = xy[j * 2 + 1] + pos_y;
      drawcircle((int)(x * (200 + i * 4) + 320),
                 (int)(y * (200 + i * 4) + 240),
                 (9 - i) * 5,
                 i * 0x030906 + 0x1f671f);
    }
  }
        
  // Unlock if needed
  if (SDL_MUSTLOCK(screen)) 
    SDL_UnlockSurface(screen);

  // Tell SDL to update the whole screen
  SDL_UpdateRect(screen, 0, 0, 640, 480);    
}

Compile and run.

In the render() function we're first clearing the screen with 0x005f00, 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(tick * 0.0002934872f) * 16;
  float shadow_y = (float)cos(tick * 0.0001813431f) * 16;

  for (j = 0; j < TREECOUNT; j++)
  {   
    float x = xy[j * 2 + 0] + pos_x;
    float y = xy[j * 2 + 1] + pos_y;
    
    for (i = 0; i < 8; i++)
    {   
      drawcircle((int)(x * 200 + 320 + (i + 1) * shadow_x),
                 (int)(y * 200 + 240 + (i + 1) * shadow_y),
                 (10 - i) * 5,
                 0x1f4f1f);
    }
  }

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? (dogs, people, buildings..)
• 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.

Let's start building a game in the part B of this tutorial series..

Having problems? Improvement ideas? Just want to discuss this tutorial? Try the forums!

Any comments etc. can be emailed to me.