Culling and ClippingFrom last time…Today’s topicsWhat are culling and clipping?Culling exampleCulling exampleLines and planesLines and planesTesting objects for containmentConservative testingView frustum cullingHierachical cullingBack-face cullingManifoldFace plane testWinding order testBack-face culling in OpenGLOcclusion culling with occlusion queriesOcclusion culling with occlusion queriesOcclusion culling with occlusion queriesClipping a line segment against a lineClipping a polygon against a lineClipping against a convex regionOutcodesOutcode for linesOutcodes for trianglesView frustum clippingHomogeneous clippingCulling and clipping in therendering pipelineNext time2/05/071Culling and ClippingComputer GraphicsCOMP 770 (236)Spring 2007Instructor: Brandon Lloyd2/05/072From last time…■ Representing 3D objects with a mesh■ Loading objects in the OBJ file format■ Interaction° pan, dolly, trackball■ Picking and selection■ Transformation hierarchies2/05/073Today’s topics■ Lines and planes■ Culling ° View frustum culling° Back-face culling° Occlusion culling° Hierarchical culling■ Clipping2/05/074What 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 model2/05/075Culling example■ Power plant model° 13 M triangles° 1.7 M triangles - gutted version show here with no internal pipes2/05/076Culling exampleFull model1.7 MtrisView frustum culling1.4 MtrisOcculsion culling89 Ktris2/05/077Lines and planes■ 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:ˆnd(0,0)xyxynx ny d 0x[n n d] y 0 l p 01+−=⎡⎤⎢⎥−=⇒⋅=⎢⎥⎢⎥⎣⎦pp′= M1ll−′=Ml ⋅p =0 ⋅nKnK2/05/078Lines and planesˆnd(0,0)lp 0⋅>lp 0⋅<l ⋅p =0 ⋅■ Lines (planes) partition 2D (3D)space:° positive and negative half spaces■ The union of negative half-spacesdefines a convex region2/05/079Testing objects for containment+++++−−−−−−−+++Outside Straddling Inside2/05/0710Conservative testingInsidelc r⋅<−rcIndeterminaterlcr−<⋅<rcrcOutsidelc r⋅>■ Use cheap, conservative bounds for trivial cases■ Can use more accurate, more expensive tests for ambiguous cases if needed2/05/0711View frustum culling■ Test objects against planes defining view frustum■ How do you compute them?■ Other planes can be computed similarly-1 11-1Ml[10 1]=−tc1 c3ll (mm)′==−Mcolumn 1- column 32/05/0712Hierachical 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/0713Back-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 visible2/05/0714Manifold■ 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/0715Face plane test■ Compute the plane for the face:■ Cull if eye point in the negative half-space 10 20n(v v)(v v)=−×−K  0v1v2v0dnv=⋅K2/05/0716Winding order test■ Back-faces have a clockwise vertex ordering when viewed from outside.■ Typically used by graphics hardware during triangle setup2/05/0717Back-face culling in OpenGLif (cull):glFrontFace(GL_CCW) # define winding orderglEnable(GL_CULL_FACE) # enable CullingglCullFace(GL_BACK) # which faces to cullelse:glDisable(GL_CULL_FACE)■ Can cull front faces or back faces■ Back-face can sometimes double performancefront-face culling2/05/0718Occlusion culling with occlusion queries■ Render objects visible in previous frame (occlusion representation)2/05/0719Occlusion 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/0720Occlusion culling with occlusion queries■ Re-enable color writes■ Render newly visible objects2/05/0721Clipping 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′l010pp t(pp)′=+ − lp 0′⋅=010010l(p t(p p)) 0(l p )tl(p p)⋅+ − =−⋅=⋅−2/05/0722Clipping 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 enter2/05/0723Clipping against a convex region■ Sutherland-Hodgman° Just clip against one edge ata time2/05/0724Outcodes■ The Cohen-Sutherland clipping algorithm uses outcodes to quickly determine the visibility of a primitive. ■ An outcode is created for each vertex. It is a bit vector with a bit set for each plane the vertex is outside of■ Works for any convex region2/05/0725Outcode for lines(outcode1 OR outcode2) == 0line segment is inside(outcode1 AND outcode2) != 0line segment is totally outside(outcode1 AND outcode2) == 0line segment potentially crosses clip regionat planes indicated by set bits in (outcode1 XOR outcode2) ■ Some line segments that are classified as potentially crossing the clip region actually don’t.2/05/0726Outcodes for trianglesCombine outcodes from vertices(outcode1 OR outcode2 OR outcode3) == 0triangle is inside(outcode1 AND outcode2 AND outcode3) != 0triangle is