Method and apparatus for high-performance rendering and hit-testing of a window tree
First Claim
1. A method for rendering a window tree having a plurality of nodes, comprising:
- defining a recursive procedure comprising;
(a) identifying one of said nodes to be rendered;
(b) determining whether a visual object defined at said identified node is visible;
(c) in response to determining that said object is visible, copying rendering information for a hub-tree of said window tree defined by said identified node onto a stack;
(d) calculating the bounds of an invalidation rectangle in coordinates relative to said object by;
(i) determining whether a transformation is applied to said object;
(ii) in response to determining that no transformation should be applied to said object, using data from said stack associated with a parent node of said object as said invalidation rectangle;
(iii) in response to determining that a transformation should be applied to said object, creating a cumulative invalidation matrix utilizing an inverse transform of said transformation;
(iv) applying said cumulative invalidation matrix to said invalidation rectangle of said parent node to obtain a new bounding polygon;
(v) determining a bounding rectangle of said new bounding polygon;
(vi) intersecting said new bounding rectangle with a bounding rectangle for said object; and
(vii) storing the results of said intersection on said stack;
and determining whether said object should be rendered;
(e) in response to determining that said object should be rendered, rendering said object and determining whether said object is a trivial object; and
(f) in response to determining that said object is not a trivial object, rendering any children of said node using said recursive procedure.
4 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for high-performance rendering and hit-testing of a window tree is provided. A window tree may be rendered using an application programming interface provided by the present invention. The application programming interface provides support for world-transforms, enabling entire sub-trees of the window tree to be rotated and scaled during rendering. In order to quickly render and hit-test the transformed nodes of the window tree, a stack-based implementation of the “painter'"'"'s algorithm” is utilized to achieve fast rendering. By storing all state information on a stack regarding each node in the window tree and building new data structures containing rendering information for each node and its children, any portion of the sub tree may be rendered on demand.
27 Citations
7 Claims
-
1. A method for rendering a window tree having a plurality of nodes, comprising:
-
defining a recursive procedure comprising;
(a) identifying one of said nodes to be rendered;
(b) determining whether a visual object defined at said identified node is visible;
(c) in response to determining that said object is visible, copying rendering information for a hub-tree of said window tree defined by said identified node onto a stack;
(d) calculating the bounds of an invalidation rectangle in coordinates relative to said object by;
(i) determining whether a transformation is applied to said object;
(ii) in response to determining that no transformation should be applied to said object, using data from said stack associated with a parent node of said object as said invalidation rectangle;
(iii) in response to determining that a transformation should be applied to said object, creating a cumulative invalidation matrix utilizing an inverse transform of said transformation;
(iv) applying said cumulative invalidation matrix to said invalidation rectangle of said parent node to obtain a new bounding polygon;
(v) determining a bounding rectangle of said new bounding polygon;
(vi) intersecting said new bounding rectangle with a bounding rectangle for said object; and
(vii) storing the results of said intersection on said stack;
and determining whether said object should be rendered;
(e) in response to determining that said object should be rendered, rendering said object and determining whether said object is a trivial object; and
(f) in response to determining that said object is not a trivial object, rendering any children of said node using said recursive procedure. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
Specification