The Graphics Pipeline: Line Clipping & Line RasterizationLast Time?Questions?Today: Line Clipping & RasterizationTodayClippingWhy clip?Clipping strategiesSlide 9Slide 10Implicit 3D Plane EquationHomogeneous CoordinatesPoint-to-Plane DistanceClipping a Point with respect to a PlaneClipping with respect to View FrustumWhat are the View Frustum Planes?Clipping & TransformationSegment ClippingSlide 19Slide 20Slide 21Slide 22Clipping against the frustumLine – Plane IntersectionIs this Clipping Efficient?Slide 26Slide 27Improving Efficiency: OutcodesSlide 29Slide 30Slide 31Slide 32Framebuffer Model2D Scan ConversionBrute force solution for trianglesSlide 36Slide 37Can we do better? Yes!Slide 39Slide 40Scan Converting 2D Line SegmentsLine Rasterization RequirementsAlgorithm Design ChoicesSlide 44Naive Line Rasterization AlgorithmEfficiencyLine RasterizationGrid Marching vs. Line RasterizationBresenham's Algorithm (DDA)Slide 50Bresenham StepSlide 52Slide 53Summary of BresenhamSlide 55Slide 56Circle RasterizationSlide 58Slide 59Slide 60Antialiased Line RasterizationNext Week:MIT EECS 6.837, Durand and CutlerThe Graphics Pipeline: Line Clipping & Line RasterizationMIT EECS 6.837, Durand and CutlerLast 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 CutlerQuestions?MIT EECS 6.837, Durand and CutlerToday: Line Clipping & Rasterization•Portions of the object outside the view frustum are removed•Rasterize objects into pixelsModeling TransformationsIllumination(Shading)Viewing Transformation(Perspective / Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility / DisplayMIT EECS 6.837, Durand and CutlerToday•Why Clip?•Line Clipping•Overview of Rasterization•Line Rasterization•Circle Rasterization•Antialiased LinesMIT EECS 6.837, Durand and CutlerClipping•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 CutlerWhy 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 CutlerClipping 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 CutlerQuestions?MIT EECS 6.837, Durand and CutlerToday•Why Clip?•Point & Line Clipping–Plane – Line intersection–Segment Clipping–Acceleration using outcodes•Overview of Rasterization•Line Rasterization•Circle Rasterization•Antialiased LinesMIT EECS 6.837, Durand and CutlerImplicit 3D Plane Equation•Plane defined by:point p & normal n ORnormal n & offset d OR3 points•Implicit plane equationAx+By+Cz+D = 0P0PMIT EECS 6.837, Durand and CutlerHomogeneous 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 CutlerPoint-to-Plane Distance•If (A,B,C) is normalized:d = H•p = HTp(the dot product in homogeneous coordinates)•d is a signed distance positive = "inside" negative = "outside"P’P0PH = (A,B,C,D)dMIT EECS 6.837, Durand and CutlerClipping a Point with respect to a Plane•If d = H•p 0Pass through •If d = H•p < 0:Clip (or cull or reject) P’P0PH = (A,B,C,D)dMIT EECS 6.837, Durand and CutlerClipping with respect to View Frustum•Test against each of the 6 planes–Normals oriented towards the interior•Clip (or cull or reject) point p if any H•p < 0PMIT EECS 6.837, Durand and CutlerWhat are the View Frustum Planes?Hnear = Hfar =Hbottom = Htop =Hleft = Hright = ( 0 0 –1 –near) ( 0 0 1 far ) ( 0 near bottom 0 ) ( 0 –near –top 0 ) ( left near 0 0 ) (–right –near 0 0 ) P(left, bottom, –near)(right*far/near, top*far/near, –far)MIT EECS 6.837, Durand and CutlerClipping & 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)MIT EECS 6.837, Durand and CutlerSegment 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 CutlerSegment 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 CutlerSegment 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 CutlerSegment 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 CutlerSegment 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 CutlerClipping 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 CutlerLine – 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 t is used to interpolate associated attributes (color, normal, texture, etc.) P0PP1MIT EECS 6.837, Durand and CutlerIs this Clipping
View Full Document
Unlocking...