Talk:Binary space partitioning

From Wikipedia, the free encyclopedia

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)

Contents 1 Rewritten intro 2 move to binary space partitioning? 3 Painter's algorithm 4 Solid Planar BSP 5 It's possible to write Doom, Quake etc without a BSP 6 BSP Tree Generation Demo 7 Needs implementation

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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://en.wikipedia.org/wiki/Binary_space_partitioning#Generation

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

[edit] 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).