Last 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 lists 3 2 04 University of Wisconsin CS559 Spring 2004 Today More clipping Cohen Sutherland Liang Barsky Project 2 clipping Weiler Atherton Weiler Drawing lines 3 2 04 University of Wisconsin CS559 Spring 2004 Clipping 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 2004 Cohen 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 regions 3 2 04 University of Wisconsin CS559 Spring 2004 Cohen Sutherland 2 1 2 3 3 4 4 3 3 4 4 1 3 2 04 2 1 2 1 2 University of Wisconsin CS559 Spring 2004 Cohen 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 first 3 2 04 University of Wisconsin CS559 Spring 2004 Cohen 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 1 Trivial reject outcode x1 outcode x2 0 Trivial accept 0010 2 3 outcode x1 outcode x2 0 Which edges to clip against outcode x1 outcode x2 3 2 04 4 University of Wisconsin CS559 Spring 2004 0101 Liang 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 3D 3 2 04 University of Wisconsin CS559 Spring 2004 Paramteric 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 ymax Consider a rectangular clip region xmin xmax ymin Line is inside clip region for values of t such that for 2D xmin x1 t x xmax ymin y1 t y ymax 3 2 04 x x2 x1 y y2 y1 University of Wisconsin CS559 Spring 2004 Parametric Intersection Infinite line intersects clip region edges when qk tk pk where pleft x qleft x1 xmin pright x qright xmax x1 pbottom y qbottom y1 ymin ptop y 3 2 04 qtop ymax y1 University of Wisconsin CS559 Spring 2004 Parametric Intersection ttop tbottom 3 2 04 tleft University of Wisconsin CS559 Spring 2004 tright Entering 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 leave 3 2 04 University of Wisconsin CS559 Spring 2004 Entering and Leaving Leave Enter Leave Leave Enter Enter 3 2 04 Enter University of Wisconsin CS559 Spring 2004 Leave Liang 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 2004 General 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 values 3 2 04 University of Wisconsin CS559 Spring 2004 In View Space For Project 2 you need to clip edges to a view frustum in world space Situation is xleft xright frustum x1 x2 eye e 3 2 04 University of Wisconsin CS559 Spring 2004 First 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 of Wisconsin CS559 Spring 2004 Finding Parametric Intersection Left clip edge x e xleft e t Line x x1 x2 x1 s Solve simultaneous equations in t and s e x x left x e x t x1 x x 2 x x1 x s e y x left y e y t x1 y x 2 y x1 y s Use endpoint inside outside information to label as entering or leaving Now we have general Liang Barsky case 3 2 04 University of Wisconsin CS559 Spring 2004 Weiler Atherton Polygon Clipping Inside Faster than SutherlandHodgman for complex polygons For clockwise polygon 2 for out to in pair follow usual rule for in to out pair follow clip edge 3 go up 1 4 Easiest to start outside 5 6 8 go up 7 3 2 04 University of Wisconsin CS559 Spring 2004 General Clipping Clipping general against general polygons is quite hard Outline of Weiler algorithm 3 2 04 Replace crossing points with vertices Double all edges and form linked lists of edges Change links at vertices Enumerate polygon patches University of Wisconsin CS559 Spring 2004 Weiler Algorithm 1 3 2 04 University of Wisconsin CS559 Spring 2004 Rearranging pointers …
View Full Document
Unlocking...