A Walk through BSP Trees
Chin Norman, Department of Computer Science Columbia University New York, New York. E-mail address: nc@cs.columbia.edu
Introduction
Binary space-partitioning (BSP) trees are data structures that allow for fast visible-surface determination in environments where the viewer moves while the polygonal objects remain static, as in interactive walkthroughs. This gem describes the construction of BSP trees and their traversal, which generates polygons in a sorted order suitable for rendering. It concludes with an efficient viewer/object collision detection algorithm based upon this versatile data structure.
Background
One solution to the visible-surface problem is to render a scene’s polygons in back-to-front ...
Get Graphics Gems V (IBM Version) now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
