Computer graphics processing and selective visual display system – Computer graphics processing
Reexamination Certificate
2000-05-03
2003-05-27
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
C345S420000, C345S686000, C345S530000, C345S443000, C345S549000, C382S202000, C382S260000
Reexamination Certificate
active
06570562
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer applications with high-performance graphics capabilities, and to subassemblies and methods for use in such applications.
BACKGROUND OF THE INVENTION
Many software applications include built-in “rendering” or “drawing” programs to build images of graphics primitives, such as lines, circles, etc., for display. The graphics primitives are laid out or rendered in a buffer memory prior to being displayed. Building an image by such rendering programs may occur by allocating a partition in the main memory address space as the buffer for rendering a graphic image. Data between the main memory and the buffer is exchanged as required by the demands of rendering. The buffer may be an on-screen video memory that displays the graphic while it is being built, an off-screen video memory partition or imaging area that will be swapped into the on-screen video memory partition when it is time to display the graphic primitive, or an address space serving as either an on-screen memory or an off-screen memory. An off-screen memory imaging area is a partition of memory that is capable of rendering graphics primitives without displaying them on a viewable device; it is an area of memory that can be addressed as if it were a graphics device.
A particular interest to the present application is the rendering of lines. Straight, solid lines may be rendered through the so-called “brute-force approach” or the “primitive line-drawing method,” of which Bresenham's algorithm is an example. The brute-force approach is a straightforward way to compute a pixel-by-pixel representation of a straight line that first requires that the equation of a line, y=mx+b, be solved and applied pixel-by-pixel. This approach, while simple, is computationally intensive and requires the use of real-number arithmetic for each pixel thus computed. Bresenham's algorithm is the usual technique for drawing a straight, solid line. Integer arithmetic is used to quickly calculate the individual pixels to be turned on. By carrying an error term, the average slope of the line is followed exactly, without having to perform multiplication at each pixel.
While the rendering of straight, solid lines is well established in the art, the drawing of patterned or stippled lines is of more concern. Certain computer software applications do not support the representation or drawing of stippled or patterned lines, so that patterned lines cannot be easily viewed through a standard viewing mechanism such as a monitor or other on-screen viewing device. Sun Microsystem's Java 1.1, a programming language used by many applications, for instance, does not support the drawing of patterned lines. There is no mechanism currently available through the Java 1.1 language interface that is capable of rendering patterned lines. Patterned or stippled lines as used herein refer to non-solid lines in which some type of pattern, such as dots, dashes, etc., is apparent. The term “pattern” generally refers to an array containing run-length encoding made up of “on” and “off” segments; the term “pattern repeat length” refers to the sum of the pattern's segment lengths. Thus a pattern of {3, 2, 1, 2}, has four pattern segments: a first, “on” segment with a length of three pixels, a second, “off” segment with a length of two pixels, a third, “on” segment with a length of one pixel, and a fourth, “off” segment with a length of two pixels. The pattern repeat length of this pattern is the sum of the segment lengths, or 8 pixels. A pattern is typically drawn over and over until the entire length of the patterned line is exhausted. An empty pattern ({ }) is equivalent to a single “on” segment of infinite length.
A patterned line is typically represented by rendering the segments of the line. The so-called “line-segment” solution calculates the extents of each line segment of a patterned line using the original endpoints of the line and employs a substantial amount of floating-point calculations to determine segment endpoints of the line. While workable, the line-segment solution results in an inaccurate representation of the line due to round-off error typically introduced during the floating-point calculations. Pixels drawn using the line-segment approach are not guaranteed to fall on the original primitive rendering of a line; the question becomes how to treat pixels that do not fall squarely on the line. This problem is not encountered when patterned lines are drawn according to the Bresenham line draw algorithm in which the particular pixels or dots between the two endpoints that will be drawn is determined. While solid lines with their integer coordinates are readily rendered in this manner, the primitive line-drawing method of the Bresenham algorithm cannot be easily used to render the fractional coordinates commonly associated with the segments of a patterned line.
Consider, for example, that a line from Cartesian coordinates [0, 0] to [9, 3] is to be rendered. [0, 0] refers to the beginning endpoint of the line, generally the leftmost endpoint. [9, 3] refers to the ending endpoint, generally the rightmost endpoint of the line. Diagram 1 illustrates the results of applying a typical line-drawing primitive to render a Cartesian coordinate representation of this line in a graphical display area, with each “#” representing a pixel that is rendered as “on.”
Now suppose that a pattern which has an initial segment of length 5 is to be imposed on the line. The coordinates of the endpoint of the initial segment would be, in real number coordinates, [4.74,1.58]. The endpoints, however, must be specified in integer coordinates. There are two methods available for converting real numbers into integer values-ignoring the fractional components (“truncation”) or picking the “nearest” integer value (“rounding”). For example, if one were to convert the real numbers to integers by ignoring the fractional components, the endpoint for the end of the initial segment would be chosen as [4,1]. Diagram 2 depicts a typical rendering of the line segment from [0,0] to [4,1]:
This method correctly chooses pixels that originally appeared on the line. However, the pixel [4,1] is turned “on” even though it only partially lies within the 5-unit pattern segment; adherence to the specified pattern is not maintained.
An alternate approach to coordinate conversion is to round up or round down a real number depending upon the value of the fractional remainder of the number, as measured in tenths. Thus, a number having a fractional remainder of greater than 0.5 would be rounded up to the next integer number while a number having a fractional remainder of equal to or less than 0.5 would be rounded down. If this standard rounding technique were applied in the example, the resulting endpoint would be [5,2]. Diagram 3 depicts a typical rendering of the line segment from [0,0] to [5,2]:
Notice that applying this technique caused the pixels at [4,2] and [5,2] to be turned on. Neither of these pixels were in the original line rendering, so some coherence with the original line rendering has been lost.
From an efficiency standpoint, the line-segment solution is very costly in that it calls the primitive line-drawing method for each segment of a patterned line. Since a pattern can have segments as small as one pixel, such calls of the primitive line-drawing method can fail to render certain portions of a line if the calculations end up with identical endpoints (beginning and ending) due to mathematical round-off. This results from the fact that the implementation of some primitive line-drawing methods render zero-length lines as a single pixel, others do not render them at all. This possibility is illustrated by the following example in which a line is drawn from [0,0] to [5,5] with an initial pattern segment of length 1. The end
Bella Matthew C.
Hewlett--Packard Development Company, L.P.
Sajous Wesner
LandOfFree
Method for drawing patterned lines in a system supporting... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for drawing patterned lines in a system supporting..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for drawing patterned lines in a system supporting... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3025905