AU2003246033B2 - Relating a Point of Selection to One of a Hierarchy of Graphical Objects - Google Patents

Description

I

S&F Ref: 645720

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT Name and Address of Applicant: Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome, Ohta-ku Tokyo 146 Japan Actual Inventor(s): Address for Service: Invention Title: Andrew R Coker, Rob Sangster, Alexander Will, Richard Barry Ling Spruson Ferguson St Martins Tower Level 31 Market Street Sydney NSW 2000 (CCN 3710000177) Relating a Point of Selection to One of a Hierarchy of Graphical Objects ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) AU 2002951807 [32] Application Date 27 Sep 2002 The following statement is a full description of this invention, including the best method of performing it known to me/us:- 5815c

I

-1- RELATING A POINT OF SELECTION TO ONE OF A HIERARCHY OF GRAPHICAL OBJECTS Field of the Invention The present invention relates generally to image processing and, in particular, to a method and apparatus for relating an event, such as a mouse event, to one or more of a plurality of graphical objects arranged in a hierarchical compositing structure. The present invention also relates to a computer program product including a computer readable medium having recorded thereon a computer program for relating an event, such as a mouse event, to one or more of a plurality of graphical objects arranged in a hierarchical compositing structure.

Background A computer based graphical object is a single item that can be displayed and transformed as a unit. For example, a graphical object can include a shape defined by geometrical data; a bitmap image; or text defined by a character string and typeface information. In order to achieve user interaction with such a graphical object being displayed by a computer system, an operation often referred to as "hit-detection" or "picking" is typically executed by the computer system. For example, in software drawing applications, a user can draw graphical objects such as lines and circles. If the user wishes to select some of these drawn objects in order to perform some operation on the objects, such a drawing application typically executes a hit-detection or picking operation in response to a mouse click corresponding to the selected object.

Known methods for performing hit-detection include calculating a bounding box around each object, or maintaining a data structure to keep track of which of a number of objects is visible at each pixel location on a display. Other known methods of hit detection include re-drawing each object in turn on a display or a representation of the display in computer memory.

645720.doc -2- One means for systematically representing a number of graphical objects forming a graphical user interface or other displayed graphical information, and which facilitates in later rendering, is referred to as a "compositing tree". Compositing trees typically comprise a plurality of nodes referred to as leaf nodes, unary nodes or binary nodes non-leaf nodes). Nodes of higher degree, or of alternative definition may also be used.

Unary nodes or binary nodes will be generically referred to hereinafter as "compositing nodes".

A leaf node is the outer most node of a compositing tree and as such has no descendent nodes. A leaf node generally represents a particular graphical object. Unary nodes represent an operation, which modifies pixel data represented by a part of the compositing tree below the unary operator. Unary nodes include such operations as colour conversions and convolutions (blurring etc). A binary node typically branches to left and right subtrees, wherein each subtree is itself a compositing tree comprising of at least one leaf node. Binary nodes represent an operation, which combines the pixel data for two children of the binary node 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 others are seen in Fig. 7. The compositing operations represented by the compositing operators are arithmetic or bitwise operations including opacity. Compositing operations are performed on the component values of the colours of a graphical object.

Several of the above types of nodes may be combined to form a compositing tree.

Figs. 1(a) to 1(h) show four example compositing trees 100, 120, 130, 140 and graphical representations 109, 129, 139, 149 corresponding to the trees 100, 120, 130 and 140, respectively. In Fig. a compositing tree 100 includes a square 101, triangle 105 and circle 103, which are combined with an "over" operator 107. The resulting graphical 645720.doc -3representation 109 of the compositing tree 100 is shown in Fig. 1(b) where the square 101 is over-laid above the circle 103, which is in turn over-laid above the triangle 105.

In Fig. a circle 121 is combined with a triangle 123 using an "in" or clipping type operator 125 as shown by the compositing tree 120. The resulting graphical representation 129 is shown in Fig. As seen in Fig. only the circle 121 is visible in the resulting graphical representation 129. The object that becomes visible as a result of a clipping operation will hereinafter be referred to as the first operand (in this case, the circle), where the extent of the first operand is limited to that defined by the other operands of an associated compositing tree. Thus, in Fig. 1(d) the visible segment of the graphical representation 129 is shaded with the horizontal shading pattern of the circle 121, not the triangle 123.

In Fig. the compositing tree 130 includes a triangle 131 clipped by a node 132 representing the result of an operation, "square 133 over circle 135". Therefore, in Fig.

the triangle 131 is shown, limited in extent to those areas covered by the circle 135 and/or the square 133.

In Fig. the compositing tree 140 includes a square 141 clipped by a circle 143, with the result of the clipping operation being combined with a triangle 145, resulting in the graphical representation 149 as shown in Fig. 1(h).

The hierarchical compositing trees described above for representing graphical objects forming a graphical user interface provide a number of advantages, particularly during rendering. However, the conventional methods described above for performing hit-detection are applicable only when displayed graphical objects are stored as a flat list.

Thus, a need exists for a method of performing a hit detection operation when graphical objects are arranged as a hierarchy in which compositing operators are used.

645720.doc -4- ISummary 0 It is an object of the present invention to substantially overcome, or at least

O

z ameliorate, one or more disadvantages of existing arrangements.

According to one aspect of the present invention there is provided a method of relating a point of selection in a space within which one or more graphical objects are defined, to at least one of said graphical objects, said selection being predefined as one of a plurality of types, said method comprising the steps of: Operforming a first traversal of a hierarchical compositing structure formed by a

O

plurality of nodes in order to identify any of said nodes that are associated with a graphical object associated with said particular type of selection; and performing a second traversal of said structure and comparing one or more of said graphical objects with said point of selection to identify any of said graphical objects corresponding to said point of selection, wherein any nodes that are not identified in said first traversal are transparent to said particular type of selection and are skipped during said second traversal.

According to another aspect of the present invention there is provided a method of executing one or more actions in response to a point of selection in a space within which one or more graphical objects are defined, said selection corresponding to at least one of said graphical objects, said method comprising the steps of: performing first and second traversals of a hierarchical compositing structure formed by a plurality of nodes in order to identify a node that is associated with said at least one graphical object, wherein one or more of said nodes which are not of a type of selection corresponding to said point of selection are skipped during said second traversal; (ii) examining said node and any parent node of said node to identify at least one action associated with said node or any parent node of said node; and 645720.doc I(iii) executing said at least one identified action, wherein said identified action is

