Jiao, Jefferson S. and Mananquil, Jeirsy Joice F.
An Enhancement of scanline algorithm applied in Lord of the Shades Game - Undergraduate Thesis: (BSCS major in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2010.
ABSTRACT: The scanline “span” is a group of adjacent pixels on a scanline that are considered to be interior to the polygon. Basic algorithm: Assume scan line start from the left and is outside the polygon. When intersect an edge of polygon, start to color each pixels. The main algorithm idea which is scanning the horizontal line over the input segments from top-to-bottom (increasing y) and performing scan while maintaining a left-to-right sequence of the segments that intersect the scan-line “for each” y-intercept value. Upon processing of polygon, active edges are sorted according to their minimum/maximum points and processed in filling from left to right. When the current scan line reaches the lowest scan point, flood filling is finished. This research study is purposely done to provide solution to the problems. This study ought to answer the following: 1. Inconsistent validation of pixel to be filled up. 2. The algorithm still connects a polygon even when there is an obstruction in the connection. 3. Slow manipulation of flood filling, since it is incrementational. The following are the objectives that the proponents decided to propose: 1. To be able to have an efficient validation of filling up polygons. 2. To connect edges of different polygon to prevent unnecessary process of the algorithm and coloring intersecting polygon. 3. To be able to enhance the speed of manipulating flood filling. To come up with an extensive study, there are a lot of process requirements gathering, simulation of existing and enhance system and analysis of results. The general method used to conduct the study is Waterfall Method which one proceeds from one phase to the next in a purely sequential manner. This type of method is a sequential software development process, in which progress is seen as flowing steadily downwards. Throughout the study it is clearly said how important it is, a step-by-step input was presented. It is clearly seen in the screenshots of the system how the problem is existed in the algorithm and how the proponents give the solution for it. Comparing figures from presentation of problems from presentation of objective it will greatly state how this problem will affect the output for the application. From the polygons that have an obstruction, it will influence the flow of the game and especially the users. On the other hand, flood filling should be in a fastest form to attract more players of the game. For the first objective, the proponents found out, filling up the polygon with stiff edges, is hard for the algorithm to validate which part of the shape will be filled up, but by the use of the existing system the proponents found a solution. Through the use of existing application the user can see that the algorithm consider even the exterior pixel of the polygon, for this drawback the proponent considered only the interior pixels of the polygon to be filled up. For the second objective, which is to prevent unnecessary process of intersecting polygon, the proponent establish a solution to be able for the algorithm to work better. For the last objective, which is the slow process of food filling, given the existing algorithm it works pixel basis, for the enhanced application the proponents cope up with the solution to flood fill the given polygon using line by line basis. Further enhancement in this thesis is needed. The algorithm is very robust. It turns out that the only difficulty with polygons that have large amounts of edges, like circles and ellipses. Filling in such a polygon would be very costly. So enhancement with this problems makes the algorithm functional. Gradient fill with polygons may be a good production especially using a scanline algorithm, it can be a best feature for the algorithm.
academic writing
QA76.75 J53 2010
An Enhancement of scanline algorithm applied in Lord of the Shades Game - Undergraduate Thesis: (BSCS major in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2010.
ABSTRACT: The scanline “span” is a group of adjacent pixels on a scanline that are considered to be interior to the polygon. Basic algorithm: Assume scan line start from the left and is outside the polygon. When intersect an edge of polygon, start to color each pixels. The main algorithm idea which is scanning the horizontal line over the input segments from top-to-bottom (increasing y) and performing scan while maintaining a left-to-right sequence of the segments that intersect the scan-line “for each” y-intercept value. Upon processing of polygon, active edges are sorted according to their minimum/maximum points and processed in filling from left to right. When the current scan line reaches the lowest scan point, flood filling is finished. This research study is purposely done to provide solution to the problems. This study ought to answer the following: 1. Inconsistent validation of pixel to be filled up. 2. The algorithm still connects a polygon even when there is an obstruction in the connection. 3. Slow manipulation of flood filling, since it is incrementational. The following are the objectives that the proponents decided to propose: 1. To be able to have an efficient validation of filling up polygons. 2. To connect edges of different polygon to prevent unnecessary process of the algorithm and coloring intersecting polygon. 3. To be able to enhance the speed of manipulating flood filling. To come up with an extensive study, there are a lot of process requirements gathering, simulation of existing and enhance system and analysis of results. The general method used to conduct the study is Waterfall Method which one proceeds from one phase to the next in a purely sequential manner. This type of method is a sequential software development process, in which progress is seen as flowing steadily downwards. Throughout the study it is clearly said how important it is, a step-by-step input was presented. It is clearly seen in the screenshots of the system how the problem is existed in the algorithm and how the proponents give the solution for it. Comparing figures from presentation of problems from presentation of objective it will greatly state how this problem will affect the output for the application. From the polygons that have an obstruction, it will influence the flow of the game and especially the users. On the other hand, flood filling should be in a fastest form to attract more players of the game. For the first objective, the proponents found out, filling up the polygon with stiff edges, is hard for the algorithm to validate which part of the shape will be filled up, but by the use of the existing system the proponents found a solution. Through the use of existing application the user can see that the algorithm consider even the exterior pixel of the polygon, for this drawback the proponent considered only the interior pixels of the polygon to be filled up. For the second objective, which is to prevent unnecessary process of intersecting polygon, the proponent establish a solution to be able for the algorithm to work better. For the last objective, which is the slow process of food filling, given the existing algorithm it works pixel basis, for the enhanced application the proponents cope up with the solution to flood fill the given polygon using line by line basis. Further enhancement in this thesis is needed. The algorithm is very robust. It turns out that the only difficulty with polygons that have large amounts of edges, like circles and ellipses. Filling in such a polygon would be very costly. So enhancement with this problems makes the algorithm functional. Gradient fill with polygons may be a good production especially using a scanline algorithm, it can be a best feature for the algorithm.
academic writing
QA76.75 J53 2010