11Scan Conversion& ShadingAdam FinkelsteinPrinceton UniversityC0S 426, Fall 200123D Rendering Pipeline (for direct illumination)3DPrimitivesModelingTransformationModelingTransformationProjectionTransformationProjectionTransformationClippingClippingLightingLightingImageViewportTransformationViewportTransformationScanConversionScanConversion2D Image Coordinates3D Modeling Coordinates3D World Coordinates3D Camera Coordinates2D Screen Coordinates2D Screen CoordinatesViewingTransformationViewingTransformation3D World Coordinates2D Image CoordinatesScan Conversion& ShadingP1P2P33Overview•Scanconversionο Figure out which pixels to fill• Shadingο Determine a color for each filled pixel4Scan Conversion• Render an image of a geometric primitiveby setting pixel colors• Example: Filling the inside of a triangleP1P2P3void SetPixel(int x, int y, Color rgba)void SetPixel(int x, int y, Color rgba)5Scan Conversion• Render an image of a geometric primitiveby setting pixel colors• Example: Filling the inside of a triangleP1P2P3void SetPixel(int x, int y, Color rgba)void SetPixel(int x, int y, Color rgba)6Triangle Scan Conversion• Properties of a good algorithmο Symmetricο Straight edgesο Antialiased edgesο No cracks between adjacent primitivesο MUST BE FAST!P1P2P3P427Triangle Scan Conversion• Properties of a good algorithmο Symmetricο Straight edgesο Antialiased edgesο No cracks between adjacent primitivesο MUST BE FAST!P1P2P3P48Simple AlgorithmP1P2P3void ScanTriangle(Triangle T, Color rgba){for each pixel P at (x,y){if (Inside(T, P))SetPixel(x, y, rgba);}}void ScanTriangle(Triangle T, Color rgba){for each pixel P at (x,y){if (Inside(T, P))SetPixel(x, y, rgba);}}• Color all pixels inside triangle9Inside Triangle Test• A point is inside a triangle if it is in thepositive halfspace of all three boundary linesο Triangle vertices are ordered counter-clockwiseο Point must be on the left side of every boundary linePL1L2L310Inside Triangle TestBoolean Inside(Triangle T, Point P){for each boundary line L of T {Scalar d = L.a*P.x + L.b*P.y + L.c;if (d < 0.0) return FALSE;}return TRUE;}L1L2L311Simple AlgorithmP1P2P3void ScanTriangle(Triangle T, Color rgba){for each pixel P at (x,y){if (Inside(T, P))SetPixel(x, y, rgba);}}void ScanTriangle(Triangle T, Color rgba){for each pixel P at (x,y){if (Inside(T, P))SetPixel(x, y, rgba);}}• What is bad about this algorithm?12Triangle Sweep-Line Algorithm• Take advantage of spatial coherenceο Compute which pixels are inside using horizontal spansο Process horizontal spans in scan-line order• Take advantage of edge linearityο Use edge slopes to update coordinates incrementallydxdy313Triangle Sweep-Line Algorithmvoid ScanTriangle(Triangle T, Color rgba){for each edge pair {initialize xL,xR;compute dxL/dyLand dxR/dyR;for each scanline at yfor(intx=xL;x<=xR; x++)SetPixel(x, y, rgba);xL+= dxL/dyL;xR+= dxR/dyR;}}xLxRdxLdyLdxRdyR14Polygon Scan Conversion• Fill pixels inside a polygonο Triangleο Quadrilateralο Convexο Star-shapedο Concaveο Self-intersectingο HolesWhat problems do we encounter with arbitrary polygons?15Polygon Scan Conversion• Need better test for points inside polygonο Triangle method works only for convex polygonsConvex PolygonL1L2L3L4L5L1L2L3AL4L5Concave PolygonL3B16Inside Polygon RuleConcaveSelf-Intersecting With Holes• What is a good rule for which pixels are inside?17Inside Polygon RuleConcaveSelf-Intersecting With Holes• Odd-parity ruleο Any ray from P to infinity crosses odd number of edges18Polygon Sweep-Line Algorithm• Incremental algorithm to find spans,and determine insideness with odd parity ruleο Takes advantage of scanline coherencexLxRTriangle Polygon419Polygon Sweep-Line Algorithmvoid ScanPolygon(Triangle T, Color rgba){sort edges by maxymake empty “active edge list”for each scanline (top-to-bottom) {insert/remove edges from “active edge list”update x coordinate of every active edgesort active edges by x coordinatefor each pair of active edges (left-to-right)SetPixels(xi,xi+1,y,rgba);}}20Hardware Scan Conversion• Convert everything into trianglesο Scan convert the triangles21Hardware Antialiasing• Supersample pixelsο Multiple samples per pixelο Average subpixel intensities (box filter)ο Trades intensity resolution for spatial resolutionP1P2P322Overview•Scanconversionο Figure out which pixels to fill• Shadingο Determine a color for each filled pixel23Shading• How do we choose a color for each filled pixel?ο Each illumination calculation for a ray from the eyepointthrough the view plane provides a radiance sample» How do we choose where to place samples?» How do we filter samples to reconstruct image?Angel Figure 6.34Emphasis on methods that canbe implemented in hardwareEmphasis on methods that canbe implemented in hardware24Ray Casting• Simplest shading approach is to performindependent lighting calculation for every pixelο When is this unnecessary?))()((∑•+•++=iiniSiiDALAEIRVKILNKIKII525Polygon Shading• Can take advantage of spatial coherenceο Illumination calculations for pixels covered by sameprimitive are related to each other))()((∑•+•++=iiniSiiDALAEIRVKILNKIKII26Polygon Shading Algorithms• Flat Shading• Gouraud Shading• Phong Shading27Polygon Shading Algorithms• Flat Shading• Gouraud Shading• Phong Shading28Flat Shading• What if a faceted object is illuminated only bydirectional light sources and is either diffuse orviewed from infinitely far away))()((∑•+•++=iiniSiiDALAEIRVKILNKIKII29Flat Shading• One illumination calculation per polygonο Assign all pixels inside each polygon the same colorN30Flat Shading• Objects look like they are composed of polygonsο OK for polyhedral objectsο Not so good for ones with smooth surfaces631Polygon Shading Algorithms• Flat Shading• Gouraud Shading• Phong Shading32Gouraud Shading• What if smooth surface is represented bypolygonal mesh with a normal at each vertex?))()((∑•+•++=iiniSiiDALAEIRVKILNKIKIIWatt Plate 733Gouraud Shading• Method 1: One lighting calculation per vertexο Assign pixels inside polygon by interpolating colorscomputed at vertices34Gouraud Shading• Bilinearly interpolate colors at verticesdown and across scan lines35Gouraud Shading• Smooth shading over adjacent polygonsο Curved surfacesο Illumination highlightsο Soft shadowsMesh with shared normals at verticesWatt Plate 736Gouraud Shading• Produces smoothly shaded polygonal meshο
View Full Document
Unlocking...