Boolean operations on surfel-bounded objects using constrained BSP-trees

Point-based modeling and rendering is an active area of research in Computer Graphics. The concept of points with attributes (e.g. normals) is usually referred to as surfels, and many algorithms have been devised to their efficient manipulation and rendering. Key to the efficiency of many methods is the use of partitioning schemes, and usually axis-aligned structures such as octrees and KD-trees are preferred, instead of more general BSP-trees. In this work we introduce a data structure called Constrained BSP-tree (CBSP-tree) that can be seen as an intermediate structure between KD-trees and BSP-trees. The CBSP-tree is characterized by allowing arbitrary cuts as long as the complexity of its cells remains bounded, allowing better approximation of curved regions. We discuss algorithms to build CBSP-trees using the flexibility that the structure offers, and present a modified algorithm for boolean operations that uses a new inside-outside object classification. Results show that CBSP-trees generate fewer cells than axis-aligned structures.