Browse Prior Art Database

Line Drawing using Mfast Digital Signal Processor Array Processor

IP.com Disclosure Number: IPCOM000116232D
Original Publication Date: 1995-Aug-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 6 page(s) / 173K

Publishing Venue

IBM

Related People

Glossner, CJ: AUTHOR [+3]

Abstract

This algorithm provides a high performance mechanism for drawing lines on a computer display using a parallel approach.

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

Line Drawing using Mfast Digital Signal Processor Array Processor

      This algorithm provides a high performance mechanism for
drawing lines on a computer display using a parallel approach.

      There are two parts to drawing a line on the Mfast Digital
Signal Processor (DSP) array processor.  First, the Sequence
Processor (SP) solves some setup variables, then the Processing
Elements (PE) use those results to calculate the diagonal movement
between pixels.  The PEs also calculate the horizontal length by
subtracting one diagonal movement result from the next.  Each
starting point (X,Y) and it length is referred to as a span and is
output to the memory interface to be written into a Frame Buffer.
Other approaches to solve this problem are done in graphics
accelerator chips using a Bresenham line algorithm.  This is an
iterative interpolation method using incrementers and adders.
Another approach is a Digital Difference Analyzer (DDA) which uses
the addition of the slope with rounding to select the pixel drawn.

      The Mfast DSP approach shown will draw lines with orders of
magnitude faster performance then the previous methods.  When running
a Windows API there are many Graphics functions used such as:
Line-Drawing, Area-Filling, Window-Clipping, or Shading triangles
just to mention a few.  For our proposed system some functions are
implemented in unique hardware while others are done in code running
on the Mfast.  This disclosure will discuss a new Line-Drawing
algorithm and how it runs on the Mfast DSP chip which integrates a
graphics subsystem tightly coupled to the array processor.

      Conventional line-drawing algorithms are inherently sequential.
When applied directly on parallel machines, these algorithms can
result in very inefficient code.  This leads us to reexamine the
existing algorithms or create new ones for the new parallel
environment Mfast offers.  As an example, a popular line-drawing
algorithm, such as Bresenham's is compared with a new one for Mfast.
Hardware implementation of Bresenham algorithm, e.g., QPAX, Weitek
and S3, includes some setup variables and a running error term that
dictates when a coordinate changes.  Typically one pixel is
calculated per clock cycle and the line drawing performance tops out
as a function of the clock speeds.  Fig. 1 outlines the Bresenham
Algorithm for a line drawn in the first octant which is less than
45 degrees in the +X,+Y direction.

      Mfast accomplishes drawing lines by running code on both the
Sequence Processor (SP) and the Processing Elements (PE) in
combination with rendering hardware.  The code is made up of unique
instructions specially architected to render graphics primitives.
The following describes a step by step process of how Mfast draws a
line.  For ease of discussion, the following example is done for a
line drawn in the first octant which is in the positive X and Y
directions and less then 45º  All other line directio...