Binary Space Partitioning: |
| Henry Fuchs, Zvi Kedem and Bruce Naylor were all involved in the development of this algorithm. They based their work on the work of Schumacker, Brand, Gilliland and Sharp (see below for article names and dates). In 1980 when their first BSP paper, "On Visible Surface Generation by A Priori Tree Structures" SIGGRAPH '80 (Fuchs, Kedem and Naylor) appeared, computer graphic hardware was much less sophisticated, meaning that the hardware accelerated Z-buffers had not yet been created and there was no fast way to sort polygons of a game scene. So, that was one of the reasons that they worked on developing the BSP algorithm. |
| People in the game programming world started to use bsp in the early 1990s. Among the first games using this algorithm was Doom, developed by John Carmack and John Romero. After this game became very popular in the game world, several other games jumped on the binary space partitioning bandwagon, including Quake. |
| The history of this algorithm as given on the FAQ page ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html#20.txt
would be hard to improve upon. It is both quite amusing and somewhat informative. So, here is the complete text
from this page exactly as it appears on the above linked page. WHAT IS THE HISTORY OF BSP TREES? Overview Neophyte: How did the BSP-Tree come to be? Sage: Long ago in a small village in Nepal, a minor godling gave a special nut to the priests at an out of the way temple. With the nut, was a prophecy: When a group of three gurus, two with red hair, and the other who was not what he seemed, came to the temple on pilgrimage, if the nut was given unto them, and they nurtured it together, it would produce a tree of great benefit to mankind. Many years later, ... N: no! No! NO! The TRUE story. S: OK. Long ago (by computer industry standards) in a rapidly growing sunbelt city in Texas, a serendipitous convergence of unusual talents and personalities occurred. A brief burst of graphics wonderments appeared, and the convergence diverged under its own explosive production, leading to further graphics developments in several new locations. One of the wonderous paths followed ... N: ...No! The facts! S: Huh? Oh you want FACTS. Boring stuff? 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. |
| References for this page: Bsp FAQ: ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html#20.txt For more information on Henry Fuchs: http://www.cs.unc.edu/People/Faculty/Bios/fuchs.html Zvi Kedem's homepage has a great deal of information about him: http://www.zmkedem.com/nyu/main.html Binary Space Partitioning Trees and Polygon Removal in Real Time 3D Rendering: A Masters Thesis by Samuel Ranta-Eskola: http://www.gamedev.net/reference/programming/features/bsptree/bsp.pdf Doom information: http://5years.doomworld.com/interviews/johnromero/ |