Web Clustering: A New Approach to Space Partitioning

A. James and A.M. Day

School of Information Systems, University of East Anglia,
University Plain, Norwich, Norfolk, NR4 7TJ. England.
aj@sys.uea.ac.uk, amd@sys.uea.ac.uk

ABSTRACT

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. In terms of the overall rendering times, the algorithm reduces line segment splitting compared to the BSP technique. Preprocessing is also attractive since it exploits the characteristics of structured scenes and is thus a faster divide and conquer technique.

keywords
binary-space partitioning, hidden-surface removal, portals, scene clustering

Hosted by Graphics & Media Lab. http://graphics.cs.msu.su

mailto: Webmaster