Method and apparatus for high-performance rendering and hit-testing of a window tree
View Patent ↗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.
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.
2. The method of claim 1 , wherein determining whether said object is a trivial object comprises examining a bit associated with said object.
3. The method of claim 2 , further comprising:
in response to determining that said object is a trivial object, rendering any children of said node using a trivial recursive rendering procedure.
4. The method of claim 2 , wherein said trivial recursive rendering procedure comprises:
defining a recursive procedure comprising,
determining whether said node intersects an invalidation rectangle;
in response to determining that said node intersects an invalidation rectangle, rendering a visual object at said node; and
calling said trivial recursive rendering procedure for each of said children of said node.
5. The method of claim 1 , wherein determining whether said object should be rendered comprises determining the intersection of said object and said bounds of said invalidation rectangle in coordinates relative to said object.
6. A computer-controlled apparatus capable of performing the method of any one of claims 1 and 2 - 5 .
7. A computer-readable medium comprising instructions which, when executed by a computer, cause the computer to perform the methods of any one of claims 1 and 2 - 5 .