Quadrant-based two-dimensional memory manager

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.

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.