Browse Prior Art Database

Polarized Raster Ling Algorithm Introduction

IP.com Disclosure Number: IPCOM000106046D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 6 page(s) / 160K

Publishing Venue

IBM

Related People

Narayanaswami, C: AUTHOR

Abstract

A raster line drawing algorithm involves the determination of the pixels to be turned on in a raster display system when drawing a line from (a0, b0) to (a1, b1). Fig. 1 shows a line and the discrete pixel approximation of the line by the [*] algorithm. The constraint used by this algorithm is that the raster line minimizes the mean squared distance error between the ideal line and the discrete line. While the above constraint is the best in many cases, sometimes it is necessary for the line to be polarized, i.e., represented in the discrete pixel space as shown in Fig. 2 or as shown in Fig. 3. For example while drawing a hollow polygon, the user might want all pixels for the edges to be inside the polygon, i.e.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 48% of the total text.

Polarized Raster Ling Algorithm Introduction

      A raster line drawing algorithm involves the determination of
the pixels to be turned on in a raster display system when drawing a
line from (a0, b0) to (a1, b1).  Fig. 1 shows a line and the discrete
pixel approximation of the line by the [*] algorithm.  The constraint
used by this algorithm is that the raster line minimizes the mean
squared distance error between the ideal line and the discrete line.
While the above constraint is the best in many cases, sometimes it is
necessary for the line to be polarized, i.e., represented in the
discrete pixel space as shown in Fig. 2 or as shown in Fig. 3.  For
example while drawing a hollow polygon, the user might want all
pixels for the edges to be inside the polygon, i.e., the pixels
should be to the left of each edge in the polygon when the vertices
of the polygon are specified in counterclockwise order.  In Fig. 2
all pixels chosen to represent the line are to either on the line or
to its right, i.e., the line is "right polarized" as seen by a viewer
walking along the edge from the starting point to the ending point.
Similarly in Fig. 3 all pixels chosen to represent the line are
either on it or to its left, i.e., the line is "left polarized" as
seen by a viewer walking along the edge from the starting point to
the ending point.  All arithmetic operations and variables used in
this algorithm are in the integer domain.  The following definitions
will be used in the description of the algorithm.

         (x0, y0) = starting point of line
         (x1, y1) = ending point of line
          delta_x = x1 - x0
          delta_y = y1 - y0
          |x| =  absolute value of x
          |delta_x| >= |delta_y| and  delta_x * delta_y >= 0
               other cases solved by symmetry

Fig. 1 shows a raster line through (x0, y0) = start point and (x1,
y1) = end point.  The equation of this line is

(y - y0)/(x - x0) = delta_y/delta_x
         => x * delta_y - y * delta_x + x1 * y0 - x0 * y1 = 0

Let F(x, y) = 2(x delta_y - y delta_x + x1 y0 - x0 y1).  F(x, y) = 0
represents the line.  When delta_x > 0, F(x, y) < 0 for the region
above the line and F(x, y) > 0 for the region below the line (Fig.
4).  An error term "e" represents twice the signed distance between
the line and the midpoint between the two candidate pixels to be
chosen next.  At the start of the algorithm, the two pixels that may
be chosen next are (x0 + sign(delta_x), y0) and (x0 + sign(delta_x),
y0 + sign(delta_y)), where "sign" is the sign function:

         sign (x) = 1 if x > 0
                    0 if x = 0
                   -1 if x < 0

The midpoint between the next two candidates is (x0 + sign(delta_x),
y0 + sign(delta_y)/2).  Therefore, the starting value for "e" is
given by
e =  F (x0 + sign(delta_x), y0 + sign(delta_y)/2)
  =  2*(sign(delta_y)*delta_y...