System and method for optimising halftoning printer performance

CROSS-REFERENCE TO RELATED PATENT APPLICATIONS

0001This application claims the right of priority under 35 U.S.C. § 119 based on Australian Patent Application No. PS1342, filed Mar. 25, 2002, which is incorporated by reference herein in its entirety as if fully set forth herein.

TECHNICAL FIELD OF THE INVENTION

0002The present invention relates generally to computer graphics and, in particular, to rendering graphical objects. The present invention relates to a method and apparatus for rendering graphical objects. The invention also relates to a computer program product including a computer readable medium having recorded thereon a computer program for rendering graphical objects.

BACKGROUND OF THE INVENTION

Field of the Invention

0003Many conventional printing systems, such as those based on ink-jet technology, print an image by forming extremely small droplets (dots) of ink onto a page. Most of these conventional printing systems do not utilise continuous-tone printers, as known in the relevant art. That is, dots that form an image printed by one of these conventional printing systems, are either fully present or fully absent. To achieve a wide range of colors, such printers use conventional dithering or halftoning methods that approximate a desired color with a pattern of dots in two or more available colors.

0004One known method of rendering pages using a printer, includes the steps of generating an image of a page in a frame buffer configured within a computer memory connected to the printer, and then performing a halftoning operation on the image after the image is fully generated for every pixel of the page. In order to then print the image, the arrangement of dots representing the image of the printed page needs to be calculated. Such a calculation is a computationally intensive process particularly if the calculation has to be performed for every pixel on the output page. This problem is further exacerbated if the printer device has a high output resolution.

0005Another known method of rendering pages on a printer, seeks to reduce memory usage by performing halftoning on each graphical object of an image before the graphical objects are rendered into a frame buffer, thus allowing the frame buffer to be much smaller. However, this method suffers from two major disadvantages. Firstly, graphical objects may overlap, requiring a great deal of work to be done in halftoning areas of graphical objects that will never be printed. Secondly, if graphical objects are not fully opaque (ie possess some transparency) and/or are rendered using logical raster operations, then graphical object data that is below the transparent objects on a page can be destroyed, producing incorrect results in an output image.

0006Thus, a need clearly exists for an improved rendering method, which provides improvements in both speed and memory usage when rendering opaque and overlapping objects.

SUMMARY OF THE INVENTION

0007It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.

0008According to one aspect of the present invention there is provided a method of creating an image, said image being formed by rendering a plurality of graphical objects on a scanline basis, where each scanline comprises at least one run of pixels, said method comprising the steps of: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0009">(I) forming an array representing said graphical objects of said image, said array being sorted in an order from a top-most graphical object to a bottom-most graphical object; and</li><li id="ul0002-0002" num="0010">(II) for each scanline of said image and for each run of pixels of said scanline: <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0011">(II) (i) traversing said array to determine objects contributing to said run of pixels; and</li><li id="ul0003-0002" num="0012">(II)(ii) compositing data associated with one or more of said contributing objects and halftoning the composited data to generate said run of pixels.</li></ul></li></ul></li></ul>

0013According to another aspect of the present invention there is provided an apparatus for creating an image, said image being formed by rendering a plurality of graphical objects on a scanline basis, where each scanline comprises at least one run of pixels, said apparatus comprising: <ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0000"><ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0014">array forming means for forming an array representing said graphical objects of said image, said array being sorted in an order from a top-most graphical object to a bottom-most graphical object;</li><li id="ul0005-0002" num="0015">traversing means for traversing said array to determine objects contributing to a run of pixels of a scanline; and</li><li id="ul0005-0003" num="0016">compositing means for compositing data associated with one or more of said contributing objects and halftoning the composited data to generate said run of pixels.</li></ul></li></ul>

0017According to still another aspect of the present invention there is provided a computer program for creating an image, said image being formed by rendering a plurality of graphical objects on a scanline basis, wherein each scanline comprises at least one run of pixels, said program comprising code for executing the following steps: <ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0000"><ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0018">(I) forming an array representing said graphical objects of said image, said array being sorted in an order from a top-most graphical object to a bottom-most graphical object; and</li><li id="ul0007-0002" num="0019">(II) for each scanline of said image and for each run of pixels of said scanline: <ul id="ul0008" list-style="none"><li id="ul0008-0001" num="0020">(II) (i) traversing said array to determine objects contributing to said run of pixels; and</li><li id="ul0008-0002" num="0021">(II)(ii) compositing data associated with one or more of said contributing objects and halftoning the composited data to generate said run of pixels.</li></ul></li></ul></li></ul>

