Web Clustering: A new approach to space partitioning.
Alexander C. James, AM Day · 1999
The Binary Space Partitioning Tree has provided a sound structure on which to build rendering algorithms since the early eighties. In this paper, we manipulate the BSP tree in a new way, and subsequently morph the algorithm and data structure resulting in a new, very different, technique. Our algorithm is restricted to two-dimensions in this paper and thus our input is line segments; our aim is to decrease the line segment splitting associated with BSP trees. We present the Web Clustering algorithm with a run-time competitive to Binary Space Partitioning in random scenes and better with structures that incorporate empty passageways or `void' regions. We show how buildings, for example, can be divided by their corridors with very few splits. Our method changes a fundamental part of BSP generation, leading to the abolition of the binary restriction. This allows us to branch our partitioning of the environment where a BSP partition would slice through the scene, regardless of obstacles. I...