要用hammer4.1
===非此吧范围,封水===

-,-求生之路2呢？

hl系列都是bsp不管是goldsrc引擎还是source引擎

插

我一直以为bsp仨字母是乱打的

Binary space partitioning
For the .BSP file extension, see BSP (file format).
Binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.
Originally, this approach was proposed in 3D computer graphics to increase the rendering efficiency. Some other applications include performing geometrical operations with shapes (constructive solid geometry) in CAD, collision detection in robotics and 3D computer games, and other computer applications that involve handling of complex spatial scenes.
Contents [hide]
1 Overview
2 Generation
3 Rendering a scene with visibility information from the BSP tree
4 Other space partitioning structures
5 Timeline
6 References
7 External links
[edit] Overview
In computer graphics it is desirable that the drawing of a scene be both correct and quick. A simple way to draw a scene is the painter's algorithm: draw it from back to front painting the background over with each closer object. However, that approach is quite limited since time is wasted drawing objects that will be overdrawn later, and not all objects will be drawn correctly.
Z-buffering can ensure that scenes are drawn correctly and eliminate the ordering step of the painter's algorithm, but it is expensive in terms of memory use. BSP trees will split up objects so that the painter's algorithm will draw them correctly without need of a Z-buffer and eliminate the need to sort the objects; as a simple tree traversal will yield them in the correct order. It also serves as base for other algorithms, such as visibility lists, which seek to reduce overdraw.
The downside is the requirement for a time consuming pre-processing of the scene, which makes it difficult and inefficient to directly implement moving objects into a BSP tree. This is often overcome by using the BSP tree together with a Z-buffer, and using the Z-buffer to correctly merge movable objects such as doors and monsters onto the background scene.
BSP trees are often used by 3D computer games, particularly first-person shooters and those with indoor environments. Probably the earliest game to use a BSP data structure was Doom (see Doom engine for an in-depth look at Doom's BSP implementation). Other uses include ray tracing and collision detection.
[edit] Generation
Binary space partitioning is a generic process of recursively dividing a scene into two until the partitioning satisfies one or more requirements. The specific method of division varies depending on its final purpose. For instance, in a BSP tree used for collision detection, the original object would be partitioned until each part becomes simple enough to be individually tested, and in rendering it is desirable that each part be convex so that the painter's algorithm can be used.
The final number of objects will inevitably increase since lines or faces that cross the partitioning plane must be split into two, and it is also desirable that the final tree remains reasonably balanced. Therefore the algorithm for correctly and efficiently creating a good BSP tree is the most difficult part of an implementation. In 3D space, planes are used to partition and split an object's faces; in 2D space lines split an object's segments.


The following picture illustrates the process of partitioning an irregular polygon into a series of convex ones. Notice how each step produces polygons with fewer segments until arriving at G and F, which are convex and require no further partitioning. In this particular case, the partitioning line was picked between existing vertices of the polygon and intersected none of its segments. If the partitioning line intersects a segment, or face in a 3D model, the offending segment(s) or face(s) have to be split into two at the line/plane because each resulting partition must be a full, independent object.
1. A is the root of the tree and the entire polygon
2. A is split into B and C
3. B is split into D and E.
4. D is split into F and G, which are convex and hence become leaves on the tree.Since the usefulness of a BSP tree depends upon how well it was generated, a good algorithm is essential. Most algorithms will test many possibilities for each partition until finding a good compromise and might also keep backtracking information in memory so that if a branch of the tree is found to be unsatisfactory other alternative partitions may be tried. Therefore producing a tree usually requires long computations.
BSP trees were also used to represent natural images. Construction methods of BSP trees of images were first introduced as efficient representations, where only a few hundred nodes can represent an image that normally require hundreds-of-thousands of pixels. Fast algorithms were also developed to construct BSP trees of images using computer vision and signal processing algorithms. These algorithms in conjunction with advanced entropy coding and signal approximation approaches were used to develop image compression methods.
[edit] Rendering a scene with visibility information from the BSP tree
BSP trees are used to improve rendering performance in calculating visible triangles for the painter's algorithm for instance. The tree can be traversed in linear time from an arbitrary viewpoint.
Since a painter's algorithm works by drawing polygons farthest from the eye first, the following code recurses to the bottom of the tree and draws the polygons. As the recursion unwinds, polygons closer to the eye are drawn over far polygons. Because the BSP tree already splits polygons into trivial pieces, the hardest part of the painter's algorithm is already solved - code for back to front tree traversal.[1]
traverse_tree(bsp_tree* tree, point eye)
{
   location = tree->find_location(eye);
   if(tree->empty())
     return;
   if(location > 0)       // if eye in front of location
   {
     traverse_tree(tree->back, eye);
     display(tree->polygon_list);
     traverse_tree(tree->front, eye);
   }
   else if(location < 0) // eye behind location
   {


1987 Thibault and Naylor described how arbitrary polyhedra may be represented using a BSP tree as opposed to the traditional b-rep (boundary representation). This provided a solid representation vs. a surface based-representation. Set operations on polyhedra were described using a tool, enabling Constructive Solid Geometry (CSG) in real-time. This was the fore runner of BSP level design using brushes, introduced in the Quake editor and picked up in the Unreal Editor.
1990 Naylor, Amanatides, and Thibault provide an algorithm for merging two bsp trees to form a new bsp tree from the two original trees. This provides many benefits including: combining moving objects represented by BSP trees with a static environment (also represented by a BSP tree), very efficient CSG operations on polyhedra, exact collisions detection in O(log n * log n), and proper ordering of transparent surfaces contained in two interpenetrating objects (has been used for an x-ray vision effect).
1990 Teller and Séquin proposed the offline generation of potentially visible sets to accelerate visible surface determination in orthogonal 2D environments.
1991 Gordon and Chen [CHEN91] described an efficient method of performing front-to-back rendering from a BSP tree, rather than the traditional back-to-front approach. They utilised a special data structure to record, efficiently, parts of the screen that have been drawn, and those yet to be rendered. This algorithm, together with the description of BSP Trees in the standard computer graphics textbook of the day (Foley, Van Dam, Feiner and Hughes) was used by John Carmack in the making of Doom.
1992 Teller’s PhD thesis described the efficient generation of potentially visible sets as a pre-processing step to acceleration real-time visible surface determination in arbitrary 3D polygonal environments. This was used in Quake and contributed significantly to that game's performance.
1993 Naylor answers the question of what characterizes a good bsp tree. He used expected case models (rather than worst case analysis) to mathematically measure the expected cost of searching a tree and used this measure to build good BSP trees. Intuitively, the tree represents an object in a multi-resolution fashion (more exactly, as a tree of approximations). Parallels with Huffman codes and probabilistic binary search trees are drawn.
1993 Hayder Radha's PhD thesis described (natural) image representation methods using BSP trees. This includes the development of an optimal BSP-tree construction framework for any arbitrary input image. This framework is based on a new image transform, known as the Least-Square-Error (LSE) Partitioning Line (LPE) transform. H. Radha' thesis also developed an optimal rate-distortion (RD) image compression framework and image manipulation approaches using BSP trees.
[edit] References
[FUCH80] H. Fuchs, Z. M. Kedem and B. F. Naylor. “On Visible Surface Generation by A Priori Tree Structures.” ACM Computer Graphics, pp 124–133. July 1980.
[THIBAULT87] W. Thibault and B. Naylor, "Set Operations on Polyhedra Using Binary Space Partitioning Trees", Computer Graphics (Siggraph '87), 21(4), 1987.
[NAYLOR90] B. Naylor, J. Amanatides, and W. Thibualt, "Merging BSP Trees Yields Polyhedral Set Operations", Computer Graphics (Siggraph '90), 24(3), 1990.
[NAYLOR93] B. Naylor, "Constructing Good Partitioning Trees", Graphics Interface (annual Canadian CG conference) May, 1993.
[CHEN91] S. Chen and D. Gordon. “Front-to-Back Display of BSP Trees.” IEEE Computer Graphics & Algorithms, pp 79–85. September 1991.
[RADHA91] H. Radha, R. Leoonardi, M. Vetterli, and B. Naylor “Binary Space Partitioning Tree Representation of Images,” Journal of Visual Communications and Image Processing 1991, vol. 2(3).
[RADHA93] H. Radha, "Efficient Image Representation using Binary Space Partitioning Trees.", Ph.D. Thesis, Columbia University, 1993.
[RADHA96] H. Radha, M. Vetterli, and R. Leoonardi, “Image Compression Using Binary Space Partitioning Trees,” IEEE Transactions on Image Processing, vol. 5, No.12, December 1996, pp. 1610–1624.
[WINTER99] AN INVESTIGATION INTO REAL-TIME 3D POLYGON RENDERING USING BSP TREES. Andrew Steven Winter. April 1999. available online
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised edition ed.). Springer-Verlag. ISBN 3-540-65620-0.   Section 12: Binary Space Partitions: pp. 251–265. Describes a randomized Painter's Algorithm.
Christer Ericson: Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology). Verlag Morgan Kaufmann, S. 349-382, Jahr 2005, ISBN 1-55860-732-3
1.^ Binary Space Partition Trees in 3d worlds