CS 445 / 645: Introductory Computer GraphicsReview: Polygon RasterizationReview: Active Edge TableSlide 4Slide 5Review: ClippingReview: Parametric EquationsCyrus-Beck AlgorithmSlide 9Slide 10Slide 11Slide 12ComparisonClipping PolygonsWhy Is Clipping Hard?Slide 16Slide 17Sutherland-Hodgeman ClippingSlide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Sutherland-Hodgeman Clipping: The AlgorithmSlide 28Slide 29Slide 30Slide 31Point-to-Plane testFinding Line-Plane IntersectionsSlide 34Line-Plane IntersectionsCS 445 / 645: Introductory Computer GraphicsClipping Lines and PolygonsReview: Polygon RasterizationA BD CFEHGFor scanline, determine all intersections of polygon edges with scanlineSort edge intersections in least to greatest orderUse parity count to determine when pixels are drawnHorizontal lines do not contribute to parity countYmin endpoints do contribute to parity countYmax endpoints do not contribute to parity countBottom edge drawn because A is min of AH. AB does not contributeNot drawn because H is max of AHAnd HG does not contributeNot drawn because D is min of EDAnd increments counter to 2.DC doesn’t contributeReview: Active Edge TableTwo data structures–Edge TableArray of pointers, A, of length (screen height)A[i] points to linked list of all edges with ymin = IEdges in linked list are ordered according to the x coordinate of the ymin vertexEdge in list is represented by ymax, initial x, slope (1/m)Review: Active Edge Table–Linked list of all edges that intersect current scanline–List must always be sorted on x intersection with scanline–First add all edges from edge table with smallest y–Use parity test to fill pixels on scanline–Increment scanline–Add all edges from edge table with ymin value = scanline–Remove all edges from AET with ymax = scanline–Update x intersection value of all edges in AET and re-sortReview: Active Edge TableReview: ClippingCohen-Sutherland–Use opcodes to quickly eliminate/include lines–Must compute viewport clipping of remaining linesIntroduced parametric equations of lines to perform edge/viewport intersection testsTruth in advertising, Cohen-Sutherland doesn’t use parametric equations of lines–Viewport intersection code:(x1, y1), (x2, y2) intersect with vertical edge at xrightyintersect = y1 + m(xright – x1), m=(y2-y1)/(x2-x1)(x1, y1), (x2, y2) intersect with horizontal edge at ybottomxintersect = x1 + (ybottom – y1)/m, m=(y2-y1)/(x2-x1)Review: Parametric EquationsFaster line clippers use parametric equationsLine 0:–x0 = x00 + (x01 - x00) t0–y0 = y00 + (y01 - y00) t0Viewport Edge L:–xL = xL0 + (xL1 - xL0) tL–yL = yL0 + (yL1 - yL0) tLx00 + (x01 - x00) t0 = xL0 + (xL1 - xL0) tLy00 + (y01 - y00) t0 = yL0 + (yL1 - yL0) tL–Solve for t0 and/or tLCyrus-Beck AlgorithmUse parametric equations of linesOptimizeWe saw that this could be expensive…Start with parametric equation of line:–P(t) = P0 + (P1 - P0) tAnd a point and normal for each edge–PL, NLCyrus-Beck AlgorithmNL [P(t) - PL] = 0Substitute line equation for P(t)Solve for t–t = NL [P0 - PL] / -NL [P1 - P0]PLNLP(t)InsideP0P1Cyrus-Beck AlgorithmCompute t for line intersection with all four edgesDiscard all (t < 0) and (t > 1)Classify each remaining intersection as–Potentially Entering (PE)–Potentially Leaving (PL)NL [P1 - P0] > 0 implies PLNL [P1 - P0] < 0 implies PE–Note that we computed this term in when computing tCompute PE with largest tCompute PL with smallest tClip to these two pointsCyrus-Beck AlgorithmPEPLP1PLPEP0Cyrus-Beck AlgorithmBecause of horizontal and vertical clip lines:–Many computations reduceNormals: (-1, 0), (1, 0), (0, -1), (0, 1)Pick constant points on edgessolution for t:–-(x0 - xleft) / (x1 - x0)–(x0 - xright) / -(x1 - x0)–-(y0 - ybottom) / (y1 - y0)–(y0 - ytop) / -(y1 - y0)ComparisonCohen-Sutherland–Repeated clipping is expensive–Best used when trivial acceptance and rejection is possible for most linesCyrus-Beck–Computation of t-intersections is cheap–Computation of (x,y) clip points is only done once–Algorithm doesn’t consider trivial accepts/rejects–Best when many lines must be clippedLiang-Barsky: Optimized Cyrus-BeckNicholl et al.: Fastest, but doesn’t do 3DClipping PolygonsClipping polygons is more complex than clipping the individual lines–Input: polygon–Output: original polygon, new polygon, or nothingWhen can we trivially accept/reject a polygon as opposed to the line segments that make up the polygon?What happens to a triangle during clipping?Possible outcomes:triangletriangleWhy Is Clipping Hard?trianglequadtriangle5-gonHow many sides can a clipped triangle have?A really tough case: Why Is Clipping Hard?A really tough case: Why Is Clipping Hard?concave polygonmultiple polygonsSutherland-Hodgeman ClippingBasic idea:–Consider each edge of the viewport individually–Clip the polygon against the edge equationSutherland-Hodgeman ClippingBasic idea:–Consider each edge of the viewport individually–Clip the polygon against the edge equation–After doing all planes, the polygon is fully clippedSutherland-Hodgeman ClippingBasic idea:–Consider each edge of the viewport individually–Clip the polygon against the edge equation–After doing all planes, the polygon is fully clippedSutherland-Hodgeman ClippingBasic idea:–Consider each edge of the viewport individually–Clip the polygon against the edge equation–After doing all planes, the polygon is fully clippedSutherland-Hodgeman ClippingBasic idea:–Consider each edge of the viewport individually–Clip the polygon against the edge equation–After doing all planes, the polygon is fully clippedSutherland-Hodgeman ClippingBasic idea:–Consider each edge of the viewport individually–Clip the polygon against the edge equation–After doing all planes, the polygon is fully clippedSutherland-Hodgeman ClippingBasic idea:–Consider each edge of the viewport individually–Clip the polygon against the edge equation–After doing all planes, the polygon is fully clippedSutherland-Hodgeman ClippingBasic idea:–Consider each edge of the viewport individually–Clip the polygon against the edge equation–After doing all planes, the polygon is fully clippedSutherland-Hodgeman ClippingBasic idea:–Consider each edge of the
View Full Document
Unlocking...