《计算机图形学computergraph》由会员分享，可在线阅读，更多相关《计算机图形学computergraph（52页珍藏版）》请在金锄头文库上搜索。
1、From Vertices to Fragments IISoftware College, Shandong University Instructor: Zhou Yuanfeng ReviewCyrusBeck clipping algorithm;LiangBarsky clipping algorithm;SutherlandHodgman polygon clipping;DDA line algorithm;Bresenhams line algorithm;3ObjectivesRasterization: Polygon scan conversion algorithm;H
2、idden surface removalAliasing4Polygon Scan ConversionScan Conversion = FillHow to tell inside from outsideConvex easyNonsimple difficultOdd even testCount edge crossingsWinding numberoddeven fill5Winding NumberCount clockwise encirclements of pointAlternate definition of inside: inside if winding nu
3、mber 0winding number = 2winding number = 1OpenGL & Concave PolygonOpenGL can only fill convex polygon correctly6OpenGL & Concave Polygon/ create tessellatorGLUtesselator *tess = gluNewTess();/ describe non-convex polygongluTessBeginPolygon(tess, user_data); / first contour gluTessBeginContour(tess);
4、 gluTessVertex(tess, coords0, vertex_data); . gluTessEndContour(tess); .gluTessEndPolygon(tess);/ delete tessellator after processinggluDeleteTess(tess);7Constrained Delaunay Triangulation89Filling in the Frame BufferFill at end of pipelineConvex Polygons onlyNonconvex polygons assumed to have been
5、tessellatedShades (colors) have been computed for vertices (Gouraud shading)Combine with zbuffer algorithmMarch across scan lines interpolating shadesIncremental work small10Using InterpolationspanC1C3C2C5C4scan lineC1 C2 C3 specified by glColor or by vertex shadingC4 determined by interpolating bet
6、ween C1 and C2C5 determined by interpolating between C2 and C3interpolate between C4 and C5 along span 11Flood FillFill can be done recursively if we know a seed point located inside (WHITE)Scan convert edges into buffer in edge/inside color (BLACK)flood_fill(int x, int y) if(read_pixel(x,y)= = WHIT
7、E) write_pixel(x,y,BLACK); flood_fill(x-1, y); flood_fill(x+1, y); flood_fill(x, y+1); flood_fill(x, y-1); /4 directionsFlood Fill12/8 directionsFlood Fill with Scan Line1312121022223322222Stack14Scan Line Fill Can also fill by maintaining a data structure of all intersections of polygons with scan
8、linesSort by scan lineFill each spanvertex order generated by vertex listdesired orderSingularities1516Data StructureScan line fillingFor each scan line:1.Find the intersections of the scan line with all edges of the polygon;2.Sort the intersections by increasing xcoordinate;3.Fill in all pixels bet
9、ween pairs of intersections.Problem:Calculating intersections is slow.Solution:Incremental computation / coherence17Coherence of Region18Trapezoid: inside and outsideCoherence of Scan Linee is an integer; e Intersections number is even; are inside;19insideinsideinsideCoherence of EdgeIntersection po
10、intsof d is le and ldThe number of le = ld and are on the same edge20edy63y24Coherence of EdgeObservation: Not all edges intersect each scanline.Many edges intersected by scanline i will also be intersected by scanline i+1Formula for scanline s is y = s, for an edge is y = mx + bTheir intersection i
11、s s = mxs + b xs = (sb)/mFor scanline s + 1, xs+1 = (s+1 b)/m = xs + 1/mIncremental calculation: xs+1 = xs + 1/m21Data Structure22Edge index table ET Active Edge List AELNode: ymax The max coord y; x The bottom x coord of edge in ET, the intersection x of edge and scan line in AEL. x 1/m next the ne
12、xt nodeWhere is the end of one edgewhile scanningInitial xCurrent scan line and edge intersectionWhen y=y+1, x=x+1/mNext edgeData Structure ET23y1256Data Structure AEL24 AEL is the edges list which intersect with current scan line, the next intersection can be computed by:ActiveEdgeList-5/357AELe0e5
13、4212AEL at y=2 scan line-5/355AELe0e54214AEL at y=3 scan line2ymaxx1/mEdge list is ordered according x increasingAlgorithmConstruct the Edge Table (ET);Active Edge List (AEL) = null;for y = Ymin to Ymax Mergesort ETy into AEL by x value Fill between pairs of x in AEL for each edge in AEL if edge.yma
14、x = y remove edge from AEL else edge.x = edge.x + dx/dy sort AEL by x valueend scan_fill2526Hidden Surface RemovalObjectspace approach: use pairwise testing between polygons (objects space)Worst case complexity O(n2) for n polygonspartially obscuringcan draw independently27Image Space ApproachLook a
15、t each projector (nm for an n x m frame buffer) and find closest of k polygonsComplexity O(nmk)Ray tracing zbufferFast but with low paint quality28Painters AlgorithmRender polygons a back to front order so that polygons behind others are simply painted overB behind A as seen by viewerFill B then A29
16、Depth SortRequires ordering of polygons first O(n log n) calculation for orderingNot every polygon is either in front or behind all other polygonsOrder polygons and deal with easy cases first, harder laterPolygons sorted by distance from COP30Easy Cases(1) A lies behind all other polygonsCan render(
17、2) Polygons overlap in z but not in either x or yCan render independently31Hard Cases(3) Overlap in all directionsbut can one is fully on one side of the othercyclic overlappenetration(4) 32Back-Face Removal (Culling)face is visible iff 90 90equivalently cos 0or v n 0plane of face has form ax + by +
18、cz +d =0but after normalization n = ( 0 0 1 0)T need only test the sign of cIn OpenGL we can simply enable cullingbut may not work correctly if we have nonconvex objects 33z-Buffer AlgorithmUse a buffer called the z or depth buffer to store the depth of the closest object at each pixel found so farA
19、s we render each polygon, compare the depth of each pixel to depth in z bufferIf less, place shade of pixel in color buffer and update z bufferz-Buffer Algorithm34z-Buffer Algorithm35Example36Example37Example3839EfficiencyIf we work scan line by scan line as we move across a scan line, the depth cha
20、nges satisfy ax+by+cz=0Along scan line y = 0z = - xIn screen space x = 1 40Scan-Line AlgorithmCan combine shading and hsr through scan line algorithmscan line i: no need for depth information, can only be in noor one polygon scan line j: need depth information only when inmore than one polygon z-Buf
21、fer Scan-Line4142ImplementationNeed a data structure to storeFlag for each polygon (inside/outside)Incremental structure for scan lines that stores which edges are encountered Parameters for planes for intersections43Visibility TestingIn many realtime applications, such as games, we want to eliminat
22、e as many objects as possible within the applicationReduce burden on pipelineReduce traffic on busPartition space with Binary Spatial Partition (BSP) Tree44Simple Exampleconsider 6 parallel polygonstop viewThe plane of A separates B and C from D, E and F45BSP TreeCan continue recursively Plane of C
23、separates B from APlane of D separates E and FCan put this information in a BSP treeUse for visibility and occlusion testing BSP Tree46BSP Algorithm Choose a polygon P from the list. Make a node N in the BSP tree, and add P to the list of polygons at that node. For each other polygon in the list: If
24、 that polygon is wholly in front of the plane containing P, move that polygon to the list of nodes in front of P. If that polygon is wholly behind the plane containing P, move that polygon to the list of nodes behind P. If that polygon is intersected by the plane containing P, split it into two poly
25、gons and move them to the respective lists of polygons behind and in front of P. If that polygon lies in the plane containing P, add it to the list of polygons at node N. Apply this algorithm to the list of polygons in front of P. Apply this algorithm to the list of polygons behind P.4748BSP display
26、Type TreeTree* front;Face face;Tree *back;EndAlgorithm DrawBSP(Tree T; point: w)/w 为视点If T is null then return; endifIf w is in front of T.face then DrawBSP(T.back,w);Draw(T.face,w);DrawBSP(T.front,w); DrawBSP(T.front,w);Draw(T.face,w);DrawBSP(T. back,w);Endifend49AliasingIdeal rasterized line shoul
27、d be 1 pixel wideChoosing best y for each x (or visa versa) produces aliased raster lines50Antialiasing by Area AveragingColor multiple pixels for each x depending on coverage by ideal lineoriginalantialiasedmagnified51Polygon AliasingAliasing problems can be serious for polygonsJaggedness of edgesSmall polygons neglectedNeed compositing so colorof one polygon does nottotally determine color ofpixelAll three polygons should contribute to colorTime-domain aliasingAdding ray tracing line from one pixel;52
