I am trying to understand BSP trees but I find the book I am reading to be somewhat unclear. Most stuff online just reiterates what my book says. For now I am assuming we are talking about 2D. I am using the method where you choose one of your lines as the initial dividing plane/root node.
1). When creating the bsp tree I randomly choose a line. If that line intersects any other lines then I divide that line into two lines (for instance line A becomes line A1 and A2). Do I just need to do this for the root node only or do I need to do this for every line in the bsp tree?
What if I am trying to create the tree and I have two lines that are co-planar? For instance say I have line A and because of the position of some other lines line A is divided in more than one place. How do I place the different parts of line A (A1, A2, A3) into the bsp tree?
Play with that until we figure something out… I’m just as lost as you are, but I figured I’d look into it as well. I’ll report back with anything I come up with.
step 1: pick a line
step 2: separate all the remaining lines into 2 groups, one group on either side of the original line (splitting lines as needed so that each group is completely on one side of the first line)
step 3: for each of the 2 groups you just made, go back to step 1, and do the same with that group.
if i remember right, coplanar (or nearly coplanar) lines usually go in the same node…you shouldn’t see split parts of 1 line tho, since they should have ended up in different groups in step 2 above.
"1). When creating the bsp tree I randomly choose a line. If that line intersects any other lines then I divide that line into two lines (for instance line A becomes line A1 and A2). Do I just need to do this for the root node only "
No, you have to repeat this process for each node ( code a recursive routine ).
You will stop processing when the set of lines
becomes convex ( i.e. no line can cut any
other line in the set ).
"or do I need to do this for every line in the bsp tree? "
"2) What if I am trying to create the tree and I have two lines that are co-planar? For instance say I have line A and because of the position of some other lines line A is divided in more than one place. How do I place the different parts of line A (A1, A2, A3) into the bsp tree? "
If A1 is at the left of the cutting line, place
it to the left node of current node. If A3 is to the right of the cutting line, place it to the right node of the current node.
Lines that are coplanar to the cutting line can either be placed to the right node or be kept in the current node.