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

#### Speeding Up the Algorithm

Looking at the code, you might think that it’s fairly tight and there’s no room for optimization. However, there are a couple of ways to speed up the algorithm. The first way is to take into consideration that all lines are symmetrical about their midpoints, as shown in Figure 8.5, so there’s no need to run the algorithm for the whole line. All you have to do is halve the line and copy the other half. In theory this is solid, but implementing it is a pain because you have to worry about lines that have an odd number of pixels and then decide to draw one extra pixel at either end. Not that it’s hard_just ugly.

Figure 8.5 Lines aresymmetrical about their midpoints.

The other optimizations have been discovered by a number of people (including myself), including Michael Abrash’s algorithm Run-Slicing, Xialon Wu’s Symmetric Double Step, and Rokne’s Quadruple Step. Basically, all these algorithms take advantage of the consistency of the pixel patterns that make up a line. The Run-Slicing algorithm takes advantage of the fact that sometimes large runs of pixels exist, such as the line (0,0) to (100,1). The line should consist of two runs of 50 pixels. One runs from (0-49,0) and the other runs from (50-100,1), as shown in Figure 8.6.

Figure 8.6 The Run-Slicing line drawing optimization.

So what’s the point in doing the line algorithm on each pixel? The problem is that the setup and the innards of the algorithm are very complex, but they work for lines with very large or very small slopes.

Wu’s Symmetric Double Step algorithm works on a similar premise, but instead of considering runs, it notes that for every two pixels there are only four different patterns that can occur, as shown in Figure 8.7. It’s fairly easy to compute the next pattern by looking at the error term and then plotting the entire pattern, in essence moving at twice normal speed. This, coupled with symmetry, gives you a speed increase of four times over the basic Bresenham algorithm. That’s the story.

Figure 8.7 Drawing lines using raster patterns.

> Note: If I decide you need a faster line, I’ll write it. But for now I’d like to keep things simple, so let’s move on to clipping.

For a demo of the line drawing function, take a look at `DEMO8_1.CPP|EXE`, which draws random lines in 640×480 mode.

### Basic 2D Clipping

There are two ways to clip computer images: at the image space level and at the object space level. Image space really means at the pixel level. When the image is being rasterized, there is a clipping filter that determines if a pixel is within the viewport. This is appropriate for plotting single pixels, but not for large objects such as bitmaps, lines, or polygons. For objects like those that have some geometry to them, you might as well take advantage of the extra information.

For example, if you’re writing a bitmap clipper, all you have to do is clip one rectangle against another; that is, clip your bitmap’s bounding rectangle to the viewport. The intersection of the two is the area that you need to blit.

Although you wouldn’t think so, lines are a little more difficult to clip. Take a look at Figure 8.8 to see the general problem of clipping a line to a rectangular viewport.

Figure 8.8 The general line clipping problem.

As you can see, there are four general cases:

  • Case 1—The line is completely outside the clipping region. This is the trivial rejection case, which is good!
  • Case 2—The line is completely inside the clipping region. In this case, no clipping is needed and the line can be passed to the rasterizer as is.
  • Case 3—One end of the line segment is outside the clipping region and must be clipped.
  • Case 4—Both ends of the line are outside the clipping region and must be clipped.

There are a number of known algorithms to clip lines, such as Cohen-Sutherland, Cyrus-Beck, and so on. But before you take a look at any full clipping algorithms, let’s see if you can figure it out yourself!

Given that you have a line (x0,y0) to (x1,y1) in 2D space, along with a viewport defined by the rectangle (rx0, ry0) to (rx1, ry1), you want to clip all lines to this region. So what you need is a preprocessor—or clipping filter, if you will—that takes the input values (x0,y0), (x1,y1), (rx0,ry0), and (rx1,ry1) and outputs a new line segment, (x0’,y0’) to (x1’,y1’), that represents the new line. This process is shown in Figure 8.9. Looking at this problem, the first thing you should notice is that at some point you’re going to have to compute the intersection of two lines. Alas, this is a fundamental problem you need to figure out right off the bat, so you might as well start there.

Figure 8.9 The clipping process diagrammed.

Basically, the line segment from (x0,y0) to (x1,y1) will intersect either the left, right, top, or bottom edge of the clipping rectangle. This means that at least you don’t have to find the intersection of two arbitrarily oriented lines since the line being rasterized will always intersect either a vertical or horizontal line. Knowing this may or may not help, but it’s worth noting. To compute the intersection of two lines, there are a number of methods, but they are all based on the mathematical form of the lines.

In general, lines can take these general forms:

> Tip: If you’re uneasy with the parametric form, don’t worry. I’ll explain parametric equations shortly. In addition, Note that the Point Slope form and the Two Point form are really the same because in both cases m = (y1 – y0)/(x1 – x0).

    Y-Intercept Form:     y=m*x+b

    Point Slope:        (y–y0)=m*(x–x0)

    Two Point Form:    (y–y0)=(x–x0)*(y1–y0)/(x1–x0)

    General Form:        a*x+b*y=c

    *Parametric Form:    P=p0+V*t

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.