Clipping Apart from clipping to the view volume clipping is a basic operation in many other algorithms Breaking space up into chunks 2D drawing and windowing Modelling May require more complex geometry than rectangular boxes Hardware Sutherland Hodgman Suitable for hardware implementation Only need the clip edge the endpoints of the current edge and the last output point Polygon edges are output as they are found and passed right on to the next clip region edge Vertices in Clip Top Clip Right Clipped vertices out Clip Bottom Clip Left Inside Outside Testing Edges Planes store a vector pointing toward the outside of the clip region Dot products give inside outside information Outside n Inside n s x 0 x n i x 0 f s x i s n f x 0 Inside Outside in Screen Space In screen space clip planes are xs 1 ys 1 zs 0 zs 1 Inside Outside reduces to comparisons before perspective divide ws xs ws ws y s ws 0 zs ws Finding Intersection Pts Watt Sect 1 4 3 1 4 4 Use the parametric form for the line between two points x1 and x2 x t x1 x 2 x1 t 0 t 1 For planes of the form x a y2 y1 z2 z1 xi a y1 a x1 z1 a x1 x2 x1 x2 x1 Similar forms for y a z a Solution for general plane in textbook Additional Clipping Planes Useful for doing things like cut away views Use a clip plane to cut off part of the object Only works if piece to be left behind is convex OpenGL allows you to do it Also one way to use OpenGL to identify objects in a region of space uses the selection mechanism Clipping Lines Lines can also be clipped by Sutherland Hodgman Slow unless you already have hardware Better algorithms exist Cohen Sutherland Liang Barsky Nicholl Lee Nicholl 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 3 1 Cohen Sutherland 2 2 3 4 4 3 3 4 4 1 2 1 2 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 Cohen Sutherland Details Only need to clip line against edges where one endpoint is out Use outcode to record endpoint in out wrt each edge One bit per edge 1 if out 0 if in 1 2 Trivial reject 0010 outcode x1 outcode x2 0 Trivial accept 3 outcode x1 outcode x2 0 Which edges to clip against outcode x1 outcode x2 4 0101 Liang Barsky Clipping Parametric clipping view line in parametric form and reason about the parameter values More efficient as not computing the coordinate values at irrelevant vertices Clipping conditions on parameter Line is inside clip region for values of t such that xmin x1 t x xmax ymin y1 t y ymax x x2 x1 y y2 y1 Liang Barsky 2 Infinite line intersects clip region edges when qk tk pk where p1 x p 2 x p 3 y p 4 y q1 x 1 x min q 2 x max x 1 q 3 y1 y min q 4 y max y1 Liang Barsky 3 When pk 0 as t increases line goes from outside to inside enter When pk 0 line goes from inside to outside leave When pk 0 line is parallel to an edge clipping is easy If there is a segment of the line inside the clip region sequence of infinite line intersections must go enter enter leave leave Liang Barsky 4 Enter Leave Leave Leave Enter Enter Enter Leave Liang Barsky Algorithm Compute entering t values which are qk pk for each pk 0 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 Nicholl Lee Nicholl clipping Some edges are irrelevant to clipping particularly if one vertex lies inside region Cases x1 in x1 in corner region x1 in edge region For each case we generate specialized test regions for x2 which use simple tests slope and tell which edges to clip against a a a Nicholl Lee Nicholl 2 Special cases for each endpoint location and slope Number of cases explodes in 3D making it unsuitable 1 Reject 2 3 Top Left Top Right 4 Left bottom Top Bottom Weiler Atherton Polygon Clipping Inside For clockwise polygon for out to in pair follow usual rule for in to out pair follow clip edge 2 3 go up Easiest to start outside 1 4 5 6 8 go up 7 General Clipping Clipping general against general polygons is quite hard Outline of Weiler algorithm Replace crossing points with vertices Double all edges and form linked lists of edges Change links at vertices Enumerate polygon patches Can use clipping to break concave polygon into convex pieces main issue is inside outside for edges Weiler Algorithm 1 Rearranging pointers makes it possible to enumerate all components of the intersection Changes to
View Full Document
Unlocking...