0022According to still another aspect of the present invention there is provided a computer readable medium, having a program recorded thereon, where the program is configured for creating an image, said image being formed by rendering a plurality of graphical objects on a scanline basis, wherein each scanline comprises at least one run of pixels, said program comprising code for executing the following steps: <ul id="ul0009" list-style="none"><li id="ul0009-0001" num="0000"><ul id="ul0010" list-style="none"><li id="ul0010-0001" num="0023">(I) forming an array representing said graphical objects of said image, said array being sorted in an order from a top-most graphical object to a bottom-most graphical object; and</li><li id="ul0010-0002" num="0024">(II) for each scanline of said image and for each run of pixels of said scanline: <ul id="ul0011" list-style="none"><li id="ul0011-0001" num="0025">(II) (i) traversing said array to determine objects contributing to said run of pixels; and</li><li id="ul0011-0002" num="0026">(II)(ii) compositing data associated with one or more of said contributing objects and halftoning the composited data to generate said run of pixels.</li></ul></li></ul></li></ul>

0027Other aspects of the invention are also disclosed.

BRIEF DESCRIPTION OF THE DRAWINGS

0028One or more embodiments of the present invention will now be described with reference to the drawings, in which:

0029<figref idref="DRAWINGS">FIG. 1</figref> is a schematic block diagram of a general purpose computer upon which arrangements described can be practiced;

0030<figref idref="DRAWINGS">FIG. 2</figref> is block diagram showing an overview of a method of rendering an image;

0031<figref idref="DRAWINGS">FIG. 3</figref> shows pixel runs generated for the image of <figref idref="DRAWINGS">FIG. 2</figref>;

0032<figref idref="DRAWINGS">FIG. 4</figref> shows the image of <figref idref="DRAWINGS">FIG. 2</figref> generated in accordance with the arrangements described; and

0033<figref idref="DRAWINGS">FIGS. 5A and 5B</figref> show a flowchart for a method of rendering graphical objects for printing.

DETAILED DESCRIPTION INCLUDING BEST MODE

0034Where reference is made in any one or more of the accompanying drawings to steps and/or features, which have the same reference numerals, those steps and/or features have for the purposes of this description the same function(s) or operation(s), unless the contrary intention appears.

0035A method <b>500</b> of rendering graphical objects is described below with reference to <figref idref="DRAWINGS">FIGS. 5A and 5B</figref>. The principles of the method <b>500</b> have general applicability to the rendering of graphical objects. However, for ease of explanation, the steps of the method <b>500</b> are described with reference to the rendering of graphical objects for printing on a page. It is not intended that the present invention be limited to the described arrangement. For example, the method <b>500</b> may have application to the rendering of graphical objects for display on a liquid-crystal or other display device, which has the characteristic that dots that comprise the displayed image are fully present or fully absent. Such display devices are often driven by embedded computing systems having extremely constrained memory and performance.

0036The method <b>500</b> is preferably practiced using a general-purpose computer system <b>100</b>, such as that shown in <figref idref="DRAWINGS">FIG. 1</figref> wherein the processes of <figref idref="DRAWINGS">FIGS. 2 to 5B</figref> may be implemented as software, such as an application program executing within the computer system <b>100</b>. In particular, the steps of the method <b>500</b> described below are effected by instructions in the software that are carried out by the computer. The instructions may be formed as one or more code modules, each for performing one or more particular tasks. The software may also be divided into two separate parts, in which a first part performs the method <b>500</b> and a second part manages a user interface between the first part and the user. 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 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 implementing the arrangements described here in.

0037The computer system <b>100</b> comprises a computer module <b>101</b>, input devices such as a keyboard <b>102</b> and mouse <b>103</b>, output devices including a printer <b>115</b> and a display device <b>114</b>. A Modulator-Demodulator (Modem) transceiver device <b>116</b> is used by the computer module <b>101</b> for communicating to and from a communications network <b>120</b>, for example connectable via a telephone line <b>121</b> or other functional medium. The modem <b>116</b> 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).

