Rendering page descriptions

In rendering a page description on a rendering system, a method comprises the step of receiving objects and generating one or more sets of render instructions. For each received object it is first determined whether by adding the corresponding render instructions of a current received object to a current set of render instructions the resources of the rendering system will be exceeded. If the resources would be exceeded then a new set of render instructions are created, render instructions are added thereto to draw the current set of render instructions as a background image, and then the corresponding render instructions of the current received object are added to the new set. On the other hand, if the resources would not be exceeded then the corresponding render instructions of the current received object are added to the current set. Finally, the method renders the one or more sets of rendering instructions.

TECHNICAL FIELD OF THE INVENTION

The present invention relates to a method and system for rendering a page description. The invention also relates to a computer readable medium comprising a computer program for rendering a page description.

BACKGROUND

In relatively recent years, graphics packages have existed for rendering printed pages to printers, display screens, and/or other locations (eg. files). A number of these graphics packages typically utilise a high-level page description language for assisting in the layout of the printed pages. These graphics packages typically comprise a rendering system, which converts the high level page description of the page layout into pixels data that can be used as raster data to be printed and/or displayed.

One such rendering system comprises a full-page frame store to hold a pixel-based image of the page or screen. The full-page frame store is a buffer that has room for every pixel that needs to be sent to the printer for a whole page. In these systems, every object that is received in the high-level page description can be rendered immediately. The main problem with this system is the memory that is required for the frame store is very large, especially when each pixel is required to be continuous-tone colour, and may have an associated transparency value.

There exist rendering systems, which perform more efficiently in both speed and memory usage when applied to the render list as a whole rather than to objects sequentially in z-order. Such systems are highly advantageous when the storage required for the render-list is within available resources, but break down if more resources are required. For instance, the size of an object render-list is unbounded, whereas the size of a frame store, although large, is limited and is strictly dependent on the resolution and size of the printed page. When such systems are used they either fail when presented with a render-list that exceeds available resources, or degrade to an object-sequential immediate rendering method using a frame store.

SUMMARY OF THE INVENTION

According to a first aspect of the invention, there is provided a method of rendering a page description on a rendering system, wherein said page description comprises one or more objects, the method comprising the steps of: receiving said objects sequentially in z-order from bottom to top; generating one or more sets of render instructions, wherein said generating step performs the following sub-steps for each received object: determining whether adding corresponding render instructions of a current said received object to a current set of render instructions will exceed the resources of the rendering system; and if the resources are exceeded performing the following sub-steps; creating a new set of render instructions; adding render instructions to the new set of render instructions to draw the current set of render instructions as a background image; and adding to the new set of render instructions the corresponding render instructions of said current received object; and if the resources are not exceeded performing the following sub-step: adding the corresponding render instructions of said current received object to the current set of instructions; and rendering said one or more sets of rendering instructions as pixel data.

According to a second aspect of the invention, there is provided a method of rendering a page description, wherein said page description comprises one or more objects, the method comprising the steps of: receiving said objects sequentially in z-order from bottom to top, wherein the method performs the following sub-steps for each said received object: testing if resources would be exceeded if the received object is added to a current render-list, and if it would, rendering said current render-list onto a frame store and then setting said current render-list to be empty; adding the received object to said current render-list; and if the received object is the last object in the z-order then: if said frame-store was rendered onto, rendering said current render-list in combination with said frame-store to form the rendered page description, else rendering said current render-list to form the rendered page description.

According to a third aspect of the invention, there is provided a system for rendering a page description, wherein said page description comprises one or more objects, the system comprising: means for receiving said objects sequentially in z-order from bottom to top; means for generating one or more sets of render instructions, wherein said generating means comprises: means for determining, for each received said object, whether adding corresponding render instructions of a current said received object to a current set of render instructions will exceed the resources of the rendering system; means for creating, if the resources are exceeded, a new set of render instructions; means for adding, if the resources are exceeded, render instructions to the new set of render instructions to draw the current set of render instructions as a background image; means for adding, if the resources are exceeded, to the new set of render instructions the corresponding render instructions of said current received object; means for adding, if the resources are not exceeded, the corresponding render instructions of said current received object to the current set of instructions; and means for rendering said one or more sets of rendering instructions as pixel data.

According to a fourth aspect of the invention, there is provided a system for rendering a page description, wherein said page description comprises one or more objects, the system comprising: means for receiving said objects sequentially in z-order from bottom to top; means for testing, for each received object, if resources would be exceeded if the received object is added to a current render-list, and if it would, rendering said current render-list onto a frame store and then setting said current render-list to be empty; means for adding the received object to said current render-list; means for rendering said current render-list in combination with said frame-store to form the rendered page description, if the received object is the last object in the z-order and said frame-store was rendered onto; and means for rendering said current render-list to form the rendered page description, if the received object is the last object in the z-order and said frame store was not rendered onto.

According to a fifth aspect of the invention, there is provided a computer readable medium comprising a computer program for rendering a page description, wherein said page description comprises one or more objects, the computer program comprising: code for receiving said objects sequentially in z-order from bottom to top; code for generating one or more sets of render instructions, wherein said generating code comprises: code for determining, for each received said object, whether adding corresponding render instructions of a current said received object to a current set of render instructions will exceed the resources of the rendering system; code for creating, if the resources are exceeded, a new set of render instructions; code for adding, if the resources are exceeded, render instructions to the new set of render instructions to draw the current set of render instructions as a background image; code for adding, if the resources are exceeded, to the new set of render instructions the corresponding render instructions of said current received object; code for adding, if the resources are not exceeded, the corresponding render instructions of said current received object to the current set of instructions; and code for rendering said one or more sets of rendering instructions as pixel data.

