Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1997-03-27
2003-03-04
Hong, Stephen S. (Department: 2176)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06529196
ABSTRACT:
TECHNICAL FIELD
The present invention relates to video controllers, and more particularly to graphics processors that process line drawing requests for display of graphics.
BACKGROUND ART
There are a variety of systems known in the art for selecting which pixels should be displayed, in the course of operation of digitally based graphics processors, for displaying line segments. The systems generally must result from a compromise of the conflicting goals of speed on the one hand and accuracy on the other. A well-known system employs the Bresenham algorithm, which is relatively efficient in handling line segments having ends coinciding with pixel locations. In situations where line segments have ends that do not coincide with pixel locations, however, the problem is more difficult. Such segments may often be identified by floating point coordinates. Moreover, relatively difficult situations arise for a display system when there are many connected line segments having lengths that are small compared to the distance between pixels. These situations are not addressed by the Bresenham algorithm.
SUMMARY OF THE INVENTION
In accordance with a preferred embodiment of the invention there is provided an improved device, of the type utilizing a display having pixels identified by a two-axis coordinate system, for displaying line segments. The coordinate system, for example, having standard rectangular X and Y Cartesian coordinates, is configured so that each pixel lies at the intersection of a coordinate line from each of the axes. The device is of the type for displaying a line segment referenced to the same coordinate system and the display operates under control of a digital computer. The improvement has an arrangement for determining as a major axis the axis of the coordinate system with respect to which the line moves most, and for defining the other one of the axes as the minor axis. A means is provided to identify the places where the major coordinate line of a pixel crosses the line segment to be displayed. There is a pixel selection arrangement operable, with respect to each crossing found by the preceding means, for selecting for display a pixel that both (i) lies on the major axis coordinate line at the crossing and (ii) has a minor axis coordinate that is closest to the line segment. In a further embodiment, the pixel selection arrangement includes means for, in the course of determining the pixel having a minor axis coordinate that is closest to the line segment, breaking a tie between two pixels by making a determination, in accordance with a uniform rule, to select for display one of them. In processing a line segment found to start or finish exactly on the major coordinate line of a pixel, so that there is no crossing of such coordinate line with the line segment, in a further embodiment, there is applied a second uniform rule to determine whether to select the pixel for display. The second uniform rule includes selecting for display one of the first and last pixels of a line segment with a possible exception in the case of a single line segment or a segment at a specified end of a series of connected segments. Related methods are also provided.
REFERENCES:
patent: 4939671 (1990-07-01), Sasser
Foley et al.,Computer Graphics: Principles and Practice, Second Edition, 1993, pp. 72-79.
3Dlabs Inc. Led.
Bockhop & Reich, LLP
Hong Stephen S.
LandOfFree
Efficient stroking of vectors with arbitrary endpoints does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient stroking of vectors with arbitrary endpoints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient stroking of vectors with arbitrary endpoints will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3039230