ABSTRACT
Certain data structures seem to pop up repeatedly in graphics applications, perhaps because they address fundamental underlying ideas such as surfaces, space, and scene structure. This chapter explains about several basic and unrelated categories of data structures that are among the most common and useful: mesh structures, spatial data structures, scene graphs, and tiled multidimensional arrays. Various forms of this data structure are ubiquitous in graphics applications because they are so useful in managing objects and transformations. All new graphics application program interface are designed to support scene graphs well. Originally developed to help paging performance in applications where graphics data needed to be swapped in from disk, such structures are crucial for memory locality on machines regardless of whether the array fits in main memory. A good mesh data structure should be reasonably compact and allow efficient answers to all adjacency queries.
