A computer application typically provides a printable page to a printing device for printing to a hard copy medium, such as a paper sheet. The printable page is typically provided in the form of a description of the page to be printed, specified using a Page Description Language (PDL), such as Adobe® PDF or Hewlett-Packard® PCL. The PDL provides descriptions of objects to be rendered onto the page in a rendering (or z) order, as opposed to a raster image (i.e. a bitmap of pixel values) of the page to be printed. The page is typically rendered for printing by an object-based graphics system, also known as a Raster Image Processor (RIP). A RIP may also be used to render the page to a display.
The printing device receives the description of the page to be rendered and generates an intermediate representation of the page. The printing device then renders the intermediate representation of the page to pixels which are printed to print media, such as paper. In general, an intermediate representation of a page consumes less memory than the raster image representation. Also, in some prior art printing devices, the intermediate representation of the page may be rendered to pixels in real-time, being the rate at which the output device, be it a printer or a display, can reproduce output pixels. Real-time rendering is particularly important for video displays, where animation frame rates must be met to ensure fluidity of motion. Real-time rendering in a printing environment is important to ensure compliance with page throughput rates of the printer.
The intermediate page representation is generated by a controlling program which is executed by a controlling processor within the printer device. A pixel rendering apparatus is used to render the intermediate page representation to pixels. The rendered pixels are transferred to a printer engine, such as an electro-photographic engine, which prints the pixel onto the print media.
Next generation printing systems are expected to operate at a much higher page rate than current printing systems. This is in addition to an increase in device resolution, graphics complexity, and the number of print features supported.
In computing, there is a trend towards achieving higher performance through the use of multi-processor and multi-core architectures. These architectures allow a number of threads to execute in parallel, each on a corresponding processor, thereby reducing the overall time it takes to complete a task. However, in order to take advantage of such parallelism, the task must be broken down into largely independent sub-tasks that can be executed in parallel. This is difficult to achieve for many tasks, including many of the operations performed by a RIP.
The RIP process consumes a large proportion of time within a printing system. It is therefore desirable that the RIP process be accelerated through the use of multi-threading on a multi-core or multi-processor device. One method of performing the RIP process in parallel is by sub-dividing the output pixel space into regions, and performing the RIP process for each region in its own thread.
One method of doing this is to assign each page object to be rasterized to each of the regions that the page object overlaps or is present in. The regions can then be rasterized in parallel, with a separate thread processing each region. Each thread can only process those objects that overlap the region that is being rendered. However, because many objects may overlap many regions, many objects must be scan-converted multiple times, once for each region that the object overlaps. It is desirable that this duplication of processing be removed.
Another method of sub-dividing the output pixel space into regions, which removes this duplication of object scan-conversion, is to split each page object prior to scan-conversion, according to the object's intersections with region boundaries. A number of sub-objects are produced, each of which is present in (or overlaps) only a single region. Each sub-object therefore only needs to be scan-converted once. However, the splitting of high-level graphic objects (which normally consist of primitives such as lines and Bezier splines) is complex, and can result in mathematical errors which affect the quality of the rasterized output.
It is desirable that one or more these problems with the prior art be resolved, or at least ameliorated, while still allowing the intermediate representation of each region of the page to be generated in parallel.