OPTIMIZATION OF THE BINARY SPACE PARTITION ALGORITHM (BSP) FOR THE VISUALIZATION OF DYNAMIC SCENES

Abstract

This paper describes an improvement of the generation of BSP trees and its utilization in the visualization of dynamic polyhedral scenes. Dynamic BSP trees, a new six-level structure, are presented. Dynamic BSP trees are based on the inclusion of five different kinds of auxiliary planes in the generation of BSP trees. These planes are included in the structure before the polygons of the scene. In most cases the inclusion of polygons is performed in zero time by making use of precomputed BSP trees of the single objects of the scene. Dynamic BSP trees lead to a very significant reduction in the computation time of the BSP tree building and the posibility of its utilization at interactive speeds for complex scenes where both viewpoint and objects are dynamic. Description and pseudocode of the generation and dynamic modification management algorithms are included, along with a set of examples from a real implementation.