AU2014277651A1

AU2014277651A1 - Generating and rendering an anti-aliased page representation

Info

Publication number: AU2014277651A1
Application number: AU2014277651A
Authority: AU
Inventors: Paul William Morrison; George Politis; Lena Qunying Ye Qian
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 2014-12-15
Filing date: 2014-12-15
Publication date: 2016-06-30

Abstract

Abstract GENERATING AND RENDERING AN ANTI-ALIASED PAGE REPRESENTATION 5 A method of generating an anti-aliased representation of a document is disclosed. An intermediate representation of the document comprising a plurality of edges scan-converted at a first predetermined resolution, is received. The edges define regions associated with region rendering instructions. Two anti-aliased edges scan-converted at a second resolution lower than the first resolution are generated for at least one edge from the plurality of edges. The anti 10 aliased edges separate an anti-aliasing region and regions associated with a single set of the region rendering instructions. The anti-aliased region is associated with sets of the region rendering instructions corresponding to two or more neighbouring regions, to form a plurality of anti-aliased region rendering instructions. Weighting coefficients are determined for the anti-aliased region rendering instructions using edges in the intermediate representation. An 15 anti-aliased representation of the document is generated for rendering at the second resolution using the plurality of anti-aliased region rendering instructions and the determined weighting coefficients. 94S9614v1 (P132R9S Snpri As Fild) -9/20 Compositing stacks Fig. 8A Edge Compositing stack/s Weights 0] W851 852 [(2)], [(2)], [(2)] F-l]F3-] [(3)], [(1)], [(3)], [(2)], [(3)], [(1)], [(1)] S F-3T-[(3)], [(2)] F4]F2][(1), (2), (2)] [(1, 2)] [(2), (3)] Fig. 8B 9459556v1(94595561)

Description

GENERATING AND RENDERING AN ANTI-ALIASED PAGE REPRESENTATION

TECHNICAL FIELD

The present invention relates generally to the field of graphics rendering and, in particular, to a method, apparatus and system for generating and rendering an anti-aliased region-based page representation. The present invention also relates to a computer program product including a computer readable medium having recorded thereon a computer program for generating and rendering an anti-aliased region-based page representation.

BACKGROUND 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.

Prior to rendering a PDL to pixel data, an intermediate representation of the page is often generated. 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 corresponding raster image representation. In particular, a region-based or edge-based intermediate representation contains only the edges of the regions of the page. The intermediate representation can therefore be stored more efficiently, or be transferred across a network using lower bandwidth. Also, in some printing devices, the intermediate representation of the page may be rendered to pixels in real-time, being the rate at which the printer can reproduce pixel data. In particular, an intermediate representation that is rasterised at the same resolution as the print device can be quickly processed and rendered to pixel data.

In a cloud printing system, a remote server may produce an intermediate representation of a page to be printed. The intermediate representation is sent to a user’s mobile device (e.g. a smart phone or tablet) so that the user can verify the contents, page setup, etc. This is commonly known as “print preview”. If the user is satisfied with the intermediate representation, the user may choose to send the intermediate representation to the print device to be printed. Prior to printing, the print device will render the intermediate representation to pixel data. Alternatively, the mobile device may render the intermediate representation to pixel data, and send the pixel data to the print device to be printed.

The print device, and therefore the intermediate representation produced by the remote server, will commonly be at a high resolution, for example 600 or 1200 dpi (dots per inch). However, the display on the mobile device will commonly be at a much lower resolution, for example 150 or 300 dpi. Due to the low resolution of mobile device displays, anti-aliasing is typically performed.

Aliasing arises when a signal containing high frequencies (such as high-resolution image) is sampled at low resolution (such as rendering on a low-resolution display). This typically results in visual artefacts such as stepped or jagged edges. Anti-aliasing, as applied to graphics rendering, is a filtering process where the colour of a pixel is determined using colour information from surrounding pixels. Anti-aliasing results in a slightly blurred but more visually pleasing image.

One method of producing a low-resolution anti-aliased intermediate representation of a page based on a higher resolution intermediate representation is known as “super-sampling”. Super-sampling involves rendering the image to a buffer at high resolution. The high-resolution pixel data is then filtered down to the lower resolution of the display. The colour of a display pixel is typically a weighted function of the corresponding high-resolution pixel in the buffer and its surrounding pixels. One advantage of super-sampling is that it is simple, and easy to implement in hardware. However, super-sampling requires additional memory to store the buffered high-resolution pixel data, and all pixels must be rendered at high resolution whether the pixels require anti-aliasing or not, reducing rendering speed.

Other anti-aliasing methods perform anti-aliasing while rendering the graphical objects in vector form to pixel data. These anti-aliasing methods typically render the page in scan line order (at low resolution), and sample the edges of graphical objects at high-resolution along each scan line. A scan line is a single row of pixels in the final raster image. The colour of a pixel can then be determined using the high-resolution sampling information associated with each graphical object that intersects the pixel. Advantages of these methods are that rendering is performed at low resolution, and is therefore fast, and that anti-aliasing is only performed on pixels near the edges of graphical objects. However, methods that perform anti-aliasing while rendering the graphical objects in vector form sample vector data at high resolution, and are therefore not suited to anti-aliasing rasterised intermediate representations. Further, these methods typically produce pixel data, rather than an intermediate representation, which consumes a large amount of memory and/or network bandwidth.

Other anti-aliasing methods generate run-length encoded anti-aliased pixel data. High-resolution pixel data is typically first produced and stored in a buffer (i.e. super-sampling). The anti-aliased pixel data is then generated in scan line order. As with super-sampling, the colour of an anti-aliased pixel is typically a weighted function of the corresponding high-resolution pixel in the buffer and its surrounding pixels. The anti-aliased pixels along a scan line are run-length encoded. Run-length encoding is a compression method, where a sequence of equal or similar values (pixel colours) is represented by a value (pixel colour) and length of the sequence (number of consecutive pixels). The pixels that undergo anti-aliasing (typically near the edges of graphical objects) may be represented using a single run with two or more colours and an associated sequence of weights. Each weight corresponds to a single pixel in the run, and indicates the contribution of each colour associated with the run. The weights may be represented by grayscale values or percentages. One advantage of the anti-aliasing methods that generate run-length encoded anti-aliased pixel data is that the methods produce a representation (run-length encoded pixels) that is compact in comparison with raw pixel data. However, the anti-aliasing methods that generate run-length encoded anti-aliased pixel data must first render the pixel data at high resolution, which incurs cost in speed and memory usage.

SUMMARY

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

According to one aspect of the present disclosure, there is provided a method of generating an anti-aliased representation of a document, the method comprising: receiving an intermediate representation of the document comprising a plurality of edges scan-converted at a first predetermined resolution, the edges defining regions associated with region rendering instructions; generating two anti-aliased edges scan-converted at a second resolution lower than the first resolution, for at least one edge from the plurality of edges, wherein the anti-aliased edges separate an anti-aliasing region and regions associated with a single set of the region rendering instructions; associating the anti-aliased region with sets of the region rendering instructions corresponding to two or more neighbouring regions, to form a plurality of anti-aliased region rendering instructions; determining weighting coefficients for the anti-aliased region rendering instructions using edges in the intermediate representation; and generating an anti-aliased representation of the document for rendering at the second resolution using the plurality of anti-aliased region rendering instructions and the determined weighting coefficients.

According to another aspect of the present disclosure, there is provided a system for generating an anti-aliased representation of a document, the system comprising: a memory for storing data and a computer program; a processor coupled to the memory for executing the computer program, the computer program comprising instructions for: receiving an intermediate representation of the document comprising a plurality of edges scan-converted at a first predetermined resolution, the edges defining regions associated with region rendering instructions; generating two anti-aliased edges scan-converted at a second resolution lower than the first resolution, for at least one edge from the plurality of edges, wherein the anti-aliased edges separate an anti-aliasing region and regions associated with a single set of the region rendering instructions; associating the anti-aliased region with sets of the region rendering instructions corresponding to two or more neighbouring regions, to form a plurality of anti-aliased region rendering instructions; determining weighting coefficients for the anti-aliased region rendering instructions using edges in the intermediate representation; and generating an anti-aliased representation of the document for rendering at the second resolution using the plurality of anti-aliased region rendering instructions and the determined weighting coefficients.

According to still another aspect of the present disclosure, there is provided an apparatus for generating an anti-aliased representation of a document, the apparatus comprising: means for receiving an intermediate representation of the document comprising a plurality of edges scan-converted at a first predetermined resolution, the edges defining regions associated with region rendering instructions; means for generating two anti-aliased edges scan-converted at a second resolution lower than the first resolution, for at least one edge from the plurality of edges, wherein the antialiased edges separate an anti-aliasing region and regions associated with a single set of the region rendering instructions; means for associating the anti-aliased region with sets of the region rendering instructions corresponding to two or more neighbouring regions, to form a plurality of antialiased region rendering instructions; means for determining weighting coefficients for the anti-aliased region rendering instructions using edges in the intermediate representation; and means for generating an anti-aliased representation of the document for rendering at the second resolution using the plurality of anti-aliased region rendering instructions and the determined weighting coefficients.

According to still another aspect of the present disclosure, there is provided a computer readable medium having a computer program stored thereon for generating an anti-aliased representation of a document, the program comprising: code for receiving an intermediate representation of the document comprising a plurality of edges scan-converted at a first predetermined resolution, the edges defining regions associated with region rendering instructions; code for generating two anti-aliased edges scan-converted at a second resolution lower than the first resolution, for at least one edge from the plurality of edges, wherein the antialiased edges separate an anti-aliasing region and regions associated with a single set of the region rendering instructions; code for associating the anti-aliased region with sets of the region rendering instructions corresponding to two or more neighbouring regions, to form a plurality of anti-aliased region rendering instructions; code for determining weighting coefficients for the anti-aliased region rendering instructions using edges in the intermediate representation; and code for generating an anti-aliased representation of the document for rendering at the second resolution using the plurality of anti-aliased region rendering instructions and the determined weighting coefficients.

According to still another aspect of the present disclosure, there is provided a method of rendering an anti-aliased graphical representation, said method comprising: receiving a graphical representation comprising a plurality of edges scan converted at a predetermined resolution, the edges defining regions including an anti-aliased region, the antialiased region being associated with a plurality of sets of rendering instructions corresponding to two or more neighbouring regions and a weighting associated with the sets of rendering instructions; and rendering the anti-aliased graphical representation including the anti-aliased region, according to the sets of rendering instructions, the rendering instructions being combined in accordance with the weighting.

According to still another aspect of the present disclosure, there is provided a system for rendering an anti-aliased graphical representation, said system comprising: a memory for storing data and a computer program; a processor coupled to the memory for executing the computer program, the computer program comprising instructions for: receiving a graphical representation comprising a plurality of edges scan converted at a predetermined resolution, the edges defining regions including an antialiased region, the anti-aliased region being associated with a plurality of sets of rendering instructions corresponding to two or more neighbouring regions and a weighting associated with the sets of rendering instructions; and rendering the anti-aliased graphical representation including the anti-aliased region, according to the sets of rendering instructions, the rendering instructions being combined in accordance with the weighting.

According to still another aspect of the present disclosure, there is provided an apparatus for rendering an anti-aliased graphical representation, said apparatus comprising: means for receiving a graphical representation comprising a plurality of edges scan converted at a predetermined resolution, the edges defining regions including an anti-aliased region, the anti-aliased region being associated with a plurality of sets of rendering instructions corresponding to two or more neighbouring regions and a weighting associated with the sets of rendering instructions; and means for rendering the anti-aliased graphical representation including the anti-aliased region, according to the sets of rendering instructions, the rendering instructions being combined in accordance with the weighting.

According to still another aspect of the present disclosure, there is provided a computer readable medium having a computer program stored thereon for rendering an anti-aliased graphical representation, said program comprising: code for receiving a graphical representation comprising a plurality of edges scan converted at a predetermined resolution, the edges defining regions including an anti-aliased region, the anti-aliased region being associated with a plurality of sets of rendering instructions corresponding to two or more neighbouring regions and a weighting associated with the sets of rendering instructions; and code for rendering the anti-aliased graphical representation including the anti-aliased region, according to the sets of rendering instructions, the rendering instructions being combined in accordance with the weighting.

According to still another aspect of the present disclosure, there is provided a method of generating an anti-aliased representation of a document, the method comprising: receiving an intermediate representation of the document comprising a plurality of edges scan-converted at a first predetermined resolution, the edges defining regions associated with region rendering instructions; for at least one edge from the plurality of edges, generating an anti-aliasing region and a region associated with a single set of the region rendering instructions, the generated regions being separated by an anti-aliased edge scan-converted at a second resolution lower than the first resolution; associating the anti-aliased region with sets of the region rendering instructions corresponding to two or more neighbouring regions, to form a plurality of anti-aliased region rendering instructions; and generating an anti-aliased representation of the document for rendering at the second resolution using the plurality of anti-aliased region rendering instructions combined based on edges in the intermediate representation.

Other aspects of the invention are also disclosed.

BRIEF DESCRIPTION OF THE DRAWINGS

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

Fig. 1 is a schematic block diagram of a cloud printing system upon which the various arrangements described can be practiced;

Fig. 2 is an example of a software architecture for the mobile device shown in Fig. 1;

Fig. 3A and 3B collectively form a schematic block diagram of a general purpose computer system upon which arrangements of the printer server 110 described can be practiced;

Fig. 4A shows an exemplary page with graphic objects;

Fig. 4B show the pixel-aligned object edges of the graphic objects of the page of Fig. 4A;

Fig. 4C show a legend of levels for the page of Fig. 4A;

Fig. 5A show a fillmap representation of the page of Fig. 4A;

Fig. 5B shows a table of compositing stacks for the fillmap representation of Fig. 5A;

Fig. 5C shows a tiled fillmap representation of the page of Fig. 4A;

Fig. 6A shows an example fillmap representation;

