Chapter Three: Output Primitives

Chapter Three
Part II
Output Primitives
CS 380 CH 3-P2 - 1
Outline
• In this chapter we will cover the following topics:

Part I:
– Line drawing algorithms.
– Circle generating algorithms
Part II:
– Setting frame-buffer values
– Pixel addressing and object geometry.
– Filled-Area primitives. (This section is from chapter four)
• This chapter will show the discrete nature for computer

graphics.
CS 380 CH 3-P2 - 2
Setting frame-buffer values
• After generating a line or circle using scan conversion, we

need to know where is the specified pixels are stored in the
frame buffer.
• Frame buffer is stored in memory as an addressable array

and stored row by row.
• Pixels are labeled from (0, 0) the lower left corner to (xmax,ymax)
the top right corner.
CS 380 CH 3-P2 - 3
Row by Row mapping
CS 380 CH 3-P2 - 4
Setting frame-buffer values (cont.)
• For a bilevel system (1 bit per pixel),the Frame-Buffer bit address

for pixel position (x, y) is calculated as:
1. addr(x, y) = addr (0,0) + y (xmax +1) + x
2. addr(x + 1, y) = addr(x, y) + 1
3. addr(x + 1, y + 1) = addr(x, y) + xmax + 2
CS 380 CH 3-P2 - 5
Setting frame-buffer values (cont.)
• Example:
Find the address of the pixel (6,5), where the address of (0,0) =500,
xmax=12, and ymax = 10.
addr(x, y) = addr (0,0) + y(xmax +1) + x

addr(6, 5) = 500 + 5(12 + 1) + 6 = 571
addr(7, 5) = addr(6, 5) + 1 = 572

addr(7, 6) = addr(6, 5) + xmax + 2 = 585
CS 380 CH 3-P2 - 6
Pixel addressing and object geometry
• When an object is scan converted into the frame buffer, the

input description is transformed to pixel coordinates.
• So, the displayed image may not correspond exactly with the
relative dimensions of the input object.
• To preserve the specified geometry of world objects, we need

to compensate for the mapping of mathematical input points
to finite pixel area, we use one of the two ways:
CS 380 CH 3-P2 - 7
Pixel addressing and object geometry (cont.)
1) Adjust the dimensions of displayed objects to account for the

amount of overlap of pixel areas with the object boundaries.
(i.e. a rectangle with 40 cm width, will be displayed in 40 pixel)
2) Map world coordinates onto screen positions between pixels, so that

we align objects boundaries with pixel boundaries instead of pixel
centers.
CS 380 CH 3-P2 - 8
Screen Grid Coordinates:
An alternative to addressing
display positions in terms of
pixel centers is to reference
screen coordinates with
respect to the grid of
horizontal and vertical pixel
boundary lines spaced one
unit a part.
CS 380 CH 3-P2 - 9
• Screen coordinate
position is then the pair of
integer values identifying
a grid intersection position
between two pixels.
• For example, the

mathematical line path for
a polyline with screen
endpoints (0, 0), (5, 2),
and (1,4) is shown
beside.
CS 380 CH 3-P2 - 10
• With the coordinate origin

at the lower left of the
screen, each pixel area
can be referenced by the
integer grid coordinates of
its lower left corner.
• The following figure

illustrates this convention
for an 8 by 8 section of a
raster, with a single
illuminated pixel at screen
coordinate position (4, 5).
CS 380 CH 3-P2 - 11
• In general, we identify the area occupied by a pixel with

screen coordinates ( x, y) as the unit square with diagonally
opposite corners at (x, y) and ( x + 1, y + 1 ).
• This pixel addressing scheme has several advantages:

1. It avoids half-integer pixel boundary
2. It facilitates precise object representations.
3. Simplifies the processing involved in many scan
conversion algorithms and in other raster procedures
CS 380 CH 3-P2 - 12
Notes:
1) The previous algorithms for drawing line, circle, …etc

are still valid when applied to input positions expressed
as screen grid coordinates.
2) The decision parameter Pk is a measure of screen

grid separation differences rather than separation
differences from pixel centers.
CS 380 CH 3-P2 - 13
 A circle of radius 5 and center position (10, 10), for instance, would
be displayed by the midpoint circle algorithm using screen grid
coordinate positions.
 But the plotted circle has a diameter of 11, To plot the circle with the
defined diameter of 10, we can modify the circle algorithm to
shorten each pixel scan line and each pixel column.
CS 380 CH 3-P2 - 14
CS 380 CH 3-P2 - 15
CS 380 CH 3-P2 - 16
Filled- Area Primitives
 A standard output primitive in general graphics packages is a solid-