According to a sixth aspect of the invention, there is provided a computer readable medium comprising a computer program for rendering a page description, wherein said page description comprises one or more objects, the computer program comprising: code for receiving said objects sequentially in z-order from bottom to top; code for testing, for each received object, if resources would be exceeded if the received object is added to a current render-list, and if it would, rendering said current render-list onto a frame store and then setting said current render-list to be empty; code for adding the received object to said current render-list; code for rendering said current render-list in combination with said frame-store to form the rendered page description, if the received object is the last object in the z-order and said frame-store was rendered onto; and code for rendering said current render-list to form the rendered page description, if the received object is the last object in the z-order and said frame store was not rendered onto.

DETAILED DESCRIPTION INCLUDING BEST MODE

FIG. 1illustrates a computer system100configured for rendering and presentation of a high-level page description into pixels that is used as raster data to be printed. The computer system100comprises a host processor102associated with system random access memory (RAM)103, a font memory104, a render engine105, an output device106, and a printer engine107. The computer system100also comprises a rendering instruction generator software module109, a rendering instruction loader software module110, and a compressor software module111for operating on the host processor102. The rendering instruction generator software module109, rendering instruction loader software module110, and compressor software module111may alternatively be implemented in hardware and coupled to the bus system108or intercoupled with local buses (not shown). In addition, the render engine105can alternatively be implemented as a software module for operation on the host processor102. The RAM memory103is adapted to store an instruction queue112of one or more sets of render instructions generated by the rendering instruction generator software module109. The font memory104has stored therein font characters of one or more fonts for use by the rendering engine105. The render instruction generator109generates one or more sets of rendering instructions in response to the high-level page description and queues them on an instruction queue112in RAM memory103. The rendering instruction loader software module110takes one set at a time of these sets of instructions from the instruction queue112and loads it into the rendering engine105, which outputs these instructions as pixels to the output device106and printer engine107. The render engine105sometimes instead of rendering the set of instructions to the output device106renders the set of instructions as an image to the compressor software module111. The compressor software module111compresses this image and feeds it back to the instruction queue112in memory103for subsequent use by the render engine105.

The above mentioned hardware components of the computer system100are interconnected via a bus system108, and are operable in a normal operating mode of computer systems well known in the art, such as the IBM PC/AT type personal computers and arrangements evolved therefrom, Sun Sparcstations and the like. The components of the computer system100may also exist in separate computing environments. Preferably, these software modules may be stored on a computer readable medium, such as a floppy disk, optical disk, memory card or other suitable mediums.

In an alternative embodiment, the pixel data produced by the render engine105may be optionally sent directly to the instruction queue112and not be compressed. In another embodiment, the pixel data may be kept within the render engine105itself for subsequent use by the render engine105. Other embodiments are possible where there is no instruction queue or render instruction loader. In these cases, the render instruction generator109would synchronously load instructions into the render engine105. In yet another embodiment it is possible for the render instruction generator109to be situated in a separate computer, and connected via a network or some other kind of data link to the computer containing the instruction queue112and/or the render engine105. In addition, the computer system100preferably utilises flow control for the page description. That is, if the render list generator109cannot receive the page description data, the page description data will remain uncorrupted, with no loss of data, until the render list generator109is ready to receive it.

The high-level page description can be any known high-level page description language for describing the layout of a printed page, such as the POSTSCRIPT language, in the form of objects arranged in z-order.

Turning now toFIG. 1B, there is shown a block diagram showing the functional data flow of the computer system ofFIG. 1A. The host processor102receives a high-level page description120. Such a high-level page description120may be supplied by a graphics package operating on the host processor102, or from graphics application on some other host processor connected via a network with this one. The render instruction generator109then generates one or more sets of rendering instructions (122,124,126) in response to the high-level page description120, which is described in more detail below. These one or more sets of rendering instructions (122,124,126) are queued on an instruction queue112in memory103. The render instruction loader110then loads one at a time these one or more sets of rendering instructions (122,124,126) from the instruction queue112, which is described in more detail below. The render engine105then renders the one or more sets of rendering instructions, which is described in more detail below. The rendering engine105supplies output pixels (image) to the output device106and printer engine107. The rendering engine105in certain conditions instead of supplying the output pixels (image) to the output device106supplies them to the compressor111. The compressor111compresses this image128, which is fed back to the instruction queue112for subsequent use by the rendering engine105. The computer system100operates in a pipeline manner, with the render instruction generator110and rendering instruction loader capable of operating in a simultaneous and asynchronous manner.

Turning now toFIG. 1C, there is shown objects of an exemplary page description and corresponding converted objects for illustrating the operation of the computer system ofFIG. 1A. The render instruction generator109receives the objects (0,1,2,3,4,5,6, and7) of the page description one at a time in increasing z-order commencing at the lowermost object (0) (viz bottom to top). The render instruction generator109first generates an initial set of rendering instructions for the page description. This initial set of instructions typically contains any basic instructions necessary for the rendering of the page. The render instruction generator109then determines if a set of instructions containing the basic instructions and the rendering instructions corresponding to the lowermost object (0) will cause the resource limits of the computer system100to be exceeded. In this example, the render instruction generator109determines the resource limits are not exceeded for this set of instructions. The render instruction generator109then determines if a set of instructions containing the basic rendering instructions, the rendering instructions corresponding to the next lowermost object (1), and the rendering instructions corresponding to the lowermost object (0) will cause the resource limits of the computer system100to be exceeded. In this example, the render instruction generator109determines the resource limits are not exceeded for this set of instructions. The render instruction generator109continues adding instructions to the set until it determines that the resource limits will be exceeded by the set. In this example, the render instruction generator109determines that the resource limits will be first exceeded when the set of instructions contains the basic rendering instructions and the rendering instructions for the objects (0,1,2,3,4,5, and6). The render instruction generator109then supplies the set of instructions containing the basic rendering instructions and the rendering instructions for the objects (0,1,2,3,4, and5) to the render engine105preferably via an instruction queue112and an rendering instruction loader110.

