MIT EECS 6.837, Durand and Cutler The Graphics Pipeline: Line Clipping & Line RasterizationMIT EECS 6.837, Durand and Cutler Last Time?•Ray Tracing vs. Scan Conversion•Overview of the Graphics Pipeline•Projective TransformationsModeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayMIT EECS 6.837, Durand and Cutler Questions?Today: Line Clipping & Rasterization MIT EECS 6.837, Durand and Cutler •Portions of the object outside the view frustum are removed•Rasterizeobjects into pixelsModeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayMIT EECS 6.837, Durand and Cutler Today•Why Clip?•Line Clipping•Overview of Rasterization•Line Rasterization•Circle Rasterization•AntialiasedLinesMIT EECS 6.837, Durand and Cutler Clipping•Eliminate portions of objects outside the viewing frustum•View Frustum –boundaries of the image plane projected in 3D–a near & far clipping plane•User may define additional clipping planesbottomtoprightleftnearfarMIT EECS 6.837, Durand and Cutler Why clip?•Avoid degeneracies–Don’t draw stuff behind the eye–Avoid division by 0 and overflow•Efficiency–Don’t waste time on objects outside the image boundary•Other graphics applications (often non-convex)–Hidden-surface removal, Shadows, Picking, Binning, CSG (Boolean) operations (2D & 3D)MIT EECS 6.837, Durand and Cutler Clipping strategies•Don’t clip (and hope for the best)•Clip on-the-fly during rasterization•Analytical clipping: alter input geometryMIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•Why Clip?•Point & Line Clipping–Plane –Line intersection–Segment Clipping–Acceleration using outcodes•Overview of Rasterization•Line Rasterization•Circle Rasterization•AntialiasedLinesMIT EECS 6.837, Durand and Cutler Implicit 3D Plane Equation•Plane defined by:point p & normaln ORnormal n & offset d OR3 points•Implicit plane equationAx+By+Cz+D= 0P0PMIT EECS 6.837, Durand and Cutler Homogeneous Coordinates•Homogenous point: (x,y,z,w) infinite number of equivalenthomogenous coordinates: (sx, sy, sz, sw)•Homogenous Plane Equation: Ax+By+Cz+D= 0 →H = (A,B,C,D)Infinite number of equivalent plane expressions: sAx+sBy+sCz+sD= 0 →H = (sA,sB,sC,sD)P0PH = (A,B,C,D)MIT EECS 6.837, Durand and Cutler Point-to-Plane DistanceP’P0PH = (A,B,C,D)d•If (A,B,C) is normalized:d = H•p= HTp(the dot product in homogeneous coordinates)•d is a signed distancepositive = "inside" negative = "outside"Clipping a Point with respect to a Plane MIT EECS 6.837, Durand and Cutler P’P0PH = (A,B,C,D)d•If d = H•p≥0Pass through •If d = H•p< 0:Clip (or cull or reject) Clipping with respect to View Frustum MIT EECS 6.837, Durand and Cutler •Test against each of the 6 planes–Normalsoriented towards the interior•Clip (or cull or reject) point pif any H•p< 0PMIT EECS 6.837, Durand and Cutler What are the View Frustum Planes?Hnear= Hfar=Hbottom= Htop=Hleft= Hright= ( 0 0 –1 –near) ( 0 0 1 far ) ( 0 nearbottom0 ) ( 0 –near–top0 ) ( leftnear0 0 ) (–right–near0 0 ) P(left, bottom, –near)(right*far/near, top*far/near, –far)MIT EECS 6.837, Durand and Cutler Clipping & Transformation•Transform M (e.g. from world space to NDC)•The plane equation is transformed with (M-1)T (1,1,1) (-1,-1,-1) near far y z x y x o eye zMIT EECS 6.837, Durand and Cutler Segment Clipping•If H•p> 0 and H•q< 0•If H•p< 0 and H•q> 0•If H•p> 0 and H•q> 0•If H•p< 0 and H•q< 0pqMIT EECS 6.837, Durand and Cutler Segment Clipping•If H•p> 0 and H•q< 0–clip q to plane•If H•p< 0 and H•q> 0•If H•p> 0 and H•q> 0•If H•p< 0 and H•q< 0pqnMIT EECS 6.837, Durand and Cutler Segment Clipping•If H•p> 0 and H•q< 0–clip q to plane•If H•p< 0 and H•q> 0–clip p to plane•If H•p> 0 and H•q> 0•If H•p< 0 and H•q< 0pqnMIT EECS 6.837, Durand and Cutler Segment Clipping•If H•p> 0 and H•q< 0–clip q to plane•If H•p< 0 and H•q> 0–clip p to plane•If H•p> 0 and H•q> 0–pass through•If H•p< 0 and H•q< 0pqnMIT EECS 6.837, Durand and Cutler Segment Clipping•If H•p> 0 and H•q< 0–clip q to plane•If H•p< 0 and H•q> 0–clip p to plane•If H•p> 0 and H•q> 0–pass through•If H•p< 0 and H•q< 0–clipped outpqnMIT EECS 6.837, Durand and Cutler Clipping against the frustum•For each frustum plane H–If H•p> 0 and H•q< 0, clip q to H –If H•p< 0 and H•q> 0, clip p to H –If H•p> 0 and H•q> 0, pass through –If H•p< 0 and H•q< 0, clipped outResult is a single segment. Why?MIT EECS 6.837, Durand and Cutler Line –Plane Intersection•Explicit (Parametric) Line EquationL(t) = P0+ t * (P1–P0)L(t) = (1-t) * P0+ t* P1•How do we intersect?Insert explicit equation of line intoimplicit equation of plane •Parameter tis used to interpolate associated attributes (color, normal, texture, etc.) P0PP1MIT EECS 6.837, Durand and Cutler Is this Clipping Efficient?pH1H2H3H4q•For each frustum plane H–If H•p> 0 and H•q< 0, clip q to H –If H•p< 0 and H•q> 0, clip p to H –If H•p> 0 and H•q> 0, pass through –If H•p< 0 and H•q< 0, clipped outMIT EECS 6.837, Durand and Cutler Is this Clipping Efficient?qpH1H2H3H4•For each frustum plane H–If H•p> 0 and H•q< 0, clip q to H –If H•p< 0 and H•q> 0, clip p to H –If H•p> 0 and H•q> 0, pass through –If H•p< 0 and H•q< 0, clipped outMIT EECS 6.837, Durand and Cutler Is this Clipping Efficient?qpH1H2H3H4What is the problem?The computation of the intersections, andany correspondinginterpolated values is unnecessaryCan we detect this earlier?•For each frustum plane H–If H•p> 0 and H•q< 0, clip q to H –If H•p< 0 and H•q> 0, clip p to H –If H•p> 0 and H•q> 0, pass through –If H•p< 0 and H•q< 0, clipped outMIT EECS 6.837, Durand and Cutler Improving Efficiency: Outcodes•Compute the sidedness of each vertex with respect to each bounding plane (0 = valid) •Combine into binary outcodeusing logical ANDH1H2H3H4000010100010011010000100000110010101pqOutcodeof p : 1010Outcodeof q : 0110Outcodeof [pq] : 0010Clipped because there is a 1MIT EECS 6.837, Durand and Cutler Improving Efficiency: Outcodes•When do we fail to save computation?H1H2H3H4000010100010011010000100000110010101qOutcodeof p : 1000Outcodeof q : 0010pOutcodeof [pq] : 0000Not clippedMIT EECS 6.837, Durand and Cutler Improving Efficiency: Outcodes•It works for arbitrary primitives•And for arbitrary dimensionsOutcodeof p : 1010Outcodeof q : 1010H1H2H3H4000010100010011010000100000110010101Outcodeof r : 0110Outcodeof s : 0010Outcodeof t : 0110Outcodeof u : 0010Outcode: 0010ClippedMIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•Why Clip?•Line Clipping•Overview of Rasterization•Line Rasterization•Circle Rasterization•AntialiasedLinesMIT EECS 6.837, Durand and Cutler FramebufferModel•Raster Display: 2D array of picture elements (pixels)•Pixels individually set/cleared (greyscale, color)•Window coordinates: pixels centered at integers(x1,y1)(x2,y2)glBegin(GL_LINES)glVertex3f(...)glVertex3f(...)glEnd();MIT EECS 6.837, Durand and Cutler 2D Scan Conversion•Geometric primitives (point, line, polygon, circle, polyhedron, sphere... )•Primitives are continuous; screen is discrete •Scan Conversion: algorithms for efficientgeneration of the samples comprising this approximationMIT EECS 6.837, Durand and Cutler Brute force solution for triangles•For each pixel–Compute line equations at pixel center–“clip” against the triangleMIT EECS 6.837, Durand and Cutler 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, Durand and Cutler Brute force solution for triangles•Improvement:–Compute only for the screen bounding box of the triangle–Xmin, Xmax, Ymin, Ymaxof the triangle verticesMIT EECS 6.837, Durand and Cutler Can we do better? Yes!•More on polygons next week.•Today: line rasterizationMIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•Why Clip?•Line Clipping•Overview of Rasterization•Line Rasterization–naive method–Bresenham's(DDA)•Circle Rasterization•AntialiasedLinesMIT EECS 6.837, Durand and Cutler Scan Converting 2D Line Segments•Given:–Segment endpoints (integers x1, y1; x2, y2)•Identify:–Set of pixels (x, y) to display for segment(x1, y1)(x2, y2)MIT EECS 6.837, Durand and Cutler Line RasterizationRequirements•Transform continuous primitive into discrete samples•Uniform thickness & brightness•Continuous appearance•No gaps•Accuracy•Speed(x1, y1)(x2, y2)MIT EECS 6.837, Durand and Cutler Algorithm Design Choices•Assume:–m = dy/dx, 0 < m < 1 •Exactly one pixel per column–fewer →disconnected, more →too thick(x1, y1)(x2, y2)MIT EECS 6.837, Durand and Cutler Algorithm Design Choices•Note: brightness can vary with slope–What is the maximum variation? •How could we compensate for this?–Answer: antialiasing2MIT EECS 6.837, Durand and Cutler Naive Line RasterizationAlgorithm•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?–Set pixel (x, round (y(x))))12(1211yyxxxxyy−−−+=xy(x1, y1)(x2, y2))1(1xxmy−+=dxdym=MIT EECS 6.837, Durand and Cutler Efficiency•Computing y value is expensive•Observe: y += mat each xstep (m = dy/dx))1(1xxmyy−+=xy(x)(x1, y1)(x2, y2)y(x+1)x+1y(x+1)y(x)xx+1mMIT EECS 6.837, Durand and Cutler Line Rasterization•It's like marching a ray through the grid •Also uses DDA (Digital Difference Analyzer)MIT EECS 6.837, Durand and Cutler Grid Marching vs. Line RasterizationLine Rasterization:Best discrete approximation of the lineRay Acceleration:Must examine every cell the line touchesMIT EECS 6.837, Durand and Cutler Bresenham'sAlgorithm (DDA)•Select pixel vertically closest to line segment–intuitive, efficient, pixel center always within 0.5 vertically•Same answer as naive approachMIT EECS 6.837, Durand and Cutler Bresenham'sAlgorithm (DDA)•Observation: –If we're at pixel P (xp, yp), the next pixel must be either E (xp+1, yp) or NE (xp, yp+1)–Why?ENEMIT EECS 6.837, Durand and Cutler BresenhamStep•Which pixel to choose: E or NE?–Choose E if segment passes below or through middle point M–Choose NE if segment passes above MENEMENEMMIT EECS 6.837, Durand and Cutler BresenhamStep•Use decision functionD to identify points underlying line L: D(x, y) = y-mx-b–positive above L–zero on L–negative below LD(px,py) =MF<0F>0F=0pvertical distance from point to lineMIT EECS 6.837, Durand and Cutler Bresenham'sAlgorithm (DDA)•Decision Function:D(x, y) = y-mx-b•Initialize:error term e= –D(x,y)•On each iteration:update x:update e:if (e≤0.5): if (e > 0.5): ee’x' = x+1e' = e + my' = y (choose pixel E)y' = y + (choose pixel NE) e' = e -1MIT EECS 6.837, Durand and Cutler Summary of Bresenham•initialize x, y, e•for (x= x1; x≤x2; x++)–plot (x,y)–updatex, y, e•Generalize to handle all eight octants using symmetry•Can be modified to use only integer arithmeticENEMIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•Why Clip?•Line Clipping•Overview of Rasterization•Line Rasterization–naive method–Bresenham's(DDA)•Circle Rasterization•AntialiasedLinesMIT EECS 6.837, Durand and Cutler Circle Rasterization•Generate pixels for 2nd octant only•Slope progresses from 0 →–1•Analog of BresenhamSegment AlgorithmMIT EECS 6.837, Durand and Cutler Circle Rasterization•Decision Function:D(x, y) =•Initialize:error term e =•On each iteration:update x:update e:if (e ≥0.5): if (e < 0.5): x' = x + 1e'= e + 2x + 1 y' = y (choose pixel E)y' = y -1(choose pixel SE), e' = e + 1Rx2+ y2–R2–D(x,y)MIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•Why Clip?•Line Clipping•Overview of Rasterization•Line Rasterization–naive method–Bresenham's(DDA)•Circle Rasterization•AntialiasedLinesMIT EECS 6.837, Durand and Cutler AntialiasedLine RasterizationaliasedantialiasedMIT EECS 6.837, Durand and Cutler Next Week:Polygon Rasterization& Polygon Clipping