Jump to content

  • Log In with Google      Sign In   
  • Create Account

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.

  • You cannot reply to this topic
2 replies to this topic

#1 Gammastrahler   Members   -  Reputation: 150

Like
0Likes
Like

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



Sponsor:

#2 Ohforf sake   Members   -  Reputation: 1832

Like
7Likes
Like

Posted 13 July 2014 - 05:48 AM

Short answer: yes

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.

#3 Gammastrahler   Members   -  Reputation: 150

Like
0Likes
Like

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.



PARTNERS