AU739491B2 - Using region arithmetic to partially update a hardware double buffer - Google Patents

Description

S&FRef: 511420

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

Name and Address of Applicant: *r Actual Inventor(s): Address for Service: Invention Title: Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome, Ohta-ku Tokyo 146 Japan David Geoffrey Slack-Smith Spruson Ferguson St Martins Tower 31 Market Street Sydney NSW 2000 Using Region Arithmetic to Partially Update a Hardware Double Buffer r r ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) AU PQ1297 [32] Application Date 30 Jun 1999 The following statement is a full description of this invention, including the best method of performing it known to me/us:lp Australia 0Q 13atch ~o n 5815c USING REGION ARITHMETIC TO PARTIALLY UPDATE A HARDWARE DOUBLE BUFFER Technical Field of the Invention The present invention relates generally to the field of computer graphics and, in particular, to graphics animation and interactive computer graphics. The present invention also relates to a method and apparatus for double buffering image data in order to minimise re-rendering. Further, the invention relates to a computer program product including a computer readable medium having recorded thereon a computer program for double buffering image data in order to minimise re-rendering.

Background Art In the field of computer graphics, it is known to double buffer a graphics output in order to avoid a visual artefact known as "tearing". Tearing is the phenomenon where a display screen displays portions of two consecutive frames simultaneously. This generally occurs when a frame buffer is being used to refresh a display screen at the same 15 time image data is being rendered to the firame buffer.

Tearing can be ameliorated using a method of double buffering, where two buffers are maintained, those being termed a front buffer and a back buffer. The front buffer is used to refresh the screen while the back buffer is being updated. The buffers can swap roles or be "flipped" when the screen is not being refreshed. When double buffering with a Cathode Ray Tube (CRT) display, for example, the buffers can be flipped during the next vertical retrace blanking interval the period of time when the electron guns are 'refocussed' to the top left corner of the CRT and the electron beams are temporarily switched off). Flipping the buffers updates the front buffer instantaneously but the back buffer will contain old data. As the front buffer only contains one complete frame of animation, no tearing will occur.

However, the above mentioned technique has a disadvantage in that, even if only a very small portion of an image is changed, generally the image in the back buffer is completely regenerated resulting in increased processing time. For example, it is common to construct pictures in which some objects are changed dynamically while others remain static. Often a large portion of the image does not need to be re-rendered.

The above mentioned technique does not attempt to minimise the re-rendering required.

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

511420.doc Disclosure of the Invention According to one aspect of the present invention there is provided a method of updating an image on a system utilising a plurality of memory units, said method comprising the steps of: storing a first image in a first memory unit having a first designation; determining a current update region representing a region of said first image to be updated; calculating a difference region representing the difference between said current update region and one previous update region; copying a first portion of said first image to a second memory unit having a second designation, wherein said first portion is dependent on said difference region; storing said current update region; rendering a second portion of said image to said second memory unit, said second portion being represented by said current update region; and changing said designations of at least said first and second memory units.

.According to another aspect of the present invention there is provided a method of updating an image on a system utilising a plurality of memory units, said method S.:..comprising the steps of: storing a first image in a first memory unit having a first designation; 20 determining a current update region representing a region of said first image to oo be updated; calculating a difference region representing the difference between said current update region and the union of one or more previous update regions; copying a first portion of said first image to a second memory unit having a 25 second designation, wherein said first portion is dependent on said difference region; storing said current update region; rendering a second portion of said image to said second memory unit, said second portion being represented by said current update region; and changing said designations of at least said first and second memory units.

According to another aspect of the present invention there is provided a method of updating an image on a system utilising at least a first memory unit containing a first image and a second memory unit containing a second image, said method comprising at least the step of copying a first portion of said first image to said second memory unit, 511420.doc wherein said first portion is dependent on a difference region representing the difference between a current update region and one previous update region.

According to still another aspect of the present invention there is provided a method of updating an image on a system utilising at least a first memory unit containing a first image and a second memory unit containing a second image, said method comprising at least the step of copying a first portion of said first image to said second memory unit, wherein said first portion is dependent on a difference region representing the difference between a current update region and a union of two or more previous update regions.

