Tricks of the Windows Game Programming Gurus:Vector Rasterization and 2D Transformations

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

## Chapter 8
Vector Rasterization and 2D Transformations

> “There are a lot worse things out than vampires tonight…”

> —Blade

This chapter will cover vector topics, such as how to draw lines and polygons, and will show you how to finish off the first module of the T3DLIB game library. This is the first chapter that pours on the math, but if you take your time, there shouldn’t be anything you can’t handle with a little effort. About the hardest thing I’m going to talk about is matrices. (It’s just an introduction so that when you get to the 3D chapters, matrix math won’t look totally alien.) Also, by popular request, I’m going to give you some ideas on how to do scrolling and even isometric 3D engines. Remember, this is a 3D book, so I have to save pages for the 3D stuff! However, anything that I don’t have room for here will be covered on the CD itself. Here’s the hit list for this chapter:

  • Drawing lines
  • Clipping
  • Matrices
  • 2D transformation
  • Drawing polygons
  • Scrolling and ISO 3D engines
  • Timing
  • The T3DLIB version 1.0

### Drawing Lines

Up to this point, you’ve drawn all of your graphical objects with either single points or bitmaps. Both of these entities are considered non-vector entities. A vector entity is something like a line or a polygon, as shown in Figure 8.1. So your first problem is figuring out how to draw a line.

Figure 8.1 A vector/line-based object.

You may think that drawing a line is trivial, but I assure you it’s not. Drawing a line on a computer screen has a number of problems associated with it, such as finite resolution, mapping real numbers onto an integer grid, speed issues, and so forth. In many cases, a 2D or 3D image is composed of a number of points that define the polygons or faces that make up an object or scene. These points are usually in the form of real numbers, such as (10.5, 120.3) and so on.

The first problem is that a computer screen is represented by a 2D grid of whole numbers, so plotting (10.5, 120.3) is almost impossible. You can only approximate it. You might decide to truncate the coordinates and plot (10,120), or you might decide to round them and plot (11,120). Finally, you might go high-tech and decide to perform a weighted pixel plotting function that plots a number of pixels of differing intensities centered at the pixel center (10.5, 120.3), as shown in Figure 8.2.

Figure 8.2 Area filtering a single pixel.

Basically, an area filter computes how much the original pixel overlaps into the other pixel positions and then draws those pixels in the same color as the desired pixel, but with decreased intensity. This creates a much rounder-looking pixel that looks anti-aliased, but in general you have lowered your maximum resolution.

Instead of me jabbering on about line-drawing algorithms, filtering, and such, let’s get to the cream pie and see a couple of really good line-drawing algorithms that you can use to compute the integer coordinates of a line from (x0,y0) to (x1,y1).

#### Bresenham’s Algorithm

The first algorithm I want to present you with is called Bresenham’s algorithm, named after the man who invented it in 1965. Originally, the algorithm was designed to draw lines on plotters, but it was later adapted to computer graphics. Let’s take a quick look at how the algorithm works and then see some code. Figure 8.3 shows the general problem you’re trying to solve. You want to fill in the pixels from point p1 to p2 with the pixels that most closely fit to the real line. This process is called rasterization.

Figure 8.3 Rasterizing a line.

If you’re a little rusty on lines, let me refresh your memory. The slope of a line is related to the angle that the line makes with the x-axis. Hence, a line with slope 0 is totally horizontal, while a line with infinite slope is totally vertical. A line with slope 1.0 is diagonal or 45 degrees. Slope is defined as rise over run, or, mathematically:

             Rise     Change in y   dy        (y1–y0)

    Slope = ------ = ------------- ---- = m = ---------

             Run      Change in x   dx        (x1–x0)

For example, if you have a line with coordinates p0(1,2) and p1(5,22), the slope or m is:

    (y2–y1)/(x2–x1) = (22–2)/(5–1) = 20/4 = 5.0

So what does the slope really mean? It means that if you increment the x-coordinate by 1.0 unit, the y-coordinate will change by 5.0 units. Okay, this is the beginning of a rasterization algorithm. At this point, you have a rough idea of how to draw a line:

  1. Compute the slope m.
  2. Plot (x0,y0).
  3. Advance x by 1.0 and then advance y by the slope m. Add this value to (x0,y0).
  4. Repeat steps 2-4 until done.

Figure 8.4 shows this example for the previous values of p0 and p1.

Figure 8.4 A first attempt at rasterization.

Do you see the problem? Every time you step one pixel in x, you step 5.0 pixels in y. Therefore, you’re drawing a line that has a lot of holes in it! The mistake you’re making is not tracing a line, but plotting pixels as integer intervals; that is, whenever x is a whole number. In essence, you’re plugging whole numbers into the equation of a line:

    (y–y0) = m*(x–x0)

Here, (x,y) are the current values or pixel locations, (x0,y0) is the starting point, and m is the slope. Rearranging this a little, you have

    y = m*(x–x0)+y0

So, if you let (x0,y0) be (1,2) and m be 5 as in the example, you get the following results:

    x        y = 5*(x–1)+2

    -----------------------------

    1        2 (starting point)

    2        7

    3        12

    4        17

    5        22 (ending point)

Now, you might ask if the slope-intercept form of a line can help:

    y = m*x + b

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.