[SOLVED] CS algorithm CS580

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 xs) 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.htmlAssume 1 < m < 1, x0 < x1 so lines are +/- 45 degrees301234210X0X13D 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 RenderingsSketchPad submitted January1963 by Ivan Sutherland for the degree of Doctor of Philosophy to theMassachusetts Institute of TechnologyTriangles (tris) are a simple explicit 3D surface representationConvex 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 dataWe define triangles with a vertex-coordinate list per triangle- used in HWsTri 1 = XYZA, XYZB, XYZD and Tri 2 = XYZC, XYZB, XYZD The order of vertices (verts) does not matter and the three edges are unambiguousNote that verts B and D (or edge BD) are repeated.We say they are shared by both trisAnother common encoding is a triangle strip (or T-strip or winged-edge)List each vertex once, taking care to sequence the vertsso that any contiguous three vertices form a complete triangleXYZATri 1XYZBXYZDXYZC Tri 2Note that the next triangle in the strip would have to share verts C and DTriangles as a 3D Surface ModelABCDTri 1Tri 2Vertices are stored in a counter-clockwise order (by default )A face orientation or normal is therefore encodedby the sequence of verticesA list of vertices, with (x, y, z, [w]) coordinates, (w is optional and defaults to 1.0)v 0.1230.2340.345v 2.341.230.88v -3.324-2.261.88v …A list of texture coords, with (u, v, [w]) coords (w is optional and defaults to 1.0)vt 0.20.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/normalsf 1 2 3- this is a ccw ordering that defines face normalsf 3/1 4/2 5/3 f 6/4/1 3/5/3 7/6/5Triangles in .obj Formatoutwardinwardhttps://en.wikipedia.org/wiki/Wavefront_.obj_file123321VerticesVerts 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}triangle1.4000002.2500000.000000-0.902861 -0.4299340.0000000.0000000.0000001.2734822.3238280.541834-0.918898 0.095044 -0.382874 0.2500000.2500001.3804692.3238280.000000-0.995495 0.094810 -0.000000 0.0000000.250000Note our format does not include face-normalsRasterizationFind and draw pixel samples inside tri edges and interpolate parameters defined at verts3 verts are given (V1, V2, V3) coordinates and parameters at each vert3 verts imply 3 edgesPixels inside edges are colored by the trianglePixel color is basedon vert parametersVert parameter valuesare interpolated to pixel locations and then used to compute pixel colorThis triangle colors 3 pixels301234210V2V1V3Rasterization and Hidden Surface Removal Two algorithm classes have evolved over many yearsImage order rasterization — ray tracing / ray castingtraverse pixels (image), process each in world-spacetransform rays from image-space to world-spaceTurner Whitted’s paper (sig 79), Glassner, web, etcObject order rasterization — scan-line / LEEtraverse primitives (tris), process each in image-spacetransform objects from model-space to image-space Reyes (PIXAR) paper (sig87) – classic referenceWell examine two object order rasterization algorithmsLEE or Scan Line – both produce the same resultPick one of them for HW2Linear Expression EvaluationUse E3 as an example (1st quadrant vector, positive slope dy/dxAll 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 lineNote: 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 edgesUse [1] definition and cast into general form of 2D line equation :Ax + By + C = 0dYx – dYX – dXy + dXY = 0(multiply terms in [1])dYx + (-dXy) + (dXY – dYX) = 0 (collectterms)A = dYB = -dXC = dXY dYX(Compute A,B,C from edge verts)E1E2E3+_++LEE for RasterizationGiven 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 edgeFor each pixel in the bounding box of the vertsCompute LEE result for all three edgesPixels with consistent sign for all three edges are inside the tri and therefore colored (green)Note circled pixel falls exactly on lineEvaluates to 0.0 (float zero) for E3Include edge pixels on left or right edges (L/R determined by sort) to avoid missed pixels (or pinholes) between trisE1E2E3_+++Vertex SortingGiven 3 tri verts we need to sort themFind CW edge cycleDetermine L/R and Top/Bot edges for edge-pixel ownershipStart by sorting vert Y-coordsV2, V1, V3 is low-to-high Y ordering (for case shown)So, CW edges are either 2-1, 1-3, 3-2or2-3, 3-1, 1-2 depending on which are L/R edgesTo 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 = 0Plug in y = Y1 and solve for x = XpCompare 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-edgesIf two verts have exact same Y-values, treat as special case (horizontal Top or Bottom edge)V1V2V3PVertex Sorting 2There are many other methods for sorting edges, for example edge-evaluation and slope-comparisons can determine L/R relationshipsEdge Eval:Formulate line Eq for long edge (between top/bottom verts V2 and V3) to getAx + By + C = 0Plug in V1 (X1, Y1) and evaluate signSign determines whether V1 (and edges including V1) lies to L or R of long edgeSlope 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 edgeV1V2V3V1V2V3Interpolate ZIn addition to X,Y coords, verts also have a Z coordNeed to determine the Z value at each pixel in a triangleCompute Z during rasterizationA 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) vectorCreate 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 pixelsneed this later for interpolations of texture or color or normals Z-buffer to remove hidden surfacesFor each pixel inside triangle:Interpolate vertex Z values to get ZpixCompare 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 its an occluded surface pointThis assumes a coord system such that Z increases with distance from the viewerPixel color is known – given by application in HW2Hardware for LEE RasterizationParallel 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 todayFirst rasterize – find the pixel coverage, interpolate Z, and do Z-buffer hidden surface removal for a triangleThen, at visible pixels, interpolate other vertex parameters needed for color, and store them in a deep frame bufferAfter all tris are rasterized, compute (deferred) shading of all FB pixels using the values stored at each FB pixelShading is parallel (SIMD) and only for visible surfacesRasterization Papers to ReadSiggraph 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 McNamaraSiggraph 1988 – “A Parallel Algorithm for Polygon Rasterization,”Juan PinedaSiggraph 2005 – Resolution-Independent Curve Rendering Using Programmable Graphics Hardware, Charles Loop, Jim BlinnRasterization Special Cases*** Watch for special casesDefine a convention for pixels on exact L/R T/B edgesUse edge-eval, slope, or intercept method for L/R sortOne edge covers pixel, the other does notHorizontal edges carefully sort edges and loop over pixelsSmall or thin tris can cover zero pixels or have gaps between pixelsEnsure loop code manages zero-iteration casesTest 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 triangles edgeVertex x-sortdoes not robustly identify L/R edges)(xfbmxy=+=xxfyxxyD+=D+)(‘)(