According to still another aspect of the present invention there is provided a method of updating an image on a system utilising at least a first memory unit containing a first image and a second memory unit containing a second image, said method comprising at least the step of copying a first portion of said first image to said second memory unit, wherein said first portion is dependent on prior knowledge of at least one previous update region of said second image.

According to still another aspect of the present invention there is provided an apparatus for updating an image on a system utilising a plurality of memory units, said S"apparatus comprising: means for storing a first image in a first memory unit having a first designation; 20 means for determining a current update region representing a region of said first ooo* image to be updated; means for calculating a difference region representing the difference between said current update region and one previous update region; means for copying a first portion of said first image to a second memory unit S 25 having a second designation, wherein said first portion is dependent on said difference region; means for storing said current update region; means for rendering a second portion of said image to said second memory unit, said second portion being represented by said current update region; and means for changing said designations of at least said first and second memory units.

According to still another aspect of the present invention there is provided a computer readable medium, having a program recorded thereon, where the program is 511420.doc configured to make a computer execute a procedure to update an image on a system utilising a plurality of memory units, said program comprising: code for storing a first image in a first memory unit having a first designation; code for determining a current update region representing a region of said first image to be updated; code for calculating a difference region representing the difference between said current update region and one previous update region; code for copying a first portion of said first image to a second memory unit having a second designation, wherein said first portion is dependent on said difference region; code for storing said current update region; code for rendering a second portion of said image to said second memory unit, said second portion being represented by said current update region; and code for changing said designations of at least said first and second memory 15 units.

.oo.

Brief Description of the Drawings The preferred embodiment of the present invention will now be described with .reference to the drawings, in which: Fig. 1 is a flow diagram of a method of updating image data utilising a double buffer in accordance with a preferred embodiment of the present invention; Fig. 2 shows double buffers of a double buffering system before either buffer has been initialised, in accordance with the method of Fig. 1; S"Fig. 3 shows the double buffers of Fig. 1 after the back buffer has been updated for the first time but before the buffers have been flipped; 25 Fig. 4 shows the buffers of Fig. 3 after the buffers have been flipped; Fig. 5 shows the buffers of Fig. 4 after the back buffer has been updated again; Fig.6 shows the buffers of Fig. 5 after an invalid region in the back buffer has had the corresponding section of the front buffer copied to it; Fig. 7 shows the buffers of Fig. 6 after the buffers have been flipped; Fig.8 shows the buffers of Fig. 7 after the back buffer has been updated; Fig. 9 shows the buffers of Fig. 8 after the invalid region of the back buffer has had a corresponding section of the front buffer copied to it; Fig. 10 shows the buffers of Fig. 9 after they have been flipped; 511420.doc Fig. 11 is a schematic block diagram of a general-purpose computer upon which the preferred embodiment of the present invention can be practiced; Fig. 12(a) shows a sequence of images being updated; and Fig. 12(b) shows a representation of a double buffering system used to update the images of Fig. 12(a).

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. 12(a) shows a sequence of pixel images 1200, 1202 and 1204, depicting a stick man catching a ball. Fig. 12(b) shows two buffers 1208 and 1210 representing a double buffering system. The buffer 1208 is commonly known as the "front buffer", being formed in a first memory unit, and is used to refresh the image 1200. The buffer 1210 is commonly known as the "back buffer", being formed in a second memory unit, and is used to store any updates to the image 1200, as the image 1200 changes. Assuming oo.o both buffers 1208 and 1210 of the double buffering system are initially completely valid they both contain pixel data that is consistent with the image 1200 being displayed), when a change needs to be made to the image 1200 within any spatial region [hereinafter update region], for example region 1206, the back buffer 1210 needs to be updated with pixel data within that region 1206. After this happens, the front buffer 1208 will still contain the old (now invalid) data within that region 1206. The role of the buffers 1208 and 1210 can now be swapped the buffers are flipped), such that the buffer 1210 will become a new front buffer and be used to refresh the image 1202, whilst the buffer 1208 will become a new back buffer and be used to store any updates to the image 1202, as the image 1202 changes. At the instant that the buffers 1208 and 1210 are flipped, the new back buffer 1208 will contain invalid data within a region equivalent to the current update region 1206 and the front buffer 1210 will contain data that is completely valid compared to the changed image 1202.

