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

Publishing Venue

IBM

Related People

Authors:
Urquhart, RJ [+details]

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.