AU742078B2 - Region-based image compositing - Google Patents

Description

S F Ref: 471440

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

C

S

S. Name and Address of Applicant: Actual Inventor(s): Address for Service: Invention Title: Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome Ohta-ku Tokyo 146

JAPAN

George Polltis Spruson Ferguson, Patent Attorneys Level 33 St Martins Tower, 31 Market Street Sydney, New South Wales, 2000, Australia Region-Based Image Compositing ASSOCIATED PROVISIONAL APPLICATION DETAILS [311 Application No(s) [33] Country PP5686 AU [32] Application Date 3 September 1998 The following statement is a full description of this invention, including the best method of performing it known to me/us:- 5815 -1- REGION BASED IMAGE COMPOSITING Field of the Invention The present invention relates to the creation of computer-generated images both in the form of still pictures and video imagery, and, in particular, relates to efficient process, apparatus, and system for creating an image made up by compositing multiple components.

Background Computer generated images are typically made up of many differing components or graphical elements which are rendered and composited together to create a final image.

In recent times, an "opacity channel" (also known as a "matte", an "alpha channel", or simply "opacity") has been commonly used. The opacity channel contains information regarding the transparent nature of each element. The opacity channel is stored alongside each instance of a colour, so that, for example, a pixel-based image with opacity stores an opacity value as part of the representation of each pixel. An element without explicit 15 opacity channel information is typicaiiy understood io be fully opaque within some defined bounds of the element, and assumed to be completely transparent outside those .bounds.

An expression tree offers a systematic means for representating an image in terms of its constituent elements and which facilitates later rendering. Expression trees typically comprise a plurality of nodes including leaf nodes, unary nodes and binary nodes. Nodes of higher degree, or of alternative definition may also be used. A leaf node, being the outer most node of an expression tree, has no descendent nodes and represents a primitive constituent of an image. Unary nodes represent an operation which modifies the pixel data coming out of the part of the tree below the unary operator.

Unary nodes include such operations as colour conversions, convolutions (blurring etc) and operations such as red-eye removal. A binary node typically branches to left and right subtrees, wherein each subtree is itself an expression tree comprising at least one leaf node. Binary nodes represent an operation which combines the pixel data of its two children to form a single result. For example, a binary node may be one of the standard "compositing operators" such as OVER, IN, OUT, ATOP and alpha-XOR, examples of which and other are seen in Fig. Several of the above types of nodes may be combined to form a compositing tree.

An example of this is shown in Fig. 1. The result of the left-hand side of the compositing tree may be interpreted as a colour converted image being clipped to spline boundaries.

471440 CFP0142AU pen_scm1 [I:\ELEC\CISRA\OPENSCRN\O_SCRNO01 ]471440.doc:IAD -2- This construct is composited with a second image.

Although the non-transparent area of a graphical element may of itself be of a certain size, it need not be entirely visible in a final image, or only a portion of the element may have an effect on the final image. For example, assume an image of a certain size is to be displayed on a display. If the image is positioned so that only the top left corner of the image is displayed by the display device, the remainder of the image is not displayed. The final image as displayed on the display device thus comprises the visible portion of the image, and the invisible portion in such a case need not be rendered.

Another way in which only a portion of an element may have an effect is when the portion is obscured by another element. For example, a final image to be displayed (or rendered) may comprise one or more opaque graphical elements, some of which obscure other graphical elements. Hence, the obscured elements have no effect on the final image.

A conventional compositing model considers each node to be conceptually infinite 5 in extent. Therefore, to construct the final image, a conventional system would apply a compositing equation at every pixel of the output image. Interactive frame rates of the order greater than 15 frames per second can be achieved by relatively brute-force approaches in most current systems, because the actual pixel operations are quite simple and can be highly optimised. This highly optimised code is fast enough to produce acceptable frame rates without requiring complex code. However, this is certainly not true in a compositing environment.

.i The per-pixel cost of compositing is quite high. This is because typically an image is rendered in 24-bit colour in addition to an 8-bit alpha channel, thus giving 32 bits per pixel. Each compositing operator has to deal with each of the four channels. Therefore, the approach of completely generating every pixel of every required frame when needed is inefficient, because the per-pixel cost is too high.

Problems arise with prior art methods when rendering graphical objects which include transparent and partially-transparent areas. Further, such methods typically do not handle the full range of compositing operators.

Summary of the Invention It is an object of the present invention to substantially overcome, or ameliorate, one or more of the deficiencies of the above mentioned methods by the provision of a method for creating an image made up by compositing multiple components.

According to one aspect of the present invention there is provided a method of creating an image, said image to be formed by rendering and compositing at least a 471440 CFP01423AU Open_scm0l [I:\ELEC\CISRA\OPENSCRN\OSCRNOI ]471440.doc: [AD plurality of graphical objects, each said object having a predetermined outline, said method comprising the steps of: dividing a space in which said outlines are defined into a plurality regions, each said region being defined by at least one region outline substantially following at least one of said predetermined outlines or parts thereof and being substantially formed by segments of a virtual grid encompassing said space; manipulating said regions to determine a plurality of further regions, wherein each said further region has a corresponding compositing expression; classifying said further regions according to at least one attribute of said graphical objects within said further regions; modifying each said corresponding compositing expression according to a classification of each said further region to form an augmented compositing expression for each said further region; and compositing said image using each of said augmented compositing expressions.

15 According to another aspect of the present invention there is provided a method of method of creating an image, said image to be formed by rendering and compositing at least a plurality of graphical objects, each said object having a predetermined outline, said method comprising the steps of: dividing a space in which said outlines are defined into a plurality regions, each 20 said region being defined by at least one region outline substantially following at least one of said predetermined outlines or parts thereof and being substantially formed by segments of a virtual grid encompassing said space, wherein each object has two region outlines arranged either side of said predetermined outline to thus define three regions for each said object, and wherein each said region has a corresponding compositing expression; classifying said regions according to at least one attribute of said graphical objects within said regions; modifying each said corresponding compositing expression according to a classification of each said region to form an augmented compositing expression for each said region; and compositing said image using each of said augmented compositing expressions.

According to still another aspect of the present invention there is provided an apparatus for creating an image, said image to be formed by rendering and compositing at least a plurality of graphical objects, each said object having a predetermined outline, said apparatus comprising: 471440 CF1109lc)51AL) Openscrn0 LI:\11II\CISRA\O I'NSCIRN\()SCINO I 47 I440.doc:IAI) -4dividing means for dividing a space in which said outlines are defined into a plurality regions, each said region being defined by at least one region outline substantially following at least one of said predetermined outlines or parts thereof and being substantially formed by segments of a virtual grid encompassing said space; manipulating means for manipulating said regions to determine a plurality of further regions, wherein each said further region has a corresponding compositing expression; classifying means for classifying said further regions according to at least one attribute of said graphical objects within said further regions; modifying means for modifying each said corresponding compositing expression according to a classification of each said further region to form an augmented compositing expression for each said further region; and compositing means for compositing said image using each of said augmented compositing expressions.

According to still another aspect of the present invention there is provided an !5 apparatus for creating an image, said image to be formed by rendering and compositing at least a plurality of graphical objects, each said object having a predetermined outline, said apparatus comprising: dividing means for dividing a space in which said outlines are defined into a plurality regions, each said region being defined by at least one region outline 20 substantially following at least one of said predetermined outlines or parts thereof and being substantially formed by segments of a virtual grid encompassing said space, wherein each object has two region outlines arranged either side of said predetermined outline to thus define three regions for each said object, and wherein each said region has a corresponding compositing expression; classifying means for classifying said regions according to at least one attribute of said graphical objects within said regions; modifying means for modifying each said corresponding compositing expression according to a classification of each said region to form an augmented compositing expression for each said region; and compositing means for compositing said image using each of said augmented compositing expressions.

According to still another aspect of the present invention there is provided a computer program product including a computer readable medium having a plurality of software modules for creating an image, said image to be formed by rendering and compositing at least a plurality of graphical objects, each said object having a 47144(1 :10951AU Ope npcnscriffl [I:\IhI.EC\CISRA\01l[ENSCRN\() SCRNN 11471440.doc:IAD) predetermined outline, said computer program product comprising: dividing module for dividing a space in which said outlines are defined into a plurality regions, each said region being defined by at least one region outline substantially following at least one of said predetermined outlines or parts thereof and being substantially formed by segments of a virtual grid encompassing said space; manipulating module for manipulating said regions to determine a plurality of further regions, wherein each said further region has a corresponding compositing expression; classifying module for classifying said further regions according to at least one attribute of said graphical objects within said further regions; modifying module for modifying each said corresponding compositing expression according to a classification of each said further region to form an augmented compositing expression for each said further region; and compositing module for compositing said image using each of said augmented 15 compositing expressions.

According to still another aspect of the present invention there is provided a computer program product including a computer readable medium having a plurality of software modules for creating an image, said image to be formed by rendering and compositing at least a plurality of graphical objects, each said object having a predetermined outline, said computer program product comprising: dividing module for dividing a space in which said outlines are defined into a plurality regions, each said region being defined by at least one region outline substantially following at least one of said predetermined outlines or parts thereof and being substantially formed by segments of a virtual grid encompassing said space, wherein each object has two region outlines arranged either side of said predetermined outline to thus define three regions for each said object, and wherein each said region has a corresponding compositing expression; classifying module for classifying said regions according to at least one attribute of said graphical objects within said regions; modifying module for modifying each said corresponding compositing expression according to a classification of each said region to form an augmented compositing expression for each said region; and compositing module for compositing said image using each of said augmented compositing expressions.

471440) CII1O0951AU Opccn_scrn01 II\IILLC\CISIA\0I'IhSCtN\(OSCRN(I ]471 440.dnc:IAI) -6- Brief Description of the Drawings A preferred embodiment of the present invention will now be described with reference to the following drawings: Fig. 1 is an example of a compositing tree; Fig. 2 illustrates an image containing a number of overlapping objects and the corresponding compositing tree; Fig. 3 shows the image of Fig. 2 illustrating the different regions which exist in the image and listing the compositing expression which would be used to generate the pixel data for each region; Fig. 4 is the image of Fig. 3, illustrating the compositing operations after being optimised according to one example of the preferred embodiment; Fig. 5 illustrates the result of combining two region descriptions using the Union operation according to the preferred embodiment; Fig. 6 illustrates the result of combining two region descriptions using the S- 15 Intersection operation according to the preferred embodiment; Fig. 7 illustrates the result of combining two region descriptions using the ,Difference operation according to the preferred embodiment; Figs. 8A to 8D illustrate the steps involved in combining two region groups using the Over operation according to the present invention; 20 Fig. 9 illustrates an image and compositing tree according to another example of the preferred embodiment; Fig. 10 illustrates an image and compositing tree according to still another example of the preferred embodiment; Fig. 11 illustrates the effect on the image of Fig. 10 of moving region A; Fig. 12 illustrates an image and compositing tree according to still another example of the preferred embodiment; Fig. 13 illustrates the effect on the image of Fig. 12 of moving region A; Fig. 14 illustrates the effect on the image of Fig. 12 of moving region B; and Fig. 15 illustrates those nodes in a compositing tree which need to have their region groups updated if leaf nodes B and H change; Fig. 16 illustrates a region and its x and y co-ordinates; Fig. 17 illustrates two regions and their x and y co-ordinates; Fig. 18 illustrates an image and compositing tree according to still another example of the preferred embodiment; Fig. 19 illustrates an apparatus upon which the preferred embodiment is 471440) C1110951AII l (pen_san~l I :\ILEC\CISRA\OIINSCRtN\O SCRN()I 1471440.doc:IAI) -7implemented; Fig. 20 depicts the result of a variety of compositing operators useful with the present invention; Fig. 21 illustrates regions formed by combining two circles with non-grid-aligned regions; Fig. 22 illustrates improved regions formed by combining two circles with gridaligned regions; Fig. 23 is a flowchart showing a method of creating an image in accordance with the preferred embodiment; and Appendix 1 is a listing of source code according to the present invention Detailed Description 1.0 Underlying Principles S.The basic shape of operands to compositing operators in most current systems is the rectangle. regardless of the actual shape of the object being composited. It is extremely 15 easy to write an operator which composites within the intersection area of two bounding boxes. However, as a bounding box typically does not accurately represent the actual bounds of a graphical object, this method results in a lot of unnecessary compositing of completely transparent pixels over completely transparent pixels. Furthermore, when the typical make-up of a composition is examined, it can be noticed that areas of many of the objects are completely opaque. This opaqueness can be exploited during the compositing operation. However, these areas of complete opaqueness are usually non-rectangular and so are difficult to exploit using compositing arguments described by bounding boxes. If irregular regions are used for exploiting opaque objects when compositing, then these regions could then be combined in some way to determine where compositing should occur. Furthermore, if any such region is known to be fully transparent or fully opaque, further optimisations are possible.

Most current systems fail to exploit similarities in composition between one frame and the next. It is rare for everything to change from frame to frame and therefore large areas of a compositing tree will remain unchanged. An example of this is where a cartoon type character comprising multiple graphical objects is rendered on a display. If, for example, the character spilt some paint on its shirt in the next frame, then it is not necessary to render the entire image again. For example, the head and legs of the character may remain the same. It is only necessary to render those components of the image that have been altered by the action. In this instance, the part of the shirt on which the paint has been spilt may be re-rendered to be the same colour as the paint, whilst the 4(71440) CI:11095 1AIJ Opcilsanlli lI:\ILEC\CISRA\0oI'ENSCRN\OSCRN( 11471440.dIoc:iAI) remainder of the character stays the same. Exploiting this principle may provide large efficiency improvements. If incremental changes are made to the compositing tree, then only a reduced amount of updating is necessary to affect the change.

Many current graphical systems use what is known as an immediate mode application program interface (API). This means that for each frame to be rendered, the complete set of rendering commands is sent to the API. However, sending the complete set of rendering commands is somewhat inefficient in a compositing environment, as typically, large sections of the compositing tree will be unchanged from one frame to the next, but would be completely re-rendered anyway in immediate mode. The preferred embodiment, on the other hand, is considered by the present inventors to be best described as a retained mode API. Retained mode means that instead of providing the complete compositing tree on a per-frame basis, the user provides an initial compositing tree, and then modifies it on a per-frame basis to effect change. Changes which can be made to the tree include geometrically transforming part or all of the tree, modifying the 15 tree structure (unlinking and linking subtrees), and modifying attributes (eg: color) of individual nodes. Note that such modifications may not necessarily mean that the tree structure, for example as seen in Fig. 1, will change where only the attributes of an Sindividual node have been modified.

The rendering operation of the preferred embodiment is a combination of a number 20 of techniques and assumptions which combine to provide high quality images and high frame rates. Some of the contributing principles are: The use of irregular regions to minimise per-pixel compositing. For example, if one graphical object is on top of another, then pixel compositing is only needed inside the area where the two objects intersect. Having the ability to use irregular regions gives the ability to narrow down areas of interest much more accurately.

(ii) An assumption is made that in the transition from one frame to the next, only part of the tree will change. This can be exploited by caching away expensive-togenerate information regarding the composition so that it can be re-used from one frame to the next. Examples of expensive-to-generate information are regions of interest (boundaries of areas of intersection between objects etc); pixel data (representing expensive composites etc); and topological relationships between objects.

(iii) If an opaque object is composited with another object using the OVER operator, then the opaque object completely obscures what it is composited onto (inside the opaque objects area). This is a very useful property because it means that no expensive pixel compositing is required to achieve the output pixel within the area of overlap. (The 4171440) CIT0951AI 1I1 Opensanm01 [I:\I"IEC\CISRkA\OPINSCRN\()SCRN( I 1471440-doc:IAI) pixel value is the same as that at the equivalent spot on the opaque object). Opaque objects induce similar behaviour in most of the compositing operators. Therefore, the preferred embodiment attempts to exploit opaque areas as much as possible.

Fig. 23 is a flowchart showing a method of creating an image in accordance with the preferred embodiment of the present invention. The image is formed by rendering graphical objects whereby each of the objects has a predetermined boundary outline. The process begins at step 2301, where a space in which the object outlines are defined is divided into a number of regions. Each of the regions is defined by at least one of the predetermined boundary outlines or parts thereof. The regions are formed by segments of a grid which encompasses the space in which the predetermined outlines are defined. At the next step 2303, the regions are manipulated to determine a number of further regions.

Each of the further regions has a corresponding compositing expression. The process of dividing the space into a number of regions and manipulating those regions is described in detail particularly with reference to section 2.3 below. Section 2.3 includes two 15 pseudocode listings which describe steps 2301 and 2303 for the "OVER" and "IN" compositing operations. The process continues at step 2305, where the further regions are classified according to attributes of the objects that fall within the further regions. At the next step 2307, each of the corresponding compositing expressions are modified according to a classification of each of the further regions. The modifications form an 20 augmented compositing expression for each of the further regions. The process of classifying the further regions and modifying each of the corresponding compositing expressions is described in detail particularly with reference to section 2.4 below. Section 2.4 includes two pseudocode listings which describe steps 2305 and 2207 for the "OVER" and "IN" compositing operations. The process concludes at step 2309, where the image is composited using each of the augmented compositing expressions. Step 2309 is described in detail with reference to section 2.6, below, which includes a pseudocode listing demonstrating the compositing process.

Basic Static Rendering Static Rendering deals with the problem of generating a single image from a compositing tree as quickly as possible. Some of the pixel compositing methods of the preferred embodiment will be explained using a static rendering example.

An example of a simple compositing tree which consists of leaf node objects and only using the "OVER" operator is shown in Fig. 2. Conventionally, each node is considered to be conceptually infinite in extent. One method to construct the final image is to apply the compositing equation OVER B) OVER C) OVER (A OVER at 471440) C1110951 AU~ Opell-SCMM II:\I[III-C\CISRA\OIIrENSCI(N\() SCRN 11471440.do:iA[) every pixel of the output image. However, this is quite an inefficient method.

A composition can generally be subdivided into a number of mutually exclusive irregular regions. The above compositing expression may be simplified independently within each region. In the example of Fig. 2, A, C and E represent opaque objects. B and D. on the other hand are partially transparent. Fig. 3 shows the different regions (1-10) produced using the five objects which exist in the example, and the compositing expression which would be used to generate the pixel data for each specific region.

The compositing expressions provided in Fig. 3 make no attempt to exploit the properties of the object's opacity. If these properties are used to simplify the compositing expressions for each region, the expressions of Fig. 4 are obtained resulting in a simplification of the rendering of regions 2, 3, 5, 6, 7, 8 and 9 compared with Fig. 3.

These simplified compositing expressions would result in far fewer pixel compositing operations being performed to produce the final picture.

Fig. 4 represents the region subdivision for the root of the compositing tree.

15 However, every node in the compositing tree can itself be considered the root of a complete compositing tree. Therefore, every node in the compositing tree can have Sassociated with it a group of regions which together represent the region subdivision of the subtree of which the node is the root. Region subdivision provides a convenient means of managing the complexity of a compositing tree and an efficient framework for caching expensive data.

Using the principles noted above, a compositing expression can be simplified dependent upon whether the graphical objects being composited are wholly opaque, wholly transparent or otherwise (herewith deemed "ordinary").

Table 1 shows how the compositing operations of Fig. 20 can be simplified when one or both operands are opaque or transparent.

TABLE 1 Expression A's opacity B's opacity Optimised AoverB Transparent Transparent neither Transparent Ordinary B Transparent Opaque B Ordinary Transparent A Ordinary Ordinary AoverB Ordinary Opaque AoverB Opaque Transparent A Opaque Ordinary A Opaque Opaque A 471440 CIT0951AUIAI ()pell-scrn~l II:\lI-:ECC\CISIRA\OI'ENSCRN\OSCRNO I 1471440-doc:IAI) S t, -11- \r AroverB Transparent Transparent neither Transparent Ordinary B Transparent Opaque B Ordinary Transparent A Ordinary Ordinary BoverA Ordinary Opaque B Opaque Transparent A Opaque Ordinary BoverA Opaque Opaque B AinB Transparent Transparent neither Transparent Ordinary neither Transparent Opaque neither Ordinary Transparent neither Ordinary Ordinary AinB Ordinary Opaque A Opaque Transparent neither Opaque Ordinary AinB Opaque Opaque A ArinB Transparent Transparent neither Transparent Ordinary neither Transparent Opaque neither Ordinary Transparent neither Ordinary Ordinary BinA Ordinary Opaque BinA Opaque Transparent neither Opaque Ordinary B Opaque Opaque B AoutB Transparent Transparent neither Transparent Ordinary neither Transparent Opaque neither Ordinary Transparent A Ordinary Ordinary AoutB Ordinary Opaque neither Opaque Transparent A Opaque Ordinary AoutB Opaque Opaque neither AroutB Transparent Transparent neither Transparent Ordinary B Transparent Opaque B Ordinary Transparent neither Ordinary Ordinary BoutA Ordinary Opaque BoutA Opaque Transparent neither Opaque Ordinary neither Opaque Opaque neither AatopB Transparent Transparent neither Transparent Ordinary B Transparent Opaque B 471440) C111095C IA Openjll~s l0 I:\II-EC\CISRtA\1O1NSCR N\()SCIRNUI 1471 44.docAAD 12- Ordinary Transparent neither Ordinary Ordinary AatopB Ordinary Opaque AatopB Opaque Transparent neither Opaque Ordinary AatopB Opaque Opaque A AratopB Transparent Transparent neither Transparent Ordinary neither Transparent Opaque neither Ordinary Transparent A Ordinary Ordinary BatopA Ordinary Opaque BatopA Opaque Transparent A Opaque Ordinary BatopA Opaque Opaque B AxorB Transparent Transparent neither Transparent Ordinary B Transparent Opaque B Ordinary Transparent A Ordinary Ordinary AxorB Ordinary Opaque AxorB Opaque Transparent A Opaque Ordinary AxorB Opaque Opaque neither 2.1 Basic Data Model Associated with every node in a compositing tree is a group of mutually exclusive regions which together represent the non-transparent area of the node. It should be noted that the region descriptions that the preferred embodiment uses are generally not pixel accurate. A region may in fact contain some transparent pixels. However, any point lying outside of all the regions at a node is certain to be transparent. The set of the mutually exclusive regions at a node is known as a region group. A leaf node region group may contain only one or two regions. The region group at the root of the tree may contain hundreds of regions. Each region in a region group contains the following basic data: A Region Description is a low-level representation of the boundaries of the region. The region descriptions of all the regions in a region group must be mutually exclusive (non-intersecting). However, the preferred embodiment is not limited to using axis-parallel (ie: every side parallel or perpendicular to a scan line of an output device) region descriptions. The preferred embodiment allows region descriptions which more closely represent arbitrary shaped regions.

471440 0C'I1'0951A U O p)pn_scrnOl II:\LL,EC\CISR~A\O)INSCtN\(OSCRN() I j 7144(.doc:IAI)

I

-13- (ii) A Proxy is some means of caching the pixel data resulting from applying the operations specified by the compositing expression at every pixel inside the region description. A proxy can be as simple as a 24-bit colour bitmap, or something much more complicated (such as a run-length encoded description). Fundamentally, a proxy simply has to represent pixel data in some way which makes it efficient to retrieve and use.

Every region group also contains a region description which is the union of all the region descriptions of the regions in the region group. The region description essentially represents the entire coverage of the region group.

2.2 Region Descriptions and Region Arithmetic The region arithmetic and data structure of the preferred embodiment has the following properties: -to allow the representation of complex regions, including convex regions, concave egions and regions with holes. This is necessary so that a region will be reasonably able 15 to follow the geometry of the graphic object it represents; -is space efficient. In a complicated composition there will be many regions. For memory efficiency, it is therefore preferable that the cost of storing these regions is reasonably small; -the region arithmetic should support basic set operations Union, Intersection and Difference; -the above-noted basic operations should be efficient in terms of speed. In a complex compositing tree, it is possible that a large amount of region arithmetic will be undertaken. A poor implementation of region arithmetic could lead to the time taken by region arithmetic being greater than the time saved from the reduction in per-pixel compositing; -it is advantageious if the region description can be geometrically translated efficiently.

In cases where a graphic object is translated, the graphics objects associated regions can then be translated quickly; and -it is sometimes helpful to be able to quickly compare two regions to determine if they are the same. It is not necessary to obtain any other statistics on their similarity, simple equality is all that is required.

Two conventional region description techniques were considered and rejected for the preferred embodiment. These were- Polygons: A polygon can be used to represent almost any object, the disadvantage of using a polygon, however, is that a ploygon's generality makes implementing the set 471440 CIT0951AH~( Opcn_scrn01 AI I:\EEC'\CIS<A\1O'IENSCIRN\()SCRN() I 147I440.duc:IAI) 14operations slow and inefficient.

Quadtrees: Using quadtrees, set operations are easy to implement and are quite efficient. In addition, they can represent a wide variety of regions given sufficient granularity (all edges in a quadtree have to be axis-parallel). Their major failing is that all quadtrees must be aligned on the same grid (granularity). This means that it is impossible to simply translate a quadtree by an arbitrary amount. Unless that amount is a multiple of the underlying grid size, the quadtree will need to be recalculated from the object it describes (otherwise it will keep growing). Therefore, quadtrees are not suitable in application domains where geometric translation is a frequent operation.

The region description data structure of the preferred embodiment can be understood by imagining that along a vertical line every coordinate has a state which is one of either inside or outside the region. The data structure stores those y co-ordinates at which some change of state between inside and outside occurs. For each such y f co-ordinate, the data contains spans of coordinates each of which toggles the state of *to 15 every vertical line running through the data. Each span of x co-ordinates is called a run.

The sequence of runs associated with a y co-ordinate is called a row. For example, the region of Fig. 16 could be described by the following: row y 10 x= 10, x 100 row y 100 x 10, x =100 20 Similarly, the regions of Fig. 17 could be described by the following: row y 10 x 10, x =100 row y 30 x 30, x row y 70 x 30, x row y 100 x +10, x 100 The data representing a region is represented by an array of integer values. There are two "special" values R NEXT IS Y A beginning-of-row marker. Indicates that the next integer in the sequence will represent a y coordinate.

R EOR Stands for End-of-Region. Indicates that the region description has finished.

All other values represent x or y coordinates. The x coordinates in a row represent runs. The first two co-ordinates represent a run, then the next two represent the next run and so on. Therefore, the x coordinates in a row should always be increasing. Also, there 4171440 CIT09O5CAU 0 (1ell-SCI-1101 I I:\LLFC\CI SRA\0I1INSCRIN\()SCINI I 147144().doc:IAI) should always be an even number of x-coordinates in a row. The region data stream for Fig. 17 is shown below.

R NEXT IS Y 10 10 100 R NEXT IS Y 30 30 R NEXT IS Y 70 30 R NEXT IS Y 100 10 100 R EOR The preferred embodiment also contains the bounding box of the region, as this is useful in certain set.operations.

As seen in Fig. 6, if two region descriptions are combined using a Union operation, then the resultant region description will describe an area in which either region description is active.

As seen in Fig. 7, if two region descriptions are combined using the Intersection 15 operation, then the resultant region description will describe an area in which both the region descriptions are active.

If two region descriptions are combined using the Difference operation, then the resultant region will describe an area in which only the first region is active, as seen in Fig. 8.

2.3 Constructing Region Groups: 2.3.1 Constructing Leaf Node Region Groups A region group for a leaf node will typically contain one or more regions, which together fully contain the non-transparent area of the graphical object represented by the leaf node. Typically, the non-transparent area is divided into regions where each region has some property that facilitates optimization. For example, the non-transparent area of some graphical object can be divided into two regions, one fully opaque and the other with ordinary opacity. The above mentioned compositing optimizations would apply where the opaque region is composited.

Alternatively, the leaf node could be subdivided based on some other attribute. For example, a leaf node could be divided into two regions, one representing an area of constant colour, the other representing blended colour. Areas of constant colour may be composited more efficiently than areas with more general colour description.

2.3.1.1 Region Formation and Phasing When creating regions, it is not always beneficial that region boundaries follow graphical object boundaries precisely. What is important is that any property that facilitates optimization is valid at all points within a region said to have that property.

471440 0 C 110951AH O pepn_scrilff I :\I1.1C\CISIRA\OlpE-'NSCIRN\()SCRNO 1471440.doc:IAl) -16- For example, an opaque circle could be covered exactly by one circular region which is classified as opaque, or by two approximate regions, one fully opaque octagonal region inscribed in the circle, and one annular octagonal region of ordinary opacity that includes the remainder of the circle plus some area exterior to the circle.

There is typically a trade-off between how closely region boundaries follow graphical object boundaries and the benefits obtained. If region boundaries follow object boundaries very closely, a lot of work is usually involved in creating the region boundaries and in performing intersections and differences of regions (the reasons for needing to perform such operations are explained in later sections). However, if region boundaries are too approximate, they may either include large areas that are outside the objects' boundaries, resulting in too much unnecessary compositing, or they may fail to include large areas where known properties lead to optimization.

One approach, as illustrated in the appendix, is to limit region boundaries to sequences of horizontal and vertical segments. Using this approach, the typical segment 15 size is chosen so that there is neither too much detail so that the region operations are overburdened, nor too much approximation to result in wasted compositing or insufficient optimization.

One method to improve the efficiency of region operations is to choose as many as is practical of the horizontal and vertical segments of substantially all region boundaries 20 to be in phase. In other words, the horizontal and vertical segments are to be chosen from the horizontal and vertical lines of the same grid. The grid need not be regularly spaced, nor have the same spacing horizontally and vertically, although typically it will.

Choosing the horizontal and vertical segments from the horizontal and vertical lines of the same grid improves the efficiency of region operations by seeking to keep all region boundary detail to the level of detail contained in the underlying grid. Without constraining the majority of region boundary segments to a grid, region operators such as difference and intersection tend to produce a lot more fine detail. For example, in Fig.

21, two circles 901 and 902 are shown with respective regions 903 and 904 that are not grid-aligned. These circles are overlapped yielding difference regions 905 and 907, and intersection region 906. In Fig. 22, the same circles 901 and 902 have regions 913 and 914 that are aligned to grid 910. These circles are overlapped yielding difference regions 915 and 917 and intersection region 916. It can be seen in this example that the gridaligned regions yield less detailed results at the expense of slightly less efficient region coverage. Regions 905, 906 and 907 together contain a total of sixty segments, while regions 915, 916 and 917 together contain only fifty-two.

471440 C'1:1109il Itl ()pciiscrii~l II:\iEC'\CISIRA\0I'1'NSCRN\O SCRN( I 1471440.doc:IAI) 17- 2.3.2 Creating Binary Region Groups The region groups of binary nodes in the compositing tree on the other hand are the result of combining the region groups of their child nodes. It will now be explained how region groups are combined to form new region groups. In this section, for simplicity only "OVER" and "IN" binary nodes will be dealt with. The operations required for binary nodes representing other compositing operators can easily be inferred from combining the "OVER" and "IN" cases in various ways.

For the sake of clarity, the method of the preferred embodiment is initially described without reference to optimization based properties such as opacity.

The following notation will be beneficial when considering binary region group creation: Notation RG1 RG2

RG

RG l-urgn RG2-+urgn RG-+urgn rgli rg2j rg i->rgn rg2j -+rgn rg i-+proxy rg2j-+proxy

I

The region group of the binary node's left child The region group of the binary node's right child The region group of the binary node. It is this region group that is being initialised The region description representing the union of all RGl's region descriptions (RG l's coverage region).

