AU765342B2 - Fill table optimisation for high speed colour rendering - Google Patents

Description

S&F Ref: 536200

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

Name and Address of Applicant: Actual Inventor(s): Address for Service: Invention Title: Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome, Ohta-ku Tokyo 146 Japan Giles Puckett and Alan Tonisson Spruson Ferguson St Martins Tower,Level 31 Market Street Sydney NSW 2000 Fill Table Optimisation for High Speed Colour Rendering ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) AU PQ5556 The following statement is a full description of this invention, performing it known to me/us:- [32] Application Date 11 Feb 2000 including the best method of ,,nt! ~Th

W~\

Ae 5815c XCl~iU(~ii -1- FILL TABLE OPTIMISATION FOR HIGH SPEED COLOUR RENDERING Field of the Invention The present invention relates to high-speed colour rendering performed by special-purpose hardware and, in particular, to the optimal formation and composition of data tables to be loaded onto such hardware to enable such rendering.

Background High-speed printing systems must generate pixel data for a downstream printing device, either in real-time (non-stop) or within tight performance constraints. The input data for this rendering operation typically comprises a variable number of objects placed on the page at random. Traditionally, such placement has been performed by a computer system and process including a memory buffer holding the colour values for every pixel on the page, and a program which converts the incoming objects into colour values therein. As printing technology has advanced, the resolution and page size have each increased, resulting in a rapid increase in the required size, and hence the cost, of this i memory buffer. To reduce this cost, the page may be broken into bands, and the objects sorted in the vertical direction so that only those objects intersecting a given band need be rendered to produce output for that band. This approach has the disadvantage that some objects will inevitably cross multiple bands and hence, must be rendered more than once.

The extreme example of this case is a scanline rendering system, which has a band size of one scanline. These rendering systems dispense with the memory holding pixel data altogether, instead generating pixels from a sorted, optimised object description. Such a process is widely known as rasterisation.

Special-purpose hardware may be built which accelerates certain aspects of the process of pixel generation. Often this hardware facilitates elastic buffering of pixel data, the generation of runs of pixels of constant colour, and the decompression of compressed 536200.doc image data. In order to minimise cost and maximise speed, the hardware system must allocate scarce resources efficiently. The related art in this area is concerned with the allocation and re-use of scarce resources either spatially or temporally, such as the colouring of maps and the allocation of registers in the instruction streams generated by computer language compilers.

High-speed rendering hardware often produces a rendered output one scanline at a time from a description of objects on the page being rendered. Fig. 1 depicts a hardware rendering arrangement formed by a list of edges 101 describing the shapes of the objects, a level table 102 containing a list of objects, in priority or level order, also known in the art as Z-order, a fill table 103 containing descriptions of the objects as to colour and image contents, and a priority encoder 104 which identifies, typically in real-time, the topmost level in the level table 102 that contributes to a specific output pixel value on the scanline being rendered. Such an arrangement permits implementation of the well known i 0 Painter's Algorithm for object visibility determination. Scanlines are generated from the V 15 top of the page downwards as shown in Fig. 2 to form a page image 200. There is a many-to-one relationship among the tables 102 and 103 such that one edge 101 can point S•to many levels in the table 102, corresponding to many different objects being "switched on" when a scanline crosses the edge and enters the interior of a filled object. Further, many levels in the table 102 can also point to one fill in the table 103, corresponding to many different objects having the same colour, such as the characters of a line of text.

S" As rendering progresses, the scanlines move down the page and new edges are encountered. The corresponding levels are made active, which results in the fill colour or image data from the fill table 103, identified by the new topmost level in the level table 102, being made available to produce an output. Such transitions are labelled in Fig. 2 by the identifiers 201 to 208 with respect to objects that collectively form a page 536200.doc -3image 200, where any one object begins or ends in the vertical direction. Only active levels (those objects whose edges have been crossed) are considered by the priority encoder 104, so the topmost object at any given point on the page contributes to the colour at that point. In some arrangements, multiple levels may contribute to the colour at a point due to binary raster operations and opacity compositing.

To make such hardware feasible, there exist severe constraints on the size of the level and fill tables. In some hardware implementations, there are 4096 entries in the level table 102 and a similar number in the fill table 103. Increasing the size of these tables in hardware implementations not only consumes more silicon for the memory itself but also increases the gate count of the supporting logic, such as that required by the priority encoder 104. It will be apparent that many pages displayed or printed will exceed the capacity of these tables if levels are assigned to objects in a naive manner.

Summary of the Invention SIn accordance with one aspect of the present invention there is disclosed a 15 mechanism for the assignment of level and fill table entries to allow a much larger range of pages to be rendered in one pass of the hardware than would otherwise be the case.

In one specific implementation, a relatively quick determination is performed as to whether a new object can use existing entries in the level and fill tables rather than having new entries assigned. In another implementation, the levels and fills are re- 0 0 ordered or optimised when either table becomes full, to allow a greater degree of sharing between the tables, and hence more objects on the page.

In accordance with one aspect of the present invention there is disclosed a method of determining a shared display level in a graphical object rendering system arranged for rendering a page image formed by a plurality of graphic objects, in which 536200.doc S a -4object display levels are tabulated in Z-order for determination of a highest active displayable object, said method comprising the steps of: examining edges of said objects to determine those ones of said objects that overlap in said page image; (ii) for each said object, using overlap information obtained in step and a corresponding fill value for said object to determine whether said object is to be assigned to an existing level or to a new level.

In accordance with another aspect of the present invention there is disclosed a method of forming a level table of graphical objects in a graphical object rendering system arranged for rendering a page image formed by said graphic objects, in which object display levels are tabulated in Z-order for determination of a highest active displayable object, said method comprising the steps of: receiving a display list incorporating said objects sequentially arranged in said Zorder; 15 inserting a first one of said objects into said level table; o* sequentially processing each remaining object in said list by: examining edges of a current said object and objects within said table to determine those ones of said table objects that overlap in said current object within said page image; and oo (ii) using overlap information obtained in step and a corresponding Ole fill value for said current object to determine whether said current object is to be assigned to an existing level or to a new level within said table.

In accordance with another aspect of the present invention there is disclosed a method of optimising level allocation within a level table comprising entries arranged in Z-order and representative of plural graphical objects to be rendered to form a page 536200.doc

I

image, each said object having a corresponding fill value, said method comprising the steps of: identifying, for each said object, deemed a parent object, other ones of said objects that overlap and lie above said object, said other objects being deemed successors of said object; and assigning said successor objects to a different level to that of the corresponding parent object wherein if any two overlapping objects appear at the same level, creating a new level and assigning one of said overlapping objects to said new level according to said Z-order.

In accordance with another aspect of the present invention there is disclosed a method of optimising level allocation within a level table comprising entries arranged in Z-order and representative of plural graphical objects to be rendered to form a page image, each said object having a corresponding fill value, said method comprising the step of: forming a directed acyclic graph wherein nodes of said directed acyclic graph represent said objects and any two objects are adjacent in said directed acyclic graph if they overlap wherein the order in said directed acyclic graph is determined by the Z-order of said objects; and (ii) processing said directed acyclic graph to represent optimised levels for said ooo* level table.

Brief Description of the Drawings Embodiments of the present invention will now be described with reference to the drawings in which: Fig. 1 is a schematic block diagram representation of a rendering (rasterisation) arrangement in which embodiments may be performed: 536200.doc a e I I -6- Fig. 2 shows the appearance of a typical page rendered by the arrangement of Fig. 1; Fig. 3 shows the appearance of a page containing objects to be rendered, illustrating the sharing of levels according to an embodiment; Figs. 4A to 4C show the operation of a level table compaction algorithm upon the objects in a page image; Fig. 5 is a flowchart representing the processing procedure in accordance with the preferred embodiment; Fig. 6 is a flowchart respresenting the method of assigning indices in the level table based on whether objects overlap or not in the vertical direction, in accordance with the preferred embodiment; Fig. 7 is a flowchart representing the method of assigning successors of a level according to the depth of the level, in accordance with the preferred embodiment; and Fig. 8 is a schematic block diagram of a general purpose computer upon which oo 15 arrangements described can be practiced.

oo Detailed Description S-The preferred embodiments described herein relate to the creation and/or optimisation of the level table and/or the fill table, such steps pre-empting the actual rendering process, such involving visibility determination and the generation of output pixel values. The creation of such tables typically arises from an object display list that represents an input to a computer graphics system, with which a page image described by the display list is to be rendered. Graphic objects from the display list are conventionally provided in Z-order and traditionally the level table and fill table are formed on an objectby-object basis in Z-order, as each object is received. If objects are not received in 536200.doc a~ -7- Z-order, they may be insertion sorted into the respective tables or using temporary tables as required.

Having regard to the placement and extent of a new object in a page image according to the described embodiments, an existing level and/or fill entry may be re-used in preference to a new entry being allocated. If two objects have the same solid colour, such as the two black objects of Fig. 2, then the objects may share the same fill entry. If the objects do not overlap indirectly via other objects, then the objects may also share the same level entry. However, an exhaustive test for indirect overlap may be very slow, and must be performed for each incoming object. In a specific embodiment, such an exhaustive test is only performed when the level table 102 becomes full. In other embodiments, such may occur when the fill table 103 becomes full, thereby saving much effort for simple page images. Typically however, no fill table is independently compacted. In the page image 200 of Fig. 2 there are four objects, but only three fills, •since two objects are of the same colour and can thus use the same fill. In practice, most 15 pages will have many more levels than fills, because there are usually many objects, such S•as text characters, having the same colour, and most pages contain many more distinct objects than they do distinct colours or images.

According to one embodiment, when a new object is received from the display list, a fast test is first performed to determine if candidate fills and levels exist for sharing with objects already represented in the tables 102 and 103. The fill table 103 may be searched for a match using a technique such as a hash table. The level table 102 is however treated with more caution when searching for matches. Consider the page image 300 shown in Fig. 3 in which objects are received for rendering from a corresponding page description, in the order indicated by their corresponding reference numbers 301- 304. This order is consistent with the well-known Painter's Algorithm for graphics object 536200.doc h'~ -8rendering. Black object 303 does not overlap the other black object 301 directly, but still cannot share the same level with the black object 301 because to do so would place the black object 303 beneath red object 302, altering the appearance of the page 300.

However, black object 304 has no such restrictions and can share a level with either one of the black objects 301 or 303. Each of black objects 301, 303 and 304 can share a single black fill.

Taking the situation of Fig. 3 to a more complex case, it will be appreciated that the search for indirect overlap will take substantial time per object unless it is terminated early. In practice, the present inventors determined that for a 4096 level system, it is preferable for 5 to 10 levels to be searched down from the top of the level table 102 (corresponding to the topmost 5 to 10 objects on the page so far). In many cases, such as successive text characters, the topmost level is in fact the level that is chosen. A pseudocode representation of the preferred processing procedure is given below, this corresponding to the flowchart of Fig. 5, where reference numbers in the pseudocode 15 correspond to those in Fig. 6. .g PseudoCode #1 (500) FOR each level in the level table, starting at top (502) ~IF the proposed object overlaps the current level (504) Remember this fact and stop and the end of the loop. (506) IF the colour of the proposed object is the same as that of the current level .(508) STOP, reuse the current level. (510) IF there was an overlap (512) STOP, a new level must be assigned. (514) REPEAT until a predetermined number (eg. 5-10 out of say 4096) of levels 536200.doc -9have been checked. (516,518) STOP, a new level must be assigned. (514) The processing of PseudoCode #1 is not limited to page images formed of graphical objects defined by simple solid colours. Any or each of the fills may be blended colours, pixel-based images, or tiled images. In practice, re-use is more common with solid colours and hence such is used to illustrate the operation of the described embodiment without limiting the scope of the present invention.

When a page is sufficiently complex, the foregoing approaches may not be adequate to ensure that the level table 102 and the fill table 103 do not become full. As stated above, the level table 102 is usually the table that first becomes full. When the level table 102 becomes full, each object on the page has been assigned a level from the bottom-up based on order of arrival (apart from sharing due to the simple algorithm 0 Ir described above). This means that there may be many non-overlapping objects that could 6:006 share entries in the level table 102, provided that the overall layout of objects on the page .9 is considered. Fig. 4A shows a page image 401 that illustrates the process which, like Fig. 3, has objects labelled according to their corresponding Painter's Algorithm arrival *:*order from the corresponding page description.

The following pseudocode assigns indices in the level table 102 based on **dS whether objects overlap or not in the vertical direction, this also being illustrated in the flowchart of Fig. 6. Again, reference numbers refer to corresponding steps.

PseudoCode #2 (600) Form a list (edge_list) of all top and bottom edges of the bounding boxes of all objects currently in the level table. (602) Sort edge_list in order of scanline number. (604) 536200.doc 2a DBOi~iP~ PP~ ~.-ii Initialise a list (active_list) of active levels to be empty. (606) FOR each edge in sorted edge_list, starting at top of page (608, 626) IF the edge is a top edge (ie. object is being entered) (610)

THEN

FOR each level (Lv) in active_list (612) IF level of edge lies above Lv (ie. it was added later) (614)

THEN

Mark level of edge as a successor of Lv. (616)

ELSE

Mark Lv as a successor of level of edge. (618)

ENDIF

ENDFOR

Insert level of edge into the active list. (622) 15 ELSE (the object is being exited) Remove level of edge from the active list. (614)

ENDIF

ENDFOR (628) At this point, each level in the list 402 has a list of successors 403 which may be expressed as a directed acyclic graph 404 where each object forms a node of the graph 404 and links within the graph 404 define the overlapping relationship between the objects. The graph 404 may be formed by forming a list of top and bottom edges of each object in the page image 401. From Fig. 4A, such a list can be determined as: top 5, top 1, bottom 5, top 4, top 3, bottom 1, bottom 3, top 2, bottom 4, bottom 2.

The list is then traversed to identify a top edge that makes an object active, and this is used to create a corresponding node of the graph 404. When a new node is created, 536200.doc _1 11 that new node is linked to all currently active nodes with the link direction being determined by the Z-order. The activity of a node is disabled by a corresponding bottom edge. Where a node has no predecessor, such is a leaf node of the graph 404, and is indicative of the lowest object in Z-order for any intersecting group of objects on the page.

Once the structure of the graph 404 is formed, the next phase assigns the successors of a level according to the depth of the level in the graph 404. This can be performed in one pass since the successors of a level were higher in the original ordering of the levels than their parents, and so will not have to be visited more than once. Such is expressed in the pseudocode below, corresponding to the flowchart of Fig. 7. Again reference numerals are used to indicate the correspondence of processing steps.

PseudoCode #3 (700) Clear the existing level numbers to zero. (702) 15 Set variable level_index to zero. (704) FOR each level (in original Z-order) (706) IF there are any successors (708)

THEN

Set level_index to the level number of level. (710) 20 Increment level_index. (712) ~FOR all successors (Lv) of level (714,720) IF index of Lv already greater then level_index (716) SKIP this successor Set index of Lv to level_index. (718)

ENDFOR

ENDIF

ENDFOR

536200.doc -12- Similar processing is also preferably applied where necessary to the fill table 103. Since the entries in the level table 102 refer to entries in the fill table 103, it is appropriate for the fill table 103 to be compacted first, and the new indices in the compacted fill table (103) taken into account. In a preferred implementation, fills must be explicitly re-loaded if they are re-used, and fills of different types (eg. colours vs. images) cannot share a fill table entry. These limitations are of detail only and do not change the fundamental operation of the described embodiments.

The embodiments described relate to processes which are preferably performed by software in special rendering hardware, such as an application specific integrated circuit (ASIC) developed for the rasterised rendering of graphical object data.

Alternatively, such may be performed as a post-processing of the display list prior to input to the rendering hardware, the output of such post processing being a modified display list in which levels and fills are already optimised. Such a post processing 15 method is preferably practiced using a general-purpose computer system 800, such as that shown in Fig. 8 wherein the processes of Figs. 5 to 7 may be implemented as software, such as an application program executing within the computer system 800. In particular, the steps of method of Fig. 5 to 7 are effected by instructions in the software that are carried out by the computer. The software may be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer from the computer readable medium, and then executed by the computer. A i computer readable medium having such software or computer program recorded on it is a computer program product. The use of the computer program product in the computer preferably effects an advantageous apparatus for fill and/or level table optimisation for rendering.

536200.doc ii~rr~muua-u, eJy- rj -13- The computer system 800 comprises a computer module 801, input devices such as a keyboard 802 and mouse 803, output devices including a printer 815 and a display device 814. A Modulator-Demodulator (Modem) transceiver device 816 is used by the computer module 801 for communicating to and from a communications network 820, for example connectable via a telephone line 821 or other functional medium. The modem 816 can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN).