0038The computer module <b>101</b> typically includes at least one processor unit <b>105</b>, a memory unit <b>106</b>, for example formed from semiconductor random access memory (RAM) and read only memory (ROM), input/output (I/O) interfaces including a video interface <b>107</b>, and an I/O interface <b>113</b> for the keyboard <b>102</b> and mouse <b>103</b> and optionally a joystick (not illustrated), and an interface <b>108</b> for the modem <b>116</b>. A storage device <b>109</b> is provided and typically includes a hard disk drive <b>110</b> and a floppy disk drive <b>111</b>. A magnetic tape drive (not illustrated) may also be used. A CD-ROM drive <b>112</b> is typically provided as a non-volatile source of data. The components <b>105</b> to <b>113</b> of the computer module <b>101</b>, typically communicate via an interconnected bus <b>104</b> and in a manner, which results in a conventional mode of operation of the computer system <b>100</b> known to those in the relevant art. Examples of computers on which the described arrangements can be practiced included IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom.

0039Typically, the application program is resident on the hard disk drive <b>110</b> and read and controlled in its execution by the processor <b>105</b>. Intermediate storage of the program and any data fetched from the network <b>120</b> may be accomplished using the semiconductor memory <b>106</b>, possibly in concert with the hard disk drive <b>110</b>. In some instances, the application program may be supplied to the user encoded on a CD-ROM or floppy disk and read via the corresponding drive <b>112</b> or <b>111</b>, or alternatively may be read by the user from the network <b>120</b> via the modem device <b>116</b>. Still further, the software can also be loaded into the computer system <b>100</b> from other computer readable media. The term “computer readable medium” as used herein refers to any storage or transmission medium that participates in providing instructions and/or data to the computer system <b>100</b> for execution and/or processing. Examples of storage media include floppy disks, magnetic tape, CD-ROM, a hard disk drive, a ROM or integrated circuit, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computer module <b>101</b>. Examples of transmission media include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including email transmissions and information recorded on websites and the like.

0040The steps of the method <b>500</b> integrate a halftone process with an existing host rendering system executing on the computer system <b>100</b>. In the method <b>500</b>, areas of constant colour are converted to a tiled representation, which can be used to represent the halftoned colour for any area of an image no matter how large. Thus, the method <b>500</b> improves the performance of the host rendering system for a wide range of output pages. Further, in the method <b>500</b>, bitmap image data can be converted into a corresponding halftoned representation on demand, thus saving considerable memory during the rendering of the corresponding image.

0041The steps of the method <b>500</b> are performed on a scanline basis as a rendering system generates runs of pixel data from one edge crossing to the next, and are performed on demand. In the method <b>500</b>, an image is rendered utilizing a display list or array of graphical objects representing the image where the objects are converted into a halftoned representation before being output for printing on a page. Preferably, dithering is performed on the objects of the image before being output. Alternatively, error diffusion, binarization or any other halftoning technique known to those in the relevant art can be performed on the objects of the image. The generation of an output in such a manner reduces the work typically required in halftoning areas of objects and does not require the use of a frame buffer. The method <b>500</b> also performs color conversion on graphical objects if required.

0042Graphical objects to be rendered using the method <b>500</b> can define areas of flat or blended color, bitmap image data, or tiled image data, for example. In the method <b>500</b>, halftoned data can be pre-calculated for different object types (e.g. text objects, graphic objects, image objects) and the halftoned data can be stored along with original input data representing the graphical objects to be rendered. As described above, the halftoned data can be based on any dithering technique known to those in the relevant art. Alternatively, the halftoned data can be based on error diffusion, binarisation or any other halftoning technique known to those in the relevant art. Where an object of an image is known to be fully opaque, halftoned data associated with the opaque object can be used to directly render the image rather than applying transparency as a separate post-rendering step, as is often performed inconventional rendering methods. Rendering of flat coloured objects using the method <b>500</b> greatly reduces the number of pixels that must be color converted and halftoned compared to conventional rendering methods. Further, only the area of an object of the image that is actually visible is processed. Thus, the amount of memory used to render graphical objects is reduced over, for example, a conventional printer rendering method requiring a temporary frame store.

0043Still further, if an object on a page to be rendered is not opaque, the original colour or image data of the object is available at full accuracy for a compositing operation or logical raster operation that depends on the data. However, if all graphical objects on a page are known to be fully opaque, such original input data can be discarded, resulting in still further memory savings.

