Talk:Binary space partitioning

Unnamed section

A bunch of quotes... hmm, this is a bad article. Who's up for helping rewrite it? Fredrik 22:45, 29 May 2004 (UTC)

I rewrote the intro and, time permitting, will begin to work on the rest of the article. cbraga 02:30, Jun 1, 2004 (UTC)

Rewritten intro

Good job, but this is NOT an intro of an article about BSP trees, rather a section about their applications (placed accordingly). Mikkalai 03:10, 1 Jun 2004 (UTC)

Thanks, but don't you think an introduction should begin describing the applications and the reasons why the algorithm is interesting? cbraga 03:29, Jun 1, 2004 (UTC)

No. This would be not an encyclopedic style (at least as accepted here). You start from general-purpose definition, right to the point, and summary. Then you proceed with the detailed def. Then the rest. I suggest you to read the Inverted pyramid article. Mikkalai 04:39, 1 Jun 2004 (UTC)

I agree that it would be better to start with the general purpose definition, but you're actually shooting yourself on the foot by invoking the inverted pyramid, since that would come to be pretty much how I'd done. I think the paragraphs I wrote would be pretty at home right after the current introduction. cbraga 13:11, Jun 1, 2004 (UTC)

move to binary space partitioning?

Correct me if I'm wrong, but I'm under the impression that the process as a whole is named Binary Space Partitioning, and that Binary Space Partition would refer to a single partition generated in that process. Anyone objects to moving this page to Binary space partitioning? --cbraga 17:15, Jun 1, 2004 (UTC)

That seems right to me. Fredrik (talk) 17:33, 1 Jun 2004 (UTC)

Painter's algorithm

BSP trees, however, solve both these problems by splitting up objects and ordering them so that the painter's algorithm will draw them correctly without need of a Z-buffer and without overdraw.

This seems to be in error to me. Using a BSP does not eliminate overdraw with the painter's algorithm. The only point, if I'm not mistaken, about using BSP combined with the painter's algorithm is that it provides an extremely fast way to sort the polygons by distance. Using Z-buffering with a front-to-back rendering method is what eliminates overdraw. Fredrik (talk) 17:42, 1 Jun 2004 (UTC)

No. BSP trees do remove overdraw by the painter's algorithm. If you look at the painter's algorithm page you'll see an example of a scene that won't draw correctly. One purpose of BSP is to convert that scene into one which will draw correctly by splitting overlapping polygons into non-overlapping polygons. Another purpose is to provide an extremely fast way to sort the polygons. Scenes drawn using BSP do not require z-buffers. When z-buffers are used they are only filled by the BSP scene to be used later, when drawing movable objects such as doors. Note that Doom's doors are not considered movable since doom's map are 2D and doom's bsp is 2d. Quake's doors and mosters are movable and need to be merged into the scene using the z-buffer provided by the rendering of the background. --cbraga 18:04, Jun 1, 2004 (UTC)

On second thought, you're at least partly correct, since that would depend on the particular implementation of the algorithm. But at lease in Doom's and Quake's case they are used to eliminate overdraw. If the trees were being used solely for other purposes (such as collision detection or ray tracing) overdraw would not be an issue and would not need to be taken into consideration when building the trees. cbraga 18:22, Jun 1, 2004 (UTC)

The point of the painter's algorithm is that you draw back to front. This means you'll draw several times to each pixel (or am I using the wrong word here?). The BSP FAQ describes what I'm saying here (section "How do you remove hidden surfaces with a BSP Tree?"). Doom doesn't use the painter's algorithm since it draws front-to-back. Fredrik (talk) 18:27, 1 Jun 2004 (UTC)

Yes, it seems you are correct. BSPs will never elliminate overdraw, just assure that the painter's algorithm will work correctly, plus provide a fast way to sort the polygons. I'll correct the article.

But in Doom's case there's no overdraw since, drawing front to back, it draws beginning at the ceiling and the floor, moving away from the viewer and towards the center of the screen. There's no overdraw since it will never overwrite a pixel from a close source with one from a distant source. And, it's very simple to determine what part of a sector (if any) is visible based on the last pixels drawn. It's a sort of reverse painter's algorithm where you never draw over what you have already drawn. It is simple in Doom's case since its maps are essentialy 2D, but that would be undoable in full 3D. --cbraga 19:12, Jun 1, 2004 (UTC)

Solid Planar BSP

The article, specifically the definition of a BSP, refers to a solid planar BSP. A BSP need not describe convex hulls, nor need it be partitioned by planes.