color or patterned polygon area.
 There are two basic approaches to area filling on raster systems:
1. The scan-line approach

Determine the overlap intervals for scan lines that cross the area.
is typically used in general graphics packages to fill polygons,
circles, ellipses
2. Filling approaches
start from a given interior position and paint outward from this point
until we encounter the specified boundary conditions.
useful with more complex boundaries and in interactive painting
systems.
CS 380 CH 3-P2 - 17
Filled- Area Primitives (cont.)
Scan-Line Fill Algorithm:
 For each scan line crossing a polygon, the area-fill

algorithm locates the intersection points of the scan line
with the polygon edges.
 These intersection points are then sorted from left to

right, and the corresponding frame-buffer positions
between each intersection pair are set to the specified fill
color.
CS 380 CH 3-P2 - 18
CS 380 CH 3-P2 - 19
 Calculations performed in scan-conversion and other

graphics algorithms typically take advantage of various
coherence properties of a scene that is to be displayed.
 Coherence is simply that the properties of one part of a

scene are related in some way to other parts of the
scene so that the relationship can be used to reduce
processing.
 Coherence methods often involve incremental

calculations applied along a single scan line or between
successive scan lines.
CS 380 CH 3-P2 - 20
Inside-Outside Tests
 Area-filling algorithms and other graphics processes

often need to identify interior regions of objects.
 To identify interior regions of an object graphics

packages normally use either:
1. Odd-Even rule
2. Nonzero winding number rule
CS 380 CH 3-P2 - 21
Odd-Even rule (Odd Parity Rule, Even-Odd Rule):
1. draw a line from any position P to a distant point outside

the coordinate extents of the object and counting the
number of edge crossings along the line.
2. If the number of polygon edges crossed by this line is

odd then
P is an interior point.
Else
P is an exterior point
CS 380 CH 3-P2 - 22
Nonzero Winding Number Rule :
 Counts the number of times the polygon edges wind

around a particular point in the counterclockwise
direction. This count is called the winding number, and
the interior points of a two-dimensional object are
defined to be those that have a nonzero value for the
winding number.
1. Initializing the winding number to 0.

2. Imagine a line drawn from any position P to a distant
point beyond the coordinate extents of the object.
CS 380 CH 3-P2 - 23
Nonzero Winding Number Rule :
3. Count the number of edges that cross the line in each

direction. We add 1 to the winding number every time
we intersect a polygon edge that crosses the line from
right to left, and we subtract 1 every time we intersect
an edge that crosses from left to right.
4. If the winding number is nonzero, then

P is defined to be an interior point
Else
P is taken to be an exterior point.
CS 380 CH 3-P2 - 24
CH 3-P2 - 25
Boundary-Fill Algorithm
 Start at a point inside a region and paint the interior
outward toward the boundary. If the boundary is
specified in a single color, the fill algorithm proceeds
outward pixel by pixel until the boundary color is
encountered.
 It is useful in interactive painting packages, where

interior points are easily selected.
 The inputs of the this algorithm are:

• Coordinates of the interior point (x, y)
• Fill Color
• Boundary Color
CS 380 CH 3-P2 - 26
Boundary-Fill Algorithm (cont.)
 Starting from (x, y), the algorithm tests

neighboring pixels to determine whether they are
of the boundary color. If not, they are painted
with the fill color, and their neighbors are tested.
This process continues until all pixels up to the
boundary have been tested.
 There are two methods for proceeding to

neighboring pixels from the current test position:
CS 380 CH 3-P2 - 27
1. The 4-connected
method.
2. The 8-connected
method.
CS 380 CH 3-P2 - 28
void boundaryFill4 (int x, int y, int fillColor, int borderColor)

{ int interiorColor;
/* set current color to fillColor, then perform following operations. */
getPixel (x, y, interiorColor);
if ( (interiorColor != borderColor) && (interiorColor != fillColor) )
{
setPixel (x, y); // set color of pixel to fillColor
boundaryFill4 (x + 1, y, fillColor, borderColor);
boundaryFill4 (x - 1, y, fillColor, borderColor);
boundaryFill4 (x, y + 1, fillColor, borderColor);
boundaryFill4 (x, y - 1, fillColor, borderColor);
}
}
CS 380 CH 3-P2 - 29
CS 380 CH 3-P2 - 30
 4-connected and 8-connected methods involve heavy

recursion which may consume memory and time. More
efficient methods are used. These methods fill horizontal
pixel spans across scan line. This called a Pixel Span
method.
 We need only stack a beginning position for each

