Boundary mapping for multi-pel thickness lines

Details Boundary mapping for multi-pel thickness lines Boundary mapping for multi-pel thickness lines

2000-05-16

2003-09-30

Johns, Andrew W. (Department: 2621)

Image analysis

Image enhancement or restoration

Object boundary expansion or contraction

C382S258000, C382S266000, C345S443000

Reexamination Certificate

active

06628840

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to computer generated graphic images and in particular to a method. for producing a straight line with rounded ends in a data processing environment. More particularly, the present invention relates to an improved method for generating a rasterized image of a straight line.
2. Description of the Related Art
A display or printer is called a “raster” if it produces a graphical image within the context of an orthogonal grid of individual picture elements (pels). When a conventional raster device displays or prints graphic images such as lines, circles, ellipses, and other curves, it does so by coloring those pels in the raster grid that lie closest to the grid location of the line or curve. Until recently, most raster devices have drawn lines that were at most a few pels thick. Currently, higher resolution raster devices are capable of generating lines and curves of arbitrary user specified thickness.
A common method for generating a line having a multi-pel thickness is to draw an initial trace of the line having a thickness of a single pel. A succession of retraces are then drawn with each subsequent retrace slightly displaced from the preceding trace. This method of generating a rasterized line requires substantial processing overhead when the required thickness is more than a few pels thick and is therefore inefficient for higher resolution displays and printers.
Another method for generating multi-pel thickness lines requires the determination of two or more curves that envelope the proposed line and then filling the space within the resulting closed curve. Efficient bound-and-fill methods for filling within a bounded curve are well known in the art. A problem encountered with conventional boundary-and-fill methods is that generating multiple boundary segments is computation intensive and requires substantial processing overhead.
U.S. Pat. No. 5,293,472 describes an alternate method for rasterizing a multi-pel line. This method entails generating a spine list that comprises a digitization of a spine that can be swept by a series of circular dots having pre-determined pen thickness (thickness of the line in pels). A line adjustment algorithm is then utilized to guide the drawing of many overlapping dots to produce the line. This overlapping dot technique requires mapping the same pels into memory many different times. Given the increased resolution of modern printers and display devices and the increased memory required for each pel, the overlapping dot technique results in decreased raster device performance.
It can therefore be appreciated that a need exists for an improved method and system for rasterizing a multi-pel thickness line to suit higher resolution and higher performance graphic display devices.
SUMMARY OF THE INVENTION
A method for mapping a picture element (pel) boundary for a multi-pel thickness line into a bitmap image is disclosed herein. The line has thickness T centered around a spine having a slope, m, between a start and stop point. The boundaries for the rounded ends of the line are determined by centering a pre-stored T-diameter pel dot boundary with respect to the start and stop points. The rounded end boundaries are tangentially connected by a first pair of sides of a rectangular perimeter whose remaining two sides diametrically intersect the dot boundaries. The start (or stop) point, the line thickness, T, and the slope of the line, m are utilized in estimating and mapping four corner points of the rectangular perimeter with respect to the orthogonal pel array. The vertical orientation of the mapped corner points designate up to five sections of the line boundary including two end sections, one of which lies above an uppermost corner point, and the other below a lowermost corner point. Both end sections are mapped according to the corresponding pel dot boundary as centered at the start and stop points. A middle section, situated between the innermost corner points of the rectangular perimeter, has a first straight sliding edged determined according to Bresenham's algorithm and a second straight edge determined by adding the fixed horizontal width of the line to te horizontal position of the first edge. For the remaining two sections, which lie between the middle section and the uppermost and lowermost sections respectively, one edge is estimated and mapped utilizing Bresenham's algorithm and the other edge is mapped in according to the corresponding pel dot boundaries.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.


REFERENCES:
patent: 4849910 (1989-07-01), Jacobs et al.
patent: 4905166 (1990-02-01), Schuerman
patent: 5293472 (1994-03-01), Lotspiech
patent: 405258068 (1993-10-01), None
“Breshenham's Algorithm.” Kenneth I. Joy, Visualization and Graphics Research Group, Department of Computer Science, University of California, Davis, pp. 1-15.

Affiliated with

Also associated with

Rating

Boundary mapping for multi-pel thickness lines does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Boundary mapping for multi-pel thickness lines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boundary mapping for multi-pel thickness lines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3037183