Binary Space Partitioning Tree

divide space in halves until a half contains just one thing

A binary space partition is a recursive division of space into halves.  A binary space partitioning tree is a binary tree, each node of which contains a subdivision of the space, and the leaves of which contain subdivisions which contain only one object (or a part thereof).  Rendering a scene is then a matter of rendering the leaves of the BSP tree.  

In the movies shown here, the lines which subdivide the space into halves are extended edges of the objects themselves.  These movies were made by Donald McElheny, '07, during the summer of 2005.

The first two movies show the partitioning of the space and the formation of the BSP tree.  One pauses to pose questions to the observer at key points in the movie.

The second two movies show the use of a BSP tree.  The query is:  "which objects in the space are intersected by a line drawn in the space?"  One of the movies pauses to pose questions to the viewer.

Remember the guidelines for the use of these movies.