1Greg HumphreysCS445: Intro GraphicsUniversity of Virginia, Fall 2004Polygon Scan Conversion& Shading3D Rendering Pipeline (for direct illumination)3D PrimitivesModelingTransformationProjectionTransformationClippingLightingImageViewportTransformationScanConversion2D Image Coordinates3D Modeling Coordinates3D World Coordinates3D Camera Coordinates2D Screen Coordinates2D Screen CoordinatesViewingTransformation3D World Coordinates2D Image CoordinatesScan Conversion& ShadingP1P2P3Overview• Scan conversion Figure out which pixels to fill• Shading Determine a color for each filled pixelScan 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)Scan 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)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);}}• Color all pixels inside triangleP1P2Line 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 thepositive 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);}}• 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/dyL and 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 integeroperations!Polygon 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 edge sort 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 trianglesHardware Antialiasing• Supersample pixels Multiple samples per pixel Average subpixel intensities (box filter) Trades intensity resolution for spatial resolutionP1P2P3Overview• Scan conversion Figure out which pixels to fill• Shading Determine a color for each filled pixelShading• 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 hardware5Ray Casting• Simplest shading approach is to performindependent lighting calculation for every pixel When is this unnecessary?))()((!•+•++=iiniSiiDALAEIRVKILNKIKIIPolygon Shading• Can take advantage of spatial coherence Illumination calculations for pixels covered by sameprimitive 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 bydirectional light sources and is either diffuse orviewed from infinitely far away))()((!•+•++=iiniSiiDALAEIRVKILNKIKIIFlat Shading• One illumination calculation per polygon Assign all pixels inside each polygon the same colorN6Flat Shading• Objects look like they are composed of polygons OK for polyhedral objects Not so good for smooth surfacesPolygon Shading Algorithms• Flat Shading• Gouraud Shading• Phong ShadingGouraud Shading• What if smooth surface is represented bypolygonal mesh with a normal at each vertex?))()((!•+•++=iiniSiiDALAEIRVKILNKIKIIWatt Plate 7Gouraud Shading• Method 1: One lighting calculation per vertex Assign pixels inside polygon by interpolating colorscomputed at verticesGouraud Shading• Bilinearly interpolate colors at verticesdown and across scan linesGouraud Shading• Smooth shading over adjacent polygons Curved surfaces Illumination highlights Soft shadowsMesh with shared normals at verticesWatt Plate 77Gouraud Shading• Produces smoothly shaded polygonal mesh Piecewise linear approximation Need fine mesh to capture subtle lighting effectsGouraud ShadingFlat ShadingPolygon Shading Algorithms• Flat Shading• Gouraud Shading• Phong ShadingPhong Shading• What if polygonal mesh is
View Full Document
Unlocking...