Conventionally, various methods for drawing lines on a computer display have been proposed. One of the typical methods is the Bresenham's algorithm. This technique is unique in that it is fast because the drawing of any gradient lines or circular arcs can be implemented without real numbers (floating point numbers) and using only integer additions, subtractions, and shift operations and that it does not require any table or memory region for temporarily storing the coordinates of each point on the lines.
On the other hand, it has been desired to draw wide lines with a width of one pixel or more on a graphic display. This is because wide lines are visually more clear than thin lines, and, more advantageously, drawing wide lines adjacently provides wider lines and also allows specific regions to be filled efficiently.
In principle, however, it is impossible to apply the Bresenham's algorithm to the drawing of wide lines because it can essentially only draw lines of width 0. Furthermore, the criteria required by those skilled in the art is that when an outline is added to a wide line which has been drawn that the wide line contains all the pixels which should be inside the outline. Even the superposition of the Bresenham's algorithm does not allow this requirement to be met, and may result in missing pixels inside the outline.
There are known the prior art that disclose various techniques for efficiently drawing wide straight lines or circular arcs.
JA PUPA (Japanese Published Unexamined Patent Application ) No. 63-14286 discloses an algorithm wherein a wide line circle is drawn by repeatedly drawing a circular arc of the same radius while the center of the circle is sequentially moved in the internal direction.
JA PUPA No. 63-180182 discloses a method enabling the rapid drawing of wide lines by drawing a wide outline of any figure based on outline coordinates and wide outline information, and then filling the inside.
JA PUPA No. 63-282583 discloses a method enabling the rapid display of wide lines by providing coordinate information for only one point on the outer frame other than the center line of the wide line and width information.
JA PUPA No. 2-35580 discloses a method for providing lines having a width of a normal value by storing line specification and width data, moving the outline of the overall character so that the width of the line is equal to the line width data, and converting the outline data into bit data.
JA PUPA No. 2-208694 discloses a method for drawing lines with a certain width by creating wide line drawing element data and synthesizing the data on a frame buffer in a drawing direction as bit map data.
JA PUPA No. 4-137187 discloses a method for drawing wide lines at a precise speed by determining an upper, a middle, and a lower bit range to process a plurality of bits altogether.
However, these wide line drawing techniques require floating point operations as well as coordinate data for drawn points to be sequentially stored in a table in a memory, and thus require an extremely high throughput. Thus, even with the most recent high-performance processors, the drawing speed is still relatively slow.
USPTO Backgrounds
USPTO Backgrounds