Dynamic view-dependent partitioning of structured grids for object-order rendering techniques

Object-order rendering techniques present an attractive approach to run-time visualization of structured grid data, particularly when combined with a parallel rendering paradigm such as image composition. Techniques such as splatting achieve better speeds than image-order techniques by projecting pre-integrated kernels only from sample points. However, certain configurations of grid boundaries prevent composition from being performed correctly. In particular, when the boundary between two partitions contains concave sections, the partitions may no longer be depth sorted correctly, a requirement for some visualization techniques such as direct volume rendering. This occurs because the concave boundary prevents even the simple ordering of two adjacent partitions. If the data may be repartitioned such that it can be depth sorted correctly, then an image composition approach is a viable option. To facilitate such an operation, we present the Tangent-Cap Partitioning algorithm to analyze the geometric structure of a grid boundary, extract knowledge about how the boundary impacts depth sorting, and create a set of partitions that can be properly depth sorted. The partitioning algorithm identifies cavities, voids and holes in the grids surface. These components are then classified into front-facing and back-facing patches. The front-facing patches form the basis of view-dependent volumes to which the data points of the grid are assigned. The set of partitions associated with each volume plus the original partition are then able to be depth sorted. As a further optimization, we investigate the use of precomputed characteristic views to reduce the run-time performance impact of the partitioning algorithm. Characteristic views allow a dictionary of partitionings to be calculated as a preprocessing step. This dictionary is then referenced at run-time using a best-fit mapping from the current viewpoint. An adaptive version of the characteristic view algorithm uses non-uniform sampling to concentrate the precomputed views in high frequency areas using a user-specified quality factor to control the sampling density.