Now the new front buffer 1210 is valid and the new back buffer 1208 is valid over all but a portion, being equivalent to the update region 1206, of its area. Updating a further portion of the back buffer 1208, for example within the region 1212 of the changed image 1204, will mean that the back buffer 1208 is invalid inside the previously invalid region less any region where the invalid region and the current update region 1212 511420.doc overlap the region 1214 which is shaded in the changed image 1204 of Fig. 12). The term "substantially consistent" will be used to describe the situation where the front buffer of a double buffering system is valid and the back buffer is valid over all but a known region of the area of the back buffer. Conventionally, the back buffer of a double buffering system has been completely re-rendered prior to every flip, in order to ensure that the back buffer is completely valid before flipping the buffers. However, as discussed above, this method has the disadvantage that it results in increased processing time.

The preferred embodiment is a method and apparatus for updating an image utilising a double buffering system. The method of the preferred embodiment takes advantage of knowledge of the content of a static portion of the image in order to minimise any re-rendering necessary to keep a back buffer of the double buffering system up-to-date. The preferred method updates the double buffer from a changed image, for example the image 1202, so that a front buffer is consistent with the image 1202 and the back buffer is "substantially consistent" with the image 1202. The method of the preferred embodiment copies the difference of an invalid region and a current update region from the front buffer to the back buffer of a double buffering system before, after, S:i" or in parallel with the back buffer's re-render, as long as it is copied before the flip. In both the conventional method, as discussed above, and the preferred method, the front buffer will be entirely valid after the flip, but the back buffer will be invalid. The region of invalidity of the back buffer is limited to the region of the image that was changed.

Therefore, both the conventional method and the method of the preferred embodiment S preserve the "substantial consistency" of the buffers. However, processing time is •markedly reduced with the method according to the preferred embodiment. The preferred 25 method is particularly advantageous where only a small region, for example region 1206, of the total display area requires updating. The preferred method minimises the pixel area that must be rendered to the back buffer of a double buffering system and minimises the pixel area that must be copied between the front and back buffers. In accordance with the method of the preferred embodiment, the invalid region is either the entire back buffer in the instance prior to the back buffer being updated the first time; or (ii) the previous update region.

The preferred method is preferably practiced using a conventional generalpurpose computer system 1100, such as that shown in Fig. 11 wherein the preferred method may be implemented as software, such as an application program executing 511420.doc within the computer system 1100. In particular, the method of updating image data utilising a double buffer in accordance with a preferred embodiment of the present invention is effected by instructions in the software that are carried out by the computer.

The software may be divided into two separate parts; one part for carrying out the updating method; and another part to manage the user interface between the latter and the user. The software may be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer from the computer readable medium, and then executed by the computer. A computer readable medium having such software or computer program recorded on it is a computer program product. The use of the computer program product in the computer preferably effects an advantageous apparatus for updating image data utilising a double buffer in accordance with the embodiment of the invention.

The computer system 1100 comprises a computer module 1101, input devices such as a keyboard 1102 and mouse 1103, output devices including a printer 1115 and a display device 1114. A Modulator-Demodulator (Modem) transceiver device 1116 is .0O* used by the computer module 1101 for communicating to and from a communications S. network 1120, for example connectable via a telephone line 1121 or other functional medium. The modem 1116 can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN).