The computer module 801 typically includes at least one general purpose processor unit 805, a memory unit 806, for example formed from semiconductor random access memory (RAM) and read only memory (ROM), input/output interfaces including a video interface 807, and an 11 interface 813 for the keyboard 802 and mouse 803 and optionally a joystick (not illustrated), and an interface 808 for the modem 816. A storage device 809 is provided and typically includes a hard disk drive 810 and a floppy disk drive 811. A magnetic tape drive (not illustrated) may also be 15 used. A CD-ROM drive 812 is typically provided as a non-volatile source of data. The components 805 to 813 of the computer module 801, typically communicate via an interconnected bus 804 and in a manner which results in a conventional mode of operation of the computer system 800 known to those in the relevant art. Examples of computers on which the described arrangements can be practised include IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom.

Typically, the application program is resident on the hard disk drive 810 and read and controlled in its execution by the processor 805. Intermediate storage of the program and any data fetched from the network 820 may be accomplished using the semiconductor memory 806, possibly in concert with the hard disk drive 810. In some instances, the application program may be supplied to the user encoded on a CD-ROM or 536200.doc -14floppy disk and read via the corresponding drive 812 or 811, or alternatively may be read by the user from the network 820 via the modem device 816. Still further, the software can also be loaded into the computer system 800 from other computer readable media including magnetic tape, a ROM or integrated circuit, a magneto-optical disk, a radio or infra-red transmission channel between the computer module 801 and another device, a computer readable card such as a PCMCIA card, and the Intemrnet and Intranets including email transmissions and information recorded on websites and the like. The foregoing is merely exemplary of relevant computer readable media. Other computer readable media may alternately be used.

