Line-Drawing AlgorithmsA Study in OptimizationMake it workMake it rightMake it fast Lecture 5 Slide 1 6.837 Fall '00Lecture 5 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture05/Slide01.html [9/21/2000 4:20:52 PM]Line-Drawing AlgorithmsOur first adventure into scan conversion.Scan-conversion or rasterization● Due to the scanning nature of raster displays● Algorithms are fundamental to both2-D and 3-D computer graphics● Transforming the continuous into this discrete(sampling)● Line drawing was easy for vector displays● Most incremental line-drawing algorithmswere first developed for pen-plotters● Most of the early scan-conversion algorithms developedfor plotters can be attributed to one man, Jack Bresenham.Lecture 5 Slide 2 6.837 Fall '00Lecture 5 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture05/Slide02.html [9/21/2000 4:21:01 PM]Quest for the Ideal LineThe best we can do is a discrete approximation of an ideal line.Important line qualities:Continuous appearence■ Uniform thickness and brightness■ Accuracy (Turn on the pixels nearest the ideal line)■ Speed (How fast is the line generated)■ Lecture 5 Slide 3 6.837 Fall '00Lecture 5 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture05/Slide03.html [9/21/2000 4:21:03 PM]Simple LineBased on the simple slope-intercept algorithm from algebray = m x + b public void lineSimple(int x0, int y0, int x1, int y1, Colorcolor) { int pix = color.getRGB(); int dx = x1 - x0; int dy = y1 - y0; raster.setPixel(pix, x0, y0); if (dx != 0) { float m = (float) dy / (float) dx; float b = y0 - m*x0; dx = (x1 > x0) ? 1 : -1; while (x0 != x1) { x0 += dx; y0 = Math.round(m*x0 + b); raster.setPixel(pix, x0, y0); } } } Lecture 5 Slide 4 6.837 Fall '00Lecture 5 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture05/Slide04.html [9/21/2000 4:21:05 PM]lineSimple( ) DemonstrationDraw a line by clicking and dragging on the pixel grid shown with the leftmouse button. An ideal line is displayed until the left button is released.Upon release a discrete approximation of the line is drawn on the displaygrid using the lineSimple() method described in the previous slide. Anideal line is then overlaid for comparison.The lineSimple() method:Does it work?Try various slopes.Lecture 5 Slide 5 6.837 Fall '00Lecture 5 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture05/Slide05.html [9/21/2000 4:21:06 PM]Let's Make it Work!Problem: lineSimple( ) does not give satisfactory results for slopes > 1Solution: symmetrypublic void lineImproved(int x0, int y0, int x1, int y1, Color color int pix = color.getRGB(); int dx = x1 - x0; int dy = y1 - y0; raster.setPixel(pix, x0, y0); if (Math.abs(dx) > Math.abs(dy)) { // slope < 1 float m = (float) dy / (float) dx; // compute slope float b = y0 - m*x0; dx = (dx < 0) ? -1 : 1; while (x0 != x1) { x0 += dx; raster.setPixel(pix, x0, Math.round(m*x0 + b)); } } else if (dy != 0) { // slope >= 1 float m = (float) dx / (float) dy; // compute slope float b = x0 - m*y0; dy = (dy < 0) ? -1 : 1; while (y0 != y1) { y0 += dy; raster.setPixel(pix, Math.round(m*y0 + b), y0); } }}Lecture 5 Slide 6 6.837 Fall '00Lecture 5 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture05/Slide06.html [9/21/2000 4:21:07 PM]lineImproved( ) DemonstrationDraw a line by clicking and dragging on the pixel grid shown with the leftmouse button. An ideal line is displayed until the left button is released.Upon release a discrete approximation of the line is drawn on the displaygrid using the lineImproved() method described in the previous slide. Anideal line is then overlaid for comparison.The lineImproved() method:Notice that the slope-intercept equation of the line is executed at each step of the inner loop.Lecture 5 Slide 7 6.837 Fall '00Lecture 5 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture05/Slide07.html [9/21/2000 4:21:07 PM]Optimize Inner LoopsOptimize those code fragments where the algorithm spends most of its time.Often these fragmentsare inside loops.Overall code organization: lineMethod( ) { // 1. general set up // 2. special case set up while (notdone) { // 3. inner loop } }remove unnecessary method invocationsreplace Math.round(m*x0 + b)with (int)(m*x0 + b + 0.5)Does this always work?● use incremental calculationsConsider the expressiony = (int)(m*x + b + 0.5)The value of y is known at x0 (i.e. it is y0 + 0.5)Future values of y can be expressed in terms ofprevious values with a difference equation:yi+1 = yi + m;oryi+1 = yi - m;● Lecture 5 Slide 8 6.837 Fall '00Lecture 5 --- 6.837 Fall '00http://graphics.lcs.mit.edu/classes/6.837/F00/Lecture05/Slide08.html [9/21/2000 4:21:08 PM]Modified AlgorithmThis line drawing method is called a Digital Differential Analyzer or DDA for short. public void lineDDA(int x0, int y0, int x1, int y1, Color color) { int pix = color.getRGB(); int dy = y1 - y0; int dx = x1 - x0; float t = (float) 0.5; // offset for rounding raster.setPixel(pix, x0, y0); if (Math.abs(dx) > Math.abs(dy)) { // slope < 1 float m = (float) dy / (float) dx; // compute slope t += y0; dx = (dx < 0) ? -1 : 1; m *= dx; while (x0 != x1) { x0 += dx; // step to next x value t += m; // add slope to y value raster.setPixel(pix, x0, (int) t); } } else { // slope >= 1 float m = (float) dx / (float) dy; // compute slope t += x0; dy = (dy < 0) ? -1 : 1; m *= dy; while (y0 != y1) { y0 += dy; // step to next y value t += m; // add slope to x value raster.setPixel(pix, (int) t, y0); } } }Lecture 5 Slide 9 6.837 Fall '00Lecture 5 --- 6.837 Fall
View Full Document
Unlocking...