CSCE 441 Computer Graphics: Clipping Polygons Jinxiang ChaiReminderReview: Clipping PointsReview: Clipping LinesSlide 5Review ClippingClipping PolygonsSlide 8Why Is Polygon Clipping Hard?Slide 10Slide 11How Many Sides?Why Is Clipping Hard?Slide 14OutlineAny idea?Slide 17Sutherland-Hodgman ClippingSlide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Sutherland-Hodgman AlgorithmSlide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Weiler-Atherton AlgorithmSlide 82Slide 83Slide 84Slide 85Slide 86Slide 87Slide 88Slide 89Slide 90Slide 91Slide 92Slide 93Slide 94Slide 95Slide 96Slide 97Slide 98Slide 99Slide 100Slide 101Slide 102Slide 103Slide 104Slide 105Slide 106Slide 107Slide 108Slide 109Slide 110Slide 111Slide 112Slide 113Slide 114Slide 115Slide 116Slide 117Next Lecture1CSCE 441 Computer Graphics:Clipping PolygonsJinxiang Chai2ReminderRequired readings: HB 6-5 to 6-7 Homework#1 deadline is passedHomework #2 will be posted tonight, due by 9/293Review: Clipping PointsGiven a point (x, y) and clipping window (xmin, ymin), (xmax, ymax), determine if the point should be drawn(xmin,ymin)(xmax,ymax)(x,y)xmin=<x<=xmax?ymin=<y<=ymax?4Review: Clipping Lines1P2P3P4P5P6P7P8P9P10P5Review: Clipping Lines5P6ˆP7P8P9ˆP10ˆP6Review ClippingSimple line clipping algorithm - compute intersection points - clip the line segment between the outside point and intersection pointCohen-Sutherland - region coding (9 regions, 4bits) - best used when trivial acceptance and rejection is possible for most linesLiang-Barsky - computation of t-intersections is cheap (only one division) - computation of (x,y) clip points is only done once - algorithm doesn’t consider trivial accepts/rejects - best when many lines must be clipped7Clipping PolygonsClipping polygons is more complex than clipping the individual lines- Input: polygon8Clipping PolygonsClipping polygons is more complex than clipping the individual lines- Input: polygon- Output: original polygon, new polygon, or nothing9Why Is Polygon Clipping Hard?What happens to a triangle during clipping? - possible outcomes:triangle->triangle triangle->quad triangle->5-gon10Why Is Polygon Clipping Hard?What happens to a triangle during clipping? - possible outcomes: triangle, quad, or else?11Why Is Polygon Clipping Hard?What happens to a triangle during clipping? - possible outcomes:triangle->triangle triangle->quad triangle->5-gonHow many sides a clipped triangle might have?How many sides a clipped triangle might have?12How Many Sides?Seven13Why Is Clipping Hard?A really tough caseConcave polygon -> Multiple polygons14Why Is Clipping Hard?A really tough case15OutlineSutherland-Hodgman Clipping - convex polygonsWeiler-Atherton Algorithm - general polygonsRequired readings - HB 6-816Any idea?Clipping polygon edges?17Any idea?Clipping polygon edges?Unconnected set of lines!18Sutherland-Hodgman ClippingBasic idea: - consider each edge of the view window individually - clip the polygon against the view window edge’s equation19Sutherland-Hodgman ClippingBasic idea: - consider each edge of the view window individually - clip the polygon against the view window edge’s equation20Sutherland-Hodgman ClippingBasic idea: - consider each edge of the view window individually - clip the polygon against the view window edge’s equation21Sutherland-Hodgman ClippingBasic idea: - consider each edge of the view window individually - clip the polygon against the view window edge’s equation22Sutherland-Hodgman ClippingBasic idea: - consider each edge of the view window individually - clip the polygon against the view window edge’s equation23Sutherland-Hodgman ClippingBasic idea: - consider each edge of the view window individually - clip the polygon against the view window edge’s equation24Sutherland-Hodgman ClippingBasic idea: - consider each edge of the view window individually - clip the polygon against the view window edge’s equation25Sutherland-Hodgman ClippingBasic idea: - consider each edge of the view window individually - clip the polygon against the view window edge’s equation26Sutherland-Hodgman ClippingBasic idea: - consider each edge of the view window individually - clip the polygon against the view window edge’s equation27Sutherland-Hodgman ClippingBasic idea: - consider each edge of the view window individually - clip the polygon against the view window edge’s equation - after doing all edges, the polygon is fully clipped28Sutherland-Hodgman ClippingJava applet: click here.29Sutherland-Hodgman ClippingInput/output for algorithm: - input: list of polygon vertices in order {abcdef} afedcb30Sutherland-Hodgman ClippingInput/output for algorithm: - input: list of polygon vertices in order - output: list of clipped polygon vertices consisting of old vertices (maybe) and new vertices (maybe)31Sutherland-Hodgman ClippingInput/output for algorithm: - input: list of polygon vertices in order - output: list of clipped polygon vertices consisting of old vertices (maybe) and new vertices (maybe) - exactly what expect from the clipping operation against each edge!32Sutherland-Hodgman ClippingBasic routine: - Go around polygon one vertex at a time - Current vertex has position E - Previous vertex had position S, and it has been added to the output if appropriateafecb {abcdef}d33Sutherland-Hodgman ClippingBasic routine: - Go around polygon one vertex at a time - Current vertex has position E - Previous vertex had position S, and it has been added to the output if appropriateafecb {abcdef}d34Sutherland-Hodgman ClippingEdge from S to E takes one of four cases:inside outsideSEE outputinside outsideSEno outputinside outsideSEI outputinside outsideSEI outputE output35Sutherland-Hodgman ClippingFour cases:S inside plane and E inside planeAdd E to outputNote: S has already been addedS inside plane and E outside planeFind intersection point IAdd I to outputS outside