I have always been fascinated by visibility problems arising in both computational geometry and computer graphics. In computer game development, an area I watch fervently, we have seen an enormous growth in the number and type of 3D entertainment products. The quality of these titles are often judged not just by their entertainment value, but also on the sheer performance of their graphics engine. While inexpensive 3D hardware is capable of rasterizing (or drawing) more polygons than ever before, a basic problem still remains: How do we represent complex 3D worlds for efficient rendering. The BSP tree proves to be a very practical data-structure for performing visibility amongst static data sets, when given an arbitrary viewing position. As a result, it has been used by all of the best 3D entertainment products to date.
The focus of my talk will begin with a introduction to general-case BSP trees, and we will see how these magnificent structures can be used to store models which can then be depth-sorted and rasterized in linear time. From here, I will turn my discussion to a new result from the FOCS '96 Proceedings, which examines the construction of BSP trees when we are confined to 2D rectangles in axis-aligned 3D space.
(Based on Material By: Foley, et al. [Computer Graphics: Principles and Practice 2nd Ed.], Abrash [a talk at CGDC '96: the Computer Game Developer's Conference], and Agarwal, Grove, Murali, and Vitter [FOCS '96: "BSP Trees for Fat Rectangles"])