1MIT EECS 6.837, Teller and Durand1Line RasterizationMIT EECS 6.837Frédo Durand and Seth TellerMIT EECS 6.837, Teller and Durand2Administrative• Prof. Teller office hours today: 5-6 in 4-035 • Assignment 2– Due Friday 27 at 5pm– Model a scene using iv files from assignt 1– Lighting: at least one spot and one other light– You are welcome to add new geometry– Pay attention to the requirements!– Shadows are challenging! (and no required)MIT EECS 6.837, Teller and Durand3Review of previous lecture?• What did we learn?• Where was the “magic”? What were the insights?MIT EECS 6.837, Teller and Durand4Review of previous lecture?• What did we learn?• Where was the “magic”? What were the insights?– Graphics is a lot about interpolation/extrapolation– Convexity is important– Planes as homogeneous coordinates & dot product– Outcodes– Orienting edges of polygons• Questions?MIT EECS 6.837, Teller and Durand5Overview of graphics pipeline?TraverseGeometricModelTransform toWorld spaceApply lightingEquation at verticesTransform toEye spacePerspective transformto NDCClipTransform to 3DScreen spaceRasterizeResolvevisibility3D SceneDatabaseCamera+Viewport Parameters2D Framebuffer ValuesMIT EECS 6.837, Teller and Durand6Today’s lecture: line rasterization• Overview of rasterization• Naïve line rasterization • Bresenham DDA• Scanline and active edge list(x1, y1)(x2, y2)ENEMy2MIT EECS 6.837, Teller and Durand7Framebuffer Model• Raster Display: 2D array of picture elements (pixels)• Pixels individually set/cleared (greyscale, color)• Window coordinates: pixels centered at integers(x1,y1)(x2,y2)MIT EECS 6.837, Teller and Durand82D Scan Conversion• Geometric primitive– 2D: point, line, polygon, circle...– 3D: point, line, polyhedron, sphere...• Primitives are continuous; screen is discreteMIT EECS 6.837, Teller and Durand92D Scan Conversion• Solution: compute discrete approximation• Scan Conversion: algorithms for efficient generation of the samples comprising this approximationMIT EECS 6.837, Teller and Durand10Brute force solution for triangles•?MIT EECS 6.837, Teller and Durand11Brute force solution for triangles• For each pixel– Compute line equations at pixel center– “clip” against the triangleProblem?MIT EECS 6.837, Teller and Durand12Brute force solution for triangles• For each pixel– Compute line equations at pixel center– “clip” against the triangleProblem?If the triangle is small, a lot of useless computation3MIT EECS 6.837, Teller and Durand13Brute force solution for triangles• Improvement:– Compute only for the screen bounding box of the triangle– How do we get such a bounding box?MIT EECS 6.837, Teller and Durand14Brute force solution for triangles• Improvement:– Compute only for the screen bounding box of the triangle– Xmin, Xmax, Ymin, Ymax of the triangle verticesMIT EECS 6.837, Teller and Durand15Can we do better? Yes!• Plus, how do we rasterize lines using this approach?• Efficient rasterization is the topic of the following two lecturesMIT EECS 6.837, Teller and Durand16Rasterization• Line rasterization– This lectureShirley page 55MIT EECS 6.837, Teller and Durand17Rasterization• Line rasterization– This lecture• Polygon filling, interpolation, visibility–TuesdayShirley page 55MIT EECS 6.837, Teller and Durand18Rasterization• There are subtle differences between rasterizing a segment, and rasterizing the boundary of a polygon• Important for assignment 3 & 44MIT EECS 6.837, Teller and Durand19Today’s lecture: line rasterization• Overview of rasterization• Naïve line rasterization • Bresenham DDA• Scanline and active edge list(x1, y1)(x2, y2)ENEMyMIT EECS 6.837, Teller and Durand20Scan Converting 2D Line Segments•Given:– Segment endpoints (integers x1, y1; x2, y2)• Identify:– Set of pixels x; y to “light up” for segment(x1, y1)(x2, y2)MIT EECS 6.837, Teller and Durand21Algorithm Design Choices• For m = dy/dx• Assume: 0 < m < 1 • Why?(x1, y1)(x2, y2)MIT EECS 6.837, Teller and Durand22Algorithm Design Choices• Exactly one pixel per column – Why?(x1, y1)(x2, y2)MIT EECS 6.837, Teller and Durand23Algorithm Design Choices• Exactly one pixel per column– fewer => disconnected– more =>too thick– “connectedness" with just 1 pixel per column(x1, y1)(x2, y2)MIT EECS 6.837, Teller and Durand24Algorithm Design Choices• Note: brightness can vary with slope– What is the maximum variation?5MIT EECS 6.837, Teller and Durand25Algorithm Design Choices• Note: brightness can vary with slope– What is the maximum variation? • How could we compensate for this?– Answer: antialiasing (wait until November…)2MIT EECS 6.837, Teller and Durand26Naive algorithm, 1st attempt • Simply compute y as a function of x– Conceptually: move vertical scan line from x1 to x2– What is the expression of y as function of x ?xy(x1, y1)(x2, y2)MIT EECS 6.837, Teller and Durand27Naive algorithm, 1st attempt • Simply compute y as a function of x– Conceptually: move vertical scan line from x1 to x2– What is the expression of y as function of x ?xy(x1, y1)(x2, y2))1(1 xxmy −+=)12(1211 yyxxxxyy −−−+=dxdym =MIT EECS 6.837, Teller and Durand28Naive algorithm, 1st attempt• Simply compute y as a function of x• Round y (Why?)• Set pixel (x, rnd(y(x)))xy(x1, y1)(x2, y2))1(1 xxmy−+=)12(1211 yyxxxxyy −−−+=dxdym =MIT EECS 6.837, Teller and Durand29Efficiency• Computing y values is expensive• Observe: y += m at each x step (m = dy/dx)• First example of spatial coherence)1(1 xxmyy−+=y(x+1)y(x)xx+1mxy(x)(x1, y1)(x2, y2)y(x+1)x+1MIT EECS 6.837, Teller and Durand30Incremental algorithm• Start at (x1; y1)• Thereafter, increment y value by slope m• Note: x integer, but y floating pointy(x+1)y(x)xx+1mxy(x)(x1, y1)(x2, y2)y(x+1)x+16MIT EECS 6.837, Teller and Durand31Questions?MIT EECS 6.837, Teller and Durand32Today’s lecture: line rasterization• Overview of rasterization• Naïve line rasterization • Bresenham DDA• Scanline and active edge list(x1, y1)(x2, y2)ENEMyMIT EECS 6.837, Teller and Durand33Bresenham's algorithm• Select pixel vertically closest to segment• Justification: intuitive, efficient• Also: pixel center always within 0.5 vertically•Is selection criterion well-defined ?•What other rules could we have used?MIT EECS 6.837, Teller and Durand34Bresenham DDA• DDA = Digital Differential
View Full Document
Unlocking...