The region description representing the union of all RG2's region descriptions (RG2's coverage region).

The union of all RG's region descriptions (to be initialised) (RG's coverage region) The current region in RGI The current region in RG2 rgli's region description rg2j's region description rgli's proxy rg2j's proxy 2.3.2.1 Constructing "OVER" Region Groups When constructing "OVER" region groups, only areas where the contributing region groups intersect need to be composited. Areas where one operand does not overlap the other involve no compositing. The method is broken into three iterative steps.

First, the coverage region of the region group of the binary node that is being initialised (RG-+urgn) is made equal to the union of the coverage regions of the binary nodes left 471440 CIT0951ALI~C Openjcnio01 II:\EI.EC\CISRA\01'1ENSCIRN\O SCRN() 1471440.doc:IAI) 18child (RGl-+urgn) and the binary node's right child (RG2->urgn). Then, for each region rgi in RG1, the difference (diffrgn) between that region and RG2's coverage region (RG2->urgn) is then calculated. If the difference (diffrgn) is non-empty then a new region with diff rgn as its region description is added to RG. The proxy of this new difference region can be the same as the proxy rgli. No compositing is required to generate it. The difference regions between RG2's regions and RGl's coverage region are similarly constructed and added to RG. Finally, the intersection (inter_rgn) between each region rgli in RG1 and each region rg2i in RG2 is calculated. If the result of this intersection is non-empty, then a new proxy (new_p) is created by compositing rgli's proxy with rg2j's proxy using the over operation with the interrgn. A new region is then added to RG with inter_rgn as its region description and new_p as its proxy. The method of constructing "OVER" groups in accordance with the preferred embodiment is described below using pseudo-code.

15 RG->urgn RG1->urgn union RG2->urgn FOR i 0 TO number of regions in RG1 DO diff rgn rgli->rgn difference RG2->urgn IF diffrgn is non-empty THEN ADD to RG a new region with diffrgn as its region description and 20 rgli->proxy as its proxy. END IF FOR j 0 TO number of regions in RG2 DO inter_rgn rgli-+rgn intersection rg2j->rgn IF inter_rgn is non-empty THEN create new proxy new_p initialised to OVER of rgli->proxy and rg2j->proxy inside inter_rgn.

ADD to RG a new region with inter_rgn as its region description and new_p as its proxy. END IF END DO END DO FOR j 0 TO number of regions in RG2 DO diff_rgn rg2j-+rgn difference RG1->urgn IF diffrgn is non-empty THEN ADD to RG a new region with diff_rgn as its region description and 4171440 0C :1109)51AH 0jOlcn_scrn01 II:\II.IC\CISRA\01PE-'NSCRN\()SCRN() I J47 440.dnc:IAI) 19rg2j--proxy as its proxy. END IF END DO The regions added by the ADD operations marked with asterisks above are termed difference regions since their shape is the result of a difference operation. Such regions are very cheap computationally because their proxies require no compositing.

The only work involved is the administrative overhead of adding a new region to the region group and the cost of the difference operation itself. In accordance with the preferred embodiment, a proxy is inherited from the region (in one of the child region groups) on which it is based. It can be seen that proxies which originate low in the compositing tree can be propagated upwards towards the root with minimal overhead (both in terms of speed and memory) by the use of difference regions.

The regions added by the ADD operation marked with the plus are termed 15 intersection regions. This is because their shape is the result of an intersection operation.

The proxies of such regions are more expensive to generate than difference regions because they involve per-pixel compositing operations to be done within the area defined by the intersection. The more fidelity granted the region descriptions, the greater the saving in pixel processing costs, at the cost of a greater administrative overhead (more complex regions require longer to intersect etc).

Figs. 8A to 8D provide a simple example of combining "OVER" region groups using the above method. The region group resulting from the combination contains regions. 3 difference regions and 2 are intersection regions. Fig. 8A represents two region groups RG1 and RG2 which are to be combined. RG1 contains two regions 81 and 82, whereas RG2 only contains a single region 83. As seen in Fig 8B, for each region in RG1, RG2's region coverage is subtracted from it. If the resultant region is non-empty, the resultant region becomes a region in the new region group. In this example both regions 81 and 83 produce non-empty difference regions 84 and 85 respectively. For each region in RG2, RGl's region coverage is subtracted from it, as seen in Fig 8C. In this example difference region 86 is produced. Finally, every region in RGI is intersected with every region in RG2, as seen in Fig 8D. Any non-empty region becomes a region in the new region group. In this example, regions 81 and 83 produce 87.

Further, regions 82 and 83 produce 88.

2.3.2.2 Constructing "IN" Region Groups The properties of the "IN" operator lead to the fact that an "IN" binary region group 471440 CIT:10951AU1 Opell-SCM01 II:\EIC..\CISRA\OI'I3NSC'R[N\OSCRN( 1471440.doc: lAD only produces pixel data in the region of intersection between the two contributing region groups. Essentially, when compared to the algorithm used for "OVER" region groups, only intersection regions are generated. Therefore, for each region rgli of RGI, and for each region rg2j of RG2 the intersection (inter_rgnij) between rgli and rg2J is calculated.

If the intersection is non-empty then a new proxy (new_p) is created by compositing rgli's proxy with rg2i's proxy using the "in" operation within interrgnii. A new region is then added to RG with inter_rgn as its region description and new_p as its proxy. The pseudocode describing the method of constructing "IN" region groups in accordance to the preferred embodiment is provided below: RG->urgn RG1->urgn intersection RG2->urgn FOR i 0 TO number of regions in RG1 DO FOR j 0 TO number of regions in RG2 DO interrgn rg1,->rgn intersection rg2i->rgn 15 IF inter rgn is non-empty THEN create new proxy new_p initialised to IN of rgl,->proxy and rg2,->proxy inside interrgn.

ADD to RG a new region with interrgn as its region description and new_p as its proxy. 20 END IF END DO END DO The major difference between the "IN" and the "OVER" cases is that the "OVER" case generates difference regions while "IN" does not. In the example demonstrated by Figs. 8A to 8D, only new regions 97 and 98 would be generated, as these are intersection regions. Difference regions 94, 95 and 96 would not be generated using "IN".

Using Table 2 below and the pseudocode examples of "OVER" and the relevant code for other compositing operators can be derived.

2.3.2.3 Constructing Region Groups of Other Compositing Operators Other compositing operators typically generate the same intersection regions as the "OVER" and "IN" cases do. However, they typically differ from one another (as indeed from "OVER" and in what difference regions they generate. This is dependent on the particular properties of each compositing operator. Table 2 summarises which difference regions are generated for some commonly used compositing operators.

471440) CIT0951A )I OpcII-SCM01 4I:\EL-EC\CISRA\OPI-NSCRN\O SCRN) 011471440.doc:iAD -21 TABLE 2 Compositing Operator Generate Diff Rgns from Generate Diff Rgns from RG1? RG2? Over Yes Yes In No No Out Yes No Atop No Yes Xor Yes Yes Plus Yes Yes 2.4 Optimising using Opaque Areas The preferred embodiment stores within each region a flag indicating whether the pixel data in the region proxy is completely opaque. It is therefore possible to reduce the number of per-pixel compositing operations by exploiting the effect opaque operands *e have on the compositing operators.

2.4.1 Opaque Area Optimisation for "Over" Region Groups If an opaque region is "OVER" another region, then there is no need to compute the 10 result of the composite, as no part of the right operand region's proxy is visible through the left operand's opaque proxy. In the preferred embodiment, the resultant region is made to reference the right operand's proxy, which has the same effect as actually doing the composite.

The method for opaque area optimisation for "OVER" region groups is a slightly 15 modified version of the "OVER" region group construction method provided previously.

The only difference is that when calculating the intersection region of the current region .in RG1 and each region of RG2, a check is carried out to see whether the current region in RGI is opaque. If this is the case, then the proxy of the newly calculated region (new_p) will be the proxy of the current region in RG The method is illustrated using the following pseudocode RG->urgn RG1->urgn union RG2->urgn FOR i 0 TO number of regions in RG1 DO diff_rgn rgli-,rgn difference RG2-+urgn IF diffrgn is non-empty THEN ADD to RG a new region with diffrgn as its region description and rg 1->proxy as its proxy. END IF 471440 C"IT09O51AU I pcn_scni01 II:\LI.EC\C I SRA\'I1NSCRtN\() SCN( I147144ii.doc:IAI) -22- FOR j 0 TO number of regions in RG2 DO inter_rgn rgli->rgn intersection rg2j-rgn IF interrgn is non-empty THEN IF rgli is OPAQUE THEN new_p rgli -proxy

ELSE

create new proxy new_p initialised to OVER of rgli->proxy and rg2j-+proxy inside inter_rgn.

END IF ADD to RG a new region with interrgn as its region description and new_p as its proxy. END IF END DO END DO 15 FOR j 0 TO number of regions in RG2 DO diff_rgn rg2j->rgn difference RG1->urgn IF diff rgn is non-empty THEN ADD to RG a new region with diff_rgn as its region description and rg2j->proxy as its proxy. 20 END IF END DO 2.4.2 Opaque Area Optimisation for "IN" Region Groups If a region is "IN" an opaque region, then according to the properties of the "IN" operator, the resultant pixel data is the same as that of the left operand. This can be achieved by having the resultant region simply reference the proxy of the left operand.

The method of the preferred embodiment is a slightly modified version of the "IN" region group construction method provided previously. The only difference is that when calculating the intersection region of the current region in RG1 and each region of RG2, a check is carried out to see whether the current region in RG2 is opaque. If this is the case, then the proxy of the newly calculated region (new_p) will be the proxy of the current region in RG1.

The technique is illustrated using the following pseudocode: 4171440 C1110951AU~l Openjancm0 A[I:\1LEC\CIS RA\OI'INSCIRN\( OSCRNO 11471 440.doc:IAI) -23 RG-urgn RG1->urgn intersection RG2--urgn FOR i 0 TO number of regions in RG1 DO FOR j 0 TO number of regions in RG2 DO inter_rgn rgli->rgn intersection rg2j->rgn IF inter_rgn is non-empty THEN IF rg 2 j is OPAQUE THEN new_p rgl->proxy

ELSE

create new proxy new_p initialised to IN of rgli-4proxy and rg2j--proxy inside interrgn.

END IF ADD to RG a new region with interrgn as its region description and new_p as its proxy. END IF END DO END DO Initialising the Entire Tree The entire compositing tree can be initialised by using the above-described method 20 of the preferred embodiment on every binary region group in the tree. A node cannot be initialised until its children have been initialised. Therefore the process simply starts at the bottom of the tree and works its way up towards the root. The process first checks to see if the current node is a leaf node. If this is the case, then a leaf node region group is constructed. However, in the case that the current node is a binary node then a binary node region group is constructed using the method of the preferred embodiment outlined in sections 2.4.1 and 2.4.2. The following pseudocode outlines a method for initialising all the region groups of the tree. The method utilises a recursive function, which is called passing the root of the tree as an argument.

tree_init(node tree ptr)

BEGIN

IFnode is a leaf node THEN CONSTRUCT leaf node region group

ELSE

tree init(node->left) 471440 I:1109551AU Opcj_scrn101 I :\E:LEC\CISR<A\OPE1-NSCRN\) SCRNIOI 1471440.doc:IAI) -24tree_init(node--right) CONSTRUCT binary node region group by combining region groups of the left and right children END IF END tree init 2.6 Constructing the Resultant Image Once the compositing tree has been initialised, the region group at the root of the tree contains a group of zero or more regions which together represent the partitioning of the resultant image into areas which differ in the way the image data was generated.

Some of the regions' proxies can refer to image data directly from leaf nodes of the tree, having not required any compositing. Other regions, on the other hand, may have proxies which are the result of compositing operations. If a single resultant image is required, such as an image stored in a pixel buffer, this can be achieved by copying the image data 15 from each region's proxy to the pixel buffer within the area corresponding to the region.

The process is demonstrated in the pseudocode provided below, which is generalised and able to restrict the construction of the final image to any nominated update region.

construct_image 20 output image pixel data ptr, urgn :region description

BEGIN

FOR i 0 TO number of region in RG DO intrgn rg->rgn intersection urgn IF int_rgn is non-empty THEN COPY image data from rg,--proxy to output_image inside int_rgn END IF END DO END construct_image Dynamic Rendering Dynamic Rendering refers to the problem of generating multiple successive images.

Given a compositing tree, it is possible to generate it's region groups (containing regions 471440 0C I1109F IAU Open_scrnl II:\-I.EC\CISRtA\OII[NSC'RM() SCtNO 1147 1440.doc: IAI) and proxies) using the method described above. A further embodiment of the above mentioned preferred method, which supports dynamic rendering is described below. The compositing tree represents an image. Changes to the tree can be made to make the tree represent a new image. The tree's region groups (and tree region description and proxies) are updated to reflect this modified tree. Performance is improved by exploiting commonality between the two images. An example will illustrate the techniques and terminology of the further embodiment.

Fig. 3 shows the region subdivision and the respective compositing expressions (advantage is not taken of opacity) for the simple compositing tree. Consider therefore the situation in which object A moves by a small amount relative to the other objects.

Some regions in the region group at the root of the tree will be affected by A moving.

If opaque case optimisations are ignored, the regions with compositing expressions which include A will be significantly affected by A moving. The region numbers which are so affected are 2, 3, 5 and 6. When updating the region group at the root of the tree, 15 those regions will need both their region descriptions and their proxies completely recalculated. This situation is known in the further embodiment as primary damage. Any region whose compositing equation includes an object which has changed in some way, may be said to suffer primary damage.

Regions that abut regions which have A in their compositing expression are also 20 effected by A moving, though not as severely as those regions with primary damage. In the example, these other affected regions are 1, 4, 7 and 8. When updating the region group at the root of the tree, these regions will need their region descriptions recalculated.

However, their proxies will only need to be recalculated in areas of the new region which were not included in the corresponding earlier region. This situation is known in the further embodiment as secondary damage. Generally, secondary damage is incurred if an object upon which a region's boundary (but not content) depends, changes in some way.

In order to reduce the per-frame update cost, it is important to reduce, as far as is practicable, the amount of work necessary, both in terms of per-pixel operations, but also in terms of region group operations. The concepts of primary and secondary damage are a way of facilitating this. If the preferred embodiment is able to accurately determine the minimum set of regions throughout all the compositing tree which have some kind of damage, then obviously the amount of work being done is reduced. The following sections describe how the reduction in work done is achieved.

3.1 Basic Data Model The data model used for static rendering, consisting as it does of a region 471440) CIT0951AUI~l Opoiscrn~01 7I41 '0 A:\C:I.CC\CISRA\O-'FNSCR SCRtNI 471440.doc:IAI) -26description and a proxy, is insufficient for use in dynamic rendering. This is because, for primary and secondary damage to be determined, it must be possible to associate regions of the same content between frames. To support the association of regions of the same content, some extra information is required in each region in a region group. Therefore, each region in a region group now contains the following data: A Region Description: A low-level representation of the boundaries of the region. The region descriptions of all the regions in a region group must be mutually exclusive (non-intersecting, non-overlapping).

(ii) A Proxy: Some means of caching the pixel data resulting from applying the operation specified by the compositing expression at every pixel inside the region description. A proxy can be as simple as a 24-bit colour bit-map, or something much more complicated (such as a run-length encoded description). Fundamentally, a proxy simply has to represent pixel data in some way which makes it efficient to retrieve and use.

15 iii) A Contents Label: A contents label represents a unique symbolic expression that describes the method of construction of image data. The terms in the symbolic expression distinguish between different categorisations of a source of image data. Therefore, the region groups of two distinct leaf nodes in the compositing tree will contain regions which are labelled with distinct contents labels even if their actual image 20 data is equivalent. The further embodiment uses a system of unique integers to represent contents labels. For example "23" could represent over B) over C".

(iv) A Flag Register: A general-purpose flag register used to store state during the region group update process. The exact flags stored here will be outlined in a later section.

3.2 Contents Labels Leaf node region groups can contain multiple regions, with each region naturally having a unique contents label. For example, the region group of a leaf node in a compositing tree could contain a single region (tagged with a single contents label) representing the non-transparent area of the leaf node. Alternatively, the leaf node region group could contain two regions (each tagged with a different contents label), one representing the area of the leaf node which is completely opaque, the other representing the remaining non-transparent area. A leaf node can also be categorised even further, into an arbitrary number of regions (and associated contents labels).

One way a contents label can be created is by assigning a new one to a region of a leaf node region group. Another way is taking other contents labels and combining them 471440 0:110951AI IIl Openjcrn0l II:\IILEC\CISRA\Ol'ENSC RN\(JSCRNN O11471440.dLc:IAD -27to create a new contents label that represents the symbolic expression that represents the combination of the contributing expressions. For example, if the contents label representing comp B) comp C) is combined with the contents label representing (D comp E) then a new contents label will be created which represents comp B) comp C) comp (D comp As well as contents labels, dependency information is also required. Dependency information indicates how a given contents label is related to other contents labels, both in terms of how the contents of one region contribute to contents of other regions, and how change of a region boundary affect the boundary of other regions. The further embodiment associates the following data with each contents label.

Primary Dependency List: Each primary dependency is a contents label L' to which a contents label L directly contributes. In other words, a "primary dependency" is a contents label L' representing an expression which has been constructed by combining L and some other contents label. Each time contents labels are combined, the contents label 15 for the combination is added to the primary dependencies of all contributors.

:i (ii) Secondary Dependency List: Each secondary dependency is a contents label L" which can be indirectly affected if the image represented by the contents label L has .changed in some way that affects it's boundary. Whenever contents labels are combined, a contributing contents label is added to the secondary steps of the continuation if and 20 only if the compositing operator yields a difference region with said contributing contents label. Table 2 shows which of some commonly used operators yield difference regions for their left and right operands. In addition, for a combination of (A comp the secondary dependencies of the combination contents labels for all (A comp bi) and all (ai comp B) are added, where aj are the secondary dependencies of A and bi are the secondary dependencies of B.

(iii) Property Information: Each contents label can represent contents which have properties which the compositing engine may be able to exploit. An example is that of opaqueness. If a contents label represents opaque content, then compositing that content could be much faster, as for certain operators, no per-pixel compositing operations would be required.