O

C, associated with said type.

0 z According to still another aspect of the present invention there is provided an apparatus for relating a point of selection in a space within which one or more graphical objects are defined, to at least one of said graphical objects, said selection being predefined as one of a plurality of types, said apparatus comprising: first traversal means for performing a first traversal of a hierarchical compositing Ostructure formed by a plurality of nodes in order to identify any of said nodes that are associated with a graphical object associated with said particular type of selection; and second traversal means for performing a second traversal of said structure and comparing one or more of said graphical objects with said point of selection to identify any of said graphical objects corresponding to said point of selection, wherein any nodes that are not identified in said first traversal are transparent to said particular type of selection and are skipped during said second traversal.

According to still another aspect of the present invention there is provided an apparatus for executing one or more actions in response to a point of selection in a space within which one or more graphical objects are defined, said selection corresponding to at least one of said graphical objects, said apparatus comprising: identifying means for performing first and second traversals of a hierarchical compositing structure formed by a plurality of nodes in order to identify a node of said structure associated with said at least one graphical object, wherein one or more of said nodes which are not of a type of selection corresponding to said point of selection are skipped during said second traversal; examining means for examining said node and any parent node of said node to identify at least one action associated with said node or any parent node of said node; and 645720.doc 13, NOV. 2006 14:10 SPRUSON FERGUSON 92615486 NO. 2918 P. 3 -6- 00 execution means for executing said at least one identifed action, wherein said identified action is associated with said type.

4 According to still another aspect of the present invention there is provided a computer program for relating a point of selection ina a space within which one or more n graphical objects are defined, to at least one of said graphical objects, said selection being VaS predefied as one of a plurality of types, said program comprising: ci code for performing a first traversal of a hierarchical compositng structure formed 0o by a plurality of nodes in order to identify any of said nodes that are associated with a Ci graphical object associated with said particular type of selection; and code for performing a second traversal of said structure and comparing one or more of said graphical objects with said point of selectionto identify any of said graphical objects corresponding to said point of selection, wherein any nodes that are not identified in said first traversal are transparent to said particular type of selection and are skipped during said second traversal.

According to still another aspect of the present invention there is provided a computer program for executing one or more actions in response to a point of selection in a space within which one or more graphical objects are defined, said selection corresponding to at least one of said graphical objects, said program; code for performing first and second traversals of a hierarchical composifing structure formed by a plurality of nodes in order to identify a node that is associated with said at least one graphical object, wherein one or more of said nodes which are not of a type of selection corresponding to said point of selection are skdpped during said second traversal; code for examining said node aad any parent node of said node to identify at least one action associated with said node or any parent node of said node; and 645720.doe COMS ID No: SBMI-05335255 Received by IP Australia: Time 14:11 Date 2006-11-13 13-NOV-2006 14:10 13.NOV. GG6 1: 1~ SPRUSON FERGUSON 92615486N.28 P.4 NO, 2918 P. 4 code folxctn adatlatoeietfed action, whlerein. said identified action is associated with said type.

z According to still another aspect of the present invention there is provided a method of relating a point of selection in a space within which one or more graphical Objects are en s defined, to at least one of said graphical objects, said selection being predeflned as one of en a plurality of types, said method compiing the steps of: performing a first traversal of a hierarhial compoaitiiig structure formed by a en plurality Of nodes in order to identify any of said nodes that are associated wit a Ci graphical object associated wit said particular type of selection; and performing a second traveral of said structure and comparing one or more of said graphical objects with said point of selection to identify any of said graphical objects corresponding to said point of selectionm wherein said first traversal determines whether one or more nudes of said compositing tree can be sldpped during said second traversal said one or more nodes being transparent to said particular type of selection.

According to still mnother aspect of the present invention there is provided an apparatus for relating a point of selection in a space within which one or more graphical objects are defined, to at least one of said graphical objects, said selection being predefined as one of a plurality of types, said apparatus comprising: first traversal means for perforning a first traversal of a hierarchical compositing structure formed by a plurality of nodes in order to identify any of said nodes that are associated with a graphical object associated with said particular type of selection, and second traversal means for performing a second traversal of said structure and comparing one or more of said graphical objects with said point of selection to identify any of said graphical objects corresponding to said point of selection, wherein said first traversal determines whether one or more nodes of said compositixig tree can be skcipped 645720.dov COMS ID No: SBMI-05335255 Received by IP Australia: Time 14:11 Date 2006-11-13 -8during said second traversal said one or more nodes being transparent to said particular Ntype of selection.

z According to still another aspect of the present invention there is provided a computer program for relating a point of selection in a space within which one or more graphical objects are defined, to at least one of said graphical objects, said selection being predefined as one of a plurality of types, said program comprising: code for performing a first traversal of a hierarchical compositing structure formed Oby a plurality of nodes in order to identify any of said nodes that are associated with a graphical object associated with said particular type of selection; and code for performing a second traversal of said structure and comparing one or more of said graphical objects with said point of selection to identify any of said graphical objects corresponding to said point of selection, wherein said first traversal determines whether one or more nodes of said compositing tree can be skipped during said second traversal said one or more nodes being transparent to said particular type of selection.

Other aspects of the invention are also disclosed.

Brief Description of the Drawings Some aspects of the prior art and one or more embodiments of the present invention will now be described with reference to the drawings, in which: Figs. 1(a) to 1(h) show example compositing trees and corresponding graphical representations; Fig. 2 is a flow diagram showing a method of determining a graphical object corresponding to the location of a mouse event; Fig. 3 is a flow diagram showing a method of marking nodes in a compositing tree representing a path to nodes that are registered for a particular event type, as performed during the method of Fig. 2; 645720.doc -9- Fig. 4 is a flow diagram showing a method of searching nodes of a compositing tree to detect a hit on a node of the compositing tree, as performed during the method of Fig.

