Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1997-05-21
2001-02-20
Vo, Cliff N. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S420000, C345S421000, C345S440000, C345S440000
Reexamination Certificate
active
06191797
ABSTRACT:
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 a 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 opacity channel information is typically understood to 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 or representation for rendering objects or elements of an image. Expression trees comprise a plurality of nodes including leaf nodes, internal nodes and a root node. A leaf node, being the outer most node of an expression tree, has no descendent nodes and consists of one or more graphical elements. An internal node typically branches to left and right subtrees, wherein each subtree is itself an expression tree comprising at least one leaf node. The internal nodes of an expression tree are compositing operators, which treat the left and right subtrees as operands of the operator. The first node of the expression tree is commonly referred to as a root node. The root node of an expression tree represents the final image, and each node of the tree represents a portion of the final image.
Although 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. Howevever, 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.
If an element, or parts of elements, that have no effect on true final image can be identified, those elements (or parts) need not be rendered, thereby saving considerable time and possibly memory.
Problems arise with prior art methods, at least for images where overlaps occur, because these methods do not easily cope with transparent graphical objects, nor do they handle the full range of compositing operators. It is therefore desirable to at least ameliorate one or more of those problems.
SUMMARY
In accordance with one aspect of the present invention, there is provided a method of optimising an expression tree for compositing an image, the expression tree comprising graphical elements and graphical operators, each node in the tree being either a graphical element or a graphical operator and having a region of the image represented by the node, the method comprising, for at least one node in the tree:
comparing the region represented by the node to a region representation data structure corresponding to one or more regions represented by at least one other node;
determining if the region represented by the node is totally or partially obscured by the one or more regions; and
modifying the expression tree in the event that the region represented by the node is partially or totally obscured.
In accordance with another aspect of rile present invention, there is provided a method of optimising an expression tree for compositing an image, the expression tree comprising a node being either a graphical element or a graphical operator and having a region of the image represented by the node, the method comprising the steps of:
traversing the expression tree node by node;
determining at a current node if a region of the image represented at the node is obscured by regions represented by at least one other node, and modifying the expression tree in the event that the current node is partially or totally obscured.
In accordance with yet another aspect of the present invention there is provided a method of optimising an expression tree for compositing an image, the expression tree comprising a node being either a graphical element or a graphical operator and having a region of the image represented by the node, the method comprising the steps of:
traversing the expression tree node by node and at each current node comprising a graphical operator applying the sub-steps of:
(i) receiving a first region representation from a parent node;
(ii) passing to a first operand of the graphical operator a modified first region representation in accordance with a first predetermined modification rule for the operator;
(iii) returning to the graphical operator a second region representation of regions obscured by a sub-tree associated with the first operand;
(iv) passing to a second operand of the graphical operator a modified second region representation in accordance with a second predetermined modification rule for the operator;
(v) returning to the graphical operator a third region representation of regions obscured by a sub-tree associated with the second operand; and
(vi) determining, in accordance with a set rule for the graphical operator, a final region representation to be returned to the parent node.
REFERENCES:
patent: 5123084 (1992-06-01), Prevost et al.
patent: 5274718 (1993-12-01), Leonardi et al.
patent: 5295236 (1994-03-01), Bjorge et al.
patent: 5579455 (1996-11-01), Greene et al.
patent: 5600763 (1997-02-01), Greene et al.
patent: 5724494 (1998-03-01), Politis
patent: 5745121 (1998-04-01), Politis
patent: 23362/95 (1996-02-01), None
patent: 0528631 (1993-02-01), None
patent: 0694881 (1996-01-01), None
“A Model For Efficient And Flexible Image Computing”, M. Shantzis, pp. 147-154, Computer Graphics SIGGRAPH 1991, Jul. 28-Aug. 2, Las Vegas, Jan. 1, 1994 XP000571017.
Goldfeather, Jack; Near Real-Time CSG Rendering Using Tree Normalization and Geometric Pruning; IEEE Computer Graphics & Applications; pp. 20-28, 1989.
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Vo Cliff N.
LandOfFree
Expression tree optimization for processing obscured... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Expression tree optimization for processing obscured..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Expression tree optimization for processing obscured... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2608162