Figure filling apparatus

Details Figure filling apparatus Figure filling apparatus

1999-06-04

2001-09-25

Luu, Matthew (Department: 2672)

Computer graphics processing and selective visual display system

Computer graphics processing

Character generating

C382S199000, C382S201000, C382S203000

Reexamination Certificate

active

06295073

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to an apparatus for use in computer graphics to fill a given figure by defining “contour color data” for each of a plurality of dots representing the contour of the figure and “inner color data” for each of another plurality of dots representing the inside of the figure, respectively. In this specification, the “computer graphics” includes not only producing an image on a CRT or liquid crystal display but also making a hardcopy using a printer, for example. The “figures” are not limited to two-or three-dimensional figures, but include many other graphics primitives such as characters and signs. The “colors” include not just chromatic colors, but achromatic colors.
An exemplary figure filling apparatus utilizing a so-called “edge fill algorithm” is disclosed in Japanese Laid-open Publication No. 6-162212. This apparatus draws a baseline near a polygon to be filled. A plurality of sides of the polygon are selected one by one, and a trapezoidal area is defined between this baseline and each side selected. Then, a plurality of dots, existing inside the trapezoidal area, are processed one after another. By repeatedly performing this processing, the polygon in question can be ultimately filled. In accordance with this technique, however, each dot should be processed numerous times. Thus, it is known that the larger the number of vertices of a polygon, the lower the resulting processing speed.
Examples of figure filling apparatuses adopting a so-called “scan algorithm” are disclosed in U.S. Pat. Nos. 4,967,376 and 5,561,534. In these apparatuses, a plurality of scan lines, crossing a figure to be filled, are drawn in parallel to a certain axis of coordinates. These scan lines are selected one by one, and a plurality of dots, existing on each scan line selected, are processed one after another. By repeatedly performing this processing, the polygon in question can be filled as a result.
In the apparatus disclosed in U.S. Pat. No. 4,967,376, however, when a doughnut-like figure with double contour loops is filled, for example, one of these two contour loops should be tracked clockwise, and the other counterclockwise (see FIGS. 2
a
and 2
b
of the patent).
Also, in the apparatus disclosed in U.S. Pat. No. 5,561,534, if the contour color data of a figure should be different from the inner color data thereof, the inner color data must be defined first for all the dots representing the inside of the figure. And then the contour color data must be defined for the respective dots representing the contour of the figure (see FIGS. 85 and 86 of the patent).
SUMMARY OF THE INVENTION
An object of the present invention is removing such restrictions that were imposed by those prior art figure filling apparatuses adopting the scan algorithm.
In order to achieve this object, the apparatus of the present invention includes means for labeling each of a plurality of dots representing the contour of a given figure as a vertical or horizontal attribute dot such that the number of vertical attribute dots, existing on arbitrary one of scan lines parallel to a certain axis of coordinates, is always zero or an even number. The apparatus further includes means for defining contour color data for all the dots labeled as the vertical or horizontal attribute dots, selecting one of the scan lines parallel to the axis of coordinates after another, excluding horizontal attribute dots from all the dots on the scan line selected, and defining the inner color data for the remaining dots existing between an odd-numbered vertical attribute dot and an even-numbered vertical attribute dot, which is next to the former dot, on the scan line selected.
More specifically, the apparatus of the present invention includes a vertex coordinate information supply unit for supplying vertex coordinate information including x and y coordinates of each of a plurality of vertex dots of a given figure. The apparatus also includes a vertex processing unit for selecting one of the vertex dots after another, determining, from the vertex coordinate information, the direction of a first vector terminating at the selected vertex dot and originating from a previous vertex dot and the direction of a second vector originating from the selected vertex dot and terminating at a next vertex dot, and labeling the selected dot as a vertical or horizontal dot based on the directions of the first and second vectors. The apparatus further includes a contour line segment producing unit for selecting one pair of adjacent vertex dots after another from the vertex dots, and defining, from the vertex coordinate information, the x and y coordinates of each of a plurality of edge dots located on a contour line segment connecting together the two vertex dots selected. The apparatus further includes a contour line segment processing unit for selecting one of the edge dots on the contour line segment after another and labeling the selected edge dot as a vertical attribute dot if the y coordinate of the edge dot selected is different from that of a previous edge dot and that of the vertex dot located at the terminal point of the contour line segment, or otherwise, as a horizontal attribute dot. The apparatus further includes a color data defining unit for defining the contour color data for all the dots labeled by the vertex and contour line segment processing units as the vertical or horizontal attribute dots, selecting one of the scan lines parallel to the axis of x coordinates after another, excluding horizontal attribute dots from all the dots on the scan line selected, and defining the inner color data for the remaining dots existing between an odd-numbered vertical attribute dot and an even-numbered vertical attribute dot, which is next to the former dot, on the scan line selected.


REFERENCES:
patent: 4626838 (1986-12-01), Tsujioka et al.
patent: 4897805 (1990-01-01), Wang
patent: 4967376 (1990-10-01), Katsura
patent: 4998211 (1991-03-01), Hamada et al.
patent: 5299299 (1994-03-01), Ohuchi
patent: 5561534 (1996-10-01), Ishida et al.
patent: 5579454 (1996-11-01), Billyard et al.
patent: 5689627 (1997-11-01), Arai et al.
patent: 5748777 (1998-05-01), Katayama et al.
patent: 5831624 (1998-11-01), Tarolli et al.
patent: 0 250 868 (1988-01-01), None
patent: 0 522877 A2 (1993-01-01), None
patent: 61-077984 (1986-04-01), None
patent: 64-73477 (1989-03-01), None
patent: 01130289 (1989-05-01), None
patent: 5-314271 (1993-11-01), None
patent: 06162212 (1994-06-01), None
patent: 7-056557 A (1995-03-01), None
patent: 8-096149 A (1996-04-01), None
patent: 8-096148 A (1996-04-01), None
patent: 8-305865 A (1996-11-01), None
patent: 377705 (2001-01-01), None
IBM Technical Disclosure Bulletin, vol. 33, No. 8, “Fast and Efficient Perimeter Drawing of Filled Polygons in a Graphics System”, Jan. 1991, pp. 454-460.

Affiliated with

Also associated with

Rating

Figure filling apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Figure filling apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Figure filling apparatus will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2524430