Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Computation of Bresenham Line Parameters

IP.com Disclosure Number: IPCOM000042124D
Original Publication Date: 1984-Mar-01
Included in the Prior Art Database: 2005-Feb-03
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Normington, G: AUTHOR

Abstract

This article describes a simple method which allows efficient continuation of the rastering process (using Bresenham's algorithm) from an intermediate position. Its applications lie in swathing algorithms for all-points-addressable printers and in line-clipping algorithms. The Method Suppose it is required to continue rastering the line from (x1,y1) to (x2,y2) from the position x=X. (An exactly similar analysis applies to a continuation from the position y=Y.) Without loss of generality, assume the line lies in the first octant. In order to continue rastering, it is sufficient to compute 1. some value Y (which in this case is unique) such that the pel (x-1,y) lies on the line and 2. the Bresenham error term at the point (X-1,Y). Bresenham Error Term: Translate the coordinates so that (x1,y1) becomes the origin.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 1

Computation of Bresenham Line Parameters

This article describes a simple method which allows efficient continuation of the rastering process (using Bresenham's algorithm) from an intermediate position. Its applications lie in swathing algorithms for all-points-addressable printers and in line-clipping algorithms. The Method Suppose it is required to continue rastering the line from (x1,y1) to (x2,y2) from the position x=X. (An exactly similar analysis applies to a continuation from the position y=Y.) Without loss of generality, assume the line lies in the first octant. In order to continue rastering, it is sufficient to compute 1. some value Y (which in this case is unique) such that the pel (x-1,y) lies on the line and 2. the Bresenham error term at the point (X- 1,Y). Bresenham Error Term: Translate the coordinates so that (x1,y1) becomes the origin. Then the error term at the point (X-1-x1,Y-y1) is 2.(X-x1).dy-2.(Y- y1).dx-dx where dx=x2-x1 and dy=y2-y1 A value of y: The equation of the (ideal) line is

(Image Omitted)

Performance Considerations Notice that the values given by equations (1) and
(2) can be computed in a time which is independent of the re-rastering start position. In any particular implementation, there is likely to be a gain in performance if complete re-rastering from the start of the line is performed for sufficiently short lines. The value of X-x1 (Y-y1) should be tested in order to determine whether to re-raster from the start or to use the...