Skip to end of metadata
Go to start of metadata

Abstract

The purpose of this project was to implement a scanline fill algorithm for polygons, and to use this algorithm to generate images. The purpose of this algorithm is to systematically fill polygon figures in a fast and efficient way.In order to quickly draw polygons, we created two new objects, polyline and polygon. The polygon object contains a function that allows users to draw a filled polygon using the scan fill algorithm.Once our code was updated and our algorithm was functional, we used it to draw images containing filled shapes.

Task

The goal of this project was to implement a scanline fill algorithm in our graphics program.In order to use this algorithm efficiently, we also defined polygon and polyline objects. These objects represent shapes in an image, and hold information on their number of vertices and their number of edges. After implementing these new objects and algorithms, our next task was to use them to draw images with filled shapes. The first image was the one coded for us on the assignment page, and then several others that we coded ourselves.

Description of how you completed the task

To complete this task, we first created the polygon and polyline objects. Then we wrote the scanline fill algorithm.

Polygon

The polyline object holds three fields: int zBuffer, which we defaulted to true; int numVertex, which is the number of vertices in the polygon and Point vertex, an array of vertices.
To draw the polyline object, the polyline is initialized using the function Polyline_init, which takes in the number of vertices and an array of points. Then, the function Polyline_drawFrame() is called, which takes in a Polyline p, the polygon to be drawn, Image src, the image on which to draw it, and Color c, the color of the polyline.

Scan Fill Algorithm

The scan fill algorithm is an efficient way of coloring in polygons. It doesn't use up as much memory as flood fill algorithms, and makes use of spatial locality to avoid pulling data from main memory; it pulls it from the cache instead.
The algorithm goes through each line in a polygon, and keeps track of the active edges of that line. An active edge is any polygon edge that is not an extremum or a horizontal edge. These two cases can be ignored, because they won't affect how the polygon is filled.

For the most part, we used the skeleton of the scan line fill algorithm provided to us. The main changes to the skeleton were filling in the empty code in the "fillScan" and "makeEdgeRec" functions. The "makeEdgeRec" algorithm takes in the upper and lower points of an edge, uses these to calculate the change in x per scan, and from this, the x intersect. The algorithm stores the maximum y value (clipping it if it is outside the range of the image). Algorithm decrements the max y value before storing it, which prevents counting edges twice where they intersect, and causes the algorithm to ignore horizontal lines and extremum which do not need to be filled.
The fillScan algorithm iterates through a scan line, using a for loop to color from the first edge until it reaches the second edge. At this point it stops, skips the space from the second edge to the third edge, then re-enters the for loop, coloring from the third edge to the forth edge. It continues this process for an arbitrary number of edges until the scanline is completed. The algorithm does not need to worry about extremum or horizontal lines being counted as edges, as these were omitted from the edge list in the makeEdgeRec function. The algorithm simply needs to color the space between every other edge it finds.

Summary of what we learned

Through coding this algorithm, we learned a very useful way to fill in polygons. We learned how graphics programs can make use of edges to define shapes in an image, and how to use those shapes to make our algorithms more efficient (in this case, our fill algorithm).

Pictures



Our beautiful, 3D, photorealistic house. (smile)


Our slightly on the lame side, and not so photo realistic rocket.




Transparency at its best. Stars in the background and the weird, exploding something, in the foreground. It's transparent!


We can also fill it with patterns and overlay another transparent layers! Almost (ALMOST!) like Photoshop (wink)


Wireframe version of the image. Without the central spots, this image will be used later.


Since the scanline operates on the borders saved in the memory, there is no need for outline.


Accelerated flood fill, follow for a long example.


A long flood fill. It takes almost 15000 executions of this recursive algorithm to fill the shape completely. You can see different possible paths that can be followed while filling in as the picture 'waves'.

Labels
  • No labels