The computer module 1101 typically includes at least one processor unit 1105, a memory unit 1106, for example formed from semiconductor random access memory (RAM) and read only memory (ROM), input/output interfaces including a video interface 1107, and an I/O interface 1113 for the keyboard 1102 and mouse 1103 and optionally a joystick (not illustrated), and an interface 1108 for the modem 1116. A storage device 1109 is provided and typically includes a hard disk drive 1110 and a floppy disk drive 1111. The processor 1105 can also have an area of memory which is commonly known as cache (not illustrated) associated with it. Cache is formed from semiconductor random access memory (RAM) and is used for the temporary storage of data. A magnetic tape drive (not illustrated) may also be used. A CD-ROM drive 1112 is typically provided as a non-volatile source of data. The video interface 1107 also includes at least two buffers, a front buffer (not illustrated) and a back buffer (not illustrated), in order to perform the method of updating image data in accordance with a preferred embodiment of the present invention. The components 1105 to 1113, 1123 and 1125 of the computer module 1101, typically communicate via an interconnected 511420.doc bus 1104 and in a manner which results in a conventional mode of operation of the computer system 1100 known to those in the relevant art.

Typically, the application program of the preferred embodiment is resident on the hard disk drive 1110 and read and controlled in its execution by the processor 1105.

Intermediate storage of the program and any data fetched from the network 1120 may be accomplished using the semiconductor memory 1106, possibly in concert with the hard disk drive 1110. In some instances, the application program may be supplied to the user encoded on a CD-ROM or floppy disk and read via the corresponding drive 1112 or 1111, or alternatively may be read by the user from the network 1120 via the modem device 1116. Still further, the software can also be loaded into the computer system 1100 from other computer readable medium including magnetic tape, a ROM or integrated circuit, a magneto-optical disk, a radio or infra-red transmission channel between the computer module 1101 and another device, a computer readable card such as a PCMCIA card, and the Internet and Intranets including email transmissions and information recorded on websites and the like. The foregoing is merely exemplary of relevant St..

computer readable mediums. Other computer readable mediums may be practiced S: without departing from the scope and spirit of the invention.

••The method of updating image data utilising a double buffer may alternatively be implemented in dedicated hardware such as one or more integrated circuits performing functions or sub functions of the preferred method. Such dedicated hardware may include graphics processors, digital signal processors, or one or more microprocessors and associated memories.

S"Fig. 1 is a flow diagram of a method of updating image data utilising a double buffer in accordance with a preferred embodiment of the present invention. The method of Fig. 1 is an iterative process that continues until buffers no longer need to be displayed.

The method commences at step 100, where a current update region is initialised to the total display area. The current update region represents those portions of an image representation (eg. a set of rectangles or a quad-tree representation) that are required to be changed. The image representation is known by the system on which the preferred method is being implemented and the image representation may be stored in main memory 1106 or cache (not illustrated). The image representation is updated with every iteration of the preferred method to reflect the changes to the image. At the next step 101, a previous update region old update region) is initialised to be equal to an empty set.

At the next step 102, the back buffer is rendered within the area represented by the current 511420.doc update region. The process continues at step 103, where a difference region is calculated.

The difference region represents a region of the image contained in the front buffer that must be copied to the back buffer and is equal to the old update region less the current update region. The step of copying the difference region to the back buffer overcomes the need to re-render the entire back buffer. It is preferred that the difference operation is efficient in space and time. Gains made by blitting smaller amounts of data could be rendered moot by a particularly inefficient representation. At the next step 105, the difference region is copied from the front buffer to the back buffer. The process continues at step 107, where the designations of the front and back buffers are flipped. At the next step 109, the current update region is saved in memory. At every iteration of the preferred method, the current update region must be saved for use in the next step. The current update region can be saved to cache or main memory depending upon the particular application in which the preferred method is being implemented. The process continues at step 111, where it is determined whether or not any more buffers need to be 15 displayed. If more buffers need to be displayed, the process continues at step 113, where a new update region of the current image representation being rendered is determined and the process then returns to step 103. The process concludes at step 111, if buffers no longer need to be displayed.

