計(jì)算機(jī)圖形學(xué)computer graphics課件15

1、from vertices to fragmentssoftware college, shandong university instructor: zhou yuanfeng e-mail: reviewshading in opengl;lights & material;from vertex to fragment:cohen-sutherland2projectionfragmentsclippingshadingblack boxsurface hiddentexturetransparency3objectivesgeometric processing: cyrus-

2、beck clipping algorithm liang-barsky clipping algorithmintroduce clipping algorithm for polygonsrasterization: dda & bresenhamcohen-sutherlandin case iv: o1 & o2 = 0intersection: clipping lines by solving simultaneous equations4solving simultaneous equationsequation of a line:- slope-interce

3、pt: y = mx + h difficult for vertical line- implicit equation: ax + by + c = 0- parametric: line defined by two points, p0 and p1 p(t) = p0 + (p1 - p0) t x(t) = x0 + (x1 - x0) t y(t) = x0 + (y1 - y0) t6parametric lines and intersectionsfor l1 :x=x0l1 + t(x1l1 x0l1)y=y0l1 + t(y1l1 y0l1)for l2 :x=x0l2

4、 + t(x1l2 x0l2)y=y0l2 + t(y1l2 y0l2)the intersection point:x0l1 + t1 (x1l1 x0l1) = x0l2 + t2 (x1l2 x0l2) y0l1 + t1 (y1l1 y0l1) = y0l2 + t2 (y1l2 y0l2)cyrus-beck algorithm (1978) for polygons mike cyrus, jay beck. generalized two- and three-dimensional clipping. computers & graphics, 1978: 23-28.