The post-processed display list may be provided to a vending processor 830 which performs a rendering of the page of objects.

Where fill/level table optimisation processing is performed in the special rendering hardware mentioned above, such may be performed in the rendering processor 830 when such is suitably configured.

15 The foregoing describes only some embodiments of the present invention and modifications may be made without departing from the scope of the present invention.

go go ooooo 536200.doc -II

Claims (5)

1. A method of determining a shared display level in a graphical object rendering system arranged for rendering a page image formed by a plurality of graphic objects, in which object display levels are tabulated in Z-order for determination of a highest active displayable object, said method comprising the steps of: examining edges of said objects to determine those ones of said objects that overlap in said page image; (ii) for each said object, using overlap information obtained in step and a corresponding fill value for said object to determine whether said object is to be assigned to an existing level or to a new level.

2. A method according to claim 1 wherein: if step determines that a current object does not overlap an existing object, 15 step (ii) determines whether the fill value of said current object corresponds to a fill value of said existing object and if so, the level of said one existing object is assigned to said current object and if not, step is repeated on a further existing object; and **if step determines that said current object does overlap said existing object, step (ii) determines whether the fill value of said current object corresponds to the fill value of said existing object and if so, the level of said existing object is assigned to said current object and if not, a new level is assigned to said current object. ell

