RuTh's
RuThLEss
HomEpAgE


* INDEX *
3D game todo list *
3D Engine todo list
( chapter
1,
2,
3,
4,
5,
6,
7 ) *
* projection formula * transformation matrices * Bresenham algorithm * Scanline Polygonfill algorithm * * Spieldesign / game design * Troubleshooting 3D * Irrlicht 3D engine * Blender for Beginners * Bresenham line algorithm in Cocoa (Objective C)
Bresenham's line algorithm draws a line from (x1,y1) to (x2,y2) into our custom framebuffer MYDraw.
The algorithm is used to draw the wireframe portion of your 3D objects and it replaces Cocoa's The ideal line is infinitly thin, but on the screen, we need to approximate lines with a row of stairstepping pixels. Obviously we are bound to lose some precision, which however is no big deal, since a 3Dgame is not rocket science. The trick is to calculate which individual pixels have to be switched on or off to create the impression of a line on the screen. To do that, we need to know the exact angle of the line. The Slope of a LineThe angle of a line is called the slope. The slope tells us how far the line from (x1,y1) to (x2,y2) moves vertically (in y) for every pixel it moves horizontally (in x). Mathematically, we need the distance between the y coordinates (dy = y2  y1) divided by the distance between the x coordinates (dx = x2  x1). Here is the formula to calculate the slope: dy = (y2  y1) dx = (x2  x1) slope = (dy / dx) = (y2  y1) / (x2  x1)In the example image above, the line goes from (1,2) to (4,8). That's all we need to know to calculate its slope: dy = 82 = 6 dx = 41 = 3 slope = 6/3 = 2A slope of 2 means, for each 2 pixels that you move down (vertically), you move 1 pixel to the right (horizontally). Note: If instead, for each 6 pixels you move down, you move 3 to the right, then you end up drawing exactly the same line! You can do either. Here is a list of cases we have to consider.
Keeping the Slope Under Control: The "Error Term"Bresenham's clever solution of the line drawing problem consisted in using a variable as an error term. It also distinguishes two cases, lines that are more horizontal than vertical, and lines that are more vertical than horizontal. In the first case, the next pixel will always be plotted to somewhere the right side of the previous one, resulting in a rather flat line. In the second case, the next pixel is always plotted somewhere below the previous one, resulting in a steeply falling line (look at the steeply falling line in the example picture). Each time we approximate the shape of the line by placing a pixel, we make a tiny error: Obviously, a plump square pixel can't get the slope of the ideal line perfectly right. Bresenham uses the error_term variable to keep track of these small errors, because as soon as they sum up, he knows he will have to correct them. In our example line from (1,2) to (4,8), we know, for each 2 pixels the line moves down, it moves 1 pixel to the right; its dy = 3 and its dx = 6. Lets step through the algorithm.
The Bresenham line algorithm works similarly for a flat line that's more horizontal than vertical — the steps are just the other way round. In flatline case, the next pixel is always plotted to the right side of the previous pixel. If the error caused by that approximation requires correction, the next pixel is additionally moved one step below the previous. If you look closely you will see, that the algorithm also provides for dealing with negative slopes, by using the variables xDirection and yDirection, which can be negative or positive to make the steps go to the left or right, or up or down as needed. This way, the algorithm can even handle horizontal and vertical lines: It just sets xDirection and yDirection to zero. Another nice thing is that the algorithm never needs to calculate the actual slope; it works only with dx and dy. This is very efficient since it spares us several slow division operations. ImplementationBresenham's line algorithm draws a line from (x1,y1) to (x2,y2) into our custom (MYDraw*) framebuffer. It relies on the argument ppr (number of pixels per row in the framebuffer), and needs to know the line's color. @implementation Bresenham + (void) drawLineX1:(short)x1 y1:(short)y1 x2:(short)x2 y2:(short)y2 buffer:(MYDraw*) mybuffer ppr:(int)ppr color:(NSColor*)color { int dx, dy, xDirection, yDirection, i; int rowOffset; int pixelOffset; int error_term; // the absolute x and y distances for this line dx = x2  x1; if (dx < 0) dx = dx; dy = y2  y1; if (dy < 0) dy = dy; // the horizontal direction of the line (moving left or right?) if (x2  x1 < 0) { xDirection = 1; /* Moving left */ } else if (x2  x1 > 0) { xDirection = 1; /* Moving right */ } else { xDirection = 0; /* vertical line! */ } /* the vertical direction of the line (moving up or down?) */ if (y2  y1 < 0) { yDirection = 1; rowOffset = ppr; /* Subtract ppr to move up a line */ } else if (y2  y1 > 0) { yDirection = 1; rowOffset = ppr; /* Add ppr to move down a line */ } else { yDirection = 0; rowOffset = 0; /* horizontal line! */ } /* Initialize the error term */ error_term = 0; /* Calculate where the first pixel will be placed */ pixelOffset = (y1*ppr) + (x1); /* the drawing loop */ if (dx > dy) { /* Line is more horizontal than vertical (x>y) */ for (i = 0; i <= dx; i++) { // Draw this pixel [mybuffer setPixel:pixelOffset to:color]; // Move the pixelOffset 1 pixel left or right. (x) pixelOffset += xDirection; // Time to move pixelOffset up or down? (y) error_term += dy; if (error_term > dx) { /* Yes. Reset the error term */ error_term = dx; /* And move the pixelOffset 1 pixel up or down */ pixelOffset += rowOffset; } } } else { // Line is more vertical than horizontal: (y>x). for (i = 0; i <= dy; i++) { // Draw this pixel [mybuffer setPixel:pixelOffset to:color]; // Move pixelOffset up or down. (y) pixelOffset += rowOffset; // Time to move pixelOffset left or right? (x) error_term += dx; if (error_term > dy) { /* Yes. Reset the error term */ error_term = dy; /* And move the pixelOffset 1 pixel left or right */ pixelOffset += xDirection; } } } } CallThe Bresenham algorithm is called from MYDraw. MYDraw has a method [MYDraw drawWireframePolygon] replacing [NSBezierPath stroke]. (void) drawWireframePolygon { // Bresenham line drawing algorithm // call drawWireframePolygon after closePath int i, x1,y1,x2,y2; for( i = 0; i < vertexNum1; i++) { x1 = [[vertexListX objectAtIndex:i] intValue]; y1 = [[vertexListY objectAtIndex:i] intValue]; x2 = [[vertexListX objectAtIndex:i+1] intValue]; y2 = [[vertexListY objectAtIndex:i+1] intValue]; [Bresenham drawLineX1:x1 y1:y1 x2:x2 y2:y2 buffer:self ppr:ppr color:color]; } } 

http://www.ruthless.zathras.de/ 