Browse Prior Art Database

Symmetric 3D Bresenham Line Algorithm

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

Publishing Venue

IBM

Related People

Narayanaswami, C: AUTHOR

Abstract

The [*] line algorithm can be used to determine the pixels ( (x, y) locations) to be turned on in a raster display system when drawing a 3-D line from (a0, b0, c0) to (a1, b1, c1). Let A be the set of pixels drawn for the line from (a0, b0, c0) to (a1, b1, c1). Let B be the set of pixels drawn for the line from (a1, b1, c1) to (a0, b0, c0). 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. Similarly, if the depth of the line is also determined by a Bresenham algorithm then the depth at a pixel can depend on the order in which the endpoints are specified.

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

Symmetric 3D Bresenham Line Algorithm

      The [*]  line algorithm can be used to determine the pixels (
(x, y) locations) to be turned on in a raster display system when
drawing a 3-D line from (a0, b0, c0) to (a1, b1, c1).  Let A be the
set of pixels drawn for the line from (a0, b0, c0) to (a1, b1, c1).
Let B be the set of pixels drawn for the line from (a1, b1, c1) to
(a0, b0, c0).  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.
Similarly, if the depth of the line is also determined by a Bresenham
algorithm then the depth at a pixel can depend on the order in which
the endpoints are specified.

Note: The use of the DDA algorithm as opposed to the Bresenham
algorithm only exacerbates the problem.

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.  Also
when the two lines are z-buffered and in different colors, one of the
lines may periodically "poke-through" the other, creating visually
unpleasing results.

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 a 3-D raster line drawing algorithm which is
"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.

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, z0) = starting point of line
         (x1, y1, z1) = ending point of line
          delta_x = x1 - x0
          delta_y = y1 - y0
          delta_z = z1 - z0
    abs(delta_x) >= abs(delta_y)
    delta_x * delta_y >= 0  (Other cases solved by symmetry)

The 3-D line is drawn by decomposing the line into its projection on
the XY plane and one of the XZ or the YZ planes.

SYMMETRY IN THE XY PLANE- This section is adapted from disclosure
AT-91-1024 and is included here for convenience and completeness.

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