Browse Prior Art Database

High Speed Line Drawing Algorithm

IP.com Disclosure Number: IPCOM000040362D
Original Publication Date: 1987-Nov-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 3 page(s) / 40K

Publishing Venue

IBM

Related People

Urquhart, RJ: AUTHOR

Abstract

A method is described to increase the line drawing speed of display adapters. Previous algorithms implemented in the GSL used the Bresenham algorithm and wrote to the adapter after each pel was generated. Bresenham has described a run-length algorithm for obtaining faster line drawing speeds in an article entitled "Algorithm for Computer Control of a Digital Plotter," IBM Systems Journal 4(1), 25-30 (1965). However, that algorithm has increased complexity in preprocessing to determine the run-length options, determining which option to use per run, determining the beginning and ending runs, and still requires extra effort to "repackage" the runs to fit the memory contraints of these adapters. For average length lines and random angles the approach described here appears to be faster.

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

High Speed Line Drawing Algorithm

A method is described to increase the line drawing speed of display adapters. Previous algorithms implemented in the GSL used the Bresenham algorithm and wrote to the adapter after each pel was generated. Bresenham has described a run-length algorithm for obtaining faster line drawing speeds in an article entitled "Algorithm for Computer Control of a Digital Plotter," IBM Systems Journal 4(1), 25-30 (1965). However, that algorithm has increased complexity in preprocessing to determine the run-length options, determining which option to use per run, determining the beginning and ending runs, and still requires extra effort to "repackage" the runs to fit the memory contraints of these adapters. For average length lines and random angles the approach described here appears to be faster. The new method is to execute the Bresenham algorithm to generate one pel at a time but to delay writing pels until an adapter memory boundary is exceeded. At that time the accumulated pels are written. This amortizes the write time over from one to eight pels.

In addition the Bresenham inner loop is "unfolded" to match the natural memory byte boundary and selected "adjacency" mode which further reduces the overhead per pel. There are four assembly level subroutines (horizontal, vertical, x-direction and y-direction) for each of two writing modes (replace and exclusive-OR). This concept was applied to the x- and y-direction routines. The horizontal and vertical routies were already optimized for minimum adapter writes per pel. The x-direction or y-direction routine is selected when the line is neither horizontal nor vertical. The x-direction is selected when the absolute angle is less than or equal to 45 degrees; otherwise, the y-direction is used. Lines consist of two points: x1,y1 and x2,y2. The method folds all lines into the positive x-direction. That is the end points may be swapped so that x2 >= x1. The memory-mapped display buffer memory is organized so that two "adjacent" bytes (16 pels) can be written at one time. Adjacency has one of the following four meanings: 1. The second byte is the next byte forward in the

x-direction (+X).

2. The second byte is the next byte backward in the

x-direction (-X).

3. The second...