Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
2000-01-05
2003-01-07
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
C345S467000, C345S469100, C345S470000
Reexamination Certificate
active
06504543
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a polygon drawing method and a polygon drawing apparatus and, more particularly, to those for drawing a polygon which is colored inside its outline, by using data indicating the outline of the polygon.
BACKGROUND OF THE INVENTION
When outputting characters to a printer or the like, the bit map font in which each character is represented as an array of dots has the advantage of rapidly displaying the characters on a screen and, therefore, this font has generally been used in computer systems and the like. In the bit map font, however, since the number of dots constituting each character is determined, the dots increase in size as the character is scaled up, and the stepwise notches called “jaggy” become conspicuous. As a result, the outline font has spread in recent years. In the outline font, each character is treated as a polygon and represented as the outline of the polygon. The outline font comprises coordinates of representative points specifying the polygon as the formula of the character, and data indicating curves or straight lines for connecting the representative points with each other. By using the outline font, even when a large character is printed, a beautiful print having no jaggy is obtained and, moreover, a character of an arbitrary size can be printed. The outline font has spread as being mounted on printers and word processors, and recently it is increasingly used for screen display of personal computers and the like.
When processing a character or the like by using the outline font, the procedure is as follows. The coordinates of plural points (representative points) specifying a polygon constituting a character are stored as data. When printing or displaying the character, the outline of the polygon constituting the character is calculated through the representative points, and the inside of the outline is painted. Accordingly, when printing characters of different sizes, it is possible to use a font which is scaled up or down by calculation based on the fundamental font. Therefore, the outline font is advantageous over the dot font like the bitmap font in that it doesn't need to have different font data for different sizes of characters.
There are two typical methods for painting the inside of the outline, “scan conversion” and “seed painting”. In the scan conversion method, with respect to the edges of a given polygon, intersections of each horizontal scanning line with the edges of the polygon are detected, and the space between the intersections is colored (refer to 3D computer graphics, written by Nakamae, published by Shoko-do, pp.117-120).
On the other hand, the seed painting method is as follows. Initially, one unit (one pixel) specified as the starting point (seed) of painting inside the outline is painted, and a pixel to be painted next is detected from pixels surrounding the seed pixel (starting point), and thereafter, the same process as above is repeated with the detected pixel as a new seed. The painting is completed when there are no more pixels to be a new seed (refer to Japanese Published Patent Applications Nos. Sho.62-83790 and Sho.62-192878).
Japanese Published Patent Applications Nos. Hei.1-296389 and Hei.3-116288 disclose improved methods based on the typical painting methods described above. In these methods, data indicating the outline of a character or the like (hereinafter referred to as outline data) is stored in a control plane, and the dots inside the outline are colored on the basis of the data.
To be specific, the method disclosed in Japanese Published Patent Application No. Hei.1-296389 is aimed at avoiding the difficulty in determining a starting point in the seed painting method, which difficulty will be described later. In this method, when storing the outline data in the control plane, a segment or a curve corresponding to the outline data is generated to be stored. Then, it is decided whether the generated segment (or curve) is positioned on the left side of the horizontal scanning line (in this case, the count value of the segment is odd) or on the right side of the scanning line (in this case, the count value of the segment is even), and control data indicating the result of this decision is generated, and painting is performed according to the control data while scanning in the horizontal direction, whereby the process of determining the starting point is dispensed with.
Further, the method disclosed in Japanese Published Patent Application No. Hei.3-116288 is aimed at reducing the processing load, as compared with the above-described painting methods. In this method, painting start data is subtracted from painting end data to obtain painting data which specifies painting. Thereby, the processing is simplified and the processing load is reduced.
Further, there is still another painting method disclosed in the specification of HD64412 by Hitachi. According to this method, painting data is generated by performing an EXOR (Exclusive OR) operation on a control plane from a reference line (left end) on the basis of outline data, and the dots inside the outline are colored on the basis of the painting data so generated, thereby simplifying the painting process.
By the way, also in the field of car navigation system which has been remarkably developed in recent years, high-quality characters can be displayed by using the outline font described above. Further, in the car navigation system, when displaying a graphic such as map information, buildings and natures (river, pond, etc.) are handled as polygons, and painting is performed on the basis of data indicating the outlines of the polygons in the same manner as described for the outline font, thereby displaying the map information according to various kinds of contraction scales. FIGS.
10
(
a
)-
10
(
d
) are diagrams for explaining the polygon processing in the display of the car navigation system. FIG.
10
(
a
) shows outline data for displaying a character “A”, and FIG.
10
(
b
) shows the character obtained by painting the inside of the outline data. Like the character, the graphic shown in FIG.
10
(
d
) is obtained on the basis of outline data of the graphic shown in FIG.
10
(
c
).
In the conventional polygon drawing method so constructed, it is not necessary to prepare a font or a graphic pattern for each character size, and a character or a graphic with smooth outline can be displayed even when it is scaled up.
However, in the above-described scan conversion method, since the processing load due to sorting of coordinate data constituting the edges is considerable, the processing time is decided not by the size of the graphic but by the number of the edges. Therefore, when processing a character constituted by many edges, the processing takes time even if the character is a relatively small graphic. Further, since curves cannot be used in the outline, it is necessary to approximate straight lines to curves. So, in order to represent a high-quality character or the like, a lot of straight lines are needed, and the number of the edges increases significantly, resulting in an increase in processing time.
On the other hand, the problem of the seed painting method resides in the difficulty in determining a seed pixel to be a starting point. That is, in the seed painting algorithm, a graphic representing one character is handled as one polygon, and this is one continuous region. So, one graphic (character or the like) can be processed with one seed pixel determined. However, if the graphic (character or the like) has a constricted part, the continuous region is sometimes divided into plural regions when the graphic is scaled down. In the seed painting method, when there are plural regions each being surrounded by an outline, plural seed pixels must be specified. So, in order to avoid that a small region separated from one region remains unpainted, plural seed pixels must be specified. Accordingly, in this case, the character cannot be processed according to the relatively simple algorithm in which one seed pixel
Okamoto Tadashi
Shigenaga Satoshi
Havan Thu-Thao
Luu Matthew
Wenderoth , Lind & Ponack, L.L.P.
LandOfFree
Polygon drawing method and polygon drawing 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 Polygon drawing method and polygon drawing apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polygon drawing method and polygon drawing apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3021860