3.3 Contents Label Implementation The further embodiment uses unique integers as contents labels, and stores a number representing the number of contents labels which currently exist. When a new contents label is created, the number is incremented and becomes the unique integer representing the contents label. This technique of assigning a contents label by 471440 CAT0951A III Open-nscm~l SI :\['I-I-C\CISRA\1OI':NSCRN\O5CI(NO I 1471440.doc:AD -28monotonically incrementing an integer means that the contents labels' associated data structures can be stored in a one dimensional array which grows as more contents labels are added. A content label's data structure can be referenced simply by using the contents label as an index. When a leaf node contents label is created, the contents label is initialised to have no primary or secondary dependencies. If the current leaf node contents label is opaque, then a flag is set in content label i's properties.

The pseudocode below illustrates the basic techniques used to create a new contents label which is not dependent on other contents labels (ie: a leaf node region group contents label): Notation oa. a a a a a. a o *°oo* *Oo O o oo o oo oo oooo opaque curclab clabs clabs[i]->pri_deps clabs[i]->sec_deps clabs[i]->properties A flag passed to the function which indicates whether or not the contents label represents opaque content or not.

A global integer which stores the last contents label created.

A global array which stores the associated data structures of the contents label.

A pointer to the head of content label i's primary dependency list.

A pointer to the head of content label i's secondary dependency list.

A flag register representing contents label i's properties.

create new contents label opaque boolean RETURNS unsigned int

BEGIN

INCREMENT curclab.

clabs[cur_clab]-pri_deps

NULL.

clabs[cur_clab]-+sec_deps

NULL.

IF opaque THEN clabs[curclab]->properties

OPAQUE.

ELSE

clabs[cur_clab]-+properties 0.

END IF RETURN curclab.

471440 0C'110951 AU O penjcninll II:\[i:lEC\CISRA\OIINSCRN\O SCRN() 11471440.doc:AI) -29- END create new contents label.

Contents labels can also be created to represent the combination of existing contents labels. This is achieved in the further embodiment by a hash table which maps an S operation and the contents labels of its operands (hashed together to create a key) to a single contents label representing the result.

When a region is created which represents an intersection between two other regions (each with its own contents label), a new contents label is generated which is used to tag the new region. When this new contents label is generated, it must be added to the primary dependency lists of both its contributing operands. A secondary dependency list which depends on the secondary dependencies of the two contributing contents labels as well as the properties of the compositing operator must also be generated.

The process is recursive and begins by adding the newly created contents label (new_cl) to the primary dependency lists of the contributing contents labels. Then, 15 depending on the properties of the compositing operator, none, either or both of the contributing contents labels are added to the secondary dependency list. Then every contents label representing (clabl op sd2i) and (sdli op tab2) are added to the secondary S" dependency list.

Notation S""clabi The first contributing contents label.

clab2 The second contributing contents label.

sdli The i'th element of clabl's secondary dependency list.

sd2i The i'th element ofclab2's secondary dependency list.

create_binarycontentslabel clab contents label, clab2 contents label, clab2 contents label, op: compositing operator

BEGIN

IF the hash table already contains an entry representing clabl op clab2

THEN

RETURN the existing contents label representing the combination.

471440 C1110951A U ll(penjcninli II:\ILEC\CISRA\'0WENSCRN\(SCRN) 011471440.doc:IAD 30 END IF Generate a new entry in the hash table representing clabl op clab2, mapping to new_cl.

(Add the new contents label to the primary dependency lists of the contributing contents labels if the compositing op requires it) add_to_primary_dep_list(clab1, new_cl) add_to_primary_dep_list(clab2, new_cl) (Generate the secondary dependencies) IF op generates left diff rgns THEN add clabl to secondary deps END IF IF op generates right diff rgns THEN 5 add clab2 to secondary deps END IF FOR i 0 TO number of elements in sdl DO add_tosecondary_dep_list 20 new_cl, create_binarycontents_label(sd1i, clab2) END DO FOR i 0 TO number of elements in sd2 DO addtosecondary_dep_list new_cl, create_binary_contents_label(clab1, sd 2 j) END DO END constuct_binary_contents_label 3.4 Combining Region Groups for Dynamic Rendering Before any incremental updates can be made to a compositing tree, the com- 4714401 C1.110951AU OpencnscnIM II:\IILEC\CISRkA\0I'I[NSCRtN\()SCIN)I 1471440.doc:IAI) -31 positing tree must be constructed to be in a consistent initial state. The basic technique for achieving this is the same as that used for static rendering, except that support for contents labels is included.

Leaf node region groups are initialised essentially as with the static rendering case, except that each region in each leaf node region group is tagged with a unique contents label. Each contents label can in turn be tagged with various categorisation properties which may help the renderer to be more efficient. For example, a contents label can be tagged as being completely opaque.

The initialisation of binary nodes is also similar to the static rendering case. By way of example, the way in which the region group for an "OVER" binary node is constructed will now be explained. The techniques for constructing the region groups of the other compositing operators can easily be inferred from the "OVER" case.

When a difference region between rgi of one operand and the coverage region of the other operand is calculated, the difference region inherits the contents label rgi. When an intersection region is created, on the other hand, a new contents label is created by combining the contents labels of the two contributing regions since the two contributing regions had their proxies composited into a new proxy which means new content. The pseudocode for constructing an "OVER" region group which includes contents label management is provided below: Notation

°O

o* 0

S

55o5*

S

o

S

RG1 RG2

RG

RGl->urgn RG l--urgn RG--urgn rgli rg2j rg I i--rgn rg2j->rgn rgl i--proxy The region group of the binary node's left child The region group of the binary node's right child The region group of the binary node. It is this region group that we are initialising The region description representing the union of all RGl's region descriptions (RGl's coverage region).

The region description representing the union of all RG2's region descriptions (RG2's coverage region).

The union of all RG's region descriptions.

The current region in RGI The current region in RG2 rgli's region description rg2j's region description rgl i's proxy 471440) CH10951AU~I Open_scril01 [1:\[:LEC\CIS(A\OI'ENSC RN\()SCRN(O I 1471 440.doc:IAl) -32rg2j->proxy rg2j's proxy RG->urgn RG1->urgn union RG2->urgn FOR i 0 TO number of regions in RG1 DO diffrgn rgli->rgn difference RG2->urgn IF diff_rgn is non-empty THEN ADD to RG a new region with diff_rgn as its region description, rg 1i-proxy as its proxy and rgli->clab as its contents label.

END IF 10 FOR j 0 TO number of regions in RG2 DO interrgn rgli->rgn intersection rg2j->rgn IF interrgn is non-empty THEN newclab GENERATE a new unique contents label as a result of combining rgli->clab and rg2j->clab.

15 IF rgli->clab is OPAQUE THEN .e new_p rgli->proxy

ELSE

create new proxy new_p initialised to OVER of rg1 l->proxy and rg2j->proxy inside inter_rgn.

END IF ADD to RG a new region with interrgn as its region description, newp as its proxy and new_clab as its contents label.

END IF END DO END DO FOR j 0 TO number of regions in RG2 DO diffrgn rg2j->rgn difference RG1->urgn IF diffrgn is non-empty THEN ADD to RG a new region with diff_rgn as its region description, rg2j-proxy as its proxy and rg2j->clab as its contents label.

END IF END DO 4(71440l CIT0951AUIAI Opoijernr1 1l lI:\EI-1 C\CISIA\OPEl-NSCIr'\() SCRtNO I 47 I44(0.doc:IAD) Secondary Dependencies and Over The rationale behind the preferred method used for generating secondary dependencies requires more explanation. Secondary dependencies are only generated when a new contents label is created by combining two other contents labels. As can be seen in the above pseudocode, this only occurs when an intersection region is generated.

Essentially, the further embodiment uses contents labels generated for intersection regions as triggers the regions tagged with two contents labels cannot indirectly affect one another unless they intersect. The secondary dependency list for a particular contents label is dependent on the compositing operator the composite contents label represents, the two contributing contents labels and their secondary dependency lists.

The method of the further embodiment of generating a secondary dependency list for a new contents label which represents one contents label composited over another contents label using the "OVER" operator will now be explained. Elements of A's and B's secondary dependency lists are referred to as Ai and Bi respectively. First, both 15 A and B are added to C's secondary dependency list. This is because if the region tagged with C changes its boundary, then it is likely that any regions tagged with A and B will need to be recalculated (because their regions are likely to abut C's region), Next, for each element of B's secondary dependency list, each contents labels representing (A OVER Bi) is added. A mapping representing A OVER Bi may not currently exist in the 20 system and needs to be created. A secondary dependency list can contain contents labels which are not represented by any region in a region group. They could come into existance by changes in region boundaries. The rationale is that A intersects B, and therefore it is likely that A also intersects regions tagged with contents labels which exist in B's secondary dependency list. Similarly, for each element of A's secondary dependency list, each contents label representing (Ai OVER B) is added.

3.6 Contents Labels and Damage The concepts of primary and secondary damage were introduced with reference to Fig. 3 to demonstrate that it is not always necessary to regenerate an entire image as a result of a change to the compositing tree. By keeping track of dependencies between regions of different content, it only becomes necessary to regenerate image data in regions whose contents have become damaged. The following explanation outlines the dependencies and damage for simple compositing tree changes. "Simple" means that only leaf nodes are modified. More complex change scenarios such as tree structure changes etc will be outlined in later sections.

If a leaf node is modified, the contents labels of its affected regions are said to be 471440 CI:1l0951 AI1 Openjuncml lI:\[-I.I-C\CISRA\I'NsSCRN\()SC N) 11471440.doc:IAI) -34- "primary damaged". Primary-damaging a contents label involves recursively primarydamaging all its primary dependencies. Whenever a contents label is primary-damaged, all its secondary dependencies are non-recursively marked with secondary damage. The process begins by flagging the contents label to be damaged. The following pseudocode demonstrates how contents labels can be damaged: Notation clab The contents label to be damaged pdi The i'th element of clab's primary dependency list.

sdi The i'th element of clab's secondary dependency list.

damagecontents label 10 clab contents label,

BEGIN

FLAG clab with PRIMARY damage 15 FOR i 0 TO number of elements in sd DO FLAG sdi with SECONDARY damage END DO FOR i 0 TO number of elements in pd DO damage_contents_label(pdi) END DO END damage_contents_label When a tree update occurs, any region with its contents label marked as having primary damage will need to recalculate both its region boundaries and its proxy. Any region with its contents label marked as having secondary damage will need to recalculate its region description but will only need to recalculate its proxy in areas of the new region that were not included in the earlier region.

3.7 Examples of Contents Labels and Dependencies In order to clarify the concepts of contents labels and damage, some examples of 471440) CH10951AH opoi)pcnscrn~l I\II MilEC\CISRtA\0I'ENSCR[N\(SCIRN( 1471440.doc:IAI) varying complexity will be presented.

3.7.1 Example 1 Fig. 9 will result in the following contents label table after the compositing tree is initially constructed (Note: in the following table contents labels are represented as unique strings not as integers where "over" has been abbreviated to This is simply for readability.): Contents Label Primary Deps. Secondary Deps.

A AoB B AoB AoB A, B If A moves, then AoB will have primary damage, resulting in B having secondary 10 damage.

3.7.2 Example 2 Fig. 10 will result in the following contents label table after the compositing tree is initially constructed: .oo*e .o Contents Label Primary Deps. Secondary Deps.

A AoB, AoC B AoB, BoC AoB AoBoC A, B C AoC, BoC, (AoB)oC AoC A,C BoC B, C (AoB)oC AoB, C, AoC, BoC In this example, every object intersects every other object, so if something changes, everything will be damaged in some way everything which is a primary dependency of the changed object will have primary damage, whereas everything else will have secondary damage.

Fig. 11 illustrates the effect of A moving in a subsequent frame. As can be seen, if A is damaged, the regions defined by A, AoB, AoC and (AoB)oC will each have primary damage. The regions defined by B, C and BoC will each have secondary damage.

3.7.3 Example 3 Fig. 12 will result in the following contents label table after the compositing tree is initially constructed: 471440 CTPO() IAU OpcnSCn1O1 I I:\IEliC\CISRA\01'LNSCRtN\()SCRN( I 1471440.doc:[AI) 36 Contents Label Primary Deps. Secondary Deps.