Figs. 2 to 10 show the operation of the buffers in an example of updating an 20 image utilising a double buffering system in accordance with the method of the preferred *embodiment. Fig. 2 shows a pair of buffers as a flipping pair before either buffer has been initialised. The buffers initially are labelled F (front) with a region 201 and B (back) with a region 202 and both buffers are invalid over the entire display region. The back o*o4 buffer is updated a first time, such that the region 301 of F is invalid and the region 302 of 25 B is valid, as seen in Fig. 3. As far as the display seen by a user is concerned, nothing has changed at this point. The buffers are flipped a first time, such that the designation of the buffers is swapped changing the labels F and B, and thus the region 401 of B is completely invalid and the region 402 ofF is entirely valid, as seen in Fig. 4.

Continuing the example, if a small portion of the image in the back buffer is updated, representing a region of the image that has changed, then the new update region 501 of B is valid and the difference of the old and new update regions 502 of B is invalid, as seen in Fig. 5. The front buffer F still contains an image that is consistent with the previously displayed image. However, at this point the displayed image as seen by the user has not changed. F contains regions 504 and 505, as seen in Fig. 5. The region 504 511420.doc represents the region of the image that has changed. The difference region is copied from F to B such that B's update region 601 and its difference region 602 are valid, and F with regions 603 and 604, still contains a consistent image, as seen in Fig. 6. As noted previously, the step of copying the difference region to the back buffer overcomes the need to re-render the entire back buffer. It is noted however that region 603 is no longer current. The buffers are flipped swapping the labels F and B and resulting in a valid front buffer 701, an invalid portion of the back buffer 702 and a valid portion of the back buffer 703, as seen in Fig 7.