2; Fig. 5 is a flow chart showing a method of searching a group of graphical objects composited with an "over" operator, as performed during the method of Fig. 4; Fig. 6 is a flow chart showing a method of searching a group of graphical objects composited with a clipping operator, as performed during the method of Fig. 4; Fig. 7 shows the result of a variety of compositing operators useful with the present invention; and Fig. 8 is a schematic block diagram of a general-purpose computer upon which arrangements described can be practiced.

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

The principles of the preferred methods described herein have general applicability to image processing. However, for ease of explanation, the steps of the preferred methods are described with reference to a graphics framework for the creation of graphical userinterfaces and other displayed information, where such an interface is comprised of a number of graphical objects.

The methods described herein are preferably practiced using a general-purpose computer system 800, such as that shown in Fig. 8 wherein the processes of the preferred methods may be implemented as software, such as an application program executing within the computer system 800. In particular, the steps of methods described herein are effected by instructions in the software that are carried out by the computer. The 645720.doc

I

instructions may be formed as one or more code modules, each for performing one or more particular tasks. The software may also be divided into two separate parts, in which a first part performs the described methods and a second part manages a user interface between the first part and the user. The software may be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer from the computer readable medium, and then executed by the computer. A computer readable medium having such software or computer program recorded on it is a computer program product. The use of the computer program product in the computer preferably effects an advantageous apparatus for implementing the described methods.

The computer system 800 is formed by a computer module 901, input devices such as a keyboard 802 and mouse 803, output devices including a printer 815, a display device 814 and loudspeakers 817. A Modulator-Demodulator (Modem) transceiver device 816 is used by the computer module 801 for communicating to and from a communications network 820, for example connectable via a telephone line 821 or other functional medium. The modem 816 can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN), and may be incorporated into the computer module 901 in some implementations.

The computer module 801 typically includes at least one processor unit 805, and a memory unit 806, for example formed from semiconductor random access memory (RAM) and read only memory (ROM). The module 801 also includes an number of input/output interfaces including an audio-video interface 807 that couples to the video display 814 and loudspeakers 817, an I/O interface 813 for the keyboard 802 and mouse 803 and optionally a joystick (not illustrated), and an interface 808 for the modem 816 and printer 815. In some implementations, the modem 816 may be 645720.doc 11 incorporated within the computer module 801, for example within the interface 808. A storage device 809 is provided and typically includes a hard disk drive 810 and a floppy disk drive 811. A magnetic tape drive (not illustrated) may also be used. A CD-ROM drive 812 is typically provided as a non-volatile source of data. The components 805 to 813 of the computer module 801, typically communicate via an interconnected bus 804 and in a manner that results in a conventional mode of operation of the computer system 800 known to those in the relevant art. Examples of computers on which the described arrangements can be practised include IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom.

Typically, the application program is resident on the hard disk drive 810 and read and controlled in its execution by the processor 805. Intermediate storage of the program and any data fetched from the network 820 may be accomplished using the semiconductor memory 806, possibly in concert with the hard disk drive 810. In some instances, the application program may be supplied to the user encoded on a CD-ROM or floppy disk and read via the corresponding drive 812 or 811, or alternatively may be read by the user from the network 820 via the modem device 816. Still further, the software can also be loaded into the computer system 800 from other computer readable media. The term "computer readable medium" as used herein refers to any storage or transmission medium that participates in providing instructions and/or data to the computer system 800 for execution and/or processing. Examples of storage media include floppy disks, magnetic tape, CD-ROM, a hard disk drive, a ROM or integrated circuit, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computer module 801. Examples of transmission media include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including e-mail transmissions and information recorded on Websites and the like.

645720.doc -12- The methods described herein allow a programmer to assemble a collection of graphical objects and to assign attributes size, position or shape) to the graphical objects. Subsequent user interaction events, such as events input by a user with a pointing device the mouse 803), are captured, processed and executed by the processor 805 in a manner defined by the programmer for a particular type of mouse event. In determining the response to be executed, the processor 805 selects which of a set of graphical objects that are being displayed corresponds to the position of an event on the display 814 a hit detection operation is performed by the processor 805). A method 200 of determining a graphical object corresponding to the location of a mouse event, will be described in detail below with reference to Fig. 2.

The methods described herein further allow a programmer to create an animation for display on the display 814. The animation can subsequently enable a user to interact with the computer system 800, where the computer system 800 can be used as a tool for creating and implementing graphical user-interfaces.

In the following description, the term "mouse events" is used interchangeably to refer to any type of event resulting from the use of a pointing device, and is not limited to a computer mouse. For example, such a pointing device can include a drawing tablet, trackball or touch-sensitive display. The term mouse events includes depressing or releasing any buttons of the mouse, or moving the position of the mouse. The coordinates of any such mouse event correspond to the position of a device "pointer" on a display the display 814) at the time of the event.

Additionally, the methods described herein can be executed other than in response to a physical event from a pointer device. The described methods can be triggered in computer software, for example, so as to determine if there is a displayed object at some point on the display 814.

645720.doc

I

13- The methods described herein are preferably executed in relation to a hierarchy of graphical objects in the form of a compositing tree as described above. Instead of being represented simply as a collection of graphical objects, which are drawn sequentially to the display 814, such graphical objects can be combined together by compositing operators using compositing trees as described above. However, the described methods are not limited to any defined set of compositing operators.

In the methods described herein, a programmer can configure a compositing tree 100) in order for interaction with user events from a pointing device the mouse 803) to occur. Any leaf node graphical object node) or any compositing node can be registered as being responsive to any set of mouse events. The registration is preferably implemented by associating such mouse events with one or more particular graphical objects and storing details of such associations as a set of flags for each event) in memory 806. Such registration indicates that a corresponding object can be "hit" by an event at a specific location. If a node is not registered for an event of a particular type, then the node will be "transparent" to events of that type. If such a mouse event occurs within the boundaries of a corresponding graphical object on the display 814, then the corresponding object will not be hit, allowing another graphical object that is underneath the corresponding graphical object to be hit.

When a compositing node is registered for an event, a hit of any constituent parts of the registered node represents a hit for the registered node. For example, a compositing node that represents a control comprising several graphical objects composited together can be registered as described above. In the methods described herein, in determining which node has been hit by a mouse event, the node selected as being hit is always one of the registered nodes. In such a case, the processor 805 determines that the whole compositing node was hit, not just an associated individual graphical object leaf node).

