Browse Prior Art Database

Parallel Bresenham Line Algorithm

IP.com Disclosure Number: IPCOM000110585D
Original Publication Date: 1992-Dec-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 3 page(s) / 102K

Publishing Venue

IBM

Related People

Narayanaswami, C: AUTHOR

Abstract

A parallel algorithm to draw lines on a raster display is presented. The algorithm is a parallelization of Bresenham's sequential raster line algorithm. The set-up cost is similar to that of the sequential algorithm and the remaining work is distributed evenly among the processors.

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

Parallel Bresenham Line Algorithm

       A parallel algorithm to draw lines on a raster display is
presented.  The algorithm is a parallelization of Bresenham's
sequential raster line algorithm.  The set-up cost is similar to that
of the sequential algorithm and the remaining work is distributed
evenly among the processors.

      This article describes a parallel version of the Bresenham [1]
raster line algorithm.  This involves the determination of the pixels
to be turned on in a raster display system when drawing a line from
(x0, y0) to (x1, y1).  The algorithm presented here is different from
the one described in [2] in that it does not divide the line into
many pieces and associate each piece to a separate processor.
Instead, consecutive pixels on the line are handled by different
processors, ensuring that spatially contiguous pixels are visited
contiguously in time, thereby making this scheme more suitable for
interleaved memory organizations.
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.
            N  = number of processors
            (x0, y0) = starting point of line
            (x1, y1) = ending point of line
            delta_x = x1 - x0  > 0
            delta_y = y1 - y0  > 0
            delta_x >= delta_y (other cases solved by symmetry)
            jump_x = N
            jump_y = ( N  * delta_y ) / delta_x

      The figure shows a raster line through (x0, y0) and (x1, y1).
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.
xs(i) and ys(i) denote the starting x and y coordinates for processor
i.  The next pixel processed by processor i will be either (xs(i)
jump_x, ys(i) + jump_y) or (xs(i) + jump_x, ys(i) + jump_y+ 1),
depending on which one is closer to the real line.  The vector
(disp_x (i), disp_y(i)) is the displacement between the first
endpoint of the line (x0, y0) and the first pixel visited by the i th
processor (xs(i), ys(i)).
               xs(i) = x0 + disp_x(i) = x0 +...