1Scan Conversion& ShadingTom FunkhouserPrinceton UniversityCOS 426, Spring 20063D 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 conversion Figure out which pixels to fill• Shading Determine a color for each filled pixel• Texture mapping Describe shading variation within polygon interiorsScan 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 algorithm Symmetric Straight edges Antialiased edges No cracks between adjacent primitives MUST BE FAST!P1P2P3P42Triangle Scan Conversion• Properties of a good algorithm Symmetric Straight edges Antialiased edges No cracks between adjacent primitives 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 line On line: ax + by + c = 0 On right: ax + by + c < 0 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 lines Triangle vertices are ordered counter-clockwise 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 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 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;}}xLxRdxLdyLdxRdyRPolygon Scan Conversion• Fill pixels inside a polygon Triangle Quadrilateral Convex Star-shaped Concave Self-intersecting HolesWhat problems do we encounter with arbitrary polygons?Polygon Scan Conversion• Need better test for points inside polygon 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 rule 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 rule 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 triangles Scan convert the trianglesOverview• Scan conversion Figure out which pixels to fill• Shading Determine a color for each filled pixel• Texture mapping Describe shading variation within polygon interiorsShading• 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 can be implemented in hardware Emphasis on methods that can be implemented in hardware Ray Casting• Simplest shading approach is to perform independent lighting calculation for every pixel When is this unnecessary?))()((•+•++=iiniSiiDALAEIRVKILNKIKII5Polygon Shading• Can take advantage of spatial coherence 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 Assign all pixels inside each polygon the same colorNFlat Shading• Objects look like they are composed of polygons OK for polyhedral objects Not so good for smooth surfaces6Polygon 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 vertex 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 polygons Curved surfaces Illumination
View Full Document
Unlocking...