RasterizationLast time?High-level concepts for 6.837Scan Conversion (Rasterization)Visibility / DisplayTodayScan Converting 2D Line SegmentsLine Rasterization RequirementsAlgorithm Design ChoicesNaive Line Rasterization AlgorithmEfficiencyBresenham's Algorithm (DDA)Slide 13Bresenham StepSlide 15Slide 16Summary of BresenhamLine RasterizationLine Rasterization vs. Grid MarchingQuestions?Circle RasterizationSlide 22PhilosophicallySlide 24Antialiased Line RasterizationSlide 262D Scan ConversionSlide 28Brute force solution for trianglesSlide 30Slide 31Can we do better? Kind of!Use line rasterizationScan-line RasterizationSlide 35Slide 36For modern graphics cardsModern rasterizationSlide 39Can we do better?Slide 41Slide 42Adding Gouraud shadingSlide 44Slide 45Slide 46In the modern hardwareRefTake-home messageSlide 50Slide 51VisibilityRay CastingPainter’s algorithmSlide 55Slide 56Slide 57Z bufferZ-buffer pseudo codeWorks for hard cases!What exactly do we storeZ interpolationSimple Perspective ProjectionYet another Perspective ProjectionAdvantages of 1/zInteger z-bufferInteger Z-buffer pseudo codeGouraud interpolationSlide 69Slide 70The infamous half pixelSlide 72The Graphics PipelineModern Graphics HardwareGraphics HardwareProgrammable Graphics HardwareSlide 77Current GPUsComputational RequirementsSlide 80Next Week: Ray Casting AccelerationMIT EECS 6.837, Cutler and Durand 1RasterizationMIT EECS 6.837Frédo Durand and Barb CutlerMIT EECS 6.837, Cutler and Durand 2Last time?•Point and segment Clipping•Planes as homogenous vectors (duality)•In homogeneous coordinates before division•Outcodes for efficient rejection•Notion of convexity•Polygon clipping via walking•Line rasterization, incremental computationMIT EECS 6.837, Cutler and Durand 3High-level concepts for 6.837•Linearity•Homogeneous coordinates•Convexity•Discrete vs. continuous•Incremental computation•Trying things on simple examplesMIT EECS 6.837, Cutler and Durand 4Scan Conversion (Rasterization)•Rasterizes objects 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 5Visibility / 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 6Today•Line scan-conversion•Polygon scan conversion–smart–back to brute force•VisibilityMIT EECS 6.837, Cutler and Durand 7Scan 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, Cutler and Durand 8Line Rasterization Requirements•Transform c ontinuous primitive into discrete samples•Uniform thickness & brightness•Continuous appearance•No gaps•Accuracy•Speed(x1, y1)(x2, y2)MIT EECS 6.837, Cutler and Durand 9Algorithm 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, Cutler and Durand 10Naive Line Rasterization Algorithm•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)))xy(x1, y1)(x2, y2))1(1 xxmy )12(1211 yyxxxxyy dxdym MIT EECS 6.837, Cutler and Durand 11Efficiency•Computing y value is expensive•Observe: y += m at each x step (m = dy/dx))1(1 xxmyy y(x+1)y(x)x x+1mxy(x)(x1, y1)(x2, y2)y(x+1)x+1MIT EECS 6.837, Cutler and Durand 12Bresenham's Algorithm (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, Cutler and Durand 13Bresenham's Algorithm (DDA)•Observation: –If we're at pixel P (xp, yp), the next pixel must be either E (xp+1, yp) or NE (xp+1, yp+1)–Why?EN EMIT EECS 6.837, Cutler and Durand 14Bresenham Step•Which pixel to choose: E or NE?–Choose E if segment passes below or through middle point M–Choose NE if segment passes above MEN EMEN EMMIT EECS 6.837, Cutler and Durand 15Bresenham Step•Use decision function D 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, Cutler and Durand 16Bresenham's Algorithm (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): x' = x+1e' = e + my' = y (choose pixel E)y' = y + (choose pixel NE) e' = e - 1ee’MIT EECS 6.837, Cutler and Durand 17Summary of Bresenham•initialize x, y, e •for (x = x1; x ≤ x2; x++)–plot (x,y)–update x, y, e•Generalize to handle all eight octants using symmetry•Can be modified to use only integer arithmeticEN EMIT EECS 6.837, Cutler and Durand 18Line Rasterization•We will use it for ray-casting acceleration•March a ray through a gridMIT EECS 6.837, Cutler and Durand 19Line Rasterization vs. Grid MarchingRay Acceleration:Must examine every cell the line touchesLine Rasterization:Best discrete approximation of the lineMIT EECS 6.837, Cutler and Durand 20Questions?MIT EECS 6.837, Cutler and Durand 21Circle Rasterization•Generate pixels for 2nd octant only•Slope progresses from 0 → –1•Analog of Bresenham Segment AlgorithmMIT EECS 6.837, Cutler and Durand 22Circle 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 + 1x2 + y2 – R2–D(x,y)RMIT EECS 6.837, Cutler and Durand 23PhilosophicallyDiscrete differential analyzer (DDA):•Perform incremental computation•Work on derivative rather than function•Gain one order for polynomial–Line becomes constant derivative–Circle becomes linear derivativeMIT EECS 6.837, Cutler and Durand 24Questions?MIT
View Full Document
Unlocking...