horizontal pixel span, instead of stacking all unprocessed
neighboring positions around the current position, where
spans are defined as the contiguous horizontal string of
positions.
CS 380 CH 3-P2 - 31
Pixel Span Method
• Start from the initial interior point, then fill in the

contiguous span of pixels on this starting scan line. Then
we locate and stack starting positions for spans on the
adjacent scan lines, where spans are defined as the
contiguous horizontal string of positions bounded by
pixels displayed in the area border color.
• At each subsequent step, we unstack the next start

position and repeat the process. An example of how
pixel spans could be filled using this approach is
illustrated for the 4-connected fill region in the following
figure.
CS 380 CH 3-P2 - 32
Pixel Span Method (cont.)
CS 380 CH 3-P2 - 33
Pixel Span Method (cont.)
CS 380 CH 3-P2 - 34
Flood-Fill Algorithm
 Sometimes we want to fill in (or

recolor) an area that is not defined
within a single color boundary. We
can paint such areas by replacing a
specified interior color instead of
searching for a boundary color
value. This approach is called a
flood-fill algorithm.
CS 380 CH 3-P2 - 35
Flood-Fill Algorithm (cont.)
 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.
CS 380 CH 3-P2 - 36
Flood-Fill Algorithm (cont.)
void floodFill4 (int x, int y, int fillColor, int interiorColor)

{ int color;
/* set current color to fillColor, then perform following operations. */
getPixel (x, y, color);
if (color = interiorColor)
{
setPixel (x, y); // set color of pixel to fillColor
floodFill4 (x + 1, y, fillColor, interiorColor);
floodFill4 (x - 1, y, fillColor, interiorColor);
floodFill4 (x, y + 1, fillColor, interiorColor);
floodFill4 (x, y - 1, fillColor, interiorColor);
}
}
CS 380 CH 3-P2 - 37

Chapter Three: Output Primitives

Uploaded by

Copyright:

Available Formats

Chapter Three: Output Primitives

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter Three: Output Primitives

Uploaded by

Copyright:

Available Formats

Chapter Three

• In this chapter we will cover the following topics:

• This chapter will show the discrete nature for computer

• After generating a line or circle using scan conversion, we

• Frame buffer is stored in memory as an addressable array

• For a bilevel system (1 bit per pixel),the Frame-Buffer bit address

1. addr(x, y) = addr (0,0) + y (xmax +1) + x

3. addr(x + 1, y + 1) = addr(x, y) + xmax + 2

addr(x, y) = addr (0,0) + y(xmax +1) + x

addr(7, 5) = addr(6, 5) + 1 = 572

• When an object is scan converted into the frame buffer, the

• To preserve the specified geometry of world objects, we need

1) Adjust the dimensions of displayed objects to account for the

2) Map world coordinates onto screen positions between pixels, so that

Screen Grid Coordinates:

• For example, the

• With the coordinate origin

• The following figure

• In general, we identify the area occupied by a pixel with

• This pixel addressing scheme has several advantages:

1) The previous algorithms for drawing line, circle, …etc

2) The decision parameter Pk is a measure of screen

 A standard output primitive in general graphics packages is a solid-

 There are two basic approaches to area filling on raster systems:

1. The scan-line approach

Scan-Line Fill Algorithm:

 For each scan line crossing a polygon, the area-fill

 These intersection points are then sorted from left to

 Calculations performed in scan-conversion and other

 Coherence is simply that the properties of one part of a

 Coherence methods often involve incremental

 Area-filling algorithms and other graphics processes

 To identify interior regions of an object graphics

Odd-Even rule (Odd Parity Rule, Even-Odd Rule):

1. draw a line from any position P to a distant point outside

2. If the number of polygon edges crossed by this line is

Nonzero Winding Number Rule :

 Counts the number of times the polygon edges wind

1. Initializing the winding number to 0.

Nonzero Winding Number Rule :

3. Count the number of edges that cross the line in each

4. If the winding number is nonzero, then

 It is useful in interactive painting packages, where

 The inputs of the this algorithm are:

 Starting from (x, y), the algorithm tests

 There are two methods for proceeding to

void boundaryFill4 (int x, int y, int fillColor, int borderColor)

 4-connected and 8-connected methods involve heavy

 We need only stack a beginning position for each

• Start from the initial interior point, then fill in the

• At each subsequent step, we unstack the next start

 Sometimes we want to fill in (or

void floodFill4 (int x, int y, int fillColor, int interiorColor)

You might also like