CS580
CS580
Computer Graphics Rendering
Rasterization
Flat-shaded z-buffer rendering
Ulrich Neumann
Rendering HWs in steps
first build a display (HW1)
then rasterize a screen space triangle (HW2)
Input tris (pre-transformed vertex coordinates)
Output pixels to display created in HW1
then add arbitrary transformations (HW 3)
then add shading (HW 4)
…..
Rasterization
The center points (marked by x’s) are the integer coordinates of the pixels, eg., (3,2)
The colors at those points are stored in the frame buffer
The circles represent the area (region) of color that is created around the pixel point by the display
3
0
1
2
3
4
2
1
0
Pixel Array
and coordinates (X,Y)
X
Y
Rasterizing Lines
Given two endpoints, P= (x0, y0), R = (x1, y1)
find the pixels that make up the line
P
R
Lines are infinitely thin so they
rarely fall on pixel sample points
Rasterizing Lines
Rasterize lines as “closest” pixels to actual lines
No gaps
Minimize error (distance to true line)
Rasterizing Lines
Taylor Expansion:
Equation of a Line:
So if we know an x,y position on the line,
we can find the next point incrementally
This is the basis of many line rendering algorithms
Rasterizing Lines
Line (int x0, int y0, int x1, int y1)
float dx = x1 – x0;
float dy = y1 – y0;
float m = dy/dx;
float x = x0, y= y0;
for(x = x0; x <= x1; x++) setPixel(x, round(y)); y = y+m; The mid-point algorithm is a faster version of this idea that eliminates floats and rounding http://www.mat.univie.ac.at/~kriegl/Skripten/CG/node25.html Assume –1 < m < 1, x0 < x1 so lines are +/- 45 degrees 3 0 1 2 3 4 2 1 0 X0 X1 3D line drawing is sufficient for conveying or manipulating objects. More realistic 3D graphics requires an ability to draw surfaces. Renderings that include both lines and surfaces are possible and useful. Line and Surface Renderings “SketchPad” submitted January 1963 by Ivan Sutherland for the degree of Doctor of Philosophy to the Massachusetts Institute of Technology Triangles (tris) are a simple explicit 3D surface representation Convex and concave polygons (polys) can be decomposed into triangles (usually offline) Tris are planar and unambiguously defined by three vertex coordinates (coords) There are several common options for structuring triangle data We define triangles with a vertex-coordinate list per triangle - used in HWs Tri 1 = XYZA, XYZB, XYZD and Tri 2 = XYZC, XYZB, XYZD The order of vertices (verts) does not matter and the three edges are unambiguous Note that verts B and D (or edge BD) are repeated. We say they are shared by both tris Another common encoding is a triangle strip (or T-strip or winged-edge) List each vertex once, taking care to sequence the verts so that any contiguous three vertices form a complete triangle XYZA Tri 1 XYZB XYZD XYZC Tri 2 Note that the next triangle in the strip would have to share verts C and D Triangles as a 3D Surface Model A B C D Tri 1 Tri 2 Vertices are stored in a counter-clockwise order (by default ) A face orientation or normal is therefore encoded by the sequence of vertices A list of vertices, with (x, y, z, [w]) coordinates, (w is optional and defaults to 1.0) v 0.123 0.234 0.345 v 2.34 1.23 0.88 v -3.324 -2.26 1.88 v ... A list of texture coords, with (u, v, [w]) coords (w is optional and defaults to 1.0) vt 0.2 0.33 vt … A list of vertex normals, with (x,y,z) coords (might not be unit vectors) vn 0.707 0.000 -0.707 vn ... A list of faces, with indices to vertices/texture coords/normals f 1 2 3 - this is a ccw ordering that defines face normals f 3/1 4/2 5/3 f 6/4/1 3/5/3 7/6/5 Triangles in .obj Format outward inward https://en.wikipedia.org/wiki/Wavefront_.obj_file 1 2 3 3 2 1 Vertices Verts have X,Y,Z coords and other attributes like color, normal, texture coords, etc. Verts are where we “know something” about the model. Verts are model "sample points". Tris are planar approximation of “true” object geometry. Coords are relative to some origin and axes (e.g., Model Space). Example of tri from pot4.asc input file: {X, Y, Z, Nx, Ny, Nz, U, V} triangle 1.400000 2.250000 0.000000 -0.902861 -0.429934 0.000000 0.000000 0.000000 1.273482 2.323828 0.541834 -0.918898 0.095044 -0.382874 0.250000 0.250000 1.380469 2.323828 0.000000 -0.995495 0.094810 -0.000000 0.000000 0.250000 Note – our format does not include face-normals Rasterization Find and draw pixel samples inside tri edges and interpolate parameters defined at verts 3 verts are given (V1, V2, V3) coordinates and parameters at each vert 3 verts imply 3 edges Pixels inside edges are colored by the triangle Pixel color is based on vert parameters Vert parameter values are interpolated to pixel locations and then used to compute pixel color This triangle colors 3 pixels 3 0 1 2 3 4 2 1 0 V2 V1 V3 Rasterization and Hidden Surface Removal Two algorithm “classes” have evolved over many years Image order rasterization -- ray tracing / ray casting traverse pixels (image), process each in world-space transform rays from image-space to world-space Turner Whitted's paper (sig 79), Glassner, web, etc Object order rasterization -- scan-line / LEE traverse primitives (tris), process each in image-space transform objects from model-space to image-space Reyes (PIXAR) paper (sig87) - classic reference We’ll examine two object order rasterization algorithms LEE or Scan Line - both produce the same result Pick one of them for HW2 Linear Expression Evaluation Use E3 as an example (1st quadrant vector, positive slope dy/dx All edges are clockwise (CW) about tri (need to sort verts) Tail of vector is (X,Y) Head is (X + dX, Y + dY) Edge Equation: E(x,y) = dY (x-X) - dX (y-Y) [1] = 0 for points (x,y) on line (use E3 for this example) = - for points in half-plane to right/below line = + for points in half-plane to left/above line Note: these relations hold for all multiples of dY and dX: KdY, KdX (E vectors of any edge length within the same line) Points (x,y) inside tri evaluate to same sign for all 3 edges Use [1] definition and cast into general form of 2D line equation : Ax + By + C = 0 dYx - dYX - dXy + dXY = 0 (multiply terms in [1]) dYx + (-dXy) + (dXY - dYX) = 0 (collect terms) A = dY B = -dX C = dXY – dYX (Compute A,B,C from edge verts) E1 E2 E3 + _ + + LEE for Rasterization Given 3 tri verts defining 3 edges, Compute consistent CW or CCW edge orientation by sorting verts (see next slide) Compute A, B, C for each edge For each pixel in the bounding box of the verts Compute LEE result for all three edges Pixels with consistent sign for all three edges are inside the tri and therefore colored (green) Note circled pixel falls exactly on line Evaluates to 0.0 (float zero) for E3 Include edge pixels on left or right edges (L/R determined by sort) to avoid missed pixels (or pinholes) between tris E1 E2 E3 _ + + + Vertex Sorting Given 3 tri verts we need to sort them Find CW edge cycle Determine L/R and Top/Bot edges for edge-pixel ownership Start by sorting vert Y-coords V2, V1, V3 is low-to-high Y ordering (for case shown) So, CW edges are either 2-1, 1-3, 3-2 or 2-3, 3-1, 1-2 depending on which are L/R edges To find L/R relationship, use mid-Y vert V1 (X1, Y1) and find X-coord of point P (Xp, Y1) along long edge (V2-V3) Formulate line eq for V2-V3 to get Ax + By + C = 0 Plug in y = Y1 and solve for x = Xp Compare Xp to X1 and greatest value establishes which is Right-edge(s) In case shown, Xp < X1, so edges with V1 (mid-Y vertex) must be R-edges If two verts have exact same Y-values, treat as special case (horizontal Top or Bottom edge) V1 V2 V3 P Vertex Sorting 2 There are many other methods for sorting edges, for example edge-evaluation and slope-comparisons can determine L/R relationships Edge Eval: Formulate line Eq for long edge (between top/bottom verts V2 and V3) to get Ax + By + C = 0 Plug in V1 (X1, Y1) and evaluate sign Sign determines whether V1 (and edges including V1) lies to L or R of long edge Slope Compare: Compute slopes of long edge (V2 to V3) and top to middle-vert edge (V2 to V1) Compare dx/dy slopes to determine L/R edge V1 V2 V3 V1 V2 V3 Interpolate Z In addition to X,Y coords, verts also have a Z coord Need to determine the Z value at each pixel in a triangle Compute Z during rasterization A general 3D plane equation has four terms: Ax + By + Cz + D = 0 [1] where vector (A,B,C) is normal to the plane (face-normal) The cross-product of two tri edges produces the (A,B,C) vector Create edge vectors (X,Y,Z)0 and (X,Y,Z)1 from any two pairs of verts (X,Y,Z)0 × (X,Y,Z)1 = (A,B,C) = norm to plane of edges (and tri) Use (A,B,C) and plug any vertex coord into [1] and solve for D Given (A,B,C,D) for a given tri, evaluate [1] at any pixel (x,y) and solve for z at that pixel (interpolated Z value) We can substitute other parameters (e.g., u,v) for Z, and compute (A,B,C,D) plane coefficients to interpolate these parameters to pixels need this later for interpolations of texture or color or normals Z-buffer to remove hidden surfaces For each pixel inside triangle: Interpolate vertex Z values to get Zpix Compare computed Zpix value against current Z-value in Frame Buffer (Zfb) If Zpix < Zfb, write new pixel color and Zpix into FB (overwrite current FB values) Otherwise, do nothing, skip pixel – it’s an occluded surface point This assumes a coord system such that Z increases with distance from the viewer Pixel color is known - given by application in HW2 Hardware for LEE Rasterization Parallel evaluation is possible for all pixels in NxM pixel-region given 3 edge coefficient sets for a triangle (A1,B1,C1) (A2,B2,C2) (A3,B3,C3) this is the basis of Pixel-Planes and Pixel-Flow systems from UNC (1980s and 1990s) and many graphics accelerators today First rasterize - find the pixel coverage, interpolate Z, and do Z-buffer hidden surface removal for a triangle Then, at visible pixels, interpolate other vertex parameters needed for color, and store them in a deep frame buffer After all tris are rasterized, compute (deferred) shading of all FB pixels using the values stored at each FB pixel Shading is parallel (SIMD) and only for visible surfaces Rasterization Papers to Read Siggraph 1985 - "Fast Spheres, Shadows, Textures, Transparencies, and Image Enhancements in Pixel-Planes," Henry Fuchs,et. al. 2000 Sig/Euro Workshop on Graphics Hardware - "Tiled Polygon Traversal Using Half-Plane Edge Functions," Joel McCormack, Robert McNamara Siggraph 1988 - "A Parallel Algorithm for Polygon Rasterization," Juan Pineda Siggraph 2005 - “Resolution-Independent Curve Rendering Using Programmable Graphics Hardware,” Charles Loop, Jim Blinn Rasterization Special Cases *** Watch for special cases Define a convention for pixels on exact L/R T/B edges Use edge-eval, slope, or intercept method for L/R sort One edge covers pixel, the other does not Horizontal edges – carefully sort edges and loop over pixels Small or thin tris can cover zero pixels or have gaps between pixels Ensure loop code manages zero-iteration cases Test yourself (these need not be addressed in your HW) What if a vertex falls exactly on a pixel? How can you ensure that one and only one triangle will color that pixel? Why is it a bad idea to create a model with a T-junction? A T-junction is created when a vertex lies on another triangle’s edge Vertex x-sort does not robustly identify L/R edges ) ( x f b mx y = + = x x f y x x y D + = D + ) ( ' ) (