ClippingViewing Pipeline RevisitedWhy do clippingWhat is clipping, two viewsPowerPoint PresentationSlide 6Slide 7Cohen-Sutherland Algorithm (Outcode clipping)Slide 9Slide 10The Maybe caseThe Maybe CaseOne Plane At a Time Clipping (a.k.a. Sutherland-Hodgeman Clipping)Slide 14Slide 15Slide 16Slide 17Slide 18Sutherland-HodgmanInterpolating ParametersSlide 21Naïve 3D Euclidean Space ClippingDifficulty with Euclidean Space ClippingSlide 24Slide 254D ClippingSlide 27Slide 28More on Perspective TransformMore on perspective transformsSlide 31More on Homogeneous CoordinatesTransforming NormalsSlide 34Slide 35Slide 36Right-Handed Or Left-HandedHow about the viewing pipeline?ClippingJian Huang, CS594This set of slides reference slides devised at Ohio State and MIT.January 14, 2019 2Viewing Pipeline Revisited–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 coordinatesObject SpaceWorld SpaceEye SpaceClipping SpaceCanonical view volume Screen SpaceJanuary 14, 2019 3Why do clippingClipping is a visibility preprocess. In real-world scenes clipping can remove a substantial percentage of the environment from consideration.Clipping offers an important optimizationJanuary 14, 2019 4What is clipping, two viewsClipping 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 primitivesClipping is to subdivide geometric primitives. Several other potential applications.–Binning geometric primitives into spatial data structures–computing analytical shadows.January 14, 2019 5Point Clipping(x, y) is inside iff XminXmaxYminYmaxXminx Xmax Yminy Ymax ANDJanuary 14, 2019 6Line Clipping - Half Plane TestsModify endpoints to lie in rectangle“Interior” of rectangle?Answer: intersection of 4 half-planes3D ? (intersection of 6 half-planes)y < ymax y > yminx > xmin x < xmax=interiorxmin xmaxyminymaxJanuary 14, 2019 7Line ClippingIs end-point inside a clip region? - half-plane testIf outside, calculate intersection betwee line and the clipping rectangle and make this the new end point•Both endpoints inside: trivial accept•One inside: find intersection and clip•Both outside: either clip or reject (tricky case)January 14, 2019 8Cohen-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 9Cohen-Sutherland Algorithm (Outcode clipping)if (outcode1 == '0000' and outcode2 == ‘0000’) then line segment is insideelse if ((outcode1 AND outcode2) == 0000) then line segment potentially crosses clip region else line is entirely outside of clip region endifendifJanuary 14, 2019 10The 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 edgeReplace outside endpoint with intersection pointRepeat outcode test until trivial accept or rejectJanuary 14, 2019 11The Maybe caseJanuary 14, 2019 12The Maybe CaseJanuary 14, 2019 13One 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 14Sutherland-HodgmanPolygon Clipping AlgorithmSubproblem:clip a polygon (input: vertex list) against a single clip edgesoutput 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/polyhedronUsed in viewing transformsJanuary 14, 2019 15Polygon Clipping At WorkJanuary 14, 2019 16Sutherland-HodgmanSHclippedge(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 ;;;;;;;;; -- case 1 addlist(d, olist); ;;;;olen := olen + 1; else -- case 4 n := intersect(s, d, edge); addlist(n, olist); addlist(d, olist); olen = olen + 2; else if (inside(s, edge) then -- case 2 n := intersect(s, d, edge); addlist(n, olist); olen ++; s = d;end_for;January 14, 2019 17Sutherland-HodgmanSHclip(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 18With PicturesJanuary 14, 2019 19Sutherland-HodgmanAdvantages:–Elegant (few special cases)–Robust (handles boundary and edge conditions well)–Well suited to hardware–Canonical clipping makes fixed-point–implementations manageableDisadvantages:–Only works for convex clipping volumes–Often generates more than the minimum number of triangles needed–Requires a divide per edgeJanuary 14, 2019 20Interpolating ParametersJanuary 14, 2019 213D Clipping (Planes) xyzimage planenearfarRed Polygon – ClipTransform into 4D Clipping space (canonical viewing volume) Homogenous co-ordinatesJanuary 14, 2019 22Naïve 3D Euclidean Space ClippingAfter perspective projection, Euclidean space is not linear!!January 14, 2019 23Difficulty with Euclidean
View Full Document
Unlocking...