Fig. 6B is a table mapping each edge of the fillmap representation of Fig. 6A to compositing stacks;

Fig. 6C shows a table of compositing stacks for the fillmap representation of Fig. 6A;

Fig. 7 shows an example anti-aliased fillmap representation, generated from the fillmap representation shown in Fig. 6;

Fig. 8 A shows a table of compositing stacks for the fillmap representation of Fig. 7

Fig. 8B shows weights associated with the edges of the anti-aliased fillmap representation shown in Fig. 7;

Fig. 9 is a schematic flow diagram showing a method of generating an anti-aliased fillmap as used in an anti-aliased fillmap generator in the disclosed arrangements;

Fig. 10 shows an example of anti-aliased edges part-way through generation of the example anti-aliased fillmap shown in Fig. 7;

Fig. 11 is a schematic flow diagram showing a method of generating candidate antialiased edges on an anti-aliased scan line, as executed in the method of Fig. 9;

Fig. 12 is a schematic flow diagram showing a method of generating candidate antialiased edges for an individual fillmap edge on an anti-aliased scan line, as executed in the method of Fig. 11;

Fig. 13 shows an example of the generation of candidate anti-aliased edges along an anti-aliased scan line of the example anti-aliased fillmap shown in Fig. 7;

Fig. 14 is a schematic flow diagram showing a method of generating anti-aliased edges for an anti-aliased scan line, as executed in the method of Fig. 9;

Fig. 15 is a schematic flow diagram showing a method of determining compositing stacks and weights for an anti-aliased pixel, as executed in the method of Fig. 14;

Fig. 16 is a schematic flow diagram showing a method of updating the anti-aliased edge for an anti-aliased pixel, as executed in the method of Fig. 14;

Fig. 17A is a table showing the current compositing stack for each fillmap scanline at each anti-aliased pixel along an example anti-aliased scan line shown in Fig. 7;

Fig. 17B shows contributing compositing stacks and weights for all anti-aliased pixels containing candidate edges on the anti-aliased scan line shown in Fig. 7;

Fig. 17C shows existing anti-aliased edges and candidate edges on anti-aliased scan lines for the example of Figs. 17A and 17B;

Fig. 18 is a schematic flow diagram showing a method of rendering an anti-aliased fillmap representation; and

Fig. 19A shows rendered anti-aliased pixels along an example anti-aliased scan line of the fillmap shown in Fig. 7; and

Fig. 19B shows the results of all anti-aliased scan lines of the fillmap of Fig. 7 being rendered according to the method Fig. 18.

DETAILED DESCRIPTION INCLUDING BEST MODE

Where 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.

Fig. 1 shows a schematic block diagram of a cloud printing system 100 for printing a document. The cloud printing system 100 includes a remote print server 110 connected to a print device 120 and a mobile device 130 through a communications network 140. The communications network 140 may be a wide-area network (WAN), such as the Internet, a cellular telecommunications network, or a private WAN. The network 140 may comprise multiple computers. Alternatively, the network 140 may be a single print server 110, a mobile device 130, and a print device 120. In one arrangement, the print server 110, print device 120 and mobile device 130 may be connected by cables used to communicate between devices via ports, such as a USB, serial, parallel or FireWire port.

The print server 110 comprises at least one server processor 111 for executing a software application 112. The software application 112 is configured to generate print fillmaps for pages of a document to be printed on the print device 120 and previewed on the mobile device 130. Each page may also be referred to as a document. A print fillmap, also known simply as a fillmap, is a compact region-based intermediate representation of a page of the document to be printed. A fillmap is a rasterised representation, meaning it represents graphic objects that have undergone rasterisation, typically at a first predetermined resolution being the resolution of the print device 120 that will ultimately print the page. The fillmap intermediate representation will be described in more detail with reference to Fig. 4 and Fig. 5.

The print device 120 comprises a print device processor 121 for executing a fillmap Tenderer software program 122, which is stored in a print device memory 123. The print device 120 also has a printer engine 125 coupled to the print device processor 121, via an interconnected bus 124. Upon receiving the intermediate representation in the form of a fillmap 201 (see Fig. 2) produced by a software application 112, the fillmap Tenderer 122 produces pixel data values for printing. The fillmap 201 may comprise a plurality of edges scan-converted at the first predetermined resolution. The edges of the print fillmap 201 define regions of a page of the document to be printed. Each edge of the print fillmap 201 may be associated with a compositing stack comprising rendering instructions for rendering the regions.

The pixel data values may then be stored in print device memory 123 and reproduced as pixels by the printer engine 125, for example. The fillmap Tenderer program 122 is executed by the print device processor 121.

The mobile device 130 comprises a mobile device processor 131 for executing an antialiased fillmap software program 132, which is stored in a mobile device memory 133. The mobile device processor 131 is coupled to the mobile device memory 133 via an interconnected bus 135. The operation of the anti-aliased fillmap software program 132 will be described in more detail below with reference to Fig. 2. The anti-aliased fillmap program 132 receives a high-resolution print fillmap 201 from the print server 110 and generates an anti-aliased fillmap 204, as seen in Fig. 2, at a second resolution lower than the first resolution. The anti-aliased fillmap 204 typically represents the same page as the print fillmap 201, but is at the resolution of mobile display 210 (i.e., the first predetermined resolution), and has undergone anti-aliasing and in order to display the page in a more visually pleasing manner. As described later, an antialiased fillmap is a similar data structure to a usual fillmap, with the exception that edges may refer to a plurality of compositing stacks each compositing stack comprising rendering instructions. The plurality of compositing stacks may be associated with an anti-aliased edge using neighbouring anti-aliased edges.

In generating the anti-aliased fillmap 204, the anti-aliased fillmap software program 132 may generate two anti-aliased edges scan-converted at the second resolution, for at least one edge from the plurality of edges of the print fillmap 201. The anti-aliased edges separate an anti-aliasing region and regions associated with a single set of the region rendering instructions. The anti-aliased fillmap software program 132 may also be configured for associating an antialiased region with sets of the region rendering instructions corresponding to two or more neighbouring regions, to form a plurality of anti-aliased region rendering instructions represented by one or more compositing stacks.

Each edge of the anti-aliased fillmap 204 also has associated weighting coefficients that indicate how the compositing stacks and associated anti-aliased region rendering instructions are to be combined. The anti-aliased fillmap software program 132 is configured for determining the weighting coefficients for an anti-aliased region rendering instructions using edges in the print fillmap 201.

As seen in more detail in Fig. 3A, the cloud print system 100 includes: the computer module 110 forming the print server; input devices such as a keyboard 302, a mouse pointer device 303, a scanner 326, a camera 327, and a microphone 380; and output devices including the print device 120, a display device 314 and loudspeakers 317. An external Modulator-Demodulator (Modem) transceiver device 316 may be used by the print server 110 for communicating to and from the communications network 140 via a connection 321. The communications network 140 may be a wide-area network (WAN), such as the Internet, a cellular telecommunications network, or a private WAN. Where the connection 321 is a telephone line, the modem 316 may be a traditional “dial-up” modem. Alternatively, where the connection 321 is a high capacity (e g., cable) connection, the modem 316 may be a broadband modem. A wireless modem may also be used for wireless connection to the communications network 140.

The print server 110 typically includes the at least one processor unit 111, and a memory unit 306. For example, the memory unit 306 may have semiconductor random access memory (RAM) and semiconductor read only memory (ROM). The print server 110 also includes a number of input/output (I/O) interfaces including: an audio-video interface 307 that couples to the video display 314, loudspeakers 317 and microphone 380; an FO interface 313 that couples to the keyboard 302, mouse 303, scanner 326, camera 327 another human interface device (not illustrated); and an interface 308 for the external modem 316 and the print device 120. In some implementations, the modem 316 may be incorporated within the print server 110, for example within the interface 308. The print server 110 also has a local network interface 311, which permits coupling of the print server 110 via a connection 323 to a local-area communications network 322, known as a Local Area Network (LAN). As illustrated in Fig. 3A, the local communications network 322 may also couple to the wide network 140 via a connection 324, which would typically include a so-called “firewall” device or device of similar functionality. The local network interface 311 may comprise an Ethernet™ circuit card, a Bluetooth™ wireless arrangement or an IEEE 802.11 wireless arrangement; however, numerous other types of interfaces may be practiced for the interface 311.

The FO interfaces 308 and 313 may afford either or both of serial and parallel connectivity, the former typically being implemented according to the Universal Serial Bus (USB) standards and having corresponding USB connectors (not illustrated). Storage devices 309 are provided and typically include a hard disk drive (HDD) 310. An optical disk drive 312 is typically provided to act as a non-volatile source of data. Portable memory devices, such optical disks (e.g., CD-ROM, DVD, Blu ray Disc™), USB-RAM, portable, external hard drives, and floppy disks, for example, may be used as appropriate sources of data to the system 100.

The components 306 to 313 of the print server 110 typically communicate via an interconnected bus 304 and in a manner that results in a conventional mode of operation of the computer system 100 known to those in the relevant art. For example, the processor 111 is coupled to the system bus 304 using a connection 318. Likewise, the memory 306 and optical disk drive 312 are coupled to the system bus 304 by connections 319. Examples of computers on which the described arrangements can be practised include IBM-PC’s and compatibles, Apple Mac™ or alike computer systems.

Methods described below may be implemented using the system 100 wherein one or more steps of the processes of Figs. 9, 11-12, 14-16 and 18 to be described, may be implemented as one or more code modules of the software application program 112 executable within the system 100. One or more of the steps of the described methods may be effected by instructions 331 (see Fig. 3B) in the software 112 that are carried out within the system 100.

As also described below, one or more steps of the processes Figs. 9, 11-12, 14-16 and 18 to be described, may be implemented as one or more of the code modules forming the antialiased fillmap program 132 executable within the mobile device 130. Again, one or more of the steps of the described methods may be effected by instructions, similar to the instructions 331 in the software 112.

The software instructions 331 implementing the software 112 may be formed as the 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 and the corresponding code modules performs the described methods and a second part and the corresponding code modules manage 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 112 is typically stored in the HDD 310 or the memory 306. The software is loaded into the system 100 from the computer readable medium, and is then executed by the system 100. A computer readable medium having such software or computer program recorded on the computer readable medium is a computer program product. The use of the computer program product in the system 100 preferably effects an advantageous apparatus for implementing the described methods.

In some instances, the application programs 112 may be supplied to the user encoded on one or more CD-ROMs 325 and read via the corresponding drive 312, or alternatively may be read by the user from the networks 140 or 322. Still further, the software can also be loaded into the system 100 from other computer readable media. Computer readable storage media refers to any non-transitory tangible storage medium that provides recorded instructions and/or data to the system 100 for execution and/or processing. Examples of such storage media include floppy disks, magnetic tape, CD-ROM, DVD, Blu-ray Disc™, a hard disk drive, a ROM or integrated circuit, USB memory, 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 print server 110. Examples of transitory or non-tangible computer readable transmission media that may also participate in the provision of software, application programs, instructions and/or data to the print server 110 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 e-mail transmissions and information recorded on Websites and the like.

The second part of the application program 112 and the corresponding code modules mentioned above may be executed to implement one or more graphical user interfaces (GUIs) to be rendered or otherwise represented upon the display 314. Through manipulation of typically the keyboard 302 and the mouse 303, a user of the system 100 and the application may manipulate the interface in a functionally adaptable manner to provide controlling commands and/or input to the applications associated with the GUI(s). Other forms of functionally adaptable user interfaces may also be implemented, such as an audio interface utilizing speech prompts output via the loudspeakers 317 and user voice commands input via the microphone 380.

Fig. 3B is a detailed schematic block diagram of the processor 111 and a “memory” 334. The memory 334 represents a logical aggregation of all the memory modules (including the HDD 309 and semiconductor memory 306) that can be accessed by the print system 110 in Fig. 3A.

When the print system 110 is initially powered up, a power-on self-test (POST) program 350 executes. The POST program 350 is typically stored in a ROM 349 of the semiconductor memory 306 of Fig. 3A. A hardware device such as the ROM 349 storing software is sometimes referred to as firmware. The POST program 350 examines hardware within the print server 110 to ensure proper functioning and typically checks the processor 111, the memory 334 (309, 306), and a basic input-output systems software (BIOS) module 351, also typically stored in the ROM 349, for correct operation. Once the POST program 350 has run successfully, the BIOS 351 activates the hard disk drive 310 of Fig. 3A. Activation of the hard disk drive 310 causes a bootstrap loader program 352 that is resident on the hard disk drive 310 to execute via the processor 111. This loads an operating system 353 into the RAM memory 306, upon which the operating system 353 commences operation. The operating system 353 is a system level application, executable by the processor 111, to fulfil various high level functions, including processor management, memory management, device management, storage management, software application interface, and generic user interface.

The operating system 353 manages the memory 334 (309, 306) to ensure that each process or application running on the print server 110 has sufficient memory in which to execute without colliding with memory allocated to another process. Furthermore, the different types of memory available in the system 100 of Fig. 3 A need to be used properly so that each process can run effectively. Accordingly, the aggregated memory 334 is not intended to illustrate how particular segments of memory are allocated (unless otherwise stated), but rather to provide a general view of the memory accessible by the system 100 and how such is used.

As shown in Fig. 3B, the processor 111 includes a number of functional modules including a control unit 339, an arithmetic logic unit (ALU) 340, and a local or internal memory 348, sometimes called a cache memory. The cache memory 348 typically includes a number of storage registers 344-346 in a register section. One or more internal busses 341 functionally interconnect these functional modules. The processor 111 typically also has one or more interfaces 342 for communicating with external devices via the system bus 304, using a connection 318. The memory 334 is coupled to the bus 304 using a connection 319.