For example, consider the following. Enclose every primitive in a sphere (specifically the smallest sphere that will encapsulate the primitive). Merge each sphere with the sphere closest to it to create a new sphere, merging each sphere only once. These new spheres are the parents of their respective children. Iterate the process until only one sphere remains. We now have a spherical BSP. It has three advantages over a planar BSP: 1) primitives are not subdivided, 2) it can be generated extremely fast (ie at runtime, as opposed to pre-processing), 3) new primitives can be quickly added into the tree on-the-fly. While it cannot be used to perfectly sort polygons (which is not an issue with hardware rendering), it is efficient at determining which primitives lie within the view frustum.

Also the article does not discuss leafy verses nodey trees. Leafy being that the geometric primitives are stored in the leafs, where in nodey trees they are stored in the nodes. The difference has repercussions on collision detection. Also nodey trees infer that the geometric primitives themselves were used to partition the BSP.

Again, the Generation section is planar-centric, yet it does not mention where potential partitions are chosen from. The simplest method (and one required for a nodey BSP) is to use the planes of the polygons of the mesh we are generating a BSP for. This only works well for specific types of geometry, such as buildings with many perpendicular planes. When this technique is applied to geometry such as a heightmap, it fails miserably, causing a massive amount of polygon subdivision. The polygon count can easily increase by a factor of 10 or more. In this case choosing partition planes using another method - for example using planes that lie on the edge of a polygon that are perpendicular to the normal - work much better.

--Dan East 01:17, Mar 14, 2005 (UTC)

What you are describing is not a BSP tree, but a set of hierarchical bounding volumes. --Pezezin 13:44, 28 September 2006 (UTC)

It's possible to write Doom, Quake etc without a BSP

Beforehand (or dynamically) you carve up the world into (mostly disjoint) convex objects. For each non-solid border of each object you store the convex object on the other side, as well as a list of the objects that it (partially) contains.

During the game you don't just store the position of each movable object, but also the convex object(s) that contains (parts of) it (dynamic programming). Then, when the object moves (or shoots or looks at something), you first makes sure that it does not hit an object that is (partially) contained by the current convex object. If it's not, you calculate through which border the representative line segment will leave the current convex object(s). If the border is solid, the line is terminated, and if the border is not, the line is traced through the next convex object and so on.

This algorithm is quite efficient as long as the convex objects are mostly disjoint.

In the highly inlikely case that you do not know inside which object you are currently located, you can discover that by tracing a line from any known place. But this never happens in Doom or Quake. -- Nic Roets 15:22, 24 August 2005 (UTC)

BSP Tree Generation Demo

That demo is not very good at showing how the tree is generated. For one, the tree is easily made heavy on one side or another (not something which would happen in a proper compiler). Also, it does a poor job of showing how the technique affects lighting (everything is pretty much the exact same). I recommend removing the link because it conveys partial information to the reader which will lead to incorrect assumptions.

The link in question: http://symbolcraft.com/graphics/bsp/ Located: http://wiki.riteme.site/wiki/Binary_space_partitioning#Generation

Dragon Hilord 21:13, 15 August 2006 (UTC)

Needs implementation

This article needs to show programmatic implementation of this process I think. If I'm wrong than don't be hesitant to speak... —The preceding unsigned comment was added by 69.137.157.249 (talk) 10:53, 28 March 2007 (UTC).

A full implementation is hard make...if you want examples of bsp tree usage check quake 3 source code: http://www.idsoftware.com/business/techdownloads/ You can get it there free with a GPL license.85.204.189.171 (talk) 14:41, 5 June 2008 (UTC)

generation section

Could someone explain these sentences please? "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."

Is this the explanation how the algorithm for this example is supposed to work?

What particular case? The example or the last step? What polygon? The one the example startet with? "and intersected none of its segments" What is a segment, which line doesnt intersect any segment (in which step)? Thank you! --Novar08 (talk) 14:55, 28 November 2008 (UTC)

I've removed this section of the article and parked it here. It seems to have been added out of confusion between BSP and convex decomposition. The first paragraph discusses partitioning a concave polygon into multiple convex polys. Though this can use a BSP tree when trying to select preferable partitions, it is not needed to find a convex decomposition when partitioning between vertices since in that case the order of partitioning has no bearing. It also asserts that if a partion line intersected a segment then you would have to split it, which is not only unnecessary, but inadvisable. In such a case you have only to select an alternative partition (which is mathematically guarenteed) (see: Polygon triangulation. I feel as though these convex polys might have been confused with the convex sets that a BSP is guarenteed to produce. The latter paragraph is mostly a restatement of the paragragh previous to this in the same section (which I've left in). What follows is the offending section:

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 they find a good compromise. They 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. Thus producing a tree usually requires long computations.

