Visiblity: Culling and ClippingToday’s topicsWhat are culling and clipping?Culling exampleSlide 5Lines and planesSlide 7Testing objects for containmentConservative testingView frustum cullingHierachical cullingBack-face cullingManifoldFace plane testWinding order testBack-face culling in OpenGLOcclusion culling with occlusion queriesSlide 18Slide 19Clipping a line segment against a lineClipping a polygon against a lineClipping against a convex regionHomogeneous clippingCulling and clipping in the rendering pipeline1Visiblity: Culling and ClippingComputer GraphicsCOMP 770 (236)Spring 2009January 21 & 26: 20092Today’s topics■Lines and planes■Culling °View frustum culling°Back-face culling°Occlusion culling°Hierarchical culling■Clipping3What are culling and clipping?■Culling°Throws away entire objects and primitives that cannot possibly be visible°An important rendering optimization (esp. for large models)■Clipping°“Clips off” the visible portion of a primitive°Simplifies rasterization °Used to create “cut-away” views of a model4Culling example■Power plant model°13 M triangles°1.7 M triangles - gutted version show here with no internal pipes2/05/075Culling exampleFull model1.7 MtrisView frustum culling1.4 MtrisOcculsion culling89 Ktris6■Implicit equation for line (plane):■If is normalized then d gives the distance of the line (plane) from the origin along ■Transforming points and lines with transformation M: points: lines:Lines and planes�nd(0,0)x yx ynx n y d 0x[n n d] y 0 l p 01+ - =����- = � �=������&p p�=M& &1l l-�= Ml  p  0 nvnv2/05/077■Lines (planes) partition 2D (3D)space:°positive and negative half spaces■The union of negative half-spacesdefines a convex regionLines and planes�nd(0,0)l p 0�>&l p 0�<&l  p  0 8Testing objects for containmentOutside Straddling Inside2/05/079Conservative testingOutsiderc&l c r�>&Indeterminater l c r- < �<&rc&Insidel c r�<-&rc&■Use cheap, conservative bounds for trivial cases■Can use more accurate, more expensive tests for ambiguous cases if needed2/05/0710View frustum culling■Test objects against planes defining view frustum■How do you compute them?■Other planes can be computed similarly-1 11-1Ml [1 0 1]= -tc1 c3l l (m m )�= = -Mcolumn 1- column 32/05/0711Hierachical culling■Culling needs to be cheap!■Bounding volume hierarchies accelerate culling by trivially rejecting/accepting entire sub-trees at a time■Simple algorithm: while( node is indeterminate ) recurse on childrennot visitedvisitedInsideIndeterminateIndeterminateIndeterminate OutsideInsideInside2/05/0712Back-face culling■Special case of occlusion - convex self-occlusion°for closed objects (has well-defined inside and outside) some parts of the surface must be blocked by other parts of the surface■Specifically, the backside of the object is not visible13Manifold■Back-face culling can be applied to any orientable two-manifold. ■Orientable two-manifolds have the following properties.1. All points on the surface are locally like a plane. No holes, cracks, or self-intersections. 2. Boundary partitions 3D space into interior and exterior regions ■In our case, manifolds will be composite objects made of many primitives, generally triangles. ■Back-face culling eliminates a subset of these primitives. °Assumes that you are outside of all objects.2/05/0714Face plane test■Compute the plane for the face:■Cull if eye point in the negative half-space 1 0 2 0n (v v ) (v v )= - � -v& & & &0v&1v&2v&0d n v= �v&15Winding order test■Back-faces have a clockwise vertex ordering when viewed from outside.■Typically used by graphics hardware during triangle setup2/05/0716Back-face culling in OpenGL if (cull): glFrontFace(GL_CCW) # define winding order glEnable(GL_CULL_FACE) # enable Culling glCullFace(GL_BACK) # which faces to cull else: glDisable(GL_CULL_FACE) ■Can cull front faces or back faces■Back-face can sometimes double performancefront-face culling2/05/0717Occlusion culling with occlusion queries■Render objects visible in previous frame (occlusion representation)2/05/0718Occlusion culling with occlusion queries■Turn off color and depth writes. ■Render object bounding boxes with occlusion queries.°An occlusion query returns the number of visible pixelsnewly visible2/05/0719Occlusion culling with occlusion queries■Re-enable color writes■Render newly visible objects20Clipping a line segment against a line■First check endpoints against the plane. If they are on the same side, no clipping is needed■Interpolate to get new point■Vertex attributes interpolated the same way0p&1p&p�&l0 1 0p p t(p p )�= + -& & & &l p 0�� =&0 1 001 0l (p t(p p )) 0(l p )tl (p p )� + - =- �=� -& & &&& &21Clipping a polygon against a line■Traverse edges■Keep edges that are entirely inside■Create new point when we exit■Throw away edges entirely outside■Create new point and new edge when we enter22Clipping against a convex region■Sutherland-Hodgman°Just clip against one edge ata time2/05/0723Homogeneous clipping■NDC simplify view frustum clipping■Clip after applying projection matrix, but before the divide by w°clip coordinates■Easy in/out test and interpolation. Other coordinates treated exactly the same way-1 1xww 1=w x=w x=-w x w- < <xl+xi i i0 00 0 1 1l [1 1 0]v [x w 1]w xt(w x ) (w x)+= -=-=- - -&T0v&1v&Add extra coordinateso we can use our lineequation2/05/0724Culling and clipping in therendering pipeline Culling done by applicationView frustum clipping on clip coordinates.Back-face culling done in setup phaseof rasterization. Eye coordinates. View frustum clipping andback-face culling can be done