MIT EECS 6.837, Cutler and Durand 1 RasterizationMIT EECS 6.837Frédo Durand and Barb CutlerMIT EECS 6.837, Cutler and Durand 2 Final projects•Rest of semester–Weekly meetings with TAs–Office hours on appointment•This week, with TAs–Refine timeline–Define high-level architecture•Project should be a whole, but subparts should be identified with regular merging of codeMIT EECS 6.837, Cutler and Durand 3 The Graphics PipelineModeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayMIT EECS 6.837, Cutler and Durand 4 Modeling Transformations•3D models defined in their own coordinate system (object space)•Modeling transforms orient the models within a common coordinate frame (world space)Modeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayObject spaceWorld spaceMIT EECS 6.837, Cutler and Durand 5 Illumination (Shading) (Lighting)•Vertices lit (shaded) according to material properties, surface properties (normal) and light sources•Local lighting model (Diffuse, Ambient, Phong, etc.)Modeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayMIT EECS 6.837, Cutler and Durand 6 Viewing Transformation•Maps world space to eye space•Viewing position is transformed to origin & direction is oriented along some axis (usually z)Modeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /Display P NEAR v u -n o FAR z y x o EYE Seth Teller Image adapted from: WORLD SPACE EYE SPACEMIT EECS 6.837, Cutler and Durand 7 ClippingModeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /Display•Transform to Normalized Device Coordinates (NDC) •Portions of the object outside the view volume (view frustum) are removed NEAR EYE FAR y z z x y x o Seth Teller Image adapted from: EYE SPACE NDCMIT EECS 6.837, Cutler and Durand 8 Projection•The objects are projected to the 2D image place (screen space)Modeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /Display y y x x z z o NDC SCREEN SPACE Seth Teller Image adapted from:MIT EECS 6.837, Cutler and Durand 9 Scan Conversion (Rasterization)•Rasterizesobjects into pixels•Interpolate values as we go (color, depth, etc.)Modeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayMIT EECS 6.837, Cutler and Durand 10 Visibility /Display•Each pixel remembers the closest object (depth buffer)•Almost every step in the graphics pipeline involves a change of coordinate system. Transformations are central to understanding 3D computer graphics.Modeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayMIT EECS 6.837, Cutler and Durand 11 Today•Polygon scan conversion–smart–back to brute force•VisibilityMIT EECS 6.837, Cutler and Durand 12 2D Scan Conversion•Geometric primitive–2D: point, line, polygon, circle...–3D: point, line, polyhedron, sphere...•Primitives are continuous; screen is discreteMIT EECS 6.837, Cutler and Durand 13 2D Scan Conversion•Solution: compute discrete approximation•Scan Conversion: algorithms for efficient generation of the samples comprising this approximationMIT EECS 6.837, Cutler and Durand 14 Brute force solution for triangles•?MIT EECS 6.837, Cutler and Durand 15 Brute force solution for triangles•For each pixel–Compute line equations at pixel center–“clip” against the triangleProblem?MIT EECS 6.837, Cutler and Durand 16 Brute 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 computationMIT EECS 6.837, Cutler and Durand 17 Brute force solution for triangles•Improvement:–Compute only for the screen bounding boxof the triangle–How do we get such a bounding box?MIT EECS 6.837, Cutler and Durand 18 Brute force solution for triangles•Improvement:–Compute only for the screen bounding boxof the triangle–Xmin, Xmax, Ymin, Ymaxof the triangle verticesMIT EECS 6.837, Cutler and Durand 19 Can we do better? Kind of! •We compute the line equation for many useless pixels•What could we do?MIT EECS 6.837, Cutler and Durand 20 Use line rasterization•Compute the boundary pixelsShirley page 55MIT EECS 6.837, Cutler and Durand 21 Scan-line Rasterization•Compute the boundary pixels•Fill the spansShirley page 55MIT EECS 6.837, Cutler and Durand 22 Scan-line Rasterization•Requires some initial setup to prepare Shirley page 55MIT EECS 6.837, Cutler and Durand 23 Clipping problem•How do we clip parts outside window?MIT EECS 6.837, Cutler and Durand 24 Clipping problem•How do we clip parts outside window?•Create two triangles or more. Quite annoying.MIT EECS 6.837, Cutler and Durand 25 Old style graphics hardware•Triangles were big•Bresenham+interpolationis worth it•Annoying clipping step•+ a couple of otherthings have changed•Not that good to parallelize beyond triangle granularityMIT EECS 6.837, Cutler and Durand 26 Questions?MIT EECS 6.837, Cutler and Durand 27 Today•Polygon scan conversion–smart–back to brute force•VisibilityMIT EECS 6.837, Cutler and Durand 28 For modern graphics cards•Triangles are usually very small•Setup cost are becoming more troublesome•Clipping is annoying •Brute force is tractableMIT EECS 6.837, Cutler and Durand 29 Modern rasterizationFor every triangleComputeProjectionCompute bbox, clip bboxto screen limitsFor all pixels in bboxCompute line equationsIf all line equations>0 //pixel [x,y] in triangleFramebuffer[x,y]=triangleColorMIT EECS 6.837, Cutler and Durand 30 Modern rasterizationFor every triangleComputeProjectionCompute bbox, clip bboxto screen limitsFor all pixels in bboxCompute line equationsIf all line equations>0 //pixel [x,y] in triangleFramebuffer[x,y]=triangleColor•Note that Bboxclipping is trivialMIT EECS 6.837, Cutler and Durand 31 Can we do better?For every triangleComputeProjectionCompute bbox, clip bboxto screen limitsFor all pixels in bboxCompute line equationsIf all line equations>0 //pixel [x,y] in triangleFramebuffer[x,y]=triangleColorMIT EECS 6.837, Cutler and Durand 32 Can we do better?For every triangleComputeProjectionCompute bbox, clip bboxto screen limitsFor all pixels in bboxCompute line equations ax+by+cIf all line equations>0 //pixel [x,y] in triangleFramebuffer[x,y]=triangleColor•We don’t need to recomputeline equation from scratchMIT EECS 6.837, Cutler and Durand 33 Can we do better?For every triangleComputeProjectionCompute bbox, clip bboxto screen limitsSetup line eqcompute aidx, bidyfor the 3 linesInitialize line eq, values for bboxcornerLi=aix0+biy+ciFor all scanliney in bboxFor 3 lines, update LiFor all x in bboxIncrement line equations: Li+=adxIf all Li>0 //pixel [x,y] in triangleFramebuffer[x,y]=triangleColor•We save one multiplication per pixelMIT EECS 6.837, Cutler and Durand 34 The Graphics PipelineModeling Transformations•Modern hardware mostly avoids clipping•Only with respect to plane z=0Illumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayMIT EECS 6.837, Cutler and Durand 35 Full Clipping(eyex, eyey, eyez)image planez axis"clip" geometry to view frustumMIT EECS 6.837, Cutler and Durand 36 One-plane clipping(eyex, eyey, eyez)image planez axis"clip" geometry to near planeMIT EECS 6.837, Cutler and Durand 37 Adding Gouraudshading•Interpolate colors of the 3 vertices•Linear interpolationMIT EECS 6.837, Cutler and Durand 38 Adding Gouraudshading•Interpolate colors of the 3 vertices•Linear interpolation, e.g. for R channel:–R=aRx+bRy+cR–Such that R[x0,y0]=R0; R[x1, y1]=R1; R[x2,y2]=R2–Same as a plane equation in (x,y,R)MIT EECS 6.837, Cutler and Durand 39 Adding GouraudshadingInterpolate colors For every triangleComputeProjectionCompute bbox, clip bboxto screen limitsSetup line eqSetup color equationFor all pixels in bboxIncrement line equationsIncrement color equationIf all Li>0 //pixel [x,y] in triangleFramebuffer[x,y]=interpolatedColorMIT EECS 6.837, Cutler and Durand 40 In the modern hardware•Edge eq. in homogeneous coordinates [x, y, w]•Tiles to add a mid-level granularity–early rejection of tiles–Memory access coherenceMIT EECS 6.837, Cutler and Durand 41 Ref•Henry Fuchs, Jack Goldfeather, Jeff Hultquist, Susan Spach, John Austin, Frederick Brooks, Jr., John Eylesand John Poulton, “Fast Spheres, Shadows, Textures, Transparencies, and Image Enhancements in Pixel-Planes”, Proceedings of SIGGRAPH ‘85 (San Francisco, CA, July 22–26, 1985). In Computer Graphics, v19n3 (July 1985), ACM SIGGRAPH, New York, NY, 1985.•Juan Pineda, “A Parallel Algorithm for Polygon Rasterization”, Proceedings of SIGGRAPH ‘88 (Atlanta, GA, August 1–5, 1988). In Computer Graphics, v22n4 (August 1988), ACM SIGGRAPH, New York, NY, 1988. Figure 7: Image from the spinning teapot performance test.•Triangle Scan Conversion using 2D Homogeneous Coordinates, Marc OlanoTrey Greerhttp://www.cs.unc.edu/~olano/papers/2dh-tri/2dh-tri.pdfMIT EECS 6.837, Cutler and Durand 42 Take-home message•The appropriate algorithm depends on–Balance between various resources (CPU, memory, bandwidth)–The input (size of triangles, etc.)•Smart algorithms often have initial preprocess–Assess whether it is worth it•To save time, identify redundant computation–Put outside the loop and interpolate if neededMIT EECS 6.837, Cutler and Durand 43 Today•Polygon scan conversion–smart–back to brute force•VisibilityMIT EECS 6.837, Cutler and Durand 44 Visibility•How do we know which parts are visible/in front?MIT EECS 6.837, Cutler and Durand 45 Ray Casting•Maintain intersection with closest objectMIT EECS 6.837, Cutler and Durand 46 Painter’s algorithm•Draw back-to-front•How do we sort objects?•Can we always sort objects?1254367MIT EECS 6.837, Cutler and Durand 47 Painter’s algorithm•Draw back-to-front•How do we sort objects?•Can we always sort objects?–No, there can be cycles–Requires to split polygonsABCABMIT EECS 6.837, Cutler and Durand 48 Painter’s algorithm•Old solution for hidden-surface removal–Good because ordering is useful for other operations (transparency, antialiasing)•But–Ordering is tough–Cycles–Must be done by CPU•Hardly used now•But some sort of partial ordering is sometimes useful–Usuallfront-to-back–To make sure foreground is rendered firstMIT EECS 6.837, Cutler and Durand 49 visibility•In ray casting, use intersection with closest t•Now we have swapped the loops (pixel, object)•How do we do?MIT EECS 6.837, Cutler and Durand 50 Z buffer•In addition to frame buffer (R, G, B)•Store distance to camera (z-buffer)•Pixel is updated only if new z is closer than z-buffer valueMIT EECS 6.837, Cutler and Durand 51 Z-buffer pseudo codeFor every triangleCompute Projection, color at verticesSetup line equationsCompute bbox, clip bboxto screen limitsFor all pixels in bboxIncrement line equationsCompute curentZIncrement currentColorIf all line equations>0 //pixel [x,y] in triangleIf currentZ0 //pixel [x,y] in triangleIf current_1ovZ>1ovzBuffer[x,y]//pixel is visibleFramebuffer[x,y]=currentColor1ovzBuffer[x,y]=current1ovZMIT EECS 6.837, Cutler and Durand 60 Gouraudinterpolation•Gouraud: interpolate color linearly in screen space•Is it correct?z0z1ximagex’[R0, G0, B0][R1, G1, B1]MIT EECS 6.837, Cutler and Durand 61 Gouraudinterpolation•Gouraud: interpolate color linearly in screen space•Not correct. We should use hyperbolic interpolation•But quite costly (division)z0z1ximagex’[R0, G0, B0][R1, G1, B1]MIT EECS 6.837, Cutler and Durand 62 Next time•Clipping•Segment intersection & scanlinealgorithms