• FEATURED

View more

View more

View more

Image of the Day Submit

IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

BSP Tree Question

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

2 replies to this topic

#1Gammastrahler  Members

Posted 13 July 2014 - 04:33 AM

Hi,

i want to use a BSP tree for processing boolean operations on solids (CSG).

In theory, i have understood the algorithm, but what actually confuses me is the step when selecting the splitting polygons for the BSP construction process. For example, if i have a cube, do i need a split plane / left and right nodes for each side of the cube?

Any help would be appreciated.

Regards

Gammastrahler

#2Ohforf sake  Members

Posted 13 July 2014 - 05:48 AM

POPULAR

Long answer: Consider a rectangle in 2D (works the same, but has less sides).

Every node splits the space into two halves. Leaf nodes labels it's space as empty or solid.

So for a rectangle
   +-------+
|       |
|       |
|       |
+-------+

you could start by choosing the left side as the first splitting plane (in 2D a splitting line):
  A | B
|
|
+-------+
|       |
|       |
|       |
+-------+
|
|

So your root node now has a splitting plane and two children A and B. A will remain a leaf node and label the left hand side as empty.
B we could now split further by, for example, the top edge:
  A |
|
| [B] C
+-------+------------
|       | [B] D
|       |
|       |
+-------+
|
|

so the node B now has two children C and D. C again labeling it's space as empty. Now after splitting D for example by the right hand side we get:
   A |
|
| [B] C
+-------+------------
|       |
|       |
|       |
+-------+
|       |
|       |
|       |
|[B,D] F|[B,D] E

and there you have it: one splitting plane on the left, and further down the tree one on the right. E, which is a child node of D, which again is a child node of B, denotes the right hand side as empty. Now we can finish things up by splitting F
   A |
|
| [b] C
+-------+------------
|       |
|       |
|B,D,F]H|
+-------+
|B,D,F]G|
|       |
|       |
|       |[B,D] E

and labeling G as empty and H as solid.

And there you have it, a BSP tree with a total of 4 splits, one for each side.

#3Gammastrahler  Members

Posted 13 July 2014 - 06:01 AM

Thank you for the detailed description

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.