The application program 112 includes a sequence of instructions 331 that may include conditional branch and loop instructions. The program 112 may also include data 332 which is used in execution of the program 112. The instructions 331 and the data 332 are stored in memory locations 328, 329, 330 and 335, 336, 337, respectively. Depending upon the relative size of the instructions 331 and the memory locations 328-330, a particular instruction may be stored in a single memory location as depicted by the instruction shown in the memory location 330. Alternately, an instruction may be segmented into a number of parts each of which is stored in a separate memory location, as depicted by the instruction segments shown in the memory locations 328 and 329.

In general, the processor 111 is given a set of instructions which are executed therein. The processor 111 waits for a subsequent input, to which the processor 111 reacts to by executing another set of instructions. Each input may be provided from one or more of a number of sources, including data generated by one or more of the input devices 302, 303, data received from an external source across one of the networks 140, 322, data retrieved from one of the storage devices 306, 309 or data retrieved from a storage medium 325 inserted into the corresponding reader 312, all depicted in Fig. 3 A. The execution of a set of the instructions may in some cases result in output of data. Execution may also involve storing data or variables to the memory 334.

The methods described below may use input variables 354, which are stored in the memory 334 in corresponding memory locations 355, 356, 357. The disclosed methods produce output variables 361, which are stored in the memory 334 in corresponding memory locations 362, 363, 364. Intermediate variables 358 may be stored in memory locations 359, 360, 366 and 367.

Referring to the processor 111 of Fig. 3B, the registers 344, 345, 346, the arithmetic logic unit (ALU) 340, and the control unit 339 work together to perform sequences of microoperations needed to perform “fetch, decode, and execute” cycles for every instruction in the instruction set making up the program 333. Each fetch, decode, and execute cycle comprises: (a) a fetch operation, which fetches or reads an instruction 331 from a memory location 328, 329, 330; (b) a decode operation in which the control unit 339 determines which instruction has been fetched; and (c) an execute operation in which the control unit 339 and/or the ALU 340 execute the instruction.

Thereafter, a further fetch, decode, and execute cycle for the next instruction may be executed. Similarly, a store cycle may be performed by which the control unit 339 stores or writes a value to a memory location 332.

One or more steps or sub-processes in the processes of Figs. 9, 11-12, 14-16 and 18 may be associated with one or more segments of the program 112 and is performed by the register section 344, 345, 347, the ALU 340, and the control unit 339 in the processor 111 working together to perform the fetch, decode, and execute cycles for every instruction in the instruction set for the noted segments of the program 112.

As described above, one or more steps of the processes of Figs. 9, 11-12, 14-16 and 18 to be described, may be implemented as one or more code modules of the anti-aliased fillmap program 132 executable within the mobile device 130. The code modules forming the antialiased fillmap program 132 are typically stored in the mobile device memory 130. The code modules forming the anti-aliased fillmap program 132 may be loaded into the mobile device 130 from the computer readable medium, and then executed by the mobile device 130. A computer readable medium having such software or computer program recorded on the computer readable medium is a computer program product. The use of the computer program product in the mobile device 130 preferably effects an advantageous apparatus for implementing one or more steps of the described methods.

In some instances, the anti-aliased fillmap program 132 may be supplied to the user encoded on one or more CD-ROMs, similar to the CD-ROMs 325, or alternatively may be read by the user from the networks 140 or 322. Still further, software code modules for the antialiased fillmap program 132 may also be loaded into the system 100 from other computer readable media.

The code modules implementing the anti-aliased fillmap program 132 may be executed by the mobile processor 131 in a similar manner to the code modules implementing the software application program 112 as described above.

The described methods may alternatively be implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of the described methods. Such dedicated hardware may include graphic processors, digital signal processors, or one or more microprocessors and associated memories.

Fig. 2 shows a software architecture for the anti-aliased fillmap program 132 as executed on the mobile device 130. Each module 203 and 205 described below may be formed by one or more of the code modules of the anti-aliased fillmap program 132.

The software application 112, executing on the print server 110, provides printable page 201 to the mobile device 130 for print preview using the mobile display 210 of the mobile device 130. The printable page 201 is provided in the form of a fillmap representation, as described below with reference to Fig. 4 and Fig. 5. However, the printable page 201 may be provided in another form. The fillmap representation, hereafter also referred to as a fillmap, is typically produced for printing, and will be of (high) print resolution, typically at the resolution of the print device 120. The fillmap is stored in the mobile device memory 133.

An anti-aliased fillmap generator module 203, under execution of the processor 131, receives the print fillmap 201 and generates an anti-aliased fillmap 204 representation in the form of an anti-aliased fillmap 204. The anti-aliased fillmap 204 is of the same resolution as the mobile display 210 (i.e., the second resolution described above). The anti-aliased fillmap 204 may then be used by the mobile device 130 for rendering the page represented by the antialiased fillmap 204, at the second resolution, using the plurality of anti-aliased region rendering instructions and the determined weighting coefficients associated with the edges of the antialiased fillmap 204 as described above. The mobile device 130 uses an anti-aliased fillmap Tenderer module 205, under execution of the processor 131, to render the anti-aliased fillmap 204 to pixel data values 206. The pixel data values 206 are displayed on the display 210 of the mobile device 130. Because the pixel data 206 has been generated from an anti-aliased fillmap 204, the image on the mobile display 210 is visually pleasing, without jagged edges.

The anti-aliased fillmap generator module 203 and anti-aliased fillmap Tenderer module 205 may be implemented as one or more code modules of the anti-aliased fillmap program 132 which is executed by the mobile processor 131 within the mobile device 130. The anti-aliased fillmap generator module 203 will be described in more detail later with reference to Fig. 9 to Fig. 16.

The software architecture and operation of the mobile device 130 is similar to that of the print server 110 in terms of storage and execution of the program 132 by the memory 133 and the processor 131, respectively. In addition, the software architecture and operation of the print device 120 is similar to that of the print server 110 in terms of storage and execution of the program 122 by the memory 123 and the processor 121, respectively. As such, the foregoing description of the print server 110 is generally applicable to the printing system 100, including the mobile device 130. A fillmap representation (or “fillmap”) of a graphical image such as a page will now be described in more detail. This description applies generally to both high-resolution print fillmaps, such as print fillmap 201, and anti-aliased fillmaps, such as anti-aliased fillmap 204. A fillmap is a region-based representation of a page. The fillmap maps a region of pixels within the page to a compositing stack which will be composited to generate the colour data for each pixel within that fillmap region. Multiple fillmap regions within a fillmap can map to the same compositing stack comprising region rendering instructions for rendering the fillmap regions. Fillmap regions within the fillmap do not overlap and therefore each pixel in the rendered page only belongs to a single fillmap region. Each fillmap region within the fillmap is defined by a set of pixel-aligned fillmap edges which activate the compositing stack associated with that fillmap region. Pixel-aligned fillmap edges, also known as fillmap edges or simple edges: (i) are monotonically increasing in the >'-di recti on of the page; (ii) do not intersect with each other; (iii) are aligned with pixel boundaries, meaning that each pixel-aligned fillmap edge consists of a sequence of segments, each of which follows a boundary between two contiguous pixels; (iv) contain a reference to the compositing stack required to be composited to render to pixels the fillmap region to which the pixel-aligned fillmap edge belongs; and (v) activate pixels within a single fillmap region.

In one arrangement, references to compositing stacks are indices into a table of compositing stacks.

On any given scan line, starting at a fillmap edge which activates a fillmap region, and progressing in the direction of increasing x, the fillmap region remains active until a second fillmap edge which activates a further fillmap region is encountered. When the second fillmap edge is encountered, the active fillmap region is deactivated, and the fillmap region corresponding to the second fillmap edge is activated.

Within a fillmap, the compositing stacks active within each fillmap region of pixels is stored in the table of compositing stacks. A compositing stack is a sequence of z-ordered levels, where each level contains attributes such as a fill, the opacity of the level, a compositing operator, and the priority, or z-order, of the level. The operator determines how to mix the colour data of a level with other overlapping levels. A fill specifies the colour or appearance of a single object. A fill may be a flat fill representing a single colour, a blend representing a colour which varies according to a predetermined function such as a linear gradient or sinusoid, a bitmap image, or a tiled (i.e. repeated) image. A compositing stack contains references to all the levels which contribute colour to the pixels within a fillmap region. The table of compositing stacks contains all of the compositing stacks required to render the page to pixels. The table of compositing stacks does not contain duplicate instances of identical compositing stacks. Hence, multiple fillmap regions within a fillmap, which map to the same compositing stack, map to the same instance of the compositing stack within the table of compositing stacks.

The generation of a fillmap (or intermediate) representation of a page will now be described with reference to Figs. 4A, 4B, 4C, 5A, 5B and 5C. Fig. 4A shows a page representation 400. The page 400 has a white background and two graphic objects 401 and 402 over a white background. The first graphic object 401 is an opaque “T” shaped object with a right-leaning hatched fill. The second graphic object 402 is a partially transparent (translucent) square with a left-leaning hatched fill. The second graphic object 402 partially overlaps the first graphic object 401.

Fig. 4B shows the decomposition of the graphic objects 401 and 402 of the page 400 into pixel-aligned graphic object edges (also referred to simply as object edges), levels and fills according to a pixel grid 420, with Fig. 4C showing a legend of corresponding levels. A graphic object is decomposed into two or more object edges, a single level, and one or more fills. Object edges define the activation or deactivation of a level during rasterisation. Object edges therefore refer to the level of the object from which the object edges are derived. The first graphic object 401 is decomposed into two object edges 421 and 422, and a level 432 that consists of a right-leaning hatched fill. Object edges 421 and 422 refer to the level 432 of the first graphic object 401. The second graphic object 402 is decomposed into two object edges 423 and 424, and a level 433 that consists of a transparent left-leaning hatched fill. Object edges 423 and 424 refer to the level 433 of the second graphic object 402. The background 425 has a level 431 that consists of white fill.

Fig. 5 A shows a fillmap representation 540 of the page 400 represented in Fig. 4A, with a table of compositing stacks being shown in Fig. 5B. The fillmap representation 540 is composed of five fillmap edges. Each edge is associated with a reference to a compositing stack comprising appearance information which will be used to determine the colour of each of the pixels activated by that edge. On any given scan line on which an edge is active, the edge will activate those pixels which are immediately to the right of the edge, until the next edge or a page boundary is encountered. First edge 541 traces a left hand boundary of the page 400, and references a compositing stack 551 which contains a single opaque level to be filled using the background fill. Second edge 542 traces a left hand boundary of the first graphic object 401, and references a compositing stack 552 that contains a single level which is opaque and is to be filled using a right-leaning hatched fill. Third edge 543 references the same compositing stack 551 as the first edge 541. Fourth edge 544 traces the left hand boundary of the region where the second object 402 overlaps the white background. The fourth edge 544 references a compositing stack 554 which contains two levels. The top most level is transparent and is to be filled using a left-leaning hatched fill. The bottom most level is opaque and is to be filled using the background fill. Fifth edge 545 traces the left hand boundary of the region where the second graphic object 402 overlaps the first graphic object 401. The fifth edge 545 references a compositing stack 553 which contains two levels. The top most level is transparent and is to be filled using a left-leaning hatched fill. The bottom most level is opaque and is to be filled using a right-leaning hatched fill.

Accompanying the fillmap representation 540 of the page 400 is a table of compositing stacks equivalent to that shown in Fig. 5B which contains the compositing stacks 551, 552, 553 and 554 referenced by the edges contained in the fillmap representation 540 of the page 400.

Fig. 5C shows a tiled fillmap representation 560 of the page 400 represented in Fig. 4A. The tiled fillmap contains four tiles 565, 570, 575 and 580. Each tile has a height and width of eight pixels. In order to generate the tiled fillmap representation 560 of the page 400, the edges of the original fillmap representation 540 have been split across fillmap tile boundaries. For example, edge 541, which traces the left hand boundary of the page in the untiled fillmap representation 540 shown in Fig. 5A, has been divided into two edges 566 and 576. The first edge 566 activates pixels in the top-left hand tile 565, while the second edge 576 activates pixels in the bottom-left hand tile 575. Also, new edges have been inserted on the tile boundaries to activate the left most pixels of each tile which were previously activated by an edge in a tile to the left of the tile in which the pixels reside. For example, in the top-right tile 570, a new edge 571 has been inserted to activate pixels which were activated by edge 542 which traces the left hand boundary of the first graphic object 401 in the original fillmap representation 540 shown in Fig. 5A.

While this description of the fillmap representation also applies to anti-aliased fillmaps, the edges of anti-aliased fillmaps can reference multiple compositing stacks, and weights associated with those compositing stacks. An example of an anti-aliased fillmap is described later with reference to Fig. 7 and Fig. 8.

The described methods generate an anti-aliased fillmap representation of a page, based on a high-resolution fillmap representation. The described methods enable the rendering of an anti-aliased fillmap representation to anti-aliased pixel data that, for example, can be viewed on a mobile device for the purpose of print preview.

The generation of an anti-aliased fillmap is based on fillmap edge data rather than pixel data. Therefore, not all pixels of the page are processed and the low-resolution anti-aliased fillmap is generated quickly, compared with conventional methods. The anti-aliased fillmap is also edge-based, and therefore consumes little memory, compared with conventional methods that generate anti-aliased pixel data immediately. Since the anti-aliased fillmap 204 is compact, the anti-aliased fillmap 204 can be efficiently and quickly transferred across a network. The anti-aliased fillmap 204 can also be rendered quickly to pixel data using existing fillmap rendering software that is largely unchanged.

An example of a high-resolution fillmap 600 is shown in Fig. 6A. The fillmap 600 represents a page containing graphic objects. The graphic objects include a white background, a circle with a grey flat fill, and a triangle with a hatched fill as shown in Fig. 6A. The triangle with the hatched fill is semi-transparent and has a higher priority than the circle with the grey flat fill. In addition, the triangle with the hatched fill partially overlaps the circle with the grey flat fill.

