Efficient clip-list management for a two-dimensional graphics subsystem
View Patent ↗A graphics sub-system manages a two-dimensional coordinate space which includes a plurality of rectangular regions. The two-dimensional coordinate space is represented by a hierarchical linked list of nodes. Each node represents a rectangular region of two-dimensional coordinate space. Each node acts as a bounding box for all descendant nodes in the hierarchical linked list of nodes.
1. A method for managing an on screen buffer representing a two-dimensional coordinate space comprising the steps of:
representing the on screen buffer as a hierarchical linked list of nodes, each node representing a rectangular region of the two-dimensional coordinate space, the rectangular region of a parent node acts as a bounding box for all descendant nodes; and
determining a region of the on screen buffer to be updated by traversing the hierarchical linked list for nodes representing respective rectangular regions intersecting a desired update area.
2. The method of claim 1 wherein the step of representing includes each node having a respective node identifier stored in a single cache line.
3. The method of claim 2 wherein the node identifier identifies the rectangular region represented by the node and a next node, a skip node, a previous node and a parent node associated with the node in the hierarchical linked list of nodes.
4. The method of claim 1 wherein the rectangular region is a window.
5. A graphics subsystem which manages an on screen buffer representing a two-dimensional coordinate space comprising:
a hierarchical linked list of nodes, each node representing a rectangular region of the two-dimensional coordinate space, the rectangular region of a parent node acts as a bounding box for all descendant nodes; and
an on-screen buffer manager which determines a region of the on screen buffer to be updated by traversing the hierarchical linked list for nodes representing respective rectangular regions intersecting a desired update area.
6. The graphics subsystem of claim 5 wherein each node in the hierarchical linked list of nodes has a respective node identifier stored in a single cache line.
7. The graphics subsystem of claim 6 wherein the node identifier identifies the rectangular region represented by the node and a next node, a skip node, a previous node and a parent node associated with the node in the hierarchical linked list of nodes.
8. The graphics subsystem of claim 5 wherein the rectangular region is a window.
9. A graphics subsystem which manages an on screen buffer representing a two-dimensional coordinate space comprising:
a hierarchical linked list of nodes, each node representing a rectangular region of the two-dimensional coordinate space, the rectangular region of a parent node acts as a bounding box for all descendant nodes; and
means for determining a region of the on screen buffer to be updated by traversing the hierarchical linked list for nodes representing respective rectangular regions intersecting a desired update area.
10. The graphics subsystem of claim 9 wherein each node in the hierarchical linked list of nodes has a respective node identifier stored in a single cache line.
11. The graphics subsystem of claim 10 wherein the node identifier identifies the rectangular region represented by the node and a next node, a skip node, a previous node and a parent node associated with the node in the hierarchical linked list of nodes.
12. The graphics subsystem of claim 9 wherein the rectangular region is a window.
13. A computer program product, for managing an on screen buffer representing a two-dimensional coordinate space, the computer program product comprising a computer readable medium having computer readable code thereon, including program code which:
represents the on screen buffer as a hierarchical linked list of nodes, each node representing a rectangular region of the two-dimensional coordinate space, the rectangular region of a parent node acts as a bounding box for all descendant nodes; and
determines a region of the screen buffer to be updated by traversing the hierarchical linked list for nodes representing respective rectangular regions intersecting a desired update area.
14. The method of claim 1 wherein leaf nodes in the hierarchical linked list of nodes represent visible regions in the on screen buffer.
15. The method of claim 1 further comprising:
storing visible rectangular regions represented by leaf nodes in the hierarchical linked list of nodes in the on screen buffer.