0044Still further, in a system where a list of object data (i.e., display list) resides in memory <b>106</b> and the rendering of the object data in accordance with the method <b>500</b> is executed by the printer <b>115</b>, for example, the method <b>500</b> can reduce the size of an associated spool file significantly. The reduction in the size of the spool file is realised since the original contone bitmap data is replaced with equivalent halftoned data before the spooling of the display list to the printer <b>115</b>.

0045Referring to <figref idref="DRAWINGS">FIG. 2</figref>, in the method <b>500</b>, an image <b>200</b> comprising objects <b>203</b>, <b>204</b> and <b>205</b>, for example, is rendered by generating edge-crossing information during a scan of the image <b>200</b>. The edge-crossing information is extracted from a list of graphical objects <b>202</b>, representing the image <b>200</b>, where the list <b>202</b> is pre-ordered by depth (i.e. z-order). The edge crossing information is then used to generate runs of pixels to be output to a printer (e.g. the printer <b>115</b>) for printing on a page <b>210</b>. For example, <figref idref="DRAWINGS">FIG. 3</figref> shows a portion of the image <b>200</b> where a scanline <b>301</b> crosses edges <b>322</b>, <b>323</b> and <b>324</b> resulting in pixel runs <b>325</b>, <b>326</b>, <b>327</b> and <b>328</b>.

0046As discussed above, the method <b>500</b> can be utilised to render flat colours (i.e. areas of constant colour) (e.g. the object <b>203</b>), colors interpolated between two endpoints (e.g. the object <b>204</b>), and bitmap image data (e.g. the bitmap image <b>205</b>). The method <b>500</b> can also be utilised to render bitmap image data that is repeated or tiled throughout an area being rendered. In particular, areas of constant color are converted into a tiled representation, which is then used in a halftoning operation for that area of the image.

0047The method <b>500</b> is preferably implemented as an application program being resident on the hard disk drive <b>110</b> and being read and controlled in its execution by the processor <b>105</b>. The method <b>500</b> begins at step <b>501</b>, where the processor <b>105</b> detects a first graphical object to be rendered. At the next step <b>503</b>, the graphical object is decomposed by the processor <b>105</b> into a set of edges defining the object, priority information for the object, a raster operation for the object and a corresponding winding rule for the object. The method <b>500</b> continues at the next step <b>505</b> where the set of edges defining the object are added to an edge database configured within memory <b>106</b>. At the next step <b>507</b>, if all objects of the image have been received by the processor <b>105</b>, then the method <b>500</b> continues at the next step <b>509</b>. Otherwise, the method <b>500</b> returns to step <b>501</b>.

0048At step <b>509</b>, the edges stored in the edge database configured within memory <b>106</b>, are sorted in ascending y-coordinate, ascending x-coordinate, and ascending priority order (i.e. z-order). At the next step <b>511</b>, the processor <b>105</b> selects a scanline for the image to be rendered. For each pixel run on the scanline selected at step <b>511</b>, objects having an edge entered by the scanline are activated and objects having an edge exited by the scanline are de-activated, at the next step <b>513</b>. The method <b>500</b> continues at the next step <b>514</b>, where if the highest priority active object for a current pixel run is opaque, then the method <b>500</b> continues at the next step <b>515</b>. Otherwise, the method <b>500</b> proceeds to step <b>517</b>. At step <b>515</b>, if fill data for the highest priority object has been halftoned, then the method <b>500</b> proceeds to step <b>519</b>. Otherwise, the method <b>500</b> proceeds to step <b>516</b> where halftone information is generated for the fill data of the object and is stored in memory <b>106</b> together with the original fill data for the object. The method <b>500</b> continues at the next step <b>519</b>, where the pixel run is output, using halftoned fill data for printing on a printer (e.g. the printer <b>105</b>).

0049At step <b>517</b>, fill data for all visible objects of the current pixel run are composited together to generate data for the pixel run. Also at step <b>517</b>, the data for the current pixel run is halftoned and then output for printing. At the next step <b>521</b>, if all pixel runs have been processed for the current scanline, then the method <b>500</b> continues at the next step <b>523</b>. Otherwise, the method <b>500</b> returns to step <b>513</b>. At step <b>523</b>, if all scanlines have been processed for the image to be rendered, then the method <b>500</b> concludes. Otherwise, the method <b>500</b> returns to step <b>511</b> where a next scanline is selected by the processor <b>105</b>.