645720.doc 14- In addition to registering nodes of a compositing tree for mouse events, eventhandling behaviour can also be associated with the nodes of the compositing tree. When a node is found to be hit by a mouse event, then that node and each ancestor of the node is examined in order, until an event handler is found. An event handler in this context is a user-defined function that is executed using parameters indicating the type and location of the mouse event, and the registered node in the compositing tree that was hit by the mouse event. Depending on the type of mouse event, the executed event handler may be configured to execute one or more different actions modifying a compositing tree representing the visual appearance of the user interface, activating a procedure, calculating a data value, determining the meaning of a key-board press, or the like).

A hierarchy of event handling can be organised within a hierarchy of graphical objects. For example, many graphical objects can be combined together to form a compound graphical object such as a control on a graphical user interface. Subsequently, each component part of that control can be configured to handle mouse events by means of a first general mouse event handler, and some other part of that control can handle mouse events by means of a second, more specific mouse event handler.

As an example, a compound graphical object representing a control on a user interface can have many associated component graphical objects. Each of the component graphical objects can be registered for interaction with a pointing device. In this instance, a first general event handler can be configured such that a mouse event received for any of the component graphical objects causes a change in visual appearance of the control.

Such a change can represent that the control has gained "focus" on the user interface the control will receive all pointer device input events). A second specific event handler can be configured such that once the control has gained focus, a mouse event received for any specific component graphical object has a different effect. For example, activating some other feature of the control on the user interface.

645720.doc A single event handler can be configured for a plurality of controls of a user interface. In this instance, the single event handler can be configured such that the event handler is associated with a particular compositing node. In this instance, the particular compositing node is an ancestor to each of the plurality of controls, within the hierarchical structure of the compositing tree for graphical objects representing the controls.

As an example, an array of controls buttons operated by a mouse), can be set up and grouped together in a compositing tree by means of a compositing node. In this example, instead of supplying separate event handlers for each button, the user can associate one event handler with the corresponding compositing node.

As will be described in detail below, in the methods described herein, when determining the displayed graphical object corresponding to the location of a mouse event, a compositing tree including the graphical object is examined in two passes. In the first pass, data called hinting information is associated with one or more nodes of the compositing tree. The hinting information marks nodes in the tree that are each ancestors to one or more displayed graphical objects that have been registered to be "hittable" by the event type that has occurred.

In a second pass over the compositing tree for the displayed graphical objects, the co-ordinates of the mouse event are compared to the shape and position of each displayed graphical object. The hinting information at each node of the compositing tree is used to optimise the second pass, by culling sections of the compositing tree that do not lead to any graphical objects that are registered for the event type being searched for.

Different types of compositing operators are processed in different ways for the second pass. For each compositing node, each child node in turn is processed, skipping those nodes where permitted by the hinting information. The results of performing the 645720.doc -16search on each of these child nodes are combined, and become the net result of the search for the compositing node.

As each level in a compositing tree is searched, a cumulative product of affine transformation attributes at each node in the tree is calculated and applied to the coordinates corresponding to the initial event.

By executing two passes of compositing tree data, as described above, only operations that are computationally fast to perform are executed on the entire compositing tree. Operations that are comparatively computationally slower to perform are executed only on a minimal subset of the nodes of the compositing tree as a result of the hinting information being determined and applied in the first pass.

The method 200 of determining a tree node graphical object corresponding to the location of a mouse event, is preferably implemented as software being resident on the hard disk 810 and being controlled in execution by the processor 805. The method 200 processes a compositing tree representing one or more graphical objects displayed on the display 814 of the computer system 800 upon which the mouse event occurred.

The method 200 begins at step 201, where the type and co-ordinates of the mouse event are obtained by the processor 805, when the mouse event occurs. At the next step 210, if the mouse event type is different to a previously processed mouse event, then the method 200 proceeds to step 220. Otherwise, the method 200 proceeds to step 240. At step 220, the processor 805 marks nodes in the compositing tree representing paths to nodes that are registered for the current event type. A method 300 of marking such a path to nodes in the compositing tree that are registered for the current event type, as executed at step 220, will be described in detail below with reference to Fig. 3. The method 300 writes the "hinting" information to the compositing tree.

645720.doc -17- The method 200 continues at the next step 230, where if there exists a node in the compositing tree that is registered for the event type, then the method 200 proceeds to step 250. Otherwise the method 200 concludes.

As described above, if the mouse event type is the same as a previously processed mouse event, then the method 200 proceeds to step 240. At step 240, if a registered node was found for the previous event, then the method 200 proceeds to step 250. Otherwise the method 200 concludes.

At step 250, the processor 805 searches the compositing tree to detect a hit on a node in the tree, which is registered for the event type. A method 400 of searching nodes of the compositing tree to detect a hit on a node in the tree registered for the event type, at step 250, will be described below with reference to Fig. 4.

The result of step 250 is examined by the processor 805 at the next step 260, and if a hit was found for the co-ordinates of the event, and an appropriate event handler was found, then the method 200 proceeds to step 270. Otherwise, the method 200 concludes.

At step 270, the event handler is informed of the co-ordinates and type of the event. The event handler can then be executed by the processor 805 to execute one or more different actions activating a procedure, calculating a data value, determining the meaning of a key-board press, or the like), and the method 200 concludes.

In the method 200, if the structure of the compositing tree for the displayed graphical objects is changed by deleting a node or section of the tree, by attaching a new node, or by modifying the set of events which a node is registered for), then whenever a next mouse event is processed, the previous mouse event is considered to be NULL. In this instance, the result of step 210 of the method 200 will be negative and the method 200 will proceed to step 220, where a new path to registered nodes will be marked.

645720.doc 18- The method 300 of marking nodes of the compositing tree representing a path to nodes that are registered for a current event type, as executed at step 220, is preferably implemented as software being resident on the hard disk 810 and being controlled in execution by the processor 805. The method 300 is described with reference to the processing of a single node object. However, the method 300 is recursive. That is, for each compositing node in the compositing tree, the steps of the method 300 are performed in turn on the child nodes of that compositing node. As such, when applied to the root of the compositing tree, the net effect of executing the method 300 is that hinting information is written for the entire tree.

