ClippingOutlineRecap: Homogeneous CoordsRecap: Perspective ProjectionSlide 5Recap: Perspective Projection MatrixRecap: OpenGL’s Persp. Proj. MatrixProjection MatricesSlide 9Next Topic: ClippingSlide 11Why Clip?Slide 13Trivial AcceptsTrivial RejectsSlide 16Cohen-Sutherland Line ClippingSlide 18Slide 19Slide 20Slide 21Slide 22Clipping PolygonsWhy Is Clipping Hard?Slide 25Slide 26Slide 27Sutherland-Hodgman ClippingSlide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Point-to-Plane testPoint-to-Plane TestFinding Line-Plane IntersectionsSlide 45Line-Plane IntersectionsSlide 473-D ClippingSlide 49Clipping Under PerspectiveSlide 51Slide 52Perspective ProjectionSlide 54Slide 55Clipping Homogeneous CoordsSlide 57Slide 58Clipping: The Real WorldClippingAaron BloomfieldCS 445: Introduction to GraphicsFall 2006(Slide set originally by David Luebke)2OutlineReviewClipping BasicsCohen-Sutherland Line ClippingClipping PolygonsSutherland-Hodgman ClippingPerspective Clipping3Recap: Homogeneous CoordsIntuitively:The w coordinate of a homogeneous point is typically 1Decreasing w makes the point “bigger”, meaning further from the originHomogeneous points with w = 0 are thus “points at infinity”, meaning infinitely far away in some direction. (What direction?)To help illustrate this, imagine subtracting two homogeneous points: the result is (as expected) a vector4Recap: Perspective ProjectionWhen we do 3-D graphics, we think of the screen as a 2-D window onto the 3-D world:How tall shouldthis bunny be?5Recap: Perspective ProjectionThe geometry of the situation:Desiredresult:P (x, y, z)XZViewplaned(0,0,0)x’ = ?' , ' ,d x x d y yx y z dz z d z z d� �= = = = =6Recap: Perspective Projection MatrixExample:Or, in 3-D coordinates:10100010000100001zyxddzzyxddzydzx,,7Recap: OpenGL’s Persp. Proj. MatrixOpenGL’s gluPerspective() command generates a slightly more complicated matrix:Can you figure out what this matrix does?2cotwhere0100200000000yfarnearnearfarfarnearnearfarfovfZZZZZZZΖfaspectf8Projection MatricesNow that we can express perspective foreshortening as a matrix, we can composite it onto our other matrices with the usual matrix multiplicationEnd result: can create a single matrix encapsulating modeling, viewing, and projection transformsThough you will recall that in practice OpenGL separates the modelview from projection matrix (why?)9OutlineReviewClipping BasicsCohen-Sutherland Line ClippingClipping PolygonsSutherland-Hodgman ClippingPerspective Clipping10Next Topic: ClippingWe’ve been assuming that all primitives (lines, triangles, polygons) lie entirely within the viewport In general, this assumption will not hold11ClippingAnalytically calculating the portions of primitives within the viewport12Why Clip?Bad idea to rasterize outside of framebuffer bounds Also, don’t waste time scan converting pixels outside window13ClippingThe naïve approach to clipping lines:for each line segment for each edge of viewport find intersection points pick “nearest” point if anything is left, draw itWhat do we mean by “nearest”?How can we optimize this?14Trivial Accepts Big optimization: trivial accept/rejectsHow can we quickly determine whether a line segment is entirely inside the viewport?A: test both endpoints. xminxmaxymaxymin15Trivial RejectsHow can we know a line is outside viewport?A: if both endpoints on wrong side of same edge, can trivially reject linexminxmaxymaxymin16OutlineReviewClipping BasicsCohen-Sutherland Line ClippingClipping PolygonsSutherland-Hodgman ClippingPerspective Clipping17Cohen-Sutherland Line ClippingDivide viewplane into regions defined by viewport edgesAssign each region a 4-bit outcode: 0000 0010000110010101 01001000 10100110xminxmaxymaxymin18Cohen-Sutherland Line ClippingTo what do we assign outcodes?How do we set the bits in the outcode?How do you suppose we use them?xminxmax0000 0010000110010101 01001000 10100110ymaxymin19Cohen-Sutherland Line ClippingSet bits with simple testsx > xmax y < ymin etc.Assign an outcode to each vertex of lineIf both outcodes = 0, trivial acceptbitwise AND vertex outcodes togetherIf result 0, trivial rejectAs those lines lie on one side of the boundary lines0000 0010000110010101 01001000 10100110ymaxymin20Cohen-Sutherland Line ClippingIf line cannot be trivially accepted or rejected, subdivide so that one or both segments can be discardedPick an edge that the line crosses (how?)Intersect line with edge (how?)Discard portion on wrong side of edge and assign outcode to new vertexApply trivial accept/reject tests; repeat if necessary21Outcode tests and line-edge intersects are quite fast (how fast?) But some lines require multiple iterations:Clip topClip leftClip bottomClip rightFundamentally more efficient algorithms:Cyrus-Beck uses parametric linesLiang-Barsky optimizes this for upright volumesCohen-Sutherland Line Clipping22OutlineReviewClipping BasicsCohen-Sutherland Line ClippingClipping PolygonsSutherland-Hodgman ClippingPerspective Clipping23Clipping PolygonsWe know how to clip a single line segmentHow about a polygon in 2D?How about in 3D?Clipping polygons is more complex than clipping the individual linesInput: polygonOutput: polygon, or nothingWhen can we trivially accept/reject a polygon as opposed to the line segments that make up the polygon?24What happens to a triangle during clipping?Possible outcomes:TriangletriangleWhy Is Clipping Hard?TrianglequadTriangle5-gonHow many sides can a clipped triangle have?25A really tough case: Why Is Clipping Hard?26A really tough case: Why Is Clipping Hard?concave polygonmultiple polygons27OutlineReviewClipping BasicsCohen-Sutherland Line ClippingClipping PolygonsSutherland-Hodgman
View Full Document
Unlocking...