The regions of the page formed by the graphic objects are represented by six fillmap edges 611 - 616. Compositing stacks for the high-resolution fillmap 600 are shown in a table of compositing stacks 630 as shown in 6C. “Compositing stack 1” 631 contains only the background fill. “Compositing stack 2” 632 contains only the semi-transparent hatched fill. “Compositing stack 3” 633 contains only grey flat fill. “Compositing stack 4” 634 contains both the semi-transparent hatched fill (with highest priority) and the grey flat fill.

As described with reference to Fig. 4 and Fig. 5, each fillmap edge has reference to an associated compositing stack. The association between each of the edges of the high-resolution fillmap 600 and the compositing stacks 631, 632, 633 and 634 is shown in table 640, as seen in Fig. 6B, which maps each edge to an associated compositing stack. For example, fillmap edge ‘2’ 612 is associated with compositing stack ‘2’ 632 with a semi-transparent hatched fill.

As seen in Fig. 6A, high-resolution fillmap pixels are shown as bounded by solid and dashed lines, such as fillmap pixel 601. An example of the generation of a low-resolution antialiased fillmap using high resolution fillmap 600 will later be described with reference to Fig. 7 to 17. Because an output anti-aliased fillmap determined in accordance with the described methods is of lower resolution than a corresponding input fillmap, the anti-aliased pixels are larger than the input fillmap pixels. A single anti-aliased pixel will, in most cases, represent an area of a page represented by several fillmap pixels. Lower-resolution anti-aliased pixels of an anti-aliased fillmap are shown in Fig. 6A as bounded by solid lines, such as anti-aliased pixel 602. Anti-aliased pixel 602 represents the same area of the page as represented by four fillmap pixels.

The fillmap 600 contains twenty-four (24) scan lines, each containing twenty-four (24) high-resolution pixels. In the example of Fig. 6A, the anti-aliased fillmap will be of half the resolution as the input fillmap, in both x and y. Therefore, the anti-aliased fillmap will contain twelve (12) anti-aliased scan lines, each containing twelve (12) anti-aliased pixels. An antialiased scan line is a scan line in the anti-aliased fillmap 204 being generated at a resolution less than that of the input print fillmap 201. An anti-aliased scan line represents a row of anti-aliased pixels, being pixels in the anti-aliased fillmap. Typically, the anti-aliased fillmap 204 will be of the same resolution as the mobile display 210. The scan line numbers of the first three antialiased scan lines (0 to 2) 650-652 are shown in Fig. 6A. Anti-aliased scan line 2 652 overlaps two fillmap scan lines 4 674 and 5 675. Also shown in Fig. 6A are indexes (e.g. 661, 662 and 663) of the twelve (12) anti-aliased pixels along each anti-aliased scan line.

An example of a low-resolution anti-aliased fillmap 700 is shown in Fig. 7. The antialiased fillmap 700 is produced by the anti-aliased fillmap generator module 203 by executing a method 900 of generating an anti-aliased fillmap, described with reference to Fig. 9 to Fig. 17. The anti-aliased fillmap 700 has been produced by anti-aliasing the high-resolution fillmap 600 described previously with reference to Fig. 6.

The anti-aliased fillmap 700 contains anti-aliased edges 711-719. An anti-aliased edge is similar to a fillmap edge, but is of the same resolution as the anti-aliased fillmap. Each antialiased edge is associated with a reference to appearance information contributing to the antialiased edge. The appearance information is in the form of compositing stacks and associated weights. Each anti-aliased edge may also be associated with coverage information specifying the contribution of appearance information to pixels in a region. As described below, an antialiased edge may also activate multiple compositing stacks, and have associated weights. An anti-aliased edge can be either a solid edge (e.g. edge ‘2a’ 712) or a transition edge (e.g. edge ‘2b’ 713). A solid edge activates pixels that are to be rendered using a single compositing stack, without anti-aliasing. Pixels rendered using a solid edge have not typically undergone antialiasing. A transition anti-aliased edge activates pixels that are to be rendered using multiple compositing stacks, anti-aliased using the associated weights. Each pixel in the region is rendered using a weighted combination of the compositing stacks associated with the transition anti-aliased edge. Pixels rendered using a transition edge have undergone anti-aliasing. In Fig. 7, solid edges are shown as thick solid lines, while transition edges are shown as thick dashed lines.

Fig. 7 shows the same grid of high-resolution pixels (bounded by thin solid and thin dashed lines) and low-resolution anti-aliased pixels (bounded by thin solid lines only) as Fig. 6A. However, note that the anti-aliased edges of Fig. 7 are aligned to the borders of anti-aliased pixels only (thin solid lines).

The anti-aliased fillmap generator module 203 produces one or more anti-aliased edges for each input fillmap edge. For example, two anti-aliased edges 712 (i.e., edge ‘2a’) and 713 (i.e., edge ‘2b’) have been generated using fillmap edge 612 (i.e., edge ‘2’), shown in Fig. 6A. Anti-aliased edge 712 (i.e., edge ‘2a’) is a solid edge, and anti-aliased edge 713 (i.e., edge ‘2b’) is a transition edge. The anti-aliased edges generated from a fillmap edge will usually consist of both solid edges and transition edges, but not always. For example, only a solid edge 711 (i.e., edge ‘1’) has been generated from fillmap edge 611, since fillmap edge 611 is aligned only to the border between anti-aliased edges, and therefore does not need to undergo anti-aliasing.

Figs. 8A and 8B show an example of a mapping between anti-aliased edges and compositing stacks, and the associated weights, for the anti-aliased fillmap 700 shown in Fig. 7. A table of compositing stacks 630 previously shown in Fig. 6C is repeated in Fig. 8A. The table of compositing stacks 630 is identical to the table of compositing stacks associated with the input high-resolution fillmap, and contains four compositing stacks 631-634.

The table 840 associating anti-aliased edges with compositing stacks and weights is also shown in Fig. 8B. Each anti-aliased edge is firstly associated with one or more compositing stacks. A solid edge has only a single associated compositing stack. For example, solid edge ‘2a’ 712 is associated with compositing stack ‘2’ 632. A transition edge will have two or more associated compositing stacks. For example, transition edge ‘2b’ 713 is associated with ‘compositing stack 2’ 632 and ‘compositing stack Γ 631.

Each transition edge of the anti-aliased fillmap 700 is secondly associated with a sequence of weights that specify how to combine the two or more compositing stacks in order to render each pixel activated by the edge. The weights can be encoded in several ways. In one arrangement, shown in Fig. 8B, each set of square brackets contains the weights for a single scan line of pixels. Within each scan line, each set of parentheses contains the weights for a single pixel. For example, weights 841 associated with transition edge ‘2b’ 713 contain six sets of square brackets, each containing weights for a single scan line of anti-aliased pixels rendered using edge ‘2b’ 713. The first, second, fourth, fifth and sixth set of square brackets shown in Fig. 8B contain a single set of parentheses, indicating that the edge ‘2b’ 713 activates only one anti-aliased pixel on the associated scan lines. The third set of square brackets contains two sets of parentheses, indicating that the edge ‘2b’ 713 activated two anti-aliased pixels on the third scan line that the edge 713 intersects.

Each set of parentheses of Fig. 8B contains one or more numbers, each number being a weight. Each weight specifies how much a particular compositing stack contributes to the rendering of an anti-aliased pixel. In one arrangement, as shown in Fig. 8, there is a weight for all compositing stacks associated with the edge, except the last compositing stack. The weight of the last compositing stack can be calculated using the weights of the other compositing stacks, and can therefore be discarded in order to consume less memory. In the example of Figs. 7, 8A and 8B, each anti-aliased pixel corresponds to four fillmap pixels, as described previously with reference to Fig. 6. Therefore, the weight of the last compositing stack is calculated by subtracting the weights of the other compositing stacks from the number four. For example, the set of parentheses 851 corresponding to the first pixel of the first scan line activated by transition edge ‘2b’ 713 contains the weight value of “3”. The weight value of “3” in the set of parentheses 851 indicates that the corresponding anti-aliased pixel is to be rendered using three portions of ‘compositing stack 2’ 632 and one portion of ‘compositing stack Γ 631.

Note that there are several other ways that the weights can be represented. The weights can also be compressed to reduce memory further, for example, by difference-encoding the values.

The method 900 of generating an anti-aliased fillmap 204 will now be described with reference to Fig. 9. The method 900 may be implemented as one or more software code modules of the anti-aliased fillmap software program 132 resident in the memory 133 and being controlled in its execution by the processor 131. The one or more software code modules of the anti-aliased fillmap software program 132 implementing the method 900 may form the antialiased fillmap generator 203.

The method 900 begins at initialisation step 905, where the anti-aliased fillmap is initialised within the memory 133 under execution of the processor 131. The number of antialiased scan lines and the number of anti-aliased pixels per scan line is determined using the resolution of the mobile display 210. The compositing stack table from the input high-resolution fillmap is also copied to the anti-aliased fillmap. The method 900 then proceeds to decision step 910, where if there are anti-aliased scan lines remaining to be processed then the method 900 proceeds to step 920. Otherwise, the method 900 concludes.

If it is determined at decision step 910 that there are anti-aliased scan lines remaining to be processed, then the method 900 proceeds to step 920, where the candidate anti-aliased edges on a next anti-aliased scan line are generated under execution of the processor 131. One or more candidate anti-aliased edges are generated for each fillmap edge that intersects the antialiased scan line. A candidate anti-aliased edge, also known as a candidate edge, represents the location of a potential edge along an anti-aliased scan line. As described later, candidate edges are used as intermediate data to form anti-aliased edges in the final anti-aliased fillmap, and are subsequently deleted. A method 1100 of generating candidate anti-aliased edges on an antialiased scan line, is described in more detail with reference to Fig. 11. The candidate antialiased edges on a next anti-aliased scan line as generated at step 920 may be stored in the memory 133 under execution of the processor 131.

The method 900 then proceeds to generating step 930, where the final anti-aliased edges for the anti-aliased scan line are generated. A final anti-aliased edge, also known as an antialiased edge, is an edge that will appear in the generated anti-aliased fillmap. Final anti-aliased edges are generated using the candidate anti-aliased edges. A method 1400 of generating final anti-aliased edges for an anti-aliased scan line, as executed at step 930, will be described in more detail below with reference to Fig. 14. The final anti-aliased edges for the anti-aliased scan line generated at step 930 may be stored in the memory 133 under execution of the processor 131.

Upon completion of step 930, the method 900 returns to decision step 910. If at decision step 910 it is determined that there are no anti-aliased scan lines remaining, then the anti-aliased fillmap 204 has been generated and the method 900 concludes. The anti-aliased fillmap 204 generated in accordance with the method 900 may be stored in the memory 133.

An example of generating the anti-aliased edges on anti-aliased scan line ‘2’ 652 of the anti-aliased fillmap 700 will now be described with reference to Figs. 10A and 10B. Fig. 10A shows the intersection of three fillmap edges ‘1’ 611, ‘2’ [6] 12 and ‘3’ 613 with anti-aliased scan lines ‘Γ 651 and ‘2’ 652. Also shown are the fillmap scan lines ‘4’ 674 and ‘5’ 675 overlapped by anti-aliased scan line ‘2’ 652. Shown hatched are the fillmap pixels activated by fillmap edge ‘2’ 612. In the following description, anti-aliased edges will be generated from the fillmap edges‘1’ 611, ‘2’ [6]12and‘3’ 613.

Fig. 10B shows the anti-aliased edges 711-715 generated by processing anti-aliased scan lines ‘0’ and ‘1’ 651. At the stage shown in the example of Fig. 10B, the method 900 executed by the anti-aliased fillmap generator module 203 has completed steps 920 and 930 for antialiased scan lines ‘0’ and ‘ 1’ 651, and is about to start step 920 for anti-aliased scan line ‘2’ 652. Anti-aliased edges 711-715 were previously described with reference to Fig. 7 in their complete form (after all anti-aliased scan lines have been processed).

Anti-aliased edge ‘1’ 711 is a solid edge that has been generated from fillmap edge ‘1’ 611. Anti-aliased edge ‘1’ 711 is a solid edge that started prior to anti-aliased scan line ‘1’ 651 (anti-aliased edge ‘Γ 711 activates anti-aliased pixels on scan line 0). Anti-aliased edge ‘2a’ 712 is a solid edge that has been generated from fillmap edge ‘2’ 612. Anti-aliased edge ‘2a’ 712 started at anti-aliased scan line ‘1’ 651. Anti-aliased edge ‘2b’ 713 is a transition edge that has been generated from fillmap edge ‘2’ 612. Anti-aliased edge ‘2b’ 713 started prior to antialiased scan line ‘1’ 651. Anti-aliased edge ‘3a’ 714 is a solid edge that has been generated from fillmap edge ‘3’ 613. Anti-aliased edge ‘3a’ 714 started prior to anti-aliased scan line ‘1’ 651. Anti-aliased edge ‘3b’ 715 is a transition edge that has been generated from fillmap edge ‘3’ 613. Anti-aliased edge ‘3b’ 715 started at anti-aliased scan line ‘1’ 651.

The anti-aliased fillmap generation method 900 generates one or more anti-aliased edges for each fillmap edge. However, due to the lower resolution of the anti-aliased fillmap, some anti-aliased pixels may be intersected by more than one anti-aliased edge. Therefore, the anti-aliased fillmap generator module 203 cannot simply generate anti-aliased edges for each fillmap edge in isolation. The method 900 therefore generates anti-aliased edges in scan line order. So that anti-aliased edges can be connected between anti-aliased scan lines, each antialiased edge that has not yet ended (at the current scan line) is associated with a fillmap edge that contributes to the appearance of the anti-aliased edge. Then, when the position of an antialiased edge is identified on a new scan line, the method 900 can use anti-aliased edges associated with a fillmap edge to attempt to extend an existing anti-aliased edge to activate pixels at the position.