The method 300 begins at step 320, where if a node of the compositing tree the current node) is a compositing node then the method 300 proceeds to step 330. Otherwise the method 300 proceeds to step 370. Step 330 effectively determines whether path marking is applied recursively to all child nodes, or whether the path marking is limited to the first (top-most) child node. In the method 300, for clipping-type operations (e.g.

compositing operator only the first child is visible on the display 814. Subsequent child nodes serve only to limit the graphical extent of the visible area of the first node.

Hinting information is not applied when comparing the mouse event co-ordinates for such subsequent child nodes. Therefore, the method 300 skips needless computation.

At step 330, if the compositing operation associated with the current node is a clipping type operation, then the method 300 proceeds to step 350. Otherwise, the method 300 proceeds to step 340. At step 350, path marking is recursively performed only for the first child node of the current node and the method 300 proceeds to step 360.

Conversely, at step 340, path marking is applied recursively to all child nodes of the current node. For both steps 340 and 350, the steps of the method 300 are temporarily suspended for the current node, whilst the method 300 is again executed for each of the child nodes (or node) of the current node. After the method 300 has been executed for 645720.doc 19each of the child nodes of the current node, the current sequence of steps of the method 300 is continued for the current node.

For each time that the recursive path marking operation is applied to a child node, a result is obtained of whether any registered nodes were found during the recursive operation. Such results can be temporarily stored in memory 806. If any of the recursive operations executed at steps 340 and 350 did find a registered node, then at step 360, the method 300 proceeds to step 380. Otherwise, the method 300 proceeds to step 370. At step 380, hinting information in the form of a flag HINT_FLAG) is set to have the value "TRUE" for the current node.

At step 370 of the method 300, if the current node is registered for the current event type then the method 300 proceeds to step 380, as described above. Otherwise the method 300 proceeds to step 390 where the value of HINTFLAG is set to FALSE and the method 300 concludes.

A person skilled in the relevant art will appreciate that the method 300 can be implemented as a function, (or method, in an object-oriented programming language), which takes an event type as a first parameter, a node in the tree as a second parameter, and returns a boolean value representing the hint information.

The method 400 of searching nodes of a compositing tree to detect a hit on a node of the compositing tree, as executed at step 250, is preferably implemented as software being resident on the hard disk 810 and being controlled in execution by the processor 805. Similarly to the method 300, the method 400 is recursive. That is, for each compositing node in the compositing tree, the steps of the method 400 are performed in turn on the child nodes of that compositing node. As such, when applied to the root of the compositing tree, the net effect of executing the method 400 is that the entire tree is searched to determine a hit on a node in the tree registered for an event type.

645720.doc 20 The method 400 begins at the root of the compositing tree, at step 405, where the processor 805 determines the co-ordinates and type of event. At the next step 410, transformation attributes position, size-scaling and rotation) for the current node initially the root of the tree) are applied to the co-ordinates of the mouse event. In the method 400, the transformation attributes are preferably represented as an affine matrix of values. Such a transformation can be applied by means of matrix multiplication. As various nodes of the compositing tree are searched, the sequence of transformations is accumulated and applied to the event co-ordinates. Accordingly, when displayed graphical objects are tested, the co-ordinates that are compared to the shape and extent of the graphical objects have the net product of the transformation attributes defined by the nodes of the compositing tree taken into account.

The method 400 continues at the next step 420, where if the current node is registered for the event type currently being searched for, then the method 400 proceeds to step 425. As described above, such registration can be stored in memory 806 as a set of flags representing events where the flags are associated with the current node.

Otherwise, the method 400 proceeds to step 430. At step 425, a flag value USINGHINTS) is set to FALSE. If the current node is registered for the current event type, at step 420, then the processor 805 considers that all component parts all child nodes and descendants) of the current compositing node are considered to be registered for the current event type. Thus, all child nodes below the current node in the compositing tree, are searched exhaustively, without using the hinting information to skip over unregistered nodes, as is performed at steps 520 and 620 in the methods 500 and 600.

The method continues at the next step 435, where a method 500 or method 600, of searching a group of graphical objects to determine a hit, is executed by the processor 805, depending on the type of node that is currently being processed. The method 500 is executed at step 435 where the current node is a compositing node with an "over" 645720.doc -21 compositing operator. Alternatively, the method 600 is executed at step 435 where the current node is a compositing node with a clipping type compositing operator. The method 500 and the method 600 will be explained below with reference to Figs. 5 and 6, respectively.

If the current node is not a compositing node at step 435, but instead represents a displayed graphical object a leaf node), then the transformed mouse event coordinates are compared to the geometry of the graphical object itself. If the transformed mouse event co-ordinates fall within the defined boundary for the graphical object, then a hit has occurred. For the methods described herein, each geometrical object type has particular rules for making such a determination. For example, for a bitmap graphical object, a hit occurs if the (transformed) x co-ordinate of the mouse event is between zero and the bitmap width, and the (transformed) y co-ordinate of the mouse event is between zero and the bitmap height. A graphical object in the form of rendered text may have a rule that a hit occurs if the co-ordinates of the (transformed) mouse event fall within a theoretical rectangular box around the text, or some other rule may be implemented. For a graphical object that is a shape represented by one or more points that define the outline of the graphical object, each particular point can be compared to the geometry defined by those points to determine whether a hit has occurred. Accordingly, any type of graphical object can be processed using the described methods.

Additionally, other types of geometrical relationships can be considered in the context of relating a point of selection to a graphical object when determining if a hit has occurred. For example, a hit may be defined to have occurred if a horizontal line through a point of selection intersects a graphical object. As another example, a hit may be defined to have occurred if any part of a particular graphical object is within a given radius of a point of selection.

645720.doc -22- Data representing the outcome of the hit-detection executed at step 435 can preferably be stored in memory 806 in the form of a data structure Hit_Result, where the data structure contains information about the result of the hit-detection process, as applied to a node. Such a data structure preferably contains a boolean value Hit), which can be set to TRUE if a hit was found or, FALSE otherwise. The data structure can also contain a pointer PtrNode) containing the address of the node object that is hit; and a pointer PtrHandler) containing the address of a node associated with a mouse event handling function.