The example has now progressed to a typical iteration of the preferred method and the following description of Figs 8 to 10 are an example of one full iteration of the update loop which is shown in Fig 1. A current update region is determined (step 113 of Fig. 1) and the back buffer is updated. This results in F, having regions 801 and 802, still containing a consistent image. At this point the back buffer can be divided into three sections; the updated portion 803, the invalid portion 804, and the valid portion 805. The 15 updated portion 803 represents the region of the image that has changed. A difference ,.region 804, being equal to the old update region 702 less the current update region 803 (step 103 of Fig. is determined and then copied from F to B (step 105 of Fig. At this stage, F can be divided into an invalid region 901 and a valid region 902, as seen in Fig. 9. Further, the back buffer can be divided into an updated region 903 and two valid 20 regions 905 and 906. The flipping of the buffers (step 107 of Fig. 1) will result in a back buffer divided into valid 1002 and invalid 1001 regions and a valid front buffer 1003, as seen in Fig. The cost execution time) of performing the method of the preferred embodiment is the sum of the costs of the following components: 25 the cost of rendering to the back buffer being approximately proportional to the number of pixels in the new update region; (ii) the cost of a blit from the front buffer to the back buffer being approximately proportional to the number of pixels in the difference region which is less than or equal to the number of pixels in the old update region; and (iii) the cost of calculating the difference region being dependent on the implementation of the region description structure.

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

The following pseudo-code shown in Table 1 contains an algorithm suitable for implementing the preferred method. The pseudo-code assures that the buffers of a system on which the preferred method is implemented, remain consistent with a representation of the image that the buffers are being rendered from, as the designation of the buffers is swapped. The method in accordance with the preferred embodiment is preferably implemented in an environment capable of supporting a region representation (eg. a quadtree representation). Those skilled in the art will appreciate that alternate representations other than a quad-tree representation can be used as the region representation. For example, an alternate representation can include one or more rectangles (ie. a set of rectangles) approximating a region of the image, each rectangle typically being defined by two diagonally opposite co-ordinate pairs.

oooo o o oooe c e.oo 511420.doc Table 1 Initialise update region to the total display area.

Loop Call update(double buffer, image representation, update region).

If buffers need no longer be displayed Exit endif Perform any preprocessing that needs to be performed before the new update region can be known.

Calculate the new update region according to what portions of the image representation need to be changed.

Change the image representation as necessary.

endloop (where the update subroutine is defined as follows:) function update(double buffer, image representation, update region) begin S. Calculate difference region .double buffer's old update region update region.

The order of thefollowing two actions can be swapped.

eooe Use image representation to re-render to back buffer within update e region.

Copy the difference region from the front buffer to the back buffer.

Flip the double buffer's front and back buffers.

Save update region as double buffer's old update region.

End The foregoing describes only one embodiment of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiment(s) being illustrative and not restrictive. For example, the preferred embodiment can be implemented on a system utilising triple (or higher order) buffering. An n-buffer flipping chain consists of a front buffer and n 1 back buffers. Flipping such a chain "rotates" the buffers, so that the front buffer becomes 511420.doc the last back buffer, the first back buffer becomes the front buffer, and the remaining back buffers are "promoted" closer to the front. In such a flipping chain, after the first back buffer has been updated it will still be invalid within the region calculated as the difference of the union of the previous n 1 update regions and the current update region.

Further, other methods can be used to ensure that the back buffer is completely valid before flipping the buffers. For example, the invalid region of the back buffer can be copied from the front buffer before the back buffer is updated. Alternatively, the entire area outside the update region of the back buffer can be copied from the front buffer to the back buffer after the back buffer's update region has been re-rendered and before the flip. Still further, the union of the invalid region and the update region can be rerendered.

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 15 corresponding meanings.

••oo o• 0. o.

511420.doc

Claims (15)

1. A method of updating an image on a system utilising a plurality of memory units, said method comprising the steps of: storing a first image in a first memory unit having a first designation; determining a current update region representing a region of said first image to be updated; calculating a difference region representing the difference between said current update region and one previous update region; copying a first portion of said first image to a second memory unit having a second designation, wherein said first portion is dependent on said difference region; storing said current update region; rendering a second portion of said image to said second memory unit, said second portion being represented by said current update region; and 15 changing said designations of at least said first and second memory units.

2. The method according to claim 1, wherein said current update region is represented by a quad-tree. oo€1 20

3. The method according to claim 1, wherein said current update region is represented by a set of rectangles.

4. The method according to any one of the previous claims, wherein said first and second designations of said first and second memory units are swapped.

The method according to any one of the claims 1 to 3, including the further step of changing a designation of a plurality of memory units.

6. The method according to claim 5, wherein said designation represents an order of priority of said plurality of memory units.

7. The method according to claim 6, wherein said plurality of memory units are promoted in said order of priority.

511420.doc

8. The method according to any one of claims 6 or 7, wherein said designation of said first memory unit is changed to the lowest priority.

9. A method of updating an image on a system utilising a plurality of memory units, said method comprising the steps of: storing a first image in a first memory unit having a first designation; determining a current update region representing a region of said first image to be updated; calculating a difference region representing the difference between said current update region and the union of one or more previous update regions; copying a first portion of said first image to a second memory unit having a second designation, wherein said first portion is dependent on said difference region; storing said current update region; rendering a second portion of said image to said second memory unit, said S:r 15 second portion being represented by said current update region; and .o changing said designations of at least said first and second memory units.

10. The method according to claim 9, wherein said current update region is S.. represented by a quad-tree. o

11. The method according to claim 9, wherein said current update region is represented by a set of rectangles. *SSS

12. The method according to any one of the claims 9 to 11, including the further step 25 of changing a designation of a plurality of memory units.

13. The method according to claim 12, wherein said designation represents an order of priority of said plurality of memory units.

14. The method according to claim 13, wherein said plurality of memory units are promoted in said order of priority. The method according to any one of claims 12 or 14, wherein said designation of said first memory unit is changed to the lowest priority. 511420.doc 16. A method of updating an image on a system utilising at least a first memory unit containing a first image and a second memory unit containing a second image, said method comprising at least the step of copying a first portion of said first image to said second memory unit, wherein said first portion is dependent on a difference region representing the difference between a current update region and one previous update region. 17. The method according to claims 16, comprising the further steps: determining said current update region representing a region of said first image to be updated; calculating said difference region; storing said current update region. 18. The method according to any one of claims 16 to 17, wherein each said memory unit includes a designation. 19. The method according to claim 18, including the further step of changing said designation of at least said first and second memory units. The method according to any one of claims 16 to 19, wherein said current update region is represented by a quad-tree. 21. The method according to any one of claims 16 to 19, wherein said current update 0o S" 25 region is represented by a set of rectangles. 22. The method according to any one of claims 18 to 21, wherein said designation of said first and second memory units are swapped. 23. The method according to any one of the claims 18 to 22, including the further step of changing a designation of a plurality of memory units. 24. The method according to claim 23, wherein said designation represents an order of priority of said plurality of memory units. 511420.doc -17- The method according to claim 24, wherein said plurality of memory units are promoted in said order of priority. 26. The method according to any one of claims 24 or 25, wherein said designation of said first memory unit is changed to a lowest priority. 27. A method of updating an image on a system utilising at least a first memory unit containing a first image and a second memory unit containing a second image, said method comprising at least the step of copying a first portion of said first image to said second memory unit, wherein said first portion is dependent on a difference region representing the difference between a current update region and a union of two or more previous update regions.

15 28. The method according to claims 27, comprising the further steps: ooo o determining said current update region representing a region of said first image to be updated; ""calculating said difference region; storing said current update region. 0o0. 29. The method according to any one of claims 27 to 28, wherein each said memory unit includes a designation. 30. The method according to claim 29, including the further step of changing said 25 designation of at least said first and second memory units. 31. The method according to any one of claims 27 to 30, wherein said current update region is represented by a quad-tree. 32. The method according to any one of claims 27 to 30, wherein said current update region is represented by a set of rectangles. 33. The method according to any one of claims 29 to 32, wherein said designation of said first and second memory units are swapped. 511420.doc 34. The method according to any one of the claims 29 to 33, including the further step of changing a designation of a plurality of memory units. 35. The method according to claim 34, wherein said designation represents an order of priority of said plurality of memory units. 36. The method according to claim 35, wherein said plurality of memory units are promoted in said order of priority. 37. The method according to any one of claims 35 or 36, wherein said designation of said first memory unit is changed to a lowest priority. 38. A method of updating an image on a system utilising at least a first memory unit containing a first image and a second memory unit containing said first image except for a known invalid region, said method comprising at least the step of copying a portion of .i said first image from said first memory unit to said second memory unit, wherein said i portion is dependent on said known invalid region. *oo* 39. The method according to claim 38, comprising the further steps: determining said current update region representing a region of said first image to be updated; calculating said difference region; -"storing said current update region. S" The method according to any one of claims 38 to 39, wherein each said memory unit includes a designation. 41. The method according to claim 40, including the further step of changing said designation of at least said first and second memory units. 42. The method according to any one of claims 38 to 41, wherein said current update region is represented by a quad-tree. 511420.doc -19- 43. The method according to any one of claims 38 to 41, wherein said current update region is represented by a set of rectangles. 44. The method according to any one of claims 40 to 43, wherein said designation of said first and second memory units are swapped. The method according to any one of the claims 40 to 44, including the further step of changing a designation of a plurality of memory units. 46. The method according to claim 45, wherein said designation represents an order of priority of said plurality of memory units. 47. The method according to claim 46, wherein said plurality of memory units are promoted in said order of priority. 48. The method according to any one of claims 46 or 47, wherein said designation of said first memory unit is changed to a lowest priority. 49. A method of updating an image on a system utilising at least a first memory unit 20 containing a first image and a second memory unit containing a second image, said method comprising at least the step of copying a first portion of said first image to said second memory unit, wherein said first portion is dependent on prior knowledge of at least one previous update region of said second image. 25 50. The method according to claim 49, wherein said portion is equal to a difference region representing the difference between a current update region and one previous update region. 51. The method according to claim 49, wherein said portion is equal to a difference region representing the difference between a current update region and the union of two or more previous update regions. 52. The method according to any one of claims 50 to 51, comprising the further steps: 511420.doc determining said current update region representing a region of said first image to be updated; calculating said difference region; storing said current update region; and rendering an update portion of said image to said second memory unit, wherein said update portion is represented by said current update region. 53. The method according to any one of claims 49 to 52, wherein each said memory unit includes a designation. 54. The method according to claim 53, including the further step of changing said designation of at least said first and second memory units. The method according to any one of claims 49 to 54, wherein said current update region is represented by a quad-tree. 56. The method according to any one of claims 49 to 54, wherein said current update ""region is represented by a set ofrectangles. 20 57. The method according to any one of claims 53 to 56, wherein said designation of o*oo said first and second memory units are swapped. •ooo 58. The method according to any one of the claims 53 to 56, including the further step of changing a designation of a plurality of memory units. o• 59. The method according to claim 58, wherein said designation represents an order of priority of said plurality of memory units. The method according to claims 58 or 59, wherein said plurality of memory units are promoted in said order of priority. 61. The method according to any one of claims 59 or 60, wherein said designation of said first memory unit is changed to a lowest priority. 511420.doc -21- 62. An apparatus for updating an image on a system utilising a plurality of memory units, said apparatus comprising: means for storing a first image in a first memory unit having a first designation; means for determining a current update region representing a region of said first image to be updated; means for calculating a difference region representing the difference between said current update region and one previous update region; means for copying a first portion of said first image to a second memory unit having a second designation, wherein said first portion is dependent on said difference region; means for storing said current update region; means for rendering a second portion of said image to said second memory unit, said second portion being represented by said current update region; and means for changing said designations of at least said first and second memory units. 63. The apparatus according to claim 62, wherein said current update region is represented by a quad-tree. 64. The apparatus according to claim 62, wherein said current update region is represented by a set of rectangles. The apparatus according to any one of claims 62 to 64, wherein said first and "second designations of said first and second memory units are swapped. o• S 66. The apparatus according to any one of the claims 62 to 64, further including means for changing a designation of a plurality of memory units. 67. The apparatus according to claim 66, wherein said designation represents an order of priority of said plurality of memory units. 68. The apparatus according to claim 67, wherein said plurality of memory units are promoted in said order of priority. 511420.doc 69. The apparatus according to any one of claims 67 or 68, wherein said designation of said first memory unit is changed to the lowest priority. A computer readable medium, having a program recorded thereon, where the program is configured to make a computer execute a procedure to update an image on a system utilising a plurality of memory units, said program comprising: code for storing a first image in a first memory unit having a first designation; code for determining a current update region representing a region of said first image to be updated; code for calculating a difference region representing the difference between said current update region and one previous update region; code for copying a first portion of said first image to a second memory unit having a second designation, wherein said first portion is dependent on said difference region; code for storing said current update region; .•"code for rendering a second portion of said image to said second memory unit, said second portion being represented by said current update region; and S.:i code for changing said designations of at least said first and second memory units. 71. The computer readable medium according to claim 70, wherein said current update region is represented by a quad-tree. 72. The computer readable medium according to claim 70, wherein said current update region is represented by a set of rectangles. 73. The computer readable medium according to any one of claims 70 to 72, wherein said first and second designations of said first and second memory units are swapped. 74. The computer readable medium according to any one of the claims 70 to 72, further including means for changing a designation of a plurality of memory units. The computer readable medium according to claim 74, wherein said designation represents an order of priority of said plurality of memory units. 511420.doc -23- 76. The computer readable medium according to claim 75, wherein said plurality of memory units are promoted in said order of priority. 77. The computer readable medium according to any one of claims 75 or 76, wherein said designation of said first memory unit is changed to the lowest priority. 78. A method of updating an image substantially as herein described with reference to Figs. 1 to 12(b). 79. An apparatus for updating an image substantially as herein described with reference to Figs. 1 to 12(b). A computer readable medium, having a program recorded thereon, where the program is configured to make a computer execute a procedure to update an image on a system utilising a plurality of memory units, said program being substantially as herein described with reference to Figs. 1 to 12(b). DATED this Twenty-sixth Day of June 2000 Canon Kabushiki Kaisha Patent Attorneys for the Applicant SPRUSON FERGUSON 511420.doc