Quadrant-based two-dimensional memory manager
First Claim
1. In a computer graphics system, a memory manager for storing a plurality of variable-sized two-dimensional storage areas, comprising:
- a two-dimensionally addressed graphics memory having a size equal to or greater than the largest of said two-dimensional storage areas;
a quadtree for storing data regarding the state of said graphics memory and having a plurality of nodes, each of said nodes directly corresponding to a portion of said graphics memory;
an allocation attribute for each of said nodes, each allocation attribute being selected from the group consisting of free, partially-allocated, or full, where said free attribute corresponds to a completely empty portion of said graphics memory, said partially-allocated attribute corresponds to a partially full portion of said graphics memory, and said full attribute corresponds to a completely allocated portion of said graphics memory, wherein said partially-allocated attribute further indicates a mip map storage orientation for a base texture map having square mip maps associated and stored therewith in said graphics memory; and
allocation means for storing said two-dimensional storage areas within said graphics memory responsive to said state of said graphics memory stored in said quadtree.
1 Assignment
0 Petitions
Accused Products
Abstract
A computer graphics system simultaneously stores graphical storage areas of variable size in a two-dimensionally addressed graphics memory. The storage areas contain data corresponding to two-dimensional graphical images such as, for example, texture maps, mip maps, bit maps, or fonts. The graphics system manages the storage areas within the graphics memory using a quadtree that indicates the current storage state thereof. Using the quadtree, a memory manager divides the graphics memory address space into a first level of quadrants of equal two-dimensional size. The size of a storage area to be placed into the memory is compared with the size of the first level quadrants. If size is equal, then the storage area is placed into one of the quadrants. Otherwise, the memory manager further subdivides the graphics memory into quadrants on one or more descending levels as necessary to store the storage area within.
200 Citations
32 Claims
-
1. In a computer graphics system, a memory manager for storing a plurality of variable-sized two-dimensional storage areas, comprising:
-
a two-dimensionally addressed graphics memory having a size equal to or greater than the largest of said two-dimensional storage areas; a quadtree for storing data regarding the state of said graphics memory and having a plurality of nodes, each of said nodes directly corresponding to a portion of said graphics memory; an allocation attribute for each of said nodes, each allocation attribute being selected from the group consisting of free, partially-allocated, or full, where said free attribute corresponds to a completely empty portion of said graphics memory, said partially-allocated attribute corresponds to a partially full portion of said graphics memory, and said full attribute corresponds to a completely allocated portion of said graphics memory, wherein said partially-allocated attribute further indicates a mip map storage orientation for a base texture map having square mip maps associated and stored therewith in said graphics memory; and allocation means for storing said two-dimensional storage areas within said graphics memory responsive to said state of said graphics memory stored in said quadtree. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A computer graphics system for storing a plurality of variable-sized two-dimensional texture maps, comprising:
-
a two-dimensionally addressed texture buffer having a size equal to or greater than the largest of said two-dimensional texture maps; a quadtree for storing data regarding the state of said texture buffer and having a plurality of nodes, each of said nodes directly corresponding to a portion of said texture buffer; an allocation attribute for each of said nodes, each allocation attribute selected from the group consisting of free, partially-allocated, or full, where said free attribute corresponds to a completely empty portion of said texture buffer, said partially-allocated attribute corresponds to a partially full portion of said texture buffer, and said full attribute corresponds to a completely allocated portion of said texture buffer, wherein said partially-allocated attribute further includes a mip map storage orientation for a base texture map having square mip maps associated and stored therewith in said texture buffer; and a texture manager, coupled to said texture buffer, using a procedure for allocating and storing said two-dimensional texture maps within said texture buffer responsive to said state thereof stored in said quadtree, said texture manager providing an update of said state to said quadtree when storing at least one texture map. - View Dependent Claims (22, 23, 24, 25, 26)
-
-
27. In a computer graphics system for storing a plurality of variable-sized two-dimensional texture maps, each having a base texture size, in a two-dimensionally addressed texture buffer having a memory space managed as a hierarchy of parent and child quadrants with four child quadrants of memory space corresponding to a parent quadrant, said system having a quadtree for storing data regarding the state of said texture buffer and having a plurality of nodes arranged in a hierarchy corresponding to said hierarchy for said texture buffer, each of said nodes having at least one allocation flag such that there is a plurality of allocation flags for said nodes, each of said nodes directly corresponding to one of said quadrants of said texture buffer, and each of said nodes having a directional attribute corresponding to one of four orthogonal directions in a two-dimensional plane corresponding to said texture buffer, each of said orthogonal directions corresponding to the same relative position in said texture buffer for all quadrants thereof, a method comprising the steps of:
-
performing a comparison of said base texture size with said quadrant size for a texture map to be stored; traversing said quadtree responsive to said comparison with a positional preference corresponding to a pre-determined sequence of said orthogonal directions ordered as first, second, third, and fourth subdivision directions; setting at least one of said allocation flags for at least one of said nodes in said quadtree during said traversing to a state indicating a storage status of the quadrant corresponding to said node; and storing said texture map in said texture buffer responsive to said state of at least one of said allocation flags. - View Dependent Claims (28, 29, 30, 31, 32)
-
Specification