Also shown in Fig. 10B are the anti-aliased edges associated with each fillmap edge at the stage of execution of the method 900 (i.e., immediately before processing anti-aliased scan line ‘2’ 652). Fillmap edge ‘Γ 611 has a single (solid) anti-aliased edge ‘Γ 711 associated with the edge ‘Γ 611. Fillmap edge ‘2’ 612 has a solid anti-aliased edge ‘2a’ 712 associated with the edge ‘2’ 612, and a transition anti-aliased edge ‘2b’ 713 associated with the fillmap edge ‘2’ 612. Fillmap edge 3 613 has a solid anti-aliased edge ‘3a’ 714 associated with the edge ‘3’ 613, and a transition anti-aliased edge ‘3b’ 715 associated with the edge ‘3’ 613.

The method 1100 of generating candidate anti-aliased edges, as executed at step 920, will now be described with reference to Fig. 11. As described below, the anti-aliased edges may span multiple scanlines in an anti-aliased fillmap 204. The method 900 may be implemented as one or more software code modules of the anti-aliased fillmap software program 132 resident in the memory 133 and being controlled in its execution by the processor 131.

The method 1100 starts at retrieval step 1110, where the fillmap edges that intersect the anti-aliased scan line are retrieved under execution of the processor 131. An anti-aliased scan line typically spans several fillmap scan lines, since the anti-aliased scan line is of lower resolution. At step 1110, any fillmap edge that intersects one of the fillmap scan lines that is spanned by the anti-aliased scan line is retrieved. The retrieved edges may be stored in the memory 133.

The method 1100 then proceeds to sorting step 1120 where the retrieved fillmap edges stored within the memory 133 are sorted according to their x-positions, from smallest value to largest value. A first fillmap edge is deemed to be to the left of a second fillmap edge if, for the fillmap scan lines that both edges intersect, the x-positions of the first fillmap edge are less than the x-positions of the second fillmap edge. As described previously with reference to Fig. 5, fillmap edges do not cross. Therefore, fillmap edges can be sorted in accordance with step 1120 over a range of scan lines.

The method 1100 then proceeds to decision step 1130, where the sorted fillmap edges are looped over, by deciding if there are more fillmap edges in the sorted edges that have not yet been processed. If it is determined that there are more fillmap edges to process, then the method 1100 proceeds to step 1140, where the next fillmap edge in the fillmap edges sorted at step 1120 is retrieved from memory 133. The method 1100 then proceeds to step 1150 where candidate edges for the next fillmap edge are generated under execution of the processor 131. A method 1200 of generating candidate anti-aliased edges for an individual fillmap edge on an anti-aliased scan line, as executed at step 1150, will described in more detail with reference to Fig. 12.

The method 1100 then proceeds to storing step 1160, where the candidate edges generated at step 1150 are stored in the memory 133 at the x-positions at which the candidate edges intersect the anti-aliased scan line. Upon completion of step 1160, processing returns to decision step 1130. If, at decision step 1130, there are no more fillmap edges that intersect the anti-aliased scan line, then the method 1100 concludes.

The method 1200 of generating anti-aliased candidate edges for a fillmap edge on an anti-aliased scan line, as executed at step 1150, will now be described with reference to Fig. 12. The method 1200 may be implemented as one or more software code modules of the anti-aliased fillmap software program 132 resident in the memory 133 and being controlled in its execution by the processor 131.

The method 1200 starts at decision step 1210, where the processor 131 is used to determine if the fillmap edge intersects all fillmap scan lines spanned by the anti-aliased scan line by analysing the fillmap scan lines for a given anti-aliased scan line. If it is determined that the fillmap edge does not intersect all fillmap scan lines (i.e., the edge ends before the last fillmap scan line), then the method 1200 proceeds to generating step 1220. At generating step 1220, transition candidate edges are generated under execution of the processor 131. The generated candidate edges may be stored in the memory 133. A transition candidate edge is generated for each anti-aliased pixel intersected by the fillmap edge. Since the fillmap edge does not activate all fillmap scan lines spanned by the anti-aliased scan line, the compositing stack of each anti-aliased pixel that the fillmap edge contributes to will also contain the compositing stack of other fillmap edges. A solid anti-aliased edge is therefore not generated at step 1220. An example of this case is shown in Fig. 6 and 7, where the fillmap edge ‘2’ 612 intersects anti-aliased scan line ‘5’ 653, resulting in anti-aliased edge ‘2b’ 713 on anti-aliased scan line ‘5’ 653, but not solid edge ‘2a’ 712. The method 1200 concludes upon completion of step 1220.

If it is determined at step 1210 that the fillmap edge does intersect all fillmap scan lines spanned by the anti-aliased scan line, then the method 1200 proceeds to decision step 1230. At step 1230, it is determined if the fillmap edge traverses the border between two anti-aliased pixels without entering one of the two anti-aliased pixels. If it is decided that the fillmap edge traverses the border between anti-aliased pixels, then the method 1200 proceeds to generating step 1240. At step 1240, a single solid candidate edge is generated under execution of the processor 131. The generated solid candidate edge may be stored in the memory 133 under execution of the processor 131. In this case, the fillmap edge does not cause anti-aliasing to occur on the anti-aliased scan line, so transition candidate edges are not required for the fillmap edge. Examples of this case are shown in Fig. 7, for example, where anti-aliased edge ‘1’ 711 does not cause anti-aliasing to occur. The method 1200 ends upon completion of step 1240.

If it is determined at step 1230 that the fillmap edge does not traverse the border between anti-aliased pixels, then the method 1200 proceeds to step 1250, where both transition edges and a solid candidate edge are generated under execution of the processor 131. The generated transition edges and solid candidate edge generated at step 1250 may be stored in the memory 133 under execution of the processor 131. A transition candidate edge is generated for each anti-aliased pixel intersected by the fillmap edge. The solid candidate edge is required for the anti-aliased pixel to the right of the right-most transition candidate edge. The solid antialiased edge to the right of the right-most transition candidate edge will typically activate pixels within a region that do not undergo anti-aliasing. For example, in Fig. 7, anti-aliased edge ‘2a’ 712 activates pixels that do not undergo anti-aliasing. The method 1200 ends upon completion of step 1250.

Fig. 13 shows an example of the candidate edges 1351-1356 generated for anti-aliased scan line ‘2’ 652 of anti-aliased fillmap 700. The method 1100 of generating candidate edges for an anti-aliased scan line was described previously with reference to Fig. 11 and Fig. 12. The generation of the example candidate edges 1351-1356 will now be described with reference to steps of the method 1100.

As at step 1110, the fillmap edges that intersect the anti-aliased scan line 2 652 are retrieved under execution of the processor 131. As shown in Fig. 6, the fillmap edges this antialiased scan line are fillmap edges ‘Γ 611, ‘2’ 612 and ‘3’ 613. At step 1120, the fillmap edges are sorted in x, from left to right, resulting in the order ‘Γ 611, ‘2’ 612 then ‘3’ 613.

Steps 1140, 1150 and 1160 are then executed for each fillmap edge in the order determined at step 1120. An example of executing steps 1140, 1150 and 1160 for fillmap edge ‘2’ 612 on anti-aliased scan line ‘2’ 652 will now be described. As at step 1140, fillmap edge ‘2’ 612 will be retrieved.

Then as at step 1210 of method 1200, it is determined that fillmap edge ‘2’ 612 intersects both fillmap scan lines ‘4’ 674 and ‘5’ 675 spanned by anti-aliased scan line ‘2’ 652, as seen in Fig. 10A. As at step 1230 of the method 1200, it is determined that fillmap edge ‘2’ 612 does not traverse the border between anti-aliased pixels, as seen in Fig. 10A. As at step 1250, transition candidate edges and a solid candidate edge are generated.

As seen in Fig. 10A, fillmap edge ‘2’ 612 intersects anti-aliased scan line 652 at antialiased pixels at x-positions ‘4’ 661 and ‘5’ 662. At both of the positions ‘4’ 661 and ‘5’ 662, fillmap edge ‘2’ 612 activates a subset of the high-resolution fillmap pixels within each antialiased pixel, rather than activating all fillmap pixels. As such, the anti-aliased pixels at x-positions ‘4’ 661 and ‘5’ 662 are rendered using more than one compositing stack associated with more than one fillmap edge. Transition edges are therefore required to activate the antialiased pixels x-positions ‘4’ 661 and ‘5’ 662. Therefore, at step 1250 of the method 1200, candidate transition edges ‘2’ 1352 and ‘3’ 1353 are generated.

To the right of the pixel at position ‘5’ 662, fillmap edge ‘2’ 612 activates anti-aliased pixels that are not intersected by fillmap edge ‘2’ 612. The activated anti-aliased pixels to the right of the pixel at position ‘5’ 662 are therefore rendered using a single compositing stack (i.e., compositing stack ‘2’ 632). Therefore, as at step 1250 of the method 1200 a candidate solid edge ‘4’ 1354 is also generated, at the x-position ‘6’ 663 immediately following the right-most candidate transition edge ‘3’ 1353.

As at step 1160 of the method 1100, the generated candidate edges ‘2’ 1352, ‘3’ 1353 and ‘4’ 1354 are stored within memory 133, for example, at the x-position of the first antialiased pixel that each of the generated candidate edges ‘2’ 1352, ‘3’ 1353 and ‘4’ 1354 activate. The x-positions of the first anti-aliased pixel that each of the generated candidate edges ‘2’ 1352, ‘3’ 1353 and ‘4’ 1354 activate are x-positions ‘4’ 661, ‘5’ 662 and ‘6’ 663, respectively. Fig. 13 shows the x-position of all candidate edges generated for anti-aliased scan line ‘2’ 652.

The method 1400 of generating the final anti-aliased edges for an anti-aliased scan line, as executed at step 930, will now be described with reference to Fig. 14. The method 1400 retains a “current” compositing stack for each of the fillmap edges spanned by the anti-aliased scan line. The anti-aliased pixels on the anti-aliased scan line that have associated candidate edges are traversed from left to right. At each anti-aliased pixel, the candidate edges and “current” compositing stacks are used to determine the contribution of each compositing stack. The final anti-aliased edges are updated with information from the candidate edges and “current” compositing stacks. The method 1400 may be implemented as one or more software code modules of the anti-aliased fillmap software program 132 resident in the memory 133 and being controlled in its execution by the processor 131.

The method 1400 begins at initialising step 1410, where a “current” compositing stack for each fillmap scan line associated with the anti-aliased scan line is initialised within memory 133, for example, to be the compositing stack associated with the page background. Initialising a “current” compositing stack for each fillmap scan line associated with the anti-aliased scan line indicates that no edges are currently contributing to the appearance of the anti-aliased pixels on the anti-aliased scan line.

The method 1400 then proceeds to decision step 1420, where the anti-aliased pixels on the scan line that have candidate edges are looped over, by determining if there are more antialiased pixels on the anti-aliased scan line that have associated candidate edges. As mentioned earlier, the anti-aliased pixels are traversed from left to right (i.e., from smallest x-position to largest). If it is determined at step 1420 that there are more anti-aliased pixels with candidate edges, then the method 1400 proceeds to retrieving step 1430. At retrieving step 1430, the candidate edges at the next anti-aliased pixel are retrieved from the memory 133 under execution of the processor 131.

The method 1400 then proceeds to determining step 1440, where the compositing stacks and weights of the anti-aliased pixel are determined under execution of the processor 131. The compositing stacks and weights indicate how the anti-aliased pixel is to be rendered when the anti-aliased fillmap Tenderer module 205 renders the anti-aliased fillmap 204 to pixels, for example. A method 1500 of determining compositing stacks and weights for an anti-aliased pixel, as executed at step 1440, will be described in more detail later with reference to Fig. 15.

The method 1400 then proceeds to updating step 1450, where the anti-aliased edge that activates the anti-aliased pixel is updated under execution of the processor 131. Updating the anti-aliased pixel may involve creating a new anti-aliased edge within memory 133, extending an existing anti-aliased edge from the previous anti-aliased scan line, or extending the range of pixels activated by an existing anti-aliased edge on the current anti-aliased scan line. A method 1600 of updating the anti-aliased edge for an anti-aliased pixel, as executed at step 1450, will be described in more detail later with reference to Fig. 16.

The method 1400 then proceeds to updating step 1460, where the “current” compositing stack for each fillmap scan line within the anti-aliased scan line is updated within the memory 133 under execution of the processor 131. Previously, the “current” compositing stacks indicated the compositing stacks prior to the left border of the anti-aliased pixel. Since the antialiased pixel has been processed in steps 1410 to 1450, the “current” compositing stacks are updated to indicate the compositing stacks following the right border of the anti-aliased pixel. Therefore, for each fillmap scan line, the associated “current” compositing stack is set at step 1460 to the compositing stack associated with the candidate edge whose fillmap edge activates the right-most fillmap pixels that intersect the anti-aliased scan line. The method 1400 then returns to decision step 1420. If it is determined at decision step 1420 that there are no more anti-aliased pixels to the right (i.e., in the direction of increasing x-position) that have associated candidate edges, then the method 1400 ends. Following completion of step 1460, the anti-aliased fillmap 204 is complete up to and including the anti-aliased scan line. A method 1500 of determining the compositing stacks and weights for an anti-aliased pixel, as executed at step 1440, will now be described with reference to Fig. 15. The method 1500 may be implemented as one or more software code modules of the anti-aliased fillmap software program 132 resident in the memory 133 and being controlled in its execution by the processor 131.

The method 1500 begins at step 1510, where the compositing stacks and weights contributing to a next anti-aliased pixel being traversed at step 1430 are initialised within memory 133 to indicate that there are currently no compositing stacks contributing to the antialiased pixel. As described previously, and in more detail later with reference to Fig. 7 and Fig. 8, the weights indicate how much each compositing stack contributes to the final colour of an anti-aliased pixel.

