Introduction to Computer Graphics CS 445 / 645 Lecture 9 Chapter 4: RasterizationWhat made line drawing faster?The Rendering PipelineSwitch to MIT SlidesRasterizing PolygonsSlide 6TriangulationTriangle Rasterization IssuesSlide 9Slide 10Rasterizing TrianglesEdge WalkingEdge Walking: NotesEdge Walking: DisadvantagesSlide 15Slide 16Edge EquationsSlide 18Slide 19Slide 20Using Edge EquationsComputing Edge EquationsSlide 23Slide 24Edge Equations: CodeOptimize This!Edge Equations: Speed HacksSlide 28General Polygon RasterizationSlide 30Polygon RasterizationSlide 32Slide 33Slide 34Faster Polygon RasterizationActive Edge TableSlide 37Review: Polygon RasterizationIntroduction to Computer GraphicsCS 445 / 645Lecture 9Chapter 4: RasterizationL. McMillanMIT 6.837 notes (Fall ’98)What made line drawing faster? Symmetry and Differential AnalyzerSymmetry and Differential AnalyzerSymmetry and Differential AnalyzerSymmetry and Differential Analyzerf (x) = mx + bf (x + 1) = m(x + 1) + b = mx + m + b= f (x) + ¢¢ = f (x + 1) ¡ f (x)= mx ¡ mx + m + b ¡ b= mf (x + 1) = f (x) + mThe Rendering PipelineTransformIlluminateTransformClipProjectRasterizeModel & CameraModel & CameraParametersParametersRendering PipelineRendering PipelineFramebufferFramebufferDisplayDisplayModelWorldWorldCameraSwitch to MIT SlidesCourse slides from Leonard McMillan’s MIT Course slides from Leonard McMillan’s MIT Course (6.837) from Fall ‘98Course (6.837) from Fall ‘98Course slides from Leonard McMillan’s MIT Course slides from Leonard McMillan’s MIT Course (6.837) from Fall ‘98Course (6.837) from Fall ‘98Rasterizing PolygonsIn interactive graphics, polygons rule the worldIn interactive graphics, polygons rule the worldTwo main reasons:Two main reasons:•Lowest common denominator for surfacesLowest common denominator for surfaces–Can represent any surface Can represent any surface with arbitrary accuracywith arbitrary accuracy–Splines, mathematical functions, volumetric isosurfaces…Splines, mathematical functions, volumetric isosurfaces…•Mathematical simplicity lends itself to simple, regular rendering Mathematical simplicity lends itself to simple, regular rendering algorithmsalgorithms–Like those we’re about to discuss… Like those we’re about to discuss… –Such algorithms embed well in hardwareSuch algorithms embed well in hardwareIn interactive graphics, polygons rule the worldIn interactive graphics, polygons rule the worldTwo main reasons:Two main reasons:•Lowest common denominator for surfacesLowest common denominator for surfaces–Can represent any surface Can represent any surface with arbitrary accuracywith arbitrary accuracy–Splines, mathematical functions, volumetric isosurfaces…Splines, mathematical functions, volumetric isosurfaces…•Mathematical simplicity lends itself to simple, regular rendering Mathematical simplicity lends itself to simple, regular rendering algorithmsalgorithms–Like those we’re about to discuss… Like those we’re about to discuss… –Such algorithms embed well in hardwareSuch algorithms embed well in hardwareRasterizing PolygonsTriangle is the Triangle is the minimal unitminimal unit of a polygonof a polygon•All polygons can be broken up into All polygons can be broken up into trianglestriangles•Triangles are guaranteed to be:Triangles are guaranteed to be:–PlanarPlanar–ConvexConvexTriangle is the Triangle is the minimal unitminimal unit of a polygonof a polygon•All polygons can be broken up into All polygons can be broken up into trianglestriangles•Triangles are guaranteed to be:Triangles are guaranteed to be:–PlanarPlanar–ConvexConvexTriangulationConvex polygons easily Convex polygons easily triangulated (Delaunay)triangulated (Delaunay)Concave polygons present Concave polygons present a challengea challengeConvex polygons easily Convex polygons easily triangulated (Delaunay)triangulated (Delaunay)Concave polygons present Concave polygons present a challengea challengeTriangle Rasterization IssuesSliverSliverSliverSliverMoving SliversMoving SliversMoving SliversMoving SliversTriangle Rasterization IssuesTriangle Rasterization IssuesShared Edge OrderingShared Edge OrderingShared Edge OrderingShared Edge OrderingRasterizing TrianglesInteractive graphics hardware commonly uses Interactive graphics hardware commonly uses edge walkingedge walking or or edge equationedge equation techniques for techniques for rasterizing trianglesrasterizing trianglesInteractive graphics hardware commonly uses Interactive graphics hardware commonly uses edge walkingedge walking or or edge equationedge equation techniques for techniques for rasterizing trianglesrasterizing trianglesEdge WalkingBasic idea: Basic idea: •Draw edges verticallyDraw edges vertically–Interpolate colors down edgesInterpolate colors down edges•Fill in horizontal spans for each Fill in horizontal spans for each scanlinescanline–At each scanline, interpolate At each scanline, interpolate edge colors across spanedge colors across spanBasic idea: Basic idea: •Draw edges verticallyDraw edges vertically–Interpolate colors down edgesInterpolate colors down edges•Fill in horizontal spans for each Fill in horizontal spans for each scanlinescanline–At each scanline, interpolate At each scanline, interpolate edge colors across spanedge colors across spanEdge Walking: NotesOrder three triangle vertices in x and yOrder three triangle vertices in x and y•Find middle point in y dimension and compute if it is to the left or right Find middle point in y dimension and compute if it is to the left or right of polygon. Also could be flat top or flat bottom triangleof polygon. Also could be flat top or flat bottom triangleWe know where left and right edges are.We know where left and right edges are.•Proceed from top scanline downwardsProceed from top scanline downwards•Fill each spanFill each span•Until breakpoint or bottom vertex is reachedUntil breakpoint or bottom vertex is reachedAdvantage: can be made very fastAdvantage: can be made very fastDisadvantages: Disadvantages: •Lots of finicky special casesLots of finicky special casesOrder three triangle vertices in x and yOrder three triangle vertices in x and y•Find middle point in y dimension and compute if it is to the left or right Find middle point in y dimension and compute if it is to the left or right of polygon. Also could be flat top or flat bottom triangleof polygon. Also
View Full Document
Unlocking...