BSP history
From CGAFaq
Henry Fuchs started teaching at an essentially brand new campus, the University of Texas at Dallas, in January 1975. He returned to Utah to complete his PhD the following summer. He returned to Dallas and taught for the 1975-76, 1976-77 and 1977-78 academic years, before being lured away to UNC-Chapel Hill.
Zvi Kedem joined this faculty in the fall of 1975. He was (and still is I suppose) a "theory person," but a special theory person. He is good at applying theory to practical problems.
Bruce Naylor had a bachelors degree from the U of Texas (Austin - "the real one"), in philosophy if I recall correctly. He had talked his way into a job at Texas Instruments in Dallas. (Something about philosophy makes you good in logic, which is really the same as computers...!?) He came to UTD to take some computer courses. He was spotted as "good" - probably by Kedem, but I can't swear to it - and convinced to become a full time graduate student.
Graphics, of course, is dazzling and wonderful. Henry was (is) full of energy and enthusiasm. It was natural that he attracted lots of the grad students. Kedem was a perfect complement, providing not only the formal rigor and proofs, but also the impetus to "write this part up" before going on to "the next thing and the next thing and ..." Kedem and Fuchs together (and most of the grad students) also found a new thrust in the CS theory community, called computational geometry, particularly interesting. Henry liked to talk about the Schumacker priority driven visible surface algorithm when the class got to that topic. He seemed to think there was something more to be done in that vein. Naylor being a grad student in search of a topic, looked into it.
The result was two SIGGRAPH papers and Naylor's PhD dissertation, and the launch of BSP-trees into the world. The two papers are
Fuchs, Kedem and Naylor, "Predeterming Visibility Priority in 3-D Scenes" SIGGRAPH '79, pp 175-181. (subtitled "preliminary report")
and
Fuchs, Kedem and Naylor, "On Visible Surface Generation by A Priori Tree Structures" SIGGRAPH '80, pp124-133.
The first paper isn't really BSP-trees, but rather the preliminary work which led to BSP-trees as the solution. The second paper is the "classic" starting point referenced in texts, etc.
Both reference Schumacker, Brand, Gilliland and Sharp, "Study for Applying Computer-Generated Images to Visual Simulation" AFHRL-TR-69-14, US AF Human Resources Lab, 1969
and the description of this algorithm more easily found in
Sutherland, Sproull and Schumacker, "A Characterization of Ten Hidden Surface Algorithms", ACM Computing Surveys, v 6, no 1, pp 1-55.
Naylor finished in 1981 (?) and went to Georgia Tech, and later to Bell Labs. He has continued to work on related and similar ideas with a variety of students and collaborators. Others have also taken the ideas in new directions.
Initial content for this page from the BSP tree FAQ, included with permission of its maintainer, Bretton Wade.