0050The method <b>500</b> will now be further explained with reference to the example of <figref idref="DRAWINGS">FIGS. 2 to 4</figref>. Referring to <figref idref="DRAWINGS">FIG. 4</figref>, scanlines are preferably generated downwards from the top of a page <b>210</b> to be rendered. However, a person skilled in the relevant art would appreciate that scanlines can also be generated from the bottom of the page <b>210</b>. As seen in <figref idref="DRAWINGS">FIG. 4</figref>, pixel runs <b>431</b>, <b>450</b> and <b>451</b> are generated for the scanline <b>401</b> and pixel runs <b>434</b>, <b>435</b>, <b>436</b> and <b>437</b> are generated for the scanline <b>402</b>. Any scanlines prior to scanline <b>401</b> do not intersect any of the graphical objects <b>203</b> or <b>205</b>, so pixel runs generated by the scanlines prior to the scanline <b>401</b> do not result in any halftoned output. This is also true for the pixel run <b>431</b>. The first non-white graphical object encountered during the scanline process is the flat fill object <b>203</b>. In the method <b>500</b>, the object <b>203</b> is converted into a tiled image <b>433</b> representing a portion of the object <b>203</b> and all subsequent pixel runs within the flat fill object <b>203</b> from the scanline <b>401</b> onwards, use the tiled image <b>433</b> to generate halftoned output directly for printing on the printer <b>115</b>. Generating pixel runs in this manner results in an improvement in both speed and efficiency over conventional methods of rendering since tiled images can be rendered by a computer system (e.g. the computer system <b>100</b>) with little overhead.

0051For the scanline <b>402</b>, the pixel run <b>434</b> will be white and the pixel run <b>435</b> will utilise the tiled image <b>433</b>. In the method <b>500</b>, for the pixel run <b>436</b>, a portion of the image object <b>205</b> is converted into a halftoned image <b>438</b> (i.e. represented by the shaded area) as seen within the image object <b>205</b>. The halftone image <b>438</b> is used for all subsequent pixel runs within the image object <b>205</b> assuming that the image object <b>205</b> is fully opaque in the region of overlap <b>457</b> (i.e. represented by the phantom line) between the object <b>203</b> and the object <b>205</b>. In contrast, if the image object <b>205</b> is not fully opaque then the region of overlap <b>457</b> is composited using the original data of the flat fill object <b>203</b> and the image object <b>205</b>. The result of the compositing operation is then halftoned. It is noted however that such compositing is only required within the region of overlap <b>457</b> and then only if the corresponding compositing or logical raster operation requires such action.

0052Continuing the example of <figref idref="DRAWINGS">FIG. 4</figref>, if it is known in advance that none of the graphical objects <b>203</b>, <b>205</b> or <b>204</b> require compositing since all of the objects are opaque, then the original bitmap data for the image object <b>203</b> can be discarded after the halftoned image is generated. Such action results in a large reduction in memory usage for a 24-bit RGB contone image, for example. The original data for such an RGB image uses three bytes per pixel, while a four bit per pixel halftoned representation of the image at the same resolution packs two pixels into a byte, providing an improvement of 6:1.

0053The steps of the method <b>500</b> are preferably performed as the processor <b>105</b> generates runs of pixel data from one edge crossing to the next. This results in several advantages over conventional rendering methods. Firstly, only the area of each graphical object that is actually visible within one or more pixel runs is processed. Secondly, if an object is not opaque then the original fill color or image data for the object is available at full accuracy for any compositing operation or logical raster operation that depends on the object. Thirdly, if it is known that no transparent graphical objects exist on a page to be rendered, data associated with hidden objects (i.e. lower priority objects) may be discarded after the data associated with the lower priority objects has been halftoned, resulting in considerable memory savings for image data. Finally, bitmap image data can be converted into a halftoned representation on demand, thus saving considerable memory.

0054The method <b>500</b> can alternatively be implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of <figref idref="DRAWINGS">FIG. 5</figref>. Such dedicated hardware may include graphic processors, digital signal processors, or one or more microprocessors and associated memories.

0055The aforementioned method comprises a particular control flow. There are many other variants of the method which use different control flows without departing the spirit or scope of the invention. Furthermore one or more of the steps, of the methods may be performed in parallel rather than sequentially.

0056The 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 embodiments being illustrative and not restrictive.