Browse Prior Art Database

Accelerated Bresenham Algorithm

IP.com Disclosure Number: IPCOM000084070D
Original Publication Date: 1975-Sep-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 72K

Publishing Venue

IBM

Related People

Hoo, SK: AUTHOR

Abstract

One of the potential uses of four gaseous discharge display devices is that of the vector generation on a digital plotter display. For efficient utilization of the device, it is desirable to draw vectors by writing slices and to relate a given coordinate address on the display device to the nearest vector. The Bresenham algorithm is modified to incorporate these features. The Bresenham algorithm represents one method used with conventional digital plotters for computing successive points of a vector.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Accelerated Bresenham Algorithm

One of the potential uses of four gaseous discharge display devices is that of the vector generation on a digital plotter display. For efficient utilization of the device, it is desirable to draw vectors by writing slices and to relate a given coordinate address on the display device to the nearest vector. The Bresenham algorithm is modified to incorporate these features. The Bresenham algorithm represents one method used with conventional digital plotters for computing successive points of a vector.

Referring to Fig. 1, a quadrant of a display area is illustrated in which V represents the exact vector to be displayed. D1, Q1, Q2, Q3 and D2 are the five coordinate points which comprise the best representation for V. Bresenham's algorithm gives an indicated movement of either m1 or m2 from a previous point, m1 indicating horizontal movement and m2 movement at a 45 degree angle. Thus V is represented by m1 and m2 movements as shown. The described implementation improves the operating speed of the Bresenham algorithm by writing slices, and relating a given address "P" on the display to the vector V.

Referring to Fig. 2, vector V2 is composed of 9 points as illustrated which form one horizontal slice. The 8 points for V1 form four horizontal slices, the first slice consisting of one point, the second slice of 3 points, the third and fourth slices of 2 points each. Vectors drawn in slices require less motion and time than point-by-point plotting, and by relating the given address P to a Sector, the modified algorithm reduces the time required by a factor of 2/N/ where N=0,1,2,3, etc.

Fig. 3 illustrates how P is related to V2 where n=1. The points representing the vector are reduced by a factor of 2/N/ such that when N=1, the time required to generate vector V1 is halved.

The Bresenham algorithm is also used when it is desired to locate a vector given an X,Y location on the digital plot, such as provided by a light pen detect on a raster scan cathode-ray tube (CRT) or gas panel. P identifies the location pointed at, and by inspection V1 is indicated. This procedure is implemented by running the Bresenham algorithm through all the points of every vector. At each point the generated X,Y location is compared with the location for P.

When the error of this compare is less than a predetermined amount, the desired vector is identified. This locate time is shortened by first dividing Deltaa(i), Deltab(i) of every vector by an integer N > or - 1, where Deltaa(i), Deltab(i), DeltaX, Delta4 for the vector. Points are then generated, and compares made and the raster grid made effectively coarser by N.

In Fig. 3, Deltaa(i) and Deltab(i) are divided by 2 so they are shifted right by one position, thereby reducing the new vector location time from 17 points, to 9 points plus two right shifts. Further speed-up is pos...