The render instruction generator109then creates a new initial set of the basic instructions and first adds rendering instructions to draw a background image on the page corresponding to objects (0,1,2,3,4, and5), which is designated inFIG. 1Cas object0′. These rendering instructions do not contain the background image itself but contain a reference to the background image, which will be subsequently generated by the render engine. The rendering instruction generator109then proceeds to determine in the same manner as described above, whether adding rendering instructions corresponding to object6to the newly created set will cause the resource limits to be exceeded. In this example, the rendering instruction generator109determines that adding rendering instructions for both objects6and7to the newly created set will not cause the resource limits to be exceeded.

The render engine105at some later time generates pixel data in the form of a background image in response to the first set of rendering instructions (ie. corresponding to objects0,1,2,3,4, and5). The render engine105then-generates pixel data in response to the second set of rendering instructions (ie. corresponding to objects (0′,6, and7) and using the pixel data generated by the render engine105in response to the first set of rendering instructions for the background image, ie. object0′.

In this way, the preferred embodiment is able to create instructions, which produce a page in layers. Objects that have arrived first in the page description, and hence are lowest in z-order, are converted into instructions and then rendered into pixels as a layer. These pixels are used as a background image for the next layer. A complex page, or a page containing large objects, may be rendered onto the frame-store in several layers. A number of lower order objects of the page which utilise significant resources may be rendered as an image, which in turn can be used as a background image for further higher order objects of the page. This has the advantage that the background image object may utilise fewer resources than its corresponding number of objects. A page comprising a large number of objects, which would normally exceed the resource limits of the system, can be converted into layers and thus not exceed the resource limits.

FIG. 2Ais a block diagram illustrating one example of the queuing of multiple pages in accordance with the preferred embodiment. The mechanism of queuing and sharing of queue space resources allows multiple pages to be prepared and rendered separately in the preferred embodiment. In the preferred embodiment, the instruction queue112functions in a fixed or restricted amount of memory. In the preferred embodiment, sets of render instructions representing either a whole page, or a layer in z-order within the page, are queued in the instruction queue112. Alternatively, it is possible to continuously stream the instructions, with the render instruction loader110determining the breaks between pages or layers, and starting the render engine when a full page or layer has been loaded.

Preferably, a set of render instructions is completely prepared, then queued.FIG. 2Ashows an example of the appearance of the instruction queue112when every page could be rendered within the limits of render and system resources. In this example, each set of render instructions represents a whole page. These are queued in the order they are received from the page description, with Page1first, Page2second, Page3third and so on.

FIG. 2Bis a block diagram illustrating another example of the queuing of multiple pages in accordance with the preferred embodiment.FIG. 2Bshows an example of the appearance of the instruction queue112when one of the pages requires layering. Page1containing a large number of objects would exceed the resource limits of either the system or the render engine. Therefore, Page1is split into layers Page1a, Page1band Page1c. Page1ais the most obscured layer (lowermost) of the page. It does not need a background image, as its background is the paper. The rendered output of the Page1ainstructions goes to a reserved space113in memory103as the background image for Page1b. The reserved space113in memory103acts as a frame-store for the background image for Page1b. Then if Page1requires another layer, the same reserved space113in memory103for the background image can be used as a frame store for the background image for the next layer, Page1c. For the sake of clarity, the reserved space113in memory103for the background images for Pages1band1cis shown separately. The rendered output of Page1binstructions goes into the space113reserved for the background image of Page1b. This works because the rendered output of Page1bis a picture of the whole page drawn so far, from the bottom up. The background image produced by Page1ainstructions is part of this picture. So the background image produced by Page1aneed not be kept. Page1cuses the background image produced by Page1b, and produces the final picture of the page, which is directed to the printer. Page2is on the queue, and does not require layering.

FIG. 2Cis a block diagram illustrating the queuing of the pages inFIG. 2Bat a further stage in time. In particular, it shows an example of the appearance of the instruction queue112when two pages require layering, and both pages are simultaneously in the queue.FIG. 2Cis a time continuation ofFIG. 2B, where Pages1aand1bhave been de-queued. Page1cis still on the queue when the space in memory103is about to be reserved for the background image for Page3b. The same space113in memory103is reserved for the background image for Page3bas is reserved for background image for Page1c. For the sake of clarity, the reserved space113in memory103for the background images for pages1cand3bis shown separately. The output of Page3ais directed into this reserved space, and the background image for Page3bis read from this space.

The space reserved in the memory103for the background image varies in size for different pages. If, for example, a layer contains only black and white objects, the compressed pixel data representing that layer will take less space than a full colour layer compressed. So the space reserved for the background image is smaller for black and white or monotone layers. This makes sharing the space for the background image a little more difficult. If layers generated earlier are still in the queue, but the space previously reserved for the background image is insufficient, then the additional amount of space required for this layer is reserved and added onto the space kept for the background image. The original portion of reserved memory is still used, as well.

The implementation of the instruction queue in the preferred embodiment uses a dynamic memory allocator, which operates on the memory reserved for use by the background images. This dynamic memory allocator is thread-safe, to allow the render instruction generator to allocate memory in it, and to allow the render instruction loader, which operates asynchronously, to free the memory.

In the preferred embodiment, the reserved space in memory103for the background image is shared between all layers that need it. This is possible because the Render Instruction Loader110removes each layer from the queue as it loads it into the render engine105. The render instruction loader could de-queue pages out of order for duplexing etc. In the latter case, enough memory must be made available and out of order dequeuing must be accounted for in resource calculation.

However, with some other embodiments it may be necessary to keep the instructions on the queue. For example, the instructions could be kept until the page is known to have been printed without error. If there was a printing or paper error, the instructions can be re-loaded into the render engine, and the page can be printed again. One way of keeping a complete set of instructions to render each page is to discard all layers but the last one, and keep the background image associated with the last layer. In this type of system, the reserved space for the background image may be shared within a page, but the background image for each page will need its own separate reserved space, as there may be valid data in multiple background images at the same time. Another possible method is to render the last layer as background image for the page, and just keep the background image for the page. In general this saves space, but wastes time, unless the compressor can be run synchronously with the printer, and accept data at the same speed as the printer. Then the image used for paper error recovery can be generated with no loss of system speed. A background image still needs to be kept per layered page. An alternative mechanism is to keep all the render instruction data for all the layers of the page. Then the background image can be shared between all pages. But if the limit that caused a layer was the size of memory available for the render instruction queue, the layers must be freed to allow other jobs to print. A hybrid of all the above approaches is possible. Namely, a hybrid mechanism that minimises the memory saved for paper error recovery, while maximising the throughput speed.

FIGS. 3(a) and3(b) show a flow chart of the procedure for generating one or more sets of rendering instructions used by the render instruction generator ofFIG. 1A. The render instruction generator109is started300and initialised301for each single printed page. Initially, at step301, it creates a new set of current render instructions containing the basic render instructions that are always required for every page. The render instruction generator109receives and processes objects one by one from the page description. Next, at step302, it obtains the current usage of all render and system resources utilised by the set of current render instructions. The render instruction generator109then proceeds to step303, where it retrieves enough information about the next object in the page description to determine the object's complexity and size. The manner in which this is determined is further explained below with reference toFIG. 4(a) and4(b).

The render instruction generator109then proceeds to decision block304, where it queries whether adding the object's render instructions to the set of current render instructions would cause the resultant set of instructions to exceed the resource limits. In particular, it checks whether this resultant set of instructions would cause an overflow of the complexity limits or memory capacity of the render engine, or would cause the resultant set of instructions to use an excess of memory in the render instruction queue.

If decision block304returns false (NO), that is the limits are not exceeded, then render instruction generator proceeds to step312, where the rest of the object data is received, if necessary. The render instruction generator then proceeds to step313, which is described in more detail below.

On the other hand, if the decision block304true (YES), namely the limits are exceeded, then the render instruction generator109proceeds to step305. In step305, the current set of instructions (not the resultant set of instructions) is queued to the render instruction loader110via the instruction queue112as a layer of the page. In addition, instructions are added to the current set of instructions requesting that the resultant rendered page be put in the space in memory which will be reserved for the background image in the next set of instructions (not yet queued). The output pixel data generated by rendering this current layer of the page is directed to the space which will be reserved in the subsequent layer at step308or step309. The output pixel data may be compressed or degraded to make it fit in the available space. The size of the space reserved is determined by the compression ratio required for the background image pixel data.

After step305, the render instruction generator109proceeds to step306, where a new set of current render instructions is created. This new set of current render instructions contains initially the basic render instructions that are always required for every page.

After step306, the render instruction generator109proceeds to decision block307, where a check is made if there is space already reserved somewhere in the queue for the background image. If the decision block307returns TRUE (YES), then render instruction generator109increments the reference count associated with the reserved space (step308). The decision block307and step308are done indivisibly, to prevent the render instruction loader110from de-queuing the reserved space while the render instruction generator is trying to reference it. If decision block307returns FALSE (NO), that is no space already exists in the queue for the background image, then the render instruction generator109reserves space in memory and sets the reference count associated with the reserved space to 1 (step309).

The render instruction generator109then proceeds to step310. In step310, the render instruction generator109adds instructions to draw an image the size of the whole page (the background image) to the current render instructions, previously created during step306. The resultant current set of instructions will then be the basic instructions for rendering the page, and the instructions to draw the background image. The background image will be located at the reserved space by the time this set of instructions is ready to be loaded to the render engine107.

After step310, the render instruction generator109proceeds to step312. In the event decision block304returns FALSE (NO), the render instruction generator109also proceeds to step312. In step312, the render instruction generator109receives the rest of the incoming object, if necessary. This is explained in more detail below with reference toFIGS. 5(a) and (b). After step312, the render instruction generator109then converts the object into render instructions, which is an intermediate data form of the page description (step313) and then adds these converted render instructions to the set of current render instructions (step314). Where the resource limits have been exceeded (304), a new set of current instructions has been created. In this case, the current set (step314) is the newly new set of instructions. On the other hand, where the resource limits have not been exceeded (304), the current set (step314) is the existing set of instructions.

After step314, the render instruction generator109proceeds to decision block315. In decision block315, a check is made whether the current object is the last object on the page. If the decision block315returns TRUE (YES), the set of current render instructions are queued (step316) on the instruction queue112for subsequent loading by the render instruction loader110. Otherwise, if the decision block315returns FALSE (NO), the render instruction generator109returns to step302to receive the next object, where the process starts again for the next object.

In the preferred embodiment, objects passed to the system can be text characters or shapes or images. Characters and paths can be filled with flat colour, blended colour, image colour data (possibly tiled), or pattern colour data (also possibly tiled). Objects can also be used to define clip regions. The render engine105requires every object to be bound by edges. Therefore the render instruction generator109creates edges for all incoming objects, even if the incoming object did not have an explicit outline defined. The region filled by the object is always defined by the page description, either explicitly or implicitly. The render instruction generator109uses this definition to generate edges. So as every object generates edges, every object can be used as a clip. The render engine supports clips. Most clips use up only one level, and no colour slots.

Turning now toFIGS. 4(a) and4(b), there is shown a flow chart of the sub-steps of the step303for determining the object's size and complexity as shown inFIG. 3(a). During this process, the render instruction generator109receives part of the data for an object, which part being enough to determine the size and complexity of the object. After step302, the process proceeds to decision block420, where a check is made whether the current object is a character. If it is a character, the decision block420returns TRUE (YES) and the render instruction generator proceeds to decision block421. In decision block421, a check is made whether the character is already stored in the system in the font memory104. If the decision block421returns TRUE (YES), the render instruction generator109proceeds to step422, where the character's pre-calculated size and complexity is obtained. This is returned for subsequent use in decision block304. The render instruction generator109then proceeds to step429.

If the decision block421returns FALSE (NO), the render instruction generator109proceeds to decision block423, where a check is made whether the character is a bit map. If the decision block423returns TRUE (YES), the render instruction generator109proceeds to step424, where the size of the bit map (width and height) is read, but not the bit map data itself. After step424, the render instruction generator109proceeds to step425, where the render instruction generator109calculates a pessimistic estimate of the size of the edge data produced by the character, by assuming a 1-pixel checkerboard or similar. This is returned as the current object's size and complexity for subsequent use in decision block304. After step425, the render instruction generator109proceeds to step429.

If the decision block423returns FALSE (NO), namely the character was not a bit map, the render instruction generator109proceeds to step427.

If the decision block420returns FALSE (NO), namely the object is not a character, the render instruction generator109proceeds to decision block426, where a check is made whether the current object is a shape defined by path data. If the decision block426returns TRUE (YES), the render instruction generator proceeds to step427.

During step427, the render instruction generator109, reads the path data for the shape or character. Alternatively, the render instruction generator109can defer the reading of path data, and retrieve enough information from within the header for the path data to determine the size and complexity of the shape or character. This has not been implemented in the preferred embodiment because most existing page description languages do not contain this kind of header information. After step427, the render instruction generator109proceeds to step428, where it calculates a pessimistic estimate of the size of the edge data that would be produced by the path, using the number of points in the path and the bounding box of the path. This is returned as one aspect of the current object's size and complexity for subsequent use in decision block304. After step428, the render instruction generator109proceeds to step429.

If the decision block426returns FALSE (NO), the render instruction generator, proceeds to step430. If the current object is not a character or a shape, it must be an image. During step430, the render instruction generator109reads the header for the image, which defines the size of the image data (width and height), and the size of each pixel (step30). The header also contains the transform to be applied to the image. After step430, the render instruction generator109then proceeds to decision block431.

In decision block431, a check is made whether the image will fit uncompressed within the maximum memory allowed for an image in both the queue and the render engine. If the decision block431returns TRUE (YES), the render instruction generator109then calculates the amount of edge data which will be generated by transforming all four corner points of the image by the image transform. After step432, the render instruction generator proceeds to step429.

If the decision block431returns FALSE (NO), the render instruction generator109proceeds to decision block433, where a check is made whether the image is rotated.

If the image is not rotated, or is rotated by only a small angle, the decision block433returns FALSE (NO) and the render instruction generator proceeds to step434. During step434, the render instruction generator109calculates resources knowing the image will be split into horizontal compressed strips. After step434, the render instruction generator109proceeds to step436.

On the other hand, if the image is rotated through a substantial angle, the decision block433returns TRUE (YES) and the render instruction generator109proceeds to step435. In step435, the render instruction generator109calculates resources knowing the image will be split into tiled compressed fragments. After step435, the render instruction generator109proceeds to steps436.

During step436, the render instruction generator109calculates the maximum allowable size of memory that the total compressed data of the image may occupy. This is returned as one property of the current object's size and complexity for subsequent use in decision block304. After step436, the render instruction generator proceeds to step437, where it calculates the amount of memory required in the render engine105for buffers to decompress the image data. This is returned as another property of the current object's size and complexity for subsequent use in decision block304. After step437, the render instruction generator109proceeds to step438, where it calculates the space in memory that will be required for the edge data of the horizontal strips or tiled fragments. This is returned as farther property of the current object's size and complexity for subsequent use in decision block304. After step438, the render instruction generator109then proceeds to step429.

During step429, the render instruction generator109determines if the current object can share any complexity resources, being a level and/or colour slot in the preferred embodiment, with any previous object in the current render instructions, based on its extent and fill colour. If the object cannot share levels or fill colours with previous objects, new levels must be allocated for it when it is added. These may cause the set of current render instructions to overflow the limitations of the render engine105. Also, the object will use up a certain amount of memory in both the render instruction queue and the render engine, and it will use up both render and system resources in the generation and tracking of its edges. Adding the object may overflow these limits also. All these limits, plus any others that exist in either the system or the render engine, together with object's size and complexity determined in step303are examined at step304inFIG.3(a).

Turning now toFIGS. 5(a) and5(b), there is shown a flow chart of the sub-steps of the step312of receiving the rest of the current object's data as shown inFIG. 3(b). This sub-process commences at step310and proceeds to decision block540, where a check is made whether the current object is a character. If the decision block540returns TRUE (YES), the render instruction generator109proceeds to decision block541, where a check is made whether there is still bit map image data to receive.

If the decision block541returns TRUE (YES), then the render instruction generator109proceeds to step542, where the bit map data is received. After step542, the render instruction generator proceeds to step543, where it traces the bit map image to produce edge data. This edge data is then stored544in the font cache104using this object's character definition as the character key. This edge data also forms part of the set of current render instructions.

If the decision block541returns FALSE (NO), the render instruction generator109proceeds to decision block545, where a check is made whether there is still path data to convert to edges. If there is still path data, the decision block545returns TRUE (YES) and the render instruction generator109proceeds to step546, where the path data is converted to edge data. This edge data also forms part of the set of current render instructions.

If the decision block540returns FALSE (NO), the render instruction generator10proceeds to decision block547, where a check is made whether the current object is a shape. If the current object is a shape, the decision block547returns TRUE (YES) and the render instruction generator109proceeds to step546, where the path data of the shape is converted to edge data. This edge data also forms part of the set of current render instructions.

If the decision block547returns FALSE (NO), then the current object was not a bitmap or a shape so it must be an image, and the render instruction generator109proceeds to decision block548, which checks whether the image needs to be compressed. If the image does not need to be compressed, the decision block548returns FALSE (NO), and the render instruction generator109proceeds to step549. During step549, the render instruction generator reads the image data directly into the set of current render instructions. The render instruction generator109then proceeds to step550where it generates the edges for the image. This edge data also forms part of the set of current render instructions.

The decision block548returns TRUE (YES) if the image is to be compressed, and the render instruction generator proceeds to step551. During step551, the render instruction generator109reads a horizontal strip of image data. After step551, the render instruction generator109proceeds to decision block552, where a check is made whether the image is to be compressed solely in horizontal strips. If the decision block552returns TRUE (YES), the render instruction generator109proceeds to step553where the strip is compressed.

If the decision block552returns FALSE (NO), the render instruction generator109proceeds to step554, where the strip is vertically split into tile fragments. After step554, the instruction generator109proceeds to step555where the tile fragments are then individually compressed.

After step553or step555, the render instruction generator109proceeds to decision block556, where a check is made whether there are any more horizontal strips to compress. If the decision block556returns TRUE (YES), the instruction generator returns to step551where the next horizontal strip of image data is read. The same buffer used for reading the previous horizontal strip may be re-used.

The render instruction generator109continues reading and processing the horizontal strips of image data until there is no more image data. The decision block556then returns a FALSE (NO), and the render instruction generator continues to step557. During step557, the render instruction generator109creates the edge data for all the strips or fragments in the image, and continues processing at step313ofFIG. 3(b).

It is possible that due to a constraint of the render system, the image may have to be decimated as well as compressed. Preferably, the render engine105allows an image to be scaled down by no more than 2 times. Thus if the input image is more than 2 times the resolution of the printer, pixels must be removed from the input image to lower its resolution. In the preferred embodiment, this is achieved by averaging an appropriate number of pixels in the x direction, and leaving out scanlines in the y direction. The resolution limit is another of the resource limits handled within the system.

In some circumstances the compressed image data does not fit within the maximum space allowed. This is because the compression ratio achieved by most image compression schemes is data dependent, and the desired compression ratio may not be achieved. Also, the entire image must be compressed in the same way, or artifacts will be visible in the printed page. Also, once image data has been read from the page description, it cannot be read again. So if part of an image is compressed, and then it is discovered that the compressed data will not fit into the available space, the existing compressed data must be decompressed and re-compressed to give a higher compression ratio. This is done without using more resources than originally committed to.

Turning now toFIGS. 6(a) and6(b), there is shown a flow diagram of the procedure for loading the one or more sets of rendering instructions used by the render instruction loader ofFIG. 1A. The render instruction loader loops continuously, waiting for one or more sets of render instructions to appear in the queue, processing them one set at a time, then waiting again.

The render instruction loader110commences at the same time as the render instruction generator109but operates in an asynchronous manner thereto. The render instruction loader commences at step600and proceeds to step660, where it waits until there is a set of render instructions on the instruction queue112. When a set of render instructions has appeared, the render instruction loader110at step661loads the current set of instructions immediately into the render engine. The render instruction loader proceeds to step662, where it de-queues the current set of render instructions, extracts control information from the header of the current set of render instructions, and frees the space used by the current set of render instructions in the instruction queue112.

After step662, the render instruction loader110proceeds to decision block663, where a check is made whether the current set of render instructions uses a background image. Namely, it checks whether the current set of instructions include instructions to draw a background image. If the decision block663returns TRUE (YES), the render instruction loader proceeds to step664, where the reference counter of the background image is decremented. This reference counter is the same counter as used by the render instruction generator109discussed above and can be accessed by both the loader110and generator109.

After step664, the render instruction loader110proceeds to decision block665, where a check is made whether the reference counter is zero (0). If the reference count is now zero (0), it means there are no other sets of render instructions currently in the queue reserving the same space in memory as the current background image, so this reserved space in memory is no longer needed. It should be noted that the current background image was previously loaded into the render engine during step661. Thus when the decision block665returns TRUE (YES), the render instruction loader110frees the reserved space and continues to decision block667. If the decision block665returns FALSE (NO), the render instruction loader proceeds directly to decision block667. The decrement and test of the reference counter must be done in an indivisible operation, to guarantee correct operation with the render instruction generator109, which asynchronously adds sets of render instructions to the queue. In another implementation, it is possible for the render engine to execute instructions directly from the queue, so dequeuing instructions and decrementing the reference count would take place after rendering was completed.

In decision block667, a check is made whether the current set of render instructions will produce a layer, ie. a background image for a subsequent layer. This can be determined from information contained in the header of the current set of render instructions, which is added by the render instruction generator109. If the decision block667returns FALSE (NO), the render instruction loader110proceeds to step668, where it directs the output of the render engine105to the printer106. The render instruction loader110proceeds to step669where it starts the render engine and then proceeds to step670where it waits for the rendering of the current set of instructions to finish. Once the rendering is finished, the rendering instruction loader returns to step660. In another embodiment, the render instruction loader110waits only when the memory in the render engine105is exhausted.

On the other hand, if the decision block667determines that the current set of render instructions will produce a layer, the render instruction loader110proceeds to step671. During step671, the render instruction loader110waits until the next set of instructions is in the instruction queue112. When the next set of render instructions are received in the queue the render instruction loader110proceeds to step672. In step672, the render instruction loader110obtains the location of the background image in memory for the next set of render instructions. At this stage the render instruction loader110does not dequeue the next set of render instructions but proceeds to step673, where it instructs the render engine105to direct the output of the pixel data for the current set of render instructions to the compressor111. The render instruction loader110then proceeds to step674, where it instructs the compressor111to direct its output for the compressed pixel data of the current set of render instructions to the space in memory reserved for the background image for the next set of render instructions. The render instruction loader110then proceeds to step675, where it instructs the render engine105to start rendering the current set of instructions. It also instructs the compressor111to compress the resultant output pixel data, which it then stores it in the reserved space in memory. The rendering instruction loader then in step676waits for the rendering and compression to be completed. The render instruction loader then proceeds to decision block677, where a check is made whether the compressed render output pixels fitted into the space available for the background image. If the decision block677returns FALSE (NO), then the render instruction loader110proceeds to step678, where it directs the compressor111to achieve a higher compression ratio. After step678, the render instruction loader returns to step673. On the other hand, if the decision block677returned TRUE (YES), namely the compressed render output pixels did fit into the space available for the background image, the render instruction loader110continues at step661.

The render engine110can be based on any known render engine with some modification. The render engine should have the capability of re-directing its rendered pixel data back via a compressor to the instruction queue, as well directing its rendered pixel data to the printer. The compressor can be based on any known compressor. Alternatively, the compressor may be dispensed with the result that the background image is uncompressed. In the latter circumstances, this may put resource limits on the rendering system.

The preferred computer system has the advantage that it tests whether the next object will fit before converting it to intermediate data. Sometimes, the test for whether the next object will fit is done even before the data for the object is received by the entire system. For example, a large image may be about to arrive. The system will check whether the image will cause any limits in the system to be exceeded before the data for the image is received. For smaller objects, such as shapes or characters, the data is received by the system but not converted to intermediate data at the time the test for whether the object will fit is made. In this way, the preferred computer system can both use resources efficiently and handle large or complex objects correctly. Moreover, the preferred computer system has significant resource limitations within the render engine that are related to object and render instruction complexity rather than size. The preferred computer system tests whether the incoming object would cause any of the system or render resource limits to be exceeded. It instigates the layering mechanism if the object might cause any limit to be breached. In addition, the preferred computer system has a knowledge of the maximum possible amount of memory that could become available rather than just at the time the object is received, and performs layering only when the maximum amount of memory would be exceeded. This might have the side effect of making the system wait to print a page before more page description data can be received. In addition, the preferred computer system uses compression of background pixel data to make it fit within memory. The compression can be lossy or lossless. Lossy compression may still slightly degrade the appearance of the image, but the appearance will be better than degrading the pixel data. Lossless compression causes no degradation of the appearance of the final image at all.

Turning now toFIG. 7, there is shown a flow chart of an alternative procedure for generating one or more sets of rendering instructions used by the render instruction generator ofFIG. 1A. This alternative procedure differs from the procedure shown inFIGS. 3(a) and3(b) in that the alternative procedure is able to handle composite objects comprising multiple primitive objects combined together using compositing operators in one single z-layer. That is, the group of composited primitive objects is considered for the purposes of Painter's Algorithm to be a single z-layer, wherein the composited objects are combined using compositing operators and/or structures that are not compatible with Painter's Algorithm. Thus, the group of composited primitive objects is treated as indivisible from the point of view of layering. This means that all the components of a composited object must be received before the object can be added to the current set of render instructions. This slightly changes the procedure for generating one or more sets of rendering instructions as previously described with reference toFIGS. 3(a) and3(b) as will be apparent. However, there are many steps in common in both these procedures and for ease of understanding these steps are referenced by the same reference numerals.

On the other hand, the procedure described with reference toFIGS. 3(a) and3(b) is able to handle only one single primitive object per z-layer. As this procedure requires only one primitive object per z-layer, the operations of receiving a primitive object and “Painting” the object into the render instruction queue (step314) can be a sequential operation. This means the object data does not need to be stored before converting to render instructions. However, in the alternate procedure multiple primitive objects can be processed per z-layer. So the object data and associated composited operations need to be stored as they are received. When all primitive objects contributing to the z-layer have been received they are then “Painted” (step314) into the set of current render instructions together in one go.

Returning toFIG. 7, the alternative procedure for generating one or more sets of rendering instructions will now be described in more detail. The render instruction generator109is started700and initialised for each single printed page. The alternative procedure then processes702the next command of the page description in accordance with the page description language (eg PostScript™). The alternative procedure then tests704whether the command is one of several types, and the alternative procedure then proceeds to either one of four different sub-procedures706,708,710, and712depending upon the command type. A switch type statement can perform this multiple branching in flow control.

The sub-procedure706is activated when the command type is for adding a primitive object. As would be apparent, an arbitrary number of primitive objects can be received, and added to the composited object being constructed. The sub-procedure708is activated when the command type is for changing the compositing operator. Again, an arbitrary number of primitive compositing operators can be set for constructing the composited object. The sub-procedure710is activated when the construction of the composited object is complete. This sub-procedure710can be activated on the command type as the commands within the z-layer are not compatible with Painter's Algorithm. The sub-procedure712is activated when command type is for other utilities to be activated. Such utilities may include clipping, diagnostics, render mode adjustment and so forth.

These four sub-procedures return via714to step702, where the next command of the page description is processed702. The alternative procedure terminates at step716after the final completion of the paint sub-procedure710.

Turning now toFIGS. 8(a) and8(b), there is now described in more detail the sub-procedure706for adding a primitive object used in the procedure shown inFIG. 7. The sub-procedure706for adding a primitive object commences at step800where basic information concerning the primitive object is retrieved. The sub-procedure706proceeds to decision block806, where a check is made whether or not the current primitive object is to replace an existing object. If the decision block806returns TRUE(YES), the primitive object is replaced808within the composited object. For example, the composited object may be using a ROP4operator. This takes operands of Source, Pattern and Mask. The Source, Pattern or Mask may be replaced several times before the final combination to be painted is known. If a primitive object is being replaced, it is removed (808) as it no longer contributes to the cumulative resources for the composite object. Next, at step302, the sub-procedure706obtains the current usage of all render and system resources utilised by the set of current render instructions in similar fashion as that described with reference toFIGS. 3(a) and3(b). The sub-procedure706then proceeds to step303, where it retrieves enough information about the next primitive object in the page description to determine the primitive object's complexity and size. The manner in which this is determined is similar to that described with reference to the preferred procedure shown inFIGS. 4(a) and4(b).

Next, at decision block810, a check is made whether adding this primitive object would exhaust the host memory limits. If the host memory limits would not be exhausted the sub-procedure706proceeds to step816. If the host memory limits would be exceeded, then sub-procedure706tests at decision block812whether layering might help. Layering might help if there are already exists objects in the current set of render instructions which, when rendered into a background layer, will free up host memory. If layering will not free up memory, then the sub-procedure706returns with an error814signal of “object too complex”. On the other hand, if layering might help, the sub-procedure706proceeds to steps305to310(FIG. 8(a) and8(b)). The operation of these steps305to310(FIG. 8(a) and8(b)) is substantially the same as that described above with reference to steps305to310ofFIGS. 3(a) and3(b) and will not be described further.

After step310(FIG. 8(b)) or when the decision block810(FIG. 8(a)) returns False (No), the sub-procedure706proceeds to step816where the rest of the primitive object's data is received. Note that in this alternative procedure, it is possible for this step to fail. It is possible that there will be insufficient host memory to receive the primitive object. If there is insufficient host memory, even after waiting for the render instruction queue to be completely empty, this embodiment returns an “object too complex” error. If there was sufficient host memory, the primitive object is saved818, along with its complexity information, the current compositing operator, and any other relevant information. The sub-procedure706then terminates820and returns to step702via714for the next command.

Turning now toFIG. 9, there is shown a flow chart of the sub-procedure708for changing the compositing operator used in the procedure shown inFIG. 7. The subprocedure708commences at step900where the compositing operator is retrieved. The type of compositing operator retrieved depends upon the type of command processed in step702. This compositing operator is then saved as the current compositing operator. The sub-procedure708then terminates904and returns to step702via714for the next command.

Turning now toFIGS. 10(a) and10(b), there is shown a flow chart of the sub-procedure710for painting used in the procedure shown inFIG. 7. This sub-procedure710commences when the command processed in step702is compatible with Painter's algorithm. When this occurs, the group of primitive objects previously received and stored by the sub-procedures706and708currently being constructed is complete. The sub-procedure710firstly determines1002the size and complexity of the constructed group of primitive objects. This is the sum of the known size and complexity of each of the component primitive objects, plus possibly some additional resource usage. For example, in an implementation it may require additional levels to composite the primitive objects together. Then the sub-procedure710determines the current usage of all resources, in a similar fashion to step302(FIG. 3(a)). The sub-procedure then proceeds to a decision block304, where a check is made whether or not the resource limits will be exceeded, in a similar fashion to decision block304(FIG. 3(a)). If the decision block304returns False (No) the sub-procedure proceeds to step313. On the other hand, if the decision block304returns True (Yes), the sub-procedure proceeds to decision block1004where a check is made whether or not layering might help. If the decision block1004determines layering will not help, then the sub-procedure returns1006an error signal of “object too complex”. If the decision block1004determines layering may help, the subprocedure710proceeds to steps305to310(FIG. 10(b)). The operation of these steps305to310(FIG. 10(b)) is substantially the same as that described above with reference to steps305to310ofFIGS. 3(a) and3(b) and will not be described further. After step310, the sub-procedure710proceeds to step302.

If the decision block304(FIG. 10(a)) returns false, the sub-procedure proceeds to step313where the object data is converted into render instructions, which is an intermediate data form of the page description and then adds314these converted render instructions to the set of the current render instructions.

After step314, the sub-procedure710proceeds to decision block315. In decision block315, a check is made whether the current group of primitive objects is the last group of primitive objects on the page. If the decision block315returns TRUE (YES), the set of current render instructions are queued (step316) on the instruction queue112for subsequent loading by the render instruction loader110. The sub-procedure710terminates317and the alternative procedure then terminates716. If the decision block315returns FALSE (NO), the sub-procedure710returns to step302to receive the next group of primitive objects, where the process starts again for the next group of primitive objects.

In this way, arbitrarily complex constructed objects can be rendered. However, layering can only be done where z ordering applies. So the entire composited object must fit into host memory at one time, and it must also fit within one layer (both memory and complexity-wise), for the composited object to be able to be rendered within the fixed memory and fixed resource environment. Practically speaking, using conventional page description languages, objects are rarely so complex that they cannot be rendered.

As mentioned above, the instruction queue and render instruction loader can be dispensed with. In these cases there is only one set of rendering instructions and there is no need for a queue. The instruction generator will again test if available resources would be exceeded if the received object is added to the current set of rendering instructions. If the resources would be exceeded, the instruction generator instructs the render engine to render the current set (not including the current received object) onto the reserved space in memory (frame store) of the background image and then sets the current render-list to empty. This empty set of current rendering instructions however may contain basic render initialisation instructions. If the resources would not be exceeded, the instruction generator does not alter the current set of rendering instructions. The instruction generator then adds the received object to the current set of rendering instructions. If the received object is the last object in the z-order and if said frame-store was rendered onto, the instruction loader requests the render engine to render the current set of rendering instructions in combination with said frame-store to form the rendered page description. On the other hand, if the received object is the last object in the z-order and if the frame store was not rendered onto the instruction loader requests the render engine to render the current set to form the rendered page description.

The aforementioned preferred method(s) comprise a particular control flow. There are many other variants of the preferred method(s) which use different control flows without departing the spirit or scope of the invention: Furthermore one or more of the steps of the preferred method(s) may be performed in parallel rather than sequential. The aforementioned preferred method(s) may be implemented as a computer program, which may be stored on a computer readable medium. The steps of the method can be implemented as program code for instructing the host processor to perform the functions of those steps.

INDUSTRIAL APPLICABILITY

It is apparent from the above that the embodiments of the invention are applicable to the computer graphics and printing industries.

The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiment(s) being illustrative and not restrictive. For example, the preferred embodiment may be adapted for use in rendering to a display screen.