Creation and spatial partitioning of mip-mappable geometry images

A Geometry Image (GIM) describes a regular polygonal surface mesh using a standard 2D image format without the need for explicit connectivity information. Like many regular or semi-regular surface representations, GIMs lend themselves well to a number processing tasks performed in computer graphics. It has been suggested that GIMs could provide improvements within real-time rendering pipelines through straightforward localised surface processing and simple mip-map based level-of-detail. The simplicity of such algorithms in the case of GIMs makes them highly amenable to user transparent implementation in graphics hardware or programming libraries, shifting implementation responsibility from the application programmer and reducing the processing load on the CPU. However, these topics have received limited attention in the literature. This thesis examines a number of issues regarding mip-mapping and localised processing of GIMs. In particular, it focuses on the creation of mip-mappable multi-chart GIMs and how to spatially partition and cull GIMs such that mip-mapping and localised processing can be performed effectively. These are important processing tasks that occur before rendering takes place, but influence how mip-mapping and localised processing can be implemented and utilised during rendering. Solutions to these tasks that consider such influences are, therefore, likely to facilitate simple and effective algorithms for mip-mapping and localised processing of GIMs that are amenable to hardware implementation. The topics discussed in this thesis will form a basis for future work on low level geometric mip-mapping and localised processing of GIMs in real-time graphics pipelines. With respect to creating mip-mappable GIMs, the thesis presents a method for automatic generation of polycube parameter domains and surface mappings that can be used to create multi-chart GIMs with square or rectangular charts. As will be discussed, these GIMs provide particular advantages for mip-mapping compared to multi-chart GIMs with irregular shaped charts. The method casts the polycube generation problem as a coarse topology preserving voxelisation of the surface that simultaneously aligns the surface with the voxel set boundary. This process produces both the polycube and an initial surface-to-polycube mapping. Theorems for piecewise construction of well-composed voxel sets are also presented that facilitate a piecewise implementation of the polycube generation algorithm and support the topological guarantees it provides. This method improves on previous methods for polycube generation which require significant user interaction. For spatial partitioning of GIMs the thesis introduces the concept of locality masks, bit masks partitioning parameter space. The method stores a 2D bit mask at each spatial node which identifies the set of GIM samples inside the node’s spatial range. Like GIMs the locality masks support mip-mapping through simple image down-sampling. By unifying the masks of all nodes that pass a spatial query processing can be performed globally on the unculled set of primitives rather than on a node-by-node basis, promoting a more optimised order in which to performed localised processing. Locality masks are also well suited to compression and provide a bandwidth efficient method of transferring a list of indexed rendering primitives. The locality masks method is compared to other methods of partitioning and culling GIMs in various ways and their suitability for rendering and other task is analysed