Premium
Computing Dynamic Changes to BSP Trees
Author(s) -
Chrysanthou Y.,
Slater M.
Publication year - 1992
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/1467-8659.1130321
Subject(s) - computer science , tree (set theory) , representation (politics) , computation , partition (number theory) , binary tree , range (aeronautics) , algorithm , data structure , theoretical computer science , computer graphics (images) , mathematics , mathematical analysis , materials science , combinatorics , politics , political science , law , composite material , programming language
Abstract This paper investigates a new method for dynamically changing Binary Space Partition (BSP) trees. A BSP tree representation of a 3D polygonal scene provides an ideal data structure for rapidly performing the hidden surface computations involved in changing the viewpoint. However, BSP trees have generally been thought to be unsuitable for applications where the geometry of objects in the scene changes dynamically. The purpose of this paper is to introduce a dynamic BSP tree algorithm which does allow for such changes, and which maintains the simplicity and integrity of the BSP tree representation. The algorithm is extended to include dynamic changes to shadows. We calibrate the algorithms by transforming a range of objects in a scene, and reporting on the observed timing results.