Browse Prior Art Database

Modification of Bresenhams Algorithm for Displays

IP.com Disclosure Number: IPCOM000084328D
Original Publication Date: 1975-Oct-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 2 page(s) / 43K

Publishing Venue

IBM

Related People

Gardner, PL: AUTHOR

Abstract

The article by J. E. Bresehham entitled "Algorithm for Computer Control of a Digital Plotter" in the IBM Systems Journal, Volume 4, No 1, 1965, describes an algorithm which can be used to generate points on a digital display or digital plotter to define a vector. Given the end points of the vector (e.g., x(1) y(1) and x(2) y(2)) or one end point and the length (e.g., x(1) y(1) and dx, dy), the algorithm can be used to generate one point per iteration.

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 2

Modification of Bresenhams Algorithm for Displays

The article by J. E. Bresehham entitled "Algorithm for Computer Control of a Digital Plotter" in the IBM Systems Journal, Volume 4, No 1, 1965, describes an algorithm which can be used to generate points on a digital display or digital plotter to define a vector. Given the end points of the vector (e.g., x(1) y(1) and x(2) y(2)) or one end point and the length (e.g., x(1) y(1) and dx, dy), the algorithm can be used to generate one point per iteration.

Referring now to Fig. 1, it is desired to determine which points on a matrix need to be selected to display an approximation of the straight line between S and F. Starting from point S (x(0) y(0)) the x coordinate is stepped by 1 and Bresenham's algorithm is used to determine whether the y coordinate should be stepped by 1 for the current point. An accumulator is used to record the current difference between the computed value for y (i.e., yc) and the real value for y (yr) at the current value of x. Rounding up or rounding down can be used.

The algorithm can be modified to allow 2 points per iteration and possibly 4. The computed values of y, that is yc, before rounding will by symmetrical about the midpoint of the line. Thus (yc-yr) will be the same for the kth point up from x(0) y(0) as for the kth point down from x(10) y(4): The modification is to use the accumulated difference (yc-yr) to step the points not only up from x(0) y(0) but also down from x(10) y(4): this allows two points to be...