System and method for fast polyhedral cell sorting

Abstract

The visibility ordering of polyhedral cells is efficiently determined by building an ordering graph, comprising oriented edges between two cells. Each edge (A,B) corresponds to the fact that cell A has to be projected, or rendered, before B. A set of ordering relations and rules that can be shown to generate, if one exists, a global ordering of the polyhedral cell complex. Three different types of edges are used to accomplish this: MPVO, BSP and PPC edges. MPVO edges exist between two cells that share a face. To define the BSP edges, a BSP-tree of the boundary faces of the cell complex is constructed. During this construction, some of the boundary faces of the cells will be 'cut' by the BSP-tree 'extended' faces, into multiple pieces. If C is the boundary cell, and c′, c″, and so on, are the pieces of its boundary faces, the BSP_edge (c′, C) is defined to mean that cell C can only be projected after c′ has been projected by the BSP. A cell C is in the PPC if one of the pieces that compose it, say c′, has been projected by the BSP, but there exist other pieces of cell C that have not been projected. In this case, additional checks are done to ensure cells are not being projected out of order. This is accomplished by performing ‘ray shooting’.