Browse Prior Art Database

Symmetric Bresenham Ling Algorithm

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

Publishing Venue

IBM

Related People

Narayanaswami, C: AUTHOR

Abstract

The Bresenham[*], line 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). Let A be the set of pixels drawn for the line from (a0, b0) to (a1, b1). Let B be the set of pixels drawn for the line from (a1, b1) to (a0, b0). For the Bresenham algorithm A != B, i.e., the output of the algorithm is not "symmetric" with respect to the ordering of the line's coordinates. Figs. 1 and 2 illustrate this difference.

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

Symmetric Bresenham Ling Algorithm

      The Bresenham[*], line 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).  Let A be the set of pixels drawn for
the line from (a0, b0) to (a1, b1).  Let B be the set of pixels drawn
for the line from (a1, b1) to (a0, b0).  For the Bresenham algorithm
A != B, i.e., the output of the algorithm is not "symmetric" with
respect to the ordering of the line's coordinates.  Figs.  1 and 2
illustrate this difference.

      This asymmetry causes artifacts such as varying width lines at
the common edge between two adjacent faces of a polyhedron because
the edge may not be specified in the same order in the two faces.
These artifacts are currently avoided by ensuring that the edges get
drawn in the same direction for both faces by reversing one of the
edges if necessary.  This involves additional overhead of sorting the
coordinates of the line.  When the edges of the polygon are drawn as
patterned lines, if the endpoints are reversed the pattern needs to
be reversed too and this is complicated.

      This disclosure presents an improvement of the Bresenham raster
line drawing algorithm which makes it "symmetric" with respect to the
endpoints and ensures that A = B.  Thus, this algorithm avoids the
need to sort the endpoints of the line and the overhead to reverse
the pattern for patterned lines.

THE ALGORITHM - 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           abs(delta_x) >=
abs(delta_y)
          delta_x * delta_y >= 0  (Other cases solved by symmetry)

      Fig. 1 shows a raster line through (x0, y0) = (a0, b0)
      and (x1, y1) = (a1, b1).  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.  For the region above the line
      F(x, y) < 0 and for the region below the line and F(x, y) > 0.

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_...