Dynamic view-dependent partitioning of structured grids with complex boundaries 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. The ability of this combination to exploit hardware exceeds that of parallel image order methods. 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 an algorithm to analyze the geometric structure of a grid boundary and extract knowledge about how the boundary impacts depth sorting and therefore image composition. We then show through examples how this knowledge may be applied to create a set of partitions that may be properly depth sorted.