The method 1500 then proceeds to decision step 1520, where the fillmap scan lines within the anti-aliased scan line are looped over, by determining if there are more fillmap scan lines within the anti-aliased scan line to process for the current anti-aliased pixel. If it is determined that there are more fillmap scan lines to process, then the method 1500 proceeds to sorting step 1530. At step 1530, the fillmap edges that intersect the anti-aliased pixel on the fillmap scan line are sorted from right to left according to x-positions of the fillmap edges on the fillmap scan line. The fillmap edges to be sorted are those fillmap edges that are associated with the candidate edges located at the anti-aliased pixel, and that intersect the fillmap scan line. Sorting the fillmap edges from right to left allows the following steps of the method 1500 to accumulate coverage information associated with the anti-aliased pixel, as each fillmap edge activates the region to its right. As described above, each anti-aliased edge may be associated with coverage information specifying the contribution of each item of appearance information to pixels in a region.

The method 1500 then proceeds to step 1540, where the variable referred to as current x, configured within memory 133, is set to the width of the anti-aliased pixel, in units of fillmap pixels. For example, there may be four (4) fillmap pixels between the left boundary and the right boundary of the anti-aliased pixel, in which case the current x is set to four (4).

Then at decision step 1550, it is determined if there are more fillmap edges remaining to be processed for the current fillmap scan line (i.e., more fillmap edges intersecting the antialiased pixel. If it is determined that there are more fillmap edges to process, then the method 1500 proceeds to step 1560, where the number of fillmap pixels activated by the next fillmap edge within the anti-aliased pixel on the current fillmap scan line is determined under execution of the processor 131. The x-position of the fillmap edge within the anti-aliased pixel is first determined. The x-position of the fillmap edge within the anti-aliased pixel is subtracted from the current x value, to indicate the number of fillmap pixels the fillmap edge activates on the fillmap scan line. An example of determining the number of fillmap pixels activated by a fillmap edge within an anti-aliased pixel is described below with reference to Fig. 17. At step 1560, the value of current x is updated to be the x-position of the fillmap edge within the antialiased pixel.

The method 1500 then proceeds to updating step 1570, where the determined number of fillmap pixels is added to the weights associated with the compositing stack associated with the fillmap edge for the current anti-aliased pixel. Upon completion of step 1570, then the method 1500 returns to decision step 1550. If at step 1550, it is determined that there are no more fillmap edges on the current fillmap scan line to process, then the method 1500 proceeds to step 1580, where the weights are updated according to the remaining fillmap pixels on the current fillmap scan line. The value of current x is added to the weight associated with the “current” compositing stack on the fillmap scan line. The value of current x plus the weight associated with the “current” compositing stack represents the contribution of the fillmap edge to the left of the anti-aliased pixel, which activates the fillmap pixels on the left side of the anti-aliased pixel, on the same fillmap scan line. Fig. 17 shows an example of the generation of anti-aliased edges along an anti-aliased scan line of the example anti-aliased fillmap shown in Fig. 7.

Upon completion of step 1580, the method 1500 returns to decision step 1520. If at step 1520 it is determined that there are no more fillmap scan lines to process, then the method 1500 ends.

As described above, the method 1500 accumulates the weights of each compositing stack contributing to the anti-aliased pixel. Determination of the compositing stacks and weights of an anti-aliased pixel will be described below with reference to Fig. 17. A method 1600 of updating the anti-aliased edge for an anti-aliased pixel, as executed at step 1450, will now be described with reference to Fig. 16. The method 1600 may be implemented as one or more software code modules of the anti-aliased fillmap software program 132 resident in the memory 133 and being controlled in its execution by the processor 131.

The method 1600 begins at decision step 1610, where it is determined, under execution of the processor 131, if the anti-aliased pixel being traversed at step 1430 has a single compositing stack. Step 1610 is done by analysing the compositing stacks and weights determined for the anti-aliased pixel previously at step 1440, as described with reference to Fig. 15.

If it is determined at step 1610 that the anti-aliased pixel does have a single compositing stack, then the method 1600 proceeds to step 1620. At step 1620, a solid candidate edge is selected from the candidate edges associated with the anti-aliased pixel as stored in the memory 133 at step 1160. Since the anti-aliased pixel has a single compositing stack, only a single solid candidate edge will be available. A solid edge activates pixels that are to be rendered using a single compositing stack, without anti-aliasing. Because the anti-aliased pixel has a single compositing stack, the anti-aliased pixel can be activated by a solid edge. Upon completion of step 1620, the method 1600 proceeds to step 1640.

If it is determined at step 1610 that the anti-aliased pixel does not have a single compositing stack, then the method 1600 proceeds to step 1630. At step 1630, a transition candidate edge is selected, under execution of the processor 131, from the candidate edges associated with the anti-aliased pixel. Since the anti-aliased pixel has multiple compositing stacks, there will typically be multiple candidate edges available to be selected. A transition anti-aliased edge activates pixels that are to be rendered using multiple compositing stacks, anti-aliased using the associated weights. Because the anti-aliased pixel has multiple compositing stacks, the anti-aliased pixel must be activated by a transition anti-aliased edge. At selection step 1630 the first transition candidate edge, for example, may be selected. In another arrangement, the transition candidate edge that has compositing stacks that match those of an existing anti-aliased edge from the previous scan line may be selected at step 1630. Upon completion of step 1630, the method 1600 proceeds to decision step 1635.

At decision step 1635, it is determined if the anti-aliased pixel can be activated by the anti-aliased edge immediately to the left of the anti-aliased pixel. More specifically, at step 1635 the compositing stacks of the anti-aliased pixel is compared with the compositing stacks of the edge to the left. If the compositing stacks of the anti-aliased pixel are identical to the compositing stacks of the edge to the left, the edge to the left can be used to also activate the anti-aliased pixel and possibly other anti-aliased pixels to the immediate right of the anti-aliased pixel. If it is determined that the edge to the left of the anti-aliased pixel can be used to activate the anti-aliased pixel, then the method 1600 proceeds to step 1636 where the edge to the left of the anti-aliased pixel is updated. Step 1636 involves appending the weights of the anti-aliased pixel to the weights associated with the edge to the left of the anti-aliased pixel. The weights are appended to the list of weights stored in the memory 133 for the scan line associated with the edge to the left of the anti-aliased pixel, rather than a new scan line. An example of a method of encoding weights, in order to separate weights for anti-aliased pixels on the same scan line and on different scan lines, is described with reference to Fig. 7 and Fig. 8. Upon completion of step 1636, the method 1600 proceeds to step 1690.

If, at decision step 1635, it is decided that the edge to the left of the anti-aliased pixel cannot activate the anti-aliased pixel, then the method 1600 proceeds to step 1640.

At step 1640, the fillmap edge that is associated with the candidate edge that was selected at step 1620 or 1630 is retrieved from memory 133 under execution of the processor 131. Upon completion of step 1640, the method 1600 proceeds to decision step 1650, where it is decided if the fillmap edge retrieved at step 1640 has an associated anti-aliased edge of the same type as the selected candidate edge. For example, if the selected candidate edge is of type “solid edge”, it is determined at step 1650 if the fillmap edge has an associated solid edge. If the selected candidate edge is of type “transition edge”, it is determined at step 1650 if the fillmap edge has an associated transition edge.

If it is determined at step 1650 that the fillmap edge does not have an associated antialiased edge of the same type, then the method 1600 proceeds to step 1660, where the selected candidate edge is associated with the fillmap edge, using the type of the candidate edge. In the situation that it is determined at step 1650 that the fillmap edge does not have an associated anti-aliased edge of the same type, the anti-aliased edge is a new anti-aliased edge starting at the current anti-aliased pixel. The anti-aliased edge is associated with the fillmap edge so that, on the next scan line, it can be determined whether to extend the anti-aliased edge. Upon completion of step 1660, the method 1600 proceeds to step 1695.

If it is determined at step 1650 that the fillmap edge does have an associated anti-aliased edge of the same type, then the method 1600 proceeds to decision step 1670, where it is determined if the associated anti-aliased edge can be extended. The associated anti-aliased edge can be extended to activate the current anti-aliased pixel if it has the same associated compositing stacks, and there are no other anti-aliased edges on the previous scan line that have x-positions between the associated anti-aliased edge and the anti-aliased pixel. The latter condition of no other anti-aliased edges on the previous scan line having x-positions between the associated anti-aliased edge and the anti-aliased pixel is required so that anti-aliased edges do not cross.

If it is determined at step 1670 that the associated anti-aliased edge cannot be extended, then the method 1600 proceeds to step 1660, where the selected candidate edge is associated with the fillmap edge as a new anti-aliased edge.

If it is determined at step 1670 that the associated anti-aliased edge can be extended, then the method 1600 proceeds to step 1680, where the associated anti-aliased edge is extended to include the selected candidate edge. At step 1680, the associated anti-aliased edge is extended by appending the x-position of the current anti-aliased pixel to the list of x-crossings for the anti-aliased edge, and appending the weights of the anti-aliased pixel to the weights of the anti-aliased edge.

Upon completion of step 1680, the method 1600 proceeds to step 1690, where the selected candidate edge is deleted. The selected candidate edge can be deleted since the associated anti-aliased edge was extended to include the current anti-aliased pixel, so the candidate edge is no longer needed. Upon completion of step 1690, the method 1600 proceeds to step 1695, where the candidate edges that were not selected at step 1620 or 1630 for the current anti-aliased pixel are deleted. Upon completion of step 1695, the method 1600 concludes.

An example of generating the final anti-aliased edges for anti-aliased scan line ‘2’ 652 will now be described with reference to Figs. 17A, 17B and 17C. The method 1400 of generating anti-aliased edges for an anti-aliased scan line was described previously with reference to Fig. 14. The generation of anti-aliased edges on scan line ‘2’ 652 using candidate edges 1351-1356 will now be described with reference to steps of the method 1400.

Fig. 17A is a table 1700 showing the current compositing stack for each fillmap scan line at each anti-aliased pixel along anti-aliased scan line ‘2’ 652, including the initial current compositing stack. As described previously with reference to Fig. 14, the current compositing stack is used to determine the weights of each compositing stack for the anti-aliased pixels activated by anti-aliased edges.

As at step 1410 of the method 1400, the current compositing stack for each fillmap scan line that overlaps the anti-aliased scan line ‘2’ 652 is initialised. The current compositing stack is initialised to the background compositing stack 631 (shown in Fig. 8A), as shown in column 1701 of table 1700.

As at steps 1430-1460 of the method 1400, each anti-aliased pixel that contains candidate edges for anti-aliased scan line ‘2’ 652 is processed. In the example, anti-aliased pixels at x-positions 0, 4, 5, 6, 8 and 9 contain candidate edges, as shown in Fig. 13. An example of executing steps 1430-1460 for the anti-aliased pixel at position ‘5’ 662 will now be described.

For the anti-aliased pixel at x-position ‘5’ 662 (shown in Fig. 6 and Fig. 13), step 1430 retrieves candidate edge ‘3’ 1353. As at step 1440, the compositing stacks and associated weights for the anti-aliased pixel at x-position 5 [6]62 are determined.

As at step 1510 of the method 1500, the compositing stacks and associated weights for the anti-aliased pixel are initialised. The following steps of the method 1500 are then executed for each fillmap scan line ‘4’ 674 and ‘5’ 675 overlapping the anti-aliased scan line ‘2’ 652.

As at step 1530, the fillmap edges that intersect the anti-aliased pixel at fillmap scan line ‘4’ 674 are sorted from right to left. The sorted fillmap edges are associated with the candidate edges located at the anti-aliased pixel location. The anti-aliased pixel at x-position ‘5’ has a single candidate edge ‘3’ 1353 (as shown in Fig. 13), which is associated with fillmap edge ‘2’ 612 (as shown in Figs. 6A, 6B and 6C) that intersects fillmap scan line ‘4’ 674. Since there is only one fillmap edge, the single fillmap edge ‘2’ 612 is returned as at step 1530 of the method 1500.

For scan line ‘4’ 674, the current x is set to be the width of the anti-aliased pixel, in units of fillmap pixels, as at step 1540. In the current example, each anti-aliased pixel is two fillmap pixels wide. Therefore, the current x is set to two (2). The number of fillmap pixels activated by the fillmap edge within the anti-aliased pixel, on the current fillmap scan line, are determined as at step 1560 of the method 1500. As observed in Fig. 6A, 6B and 6C, fillmap edge ‘2’ 612 intersects fillmap scan line ‘4’ 674 within the anti-aliased pixel at position ‘5’ 662 at the second fillmap pixel 660. The number of fillmap pixels activated is the value of current x (2) minus the position of the edge’s intersection (1) is determined as at step 1560 of the method 1500. Therefore, as at step 1560, it is determined that fillmap edge ‘2’ 612 activates one (1) fillmap pixel on the current scan line, for the current anti-aliased pixel. The value of current x is also updated, as at step 1560, to be the intersection position (1).

The number of fillmap pixels (1) determined at step 1560 is used to update the contributing compositing stacks and weights for the anti-aliased pixel, as at step 1570 of the method 1500. The compositing stack associated with fillmap edge ‘2’ 612 is the compositing stack ‘2’ 632 with the hatched fill. Therefore, compositing stack ‘2’ 632 is added to the contributing compositing stacks if compositing stack ‘2’ 632 has not previously been added (in the present example, compositing stack ‘2’ 632 has not previously been added). Initially, the weight associated with a contributing compositing stack is initialised to zero (0). Then, the number of fillmap pixels (1) determined, as at step [15]60, is added to the weight associated with the contributing compositing stack ‘2’ 632.

As at step 1550, it is determined that there are no more fillmap edges intersecting fillmap scan line ‘4’ 674 within the anti-aliased pixel at position ‘5’ 662. In the present example, the method 1500 then proceeds to step 1580, where the contributing compositing stacks and weights are updated using the current compositing stack on the current fillmap scan line ‘4’ 1514, if the value of current x is greater than zero (0) (in the present example, current x has a value of one (1)). As seen in Fig. 17A, the current compositing stack 1702 prior to processing the anti-aliased pixel at position ‘5’ 662 on fillmap scan line ‘4’ 674 is compositing stack ‘Γ 631. Therefore, compositing stack ‘1’ 631 is added to the contributing compositing stacks if compositing stack ‘ Γ 631 has not previously been added (in the present example, compositing stack ‘Γ 631 has not previously been added). Then, as at step 1580, the value of current x is added to the weight associated with the contributing compositing stack 1 631, to represent the contribution of the edge to the left of the anti-aliased pixel at position ‘5’ 662.

Fillmap scan line ‘5’ 675 is processed in a similar manner using steps 1530-1580. Upon completion of the method 1500, the contributing compositing stacks and associated weights for the anti-aliased pixel at position ‘5’ 662 are known.

Fig. 17B shows the contributing compositing stacks and weights 1720 for all antialiased pixels containing candidate edges on anti-aliased scan line ‘2’ 652. Anti-aliased pixel at position ‘5’ 662 has two contributing compositing stacks, ‘1’ 631 and ‘2’ 632. Compositing stack ‘1’ 631 has a weight of one (1), and compositing stack ‘2’ 632 has a weight of three (3), reflecting the number of fillmap pixels of each compositing stack overlapped by the anti-aliased pixel. When rendering the anti-aliased pixel, the weights will be used to combine the contributing compositing stacks and thereby determine the final pixel appearance.

Once the contributing compositing stacks and weights have been determined for an antialiased pixel, the method 1600 is executed to determine the final anti-aliased edge to activate the pixel. Fig. 17C shows the existing anti-aliased edges 711-715 on anti-aliased scan line ‘Γ 651 (described previously with reference to Fig. 10B), and the candidate edges on anti-aliased scan line ‘2’ 652 (described previously with Fig. 13). The method 1600 is executed to extend the set of existing anti-aliased edges 711-715 to include the candidate edges. Extending the set of existing anti-aliased edges may involve extending an existing anti-aliased edge to include a candidate edge, and creating a new anti-aliased edge. The method 1600 will be described for the anti-aliased pixels at positions ‘4’ 661 and ‘5’ 662.

For the anti-aliased pixel at position ‘4’ 661, it is determined, as at step 1610 of the method 1600, that the anti-aliased pixel at position ‘4’ 661 does not have a single compositing stack. The anti-aliased pixel at position ‘4’ 661 has a transition candidate edge ‘2’ 1352 that references two compositing stacks, as observed in the table 1720 of Fig. 17B. As at step 1630, the transition candidate edge ‘2’ 1352 is selected, since there are no other candidate edges at anti-aliased pixel at position ‘4’ 661.

As at step 1635, it is determined whether the pixels activated by selected candidate edge ‘2’ 1352 can be activated by the anti-aliased edge to the left of the selected candidate edge ‘2’ 1352. In the case where selected candidate edge ‘2’ 1352 can be activated by the anti-aliased edge to the left of the selected candidate edge ‘2’ 1352, the edge to the left is anti-aliased edge ‘Γ 711 that was previously extended to include candidate edge ‘Γ 1351. Since candidate edge ‘2’ 1352 and anti-aliased edge ‘Γ 711 have different associated compositing stacks, it is determined that anti-aliased edge ‘Γ 711 cannot be used to activate the anti-aliased pixels activated by candidate edge ‘2’ 1352.

As at step 1640 of the method 1600, the fillmap edge ‘2’ 612 that was used to generate transition candidate edge ‘2’ 1352 is retrieved. As at step 1650, it is determined if the fillmap edge has an associated anti-aliased edge that is of the same type as the candidate edge. On previous scan lines, fillmap edge ‘2’ 612 will have been associated with transition anti-aliased edge ‘2b’ 713. Therefore, as at step 1650, it is determined that there is an associated anti-aliased edge of the same type (i.e., transition edge).

As at step 1670, it is determined if the existing anti-aliased edge ‘2b’ 713 can be extended to include candidate edge ‘2’ 1352. Both the existing anti-aliased edge ‘2b’ 713 and the candidate edge ‘2’ 1352 reference compositing stacks ‘1’ 631 and ‘2’ 632, and there are no existing anti-aliased edges between the x-positions of existing anti-aliased edge ‘2b’ 713 and the candidate edge ‘2’ 1352. Therefore, as at step 1670, it is determined that existing antialiased edge ‘2b’ 713 can be extended to include candidate edge 2 [13]52.

As at step 1680, existing anti-aliased edge ‘2b’ 713 is extended to include candidate edge ‘2’ 1352. The x-position candidate edge ‘2’ 1352 (4) is appended to the list of x-positions of anti-aliased edge ‘2b’ 713. The weights associated with anti-aliased edge ‘2b’ 713 are also updated to include the weights 1721 for candidate edge ‘2’ 1352. As at step 1690, candidate edge ‘2’ 1352 is deleted in the example of Figs. 17A to 17C.

For the anti-aliased pixel at position ‘5’ 662, it is determined that the anti-aliased pixel does not have a single compositing stack, as at step 1610 of the process 1600. The anti-aliased pixel has a transition candidate edge ‘3’ 1353 that references two compositing stacks, as observed in the table 1720 of Fig. 17B. As at step 1630, the transition candidate edge ‘3’ 1353 is selected, since there are no other candidate edges at anti-aliased pixel at position ‘5’ 662.

Then as at step 1635, it is determined whether the pixels activated by selected candidate edge ‘3’ 1353 can be activated by the anti-aliased edge to the left of candidate edge ‘3’ 1353. In the case that selected candidate edge ‘3’ 1353 can be activated by the anti-aliased edge to the left of candidate edge ‘3’ 1353, the edge to the left of candidate edge ‘3’ 1353 is anti-aliased edge ‘2b’ 713 that was previously extended to include candidate edge ‘2’ 1352. Since both candidate edge ‘3’ 1353 and anti-aliased edge ‘2b’ 713 have the same associated compositing stacks (i.e., compositing stacks ‘1’ 631 and ‘2’ 632), it is determined that anti-aliased edge ‘2b’ 713 can be used to activate the anti-aliased pixels activated by candidate edge ‘3’ 1353.

As at step 1636, the weights associated with anti-aliased edge ‘2b’ 713 are extended to include the weights 1722 associated with candidate edge ‘3’ 1353. As at step 1690, candidate edge ‘3’ 1353 is deleted.

The other anti-aliased pixels on scan line ‘2’ 652 are processed in a similar way. Upon completion of the method 1600 for all anti-aliased pixels with candidate edges, the anti-aliased edges will have been updated to activate all anti-aliased pixels up to and including the antialiased scan line. Upon completion of the method 1600, the anti-aliased edges for the entire fillmap will be complete (as shown in Fig. 7 and Fig. 8). A method 1800 of rendering an anti-aliased fillmap 204 will now be described with reference to Fig. 18. The method 1800 may be implemented as one or more software code modules of the anti-aliased fillmap software program 132 resident in the memory 133 and being controlled in its execution by the processor 131. The one or more software code modules of the anti-aliased fillmap software program 132 implementing the method 1800 may form the antialiased fillmap Tenderer module 205.

The method 1800 starts at decision step 1805, where it is determined if there are antialiased scan lines remaining to be rendered. If it is determined that there are more anti-aliased scan lines to be rendered, then the method 1800 proceeds to sorting step 1810. At sorting step 1810, the anti-aliased edges that intersect the next anti-aliased scan line are sorted, under execution of the processor 131, according to the x values of their intersection points with the anti-aliased scan line, from smallest to largest. The anti-aliased edges may be stored in the memory 133.

The method 1800 then proceeds to retrieving step 1815, where the first edge in the sorted anti-aliased edges is retrieved from the memory 133 for example. The first edge in the sorted anti-aliased edges is the edge with the left-most intersection with the scan line, and in one arrangement is the edge that activated the left-most pixels on the scan line. The method 1800 then proceeds to retrieving step 1820, where the compositing stacks and weights of the first edge are retrieved from the memory 133 under execution of the processor 131. If the first edge is a solid edge, the first edge will only have a single associated compositing stack, and will not have any weights. If the first edge is a transition edge, the first edge will have two or more compositing stacks, and one or more weights that indicate how those compositing stacks contribute to the pixels activated by the edge.

The method 1800 then proceeds to decision step 1825, where it is determined if there are any edges remaining in the sorted edges. If it is determined that there are more edges, then the method 1800 proceeds to retrieving step 1830, where the next edge in the sorted edges is retrieved from memory 133 under execution of the processor 131.

At rendering step 1835, the span of consecutive pixels between the previous edge and the next edge are rendered under execution of the processor 131. The span of consecutive pixels between the previous edge and the next edge is delineated by the x values of the intersection points of the two edges. The colour of each pixel in the span is determined using the compositing stacks and weights retrieved previously at step 1820 or the previous execution of step 1840. Each anti-aliased pixel in the span is rendered in sequence, from smallest x to largest x. If a single compositing stack (and no weights) was previously retrieved, the single compositing is evaluated at each pixel as described previously with reference to Fig. 4 and Fig. 5. If multiple compositing stacks (and weights) were retrieved, at each pixel, each compositing stack is first evaluated to form a colour value. Each colour is then scaled by a corresponding weight as a percentage of the overall pixel. For example, in one arrangement, each weight is a number indicating a number of high-resolution fillmap pixels within an anti-aliased pixel associated with a compositing stack. Therefore, if the weight of a compositing stack is one (1), and there are four (4) fillmap pixels per anti-aliased pixel, the colour of the evaluated compositing stack is scaled by '4 (25%). The final colour of an anti-aliased pixel is then determined by summing the scaled colours associated with each compositing stack.

The method 1800 then proceeds to retrieving step 1840, where the compositing stacks and weights of the next edge are retrieved under execution of the processor 131. Similarly to step 1820, if the next edge is a solid edge, then the next edge will only have a single associated compositing stack, and will not have any weights. If the next edge is a transition edge, then the next edge will have two or more compositing stacks, and one or more weights that indicate how those compositing stacks contribute to the pixels activated by the edge. Upon completion of step 1840, the method 1800 returns to decision step 1825.

If it is determined at step 1825 that there are no more anti-aliased edges, then the method 1800 proceeds to step 1845, where the pixels in the span from the previous edge to the end of the scan line are rendered using the compositing stacks and weights determined previously in a similar manner to step [1835 described previously. Upon completion of step 1845, the method 1800 returns to decision step 1805. If it is determined at step 1805 that there are no more anti-aliased scan lines to be rendered, then the method 1800 ends.

An example of rendering anti-aliased fillmap 700 will now be described with reference to Figs. 19A and 19B. Fig. 19A shows rendered anti-aliased pixels along anti-aliased scan line ‘2’ 652. The rendering of the anti-aliased scan line 2 622 will now be described, with reference to steps of the method 1800, described previously with reference to Fig. 18.

As at step 1810 of the method 1800, the anti-aliased edges that intersect the anti-aliased scan line ‘2’ 622 are sorted according to the x-positions of the anti-aliased edges along the scan line. The anti-aliased edges that intersect anti-aliased scan line ‘2’ 622 are ‘ Γ 711, ‘2a’ 712, ‘2b’ 713, ‘3a’ 714 and ‘3b’ 715. Then as at step 1810, the anti-aliased edges are sorted into the order ‘1’ 711, ‘2b’ 713, ‘2a’ 712, ‘3b’ 715, then ‘3a’ 714.

The first edge in the sorted edges is anti-aliased edge ‘1’ 711. As at step 1820, the compositing stack ‘1’ 631 associated with the first edge is retrieved from memory 133, for example. As at step 1830, the next edge ‘2b’ 713 in the sorted edges is retrieved. Then as at step 1835, the anti-aliased pixels from edge ‘1’ 711 to edge ‘2b’ 713 are rendered under execution of the processor 131. The compositing stack that was previously retrieved is compositing stack ‘1’ 631. Therefore, the first four pixels (i.e., at positions zero (0) to three (3)) on anti-aliased scan line ‘2’ 652 are rendered using compositing stack ‘1’ 631, which contains the background fill only.

As at step 1840, the compositing stacks and weights of the next edge ‘2b’ 713 are retrieved. The compositing stacks and weights of the next edge ‘2b’ 713 are compositing stacks ‘2’ 632 and ‘1’ 631, and weights 841, as shown in Figs. 8A and 8B.

In the example of Figs. 19A and 19B, at the next execution of step 1830, the next edge in the sorted edges, edge ‘2a’ 712, is retrieved. Then, as at step 1835, the anti-aliased pixels between the previous edge 2b 713 and 2a 712 (i.e., at positions four (4) and five (5)) are rendered, using the previously retrieved compositing stacks and weights. As seen in Figs. 8A and 8B, the weights 852 associated with the anti-aliased pixels between the previous edge 2b 713 and edge 2a 712 are denoted [(1), (3)] meaning that there are two pixels in the span (i.e., two sets of parentheses). Since there are two compositing stacks associated with edge ‘2b’ 713, each pair of parentheses contains a single number. The single number in each pair of parentheses indicates the contribution of the first compositing stack ‘2’ 632. The contribution of the second compositing stack ‘1’ 631 is derived by subtracting the values other weight(s) from the maximum possible contribution (i.e., four (4) in the example of Fig. 19A and 19B). Therefore, the anti-aliased pixel at x-position four (4) is rendered using the value of compositing stack ‘2’ 632 scaled by one-quarter (Vi), and compositing stack ‘Γ 631 scaled by three quarters (¾). Similarly, the anti-aliased pixel at x-position ‘5’ is rendered using the value of compositing stack ‘2’ 632 scaled by three quarters (3Α), and compositing stack ‘Γ 631 scaled by one-quarter (¼). The scaled values of the compositing stacks for an anti-aliased pixel are added to determine the final anti-aliased pixel value.

Subsequent spans of anti-aliased pixels on anti-aliased scan line ‘2’ 652 are rendered in a similar manner in accordance with the method 1800. Fig. 19B shows the results of all antialiased scan lines of anti-aliased fillmap 700 rendered according to the method 1800 of the antialiased fillmap Tenderer module 2]05. A method 900 of generating an anti-aliased fillmap is described above with reference to Fig. 9 to Fig. 17. In alternative arrangement, it is possible for the anti-aliased fillmap generator module 203 to generate anti-aliased edges directly on an anti-aliased scan line without first generating candidate edges. For example, the fillmap edges that intersect an anti-aliased scan line can be sorted in x, and processed from left to right. For each anti-aliased fillmap pixel intersected by a fillmap edge (rather than a candidate edge), an anti-aliased edge may be generated directly. The anti-aliased edge may be generated directly using the number of pixels at a fillmap resolution covered by the fillmap edge within the anti-aliased pixel, the compositing stacks of the fillmap edges intersecting the anti-aliased edge, and the compositing stacks to the left of the anti-aliased edge. Similarly, anti-aliased fillmap rendering methods other than the method described with reference to Fig. 18 to Fig. 19 may be used.

In alternative arrangements, the anti-aliased fillmap program 132 may be resident within the memory 123 of the print device 120 and be controlled in its execution by the processor 121 of the print device 120. In another alternative arrangement, the anti-aliased fillmap program 132 may be resident within the memory of a non-mobile computer device, for example, and be controlled in its execution by a processor of the non-mobile computer device. In arrangements where the anti-aliased fillmap program 132 is resident in the print device 120 or a non-mobile computer device, the generated anti-aliased fillmap 204 may be used to show the fillmap on a display of the print device 120 or a monitor attached to a personal computer, for example.

In another arrangement, the anti-aliased fillmap 204 completely replaces the print fillmap 201, and is used by the print device 120 to print a page. In an arrangement where the anti-aliased fillmap 204 replaces the print fillmap 201, the print device 120 can print the antialiased fillmap 204 at the same (low) resolution as the anti-aliased fillmap 204. Alternatively, in such an arrangement, the print device 120 can print the anti-aliased fillmap 204 at (high) print resolution by sampling each anti-aliased pixel several times, where each anti-aliased pixel is sampled once for each high-resolution pixel that intersects the anti-aliased pixel.

In still another alternative arrangement, the anti-aliased fillmap generator module 203 is resident within the print server 110 and is controlled in its execution by the processor 111 of the print server 110, and an anti-aliased fillmap 204 is sent to the mobile device 130, where the anti-aliased fillmap Tenderer module 205 is rendered to pixel data 206.

In still another arrangement, anti-aliased edges are rendered as the anti-aliased edges are generated. For example, anti-aliased edges on a scan line may be rendered after the anti-aliased edges on the scan line are generated.

The described methods are not limited to printing systems and may also be implemented, for example, as part of other graphics rendering systems in which an intermediate representation is rendered (e.g. for displaying PDF documents on an LCD display).

In alternative arrangements, the anti-aliased fillmap 204 may be generated at several different resolutions, corresponding to different levels at which a user can zoom in during print preview on the mobile display 210. In arrangements where the anti-aliased fillmap 204 is generated at several different resolutions, each anti-aliased fillmap may be generated at once by the anti-aliased fillmap generator module 203, or each anti-aliased fillmap may be generated as needed. Further, in one arrangement, only portions (e.g. tiles) of the anti-aliased fillmap 204 are generated by the anti-aliased fillmap generator module 203, and are rendered by the antialiased fillmap Tenderer module 205, depending on which portions are currently visible on the mobile display 210. For example, if a user is currently zoomed in to the top-left comer of a page, only the portion of the anti-aliased fillmap 204 corresponding to the top-left comer of the page needs to be generated and rendered. If the user chooses to pan to the right or zoom out, for example, additional portions of the anti-aliased fillmap 204 can be generated and rendered.

In the arrangements described above, the anti-aliased fillmap 204 is considered separate to the print fillmap 201. In alternative arrangements, the print fillmap 201 and anti-aliased fillmap 204 are combined in a single data structure, for example, generated on the print server 110 and sent to the mobile device 130. In such a data structure, the print fillmap 201 and antialiased fillmap 204 have separate sets of fillmap edges, which reference compositing stacks in a single shared compositing stack table.

In the arrangements described above, the grid of anti-aliased pixels is aligned with the grid of fillmap pixels, such that each anti-aliased pixel overlaps a whole number of fillmap pixels. In alternative arrangements, the grids of anti-aliased pixels may not be aligned, and each anti-aliased pixel may overlap a non-integer number of fillmap pixels. In arrangements where the grids of anti-aliased pixels are not aligned, the method 900 is substantially the same. When determining the contribution of a fillmap edge to an anti-aliased pixel, sub-pixel coverage may be calculated, or fractional coverage values may be rounded to the nearest integer number of fillmap pixels.

In the arrangements described above, each fillmap pixel overlapped by an anti-aliased pixel is given equal weighting when determining weights, and therefore when determining a final pixel colour during rendering. Giving each fillmap pixel overlapped by an anti-aliased pixel an equal weighting is similar to the application of a box filter. In alternative arrangements, the weight assigned to each overlapped fillmap pixel may not be equal, and may be a function of the distance of the fillmap pixel from the centre of the anti-aliased pixel, for example. Various functions may be used to assign weight values. For example, a sinusoidal function may be used to assign weight values. Further, fillmap pixels overlapped by neighbouring antialiased pixels may be used in the determination of compositing stacks and weights for the antialiased pixel.

Alternative methods of representing anti-aliased pixels with anti-aliased edges may also be used. In arrangements described above, each anti-aliased edge has a single set of compositing stack references, which are applied to all anti-aliased pixels activated by the edge. In alternative arrangements, a separate set of compositing stacks may be referenced for each scan line or each pixel activated by the edge, for example.

In the arrangements described above, solid anti-aliased edges and transition anti-aliased edges form two separate types of anti-aliased edges. In other arrangements, all anti-aliased edges may be treated as transition edges, with one or more associated compositing stacks. In still other arrangements, for example, when a transition anti-aliased edge activates a long span of pixels on a scan line, the weights may be represented by a function that describes how the weights vary across the span.

Also, in the arrangements described above, the compositing stacks referenced by edges in the anti-aliased fillmap are the same as the compositing stacks referenced by edges in the input print fillmap. In other arrangements, for some or all regions in which anti-aliasing takes place, an edge’s reference to multiple compositing stacks may be replaced by a reference to a single new compositing stack. The new compositing stack may be generated by rendering multiple compositing stacks and blending the result using a pre-defined set of weight values. Rendering multiple compositing stacks and blending the result in such a manner may be advantageous, for example, when several compositing stacks reference flat fills, and generating new compositing stacks once may be faster than performing a weighted summation of multiple compositing stacks for every anti-aliased pixel.

Industrial Applicability

The arrangements described are applicable to the computer and data processing industries and particularly for the image processing.

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

In the context of this specification, the word “comprising” means “including principally but not necessarily solely” or “having” or “including”, and not “consisting only of’. Variations of the word "comprising", such as “comprise” and “comprises” have correspondingly varied meanings.

Claims

1. A method of generating an anti-aliased representation of a document, the method comprising: receiving an intermediate representation of the document comprising a plurality of edges scan-converted at a first predetermined resolution, the edges defining regions associated with region rendering instructions; generating two anti-aliased edges scan-converted at a second resolution lower than the first resolution, for at least one edge from the plurality of edges, wherein the anti-aliased edges separate an anti-aliasing region and regions associated with a single set of the region rendering instructions; associating the anti-aliased region with sets of the region rendering instructions corresponding to two or more neighbouring regions, to form a plurality of anti-aliased region rendering instructions; determining weighting coefficients for the anti-aliased region rendering instructions using edges in the intermediate representation; and generating an anti-aliased representation of the document for rendering at the second resolution using the plurality of anti-aliased region rendering instructions and the determined weighting coefficients.

2. The method according to claim 1, associating a plurality of compositing stacks with an anti-aliased edge using neighbouring anti-aliased edges.

3. The method according to claim 1, wherein the anti-aliased edges span multiple scanlines in the anti-aliased representation.

4. The method according to claim 1, wherein a second edge from the generated two antialiased edges refers to a single compositing stack.

5. The method according to claim 1, further comprising associating each anti-aliased edge with a reference to appearance information contributing to the anti-aliased edge.

6. The method according to claim 1, further comprising associating each anti-aliased edge with a reference to coverage information specifying the contribution of each item of appearance information to pixels in a region.

7. The method according to claim 1, further comprising associating an edge with scan lines in which a plurality of compositing stacks remain the same.

8. The method according to claim 1, further comprising associating an edge with scan lines in which the edge activates pixels at the second resolution.

9. The method according to claim 1, further comprising generating an edge specifying a single set of weights for pixels activated by the edge.

10. A system for generating an anti-aliased representation of a document, the system comprising: a memory for storing data and a computer program; a processor coupled to the memory for executing the computer program, the computer program comprising instructions for: receiving an intermediate representation of the document comprising a plurality of edges scan-converted at a first predetermined resolution, the edges defining regions associated with region rendering instructions; generating two anti-aliased edges scan-converted at a second resolution lower than the first resolution, for at least one edge from the plurality of edges, wherein the anti-aliased edges separate an anti-aliasing region and regions associated with a single set of the region rendering instructions; associating the anti-aliased region with sets of the region rendering instructions corresponding to two or more neighbouring regions, to form a plurality of anti-aliased region rendering instructions; determining weighting coefficients for the anti-aliased region rendering instructions using edges in the intermediate representation; and generating an anti-aliased representation of the document for rendering at the second resolution using the plurality of anti-aliased region rendering instructions and the determined weighting coefficients.

11. An apparatus for generating an anti-aliased representation of a document, the apparatus comprising: means for receiving an intermediate representation of the document comprising a plurality of edges scan-converted at a first predetermined resolution, the edges defining regions associated with region rendering instructions; means for generating two anti-aliased edges scan-converted at a second resolution lower than the first resolution, for at least one edge from the plurality of edges, wherein the antialiased edges separate an anti-aliasing region and regions associated with a single set of the region rendering instructions; means for associating the anti-aliased region with sets of the region rendering instructions corresponding to two or more neighbouring regions, to form a plurality of anti-aliased region rendering instructions; means for determining weighting coefficients for the anti-aliased region rendering instructions using edges in the intermediate representation; and generating an anti-aliased representation of the document for rendering at the second resolution using the plurality of anti-aliased region rendering instructions and the determined weighting coefficients.

12. A computer readable medium having a computer program stored thereon for generating an anti-aliased representation of a document, the program comprising: code for receiving an intermediate representation of the document comprising a plurality of edges scan-converted at a first predetermined resolution, the edges defining regions associated with region rendering instructions; code for generating two anti-aliased edges scan-converted at a second resolution lower than the first resolution, for at least one edge from the plurality of edges, wherein the anti-aliased edges separate an anti-aliasing region and regions associated with a single set of the region rendering instructions; code for associating the anti-aliased region with sets of the region rendering instructions corresponding to two or more neighbouring regions, to form a plurality of anti-aliased region rendering instructions; code for determining weighting coefficients for the anti-aliased region rendering instructions using edges in the intermediate representation; and code for generating an anti-aliased representation of the document for rendering at the second resolution using the plurality of anti-aliased region rendering instructions and the determined weighting coefficients.

13. A method of rendering an anti-aliased graphical representation, said method comprising: receiving a graphical representation comprising a plurality of edges scan-converted at a predetermined resolution, the edges defining regions including an anti-aliased region, the antialiased region being associated with a plurality of sets of rendering instructions corresponding to two or more neighbouring regions and a weighting associated with the sets of rendering instructions; and rendering the anti-aliased graphical representation including the anti-aliased region, according to the sets of rendering instructions, the rendering instructions being combined in accordance with the weighting.

14. A system for rendering an anti-aliased graphical representation, said system comprising: a memory for storing data and a computer program; a processor coupled to the memory for executing the computer program, the computer program comprising instructions for: receiving a graphical representation comprising a plurality of edges scan-converted at a predetermined resolution, the edges defining regions including an antialiased region, the anti-aliased region being associated with a plurality of sets of rendering instructions corresponding to two or more neighbouring regions and a weighting associated with the sets of rendering instructions; and rendering the anti-aliased graphical representation including the anti-aliased region, according to the sets of rendering instructions, the rendering instructions being combined in accordance with the weighting.

15. An apparatus for rendering an anti-aliased graphical representation, said apparatus comprising: means for receiving a graphical representation comprising a plurality of edges scan-converted at a predetermined resolution, the edges defining regions including an anti-aliased region, the anti-aliased region being associated with a plurality of sets of rendering instructions corresponding to two or more neighbouring regions and a weighting associated with the sets of rendering instructions; and means for rendering the anti-aliased graphical representation including the anti-aliased region, according to the sets of rendering instructions, the rendering instructions being combined in accordance with the weighting.

16. A computer readable medium having a computer program stored thereon for rendering an anti-aliased graphical representation, said program comprising: code for receiving a graphical representation comprising a plurality of edges scan-converted at a predetermined resolution, the edges defining regions including an anti-aliased region, the anti-aliased region being associated with a plurality of sets of rendering instructions corresponding to two or more neighbouring regions and a weighting associated with the sets of rendering instructions; and code for rendering the anti-aliased graphical representation including the anti-aliased region, according to the sets of rendering instructions, the rendering instructions being combined in accordance with the weighting.

17. A method of generating an anti-aliased representation of a document, the method comprising: receiving an intermediate representation of the document comprising a plurality of edges scan-converted at a first predetermined resolution, the edges defining regions associated with region rendering instructions; for at least one edge from the plurality of edges, generating an anti-aliasing region and a region associated with a single set of the region rendering instructions, the generated regions being separated by an anti-aliased edge scan-converted at a second resolution lower than the first resolution; associating the anti-aliased region with sets of the region rendering instructions corresponding to two or more neighbouring regions, to form a plurality of anti-aliased region rendering instructions; and generating an anti-aliased representation of the document for rendering at the second resolution using the plurality of anti-aliased region rendering instructions combined based on edges in the intermediate representation.