More info

Tuesday, 4 March 2014

Computer Graphics Notes - Lab 16 - FLOOD FILL ALGORITHM

Sometimes we want to fill in (or recolor) an area that is not defined within single color boundary. We can paint such areas by replacing a specified interior color instead of searching for boundary color value. This approach is called a flood-fill algorithm. We start from a specified interior point (x, y) and reassign all pixel values that are currently set to a given interior color with the desired fill color. If the area we want to paint has more than one interior color, we can first reassign pixel values so that all interior points have the same color. Using either a 4-connected or 8-connected approach, we then step through pixel positions until all interior points have been repainted.

Recursive 4-way flood fill
void floodFill4 (int x, int y, int newColor, int oldColor)
{
if (getpixel (x, y) = = oldColor)
{
setColor (newColor);
setpixel(x, y);
floodFill4(x + 1, y, newColor, oldColor);
floodFill4(x - 1, y, newColor, oldColor);
floodFill4(x, y + 1, newColor, oldColor);
floodFill4(x, y - 1, newColor, oldColor);
}
}
CHARACTER GENERATION
Letters, numbers and other characters can be displayed in a variety of sizes and styles. The overall design style for a set (or family) of characters is called a typeface or font. Today, there are hundreds of typefaces available for computer applications. Examples of a few common typefaces are courier, Palatine etc.

Typefaces can be divided into two broad groups: serif and sans serif. Serif type has small lines or accents at the ends of the main character strokes, while type does not have accents. Serif type is generally more readable; i.e., it is easier to read in longer blocks of text. On the other hand, the individual characters in sans-serif type are easier to recognize. For this reason, sans-serif type is said to be more legible. Since sans-serif characters can be quickly recognized, this typeface is good for labeling and short headings.

Two different representations are used for storing computer fonts. A simple method for representing the character shapes in a particular typeface is to use rectangular grid patterns. The set of characters are then referred to as bitmap font. Another, more flexible, scheme is to describe character shapes using straight line and curve. In this case, the set of characters is called an outline font. The figure below illustrates the two methods for character presentation. When the pattern in fig a) is copied to an area of the frame buffer, the 1 bit designate which pixel positions are to be displayed on the monitor. To display the character shape in fig b) the interior of the character outline must be filled using the scan-line fill procedure.
1
1
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0


Bitmap fonts are the simplest to define and display but require more space because each variation (size and format) must be stored in a font cache. It is possible to generate different sizes and other variations, such as bold and italic, from one set, but this usually does not produce good results.

In contrast to bitmap fonts, outline fonts require less storage since each variation does not require a distinct font cache. We can produce boldface, italic or different sizes by manipulating the curve definitions for the character outlines. It takes more time to process the outline font than bitmap font.

ATTRIBUTES OF OUTPUT PRIMITIVES
Line Attributes
Basic attributes of a straight-line segment are its type, its width, and its color.

Line Type

Possible selections for the line-type attributes include solid lines, dashed lines and dotted lines. We modify a line-drawing algorithm to generate such lines by setting length and spacing of displayed solid sections along the line path. A dashed line could be displayed by generating an interdash spacing that is equal to the length of the solid sections. Both the length of the dashes and interdash spacing are often specified as user options. A dotted line can be displayed by generating very short dashes with the spacing equal to or greater than the dash size.

Line width

For raster implementations, a standard-width line is generated with single pixels at each sample position, as in the Bresenham's algorithm. Thicker lines are displayed as positive integer multiples of the standard line by plotting additional pixels along adjacent parallel line paths. If a line has slope magnitude less than or equal to 1.0, we can modify a line-drawing routine to display thick lines by plotting a vertical span of pixels at each x position along the line. The number of pixels to be displayed in each column is set equal to the integer value of the line width.

In the above figure we display a double-width line by generating a parallel line above the original line path. At each x sampling position, we calculate the corresponding y coordinate and plot pixels at screen coordinates (x, y) and (x, y + 1). We could display lines with a width of 3 or greater by alternately plotting pixels above and below the single-width line path.

With a line slope greater than 1.0 in magnitude, we can display thick lines using horizontal spans, alternately picking up pixels to the right and left of the line path.
This scheme is demonstrated in the above figure where a line segment with a width of 4 is plotted using multiple pixels across each scan line.

Another problem with implementing width options using horizontal or vertical pixel spans is that the method produces lines whose ends are horizontal or vertical regardless of the slope of the line. This effect is more noticeable with very thick lines. We can adjust the shape of the line ends to give them a better appearance by adding line caps.

One kind of line cap is the butt cap, which has square ends that are perpendicular to the line path. If the specified line has slope m, the square ends of the thick line have slope -l/m. Each of the component parallel lines is then displayed between the two perpendicular lines at each end of the specified line path.

Another line cap is the round cap obtained by adding a filled semicircle to each butt cap. The circular arcs are centered at the middle of the thick line and have a diameter equal to the line thickness.
A third type of line cap is the projecting square cap. Here, we simply extend the line and add butt caps that are positioned one-half of the line width beyond the specified endpoints.
Generating thick polylines requires some additional considerations. In general, the methods we-, have considered for displaying a single line segment will not produce a smoothly connected series of line segments. Displaying thick polylines using horizontal and vertical pixel spans, for example, leaves pixel gaps at the boundaries between line segments with different slopes where there is a shift from horizontal pixel spans to vertical spans. We can generate thick polylines that are smoothly joined at the cost of additional processing at the segment endpoints.
The figure above shows three possible methods for smoothly joining two line segments. A miter join is accomplished by extending the outer boundaries of each of the two line segments until they meet. A round join is produced by capping the connection between the two segments with a circular boundary whose diameter is equal to the line width. And displaying the line segments with butt caps and filling in the triangular gap where the segments meet generates a bevel join. If the angle between two connected line segments is very small, a miter join can generate a long spike that distorts the appearance of the polyline. A graphics package can avoid this effect by switching from a miter join to a bevel join when, for example, the angle between any two consecutive segments is small.




No comments:

Post a Comment