At the next step 440, data stored in memory 806 at step 435 can be examined by the processor 805. If no hit occurred the value of Hit is FALSE) then the method 400 concludes for the current node. Otherwise, the method 400 proceeds to step 450 where the remaining data stored in memory 806 at step 435 is examined. If the current node is registered for the current type of mouse event, at step 450, then the pointer indicating the address of the node object that is hit PtrNode) can be set to the current node at the next step 455. However, this preferably occurs only if the value of the pointer has not previously been set. Otherwise the method 400 proceeds to step 460, where if the current node has an associated mouse event handler function, then the process proceeds to step 465, where the value of the pointer containing the address of a node associated with a mouse event handling function PtrHandler) is set to the current node. However, this preferably occurs only if the value of the PtrHandler pointer has not previously been set, and the value of the pointer, PtrNode, has already been set. If the current node does not have an associated mouse event handler function at step 460, then the method 400 proceeds to step 470 where the hit search operation terminates, and the value of Hit_Result is subsequently examined by the processor 805 at step 260 of the method 200.

As described above, the method 400 acts recursively from the root node, working down to the level of leaf nodes (ie, actual displayed graphical objects), whereupon a 645720.doc -23positive hit against a graphical object may be detected, and the boolean value Hit) in the data structure Hit_Result) is set to TRUE. From that point, as the method 400 execution proceeds upwards towards the root of the tree, the pointers of the data structure PtrNode and PtrHandler) may be subsequently set. When the first node that is registered for the event type is found, it is recorded in the field PtrNode. When the first node with an associated handler node at or above the first registered node is found, the address of the node with the associated handler is recorded in the data structure as PtrHandler) stored in memory 806.

In one implementation of the methods described herein, the node reported to be hit (if any) can be an actual leaf node, regardless of whether that leaf node was registered, or was arrived at since a higher compositing node was registered. In still another implementation, all event handler functions can be executed down to the root of the compositing tree, instead of just the first event handler function that is found.

The method 500 of searching a group of graphical objects to determine a hit, as executed at step 435 if the current node is a compositing node with an "over" compositing operator), is preferably implemented as software being resident on the hard disk 810 and being controlled in execution by the processor 805. The method 500 checks each child node in turn, terminating when any node returns a positive result, or when all nodes of the compositing tree have been processed. The nodes are examined in order of depth, starting from the node that represents the top-most graphical object highest Zorder value). Therefore, the method 400 will find the top-most registered hit node first, in the case where multiple registered nodes overlap on the display at the point of the mouse event.

The method 500 begins at step 510, where the first unprocessed child node of the current node is selected by the processor 805. At the next step 520, if hinting information is being used at the selected node, then the method 500 proceeds to step 525. Otherwise, 645720.doc 24 the method 500 proceeds to step 540. At step 525, the hinting information of the selected child node is examined. If the selected child node does not have an associated hint flag HINTFLAG) set to the value TRUE, then the method 500 proceeds to step 560. At step 560 the method 500 processes the next child node, or concludes. In this manner, when searching on an "over" compositing node, the hinting information allows the search to skip over nodes which are known not to lead to any nodes that are registered for the current event type.

At decision block 520, if hinting information is not being used at the selected child node, then the method 500 proceeds to step 540. At step 540, the steps of the method 400 are executed recursively for the selected child node. The steps of the method 400 are recursively executed in a similar manner to the steps of the method 300 at steps 340 and 350, where a currently processed child node is becomes the current node for the purposes of the method 400. The value of the USING_HINTS flag is set to FALSE, at step 425 of the method 400 for the selected child node, indicating that hinting information is not to be used for execution of the method 400 for the selected node.

If the selected child node has a hint flag HINT_FLAG) set to the value TRUE indicating that hinting information is being used at the selected child node for the entire search operation), at step 525, then the method 500 proceeds to step 530. As described above, step 530 is skipped if the hint flag is set to FALSE at step 525. At step 530, the steps of the method 400 are executed recursively to the selected child node, as in 540. However, in this instance the value of the USING_HINTS flag is set to TRUE, indicating that the hinting information will be used for the new execution of the method 400. Steps 530 and 540 return a data structure HitResult) as previously described for the method 400.

The method 500 continues at the next step 550, where the data of the data structure is examined to determine if a positive hit has been stored in the data structure by the 645720.doc 25 processor 805. If a positive hit has been stored in the data structure, then the method 500 proceeds to step 440 of the method 400, where the value of the data structure is examined by the processor 805. Otherwise, the method 500 proceeds to step 560, where as previously described, if the processor 805 determines that there are any unprocessed child nodes remaining then the method 500 returns to step 510. Otherwise, the method 500 concludes and proceeds to step 440 of the method 400.

The method 600 of searching a group of graphical objects to determine a hit where the current node is a compositing node with a clipping type compositing operator), as executed at step 435, is preferably implemented as software being resident on the hard disk 810 and being controlled in execution by the processor 805. For a compositing node with a clipping type compositing operator, the first child node represents a displayed graphical object, and subsequent nodes represent clipping regions that may limit the extent of the displayed graphical object. The method 600 determines if a positive hit result is stored for the first child node and then verifies that the object is specifically visible at the given mouse co-ordinates by checking that those co-ordinates also hit each one of the subsequent child nodes. The method 600 executes until a negative hit result is obtained, at which a failure message is returned, or until all child nodes have been processed.

The method 600 begins at step 610, where the first unprocessed child node of the current node is selected by the processor 805. At the next step 620, if hinting information is not being used if method 600 is being executed with a value of USINGHINTS set to the value FALSE), then the method 600 proceeds to step 640. At step 640, the steps of the method 400 are executed recursively for the selected child node, with the value of USINGHINTS set to the value FALSE.

However, if hinting information is being used at the selected node, at step 620, then the method 600 proceeds to step 625, where the hinting information of the selected child 645720.doc -26node is examined. If the selected child node has a hint flag HINT_FLAG) set to FALSE, then the method 600 proceeds to step 685, where the boolean value Hit) of the data structure stored in memory 806 for the selected child node is set to FALSE, indicating that a hit was not detected. Otherwise, the method 600 proceeds to step 630, where the steps of the method 400 are executed recursively to the selected child node, as in 640. However, in this instance the value of the USINGHINTS flag is set to TRUE, indicating that the hinting information will be used for the new execution of the method 400.

