Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
1999-12-07
2002-10-15
Razavi, Michael (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
Reexamination Certificate
active
06466229
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a graphics processing apparatus for drawing graphics, text expressed in outline data, or the like in order to output the data to a printer, a display apparatus, or the like.
2. Description of the Related Art
In an editor, a CAD/CAM system, or the like which uses graphics or text expressed by outline data, in order to output the graphics or text to a printer or a display apparatus, a process of drawing the graphics is executed. The drawing process is performed by using, for example, blocks as shown in FIG.
2
.
In
FIG. 2
, when a command of drawing the graphics or text is inputted by the-user or from the outside, the command is interpreted by a command interpretation unit
1
and is supplied to a vector data generation unit
2
. In the case of the text, the vector data generation unit
2
sends a request to a font management unit
3
and acquires vector data expressing the outline of the text. A stroke (line) figure is converted to vector data, for example, as shown in
FIG. 3
on the basis of the thickness and the shape of a connecting part. The text, stroke figure, or filled (painted) graphics converted as mentioned above is inputted to a display list generation unit
4
.
The display list generation unit
4
first approximates a curved part expressed by a Bezier curve, spline, or the like to short straight lines and converts it into vector data of a polygon as shown in FIG.
4
. Then, the display list generation unit
4
converts the vector data into an expression in a display list form as shown in FIG.
7
. As an example of data regarding the vectors constructing a polygon, the display list has four pieces of element data of Dir: a direction flag (+1 in the case of upward orientation and −1 in the case of downward) Xs: X coordinate of the vector start point, Ye: Y coordinate of the vector end point, and Dx: a change amount (gradient) of X with respect to increase of +1 in the Y coordinate. The conversion from the polygon to the display list will be further described in detail hereinafter.
The display list data generated as described above is supplied to a display list drawing unit
13
. The display list drawing unit
13
calculates the coordinates of an intersecting point of each of the sides in the inputted display list and each scan line of an output device by a method of a DDA (Digital Differential Analyzer) or the like, sorts the data on the basis of the X coordinate values every scan line, obtains the correspondence between the start point and end point of a fill part, and draws a line segment parallel to the scan line corresponding to the interval on a memory unit
14
. The memory data drawn as mentioned above is transferred to an output device
15
such as a printer or display apparatus, thereby performing printing or display.
In such a graphics drawing process, the operation of the display list drawing unit
13
is “heavy” since DDA, sorting, drawing on the memory, and the like of each side are included. Especially, in the case of drawing complicated graphics including overlaps such as gradation, overwriting occurs many times in the same memory area and it is a main factor of deterioration in processing speed as a whole. Further, like a printer of recent years, in the case of reducing a page memory by accumulating a drawing command at the level of a polygon, a display list, an edge list, or the like and outputting the data while forming an image in a real time manner in accordance with the printing speed of the printer, there is a problem (hereinbelow, also called a first problem) such that an image formation is not performed in time in a complicated part where there are many overlaps and a picture dropout may occur.
Since the operation of the display list drawing unit
13
is heavy, a high-speed process is intended by dedicated hardware. Although the process is relatively simple in the case of a polygon having projected parts as shown in
FIG. 5A
, in the case where recessed parts are included as shown in
FIG. 5B
or in the case where the intersections of sides as illustrated in
FIG. 5C
are included, plural pairs of the start and end points exist in each scan line. Consequently, a process of sorting the intersections obtained as mentioned above and finding the correspondence is necessary. In the case where there is no restriction in the complication of the graphics inputted, however, the number of intersections is not limited, so that a problem (hereinbelow, also called a second problem) such that it is very difficult to construct a sorting circuit by hardware arises.
As an attempt of solving the first problem, a method of increasing the speed of the process and performing a real-time drawing by eliminating overlapped parts from the drawing elements has been conventionally proposed. Japanese Published Unexamined Patent Application Nos. Hei 8-279050, Hei 9-62851, Hei 9-171563, Hei 9-281953, and the like are conventional arts based on the idea.
As an attempt of solving the second problem, there is a method of dividing a polygon into figures such as trapezoids (including square and triangle) each having the bottom side parallel to the X axis in which no sorting occurs and processing each of the figures. Japanese Published Unexamined Patent Application Nos. Sho 60-74086, Sho 61-248176, Sho 62-271186, and the like are conventional arts based on the idea.
According to the methods of the Japanese Published Unexamined Patent Application Nos. Hei 8-279050 and Hei 9-62851, the drawing element is stored in the form of the edge list, and when the edge information of drawing for the same scan line is compared with each other and there is an overlap, the overlap is removed. The data amount of the drawing elements to be stored in the edge list is enormous when the resolution is high as in the printer of recent years, so that there is a drawback such that the cost of the memory increases.
According to the methods of Japanese Published Unexamined Patent Application Nos. Hei 9-171563 and Hei 9-281953, the drawing element is stored in the form of polygon data and an overlap of two polygons is checked. When there is an overlap, it is removed. In order to remove the overlap at the polygon level, however, the polygon has to have simple projected parts. For a polygon including a recessed part and an intersection of sides, a preliminary process of dividing the polygon into figures having projections is necessary. Although the object is narrowed down by the overlap determination, overlay graph, or the like, since a method of basically removing an overlap of two polygons is used, processes of N! (factorial of N) times are necessary to completely remove the overlaps of N process targets.
SUMMARY OF THE INVENTION
The present invention has been achieved in consideration of the problems of the conventional arts as mentioned above. The present invention provides a high speed graphics processing apparatus having an overlap removal part for removing an overlap of drawing elements expressed in a display list format, capable of storing data in a small memory amount even when the resolution is higher as compared with an edge list and removing an overlap by a small amount of process without performing a special preliminarily process.
In the Japanese Published Unexamined Patent Application Nos. Sho 60-74086 and Sho 61-248176, a polygon is divided into trapezoids (including square and triangle) each having the bottom side parallel to the X axis and the trapezoids are sequentially processed, thereby making a sorting circuit at the time of a filling process unnecessary. According to the method, however, since a number of trapezoids are generated when a complicated polygon is divided, it is difficult to control or temporarily store the trapezoids and there is also a problem that the processing speed is low since the process is performed every trapezoid.
In the Japanese Published Unexamined Patent Application No. Sho 62-271186, an inputted figure including a curve is divided into partial figures s
Fuji 'Xerox Co., Ltd.
Oliff & Berridg,e PLC
Razavi Michael
Yang Ryan
LandOfFree
Graphics processing apparatus and graphics processing method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Graphics processing apparatus and graphics processing method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graphics processing apparatus and graphics processing method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2940659