A AoB, AoC, AoE, Ao(DoE), AoD B AoB,BoC,BoE AoB AoBoE A, B D DoE, AoD, CoD, (AoC~oD E DoE, AoE, (AoB)oE, BoE, CoE, (BoC~oE, (AoC~oE DoE Ao(DoE), (AoC~o(DoE), D, E Co(DoE) C AoC, BoC, Co(DoE), CoE, CoD AoC AoCoE, (AoC~o(DoE), A, C BoC (BoC)oE B, C AoE (AoB)oE E,AoE, BoE BoE B, E CoE C,E (BoC~oE BoC, E, BoE, CoE AoD A,D CoD C,D (AoC~oE AoC,EP.AoP, CoE Ao(DoE) A, DoE, AoD, AoE Co(DoE) C, DoE, CoD, CoP (AoC~o(DoE) AoC, DoE, Ao(DoE), Co(DoE), (AoC~oD, ___(AoC~oE (AoC~oD D, AoD, CoD Since A intersects every other object, if A moves, a large amount of the comnpositing tree wil need to be recomputed. Fig. 13 shows that the only part left alone is the area corresponding to BoC and its dependent BoCoE. To summarise: *Primary Damage A, AoB, AoC, AoE, Ao(DoE), (AoB)oE, (AoC)oE, (AoC~o(DoE), AoD, (AoC~oD *Secondary Damage B, C, E, DoE, BoE, CoE, DoE, CoDoE On the other hand, if B mi-oves, the amount of damage is less than if A moved. This is because B doesn't intersect D. DoE, Ao(DoE), (AoC~o(DoE), Co(DoE) and (AoC~oE (and their ancestors) are not damnaged when B moves. This is shown in Fig. 14. The rest of the damage is summ-arised as: ePrimnary Damage B, AoB, BoC, BoE, (AoB)oE, (BoC)oE *Secondary Damage A, E, C, AoE, CoE 471440 CIT0951AU Openjun0l 47 I44( ('I'OS IAll( (eilsenl) :\IELE[C\CISRA\0I'I:NSCRIN\O SCR 471 440.doc:IAI) -37r r The examples presented so far are simple, but they are sufficient to demonstrate that the dependencies techniques presented so far will damage those contents labels which are affected when a particular contents label/s is(are) damaged. In a typical complex composite, it is rare for large numbers of objects to intersect a large number of other objects, meaning that large areas of the compositing tree should be untouched during updates using the above technique.

3.8 Example of Secondary Dependencies and Compositing Operators Consider a modified version of Example 3 above. Fig. 18 will result in the following contents label table after the compositing tree is initially constructed. Note that AaB represents A ATOP B and AiB represents A IN B etc: Contents Label Primary Deps Secondary Deps A AaB B AaB, BoC AaB B C BoC, Co(DiE) BoC B, C D DiE E DiE DiE Co(DiE) Co(DiE) C, DiE As seen in Fig. 18, the ATOP operator clips A to B's bounds, meaning that intersections between A and any of C, D or E never occur. Similar things occur with the IN operator. This means that the objects in this scene are less tightly coupled. For example, if A is changed, then only B and AaB are immediately damaged. Similarly, if E is damaged, it is only possible for DiE to be damaged.

3.9 Updating Region Groups The further embodiment uses the contents label and damage framework to reduce the amount of work that has to be done to make a binary region group consistent with its updated operands during an update. The further embodiment does this by only updating those regions in a region group whose contents labels have primary or secondary damage, adding any new region which comes into existence as a result of the changes made to the compositing tree, and deleting any region in the right group whose contact no longer exists.

Each different binary operator has a different updating function which deals with the specific requirement of that operator. The process of updating region groups is a two- 4(71440) CHI:I'MAIJ opel~n_scriffll II :\LL[-1CC\CISRA\01'NSCRNN\()SCRN( I 1471440.doc:IAI) -38pass process. The first pass updates any intersection regions that have been primary damaged and adds any new intersection regions generated due to the damage. Each region of one operand's region group is intersected with each region of the other operand's region group whenever one or both of their corresponding contents labels are primary damaged. If the intersection is non-empty, then the further embodiment determines if a contents label representing the combination exists. If the contents label doesn't exist, one is created and primary damaged. Note that primary damaging a contents label will mark all it's secondary dependencies with secondary damage.

If a region in the region group is currently tagged with the primary damage contents label, the regions boundary and proxy are updated. If no such region exists in this region o* group. then a new region keyed by this contents label is added to the region group. A new proxy is generated and assigned to this region along with the right description relating from the intersection operation.

A difference between each region group of one operand and the coverage region of 15 the other operand is calculated whenever the regions contents label has primary or secondary damage. If the difference is non-empty and a region tagged with the contents label exists in the region group, then it's region description and proxy reference are updated. If such a region doesn't exist then a region keyed by the contents label is added to the region group. The added region is assigned as a coverage region of the difference 20 result and references the proxy of current region.

Each region of one operand's region group is interacted with each region of the other operand's region group whenever the contents label representing their combination has secondary damage and no primary damage. If the intersection is non-empty, the region group is searched looking for a region keyed by the contents label. If such a region exists its region description is updated and it's proxy is updated as the difference between the new and old regions. If such a region doesn't exist, then a region keyed by the contents label is created. The created region description is assigned the result of the interaction operation and it's proxy generated.

Pseudocode which illustrates a simple algorithm for updating a binary "OVER" region group is provided below.

Notation RGI The region group of the binary node's left child RG2 The region group of the binary node's right child RG The region group of the binary node. It is this region group 471440 C:1109 IAH (pcn_scrn01 -4)I Ii sc I:\l1I .1-C\CISIRA\01'1ENSCRN\( 147 440.doc:IAl) -39- RG I -urgn RG 1 ->urgn RG--urgn rgli rg2j rg I i-rgn rg2j->rgn rg i--proxy rg2j->proxy rgli->clab rg2j-+clab that is being initialised.

The region description representing the union of all RGl's region descriptions (RGl's coverage region).

The region description representing the union of all RG2's region descriptions (RG2's coverage region).

The union of all RG's region descriptions.

The current region in RG1 The current region in RG2 rgli's region description rg2j's region description rg i's proxy rg2j's proxy rg li's contents label rg2j's contents label r RG->urgn RG1->urgn union RG2->urgn (First Pass this pass is used to deal with primary damage of intersection regions and any new intersection regions generated) FOR i 0 TO number of regions in RG1 DO FOR j 0 TO number of regions in RG2 DO IF rgli->clab has PRIMARY damage OR rg2j-clab has PRIMARY DAMAGE THEN interrgn rgli-+rgn intersection rg2j->rgn IF interrgn is non-empty THEN comp_clab SEARCH for an existing contents label which represents (rgli->clab comp rg2j->clab).

IF a region tagged with comp_clab already exists in RG

THEN

IF rgli-->clab is OPAQUE THEN new_p rgli-*proxy

ELSE

create new proxy new_p initialised to OVER of rg 1 i-proxy and rg2j-proxy inside interrgn.

471440 0C:1109'51AH 0 (pcn_scrn01 47 I441CI\I5LF\ClSRAOINSCRO SCR(I 1 1471 44II.doc:AI END IF MODIFY the existing region to have interrgn as its region description and new_p as its proxy.

ELSE

new_clab create_binary_contents_label(rg 1i-clab, rg2j->clab).

IF rgli->clab is OPAQUE THEN new_p rg li-proxy

ELSE

create new proxy new_p initialised to OVER of rgli->proxy and rg2j->proxy inside inter_rgn.

END IF Sdamage_contents_label(new_clab) ADD to RG a new region with inter_rgn as its region 15 description, new_p as its proxy and new_clab as its contents label. END IF FLAG the region as being 'RETAIN AFTER UPDATE' END IF END IF 20 END DO END DO (Second Pass this pass is used to deal with primary and secondary damage of difference regions and secondary damage of intersection regions) FOR i 0 TO number of regions in RG1 DO IF rgli->clab has PRIMARY or SECONDARY damage THEN diff rgn rgli-+rgn difference RG2->urgn IF diffrgn is non-empty THEN IF a region tagged with rgli->clab already exists in RG THEN MODIFY it to have diff_rgn as its region description and rg1i->proxy as its proxy.

ELSE

ADD to RG a new region with diff_rgn as its region description, rgli->proxy as its proxy and rg1r->clab as its contents label. END IF 471440 C:110951AU~ Open_scrn0l II:\I:LEC\CISRA\0I'INSCI(N\() SCRN( I 1471 440.doc:IAI) -41 FLAG the region as being 'RETAIN AFTER UPDATE' END IF END IF FOR j 0 TO number of regions in RG2 DO comp_clab SEARCH for an existing contents label which represents (rg1i-*clab comp rg2j-+clab).

IF comp_clab exists AND comp_clab has SECONDARY damage but NO PRIMARY damage THEN inter_rgn rgli->rgn intersection rg2j->rgn IF inter_rgn is non-empty THEN GET a reference to the existing region tagged in this region group with comp_clab which MUST exist in this region group IF rgli-+clab is OPAQUE THEN existing regions proxy =rgl -+proxy 15 ELSE update rgn inter rgn difference the region's previous region description.

update existing regions proxy to include OVER of rgli->proxy and rg 2 j proxy inside update region.

20 END IF MODIFY the existing region to have inter_rgn as its region description and new_p as its proxy.

FLAG the region as being 'RETAIN AFTER UPDATE' END IF END IF END DO END DO FOR j= 0 TO number of regions in RG2 DO IF rg2j-clab has PRIMARY or SECONDARY damage THEN diff_rgn rg2j->rgn difference RG1-+urgn IF diff_rgn is non-empty THEN IF a region tagged with rg2j->clab already exists in RG THEN MODIFY it to have diff_rgn as its region description and rg2j-*proxy as its proxy.

4714401 C11,0951AH OI (pcii_scml II:\E.LE:''C\CISRA\O1'lNSCI(N\( SCRN) I 471440.doc:iAI) -42

ELSE

ADD to RG a new region with diffrgn as its region description, rg2j->proxy as its proxy and rg2j-clab as its contents label.

IF

FLAG the region as being 'RETAIN AFTER UPDATE' END IF END IF END DO DELETE all regions of RG which are not marked RETAIN AFTER UPDATE but whose contents labels have damage, and CLEAR flag in retained regions.

4.0 Tree Modifications (Linking and Unlinking) S 15 More complex changes to a compositing tree can be achieved by changing the tree's structure. Most typical tree structure changes can be made by using two low level Soperations, link and unlink.

The unlink operation is used to separate a child node from its parent. After the operation is completed, the child node has no parent (meaning the child node can be Gov.

20 linked in somewhere else), and the parent has a link available (meaning that some other node can be linked there instead). Nodes in the compositing tree above the unlinked child contain content which is dependent on the unlinked child. Therefore, at the time of the next update, the contents label present in the unlinked child at the time of unlinking must be damaged to ensure that the dependent region groups higher in the tree are appropriately updated. The updating is achieved by the parent node caching away those contents label existing in its unlinked child. If another subtree is linked in its place and subsequently unlinked without the region group of the parent being updated, it is not necessary to cache the contents labels of this new subtree. Pseudocode for the unlink operation is provided below. Note that the UNLINKED_LEFT or UNLINKED_RIGHT flag is set so that the contents labels of a newly linked subtree may be damaged when region groups (including their proxies) higher in the tree must then be updated.

unlink node compositing tree node node compositing tree node 471440) CI:11095IAIJ Openjcni01 47II44()C A I: \LI0C\IS RA\0I'1ENSCRI 1471440.duc:IAI) 43

BEGIN

parent node parent.

node ->parent NULL.

IF node is parent's left child THEN parent left NULL.

IF parent doesn't have UNLINKED_LEFT set THEN SET the UNLINKED_LEFT flag in parent.

ELSE.

RETURN.

END IF ELSE IF node is parent's right child THEN parent -+right NULL.

IF parent doesn't have UNLINKED_RIGHT set THEN SET the UNLINKED_RIGHT flat in parent.

ELSE

RETURN

END IF END IF COPY all the contents labels in node's region group into an array stored in parent ->unlinked_clabs.

END unlink The link operation involves linking a node with no parent to a free link of a parent node. Pseudocode for the operation is provided below: link child compositing tree node, parent compositing tree node, which link either LEFT or RIGHT

BEGIN

child ->parent parent IF which link is LEFT THEN 471440 CIT09'O)SI AU Opciijcm101 II:\I3LEC\CIS RA\O[IENSCRN\()SCRN0 I j471440.doc:IA -44parent ->left child.

ELSE

parent right child.

END IF END LINK 4.1 Updating the Entire Compositing Tree If a leaf node in the compositing tree changes, the region group of every node in a direct line from the leaf node to the root of tree must be updated using the methods described above. Fig. 15 shows circled those nodes which need to have their region groups updated if leaf nodes B and H change in some way.

SPseudocode for the tree updating method is provided below: update tree node compositing tree node

BEGIN

IF node is leaf node THEN o Rerender the leaf node and update its region group.

ELSE

IF unlinking occurred in left subtree or left subtree contains dirty leaf nodes THEN update_tree(node left).

END IF.

IF unlinking occurred in right subtree or right subtree contains dirty leaf nodes THEN update_tree(node -*right).

END IF.

IF node has UNLINKED_LEFT or UNLINKED_RIGHT flags set THEN CALL damage_contents_label on every element of node-4unlinked_clabs.

IF node has UNLINKED LEFT set THEN CALL damage_contents_label on every contents label existing in node--left's region group.

471440 CFP0951IAU Openjcni0l [I:\ELEC\CISRA\OPENSCRN\O_SCRNO1]471440.doc:IAD CLEAR the UNLINKED_LEFT flag in node.

END IF IF node has UNLINKEDRIGHT set THEN CALL damage_contents_label on every contents label existing in node-right's region group.

CLEAR the UNLINKED_RIGHT flag in node.

END IF END IF CALL the region group update routine appropriate for node's compositing operator.

-END

IF

S END updatetree The embodiments of the invention can be implemented using a conventional general-purpose computer system 2100, such as that shown in Fig. 19, wherein the process described with reference to Fig. 1 to Fig. 18 are implemented as software recorded on a computer readable medium that can be loaded into and carried out by the computer. The computer system 2100 includes a computer module 2101, input devices 2102, 2103 and a display device 2104.

o With reference to Fig 19, the computer module 2101 includes at least one processor unit 2105, a memory unit 2106 which typically includes random access memory (RAM) and read only memory (ROM), input/output interfaces including a video interface 2107, keyboard 2118 and mouse 2120 interface 2108 and an I/O interface 2110. The storage device 2109 can include one or more of the following devices: a floppy disk, a hard disk drive, a CD-ROM drive or similar a non-volatile storage device known to those skilled in the art. The components 2105 to 2110 of the computer module 2101, typically communicate via an interconnected bus 2114 and in a manner which results in a usual mode of operation of the computer system 2100 known to those in the relevant art.

Examples of computer systems on which the embodiments can be practised include IBM- PC/ ATs and compatibles, Sun Sparcstations or alike computer system. In particular, the pseudocode described herein can be programmed into any appropriate language and stored for example on the HDD and executed in the RAM 2106 under control of the processor 2105 with the results being stored in RAM within the video interface 2107 and reproduced on the display 2116. The programs may be supplied to the system 2100 on a pre-programmed floppy disk or CD-ROM or accessed via a connection with a computer 471440 CF11095AU Openjcrti0l I :\ELEC\CISRA\OI'ENSCIRN\OSCRNO I ]471440.doc:IAD -46network, such as the Internet.

The aforementioned preferred method(s) comprise a particular control flow. There are many other variants of the preferred method(s) which use different control flows without departing the spirit or scope of the invention. Furthermore one or more of the steps of the preferred method(s) may be performed in parallel rather sequential.

The foregoing describes only several embodimens of the present invention, and modifications, obvious to those skilled in the art, can be made thereto without departing from the scope of the present invention.

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

471440 C1-P0951AU Openjcni1 [I:\ELEC\CISRA\OPENSCRN\O_SCRN1 ]471440.doc:IAD -47region.cpp The implemention of the region manipulation functionality in the Screen OpenPage prototype.

#include "protos.h" static static static static static static int uniontot 0; int int_tot 0; int diff_tot 0; int union full 0; int int full 0; int diff full 0; Some #defs which are used to control builder implementation..

#define R USE NEW IMP #define RB FAST SHIFT AND DUP LOOPS #define RB USE LOOKUP #define R NEW IMP CONSTRUCTION LOOP the optimisations used in the region *o r The global variables used to store the temporary results needed during region manipulation operations. Two statically allocated R_RegionBuilder structures are used. This is to allow data to be read from one of them whilst the data required for the next operation is written into the other one. Two pointers rPrevRB and R CurRB are used to swap access to the two static structures. The r_grow_region_builder function is called to grow a R_RegionBuilder structure if required.

static RRegionBuilder static R_RegionBuilder static R_RegionBuilder R_RegionBuilder r_RB1 0, NULL, NULL}; r_RB2 0, NULL, NULL}; *r PrevRB &r RBl; *RCurRB &r RB2; r_shift_and_dup A 16-byte lookup table which when provided with an unsigned char of the following form xxyy, simply produces xxxx. This lookup table _assumes_ that RSTATESIZE is 2. It won't work (and will die horribly) if this isn't the case.

unsigned char rshift_anddup16] 0x00, 0x05, OxOA, OxOF, 0x00, 0x05, OxOA, OxOF, 0x00, 0x05, OxOA, OxOF, 0x00, 0x05, Ox0A, OxOF A buffer is required to store the new region data whilst a region is being constructed. This buffer is expanded when required.

static RInt static int *rRgnBuf NULL; rRgnBufSize 0; A buffer of IntXYMinMax structures is required to store the rectangles generated during R_rects_from_region. This buffer is expanded when required.

static IntXYMinMax *r_RectBuf NULL; I:\ELEC\CISRA\OPENSCRN\O_SCRN02\appendix I.doc -48static int r RectBufSize 0; R FREE LIST GROWTH SIZE This macro defines the number of elements which will be added to free list whenever it is grown.

#define R FREE LIST GROWTH SIZE 100 r free list A linked list of unused R_RgnGrowItems which may be used during region construction.

R_RgnGrowItem *r free list NULL; r_growthlist A linked list of RRgnGrowItems which represents the current state during region construction.

RRgnGrowItem *r_growth_list NULL; r_grow_region_builder This function simply checks to see if a R RegionBuilder structure is of the required size. If it isn't the size of both arrays in the RRegionBuilder structure are doubled.

Parameters: rb The region builder to be grown.

size The required size of the arrays in the R_RegionBuilder.

Returns: TRUE on success, FALSE on failure.

static int r_grow_region_builder R_RegionBuilder *rb, R_Int size unsigned char *new state data; R_Int *new_rgn data; int new size; new_size max(size, rb->rrb Size 2); newstate data (unsigned char *)malloc(new_size sizeof(unsigned char)); if (new state data NULL) return FALSE; new_rgn_data (RInt *)malloc(new_size sizeof(R Int)); if (newrgn_data NULL) free(new_state_data); return FALSE; if (rb->rrbStateData NULL) memcpy newstate data, rb->rrbStateData, rb->rrb_Size sizeof(unsigned char) free(rb->rrbStateData); I:\ELEC\CISRA\OPENSCRN\O_SCRNQ2\appendixl .doc -49if (rb->rrb_RgnData NULL) memcpy new_rgn_data, rb->rrb_RgnData, rb->rrb Size sizeof(R Int) free(rb->rrb RgnData); rb->rrb_StateData newstatedata; rb->rrb_RgnData new_rgn_data; rb->rrb_Size new size; return TRUE; r_swap_region_builders This function simply swaps the static pointers to the r RB1 and r RB2 region builders.

Parameters: None.

Returns: Nothing.

inline static void r_swap_regionbuilders() R_RegionBuilder *tmp; tmp R_CurRB; R_CurRB rPrevRB; r_PrevRB tmp;

I

Radd_row_to_region_builder This function adds a row from a RRegion to a RRegionBuilder structure.

The region from which the row comes is passed as an argument. "Adding" has the following conditions...

If a pixel run in the row does not exist in the region builder it is added and it's current state is tagged with the region to which the row belongs. The previous state is set to 0, indicating that it did not exist before.

If a pixel run in the row did exist before, but it's present state indicates that it came from the other region then the run is retained but it's state is modified to indicate that both regions are active at this point.

If a pixel run in the row did exist before, and it's present state indicates that the current region then the region is removed and it's state is modified to indicate that the run is now empty.

If a pixel run in the row did exist before, and it's present state indicates that both regions are currently active then the run is retained, but its state is modified to indicate that only the other region is active in this run.

Parameters: row_ptr A R_Int pointer to the row in the region. Used to return the updates row pointer.

rgnmask A mask for the region the row comes from. Must be either 1 or 2.

first Whether this is the first region to be processed on the current scanline.

Returns: l:\ELEC\CISRA\OPENSCRN\OSCRN02\appendix .doc TRUE on success, FALSE on failure.

#if 1 int R_add_row_to_region_builder R_Int **row_ptr, int rgn_mask, int first R_Int *row; int srcindex; int dest_index; R_Int rb-run start; unsigned char rb_prevrunstate; int row_on; ASSERT(rgn_mask 1 rgn_mask 2); row *row_ptr; r_swap_region_builders(); Skip over the row's y value at the beginning.

ASSERT(*row R NEXT IS Y); o. row 2; S. .ASSERT(*row R_NEXTISY *row REOR); if (r PrevRB->rrbNels 0) If the current region builder's src region data array is empty, then we are dealing with an empty region builder. We simply convert the input row to the region builder format.

row on TRUE; destindex 0; while (RNOTEND OF ROW(*row)) if (++dest index R CurRB->rrb Size) if (!r_grow_region_builder(R_CurRB, dest_index)) return FALSE; R_CurRB->rrb_RgnData[dest_index 1] *row; if (row_on) R_CurRB->rrbStateData[dest index 1] (rgn_mask RB STATESIZE); else R_CurRB->rrb_StateData[dest_index 1] 0; row on !rowon; row++; *rowptr row; R_CurRB->rrbNels destindex; return TRUE; Firstly, we copy any runs from the region builder which precede this run from the region. We are checking the starting row against the start of each pixel run. Therefore we start checking against the Ind region builder data element.

ASSERT(r_PrevRB->rrb_Nels 2); src index 0; while (srcindex r_PrevRB->rrb_Nels *row r_PrevRB->rrbRgnData[src_index]) I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendix .doc -51 src-index++; dest -index src index; if (src_index 0) if (src-index RCurRB->rrbSize) if (Ir-grow region builder(RCurRB, src-index)) return FALSE; memcpy RCurRB- >rrbRgnData, r_-PrevRB- >rrb-RgnData, src_index sizeof(RInt) if (!first) memcpy 2_CurRB->rrb -StateData, rPrevRB->rrbStateData, src-index sizeof (unsigned char) else mnt 1 =0; unsigned char *src; unsigned char *dest; *src =rPrevRB->rrb_-StateData src -index; dest R RCurRB->rrb_-StateData src-index; switch (src_ index) default: for (i src index; i 10; #ifndef RBUSELOOKUP *(dest i) (*(src i) RBCURSTATEMASK) (*(src i) RBSTATESIZE); ese*(dest i) r-shift-and-dup[*(src H itendif

FALLTHROUGHI!

case ftifndef RBUSELOOKUP *(dest 10) (*(src 10) RB_-CUR_-STATEMASK) (*(src 10) RBSTATESIZE); #else *(dest 10) r-shif t and-dup (src i#endif

FALLTHROUGH!!

case 9: #ifndef RBUSELOOKUP *(dest 9) (*(src 9) RBCURSTATE MASK) (*(src 9) >>RBSTATESIZE); f4else *(dest 9) r-shift and dup[*(src #endif FALLTI4ROUGH!! case 8: #ifndef RBUSELOOKUP *(dest 8) (*(src 8) RB_-CUR_-STATEMASK) (*(src 8) RBSTATESIZE); #4else *(dest 8) r-shift-and-dup[*(src )*endif 1 LEC\CISRA\OPENSCRN'\OSCRNO2\appendix I .doc 52 FALLTHROUGHI! case 7: #ifndef RBUSELOCKUP #else #endif #ifndef #else )tendif #ifndef #else 4endif #tif ndef #else #endif #if ndef #else )#endif #fif ndef #else #endif 4ifndef #telse #endif (dest 7) "*(dest 7)

FALLT-ROUGH!

case 6: R USE LOCKUP *(dest 6) *(dest 6)

FALLT-ROUGH!

case

RBUSELOCKUP

*(dest 5) *(dest 5)

FALLT-ROUGH!

case 4: RB USE LOCKUP *(dest 4) *(dest 4)

FALLTHROUGH!

case 3: RB USE LOCKUP *(dest 3) *(dest 3)

FALLTHROUGH!

case 2: RB USE LOCKUP *(dest 2) *(dest 2) 1* FALLTI4ROUGH! case 1:

RBUSELOCKUP

*(dest 1) *(dest 1)

FALLTHROUGH!

case 0: FALLTHROUGj! ((src 7) RB_-CUR_-STATE-MASK) ((src 7) RB_STATE_SIZE); r-shift and dup[*(src 7)] ((src 6) RBCUR_-STATE -MASK) ((src 6) RBSTATE_SIZE); r-shi f tand dup(*(s rc 6)] ((src 5) RBCURSTATE MASK) ((src 5) RBSTATE_SIZE); r-shi f tand dup[*(s rc ((src 4) RBCURSTATE MASK) ((src: 4) RBSTATE_SIZE); r-shi f tand dup[*(s rc 4)] ((src 3) RBCURSTATEMASK) ((src 3) RBSTATE_SIZE); r-shif t and-dup (src 3)] ((src 2) RB_-CURSTATE MASK) (*(src 2) RBSTATESIZE); r-shif t and-dup (*(src ((src 1) RB_-CURSTATE MASK) 1) RBSTATE_SIZE); r-shi f tand-dup[*(s rc 1] if (src-index rPrevRB->rrbNels) We've already exhausted the previous region builder. Set the start of the next pixel run to be the max. possible and set the state I:\ELEC\CI SRA\OPENSCRN\C_SCRNO2\appendixl .doc -53to be 0.

rb_run_start R INTMAXVALUE 2; rb_prev_run_state 0; else We are still within the previous region builder bounds. Set up the run info appropriately.

rbrunstart r_PrevRB->rrb_RgnData[src_index]; if (src_index 0) rb_prev_run_state 0; else rbprevrunstate rPrevRB->rrbStateData[src index 1]; We can now start dealing with the elements in the row.

row on 1; while (R NOT END OF ROW(*row)) if (*row rb run start) if (destindex 1 RCurRB->rrbSize) if (!r_grow_regionbuilder(RCurRB, destindex 1)) return FALSE; R_CurRB->rrb_RgnData[dest_index] *row; if (first) We are processing the first region. Therefore, we copy the current state of the run to the lowest RB STATE SIZE bits.

R_CurRB->rrbStateData[destindex] (rb_prev_run_state RB_CUR STATE MASK) (rbprevrun_state

RBSTATESIZE);

else We are processing the second region. Therefore, the state data has already been copied to the previous state area so we just copy the state.

RCurRB->rrb_StateData[destindex] rb_prev run state; Now, if the row for the current region is active at this transition, we xor the region mask with the current contents of the new region builder slot. This gives the desired behaviour of making that region active if it is not there already, but turns it off if it is...

if (row_on) R_CurRB->rrb_StateData[dest_index] (rgnmask RB STATESIZE); destindex++; We now move onto the next row element.

row++; row on !row on; continue; I:\ELEC\CI S RA\OPENSC RN\O_SCRNO\appendixl1 .doc -54- If the current row transition point is equal in x position to the current previous region builder transition point, we advance the row counter to the next position.

if (*row rb runstart) row++; row on !row on; Output the previous regions builder's transition region. We do similiar things as for the region transition stuff above.. Firstly though, we advance the rb_prev_run_state variable to the next element. We know we can do this because if we were on the last element, we wouldn't have hit this section of code.

rb_prev_runstate r PrevRB->rrbStateData[src index]; if (destindex 1 R CurRB->rrbSize) if (!r_grow_region_builder(R_CurRB, destindex 1)) return FALSE; R_CurRB->rrbRgnData[dest_index] rbrun_start; *if (first) RCurRB->rrb_StateData[dest_index]=(rbprev_run_state RBCUR_STATE MASK) rb_prevrun_state RBSTATE SIZE); else R_CurRB->rrb_StateData[dest_index] rb_prevrun_state; if (!row_on) RCurRB->rrbStateData[destindex] (rgn mask RB_STATESIZE); Sdest index++; We've output the previous region builder's transitions. We now move over onto the next transition. If the previous src index increment has moved us onto the last element, we declare that we have run out of previous region builder data.

ASSERT(rb run start R EOR); if (++src index r PrevRB->rrb Nels) We've run out of data..

rb run start R INT MAX VALUE 2; continue; Otherwise, we still have stuff left to do, so we move onto the next run in the previous region builder.

rbrun_start r_PrevRB->rrb_RgnData[srcindex]; Now, we simply blast out any remaining region builder transition points.

if (r_PrevRB->rrb Nels src index 0) R_Intnels_tocopy; nels_to copy r_PrevRB->rrb_Nels src index; if (dest index nels_tocopy R CurRB->rrb Size) J:\ELEC\CISRA\OPENSCRN\OSCRN2\appendix .doc 55 if (!r_grow -region -builder(RCurRB, dest index nels to copy)) return FALSE; memopy RCurRB->rrbRgnData dest index, r -PrevRB->rrbRgnData src index, nels-to-copy sizeof(RInt) if (!first) memcpy RCurRB->rrbStateData dest_index, r -PrevRB->rrb StateData src index, nels_to copy sizeof (unsigned char) dest-index nels-to_copy; else unsinedchar *src; unsgne char *dest; i rPrevRB->rrbNels src index; src r rPrevRB->rrbStateData rPrevRB->rrbNels; dest index i; dest RCurRB->rrbStateData dest index; switch (i) default: for C; i 10; #ifnef BUSLOKUP *Cdest i) (*src RBCURSTATEMASK) (*Csrc RBSTATESIZE); #else *(dest i) r-shift-and-dup[*(src i] *:#endif FALLTHROUGH! I case (Cifndef RBUSELOOKUP *(dest 10) (*(src 10) RB_-CURSTATEMASK) (*(src 10) RBSTATESIZE); #felse *(dest 10) =r-shif t and-dup[*Csrc 10)1 #Cendif FALLTHROUGH! I case 9: #ifndef RBUSE_LOOKUP *Cdest 9) (*(src 9) RBCURSTATE MASK) C*(src 9) RBSTATE_SIZE); #Celse *Cdest 9) r-shift and-dup[*(src #Cendif FALLTHROUGH!I case 8: (Cifndef RBUSE_LOOKUP *Cdest 8) C*Csrc 8) RB_-CURSTATE MASK) C*(src 8) RBSTATE_SIZE); #Celse *Cdest 8) r-shift-and-dup[*(src (Cendif FALLTHROUGH!! case 7: I :\ELEC\Cl SRA\OPENSCRI4\O_SCRNQ2\appendix I .doc 56 #fifndef #felse ifendif if ndef* #felse #fendif #ififndef #felse ifendif 4ififndef

RBUSELOCKUP

*(dest 7) *(dest 7)

FALLTHROUGH!

case 6:

RBUSELOCKUP

*(dest 6) *(dest 6)

-FALLTHROUGH!

case RB USE LOCKUP *(dest 5) *(dest 5)

FALLTHROUGH!

case 4:

RBUSELOCKUP

*(dest 4) (*(src 7) RB_-CUR_-STATEMASK) (src 7) RB_STATE_SIZE); r-shift and dup[*(src (*(src 6) RBCUR_-STATEMASK) (src 6) RB_STATE_SIZE); r-shift and-dup[*(src (*(src 5) RB_-CUR_-STATEMASK) (src 5) RB_STATE_SIZE); r-sh if t and dup[*(s rc S)] ((src 4) RBCUR_-STATEMASK) ((src 4) RBSTATESIZE) 9* 9. 9* 19-* #else #fendif if fndef #felse #endif #fifndef ifelse #fendif ifif nde f #else ifendif (dest 4) r-shif t and dup (src FALLTHROUGHII case 3:

RBUSELOCKUP

*(dest 3) ((src 3) RB_-CUR_-STATEMASK) ((src 3) RB_STATE_SI ZE); *(dest 3) r-s h if tand dup*(s rc 3)] FALLTHROUGH!! case 2:

RBUSELOCKUP

*(dest 2) ((src 2) RBCUR_-STATEMASK) ((src 2) RBSTATE_SIZE); *(dest 2) r-shi f tand dup rc 2)]

FALLTHROUGH!!

case 1:

RBUSELOCKUP

*(dest 1) (*(Src 1) RBCURSTATEMASK) (src 1) RBSTATESIZE); *(dest 1) r-shi f tand-dup rc -1

FALLTH-ROUGH!!

case 0: FALLTHROUGH! I *Finally, we set the number of elements of the latest region *builder. We also return the updates row variable.

R_-CurRB->rrbNels dest index; *row-ptr row; return TRUE; 1:\ELEC\CI SRA\OP ENSCRN'OSCRN2\appcndixI .doc -57- #else int R add row to R Int int int region_builder **row_ptr, rgn_mask, first R Int R_Int unsigned char int int unsigned char unsigned char unsigned char register RInt R_Int register R Int R Int int int *row; rbrun start; rb_prev_run_state; row_on; dest_index; *src_state_ptr; *dest_stateptr; *src_state_end_ptr; *src_rgn_ptr; *src_rgn_end_ptr; *dest_rgnptr; *dest rgn_end_ptr; inc; i; n n ASSERT(rgnmask 1 rgnmask 2); row *row_ptr; r_swap_region_builders(); Skip over the row's y value at the beginning.

ASSERT(*row R NEXT IS Y); row 2; ASSERT(*row R_NEXTIS_Y *row REOR); if (r_PrevRB->rrb Nels 0) If the current region builder's src region data array is empty, then we are dealing with an empty region builder. We simply convert the input row to the region builder format.

rowon TRUE; dest_index 0; while (R NOT END OF ROW(*row)) if (++dest_index R CurRB->rrb Size) if grow region_builder(R_CurRB, dest_index)) return FALSE; R _CurRB->rrb_RgnData[dest_index 1] *row; if (row on) R CurRB->rrbStateData[dest index 1] (rgnmask RB STATE SIZE); else R_CurRB->rrb_StateData(dest_index 1] 0; row on !row on; row++; *row ptr row; R_CurRB->rrb_Nels destindex; return TRUE; Firstly, we copy any runs from the region builder which I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendixl .doc 58 precede this run from the region. We are checking the starting row against the start of each pixel run. Therefore we start checking against the 1nd region builder data element.

src-stateptr r_-PrevRB->rrb_-StateData; arc rgnptr r_PrevRB->rrbRgnData; src-state-endjptr src -state ptr rPrevRB->rrb_-Nels; srcrgnendptr rc rgn ptr r_-PrevRB->rrbNels; dest-stateptr R RCurRB->rrb_-StateData; destrgnptr RCurRB->rrbRgnData; destrgnendptr dest rgnptr P.CurRB->rrbSize; ASSERT(rPrevRB->rrbNels 2); while (arc_rgnptr-! srcrgnendptr *row *src-rgnptr) srcrgnptr++; inc s rc rgnptr r-PrevRB->rrb-RgnData; if (inc 0) src_stateptr inc; dest_stateptr inc; dest -rgnptr inc; if (destrgnptr dest-rgnendptr) if grow region builder(RCurRB, inc)) return FALSE; dest -state ptr RCurRB->rrb_-StateData; dest-rgnptr P_CurRB->rrb_RgnData; destrgnendptr dest rgnptr P. CurRB->rrbSize; #if 1 const R-Int R-Int switch (ic) const arc rgn ptr2 arc rgnptr; *destrgnptr2 dest rgn_ptr; default: for (i inc; i 10; *(destrgnptr2 rgnptr

FALLTHROUGH!!*

case *(dest-rgnptr2 10) (src-rgnptr2 FALLTHROUG-{H case 9 *(dest -rgnptr2 9) 1* FALLT-ROUGH!!* case 8: *(dest-rgnptr2 8)

FALLTHROUGH!!*

case 7: *(dest -rgnptr2 7) FALLTHROUGH!! case 6: *(dest -rgnptr2 6) FALLTHROUGH!! case *(dest -rgnptr2 5) 1* FALLTHROUGH!! case 4: *(dest -rgnptr2 4)

FALLTHROUGH!!

case 3: *(dest-rgnptr2 3)

FALLTHROUGH!!

case 2: *(srcrgnptr2 9); *(srcrgnptr2 8); *(srcrgnptr2 7); (srcrgnptr2 6); =*(srcrgnptr2 *(srcrgnptr2 4); *(src-rgn-ptr2 3); *(dest-rgnptr2 2) *(srcrgnptr2 2); I :\ELEC\CISRA\OPENSCRN\OSCRNO2\appendix .doc 59 FALLTHROUGHII case 1: *(dest -rgnptr2 1) FALLTHROUGH!! case 0: 1* FALLTHROUGH!! memcpy R_-CurRB- >rrbRgnData, r_-PrevRB- >rrbRgnData, inc sizeof(RInt) *(src-rgnptr2 1); )(else ffendif if (f irst) memcpy RCurRB->rrb_-StateData, rPrevRB->rrb_-StateData, inc sizeof (unsigned char) else switch (inc) default: for (i inc; i 10; #ifndef RBUSELOCKUP *(dest-state ptr i) (src -stateptr i) RB_-CUR_-STATEMASK) I (*(src-state ptr

RB_STATE_SIZE);

#(else ifendif case )*ifndef RBUSELOOKUP *(dest-state ptr i) r-shif t and-dup[*(src~state~ptr-

FALLTHROUGHI!

*(dest state ptr 10) -state~ytr 10)

RBCURSTATEMASK)I

(*(src-state-ptr 10)

RBSTATESIZE);

#felse ttendif case 9: )tifndef RBUSELOCKUP #telse )iendif case 8: )fifndef RBUSELOCKUP #4else )tendif dest state ptr 10) r-shift-and-dup[*(src-state ptr FALLTHROUGH!! dest-stateptr 9) (src_state ptr 9) RBCUR_-STATE_-MASK) (*(src_state ptr 9) RBSTATESIZE); dest state ptr r shift and dup(* (src-state ptr

FALLTHROUGH!!

dest state ptr (src-state ptr 8) RBCURSTATEMASK) (*(src_state ptr 8) RBSTATESIZE); deststateptr 8) r shift and dup[* (src-stateptr -8] FALLTHROUGH!! l\E LE\CI SRA\OPENSCRN\0_SC RNO2\appendix 1. doc 60

C.

fti fnde f #telse #tendi f #ifndef #telse #endif itifndef #felse ftendif ftifndef #felse itendif fti fnde f #felse #endif #ifndef #else #endif fifndef #telse fendif case 7:

RBUSELOOKUP

(deststateptr (dest-state-ptr FALLTHROUGHI I case 6:

RUSELOOKUP

(deststateptr (deststateptr

FALLTHROUGHI!

case

RBUSELOOKUP

(deststateptr (dest state ptr FALLTHROUGH! I case 4:

RBUSELOOKUP

(dest-state-ptr (dest state ptr 1* FALLTHROUGHI! case 3:

RBUSELOOKUP

(dest-state-ptr (dest-state-ptr

FALLTHROUGHI!

case 2:

RBUSELOOKUP

(dest-state-ptr (deststateptr

FALLTHROUGH!!

case 1:

RBUSELOOKUP

(dest-state-ptr (dest-state-ptr

FALLTHROUGHI!

case 0: FALLTHROUGHI I (*(src-stateptr 7) RBCUR_-STATE_-MASK) (*(src_statejptr 7) RBSTATESIZE); 7) r-shift and dup[*(src_stateptr 6) (src_statejptr 6) RB_-CUR_-STATEMASK) (*(src_stateptr 6) RBSTATESIZE); 6) r-shift and dup(*(src-state ptr 5) (src-stateptr 5) RB -CUR -STATE-MASK) (*(src-state-ptr 5) RBSTATESIZE); 5) r-shift-and-dup[*(src-state-ptr 4) (src_stateptr 4) RB -CUR -STATE-MASK) (*(src-state-ptr 4) RBSTATESIZE); 4) r-shift and dup[*(src-stateptr 3) (srcstateptr 3) RB -CUR -STATE-MASK) (*(src-state-ptr 3) RBSTATESIZE); 3) r-shift-and dup[*(src_stateptr (*(src-state ptr 2) RB CUR STATE MASK) (*(src-state-ptr 2) RBSTATESIZE); 2) r-shift-and dup[*(src-stateptr )((src-state ptr 1) RB -CUR -STATE-MASK) (*(src-state ptr 1) RBSTATESIZE); r-shift-and-dup[*(src-stateptr if (src-state ptr src_stateendptr) *We've already exhausted the previous region builder. Set the start *of the next pixel run to be the max. possible and set the state *to be 0.

I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendixl .doc -61rbrun_start R_INT_MAX_VALUE 2; rb prev_run_state 0; else We are still within the previous region builder bounds. Set up the run info appropriately.

rb_run_start *srcrgn_ptr; if (src_stateptr r_PrevRB->rrb_StateData) rb_prevrun_state 0; else rbprev_run_state *(src_stateptr 1); We can now start dealing with the elements in the row.

rowon 1; while (R NOT END OF ROW(*row)) if (*row rb run start) if (dest_rgn_ptr 1 dest_rgn_end_ptr) if (!r_grow_region_builder(R_CurRB, dest_rgn_ptr R_CurRB- >rrbRgnData return FALSE; dest_state_ptr R_CurRB->rrbStateData; dest_rgn_ptr R_CurRB->rrb_RgnData; dest_rgn_end_ptr destrgn_ptr R_CurRB->rrb Size; *destrgn_ptr *row; if (first) We are processing the first region. Therefore, we copy the current state of the run to the lowest RB STATE SIZE bits.

*dest_state_ptr (rb_prev_run_state RB_CURSTATE MASK) (rbprev_run_state RBSTATE SIZE); else We are processing the second region. Therefore, the state data has already been copied to the previous state area so we just copy the state.

*deststate_ptr rb_prev_runstate; Now, if the row for the current region is active at this transition, we xor the region mask with the current contents of the new region builder slot. This gives the desired behaviour of making that region active if it is not there already, but turns it off if it is...

if (row_on) *dest_state ptr (rgn_mask RBSTATESIZE); deststate ptr++; dest_rgn_ptr++; We now move onto the next row element.

row++; rowon !row on; I:\ELEC\CISRA\OPENSCRN\O_SCRNo2\appendix .doc -62continue; If the current row transition point is equal in x position to the current previous region builder transition point, we advance the row counter to the next position.

if (*row rb run start) row++; row on !row on; Output the previous regions builder's transition region. We do similiar things as for the region transition stuff above.. Firstly though, we advance the rb_prev_run_state variable to the next element. We know we can do this because if we were on the last element, we wouldn't have hit this section of code.

rb_prev_runstate *src_state_ptr; if (dest_rgn_ptr 1 dest_rgn_end_ptr) if (!r_grow_region_builder(R_CurRB, dest_rgn_ptr R_CurRB->rrb_RgnData return FALSE; dest_state_ptr RCurRB->rrb_StateData; destrgn_ptr R_CurRB->rrb_RgnData; dest_rgn_end_ptr dest_rgn_ptr RCurRB->rrb Size; *dest_rgn_ptr rb run start; if (first) *dest_state_ptr (rb_prevrun_state RBCUR STATE_MASK) *(rb_prev_run_state RBSTATESIZE); else *dest_state_ptr rb_prev_run_state; if (!row on) *dest_state_ptr (rgn_mask RB_STATE_SIZE); dest_state_ptr++; dest_rgn_ptr++; S* We've output the previous region builder's transitions. We now move over onto the next transition. If the previous src index increment has moved us onto the last element, we declare that we have run out of previous region builder data.

ASSERT(rbrunstart R EOR); ++src_rgn_ptr; if (++src_state_ptr src_state_end ptr) We've run out of data..

rbrunstart R INT MAX VALUE 2; continue; Otherwise, we still have stuff left to do, so we move onto the next run in the previous region builder.

rb_runstart *src_rgn_ptr; Now, we simply blast out any remaining region builder transition points.

I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendixl.doc 63 if (src-stateptr src-state endptr) RIntnels-to-copy; nels_to copy src_state endptr src_stateptr; if (destrgnptr nels_to copy dest_rgnendptr) if r_grow region builder 2_CurRB, destrgnptr R-CurRB->rrbRgnData nels t ocopy return FALSE; dest-state_ptr RCurRB->rrbStateData; destrgnptr =R CurRB->rrb RgnData; memcpy destrgnptr, srcrgnptr, nels_to_copy *sizeof(RInt) dest_rgnptr nels-to-copy; if (!first) memcpy dest_stateptr, src_stateptr, nels_to copy sizeof (unsigned char) else i nels -t ocopy; src-stateptr src-state-endptr; dest -state ptr nels-to_copy; switch Wi default: for i 10; #ifndef RBUSELOOKUP *(dest-state ptr (*(src_state ptr i) RBCURSTATE-MASK) (*(src_state ptr i) RBSTATESIZE); #else *(dest state ptr i) r-shift-and-dup[*(src-state ptr ifendif

FALLTHROUGH!!*

case )tifndef RBUSELOOKUP *(dest state ptr 10)= (*(src_state ptr 10)&RB_-CUR_-STATE -MASK) (*(src_stateptr 10) RBSTATESIZE); #else *(dest state ptr 10) =r-shift-and-dup[*(src-state ptr ftendif 1* FALLTHROUGH!!* case 9: l#ifndef RBUSELOOKUP *(dest state ptr (Src_stateptr 9) RB_-CUR_-STATE-MASK) #else(*(src_stateptr 9) RBSTATESIZE); *(dest state ptr 9) r-shift and dup[*(src-state ptr #endif 1FALLTHROUGH!!~ I:\ELEC\CI SRA\OPENSC RN\_SCRN2\appendix1. doc 64

S

ftifndef #else ftendif #if ndef #else #endif )ifndef #else )#endi f W indef #else )4endif #if ndef #else )4endif #if ndef #else t4endif #if ndef 4else ifendif #tif ndef #else ftendif case 8:

RBUSELOOKUP

(dest state ptr (deststateptr

FALLTHROUGH!!

case 7:

RBUSELOOKUP

(dest state ptr (deststateptr 1* FALLTHROUGH!! case 6:

RUSELOOKUP

(dest state ptr (deststateptr

FALLTHROUGHI!

case

RBUSELOOKUP

(dest state ptr (dest state ptr 1* FALLTHROUGHI! case 4:

RBUSELOOKUP

(deststateptr (dest-stateptr

FALLTHROUGHI!

case 3:

RBUSELOOKUP

(dest state ptr (dest-state ptr

FALLTH-ROUGHI!

case 2:

RBUSELOCKUP

(dest state ptr (dest state ptr

FALLTHROUGH!!

case 1:

RBUSELOOKUP

*(dest_state_ptr *(dest_state_ptr

FALLTH-ROUGH!!

case 0:

FALLTHROUGH!!

8) (src-stateptr 8) RB_-CURSTATEMASK) (*(src_state ptr 8) RBSTATESIZE); 8) =r shift and dup[* (src-stateptr -8] 7) (src_stateptr 7) RB_-CUR_-STATEMASK) (*(src_stateptr 7) RBSTATESIZE); 7) =r-shift and dup[*(src_stateptr ((src_state ptr 6) RB -CUR -STATE-MASK) (*(src-state-ptr 6) RBSTATESIZE); 6) r-shift and dup[*(src-stateptr 5) ((rcstateptr 5) RB_-CUR_-STATEMASK) (*(src-state-ptr 5) RBSTATESIZE); 5) r-shift-and dup[*(src_stateptr 4) (srcstateptr 4) RB -CUR -STATE-MASK) (*(src-state-ptr 4) RBSTATESIZE); 4) =r-shift_and dup(*(src-stateptr 3) =*(srcstate ptr 3) RB -CUR -STATE-MASK) ((src-state-ptr 3) RBSTATE'SIZE) 3) =r-shift-and dup[*(src-state ptr 2) ((src_state ptr 2) RB -CUR -STATE -MASK) (*(src_state ptr 2) RBSTATESIZE); 2) =r-shift-and dup[*(Src-state ptr )((src-state ptr 1) RB -CUR -STATE-MASK) (*(src_state ptr 1) RBSTATESIZE); r-shift and-dup[*(src-state-ptr -1] I :\ELEC\CISRA\OPENSCRN\OSCRNO2\appendix I .doc Finally, we set the number of elements of the latest region builder. We also return the updates row variable.

R_CurRB->rrb_Nels dest_rgn_ptr R_CurRB->rrb RgnData; *row_ptr row; return TRUE; #endif r_check_rgn_buflen This function checks to see if the static region buffer is large enough.

If it isn't then it is reallocated to make it large enough.

Parameters: size The required size of the r_RegBuf array.

Returns: TRUE on success, FALSE on failure.

static int r_check_rgnbuflen int size ASSERT(size 0); if (size rRgnBufSize) int newbuf size; R_Int *newbuf; new_buf_size max(size, r_RgnBufSize 2); newbuf (RInt *)malloc(new_bufsize sizeof(R Int)); if (new buf NULL) return FALSE; if (r_RgnBuf NULL) memcpy(new_buf, r_RgnBuf, r_RgnBufSize sizeof(RInt)); free(r_RgnBuf); r_RgnBuf new buf; r_RgnBufSize new buf size; return TRUE; R_init_regionwithrect This function initialises a R_Region structure to represent a rectangular region. It is assumed that the region is currently uninitialised.

Paramete

I

i Returns: 1 rs: rgn rect A pointer to the R_Region to be initialised.

A pointer to an IntXYMinMax structure representing the rectangular area requiring an equivalent region description.

TRUE on success, FALSE on failure.

R_init regionwithrect R_Region IntXYMinMax *rgn, *rect I:\ELEC\CISRA\OPENSCRNO_SCRN02\appendixl.doc 66 R_Int *rgn_data; ASSERT(rect->X.min rect->X.Max); ASSERT(rect->Y.Min rect->Y.Max); rgn->rr BBox =*rect; rgn_data (R Int *)malloc(9 sizeof(R-Int)); if (rgn data NULL) return FALSE; rgn_data[O] RNEXT_IS_Y; rgn -data =rect->Y.Min; rgn-data[2] rect->X.Min; rgn_data[3] rect->X.Max 1 rgn_data(4] R RNEXTISY; rect->Y.Max 1; rgn-data[6] rect->X.Min; rgn_data[7] rect->X.Max 1; rgn_data[8] 2_EOR; *rgn->rr RgnData rgn -data; rgn->rr RgnDataSize 9; return TRUE; *R-region~with~region *This function initialises a R_-Region structure to represent a the region *passed as an argument. It is assumed that the region is currently *uninitialised.

*Parameters: *rgn A pointer to the R-Region to be initialised.

*srcrgn A pointer to an RRegion structure representing the region to which this region is to be initialised.

*Returns: TRUE on success, FALSE on failure.

mnt R_mnit_region with region RRegion *rgn, RRegion *srcrgn R Tnt *rgn_data; rgn->rrBBox =src-rgn->rrBBox; rgn-data (R2_mt *)malloc(srcrgn->rrRgnDataSize *sizeof(RInt)); if (rgn data NULL) return FALSE; memcpy rgn data, srcrgn- >rrRgnData, srcrgn->rrRgnDataSize *sizeof(RInt) rgn->rrRgnData rgn_data; rgn- >rrRgnDataSize srcrgn- >rrRgnDataSize; return TRUE; 1 LEC\cI SRA\OPENSCRN\O_SCRNO2\appendix L doc 67 *R_region-with-translated region *This function initialises a R_-Region structure to represent a the region *passed as an argument translated by delta. It is assumed that the region *is currently uninitialised.

*Parameters: rgn s rcrgn A pointer to the R-Region to be initialised.

A pointer to an RRegion structure representing the region to which this region is to be initialised.

A pointer to a IntXY structure representing the translation required.

*Returns: lelta PRUE on success, FALSE on failure.

R -init region-with-translated region RRegion R_Region IntXY R Int R mnt rgn, *src_rgn, *delta *rgn_data; *src-data; rgn->rrBBox.X.Min srcrgn->rr_-BBox.X.Min delta->X; rgn->rrBBox.X.Max =srcrgn->rr_-BBox.X.Max delta->X; rgn->rr_-BBox.Y.Min src rgn->rr_-BBox.Y.Min delta->Y; rgn->rrBBox.Y.Max src rgn->rrBBox.Y.Max delta->Y; rgn-data CR It *)malloc(src-rgn..>rrRgnoataSize sizeof(RInt)); if (rgn data NULL) return FALSE; src data srcrgn->rrRgnData; for (mnt i 0; i srcrgn->rr-RgnDataSize; if Csrc-data Ci] R NEXTISY) rgn_data[i] src-data~i]; rgn_data~i] =src data~i] delta->Y; continue; else if (src-data ti) R_-EOR) rgn-data[i] src-data~i]; else rgn_data~i] src-datai delta->X; rgn->rr-RgnData rgn_data; rgn->rr -RgnDataSize srcrgn->rrRgnDataSize; return TRUE; *Rempty region *Deallocates the *data is freed.

*Parameters: *Returns: Nothing.

void region data allocated for a region. Only the The RRegion structure itself is not.

The region whose region data is to be deallocated.

I\E LEC\CI SRA\OPENSCRN\OSCRNQ2\appendix Ldoc -68- Rempty_region R_Region *rgn if (rgn NULL rgn->rr_RgnData NULL) free(rgn->rrRgnData); rgn->rr_RgnData NULL; #ifndef R USE NEW IMP R union This function inits a R_Region structure to represent the union of it's two arguments.

Parameters: rgn The R_Region to be initialised.

rl A R_Region ptr representing the first region.

r2 A R_Region ptr representing the second region.

Returns TRUE on success, FALSE on failure.

int S R union R_Region *rgn, R_Region *rl, R_Region *r2 R_Int *rl dat; R_Int *r2_dat; int overlap flags; uniontot++; if (!BB intersect test(&rl->rr BBox, &r2->rr BBox, &overlap flags)) The bounding boxes don't intersect. This means we can do the union very easily, simply by copying data from the two regions.

We malloc a new region data array of size rl->rrRgnDataSize r2->rr_RgnDataSize 1. This is the maximum possible size of resulting region. Not all of this memory will be utilised if the two regions being combined have rows with the same y coordinate (RNEXT IS Y marker is not duplicated).

rgn->rrRgnDataSize rl->rr_RgnDataSize r2->rr_RgnDataSize 1; rgn->rr_RgnData (R_Int *)malloc(rgn->rr_RgnDataSize sizeof(R_Int)); if (rgn->rr_RgnData NULL) return FALSE; Now, check to see if the regions overlap in if (!(overlap_flags BBINTERSECT_OVERLAP Y)) The regions don't overlap in y. We simply copy one region and then another into the array we malloced. We ensure that rl points to the region with the smallest y coordinate.

if (r2->rr_BBox.Y.Min rl->rr_BBox.Y.Min) I:\ELEC\CISRA\OPENSCRN\0_SCRN02\appendixl .doc 69 RRegion *tmp; tmp =ri; ri r2; r2 =tmp; memcpy rgn- >rr -RgnData, r >rrRgnData, (rl->rr-RgnDataSize 1) *sizeof(RInt) memcpy rgn->rrRgnData rl->rr-RgnDataSize -1, r2 ->rrRgnData, r2->rrRgnDataSize sizeof(RInt) ASSERT(rgn->rrRgnData~rgn->rr-RgnDataSize R EOR); else *R-It *rl-tmp; R Int *r2_tmp; Int *dest.

R-Int min-row; t ri done; int ri consumed; mt r2_consumed; int num-written; The bboxes overlap in y but not in x. we simply go row by row through each region and memcpy the individual rows as appropriate. We ensure that rl points to the region with the smallest x coordinate.

if (r2->rr_BBox.X.Min rl->rr_BBox.X.Min) tmp l r2 =tmp; r2_dat rl->rrRgnData; dest rgn->rrRgnData; rgn->rrRgnDataSize 0; rl-consumed 0; r2_consumed 0; while (*rl dat EOR *r2 dat R_EOR) ASSERT(*r1_-dat ==RNEXT_IS_-Y); ASSERT(*r2_-dat ==RNEXT_IS_-Y); min _row min(rl-dat[1], r2_dat rl-done FALSE; if (ri-dat[1] min-row) *We need to emit rl. We therefore need to find where *the next row (if any) starts. When we do this we *recall that a y value _must be followed by at least *two x values..

rltmp ri_dat 4; while (*rl_tmp RNEXTISY *rltmp R_EOR) ri -tmp++; num-written ri_tmp, ri -dat; memcpy(dest, ri dat, num-written sizeof(R Int)); 1:\ELEC\Cl SRA\OPENSC RM\0SCRNO2\appendix I doc 70 dest num written; ri-consumed num-written; rgn->rr RgnDataSize num-written; ri-dat =rltmp; ri-done TRUE; if (r2_dat[l] min-row) We need to emit ri. We therefore need to find where the next row (if any) starts. When we do this we recall that a y value -must be followed by at least two x values. If rl's current row has already been emitted for this y value, we do _not_ emit the R_NEXTISY marker or the y value itself.

if Cr1_done) r2_dat 2; r2-tmp r2_dat 2; r2_consumed 2; else r2_tmp r2_dat 4; *while (*r2_tmp 1= RNEXTISY *r2_tmp 1=REOR) r2_tmp++; *num -written r2_tmp r2 -dat; memcpy(dest, r2_-dat, num-written sizeof(k Int)); dest num written; r2 consumed num written; rgn->rr -RgnDataSize num-written; r2_dat r2_tmp; if (*rl dat R EOR) ri is the last region left standing. We memcpy *teremainder of the region (including the REOR marker) to the destination.

:ASSERT(r2_consumed r2->rrRgnDataSize 1); memcpy dest, rl dat, (rl->rrRgnDataSize rl-consumed) sizeof(RInt) rgn->rrRgnDatagize (rl->rr_RgnDataSize rl-consumed); else r2 is the last region left standing. We memcpy the remainder of the region (including the R EOR marker) to the destination.

ASSERT(rl-consumed rl->rrRgnDataSize-1) memcpy dest, r2_dat, (r2->rr_RgnDataSize r2 consumed) sizeof(RInt) rgn->rrRgnDataSize (r2->rrRgnDataSize r2 consumed); [:\ELEC\CISRA\OPENSCRN\OSCRNO2\appendixl .doc -71

ASSERT

rgn->rr_RgnData(rgn->rr_RgnDataSize 1] R EOR else R_Int min_row; int dest_size; unsigned char *rgn_bld_stat; R_Int *rgnbld_dat; int i; int inrun; int done rl in row; union_full++; The two regions _do_ overlap in x _and y. We therefore have to do a bit more work in calculating the union of the two regions. We use the RRegionBuilder struct to store state o* regarding the currently active regions as we progress through the rows of each region. After any rows relevent to a y-coord are added to the region builder, we examine the state of each pixel run in the region builder. If the addition of the row(s) for the y-coord have caused a transition to or from 0, then the pixel run is emitted. However, the first thing we do is ensure the current region builder is empty.

0rld rl_dat rl->rr_RgnData; r2_dat r2->rrRgnData; R_CurRB->rrbNels 0; dest size 0; We are now ready to loop through the data of both regions.

We continue building the new region whilst there is data remaining in either of the two regions.

while (*rldat REOR *r2_dat R EOR) ASSERT(*rl_dat RNEXT_IS_Y *rl dat R EOR); S ASSERT(*r2 dat RNEXT_IS_Y *r2 dat R EOR); if (*rldat R EOR) min row r2 dat[l]; else if (*r2_dat REOR) min row rl dat[l]; else minrow min(rl_dat[l], r2_dat[l]); done rl in row FALSE; if (*rl_dat REOR rl_dat(l] min_row) The first region is active on this y coord. We add this row to the current region builder.

if (!R_add_row to region_builder(&rl dat, Oxl, TRUE)) return FALSE; done rl in row TRUE; if (*r2_dat REOR r2_dat[l] min row) The first region is active on this y coord. We add this row to the current region builder.

if (!R_add_row_to_region_builder(&r2_dat, 0x2, !done rl in row)) I:\ELEC\C SRA\OPENSCRN\O_SCRNO\appendix I.doc 72 return FALSE; *Now, we generate the output row for the input rows.

if (!r-check rgnbuf-len(dest-size 2)) return FALSE; rRgnBuf(dest size++J R2_NEXTISY; rRgnBuf[dest size++] min _row; rgn bid stat =RCurRB->rrbStateData; rgn bid dat R RCurRB->rrb_RgnData; in run FALSE; for (i =,RCurRB->rrbNels; i 0; if *rgn bid stat 0 *(*rgn -bid -stat RBCURSTATEMASK) ==0 (*rgn hid stat RBPREVSTATEMASK) ==0 We have to emit a run here, if we're not already in one..

if (lin-run) *if (!r_check rgn buf len(dest-size 1)) return FALSE; r RgnBuf[dest-size++) =*rgn bid_dat; in-run TRUE; else if (in-run) *We've cone to the end of a run. We output the next element to end it.

if (!r_check rgn buf len(dest-size 1)) return FALSE; r_RgnBuf[dest-size++] =*rgn_hid_dat; in-run FALSE; rgn bid-stat++; rgn bid-dat++; if (rRgnBuf[dest-size 2] R NEXTISY) *we didn't output anything for these input rows. Rewind..

dest_size 2; 1A:ELEC\CI SRA\OP ENSC RMOSCRN02\appendix L doc -73- We've completed constructing the data for the region. We make a copy the constructed data from the permanent buffer to an exactly fitting buffer.

rgn->rr_RgnData (R_Int *)malloc(++dest size sizeof(R_Int)); if (rgn->rr_RgnData NULL) return FALSE; memcpy(rgn->rr_RgnData, r_RgnBuf, (destsize 1) rgn->rr_RgnData[dest_size 1] REOR; rgn->rr_RgnDataSize dest_size; ASSERT(rgn->rr_RgnDataSize 9); sizeof(R Int)); We now do a bounding box union of the two component bboxes and place the result in the new region.

BB_union(&rl->rr_BBox, &r2->rr_BBox, &rgn->rr BBox); Done! We can get out..

return TRUE; R_union_equals This function basically implements a rl union= r2 type operation. Ie rl union r2 is calculated and the result returned in rl.

Parameters: rl S r2 Returns:

TRUE

A pointer to an R_Region. This represents the first half of the union, and is also used to return the eventual result.

A pointer to an R_Region. This represents the second half of the union.

E on success, FALSE on failure.

int S R_union_equals R_Region *rl, R_Region *r2 R_Region new_rgn; if (rl->rr_RgnData NULL) return Rinit region_with region(rl, r2); if (!R_union(&newrgn, rl, r2)) return FALSE; R_empty region(rl); *rl new rgn; return TRUE; R_intersection This function inits a R_Region structure to represent the intersection of it's two arguments.

Parameters: rgn rl r2 A R_Region ptr to the R Region structure to be initialised.

A R_Region ptr representing the first region.

A RRegion ptr representing the second region.

I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendix I.doc -74- Returns TRUE on success, FALSE on failure.

int R intersection R_Region *rgn, R_Region *rl, R_Region *r2 R_Int *rldat; R_Int *r2_dat; int overlap_flags; inttot++; rgn->rr_RgnData NULL; if (!BB_intersect_test(&rl->rr_BBox, &r2->rr_BBox, &overlap flags)) The bounding boxes don't intersect. This means that the regions don't intersect. Therefore, we simply set rgn->rrRgnData to NULL (signifying an empty region) and get out..

return TRUE; R_Int min row; int dest_size; unsigned char *rgnbld stat; R Int *rgn bld dat; S. int i; int in_run; int done rl in row; IntXYMinMax new_bbox; tintfull++; The two regions _do_ overlap in x _and y. We therefore have to do a bit more work in calculating the intersection of the two regions. We use the R RegionBuilder struct to store state regarding the currently active regions as we progress through the rows of each region. After any rows relevent to a y-coord are added to the region builder, we examine the state of each pixel run in the region builder. If the addition of the row(s) for the y-coord have caused a transition to or from 0x3, then the pixel run is emitted.

Initialise the newbbox structure for determining the new bounding box.

new_bbox.X.Min R INT MAXVALUE; newbbox.Y.Min R INTMAXVALUE; newbbox.X.Max RINTMINVALUE; newbbox.Y.Max R INTMINVALUE; The next thing we do is ensure the current region builder is empty, and set up pointers into the region data of the two regions.

rl_dat rl->rr_RgnData; r2_dat r2->rr RgnData; R CurRB->rrb Nels 0; dest size 0; We are now ready to loop through the data from both regions. Notice I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendixl.doc p that we only keep looping whilst _both_ regions have some data left to give. As soon as either of the region's data has been exhausted, then we stop as the intersection region has already been calculated and is sitting in the rgn buf.

while (*rl dat R EOR *r2 dat R_EOR) ASSERT(*rl_dat R_NEXT IS Y I| *rl_dat R EOR); ASSERT(*r2_dat R NEXT IS Y *r2_dat R_EOR); if (*rldat R_EOR) min row r2_dat[l]; else if (*r2_dat R EOR) min_row rl_dat[l]; else minrow min(rl_dat[l], r2 dat[l]); donerlin row FALSE; if (*rl_dat R_EOR rl dat[l] min row) The first region is active on this y coord. We add this row to the current region builder.

if (!R_add_rowto_region_builder(&rl_dat, Oxl, TRUE)) return FALSE; done rl in row TRUE; if (*r2_dat R_EOR r2_dat[l] min row) The first region is active on this y coord. We add this row to the current region builder.

if add_row_to_region_builder(&r2_dat, 0x2, !done rl in row)) return FALSE; Now, we generate the output row for the input rows.

*1 if (.!r_check rgn_buf_len(dest size 2)) return FALSE; r RgnBuf[destsize++] R NEXT IS Y; rRgnBuf[dest_size++] min_row; rgnbld_stat R CurRB->rrb StateData; rgn_bld_dat R_CurRB->rrb_RgnData; in_run FALSE; for (i R_CurRB->rrbNels; i 0; if *rgn bldstat (3 (3 RB_STATE_SIZE)) (*rgn_bld_stat RB_PREVSTATEMASK) 3 (*rgn_bld_stat RB_CURSTATE_MASK) (3 RB STATE SIZE)) We have to emit a run here, if we're not already in one..

if (!in_run) if (!r_check_rgn_buf_len(destsize 1)) return FALSE; I:\ELEC\CISRA\OPENSCRMOSCRNQ2\appendix .doc -76r_RgnBuf[dest_size++] *rgn_bld dat; in run TRUE; new_bbox.X.Min min(new_bbox.X.Min, *rgn_bld dat); else if (in_run) We've come to the end of a run. We output the next element to end it.

if (!r_check rgn_buf_len(destsize 1)) return FALSE; r_RgnBuf[dest_size++) *rgn blddat; new_bbox.X.Max max(new_bbox.X.Max, *rgnbld dat); inrun FALSE; rgnbld stat++; rgn_blddat++; if (r_RgnBuf[dest_size 2] RNEXT IS Y) We didn't output anything for these input rows. Rewind..

destsize 2; else if (min row newbbox.Y.Min) newbbox.Y.Min min row; else if (min row new bbox.Y.Max) newbbox.Y.Max min row; We've completed constructing the data for the region. Firstly we check to see if we've emitted anything.at all. If we have then dest_size must be 0. If it isn't we simply free the region we created and get out, as the regions don't really intersect, in spite of their intersecting bounding boxes.

if (destsize 0) return TRUE; We make a copy the constructed data from the permanent buffer to an exactly fitting buffer.

rgn->rr_RgnData (R_Int *)malloc(++dest_size sizeof(RInt)); if (rgn->rr_RgnData NULL) return FALSE; memcpy(rgn->rr_RgnData, r_RgnBuf, (dest_size 1) sizeof(RInt)); rgn->rrRgnData[dest_size 11 R_EOR; rgn->rrRgnDataSize dest_size; ASSERT(rgn->rr_RgnDataSize 9); Now, copy across the bounding box.. Before we do this, we subtract 1 from X.Max and Y.Max because of the region format.

I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendixl.doc 77 ne* bo.1Mxnew-bbox.X.Max--; rgn->rrBBox new-bbox; *Done! We can get out..

return TRUE; *R-difference *This function inits a R -Region structure to represent the difference of *it's two arguments. It essentially calculates ri r2 *Parameters: *rgn A R_-Region ptr representing the R-Region to be inited.

*rl A RRegion ptr representing the first region.

*r2 A RRegion ptr representing the second region.

*Returns TRUE on success, FALSE on failure.

mt R Rdifference R_Region *rgn, *R_Region *rl, R_Region *r2 *RTnt *rl -dat; R Int *r2_dat; mt overlap flags; diff-tot++; rgn->rrRgnData NULL; if (!BB intersect test(&rl->rrBBox, &r2->rr BBox, &overlapf flags)) ax The bounding boxes don't intersect. This means that rl r2 simply equals rl. We make a copy of the relevant bits and get out..

rgn->rr_BBox rl->rr_-BBox; rgn->rrRgnDataSize =rl->rr -RgnDataSize; rgn->rrRgnData (RTnt *)malloc(r1->rrRgnDataSize *sizeof(R Tnt)); if (rgn->rrRgnData

NULL)

return FALSE; memcpy rgn- >rrRgnData, ri- >rrRgnData, rl->rrRgnDataSize *sizeof(RTnt) return TRUE; RTnt min _row; int dest-size; unsigned char *rgnbld_stat; R T nt *rgnbld_dat; mnt 1; mnt in run; mnt done-ri in row; unsigned char m-high; I :\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendix i.doc -78unsigned char m_low; IntXYMinMax newbbox; diff full++; The two regions _do_ overlap in x _and y. We therefore have to do a bit more work in calculating the difference of the two regions. We use the R_RegionBuilder struct to store state regarding the currently active regions as we progress through the rows of each region. After any rows relevent to a y-coord are added to the region builder, we examine the state of each pixel run in the region builder. If the addition of the row(s) for the y-coord have caused the following transitions rl 0 0 r2 rl r2 r2 r2 rl r2 then the relevent runs are emitted. Firstly, though, we ensure the current region builder is empty, and set up pointers into the region data of the two regions.

rl_dat rl->rr_RgnData; Sr2_dat r2->rr_RgnData; RCurRB->rrb Nels 0; destsize 0; Initialise the new_bbox structure for determining the new bounding box.

new_bbox.X.Min 32767; new_bbox.Y.Min 32767; new_bbox.X.Max -32768; newbbox.Y.Max -32768; We are now ready to loop through the data from both regions. Notice that we only keep looping whilst rl has data outstanding. When rl's data is consumed, then any transitions made by r2 are irrelevant.

while (*rl dat R EOR) ASSERT(*rl dat RNEXT IS Y *rl_dat REOR); ASSERT(*r2_dat R NEXTIS Y |I *r2 dat R_EOR); if (*rldat REOR) min row r2 dat[l]; else if (*r2_dat R EOR) min_row rl dat[l]; else min_row min(rl dat[l], r2 dat[l]); donerl in row FALSE; if (*rldat R EOR rl dat[l] min row) The first region is active on this y coord. We add this row to the current region builder.

if (!Raddrow_toregion_builder(&rl_dat, Ox1, TRUE)) return FALSE; done rl in row TRUE; if (*r2_dat REOR r2_dat[l] min row) The first region is active on this y coord. We add this row to the current region builder.

I:\ELEC\CISRA\OPENSCRN\OSCRN02\appendixl.doc 79 if CIR-add-row-to-region builder(&r2_dat, 0x2, !done-ri-in-row)) return FALSE; *Now, we generate the output row for the input rows.

if (!r-check-rgn-buf-1en(dest-size 2)) return FALSE; r-RgnBuf(dest-size++] R_-NEXTISY; r-RgnBuffdest size++] min _row; rgn -bid -stat R RCurRB->rrbStateData; rgn -bid-dat =RCurRB->rrbRgnData; in run FALSE; for Ci R CurRB->rrb Nels; i 0; m-high *rgn -bid stat RBCURSTATEMASK) RBSTATESIZE; m -low =*rgn-bid stat RBPREVSTATEMASK; if (m lo C &mhh 1 (m-low 1 m-high *We have to emit a run here, if we're not already *in one..

if (lin-run) if (Ir-check rgnbuf-len~dest size 1)) return FALSE; rRgnBuf[dest size++] *rgn bid dat; in run TRUE; new-bbox.X.Min nin(new-bbox.X.Min, *rgn-bid-dat); else if (in-run) *We've come to the end of a run. we output the next element to end it.

if (!r-check rgnbuf-len(dest-size 1)) return FALSE; rRgnBuf[dest -size++] *rgn_bid dat; new-bbox.X.Max =max~new-bbox.X.Max, *rgn bid-dat); in-run FALSE; rgn_bid_stat++; rgn bid dat++; if CrRgnBuf(dest-size 2] RNEXTISY) *We didn't output anything for these input rows. Rewind..

I:\ELEC\Cl SRA\OP EN SCRN\O_SCRNO2\appendixl .doc dest size 2; else if (minrow newbbox.Y.Min) newbbox.Y.Min min row; else if (min row new bbox.Y.Max) new_bbox.Y.Max min row; We've completed constructing the data for the region. Firstly we check to see if we've emitted anything at all. If we have then dest_size must be 0. If it isn't we simply free the region we created and get out, as r2 rl must be empty.

if (destsize 0) return TRUE; We make a copy the constructed data from the permanent buffer to an exactly fitting buffer.

-rgn->rr_RgnData (R_Int *)malloc(++destsize sizeof(R_Int)); if (rgn->rr_RgnData NULL) return FALSE; memcpy(rgn->rr_RgnData, r_RgnBuf, (dest_size 1) sizeof(RInt)); rgn->rr_RgnData[dest_size 1] R_EOR; rgn->rr_RgnDataSize destsize; SASSERT(rgn->rrRgnDataSize 9); Now, copy across the bounding box..

rgn->rr BBox new bbox; Done! We can get out..

99.9 return TRUE; 1 #endif R USE NEW IMP rgrow_freelist This function mallocs and adds R FREE LIST GROWTH SIZE new elements to the front of the region growth free list.

Parameters: None.

Returns: TRUE on success, FALSE on failure.

int r grow_free_list() R_RgnGrowItem *rgi; int i; First, malloc the memory..

rgi (RRgnGrowItem *)malloc R_FREE_LIST GROWTH_SIZE sizeof(R RgnGrowItem) if (rgi NULL) return FALSE; I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendix .doc -81 Now make the whole block of memory into a list..

for (i 0; i R FREE LIST GROWTH SIZE 1; rgi[i].rrgi Next &rgi[i 1]; Now, add it to the front of the free list..

rgi[R_FREE_LISTGROWTHSIZE 1].rrgiNext rfree list; r_free_list rgi; return TRUE; R_add_rowto_region growth_list This function adds a row from a RRegion to a linked list comprised of R_RgnGrowItem structures. "Adding" implies that the linked list is modified such that the state and coordinate information present in the list is updated to take into account the new row just added.

Adding a row has the following properties: If a pixel run in the row does not exist in the list before, it is added and it's current state is tagged with the region to which the row belongs. The previous state is set to 0, indicating that it did not exist before.

If a pixel run in the row did exist before, but it's present state indicates that it came from the other region then the run is retained but it's state is modified to indicate that both regions are .active at this point.

If a pixel run in the row did exist before, and it's present state indicates that the current region then the region is removed and it's state is modified to indicate that the run is now empty.

If a pixel run in the row did exist before, and it's present state indicates that both regions are currently active then the run is retained, but its state is modified to indicate that only the other region is active in this run.

Parameters: row_ptr A R_Int pointer to the row in the region. Used to return the updates row pointer.

rgn_mask A mask for the region the row comes from. Must be either 1 or 2.

first Whether this is the first region to be processed on the current scanline.

Returns: TRUE on success, FALSE on failure.

int R_addrowto region_growth_list R_Int **row_ptr, int rgn_mask, int first R_Int *row; R_RgnGrowItem *rgi; unsigned char rb_prev_run_state; int row_on; row *row_ptr; Skip over the row's y value at the beginning.

ASSERT(*row RNEXT IS Y); row 2; ASSERT(*row RNEXT IS Y *row REOR); I:\ELEC\CISRA\OPENSCRN\O_SCRN02appendix .doc -82- If (rgrowth_list NULL) R_RgnGrowItem **ptrnextptr; The growth list is currently empty. Therefore, we simply convert the input row to the region growth list format..

rowon TRUE; ptr_next_ptr &rgrowth list; while (R_NOT_END OF_ROW(*row)) if (rfree list NULL) if (!r_grow_free_list()) return FALSE; rgi rfree list; *ptr_next_ptr rgi; ptr_next_ptr &rgi->rrgi_Next; r_free_list *ptr_next_ptr; rgi->rrgiRgnData *row; if (rowon) rgi->rrgi_StateData (rgnmask RB STATE SIZE); o e l s e Se. rgi->rrgi_StateData 0; row_on !row_on; row++; *rowptr row; *ptr_next_ptr NULL; return TRUE; R_RgnGrowItem fakeitem; R_RgnGrowItem *prev_rgi; "fakeitem" is used as the head of the list. This is so that we _always have a valid pointer to the previous item in the list. Only the next pointer and state data are initialised, as these are they only elements which will be referenced.

fake_item.rrgi_StateData 0; fake_item.rrgi_Next r_growth_list; prev_rgi &fake_item; if (first) If this is the first row to be added on this particular scanline, then we have to update the existing contents of those elements at the beginning of the growth list which precede (in coords) the first element of the row. "Updating" involves updating the previous state of each element to match the current state. This is because none of the elements were effected by the addition of the new row.

rgi r growth list; while (rgi NULL *row rgi->rrgi_RgnData)

I

#ifndef RB USE LOOKUP rgi->rrgi_StateData (rgi->rrgi StateData RB_CUR_STATE_MASK) (rgi->rrgi_StateData RB STATE SIZE); #else rgi->rrgi_StateData r_shift and_dup[rgi->rrgiStateData] #endif prevrgi rgi; 1:\ELEC\C[SRA\OPENSCRN\O_SCRN2\appendixl.doc -83rgi rgi->rrgi_Next; else This is the second row to be added on this particular scanline.

Therefore, we don't need to update the state of the elements preceding (in coords) the first run of the row to be added, as they have already been updated by the first row to be added on this scanline. We simply skip over the unaffected elements..

rgi r_growth_list; while (rgi NULL *row rgi->rrgi_RgnData) prev_rgi rgi; rgi rgi->rrgi Next; if (rgi NULL) S• We've already exhausted the current growth list. Set the start of the next pixel run to be the max. possible and set the state to be 0.

erb_prev_runstate 0; else We are still within the current growth list bounds. Set up the run info appropriately.

if (rgi rgrowthlist) rb_prev_run_state 0; else elrb_prev_run_state prev_rgi->rrgi_StateData; We can now start merging the elements of the row with the remaining elements of the growth list.

rowon TRUE; while (R NOT END OF ROW(*row)) if (rgi NULL II *row rgi->rrgi_RgnData) This is the only situation in which we actually have to create a new list element. First, we check that we actually have an element in the free list that we can use in the growth list..

if (rfreelist NULL) if growfree list)) return FALSE; prev_rgi->rrgi_Next rfree_list; prev rgi rfreelist; r_freelist rfree_list->rrgi_Next; prev_rgi->rrgi_Next rgi; Now, fill in the data..

prev_rgi->rrgi_RgnData *row; I:\ELEC\GISRA\OP ENSC RN\OSCRNO2\appendix I .doc -84if (first) We are processing the first region. Therefore, we copy the current state of the run to the lowest RB STATE SIZE bits.

#ifndef RB USE LOOKUP prev_rgi->rrgi_StateData (rb_prevrun_state RB_CUR_STATEMASK) (rbprev_run_state RBSTATE SIZE); #else prev_rgi->rrgi StateData rshiftand dup[rb prevrunstate]; #endif else We are processing the second region. Therefore, the state data has already been copied to the previous state area so we just copy the state.

prevrgi->rrgi_StateData rbprev_runstate; Now, if the row for the current region is active at this transition, we xor the region mask with the current contents of the new list item.This gives the desired behaviour of making that region active if it is not there already, but turns it off if it is...

if (row_on) prev_rgi->rrgi StateData (rgn_mask RB STATESIZE); We now move onto the next row element.

row++; row on !row on; continue; If the current row transition point is equal in x position to the current list item's transition point, we advance the row counter to the next position.

if (*row rgi->rrgiRgnData) row++; row on !row on; We update the current list item to deal with the affects of the current row run..

rb_prev_run_state rgi->rrgi_StateData; if (first) #ifndef RB USE LOOKUP rgi->rrgi_StateData (rb prevrun_state RB_CUR STATE MASK) (rb prev_run_state RB_STATE SIZE); #else rgi->rrgi_StateData r_shiftand_dup[rb_prev run_state]; #endif if (!rowon) rgi->rrgi_StateData (rgnmask RB_STATE SIZE); We now move onto the next element in the list..

prevrgi rgi; I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendixl.doc rgi rgi->rrgi_Next; Now, simply update the remainder of the elements in the list..

if (first) while (rgi NULL) #ifndef RB USE LOOKUP rgi->rrgi StateData (rgi->rrgi_StateData RB_CUR_STATEMASK) (rgi->rrgiStateData RB_STATESIZE); #else rgi->rrgiStateData r_shiftand_dup[rgi->rrgiStateData]; #endif rgi rgi->rrgi_Next; Now copy "fake_item"'s next pointer to r_growth_list, as it will have changed if something was added to the head of the list..

r_growth_list fake_item.rrgi_Next; Update the return pointer to the region data..

S *row_ptr row; Everything should now be OK..

return TRUE; #ifdef R USE NEW IMP r union test table A 16-int lookup table which when provided with an unsigned char of the following form xxyy, will provide evaluate the key state transition test of the union construction loop.

Note that R STATE SIZE must be 2 for this lookup table to work.

int r_union_test_table[16] 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 R union This function inits a RRegion structure to represent the union of it's two arguments.

Parameters: rgn The R_Region to be initialised.

rl A R_Region ptr representing the first region.

r2 A R_Region ptr representing the second region.

Returns TRUE on success, FALSE on failure.

int R union R_Region *rgn, I:\ELEC\CISRA\OPENSCRN\O_SCRN\appendix .doc 86 R-Region *rl, R_Region *r2 R It *rldat; R It *r2_dat; int overlap-flags; union-tot++; if (!BB-intersect-test(&rl->rrBBox, &r2->rrBBox, &overlap flags)) The bounding boxes don't intersect. This means we can do the union very easily, simply by copying data from the two regions.

We malloc a new region data array of size rl->rr RgnDataSize r2->rrRgnDataSize 1. This is the maximum possible size of resulting region. Not all of this memory will be utilised if the two regions being combined have rows with the same y coordinate (R_-NEXTISY marker is not duplicated).

*rgn->rrRgnDataSize rl->rrRgnDataSize r2->rrRgnDataSize -1; rgn->rrRgnData (R-Int *)malloc(rgn->rrRgnDataSize sizeof CRInt)) 2 if (rgn->rrRgnData NULL) :*set*return

FALSE;

*Now, check to see if the regions overlap in if (I (overlap flags BBINTERSECT OVERLAP Y)) The regions don't overlap in y. We simply copy one region *and then another into the array we malloced. We ensure *that rl points to the region with the smallest y coordinate.

if (r2->rrBBox.Y.Min rl->rr BBox.Y.Min) R Region *tmp; tmp =ri; **rl =r2; r2 =tmp; memcpy rgn- >rrRgnData, r >rr-RgnData, (rl->rrRgnDataSize *sizeof(R-lInt) memcpy rgn->rrRgnData rl->rrRgnDataSize -1, r2 ->rrRgnData, r2->rrRgnDataSize sizeof(R-lInt) ASSERT(rgn->rrRgnData[rgn->rrRgnDataSize R EOR); else R-Int *rl_tnp; R-lInt *r2_tmp; R-Int *dest; R -lint min-row; int ri done; mnt ri consumed; int r2 consumed; I:\ELEC\CISRA\OPENSCRN\OSCRNO2\appendix L doc -87int numwritten; The bboxes overlap in y but not in x. We simply go row by row through each region and memcpy the individual rows as appropriate. We ensure that rl points to the region with the smallest x coordinate.

if (r2->rr BBox.X.Min rl->rr BBox.X.Min) RRegion *tmp; tmp rl; rl r2; r2 tmp; rldat rl->rrRgnData; r2_dat r2->rr_RgnData; dest rgn->rrRgnData; rgn->rr_RgnDataSize 0; rl consumed 0; r2 consumed 0; while (*rldat R_EOR *r2_dat R_EOR) ASSERT(*rl dat R NEXT IS Y); ASSERT(*r2 dat R NEXT IS Y); min row min(rl_dat[l], r2_dat[l]); rl done FALSE; if (rl_dat[l] minrow) We need to emit rl. We therefore need to find where the next row (if any) starts. When we do this we recall that a y value _must be followed by at least two x values..

rltmp rl_dat 4; while (*rl_tmp RNEXT_IS_Y *rl_tmp R_EOR) rl_tmp++; num_written rltmp rl_dat; memcpy(dest, rldat, numwritten sizeof(R Int)); dest numwritten; rl consumed numwritten; Srgn->rr_RgnDataSize num_written; rl dat rl_tmp; rldone TRUE; if (r2_dat[l] min row) We need to emit rl. We therefore need to find where the next row (if any) starts. When we do this we recall that a y value _must be followed by at least two x values. If rl's current row has already been emitted for this y value, we do not emit the RNEXT IS Y marker or the y value itself.

if (rl_done) r2_dat 2; r2_tmp r2 dat 2; r2_consumed 2; else r2_tmp r2_dat 4; while (*r2_tmp R_NEXTISY *r2_tmp R_EOR) r2_tmp++; num_written r2_tmp r2_dat; I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appcndix .doc -88memcpy(dest, r2_dat, numwritten sizeof(R_Int)); dest num written; r2_consumed numwritten; rgn->rr_RgnDataSize num written; r2_dat r2_tmp; if (*rldat REOR) rl is the last region left standing. We memcpy the remainder of the region (including the R EOR marker) to the destination.

ASSERT(r2_consumed r2->rrRgnDataSize 1); memcpy dest, rl_dat, (rl->rr_RgnDataSize rl_consumed) sizeof(R_Int) rgn->rr_RgnDataSize (rl->rr_RgnDataSize rl_consumed); else r2 is the last region left standing. We memcpy the remainder of the region (including the R EOR marker) to the destination.

ASSERT(rl_consumed rl->rr_RgnDataSize 1); memcpy dest, r2 dat, (r2->rr_RgnDataSize r2 consumed) sizeof(R Int) rgn->rr_RgnDataSize (r2->rr_RgnDataSize r2 consumed);

ASSERT

rgn->rr RgnData[rgn->rr_RgnDataSize 1] R EOR

I

else R_Int min row; int destsize; R_RgnGrowItem *rgi; R_RgnGrowItem *rgi_tail; int in run; int done rl in row; union full++; The two regions _do_ overlap in x _and_ y. We therefore have to do a bit more work in calculating the union of the two regions. We use the a list of RRgnGrowItem structs to store state regarding the currently active regions as we progress through the rows of each region. After any rows relevent to a y-coord are added to the list, we examine the state of each pixel run in the list. If the addition of the row(s) for the y-coord have caused a transition to or from 0, then the pixel run is emitted.

I:\ILE\CISRA\OPENSCRN\OSCRNO 2\appndix .doc -89rl_dat rl->rr_RgnData; r2_dat r2->rr_RgnData; destsize 0; We are now ready to loop through the data of both regions.

We continue building the new region whilst there is data remaining in either of the two regions.

while (*rldat REOR *r2_dat R EOR) ASSERT(*rl dat RNEXT IS Y *rl dat R EOR); ASSERT(*r2_dat RNEXT_IS Y *r2_dat REOR); if (*rldat REOR) min row r2 dat[l]; else if (*r2_dat REOR) min row rl dat[l]; else min row min(rl dat[l], r2 dat[l]); done rl in row FALSE; if (*rldat REOR rldat[l] min row) The first region is active on this y coord. We add this row to the current region builder.

if (!R_add_rowto_region_growthlist(&rl_dat, Oxl, TRUE)) return FALSE; o° ~done rl in row TRUE; if (*r2_dat R EOR r2 dat[l] min row) r The first region is active on this y coord. We add this row to the current region builder.

if (!R_add_rowtoregion_growth list(&r2_dat, 0x2, !done rl in row)) return FALSE; S* Now, we generate the output row for the input rows.

if (!rcheckrgnbuf_len(destsize 2)) return FALSE; r_RgnBuf[destsize++] R NEXT IS Y; r_RgnBuf[dest_size++] min_row; inrun FALSE; #ifndef R NEW IMP CONSTRUCTION LOOP for (rgi rgrowth_list; rgi NULL; rgi rgi->rrgi_Next) #if 0 if rgi->rrgi_StateData 0 (rgi->rrgi_StateData RB CUR STATE MASK) 0

II

(rgi->rrgi_StateData RB_PREV STATE MASK) 0 #else if (runiontest_table[rgi->rrgi_StateData]) #endif I:\ELEC\CISRA\OPENSCRN\O_SCRN02\appendix .doc 90 We have to emit a run here, if we're not already in one..

if (tin-run) if (!r_check_rgn-buf-len(dest-size 1)) return FALSE; r_RgnBuf~dest -size++] =rgi->rrgiRgnData; in-run TRUE; else if (in-run) *We Ive come to the end of a run. We output the next element to end it.

if (!r-check rgn buf len(dest-size 1)) return FALSE; r_RgnBuf~dest size++] rgi->rrgiRgnData; inrun FALSE; *Not efficient, get rid of it..

if (rgi->rrgi Next NULL) rgi tail =rgi; 4es rgi =rgrowth list; rgi tail rgi; while (rgi NULL !r -union-test-tablefrgi->rrgi_StateData]) rgi rgi->rrgiNext;while (rgi NULL) if (!r-check rgnbuf-len(dest-size 2)) return FALSE; r-RgnBuf [destsize++] rgi->rrgiRgnData; do rgi rgi->rrgi -Next; while (rgi !=NULL &&r-union-test-table~rgi->rrgi StateData]) rgi tail rgi; rRgnBuf[dest-size++] rgi->rrgiRgnData; do rgi rgi->rrgi Next; while (rgi !=NULL !r-union-test table~rgi->rrgi StateData] 4endif if (rRgnBuf(dest-size 2) R NEXTISY) *We didn't output anything for these input rows. Rewind..

dest size 2; Now, we've completed using the growth list for constructing this region. Therefore, we add it to the front of the free list, to I:\ELEC\CISRA\OPENSCRN\OSCRNO2\appendixl .doc -91 be re-used later.

#ifdef R NEW IMP CONSTRUCTIONLOOP while (rgi_tail->rrgi_Next NULL) rgi_tail rgi_tail->rrgi_Next; #endif rgi_tail->rrgi_Next r_free_list; r_freelist rgrowth_list; r_growth_list NULL; We've completed constructing the data for the region. We make a copy the constructed data from the permanent buffer to an exactly fitting buffer.

rgn->rr_RgnData (R Int *)malloc(++destsize sizeof(R_Int)); if (rgn->rr_RgnData NULL) return FALSE; memcpy(rgn->rr_RgnData, r_RgnBuf, (dest_size 1) rgn->rr_RgnData[dest_size 1] R_EOR; rgn->rr_RgnDataSize dest_size; ASSERT(rgn->rr_RgnDataSize 9); sizeof(RInt)); We now do a bounding box union of the two component bboxes and place the result in the new region.

BB_union(&rl->rr BBox, &r2->rr BBox, &rgn->rrBBox); Done! We can get out..

return TRUE; Runion_equals This function basically implements a rl union= r2 type operation. Ie rl union r2 is calculated and the result returned in rl.

Paramete

I

I

Returns: 1 rs: 1 A pointer to an RRegion. This represents the first half of the union, and is also used to return the eventual result.

A pointer to an RRegion. This represents the second half of the union.

TRUE on success, FALSE on failure.

int R_union_equals R_Region *rl, R_Region *r2 R_Region new_rgn; If (rl->rr_RgnData NULL) return R_init region_with_region(rl, r2); if union(&new rgn, rl, r2)) return FALSE; R_empty region(rl) *rl newrgn; return TRUE; I:\ELEC\CSRA\OPENSCN\OSCRN\appendix .doc -92r intersection test table A 16-int lookup table which when provided with an unsigned char of the following form xxyy, will provide evaluate the key state transition test of the intersection construction loop.

Note that R_STATE_SIZE _must_ be 2 for this lookup table to work.

int rintersection test table[16] 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0 Rintersection This function inits a R_Region structure to represent the intersection of it's two arguments.

r Parameters: rgn rl r2 Returns

TRUE

A R_Region ptr to the R_Region structure to be initialised.

A RRegion ptr representing the first region.

A R_Region ptr representing the second region.

E on success, FALSE on failure.

int R intersection R_Region R_Region R_Region R_Int R Int int inttot++; *rgn, *rl, *r2 *rldat; *r2 dat; overlap_flags; rgn->rr_RgnData NULL; if (!BBintersect test(&rl->rr BBox, &r2->rr_BBox, &overlap_flags)) The bounding boxes don't intersect. This means that the regions don't intersect. Therefore, we simply set rgn->rr_RgnData to NULL (signifying an empty region) and get out..

return TRUE; R_Int int R_RgnGrowItem R_RgnGrowItem int int IntXYMinMax min row; destsize; *rgi; *rgi_tail; in_run; done rl in row; new bbox; int full++; The two regions _do_ overlap in x and y. We therefore have to do a bit more work in calculating the intersection of the two regions. We use the R_RegionBuilder struct to store state regarding the currently active regions as we progress through I:TU LEC\CISROPEN\OSCRN\OSCRN2\appendix .doc -93the rows of each region. After any rows relevent to a y-coord are added to the region builder, we examine the state of each pixel run in the region builder. If the addition of the row(s) for the y-coord have caused a transition to or from 0x3, then the pixel run is emitted.

Initialise the new_bbox structure for determining the new bounding box.

newbbox.X.Min RINTMAXVALUE; new_bbox.Y.Min RINTMAX_VALUE; newbbox.X.Max RINT MINVALUE; new_bbox.Y.Max R INT_MIN_VALUE; The next thing we do is ensure the current region builder is empty, and set up pointers into the region data of the two regions.

rl_dat rl->rr_RgnData; r2_dat r2->rrRgnData; destsize 0; We are now ready to loop through the data from both regions. Notice S* that we only keep looping whilst _both_ regions have some data left to give. As soon as either of the region's data has been exhausted, then we stop as the intersection region has already been calculated and is sitting in the rgn_buf.

while (*rldat R EOR *r2 dat R EOR) :o ASSERT(*rl dat RNEXT IS Y *rl_dat R EOR); ASSERT(*r2_dat R NEXT IS Y *r2_dat REOR); If (*rl dat R_EOR) S" min row r2_dat[l]; else if (*r2_dat R EOR) else minrow rl dat[l]; else minrow min(rldat[l], r2_dat[l]); done rl in row FALSE; if (*rldat R_EOR rldat[l] min row) The first region is active on this y coord. We add this row to the current region builder.

if (!R_add_row_toregion growth_list(&rl_dat, Oxl, TRUE)) return FALSE; done rl in row TRUE; if (*r2_dat REOR r2_dat[l] min row) The first region is active on this y coord. We add this row to the current region builder.

if (!R_addrowtoregion_growth_list(&r2_dat, 0x2, !done rl in row)) return FALSE; Now, we generate the output row for the input rows.

if (!r_checkrgn_buf_len(dest_size 2)) return FALSE; r_RgnBuf[destsize++] R_NEXT_ISY; r_RgnBuf[destsize++] minrow; in run FALSE; I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendix .doc 94 #ifndef RNEW_-IMP_-CONSTRUCTION_-LOOP for (rgi rgrowth-list; rgi NULL; rgi rgi->rrgiNext) ftif 0 if rgi->rrgiStateData (3 1 (3 RB_STATESIZE)) (rgi->rrgi StateData RB PREV STATEMASK) ==3 (rgi->rrgiStateData RBCURSTATEMASK) (3 RBSTATESIZE) #~else if (r-intersection-test-table[rgi->rrgiStateData]) #endif We have to emit a run here, if we're not already in one..

if (!in-run) if check rgnbuf len(dest size 1)) return FALSE; rRgnBuf (dest -size++] rgi->rrgiRgnData; *in run TRUE; new-bbox.X.Min min(new-bbox.X.Min, rgi->rrgiRgnData); else toendit.if (in-run) *We've come to the end of a run. We output the next element if (!r-check rgnbuf-len(dest-size 1)) return FALSE; rRgnBuf[dest -size++] rgi->rrgiRgnData; new-bbox.X.Max max(new-bbox.X.Max, rgi->rrgiRgnData); in-run FALSE; *Not efficient, get rid of it..

if (rgi->rrgiNext NULL) rgi tail rgi; 4else rgi =rgrowth -list; rgi tail rgi; while (rgi NULL !r-intersection-test tahlefrgi->rrgi StateData]) rgi rgi->rrgiNext; while (rgi !=NULL) if (!r-check rgnbuf-len(dest size 2)) return FALSE; rRgnBuf[dest -size++] rgi->rrgiRgnData; new-bbox.X.Min min(new-bbox.X.Min, rgi->rrgiRgnData); I:\ELEC\CI1SRA\0PENSCRN\O-SCRN02\appendixI .doc do rgi rgi->rrgi_Next; }while (rgi NULL r_intersection_test_table[rgi->rrgi_StateData]); rgi_tail rgi; r_RgnBuf[dest_size++] rgi->rrgi_RgnData; new_bbox.X.Max max(new_bbox.X.Max, rgi->rrgiRgnData); do rgi rgi->rrgi_Next; }while (rgi NULL !r_intersection_test_table[rgi- >rrgi_StateData]); #endif if (r_RgnBuf[dest_size 2] RNEXT IS Y) We didn't output anything for these input rows. Rewind..

destsize 2; else if (min row new bbox.Y.Min) new bbox.Y.Min min row; else if (min row newbbox.Y.Max) new bbox.Y.Max minrow; Now, we've completed using the growth list for constructing this region. Therefore, we add it to the front of the free list, to be re-used later.

#ifdef R NEW IMP CONSTRUCTION LOOP while (rgi_tail->rrgiNext NULL) rgi_tail rgi_tail->rrgiNext; #endif rgi_tail->rrgi Next rfreelist; r_free_list r_growth_list; r_growthlist NULL; We've completed constructing the data for the region. Firstly we check to see if we've emitted anything at all. If we have then dest_size must be 0. If it isn't we simply free the region we created and get out, as the regions don't really intersect, in spite of their intersecting bounding boxes.

if (destsize 0) return TRUE; We make a copy the constructed data from the permanent buffer to an exactly fitting buffer.

rgn->rr RgnData (R_Int *)malloc(++destsize sizeof(R_Int)); if (rgn->rrRgnData NULL) return FALSE; memcpy(rgn->rr_RgnData, r_RgnBuf, (destsize 1) sizeof(R Int)); rgn->rr_RgnData[dest_size 1] R_EOR; rgn->rr_RgnDataSize dest_size; ASSERT(rgn->rrRgnDataSize 9); Now, copy across the bounding box.. Before we do this, we subtract 1 from X.Max and Y.Max because of the region format.

I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendixl .doc -96new bbox.X.Max--; new bbox.Y.Max--; rgn->rr_BBox newbbox; Done! We can get out..

return TRUE; r difference test table A 16-int lookup table which when provided with an unsigned char of the following form xxyy, will provide evaluate the key state transition test of the difference construction loop.

Note that R_STATE_SIZE _must be 2 for this lookup table to work.

int r difference_test_table[16] 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0 R difference This function inits a RRegion structure to represent the difference of it's two arguments. It essentially calculates rl r2 Parameters: rgn A R_Region ptr representing the RRegion to be inited.

rl A R_Region ptr representing the first region.

r2 A R_Region ptr representing the second region.

Returns TRUE on success, FALSE on failure.

int R difference R_Region *rgn, R_Region *rl, R_Region *r2 R Int *rl dat; R_Int *r2_dat; int overlap flags; difftot++; rgn->rr_RgnData NULL; if (!BB_intersect_test(&rl->rr_BBox, &r2->rr_BBox, &overlap flags)) The bounding boxes don't intersect. This means that rl r2 simply equals rl. We make a copy of the relevant bits and get out..

rgn->rr_BBox rl->rr_BBox; rgn->rr_RgnDataSize rl->rr_RgnDataSize; rgn->rr_RgnData (R_Int *)malloc(rl->rr_RgnDataSize sizeof(RInt)); if (rgn->rr_RgnData NULL) return FALSE; I:\ELEC\CISRA\OPENSCRN\O_SCRN2\appendixl .doc -97memcpy rgn->rr_RgnData, rl->rr_RgnData, rl->rr RgnDataSize sizeof(R_Int) return TRUE; R_Int min row; int dest_size; R_RgnGrowItem *rgi; R_RgnGrowItem *rgi_tail; int inrun; int done rl in row; unsigned char m high; unsigned char m low; IntXYMinMax new_bbox; difffull++; The two regions do_ overlap in x and y. We therefore have to do a bit more work in calculating the difference of the two regions. We use the RRegionBuilder struct to store state e regarding the currently active regions as we progress through the rows of each region. After any rows relevent to a y-coord are added to the region builder, we examine the state of each pixel run in the region builder. If the addition of the row(s) for the y-coord have caused the following transitions rl 0 0 r2 rl r2 r2 r2 rl r2 then the relevent runs are emitted. Firstly, though, we ensure the current region builder is empty, and set up pointers into the region data of the two regions.

rl_dat rl->rrRgnData; °r2_dat r2->rr RgnData; dest size 0; S. Initialise the newbbox structure for determining the new bounding box.

newbbox.X.Min 32767; newbbox.Y.Min 32767; new_bbox.X.Max -32768; new_bbox.Y.Max -32768; We are now ready to loop through the data from both regions. Notice that we only keep looping whilst rl has data outstanding. When rl's data is consumed, then any transitions made by r2 are irrelevant.

while (*rl_dat R_EOR) ASSERT(*rl dat R NEXT IS Y *rl_dat R_EOR); ASSERT(*r2_dat R NEXT IS Y *r2dat R EOR); if (*rldat REOR) min row r2 dat[l]; else if (*r2_dat R EOR) min row rl dat[l]; else min row min(rl dat[l], r2 dat[l]); done rl in row FALSE; if (*rldat R EOR rl_dat[l] min row) I:\ELEC\CISRA\OPENSCRN\OSCRNO\appendix I .doc -98- The first region is active on this y coord. We add this row to the current region builder.

if (!R_add_rowtoregion_growth_list(&rl_dat, Ox1, TRUE)) return FALSE; done rl in row TRUE; if (*r2 dat R EOR r2 dat[l] min row) The first region is active on this y coord. We add this row to the current region builder.

if (!R_add_rowto_region_growth_list(&r2_dat, 0x2, !done rl in row)) return FALSE; Now, we generate the output row for the input rows.

if (!rcheckrgn_buf_len(dest_size 2)) return FALSE; Sr_RgnBuf[dest size++] R NEXT IS Y; r_RgnBuf[dest_size++] min_row; in run FALSE; #ifndef R_NEW_IMP_CONSTRUCTIONLOOP for (rgi r_growth_list; rgi NULL; rgi rgi->rrgiNext) #if 0 im_high (rgi->rrgi_StateData RB_CURSTATE_MASK) RB STATE SIZE; m low rgi->rrgi_StateData RBPREVSTATEMASK; if S(mlow 1 m high 1) (mlow 1 mhigh 1) #else if (r_difference_test_table[rgi->rrgi_StateData]) #endif We have to emit a run here, if we're not already in one..

if (!inrun) if (!r_check_rgn_buf_len(destsize 1)) return FALSE; r_RgnBuf[destsize++] rgi->rrgi_RgnData; in run TRUE; new_bbox.X.Min min(new_bbox.X.Min, rgi->rrgi_RgnData); else if (in run) We've come to the end of a run. We output the next element to end it.

l:\ELEC\CSRA\OPENSCRN\OSCRNO2\appedix .doc 99 if (!r-check rgnbuf-len(dest-size 1)) return FALSE; rRgnBuf[dest -size++] rgi->rrgiRgnoata; new-bbox.X.Max max(new-bbox.X.Max, rgi->rrgiRgnData); in-run FALSE; *Not efficient, get rid of it..

if (rgi->rrgi -Next NULL) rgi tail rgi; #telse rgi =rgrowth -list; rgi tail rgi; while (rgi !=NULL !r -difference-test-tahle[rgi->rrgi-stateData]) rgi rgi->rrgi -Next; so:. while (rgi NULL) if (Ir-check rgnbuf_len(dest-size 2)) return FALSE; rRgnBuf [dest size++] rgi->rrgiRgnuata; new -bbox.X.Min min(new-bbox.X.Min, rgi->rrgiRgnData); do *SOS rgi rgi->rrgi_Next; while (rgi NULL r-difference-test-table[rgi->rrgiStateoata]); rgi tail =rgi; rRgnBuf[dest -size++] rgi->rrgiRgnData; new bbox.X.Max max(new-bbox.X.Max, rgi->rrgiRgnData); a* do are:** rgi rgi->rrgi -Next; while (rgi 1= NULL !r-difference-test_table[rgi->rrgiStateData]); 004*. fendif if (rRgnBuf[dest-size 2] RNEXTISY) 4* *We didn't output anything for these input rows. Rewind..

dest-size 2; else if (min-row new-bbox.Y.Min) new -bbox.Y.Min mm row; else if (min row new bbox.Y.Max) new-bbox.Y.Max min-row; Now, we've completed using the growth list for constructing this region. Therefore, we add it to the front of the free list, to be re-used later.

4ifdef R -NEW IMP CONSTRUCTIONLOOP while (rgi_tail->rrgi -Next NULL) rgi tail rgi_tail->rrgi_Next; 4endif rgi_tail->rrgiNext r -free -list; r-free-list =rgrowth-list; r_growth-list =NULL; *We've completed constructing the data for the region. Firstly 1:\ELEC\C ISRA\OPENSCRN\O_SCRN2appendix .doc 100 we check to see if we've emitted anything at all. If we have then dest -size must be 0. If it isn't we simply free the region we created and get out, as r2 ri must be empty.

if (dest-size 0) return TRUE; We make a copy the constructed data from the permanent buffer to an exactly fitting buffer.

rgn->rr-RgnData =(R-Int *)malloc(++dest-size sizeof(R-lot)); if (rgn->rr_RgnData ==NULL) return FALSE; memcpy(rgn->rrRgnData, rRgnBuf, (dest size *sizeof(R-Int)); rgn->rr-RgnData[dest size 1) 1] REQR; rgn->rr-RgnDataSize =dest size; ASSERT(rgn->rrRgnDataSize 9); *Now, copy across the bounding box..

rgn->rrBBox new-bbox; *Done! We can get out..

return TRUE; #tendif R USE NEWIMP *R-compare *This function compares two regions and determines if they are the same.

*Parameters: *rgnl The first R-Region.

*rgn2 The second R-Region.

*Returns: *TRUE if they are the same, FALSE if they aren't.

int R compare R_Region *rgnl, R_Region *rgn2 *If their region data sizes don't agree, then they aren't the same.

if (rgnl->rrRgnDataSize rgn2->rr_RgnDataSize) return FALSE; if memcmp rgnl ->rr-RgnData, rgn2 rr -RgnData, rgnl->rr-RgnDataSize sizeof(R-lInt) return TRUE; return FALSE; I:\ELEC\CI SRAMOP ENSC RN\O_SCRNO2append ix Ldoc 101 r check rect buf len This function checks to see if the static rectangle buffer is large enough. If it isn't then it is reallocated to make it large enough.

Parameters: size The required size of the rRectBuf array.

Returns: TRUE on success, FALSE on failure.

static int r check rect buf len int size ASSERT(size 0); if (size rRectBufSize) int newbuf size; IntXYMinMax *newbuf; new buf size max(size, r RectBufSize 2); new buf (IntXYMinMax *)malloc (newbuf size sizeof(IntXYMinMax) if (new buf NULL) return FALSE; if (r_RectBuf NULL) memcpy(new_buf, r_RectBuf, r_RectBufSize sizeof(IntXYMinMax)); free(rRectBuf); r RectBuf new buf; r RectBufSize new buf size; return TRUE; #ifndef R USE NEW IMP R_rects_from_region This function returns a group of non-overlapping rectangles which together constitute the region. The group of rectangles returned is currently non-optimal as the function uses the R_RegionBuilder structure to store state. A more specific data structure will be required to make the rectangles produced more optimal.

Paramet Returns ers: rgn The region from which a rectangle array is required.

rects A pointer to a pointer to a IntXYMinMax structure. Used to return the array.

numrects A pointer to an int. Used to return the number of elements in the array.

static_ok This boolean arg is passed as TRUE if a pointer to the rRectBuf is sufficient. This is TRUE if usefulness of the rectangle data obtained ends before the next call to R_rectsfrom_region (for any region). FALSE is passed if a newly malloced copy is required. Basically is TRUE is passed the pointer returned must not be freed.

TRUE on success, FALSE on failure.

int R_rectsfrom region I:\ELEC\CISRA\OPEN SCRN\OSCRNO2\appendix .doc -102- R_Region *rgn, IntXYMinMax **rects, int *numrects, int static ok R_Int *rgn_data; int dest index; int prev_y; int prevx; unsigned char *rgn_bld_stat; R_Int *rgnblddat; int i; int inrun; Give "nice" defaults for return stuff in cause we fail..

*rects NULL; *numrects 0; We grab a pointer to the region data for the region and ensure that the current region builder is empty..

*1 rgn data rgn->rrRgnData; if (rgn data NULL) This is an empty region.. Get out..

return TRUE; ASSERT(*rgn_data R_NEXTISY); SR CurRB->rrb Nels 0; We add the first row of the region to the region builder. We also store the y-coord of this first row.

o* prev_y rgn_data[l]; if (!R_add_row_to_region_builder(&rgn_data, Oxl, TRUE)) return FALSE; ASSERT(*rgndata RNEXT IS Y); ASSERT(*rgn_data

R_EOR);

We are now in a position to loop through the data of the region.

We continue until the region data runs out. Basically, we output the runs in the current region builder out as rectangles. Using x-coords from the region builder and y coords of the rows. Then, we add then next row to the region builder.

destindex 0; while (*rgn_data R EOR) ASSERT(*rgn data R_NEXT_ISY); rgnbldstat R CurRB->rrbStateData; rgnbld_dat R_CurRB->rrb_RgnData; in run FALSE; for (i RCurRB->rrb_Nels; i 0; if ((*rgn bldstat RBCUR_STATEMASK) 0) We have to emit a run here, if we're not already in one..

if (!in_run) prev *rglddat prev_x *rgnblddat; l:\ELEC\CISRA\OPENSCRN\O_SCRN2\appendix .doc -103else inrun TRUE; (in run) We've come to the end of a run. We output the rectangle right here..

if (!rcheckrectbuflen(destindex 1)) return FALSE; r_RectBuf[dest_index].X.Min prev_x; r RectBuf[dest_index].Y.Min prev y; r_RectBuf[dest_index].X.Max *rgn_bld_dat 1; r RectBuf[destindex++].Y.Max rgndata[l] 1; inrun FALSE; rgn_bld_stat++; rgn_blddat++; Now, we advance onto the next row..

prev_y rgn_data[l]; if (!Raddrow to region_builder(&rgn data, Oxl, TRUE)) return FALSE; Ok, we have the array of rectangles sitting around. If staticok is TRUE then we simply set the return pointers and get out.

Otherwise, we need to malloc a copy of the r RectBuf.

*numrects destindex; if (static ok) *rects r RectBuf; else *rects (IntXYMinMax *)malloc(destindex sizeof(IntXYMinMax)); if (*rects NULL) return FALSE; memcpy(*rects, r RectBuf, dest index sizeof(IntXYMinMax)); return TRUE; #else R_rects_from_region This function returns a group of non-overlapping rectangles which together constitute the region. The group of rectangles returned is currently non-optimal as the function uses the R_RegionBuilder structure to store state. A more specific data structure will be required to make the rectangles produced more optimal.

Parameters: rgn The region from which a rectangle array is required.

rects A pointer to a pointer to a IntXYMinMax structure. Used to return the array.

num_rects A pointer to an int. Used to return the number of elements in the array.

static_ok This boolean arg is passed as TRUE if a pointer to the r RectBuf is sufficient. This is TRUE if usefulness of the rectangle data obtained ends before the next call to I:\ELEC\C SRA\OP EN SCRN\O_SC RNO2\appe ndix .doc 104- R_rects_from_region (for any region). FALSE is passed if a newly malloced copy is required. Basically is TRUE is passed the pointer returned must not be freed.

Returns: TRUE on success, FALSE on failure.

int R_rects_fromregion R_Region *rgn, IntXYMinMax **rects, int *numrects, int static ok R_Int *rgn_data; int dest_index; R_RgnGrowItem *rgi; R_RgnGrowItem *rgi_tail; int prev_y; int prev_x; o. int in run; Give "nice" defaults for return stuff in cause we fail..

*rects NULL; *numrects 0; We grab a pointer to the region data for the region and ensure that the current region builder is empty..

rgn_data rgn->rrRgnData; if (rgn_data NULL) This is an empty region.. Get out..

return TRUE; ASSERT(*rgndata RNEXTISY); We add the first row of the region'to the region builder. We also store the y-coord of this first row.

prev_y rgn_data[l]; if (!R_add_rowtoregion_growth_list(&rgn_data, Oxl, TRUE)) return FALSE; ASSERT(*rgn data R_NEXTIS Y); ASSERT(*rgndata R_EOR); We are now in a position to loop through the data of the region.

We continue until the region data runs out. Basically, we output the runs in the current region builder out as rectangles. Using x-coords from the region builder and y coords of the rows. Then, we add then next row to the region builder.

destindex 0; while (*rgn_data REOR) ASSERT(*rgn_data R NEXT IS Y); in run FALSE; for (rgi r_growth_list; rgi NULL; rgi rgi->rrgi Next) if ((rgi->rrgi StateData RBCUR STATE MASK) 0) We have to emit a run here, if we're not already in one..

I:\ELEC\CISRA\OPENSCRN\O_SCRNO2\appendixl.doc 105 if (!in-run) prev -x rgi->rrgiRgnData; in-run TRUE; else if (in-run) We've come to the end of a run. We output the rectangle right here..

if (!r-check-rect-buf-len(dest-index 1)) return FALSE; r_-RectBuf[dest -index] .X.Min prev-x; r_-RectBuf[dest -index] .Y.Min prevy; r -RectBuf[dest -index] .X.Max rgi->rrgiRg3nData -1; rRectBuf (dest-index++].Y.Max =rgn-data[i] 1; in-run FALSE; *Not efficient, get rid of it..

if (rgi->rrgiNext NULL) rgi tail rgi; *Now, we advance onto the next row..

prev -y rgndata(l]; if -add -row -to region growth list (&rgn data, 0x1, TRUE)) return FALSE; Now, we've completed using the growth list for constructing the rect list. Therefore, we add it to the front of the free list, to be re-used later.

rgi tail->rrgiNext r -free -list; r -free -list =rgrowth-list; rgrowth-list =NULL; Ok, we have the array of rectangles sitting around. If static ok is TRUE then we simply set the return pointers and get out.

Otherwise, we need to malloc a copy of the rRectBuf.

*num -rects dest-index; if (staticok) "rects rRectBuf; else "*rects (IntxYminmax *)malloc(dest index *sizeof(IntXYMinMax)); if (*rects NULL) return FALSE; memcpy(*rects, rRectBuf, dest index sizeof(IntXYMinMax)); return TRUE; #endif 1* RUSENEWIMP *R translate-region l:\ELEC\C1 SRA\OP EN SCRN\O_SC KNO2\appendixl .doc 106 *This function simply translates a region by the delta provided.

*Parameters: rgn A ptr to the delta An IntXY ptr in xand y.

*Returns: Nothing.

void R -translate-region R -Region to be translated.

representing the amount to translate RRegion *rgn, IntXY *delta R-Int *rgn data; BB-translate(&rgn->rr -BBox, delta); rgn data rgn->rrRgnData; for (mnt i 0; i rgn->rr-RgnDataSize 1; if (rgndata[i] RNEXTISY) rgndata[iI delta-z.Y; continue; rgndata[i] delta->X; *R_output region_as_debug string *This function simply outputs a region's data using the debug string *functionality.

*Parameters: rgn name *rgn *Returns: Nothing.

A string used region.

The region to to output a user-defined name for the be output.

void R -output_region_as debug string char *rgn name, RRegion *rgn char buffer[128] int index; int line-len; sprintf(buffer, "\n+Rgn rgn name); OutputDebugString(buffer); if (rgn NULL) sprintf(buffer, %s (Empty)\n", rgn name); OutputDebugString (buffer); return; sprintf buffer, I:\ELEG\CISRA\OPENSCRN\O_SCRNO2\apperidixl .doc 107 rgn->rrBBox.X.Min, rgn->rrBBox.Y.Min, rgn->rrBBox.X.Max, rgn->rrBBox.Y.Max OutputDebugSt ring (buffer); sprintf(buffer, rgn->rrRgnDataSiz OutputDebugString (buffer); sprintf(buffer, .1) OutputDebugString (buffer); for (index 0; index rgn->rrRgnDataSize; index++) e) gn->rrRgnData[++index]); if (rgn->rrRgnData [in sprintf (buffer, line len strien OutputDebugString dex] RNEXTISY) (buffer)> 1, (buffer); a a. a else else if (rgn->rr-RgnData[index] ==R_EOR) sprintf(buffer, rgn-nane); OutputDebugString (buffer); sprintf(buffer, 11%3d, 11, rgn->rrRgnData~index]); if (strlen(buffer) line-len OutputDebuggtring(-\nl 11) line-len strlen(-I\nI 1) OutputuebugString(buffer); line len strlen(buffer); 4def mne NUMITERATIONS int R-test-new region_arithmetic() R_Region R_Region R_Region RRegion R_Region R_Region IntXYMinMax int IntXY char unsigned long unsigned long rgnl; rgn2; rgn3; rgn4; rgns; rgn6; rect; 1; delta; buf [256]; ticks new; ticks-old; W~i 0 Union Test.

ticks -new =GetTickCounto; rect.X.Min rect.Y.Min rect.X.Max =100; rect.Y.Max =100; if (!R-imit_region with rect( &rgnl, &rect)) return FALSE; rect.X.Min rect.Y.Min 1:\ELEC\CJSRA\OPENSCRN\RO_scRN02\appendixI Ldoc 108 rect.X.Max 120; rect.Y.Max 120; if (!R-init region with-rect(&rgn2, &rect)) return FALSE; if (!R-union list equals(&rgnl, &rgn2)) return FALSE; delta.X delta.Y for (i 0; i NUN ITERATIONS; R -translate -region(&rgn2, &delta); if (!R-union-list equals(&rgnl, &rgn2)) return FALSE; ticks-new GetTickCount() ticks-new; ticks-old GetTickCount(); rect.X.Min rect.Y.Min rect.X.Max 100; rect.Y.Max 100; if -miit region -with rect(&rgn3, &rect)) return FALSE; *etX.i =.0 rect.X.Min rect.Y.Min 720; *.*.rect.X.Max 120; if (!R-imit region with-rect(&rgn4, &rect)) return FALSE; if -union equals (&rgn3, &rgn4)) return FALSE; *delta.X delta.Y for (i 0; i <NUMITERATIONS; R -translate region(&rgn4, &delta); *if (IR -union -equals(&rgn3, &rgn4)) return FALSE; ticks-old GetTickCount() ticks-old; if (R-compare(&rgnl, &rgn3)) sprintf(buf, "New Old Region Implementations match.\n"); else sprintf(buf, "New Old Region Implementations DO NOT match.\n"l); OutputDebugString (buf); sprintf(buf, "Union Timings New=%d vs Old=%d\n", ticks-new, ticks-old); OutputDebugString (buf); output region as debug string("New Region Description", &rgnl); output region as debug string ("Old Region Description", &rgn3); *Intersection Test.

R-empty region(&rgn2); R-empty region(&rgn4); rect.X.Min rect.Y.Min rect.X.Max 120; rect.Y.Max 120; if (!R-imit region-with-rect(&rgn2, &rect)) return FALSE; delta.X delta.Y for (i 0; i NUMITERATIONS; if (!R-intersection-list(&rgns, &rgnl, &rgn2)) return FALSE; I:\ELEC\CISRA\OPENSCRN'\0_SCRNO2\appendix L doc 109 if O!R -intersection(&rgn6, &rgn3, &rgn2)) return FALSE; if (!R-compare(&rgnS, &rgn6)) sprintf(buf, "New Old Region Implementations DO NOT match.\n"); OutputDebugString (buf); Rempty region R-empty region (&rgn6); R-translate region(&rgn2, &delta); ticks-new GetTickCounto; R_empty region(&rgn2); rect.X.Min rect.Y.Min rect.X.Max 120; rect.Y.Max 120; if (!R-imit_region with-rect(&rgn2, &rect)) return FALSE; delta.X delta.Y for (i 0; i MUM ITERATIONS; .if (IR -intersection_list(&rgns, &rgnl, &rgn2)) ****return FALSE; R-emptyregion R_translate region(&rgn2,&dta ticks-new =GetTickCount() ticks-new; ticks old GetTickCounto; R Rempty region(&rgn2); rect.X.Min rect.Y.Min rect.X.Max 120; rect.Y.Max 120; *if (IR -miit_region -with-rect(&rgn2, &rect)) return FALSE; delta.X delta.Y for (i 0; i NUM ITERATIONS; if -intersection(&rgn6, &rgn3, &rgn2)) return FALSE; R -empty region (&rgn6); R-translate region(&rgn2, &delta); ticks-old GetTickCount() ticks-old; sprintf(buf, "Intersection Timings New=%d vs 0ld=%d\n", ticks-new, ticks-old); OutputDebugString (buf); output region as debug string New Region Description", &rgnl); output region as debug string ("Old Region Description", &rgn3); R_empty region(&rgnl); Rempty~region(&rg3n2); R_empty region(&rgn3); R-empty region(&rgn4); OutputoebugString ('Done! #endif return TRUE; I :\ELEC\CISRA\OPENSCPRN\O_SCPRN2\appendix I .doc

Claims (1)

110- The claims defining the invention are as follows: 1. A method of creating an image, said image to be formed by rendering and compositing at least a plurality of graphical objects, each said object having a predetermined outline, said method comprising the steps of: dividing a space in which said outlines are defined into a plurality regions, each said region being defined by at least one region outline substantially following at least one of said predetermined outlines or parts thereof and being substantially formed by segments of a virtual grid encompassing said space; manipulating said regions to determine a plurality of further regions, wherein each said further region has a corresponding compositing expression; classifying said further regions according to at least one attribute of said graphical objects within said further regions; ~modifying each said corresponding compositing expression according to a 15 classification of each said further region to form an augmented compositing expression for each said further region; and compositing said image using each of said augmented compositing expressions. 2. A method according to claim 1, wherein said attribute is selected from 20 the group consisting of colour, opacity and object outline. 3. A method according to claims 1 or 2, wherein said manipulating said regions comprises applying set operations to said regions. 4. A method according to claim 3, wherein said set operations include difference and/or intersection operations. A method according to any one of the preceding claims, wherein said grid is regularly spaced and preferably orthogonally based. 6. A method according to any one of claims 1 to 4, wherein said grid is irregularly shaped. 7. A method according to any one of claims 1 to 6, wherein the compositing 471440 CFP01423AU Open_scm1 [I:\ELEC\CISRA\OPENSCRN\O_SCRN01]471440.doc:lAD -111- expression is a hierarchically structured representation of the image. 8. A method according to any one of claims 1 to 7, wherein said image is at least in part a pixel-based image. 9. A method according to any one of the preceding claims, wherein a flag is stored to indicate whether data of an object is opaque or ordinary. A method according to claim 9, wherein said compositing expression is optimized based on a value of said flag for contributing objects. 11. A method according to any one of the preceding claims, wherein a S wholly opaque object in said region acts to eliminate one or more objects within said region from said compositing expressions. 12. A method according to any one of the preceding claims, wherein a wholly transparent object in said region eliminates at least itself from said compositing expression. S20 13. A method according to any one of claims 1 to 12, wherein said modifying oo comprises modifying a manner in which said compositing expression is evaluated without modifying said hierarchically structured representation. 14. A method of creating an image, said image to be formed by rendering and compositing at least a plurality of graphical objects, each said object having a predetermined outline, said method comprising the steps of: dividing a space in which said outlines are defined into a plurality regions, each said region being defined by at least one region outline substantially following at least one of said predetermined outlines or parts thereof and being substantially formed by segments of a virtual grid encompassing said space, wherein each object has two region outlines arranged either side of said predetermined outline to thus define three regions for each said object, and wherein each said region has a corresponding compositing expression; classifying said regions according to at least one attribute of said graphical objects within said regions; 471440 CFP01423AU Open_scm0l [I:\ELEC\CISRA\OPENSCRN\O_SCRNOI1 ]471440.doc:lAD -112- modifying each said corresponding compositing expression according to a classification of each said region to form an augmented compositing expression for each said region; and compositing said image using each of said augmented compositing expressions. A method according to claim 14, wherein said attribute is selected from the group consisting of colour, opacity and object outline. 16. A method according to any one of claims 14 or 15, wherein said grid is regularly spaced and preferably orthogonally based. 17. A method according to any one of claims 14 to 16, wherein said grid is irregularly shaped. 18. A method according to any one of claims 14 to 17, wherein said compositing expression is a hierarchically structured representation of the image. 19. A method according to any one of claims 14 to 18, wherein said image is at least in part a pixel-based image. A method according to any one of claims 14 to 19, wherein a flag is stored to indicate whether data of an object is opaque or ordinary. 21. A method according to claim 20, wherein said compositing expression is optimized based on a value of said flag for contributing objects. 22. A method according to any one of claims 14 to 21, wherein a wholly opaque object in said region acts to eliminate one or more objects within said region from said compositing expressions. 23. A method according to any one of claims 14 to 22, wherein a wholly transparent object in said region eliminates at least itself from said compositing expression. 24. A method according to any one of claims 14 to 23, wherein said modifying comprises modifying a manner in which said compositing expression is 471440 CFP01423AU Open_scm1 [I:\ELEC\CISRA\OPENSCRN\O_SCRNOI 1471440.doc:IAD -113- evaluated without modifying said hierarchically structured representation. An apparatus for creating an image, said image to be formed by rendering and compositing at least a plurality of graphical objects, each said object having a predetermined outline, said apparatus comprising: dividing means for dividing a space in which said outlines are defined into a plurality regions, each said region being defined by at least one region outline substantially following at least one of said predetermined outlines or parts thereof and being substantially formed by segments of a virtual grid encompassing said space; manipulating means for manipulating said regions to determine a plurality of further regions, wherein each said further region has a corresponding compositing expression; classifying means for classifying said further regions according to at least one attribute of said graphical objects within said further regions; .oo. modifying means for modifying each said corresponding compositing expression according to a classification of each said further region to form an augmented compositing expression for each said further region; and compositing means for compositing said image using each of said augmented compositing expressions. 26. An apparatus according to claim 25, wherein said attribute is selected from the group consisting of colour, opacity and object outline. 27. An apparatus according to claims 25 or 26, wherein said manipulating aid regions comprises applying set operations to said regions. 28. An apparatus according to claim 27, wherein said set operations include difference and/or intersection operations. 29. An apparatus according to any one of claims 25 to 28, wherein said grid is regularly spaced and preferably orthogonally based. An apparatus according to any one of claims 25 to 28, wherein said grid is irregularly shaped. 471440 CFP01423AU Openscml [I:\ELEC\CISRA\OPENSCRN\O_SCRNO 1]471440.doc: lAD -114- 31. An apparatus according to any one of claims 25 to 30, wherein said compositing expression is a hierarchically structured representation of the image. 32. An apparatus according to any one of claims 25 to 31, wherein said image is at least in part a pixel-based image. 33. An apparatus according to any one of claims 25 to 32, wherein a flag is stored to indicate whether data of an object is opaque or ordinary. 34. An apparatus according to claim 33, wherein said compositing expression is optimized based on a value of said flag for contributing objects. 35. An apparatus according to any one of claims 25 to 34, wherein a wholly o o opaque object in said region acts to eliminate one or more objects within said region from said compositing expressions. 36. An apparatus according to any one of claims 25 to 35, wherein a wholly transparent object in said region eliminates at least itself from said compositing expression. 37. An apparatus according to any one of claims 25 to 36, wherein said modifying comprises modifying a manner in which said compositing expression is evaluated without modifying said hierarchically structured representation. 38. An apparatus for creating an image, said image to be formed by rendering and compositing at least a plurality of graphical objects, each said object having a predetermined outline, said apparatus comprising: dividing means for dividing a space in which said outlines are defined into a plurality regions, each said region being defined by at least one region outline substantially following at least one of said predetermined outlines or parts thereof and being substantially formed by segments of a virtual grid encompassing said space, wherein each object has two region outlines arranged either side of said predetermined outline to thus define three regions for each said object, and wherein each said region has a corresponding compositinj expression; classifying means for classifying said regions according to at least one attribute of 471440 CFP01423AU Open_scml [I:\ELEC\CISRA\OPENSCRN\OSCRNO1 ]471440.doc:IAD -115- said graphical objects within said regions; modifying means for modifying each said corresponding compositing expression according to a classification of each said region to form an augmented compositing expression for each said region; and compositing means for compositing said image using each of said augmented compositing expressions. 39. An apparatus according to claim 38, wherein said attribute is selected from the group consisting of colour, opacity and object outline. An apparatus according to any one of claims 38 or 39, wherein said grid is regularly spaced and preferably orthogonally based. S41. method according to any one of claims 38 to 40, wherein said grid is irregularly shaped. 42. An apparatus according to any one of claims 38 to 41, wherein said compositing expression is a hierarchically structured representation of the image. 20 43.. An apparatus according to any one of claims 38 to 42, wherein said image is at least in part a pixel-based image. 44. An apparatus according to any one of claims 38 to 43, wherein a flag is stored to indicate whether data of an object is opaque or ordinary. An apparatus according to claim 44, wherein said compositing expression is optimized based on a value of said flag for contributing objects. 46. An apparatus according to any one of claims 38 to 45, wherein a wholly opaque object in said region acts to eliminate one or more objects within said region from said compositing expressions. 47. An apparatus according to any one of claims 38 to 46, wherein a wholly transparent object in said region eliminates at least itself from said compositing expression. 471440 CFP01423AU Openscm [I:\ELEC\CISRA\OPENSCRN\O_SCRN01]471440.doc:IAD -116- 48. An apparatus according to any one of claims 38 to 47, wherein said modifying comprises modifying a manner in which said compositing expression is evaluated without modifying said hierarchically structured representation. 49. A computer program product including a computer readable medium having a plurality of software modules for creating an image, said image to be formed by rendering and compositing at least a plurality of graphical objects, each said object having a predetermined outline, said computer program product comprising: dividing module for dividing a space in which said outlines are defined into a plurality regions, each said region being defined by at least one region outline substantially following at least one of said predetermined outlines or parts thereof and being substantially formed by segments of a virtual grid encompassing said space; manipulating module for manipulating said regions to determine a plurality of further regions, wherein each said further region has a corresponding compositing expression; classifying module for classifying said further regions according to at least one attribute of said graphical objects within said further regions; modifying module for modifying each said corresponding compositing expression 20 according to a classification of each said further region to form an augmented compositing expression for each said further region; and compositing module for compositing said image using each of said augmented compositing expressions. 50. A computer program product according to claim 49, wherein said attribute is selected from the group consisting ofcolour, opacity and object outline. 51. A computer program product according to claims 49 or 50, wherein said manipulating said regions comprises applying set operations to said regions. 52. A computer program product according to claim 51, wherein said set operations include difference and/or intersection operations. 53. A computer program product according to any one of claims 49 to 52, wherein said grid is regularly spaced and preferably orthogonally based. 471440 CFP01423AU Open_scm0l [1:\ELEC\CISRA\OPENSCRN\OSCRNOI ]471440.doc: IAD -117- 54. A computer program product according to any one of claims 49 to 52, wherein said grid is irregularly shaped. 55. A computer program product according to any one of claims 49 to 54, wherein said compositing expression is a hierarchically structured representation of the image. 56. A computer program product according to any one of claims 49 to wherein said image is at least in part a pixel-based image. 57. A computer program product according to any one of claims 49 to 56, wherein a flag is stored to indicate whether data of an object is opaque or ordinary. 58. A computer program product according to claim 57, wherein said compositing expression is optimized based on a value of said flag for contributing S* objects. 59. A computer program product according to any one of claims 49 to 58, 20 wherein a wholly opaque object in said region acts to eliminate one or more objects within said region from said compositing expressions. A computer program product according to any one of claims 49 to 59, wherein a wholly transparent object in said region eliminates at least itself from said compositing expression. 61. A computer program product according to any one of claims 49 to wherein said modifying comprises modifying a manner in which said compositing expression is evaluated without modifying said hierarchically structured representation. 62. A computer program product including a computer readable medium having a plurality of software modules for creating an image, said image to be formed by rendering and compositing at least a plurality of graphical objects, each said object having a predetermined outline, said computer program product comprising: dividing module for dividing a space in which said outlines are defined into a 471440 CFP01423AU Open_scm0l [I:\ELEC\CISRA\OPENSCRN\O_SCRNOI]471440.doc:IAD -118- plurality regions, each said region being defined by at least one region outline substantially following at least one of said predetermined outlines or parts thereof and being substantially formed by segments of a virtual grid encompassing said space, wherein each object has two region outlines arranged either side of said predetermined outline to thus define three regions for each said object, and wherein each said region has a corresponding compositing expression; classifying module for classifying said regions according to at least one attribute of said graphical objects within said regions; modifying module for modifying each said corresponding compositing expression according to a classification of each said region to form an augmented compositing expression for each said region; and ~compositing module for compositing said image using each of said augmented compositing expressions. 63. A computer program product according to claim 62, wherein said attribute is selected from the group consisting of colour, opacity and object outline. 4 S64. A computer program product according to any one of claims 62 or 63, wherein said grid is regularly spaced and preferably orthogonally based. method according to any one of claims 62 to 64, wherein said grid is irregularly shaped. 66. A computer program product according to any one of claims 62 to wherein said compositing expression is a hierarchically structured representation of the image. 67. A computer program product according to any one of claims 62 to 66, wherein said image is at least in part a pixel-based image. 68. A computer program product according to any one of claims 62 to 67, wherein a flag is stored to indicate whether data of an object is opaque or ordinary. 69. A computer program product according to claim 68, wherein said compositing expression is optimized based on a value of said flag for contributing 471440 CFP01423AU Open_scml [I:\ELEC\CISRA\OPENSCRN\O_SCRNOI1 ]471440.doc:IAD -119- objects. A computer program product according to any one of claims 62 to 69, wherein a wholly opaque object in said region acts to eliminate one or more objects within said region from said compositing expressions. 71. A computer program product according to any one of claims 62 to wherein a wholly transparent object in said region eliminates at least itself from said compositing expression. 72. A computer program product according to any one of claims 62 to 71, wherein said modifying comprises modifying a manner in which said compositing i expression is evaluated without modifying said hierarchically structured representation. o. So 73. A method of creating an image substantially as herein described with reference to any one of the embodiments as illustrated in Figs. 4 to 22. o 74. An apparatus for creating an image substantially as herein described with S@ reference to any one of the embodiments as illustrated in Figs. 4 to 22. 75. A computer program product substantially as herein described with reference to any one of the embodiments as illustrated in Figs. 4 to 22. DATED this Twentieth Day of August 1999 Canon Kabushiki Kaisha Patent Attorneys for the Applicant SPRUSON FERGUSON 471440 CFP01423AU Open_scm [I:\ELEC\CISRA\OPENSCRN\O_SCRN01]471440.doc:IAD