1Scan Conversion& ShadingAdam FinkelsteinPrinceton UniversityCOS 426, Spring 20033D Rendering Pipeline (for direct illumination)3D PrimitivesModelingTransformationModelingTransformationProjectionTransformationProjectionTransformationClippingClippingLightingLightingImageViewportTransformationViewportTransformationScanConversionScanConversion2D Image Coordinates3D Modeling Coordinates3D World Coordinates3D Camera Coordinates2D Screen Coordinates2D Screen CoordinatesViewingTransformationViewingTransformation3D World Coordinates2D Image CoordinatesScan Conversion& ShadingP1P2P3Overview• Scan conversiono Figure out which pixels to fill• Shadingo Determine a color for each filled pixelScan Conversion• Render an image of a geometric primitive by 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)Scan Conversion• Render an image of a geometric primitive by 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)Triangle Scan Conversion• Properties of a good algorithmo Symmetrico Straight edgeso Antialiased edgeso No cracks between adjacent primitiveso MUST BE FAST!P1P2P3P42Triangle Scan Conversion• Properties of a good algorithmo Symmetrico Straight edgeso Antialiased edgeso No cracks between adjacent primitiveso MUST BE FAST!P1P2P3P4Simple 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 triangle P1P2Line defines two halfspaces• Implicit equation for a lineo On line: ax + by + c = 0o On right: ax + by + c < 0o On left: ax + by + c > 0LInside Triangle Test• A point is inside a triangle if it is in the positive halfspace of all three boundary lineso Triangle vertices are ordered counter-clockwiseo Point must be on the left side of every boundary linePL1L2L3Inside 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;}L1L2L3Simple 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?3Triangle Sweep-Line Algorithm• Take advantage of spatial coherenceo Compute which pixels are inside using horizontal spanso Process horizontal spans in scan-line order• Take advantage of edge linearityo Use edge slopes to update coordinates incrementallydxdyTriangle Sweep-Line Algorithmvoid ScanTriangle(Triangle T, Color rgba){for each edge pair {initialize xL,xR;compute dxL/dyLand dxR/dyR;for each scanline at y for (int x = xL; x <= xR; x++) SetPixel(x, y, rgba);xL+= dxL/dyL;xR+= dxR/dyR;}}xLxRdxLdyLdxRdyRBresenham’s algorithmworks the same way, but uses only integer operations!Polygon Scan Conversion• Fill pixels inside a polygono Triangleo Quadrilateralo Convexo Star-shapedo Concaveo Self-intersectingo HolesWhat problems do we encounter with arbitrary polygons?Polygon Scan Conversion• Need better test for points inside polygono Triangle method works only for convex polygonsConvex PolygonL1L2L3L4L5L1L2L3AL4L5Concave PolygonL3BInside Polygon RuleConcaveSelf-Intersecting With Holes• What is a good rule for which pixels are inside?Inside Polygon RuleConcaveSelf-Intersecting With Holes• Odd-parity ruleo Any ray from P to infinity crosses odd number of edges4Polygon Sweep-Line Algorithm• Incremental algorithm to find spans, and determine insideness with odd parity ruleo Takes advantage of scanline coherencexLxRTriangle PolygonPolygon 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);}}Hardware Scan Conversion• Convert everything into triangleso Scan convert the trianglesHardware Antialiasing• Supersample pixelso Multiple samples per pixelo Average subpixel intensities (box filter)o Trades intensity resolution for spatial resolutionP1P2P3Overview• Scan conversiono Figure out which pixels to fill• Shadingo Determine a color for each filled pixelShading• How do we choose a color for each filled pixel? o 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 can be implemented in hardware Emphasis on methods that can be implemented in hardware5Ray Casting• Simplest shading approach is to perform independent lighting calculation for every pixelo When is this unnecessary?))()((∑•+•++=iiniSiiDALAEIRVKILNKIKIIPolygon Shading• Can take advantage of spatial coherenceo Illumination calculations for pixels covered by same primitive are related to each other))()((∑•+•++=iiniSiiDALAEIRVKILNKIKIIPolygon Shading Algorithms• Flat Shading• Gouraud Shading• Phong ShadingPolygon Shading Algorithms• Flat Shading• Gouraud Shading• Phong ShadingFlat Shading• What if a faceted object is illuminated only by directional light sources and is either diffuse or viewed from infinitely far away))()((∑•+•++=iiniSiiDALAEIRVKILNKIKIIFlat Shading• One illumination calculation per polygon o Assign all pixels inside each polygon the same colorN6Flat Shading• Objects look like they are composed of polygonso OK for polyhedral objectso Not so good for smooth surfacesPolygon Shading Algorithms• Flat Shading• Gouraud Shading• Phong ShadingGouraud Shading• What if smooth surface is represented by polygonal mesh with a normal at each vertex?))()((∑•+•++=iiniSiiDALAEIRVKILNKIKIIWatt Plate 7Gouraud Shading• Method 1: One lighting calculation per vertexo Assign pixels inside polygon by interpolating colors computed at verticesGouraud Shading• Bilinearly interpolate colors at verticesdown and across scan linesGouraud Shading• Smooth shading over adjacent polygonso Curved surfaceso
View Full Document
Unlocking...