5、given a convex polygon r:7cyrus-beck algorithmp1p2anrpara tspara te112)()(ptpptp0t1 0)(atpn)(tp,then is inside of r;0)(atpn)(tp0)(atpn)(tp,then is on r or extension;,then is outside of r.cos)( )(atpnatpn0cos 900cos 900cos 90how to get ts and tecyrus-beck algorithmintersection:nl (p(t) a) = 0substitu

6、te line equation for p(t) p(t) = p0 + t(p1 - p0)solve for t t = nl (p0 a) / -nl (p1 - p0)anlp(t)insideoutsidep0p1cyrus-beck algorithmcompute t for line intersection with all edges;discard all (t 1);classify each remaining intersection as- potentially entering point (pe)- potentially leaving point (p

7、l) (how?)nl(p1 - p0) 0 implies penote that we computed this term in when computing tcyrus-beck algorithmfor each edge:10l1l2l3l4l5p0p1t1t2t5t3t4para tspara te010()()0, 01iiiiipapp ttnn1010max0,max |()0min1,min |()0siieiittppttppnncompute pe with largest tcompute pl with smallest tclip to these two p

8、ointscyrus-beck algorithmwhen ; then ifif1110()0ippn0()0iipanthen p0p1 is invisible;0()0iipanthen go to next edge;10()ippnprogramming:12for（k edges of clipping polygon） solve ni(p1-p0); solve ni(p0-ai); if ( ni(p1-p0) = = 0 ) /parallel with the edge if ( ni(p0-ai) 0 ) break; /invisible else go to ne

9、xt edge; else / ni(p1-p0) != 0 solve ti; if ( ni(p1-p0) te ) return nil;else return p(ts) and p(te) as the true clip intersections;input:if (p0 = p1 ) line is degenerate so clip as a point;liang-barsky algorithm (1984)13the only algorithm named for chinese people in computer graphics course bookslia

10、ng, y.d., and barsky, b., a new concept and method for line clipping, acm transactions on graphics, 3(1):1-22, january 1984.because of horizontal and vertical clip lines: many computations reduce normals pick constant points on edgessolution for t:tl=-(x0 - xleft) / (x1 - x0)tr=(x0 - xright) / -(x1

11、- x0)tb=-(y0 - ybottom) / (y1 - y0)tt=(y0 - ytop) / -(y1 - y0)liang-barsky algorithm (1984)peplp1plpep0(-1, 0)(1, 0)(0, -1)(0, 1)15)()(121ppaptnn)()(121xxxlx121)(xxxrx)()(121yyyby121)(yyytyedgeinner normalap1-aleftx=xl（1，0）（xl，y）（x1-xl， y1-y）rightx=xr（-1，0）（xr，y）（x1-xr，y1-y）bottomy=yb（0，1）（x，yb）（x1-

12、x，y1-yb）topy=yt（0，-1）（x，yt）（x1-x，y1-yt）liang-barsky algorithm (1984)when rk0, tk is leaving point. if rk=0 and sk xmaxtop viewclipping polygonsclipping polygons is more complex than clipping the individual lines- input: polygon- output: polygon, or nothing25polygon clippingnot as simple as line segm

13、ent clipping- clipping a line segment yields at most one line segment- clipping a polygon can yield multiple polygonshowever, clipping a convex polygon can yield at most one other polygon26tessellation and convexity one strategy is to replace nonconvex (concave) polygons with a set of triangular pol

14、ygons (a tessellation) also makes fill easier (we will study later) tessellation code in glu library, the best is constrained delaunay triangulation27pipeline clipping of polygons three dimensions: add front and back clippers strategy used in sgi geometry engine small increase in latencysutherland-h

15、odgman clipping ivan sutherland, gary w. hodgman: reentrant polygon clipping. communications of the acm, vol. 17, pp. 32-42, 1974basic idea:- consider each edge of the viewport individually- clip the polygon against the edge equationsutherland-hodgman clippingbasic idea:- consider each edge of the v

16、iewport individually- clip the polygon against the edge equation- after doing all planes, the polygon is fully clippedsutherland-hodgman clippingbasic idea:- consider each edge of the viewport individually- clip the polygon against the edge equation- after doing all planes, the polygon is fully clip

17、pedsutherland-hodgman clippingbasic idea:- consider each edge of the viewport individually- clip the polygon against the edge equation- after doing all planes, the polygon is fully clippedsutherland-hodgman clippingbasic idea:- consider each edge of the viewport individually- clip the polygon agains

18、t the edge equation- after doing all planes, the polygon is fully clippedsutherland-hodgman clippingbasic idea:- consider each edge of the viewport individually- clip the polygon against the edge equation- after doing all planes, the polygon is fully clippedsutherland-hodgman clippingbasic idea:- co

19、nsider each edge of the viewport individually- clip the polygon against the edge equation- after doing all planes, the polygon is fully clippedsutherland-hodgman clippingbasic idea:- consider each edge of the viewport individually- clip the polygon against the edge equation- after doing all planes,

20、the polygon is fully clippedsutherland-hodgman clippingbasic idea:- consider each edge of the viewport individually- clip the polygon against the edge equation- after doing all planes, the polygon is fully clippedsutherland-hodgman clippingbasic idea:- consider each edge of the viewport individually

21、- clip the polygon against the edge equation- after doing all planes, the polygon is fully clippedwill this work for non-rectangular clip regions?what would 3-d clipping involve?sutherland-hodgman clippinginput/output for algorithm:- input: list of polygon vertices in order - output: list of clipped

22、 poygon vertices consisting of old vertices (maybe) and new vertices (maybe)note: this is exactly what we expect from the clipping operation against each edgesutherland-hodgman clippingsutherland-hodgman basic routine:- go around polygon one vertex at a time- current vertex has position p - previous

23、 vertex had position s, and it has been added to the output if appropriatesutherland-hodgman clippingedge from s to p takes one of four cases:(gray line can be a line or a plane)insideoutsidespp outputinsideoutsidespno outputinsideoutsidespi outputinsideoutsidespi outputp outputsutherland-hodgman cl

24、ippingfour cases:- s inside plane and p inside plane add p to output note: s has already been added- s inside plane and p outside plane find intersection point i add i to output- s outside plane and p outside plane add nothing- s outside plane and p inside plane find intersection point i add i to ou

25、tput, followed by psutherland-hodgman clipping42point-to-plane testa very general test to determine if a point p is “inside” a plane p, defined by q and n:(p - q) n 0: p outside ppnpqpnpqpnpq44bounding boxes rather than doing clipping on a complex polygon, we can use an axis-aligned bounding box or

26、extent- smallest rectangle aligned with axes that encloses the polygon- simple to compute: max and min of x and y45bounding boxes can usually determine accept/reject based only on bounding boxrejectacceptrequires detailed clippingellipsoid collision detection46rasterizationrasterization (scan conver

27、sion)- determine which pixels that are inside primitive specified by a set of vertices- produces a set of fragments- fragments have a location (pixel location) and other attributes such color, depth and texture coordinates that are determined by interpolating values at verticespixel colors determine

28、d later using color, texture, and other vertex properties.47scan conversion of line segmentsstart with line segment in window coordinates with integer values for endpointsassume implementation has a write_pixel functiony = mx + hxymscan conversion of line segments48one pixel49dda algorithm digital d

29、ifferential analyzer (1964)- dda was a mechanical device for numerical solution of differential equations- line y=mx+h satisfies differential equation dy/dx = m = y/x = y2-y1/x2-x1along scan line x = 1for(x=x1; x 1, swap role of x and y- for each y, plot closest x52bresenhams algorithm dda requires

30、one floating point addition per step we can eliminate all fp through bresenhams algorithm consider only 1 m 0- other cases by symmetry assume pixel centers are at half integers (opengl has this definition) bresenham, j. e. (1 january 1965). algorithm for computer control of a digital plotter. ibm sy

31、stems journal 4(1): 2530. bresenhams algorithmobserving: if we start at a pixel that has been written, there are only two candidates for the next pixel to be written into the frame buffer5354candidate pixels1 m 0last pixelcandidatesnote that line could havepassed through anypart of this pixel55decis

32、ion variable-d = x(a-b)d is an integerd 0 use lower pixelhow to compute a and b?b-a =(yi+1yi,r)-( yi,r+1-yi+1) =2yi+1yi,r(yi,r+1) = 2yi+12yi,r1(xi+1)= yi+1yi,r0.5 =bc-ac=ba=b-a = yi+1(yi,r+ yi,r+1)/2abcincremental form56if (xi+1) 0, yi+1,r= yi,r+1, pick pixel d, the next pixel is ( xi+1, yi,r+1)yi,r

33、yi,r+1abxixi+1dcd1d2yi,ryi,r+1axixi+1dcd1d2if (xi+1) 0dk+1= dk 2(y - x), otherwisefor each x, we need do only an integer addition and a testsingle instruction on graphics chips multiply 2 is simple.59bsp displaytype tree-tree* front;-face face;-tree *back;endalgorithm drawbsp(tree t; point: w)-/w 為視

34、點(diǎn)-if t is null then return; endif-if w is in front of t.face then drawbsp(t.back,w); draw(t.face,w); drawbsp(t.front,w);-else / w is behind or on t.face drawbsp(t.front,w); draw(t.face,w); drawbsp(t. back,w);-endifend60hidden surface removalobject-space approach: use pairwise testing between polygon

35、s (objects)worst case complexity o(n2) for n polygonspartially obscuringcan draw independently61image space approachlook at each projector (nm for an n x m frame buffer) and find closest of k polygonscomplexity o(nmk)ray tracing z-buffer62painters algorithmrender polygons a back to front order so th

36、at polygons behind others are simply painted overb behind a as seen by viewerfill b then a63depth sortrequires ordering of polygons first - o(n log n) calculation for ordering- not every polygon is either in front or behind all other polygons order polygons and deal with easy cases first, harder lat

37、erpolygons sorted by distance from cop64easy cases(1) a lies behind all other polygons- can render(2) polygons overlap in z but not in either x or y- can render independently65hard cases(3) overlap in all directionsbut can one is fully on one side of the othercyclic overlappenetration(4) 66back-face

38、 removal (culling)face is visible iff 90 -90equivalently cos 0or v n 0plane of face has form ax + by +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 67z-buffer algorithm use a b

39、uffer called the z or depth buffer to store the depth of the closest object at each pixel found so far as we render each polygon, compare the depth of each pixel to depth in z buffer if less, place shade of pixel in color buffer and update z buffer68efficiencyif we work scan line by scan line as we

40、move across a scan line, the depth changes satisfy ax+by+cz=0along scan line y = 0z = - xcain screen space x = 1 69scan-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

41、 only when inmore than one polygon 70implementationneed a data structure to store- flag for each polygon (inside/outside)- incremental structure for scan lines that stores which edges are encountered - parameters for planes 71visibility testingin many realtime applications, such as games, we want to

42、 eliminate as many objects as possible within the application- reduce burden on pipeline- reduce traffic on buspartition space with binary spatial partition (bsp) tree72simple exampleconsider 6 parallel polygonstop viewthe plane of a separates b and c from d, e and f73bsp treecan continue recursivel

43、y - plane of c separates b from a- plane of d separates e and fcan put this information in a bsp tree- use for visibility and occlusion testing 74polygon scan conversionscan conversion = fillhow to tell inside from outside- convex easy- nonsimple difficult- odd even test count edge crossings-winding numberodd-even fill75winding numbercount clockwise encirclements of pointalternate definition of inside: inside if winding number 0winding number = 2winding number = 176filling in the frame bufferfill at end of pipeline- convex polygons only-