Polygon Rasterization Jian Huang CS594 Fall 2001 This set of slides reference slides used at Ohio State for instruction by Prof Han Wei Shen Scanline Rasterization Polygon scan conversion Intersect scanline with polygon edges and fill between pairs of intersections For y ymin to ymax 1 intersect scanline y with each edge 2 sort interesections by increasing x p0 p1 p2 p3 3 fill pairwise p0 p1 p2 p3 Scanline Rasterization Special Handling Make sure we only fill the interior pixels Define interior For a given pair of intersection points Xi Y Xj Y Fill ceiling Xi to floor Xj important when we have polygons adjacent to each other Intersection has an integer X coordinate if Xi is integer we define it to be interior if Xj is integer we define it to be exterior so don t fill Scanline Rasterization Special Handling Intersection is an edge end point say p0 p1 p2 p0 p1 p1 p2 so we can still fill pairwise In fact if we compute the intersection of the scanline with edge e1 and e2 separately we will get the intersection point p1 twice Keep both of the p1 Scanline Rasterization Special Handling But what about this case still p0 p1 p1 p2 Rule Rule If the intersection is the ymin of the edge s endpoint count it Otherwise don t Don t count p1 for e2 Performance Improvement The goal is to compute the intersections more efficiently Brute force intersect all the edges with each scanline find the ymin and ymax of each edge and intersect the edge only when it crosses the scanline only calculate the intersection of the edge with the first scan line it intersects calculate dx dy for each additional scanline calculate the new intersection as x x dx dy Data Structure Edge table all edges sorted by their ymin coordinates keep a separate bucket for each scanline within each bucket edges are sorted by increasing x of the ymin endpoint Edge Table Active Edge Table AET A list of edges active for current scanline sorted in increasing x y 9 y 8 Polygon Scan conversion Algorithm Construct the Edge Table ET Active Edge Table AET null for y Ymin to Ymax Merge sort ET y into AET by x value Fill between pairs of x in AET for each edge in AET if edge ymax y remove edge from AET else edge x edge x dx dy sort AET by x value end scan fill
View Full Document
Unlocking...