86.5.179.220 (talk) 22:59, 26 April 2012 (UTC)

BSP in Doom?

I don't think the Doom engine used BSP. I may have misunderstood, but space partitioning is a technique used when dealing with 3D geometry, and Doom did not store it's level data as 3D geometry. I know that Quake used BSP for it's levels, but am fairly sure Doom did not. 86.14.204.223 (talk) 13:21, 15 December 2008 (UTC)

Sorry, my bad. I've just read the Doom engine article. I had the wrong end of the stick completely. I'll read more carefully next time. 86.14.204.223 (talk) 13:27, 15 December 2008 (UTC)

The original Doom *did* use BSP. It partitioned a 2d plane with half-spaces defined by lines. It used these to rapidly locate the sectors objects were in, and in the case of the player's view, cull the walls that needed to be tested by raycasting. — Preceding unsigned comment added by 217.42.115.154 (talk) 11:03, 17 February 2016 (UTC)

Relationship with other partitioning structures unclear

I have added a {{unreferenced section}} template in the section Other space partitioning structures, because I think a few questions have to be sorted out. Firstly, I'm confused about whether binary space partitioning is a specific algorithm, as the article seems to say, or if it is a class of algorithms, as Template:CS trees seems to say. Aren't both binary space partitioning trees and all trees listed after it actually spatial data partitioning trees, which is a branch if trees listed two rows down? Secondly, the section I put the {{unreferenced section}} template in contains a relationship table, which lists binary space partition trees, quadtrees and octrees, but not kd-trees. Why not kd-trees, don't they use only one dividing plane too, just like binary space partition trees?

Also, I can shortly mention that the section seemed to say that quadtrees and octrees were the most useful in subdividing 2- and 3-dimensional spaces respectively; since I couldn't agree with that I had to change it to that they were usefull for subdividing 2- and 3-dimensional spaces respectively. —Kri (talk) 00:00, 24 July 2011 (UTC)

Substantial edits

I've made some substantial edits the article, while keeping the same general sections as before. This was primarily motivated by the the lack of detail in the previous revisions making it hard to understand what binary space partitioning really involved, without going to the references. I've tried to cover (at least briefly) as many of the points raised previously on the talk page as possible. I'm aware that the new examples relate in particular to BSP as proposed by Fuchs et al. (1980), but I hope it is clear from the article that this is one of many related algorithms using BSP. Still some work to do, on referencing in particular (the existing 'Timeline' section and additional references seem to be based heavily on a Bachelors dissertation (cited as WINTER99)). Chrisjohnson (talk) 00:50, 9 June 2012 (UTC)

BSP as a generalization of binary search trees

I know there's no original research allowed, but is there anything out there about how binary search trees are a subset of BSP trees? Here's the gist: the BSP is an ordered binary tree based on the result of a dot product of a point (4d vector with an xyz in 3d space and its w-component as 1) and a plane (4d vector representing the coefficients in ax + by + cz + d = 0). Take it down to 2d, the dot product is now between a 2d point and the line ax + by + c = 0. Take that down to 1d, and it's a the dot product of a scalar and the value ax + b = 0, both of which are just scalar values, and so is the normal definition of the key of a binary search tree. Therefore BSP trees are binary search trees which order values in N-dimensional space by using an (N-1)-dimensional partitioning subspace, of which binary search trees are the 1-dimensional example. It's a very nice way to think of the BSP process and how it ties into the more generic data structures.70.120.71.220 (talk) 04:55, 14 February 2013 (UTC)

Brush Section?

Why is the "Brush" section relevant to this article? It isn't clear to me at all. It looks like it was merged from its own article--anybody know why? 64.58.7.42 (talk) 18:04, 11 December 2015 (UTC)

Agreed. At bare minimum the term "brush" originates at least from idtech 2 (Quake), on which GoldSrc was originally based. Although games have used BSPs extensively in the past, this is not anywhere near as relevant to the article as, for example, the fact that BSP provide an O(log N) point query, which isn't mentioned anywhere in the article. — Preceding unsigned comment added by 217.42.115.154 (talk) 11:00, 17 February 2016 (UTC)

As a professional in this field (research and education), I would prefer to see the "Brushes" section removed. It's irrelevant to the subject and only serves to confuse the presentation.130.236.67.113 (talk) 07:11, 25 February 2016 (UTC)