Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
2000-08-07
2004-06-29
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S440000, C345S441000, C345S619000, C345S622000, C345S672000
Reexamination Certificate
active
06756994
ABSTRACT:
TECHNICAL 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 systems for creating an image made up by compositing multiple components. The invention also relates to a computer program product including a computer readable medium having recorded thereon a computer program for creating an image made up by compositing multiple components.
BACKGROUND ART
Computer generated images are typically made up of many differing components, graphical elements or graphical objects 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 opacity channel information is typically understood to be fully opaque or partially transparent within some defined bounds of the element, and assumed to be completely transparent outside those bounds.
An expression tree offers a systematic means for representing 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 too 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 others are shown in FIG.
2
.
Several of the above types of nodes can 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. This construct is composited with a second image.
Although the non-transparent area of a graphical element can of itself be of 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 graphics rendering model considers each node to be conceptually infinite 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 these conventional 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 an alpha compositing environment where complex expressions can be very computationally expensive. Thus, the per-pixel cost of compositing can be quite high since 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. This problem is particularly relevant when performing “Dynamic Rendering”.
Dynamic rendering refers to the generation of multiple successive images. Given a compositing tree, it is possible to generate region groups (containing regions) for the compositing tree. The compositing tree represents an initial image. Changes to the tree can be made to make the tree represent a new image. The region groups and the region description of the tree are updated to reflect the modified tree. Performance can be improved by exploiting commonality between the two images.
Australian Patent Publication No. AU-A-47329/99 discloses a method of creating a series of images formed by rendering graphical objects. The method disclosed by Australian Patent Publication No. AU-A-47329/99 exploits the opaqueness of the graphical objects to be rendered during a compositing operation. The contents of Australian Patent Publication No. AU-A47329/99 are incorporated herein by cross-reference.
An example implementation of the method disclosed by AU-A-47329/99 utilises a label referred to as a “Contents Label (CL)” which represents a unique symbolic expression describing the method of construction of image data. The contents label disclosed by AU-A- 47329/99 is implemented as an index into an array of contents label property structures, which are represented by the tag CL_Properties. The terms in the symbolic expression are used to distinguish between different categorisations of the source of image data. Region groups of two distinct leaf nodes in a compositing tree can contain regions that are labelled with distinct contents labels even if their actual image data is equivalent. A region of the image is substantially defined by the boundary outlines of two or more overlapping graphical elements. The example implementation disclosed by AU-A-47329/99 utilises a system of unique integers to represent contents labels. For example, “23” represents “(A over B) over C”.
AU-A-47329/99 also described the concepts of “primary” and “secondary” damage in order to demonstrate that it is not always necessary to regenerate an entire image as a result of a change to the compositing tree representing the image. Any region of the image including a compositing equation with an object that has been altered in some way can be said to suffer primary damage. Secondary damage is said to have been incurred by a region, if the object upon which the boundary outline of the region (but not content) depends, changes in some way. 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. These dependencies are referred to as “primary” and “secondary” dependencies. A primary dependency is a contents label (e.g. L′) representing an expression which has been constructed by combining L and sonic other contents label. A 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 the boundary of L is affected, For example,
FIG. 9
shows the region subdivision and the respective compositing expressions for a simple compositing tree. Consider therefore the situation in which object A moves
Bella Matthew C.
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Rahmjoo Manucher
LandOfFree
Method and apparatus for handling secondary dependencies does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for handling secondary dependencies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for handling secondary dependencies will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3364589