From either of steps 630 or 640, the method 600 proceeds to step 650, where the value of the data structure HITRESULT) for the child node is examined. If a negative hit result (ie, the Hit field is FALSE) is detected by the processor 805, then the method 600 proceeds to proceeds to step 440 of the method 400, where the negative hit value of the data structure is examined by the processor 805.

If a positive hit result (ie, the Hit field is TRUE) is detected by the processor 805, at step 650, then the method 600 proceeds to step 660 where the next unprocessed child node of the current node is selected by the processor 805. At the next step 670, the steps of the method 400 are executed recursively for the next selected unprocessed child node.

The value of the USING_HINTS flag is set to FALSE, at step 425 of the method 400 for the selected child node, indicating that hinting information is not to be used for execution of the method 400 for the child node. Therefore, hit detection is recursively executed for each remaining child node of the compositing tree in turn, and for each child node hinting information is not used.

At the next step 680, the processor 805 examines the data structure for the selected child node to determine if a positive hit has been stored in the data structure by the processor 805. Note that the data structure for the subsequently selected unprocessed child nodes is assigned a different name CLIPPING_RESULT), so as not to 645720.doc 27 overwrite the information already represented by the previous data structure HIT_RESULT) resulting from the first node. If a positive hit is detected by the processor 805, at step 680, then the method 600 proceeds to 690. At step 690, if there are no remaining unprocessed child nodes of the current node then the method 600 proceeds to step 440 of the method 400, where the positive hit result is examined by the processor 805. Otherwise the method 600 returns to step 660.

If a negative result is obtained for any child node, at step 680, then the previous positive hit result is negated at the next step 685, before the method 600 proceeds to step 440.

Note that the data structure CLIPPINGRESULT is discarded by the processor 805, since CLIPPINGRESULT is used simply to verify the positive hit result of the first child node object. Hinting information is not used as the clipping nodes are examined, during the method 600. Instead, the clipping nodes are examined exhaustively. Further, the path marking method 300 does not write hinting information at the clipping node locations in the compositing tree for the displayed graphical objects.

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 methods described herein may alternatively be implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of the flow diagrams. Such dedicated hardware may include graphic processors, digital signal processors, or one or more microprocessors and associated memories.

The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and 645720.doc 28 spirit of the invention, the embodiments being illustrative and not restrictive. In this connection, any number of other compositing operators can be implemented in accordance with the methods described above. For example, one such operator is a negated clipping operator or "out" operator, where the extent of the first child node object is clipped to the region external to any of the subsequent child nodes. Hit-detection for such a compositing node is implemented in the same way as for the clipping operator method 600, with the exception that a positive hit result is recorded only if the first child is hit, and each of the subsequent child nodes is not hit.

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

645720.doc

Claims (4)

