Efficient Object BSP Trees

In this paper we investigate Object Oriented Binary Space Partitioning. The Binary Space Partition Tree (BSP-Trees) is widely used and effective data structure for solid modeling and hidden surface removal. We present algorithms for efficiently constructing Object BSP Trees (OBSP) in 2-Dimensions. The term object arises since the construction of our tree utilizes the property of hierarchical ellipsoid covers. Besides being object-oriented, the major advantage of the OBSP trees is the reduction in the fragmentation of the scene. This paper formulates algorithms and data-structures for representing polyhedral objects and operations such as composition, deletion and motion of objects based on Object Hierarchy using the modified version of the traditional BSP tree. We improve on the design presented in [11]. Implementation details are presented which show increased efficiency resulting through our approach.