3. A method according to claim 1 or 2 wherein said objects are received in Z-order and formed into a level table according to said Z-order and steps and (ii) are performed

536200.doc h~ nnnl~ 16- on each said object on receipt with respect to previously received objects represented in said level table.

4. A method according to claim 3 when dependent on claim 2 wherein step is repeated no more than a predetermined number of times whereupon a new level is assigned to said current object. A method according to anyone of claims 1 to 4 wherein said fill values are formed within a fill table and the assigning of said level table entries provides for multiple level table entries to point to a single fill table entry. 6. A method of forming a level table of graphical objects in a graphical object rendering system arranged for rendering a page image formed by said graphic objects, in which object display levels are tabulated in Z-order for determination of a highest active 15 displayable object, said method comprising the steps of: receiving a display list incorporating said objects sequentially arranged in said Z- order; inserting a first one of said objects into said level table; sequentially processing each remaining object in said list by: examining edges of a current said object and objects within said table to determine those ones of said table objects that overlap in said current object within said page image; and (ii) using overlap information obtained in step and a corresponding fill value for said current object to determine whether said current object is to be assigned to an existing level or to a new level within said table. 536200.doc ~D"~"L~*aartm$liana~-~~ii~ 17 7. A method of optimising level allocation within a level table comprising entries arranged in Z-order and representative of plural graphical objects to be rendered to form a page image, each said object having a corresponding fill value, said method comprising the steps of: identifying, for each said object, deemed a parent object, other ones of said objects that overlap and lie above said object, said other objects being deemed successors of said object; and assigning said successor objects to a different level to that of the corresponding i0 parent object wherein if any two overlapping objects appear at the same level, creating a new level and assigning one of said overlapping objects to said new level according to said Z-order. A method of optimising level allocation within a level table comprising entries 15 arranged in Z-order and representative of plural graphical objects to be rendered to form a page image, each said object having a corresponding fill value, said method comprising the steps of: forming a directed acyclic graph wherein nodes of said directed acyclic graph represent said objects and any two objects are adjacent in said directed acyclic 20 graph if they overlap wherein the order in said directed acyclic graph is determined by the Z-order of said objects; and (ii) processing said directed acyclic graph to represent optimised levels for said level table. 9. A method according to claim 8 wherein step comprises the sub-steps of: 536200.doc -18- sorting top and bottom edges of each said object forming said page image into a list; traversing said list and during said traversal: upon identifying a top edge that causes the corresponding said object to become active, creating a node in said directed acyclic graph; and linking said created node to all currently active nodes within said directed acyclic graph wherein a link direction corresponds to the Z-order relationship between said objects. 10. A method according to claim 8 or 9 wherein step (ii) comprises the sub-steps of: (ii-a) identifying all leaf nodes within said directed acyclic graph; (ii-b) assigning each said object represented by said leaf nodes to a current level in said level table; (ii-c) deleting said leaf nodes and corresponding links from said directed i- 15 acyclic graph and incrementing said current level; and 9* (ii-d) repeating steps (ii-a) to (ii-c) until all said nodes have been deleted. *o 0• *11. A method of optimising a fill table in a graphical object rendering system substantially as described herein with reference to the drawings. .i 12. Apparatus for performing the method of any one of the preceding claims. 13. A rendering processor comprising table means for forming a table in Z-order object display levels for graphical objects intended to form a page image, said table means comprising first means for examining edges of said objects to determine those ones 536200.doc '"liiII;--iii~'~ -19- of said objects that overlap in said page image, and second means for determining from said overlap objects and corresponding fill values whether said overlap object is to be assigned to an existing level or a new level in said table. DATED this Fifth Day of February 2001 Canon Kabushiki Kaisha Patent Attorneys for the Applicant SPRUSON FERGUSON ".:gO 0* S* e 9 0 *0 Og CS *fee S 0 C Go. ft e«g.

5* 0 0* 0 S. 536200.doc S~ t~t.~an~ rnr;