Polygon is an ordered list of vertices . For filling polygons with particular colors,we need to determine the pixels falling on the border of the polygon and those which fall inside the polygon.
Scan line algorithm works by intersecting scanline with the polygon edges and filling the polygon between pair of intersections.
Main Components:
>Edge Bucket
>Edge Table
>Active List
These components will contain an edge's information, hold all the edges that compose the figure and maintain the current edge being used to fill in the polygon, respectively.
Edge Buckets:
The edge bucket is a structure that holds information about the polygon's edges. The edge bucket looks different depending on the implementation of the algorithm.
+
ymax: Maximun y postion of the edge
ymin: Minimum Y position of the edge
x:the current position along the scan line
sign: sign of edge's slope
dx: difference between the x values of the vertices
dy: difference between the y values of the vertices
sum:used to indicate when moving to the next x coordinate
Edge Table:
The edge table is a list that contains all the edges that makes the polygon.
Active List:
Contains all the edges that are being processed/used to fill the polygon.
Algorithm:
step 1: Find out the ymin and ymax
step 2: Scanline intersects with each edge of the polygon from ymin to ymax.
Name each intersection point of the polygon.
e.g: p0, p1, p2 etc
step 3: Sort the intersection point in the increasing order of x coordinate
i.e (p0,p1) , (p1,p2), (p2,p3) etc
step 4: Fill all those pair of coordinates that are inside polygons and ignore their altervatives
Ohayō gozaimasu ^_^
ReplyDelete