Last TimeTodayClipping LinesCohen-Sutherland (1)Cohen-Sutherland (2)Cohen-Sutherland (3)Cohen-Sutherland - DetailsLiang-Barsky ClippingParamteric ClippingParametric IntersectionSlide 11Entering or Leaving?Entering and LeavingLiang-Barsky - AlgorithmGeneral Liang-BarskyIn View SpaceFirst StepFinding Parametric IntersectionWeiler Atherton Polygon ClippingGeneral ClippingWeiler Algorithm (1)Slide 22Where We StandSlide 24Drawing PointsDrawing LinesLine Drawing AlgorithmsBresenham’s Algorithm OverviewMidpoint MethodsMidpoint Decision VariableWhat Can We Decide?Updating The Decision VariableBresenham’s AlgorithmMidterm Info3/2/04 © University of Wisconsin, CS559 Spring 2004Last Time•General Perspective–Methods for specifying the view volume•As a set of clip planes•As a field of view and aspect ratio–Near and Far clip planes and depth resolution•Sutherland-Hodgman Clipping–For clipping points, lines or polygons against convex clip regions–Clip against each clip plane in turn–Rewrite vertex lists3/2/04 © University of Wisconsin, CS559 Spring 2004Today•More clipping–Cohen-Sutherland–Liang-Barsky–Project 2 clipping–Weiler-Atherton–Weiler•Drawing lines3/2/04 © University of Wisconsin, CS559 Spring 2004Clipping Lines•Lines can be clipped by Sutherland-Hodgman–Slower than necessary, unless you already have hardware•Better algorithms exist–Cohen-Sutherland–Liang-Barsky–Nicholl-Lee-Nicholl (we won’t cover this one – only good for 2D)3/2/04 © University of Wisconsin, CS559 Spring 2004Cohen-Sutherland (1)•Works basically the same as Sutherland-Hodgman–Was developed earlier•Clip line against each edge of clip region in turn–If both endpoints outside, discard line and stop–If both endpoints in, continue to next edge (or finish)–If one in, one out, chop line at crossing pt and continue•Works in both 2D and 3D for convex clipping regions3/2/04 © University of Wisconsin, CS559 Spring 2004Cohen-Sutherland (2)1 2341 234341 2341 23/2/04 © University of Wisconsin, CS559 Spring 2004Cohen-Sutherland (3)•Some cases lead to premature acceptance or rejection–If both endpoints are inside all edges–If both endpoints are outside one edge•General rule of clipping – if a fast test can cover many cases, do it first3/2/04 © University of Wisconsin, CS559 Spring 2004Cohen-Sutherland - Details•Only need to clip line against edges where one endpoint is out•Use outcode to record endpoint in/out of each edge. One bit per edge, 1 if out, 0 if in–Codes can be computed very quickly – they are not independent for rectangular clip regions•Trivial reject: –outcode(x1) & outcode(x2)!=0•Trivial accept:–outcode(x1) | outcode(x2)==0•Which edges to clip against?–outcode(x1) ^ outcode(x2)1 234001001013/2/04 © University of Wisconsin, CS559 Spring 2004Liang-Barsky Clipping•Parametric clipping - view line in parametric form and reason about the parameter values–Parametric form: x = x1+(x2-x1)t–t[0,1] are points between x1 and x2•Liang-Barsky is more efficient than Cohen-Sutherland–Computing intersection vertices is most expensive part of clipping–Cohen-Sutherland may compute intersection vertices that are later clipped off, and hence don’t contribute to the final answer•Works for convex clip regions in 2D or 3D3/2/04 © University of Wisconsin, CS559 Spring 2004Paramteric Clipping•Recall, points inside a convex region are inside all clip planes•Parametric clipping finds the values of t, the parameter, that correspond to points inside the clip region•Consider a rectangular clip region•Line is inside clip region for values of t such that (for 2D):12max1min12max1min yyyyytyyxxxxxtxxxminxmaxyminymax3/2/04 © University of Wisconsin, CS559 Spring 2004Parametric Intersection•Infinite line intersects clip region edges when:kkkpqt 1maxmin11maxmin1yyqypyyqypxxqxpxxqxptoptopbottombottomrightrightleftleftwhere3/2/04 © University of Wisconsin, CS559 Spring 2004Parametric Intersectiontbottomtleftttoptright3/2/04 © University of Wisconsin, CS559 Spring 2004Entering or Leaving?•When pk<0, as t increases line goes from outside to inside - entering•When pk>0, line goes from inside to outside – leaving•When pk=0, line is parallel to an edge (clipping is easy)•Major Insight: The infinite line must not move outside a clip plane (leave) before it moves inside another (enters)–If it does leave before it enters, it cannot be inside all the planes•For rectangular, if there is a segment of the line inside the clip region, sequence of infinite line intersections must go: enter, enter, leave, leave3/2/04 © University of Wisconsin, CS559 Spring 2004Entering and LeavingEnterEnterLeaveLeaveEnterLeaveEnterLeave3/2/04 © University of Wisconsin, CS559 Spring 2004Liang-Barsky - Algorithm•Compute entering t values, which are qk/pk for each pk<0–There will always be two for 2D rectangular clip region, three in 3D•Compute leaving t values, which are qk/pk for each pk>0•Parameter value for small t end of line is: tsmall= max(0, entering t’s)•Parameter value for large t end of line is: tlarge=min(1, leaving t’s)•If tsmall<tlarge, there is a line segment - compute endpoints by substituting t values•Improvement (and actual Liang-Barsky):–compute t’s for each edge in turn (some rejects occur earlier like this)3/2/04 © University of Wisconsin, CS559 Spring 2004General Liang-Barsky•Liang-Barsky works for any convex clip region–Compute intersection t for all clip lines/planes and label them as entering or exiting–Parameter value for small t end of line is:tsmall= max(0, entering t’s)–Parameter value for large t end of line is: tlarge=min(1, leaving t’s)–if tsmall<tlarge, there is a line segment - compute endpoints by substituting t values3/2/04 © University of Wisconsin, CS559 Spring 2004In View Space•For Project 2, you need to clip edges to a view frustum in world space•Situation is:eye, efrustumxrightxleftx1x23/2/04 © University of Wisconsin, CS559 Spring 2004First Step•Determine which side of each clip plane the segment endpoints lie–Use the cross product–What do we know if (x1 - e) (xleft - e) > 0 ?–Other cross products give other information•What can we say if both segment endpoints are outside one clip plane?–Stop here if we can, otherwise…3/2/04 © University
View Full Document
Unlocking...