1. 2. A method according to claim 1, further comprising the step of associating each of said types with one or more of said nodes.
2. 3. A method according to any one of claims 1 or 2, wherein said corresponding graphical objects are not associated with said particular type of selection.
3. 4. A method according to any one of claims 1 to 3, further comprising the step of selecting one of a set of actions to be executed in response to said selection. A method according to claim 4, wherein one of said actions is modifying said hierarchical compositing structure.
4. 645720.doc I 6. A method according to claim 4, wherein one of said actions is activating a procedure. 7. A method according to claim 4, wherein one of said actions is calculating a data value. 8. A method according to any one of claims 1 to 7, wherein one or more nodes of said Ohierarchical structure are associated with affine transformation attributes. 9. A method of executing one or more actions in response to a point of selection in a space within which one or more graphical objects are defined, said selection corresponding to at least one of said graphical objects, said method comprising the steps of: performing first and second traversals of a hierarchical compositing structure formed by a plurality of nodes in order to identify a node that is associated with said at least one graphical object, wherein one or more of said nodes which are not of a type of selection corresponding to said point of selection are skipped during said second traversal; (ii) examining said node and any parent node of said node to identify at least one action associated with said node or any parent node of said node; and (iii) executing said at least one identified action, wherein said identified action is associated with said type. A method according to claim 9, wherein said examination of said node and any parent node of said node terminates upon identification of said action. 645720.doc -31 IN 11. A method according to any one of claims 9 or 10, wherein said examination of said O Snode and any parent node of said node terminates at a root node of said hierarchical 0 z compositing structure. 12. A method according to any one of claims 9 to 11, wherein each identified action is executed in sequence. 13. A method according to any one of claims 9 to 12, wherein said action is modifying said hierarchical compositing structure. 14. A method according to any one of claims 9 to 12, wherein said action is activating a procedure. A method according to any one of claims 9 to 12, wherein said action is calculating a data value. 16. A method according to any one of claims 9 to 15, further comprising the step of associating each of said types with one or more of said nodes. 17. A method according to any one of claims 9 to 16, wherein nodes not associated with a type of event will be transparent to said type of event occurring. 18. A method according to any one of claims 9 to 17, wherein said corresponding graphical objects are not associated with said particular type of selection. 645720.doc 32- O 19. A method according to any one of claims 9 to 18, wherein one or more nodes of z said hierarchical structure are associated with affine transformation attributes. 20. An apparatus for relating a point of selection in a space within which one or more graphical objects are defined, to at least one of said graphical objects, said selection being predefined as one of a plurality of types, said apparatus comprising: Ofirst traversal means for performing a first traversal of a hierarchical compositing structure formed by a plurality of nodes in order to identify any of said nodes that are associated with a graphical object associated with said particular type of selection; and second traversal means for performing a second traversal of said structure and comparing one or more of said graphical objects with said point of selection to identify any of said graphical objects corresponding to said point of selection, wherein any nodes that are not identified in said first traversal are transparent to said particular type of selection and are skipped during said second traversal. 21. An apparatus according to claim 20, further comprising the step of associating each of said types with one or more of said nodes. 22. An apparatus according to any one of claims 20 to 21, wherein said corresponding graphical objects are not associated with said particular type of selection. 23. An apparatus according to any one of claims 20 to 22, further comprising the step of selecting one of a set of actions to be executed in response to said selection. 645720.doc -33 IN 24. An apparatus according to any one of claims 20 to 23, wherein one or more nodes O of said hierarchical structure are associated with affine transformation attributes. An apparatus for executing one or more actions in response to a point of selection in a space within which one or more graphical objects are defined, said selection corresponding to at least one of said graphical objects, said apparatus comprising: identifying means for performing first and second traversals of a hierarchical O compositing structure formed by a plurality of nodes in order to identify a node of said O structure associated with said at least one graphical object, wherein one or more of said nodes which are not of a type of selection corresponding to said point of selection are skipped during said second traversal; examining means for examining said node and any parent node of said node to identify at least one action associated with said node or any parent node of said node; and execution means for executing said at least one identified action, wherein said identified action is associated with said type. 26. An apparatus according to claim 25, wherein said examination of said node and any parent node of said node terminates upon identification of said action. 27. An apparatus according to any one of claims 25 or 26, wherein said examination of said node and any parent node of said node terminates at a root node of said hierarchical compositing structure. 28. An apparatus according to any one of claims 25 to 27, wherein each identified action is executed in sequence. 645720.doc 34 O z 29. An apparatus according to any one of claims 25 to 28, further comprising association means for associating each of said types with one or more of said nodes. An apparatus according to any one of claims 25 or 29, wherein nodes not associated with a type of event will be transparent to said type of event occurring. 31. An apparatus according to any one of claims 25 to 30, wherein said corresponding graphical objects are not associated with said particular type of selection. 32. An apparatus according to any one of claims 25 to 31, wherein one or more nodes of said hierarchical structure are associated with affine transformation attributes. 33. A computer program for relating a point of selection in a space within which one or more graphical objects are defined, to at least one of said graphical objects, said selection being predefined as one of a plurality of types, said program comprising: code for performing a first traversal of a hierarchical compositing structure formed by a plurality of nodes in order to identify any of said nodes that are associated with a graphical object associated with said particular type of selection; and code for performing a second traversal of said structure and comparing one or more of said graphical objects with said point of selectionto identify any of said graphical objects corresponding to said point of selection, wherein any nodes that are not identified in said first traversal are transparent to said particular type of selection and are skipped during said second traversal. 645720.doc 13, NOV. 2006 14:10 SPRUSON ERGUSON 92615486 NO. 2918 P, 34. A ompute program for executing one or more actions in response to a point selection in a space within which one or more graphical objects are defined, said selection Z- corresponding to at least one of said graphical obj cats, said program: code for performing first and second travels o ierarcbicoipositing structure formed by a plurality of nodes in order to identify a node that is associated with M said at least one graphical object wherein one or more of said nodes which are not of a Dtype of selection corresponding to said point of selection are skipped during said second 0 traversal; code for examining said node and any parent node of said node to identify at least t0 one action associated with said node or any parent node of said node; and code for executing said at least one identified action, wherein said identified action is associated with said type. A method of relating a point of selection in a space within which one or more 1s graphical objects are defined, to at least one of said graphical objects, said selection being predefined as one of a plurality of types, said method comprising the steps of: performing a first traversal of a hierarhical compositing structure formed by a plurality of nodes in order to identify any of said nodes that are associated with a graphical object associated with said particular type of selection; and performing a second traversal of said suctture and comparing one or more of said graphical objects with said point of selection to identify any of said graphical objects corresponding to said point of selection, wherein said first traversal determines whether one or more nodes of said compositing tree can be skipped during said second traversal said one or more nodes being transparent to said particular type of selection. 645720.doc COMS ID No: SBMI-05335255 Received by IP Australia: Time 14:11 Date 2006-11-13 -36- ID 36. The method according to claim 35, wherein one or more nodes identified in said O first traversal are not traversed during said second traversal. 37. A method according to any one of claims 35 or 36, further comprising the step of associating each of said types with one or more of said nodes. 38. A method according to any one of claims 35 to 33, wherein said corresponding Ographical objects are not associated with said particular type of selection. 39. A method according to any one of claims 35 to 38, further comprising the step of selecting one of a set of actions to be executed in response to said selection. An apparatus for relating a point of selection in a space within which one or more graphical objects are defined, to at least one of said graphical objects, said selection being predefined as one of a plurality of types, said apparatus comprising: first traversal means for performing a first traversal of a hierarchical compositing structure formed by a plurality of nodes in order to identify any of said nodes that are associated with a graphical object associated with said particular type of selection; and second traversal means for performing a second traversal of said structure and comparing one or more of said graphical objects with said point of selection to identify any of said graphical objects corresponding to said point of selection, wherein said first traversal determines whether one or more nodes of said compositing tree can be skipped during said second traversal said one or more nodes being transparent to said particular type of selection. 645720.doc -37- I 41. A computer program for relating a point of selection in a space within which one or more graphical objects are defined, to at least one of said graphical objects, said selection 0 z being predefined as one of a plurality of types, said program comprising: code for performing a first traversal of a hierarchical compositing structure formed by a plurality of nodes in order to identify any of said nodes that are associated with a graphical object associated with said particular type of selection; and code for performing a second traversal of said structure and comparing one or more 0 of said graphical objects with said point of selection to identify any of said graphical objects corresponding to said point of selection, wherein said first traversal determines whether one or more nodes of said compositing tree can be skipped during said second traversal said one or more nodes being transparent to said particular type of selection. 42. A method of relating a point of selection in a space within which one or more graphical objects are defined, to at least one of said graphical objects, said method being substantially as herein before defined with reference to any one of the embodiments as that embodiment is illustrated in Figs. 2 to 7. 43. An apparatus for relating a point of selection in a space within which one or more graphical objects are defined, to at least one of said graphical objects, said apparatus being substantially as herein before defined with reference to any one of the embodiments as that embodiment is illustrated in Figs. 2 to 7. 44. A computer program for relating a point of selection in a space within which one or more graphical objects are defined, to at least one of said graphical objects, said program being substantially as herein before defined with reference to any one of the embodiments as that embodiment is illustrated in Figs. 2 to 7. 645720.doc 38 DATED this thirty-first Day of July, 2006 0 CANON KABUSHIKI KAISHA Patent Attorneys for the Applicant SPRUSON&FERGUSON 645 720.doc