Clipping Jian Huang CS594 This set of slides reference slides devised at Ohio State and MIT Viewing Pipeline Revisited Object Space World Space Eye Space Clipping Space Canonical view volume Screen Space Object space coordinate where each component is defined World space all components put together via affine transformation camera lighting defined in this space Eye space camera at the origin view direction coincides with the z axis Hither and Yon perpendicular to the z axis Clipping space All point is in homogeneous coordinate Perspective division gets everything into 3D image space 3D image space Canonical view volume a parallelpipied shape defined by 1 1 1 1 0 1 Objects distorted Screen space x and y mapped to screen pixel coordinates January 14 2019 2 Why do clipping Clipping is a visibility preprocess In real world scenes clipping can remove a substantial percentage of the environment from consideration Clipping offers an important optimization January 14 2019 3 What is clipping two views Clipping is to spatially partition geometric primitives according to their containment within some region Clipping can be used to Distinguish whether geometric primitives are inside or outside of a viewing frustum or picking frustum Detecting intersections between primitives Clipping is to subdivide geometric primitives Several other potential applications Binning geometric primitives into spatial data structures computing analytical shadows January 14 2019 4 Point Clipping Ymax Ymin Xmin x y Xmax is inside iff Xmin x Xmax AND Y January 14 2019 y Y min max 5 Line Clipping Half Plane Tests Modify endpoints to lie in rectangle Interior of rectangle Answer intersection of 4 half planes 3D intersection of 6 half planes ymax interior ymin xmin January 14 2019 xmax y ymax x xmin y ymin x xmax 6 Line Clipping Is end point inside a clip region half plane test If outside calculate intersection betwee line and the clipping rectangle and make this the new end point January 14 2019 Both endpoints inside trivial accept One inside find intersection and clip Both outside either clip or reject tricky case 7 Cohen Sutherland Algorithm Outcode clipping Classifies each vertex of a primitive by generating an outcode An outcode identifies the appropriate half space location of each vertex relative to all of the clipping planes Outcodes are usually stored as bit vectors January 14 2019 8 Cohen Sutherland Algorithm Outcode clipping if outcode1 0000 and outcode2 0000 then line segment is inside else if outcode1 AND outcode2 0000 then line segment potentially crosses clip region else line is entirely outside of clip region endif endif January 14 2019 9 The Maybe cases If neither trivial accept nor reject Pick an outside endpoint with nonzero outcode Pick an edge that is crossed nonzero bit of outcode Find line s intersection with that edge Replace outside endpoint with intersection point Repeat outcode test until trivial accept or reject January 14 2019 10 The Maybe case January 14 2019 11 The Maybe Case January 14 2019 12 One Plane At a Time Clipping a k a Sutherland Hodgeman Clipping The Sutherland Hodgeman triangle clipping algorithm uses a divide and conquer strategy Clip a triangle against a single plane Each of the clipping planes are applied in succession to every triangle There is minimal storage requirements for this algorithm and it is well suited to pipelining It is often used in hardware implementations January 14 2019 13 Sutherland Hodgman Polygon Clipping Algorithm Subproblem clip a polygon input vertex list against a single clip edges output the vertex list s for the resulting clipped polygon s Clip against all four planes generalizes to 3D 6 planes generalizes to any convex clip polygon polyhedron Used in viewing transforms January 14 2019 14 Polygon Clipping At Work January 14 2019 15 Sutherland Hodgman SHclippedge var ilist olist list ilen olen edge integer s ilist ilen olen 0 for i 1 to ilen do d ilist i if inside d edge then if inside s edge then addlist d olist case 1 olen olen 1 else case 4 n intersect s d edge addlist n olist addlist d olist else if inside s edge then s d olen olen 2 case 2 n intersect s d edge addlist n olist olen end for January 14 2019 16 Sutherland Hodgman SHclip var ilist olist list ilen olen integer SHclippedge ilist tmplist1 ilen tlen1 RIGHT SHclippedge tmplist1 tmplist2 tlen1 tlen2 BOTTOM SHclippedge tmplist2 tmplist1 tlen2 tlen1 LEFT SHclippedge tmplist1 olist tlen1 olen TOP January 14 2019 17 With Pictures January 14 2019 18 Sutherland Hodgman Advantages Elegant few special cases Robust handles boundary and edge conditions well Well suited to hardware Canonical clipping makes fixed point implementations manageable Disadvantages Only works for convex clipping volumes Often generates more than the minimum number of triangles needed Requires a divide per edge January 14 2019 19 Interpolating Parameters January 14 2019 20 3D Clipping Planes y x z image plane near far Red Polygon Clip Transform into 4D Clipping space canonical viewing volume Homogenous co ordinates January 14 2019 21 Na ve 3D Euclidean Space Clipping After perspective projection Euclidean space is not linear January 14 2019 22 Difficulty with Euclidean Space Clipping Clipping will handle most cases However there is one case in general that cannot be handled this way Parts of a primitive lie both in front of and behind the viewpoint This complication is caused by our projection stage It has the nasty habit of mapping objects in behind the viewpoint to positions in front of it Solution January 14 2019 clip in homogeneous coordinate 23 4DPolygonClip Use Sutherland Hodgman algorithm Use arrays for input and output lists There are six planes of course January 14 2019 24 4D Clipping OpenGL uses 1 x 1 1 y 1 1 z 1 We use 1 x 1 1 y 1 1 z 0 Must clip in homogeneous coordinates w 0 w x w w y w w z 0 w 0 w x w w y w w z 0 Consider each case separately January 14 2019 What issues arise 25 4D Clipping Point A is inside Point B is outside Clip edge AB x Ax t Bx Ax y Ay t By Ay z Az t Bz Az w Aw t Bw Aw Clip boundary x w 1 i e x w 0 w x Aw Ax t Bw Aw Bx Ax 0 Solve for t January 14 2019 26 Still have issues with 4D Clipping W X W X P1 1 2 3 4 W 1 P2 1 2 3 4 P1 and P2 map to same physical point Solution Clip against both regions Negate points with negative W January 14 2019 27 Still have issues with 4D Clipping P1 Inf W 1 Inf P2 Line straddles both regions After projection one gets two line segments How to do this Only
View Full Document
Unlocking...