mit.eduLecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '01Lecture 4 --- 6.837 Fall '016.837 LECTURE 41.Line-Drawing Algorithms2.Line-Drawing Algorithms3.Quest for the Ideal Line4.Simple Line5.lineSimple( ) Demonstration6.Let's Make it Work!7.lineImproved( ) Demonstration8.Optimize Inner Loops9.Modified Algorithm10.lineDDA( ) Demonstration11.Was Our Objective Met?12.Low-Level Optimizations13.Applications of Low-level Optimizations13a.Geometric Interpretation14.More Low-level Optimizations15.More Low-level Optimizations16.The resulting method is known as Bresenham's line drawing algorithm17.lineBresenham( ) Demonstration18.Was it worth it?19.Question Infrastructure20.Faster Bresenham Algorithm21.Was it worth it?22.Beyond Bresenham23.Was it worth it?24.Epilogue25.A Line in Sheep's Clothing26.The Plot Thickens...27.Generalized Pull Down28.Next Time Lecture 4 Outline 6.837 Fall '01Lecture 4 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture04/index.html [9/20/2001 5:29:05 PM]Line-Drawing AlgorithmsA Study in OptimizationMake it workMake it rightMake it fast Lecture 4 Slide 1 6.837 Fall '01Lecture 4 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture04/Slide01.html [9/20/2001 5:29:18 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 4 Slide 2 6.837 Fall '01Lecture 4 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture04/Slide02.html [9/20/2001 5:29:20 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 4 Slide 3 6.837 Fall '01Lecture 4 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture04/Slide03.html [9/20/2001 5:29:41 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 4 Slide 4 6.837 Fall '01Lecture 4 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture04/Slide04.html [9/20/2001 5:29:43 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 4 Slide 5 6.837 Fall '01Lecture 4 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture04/Slide05.html [9/20/2001 5:29:44 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 4 Slide 6 6.837 Fall '01Lecture 4 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture04/Slide06.html [9/20/2001 5:29:46 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 4 Slide 7 6.837 Fall '01Lecture 4 --- 6.837 Fall '01http://www.graphics.lcs.mit.edu/classes/6.837/F01/Lecture04/Slide07.html [9/20/2001 5:29:47 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.
View Full Document
Unlocking...