Archived

This topic is now archived and is closed to further replies.

Building BSP trees

This topic is 5670 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I''ve been implementing a simple 2D BSP compiler and have apparently hit a snag: If a line segment has to be split during the process of compilation, the tree is generated incorrectly (walking it back to front will not yield the right results.) I don''t have a renderer yet, so I''ve just been walking the tree and printing the nodes. The source code is for DOS and it''s very simple. I''ve uploaded it here: bsp.c bsp.h The process that my render uses is described in the file, but I''ll paste it here anyway: - A root is selected - Front and back lists are created. These are simply linear lists * Walls in front of the root''s splitting lines are put in the front list as they are encountered, walls in the back are put in the back list * If a wall is split by the splitting line, the front part is put in the front list, the back part goes in the back list - A root BSP node is created. The front leaf is the front list (thus the first element in the front list) and the back leaf is the back list. The root is marked as being no longer usable (so that we don''t loop forever adding the same elements to the tree over and over) as are the 2 leaves (the first elements in the front and back lists) - Recursively repeat the process using the front leaf as a root - Recursively repeat the process using the back leaf as a root I''m learning mostly from Michael Abrash''s book (I haven''t found any really good web resources) and I couldn''t quite make out what his code was doing. I have my lines in a linear list and the root is always 0 (for now; I''ll implement a procedure to select a good root later.) Line segments that have been used are marked so that they cannot be reused (is this right?) A binary (for those who don''t have a DOS compiler handy) is available, along with a test set: bsp.exe lines.txt Thanks... --- Bart

Share this post


Link to post
Share on other sites
I looked at your source code, and it seemed pretty complicated. I''m familiar with generating 3D BSP trees, so a 2D BSP tree should be easier. I might also suggest making that a bit more modular, i.e creating seperate functions for calculating things such as line intersections.

You probably know most of this from what you described, but I''m going to explain it for my health more than yours Basically, you have the entire list of lines. What I would do first is create a bounding box around the "map", whose sides few units away from the outter-most walls. These lines, which will be clipped, along with lines selected for partitions, will eventually define our atomic spaces, i.e leafs. Now for the checklist:

1) Your recursive BSPTree function. Takes a list of lines, choses a partition, splits lines into front/back lists, recurses through children. Only returns if we reach an atomic space.

2) Select a partition. This split line should be axial if possible, and preferably close to the center of the map. Again, this partition selection process is a good candidate for a seperate function. Once a line is selected to be used as a partition, it cannot be used again, so mark it accordingly. Important note: you also need to mark all colinear lines as unusable in the future as well.

2) Once you have a partition, cut all the lines in you current list by this split into front and back lists. This seems to be where you are having the problems. It could be your intersection math, or you simply add the line to the wrong side. Anyway, all lines that coincide with the split are completely ignored, as explained ahead. This goes for that bounding box we defined earlier. However, when we move on to the front and back lists, the split line becomes part of the node boundary, as all colinear lines were ignored from before. You want that bounding box (or shall I say polygon after all the clipping) to go into a seperate list, however, so it isn''t chosed for partitioning. Call your BSPTree function on each of the child lists, and it will recurse beautifully.

3) An important thing to remember is that you are really passing a node to BSPTree. It may seem like a list of lines, but it''s really really important you have those bounding lines that define the node as well. If you can picture it, you can see that once we run out of partitions at a recursion, all we have left to define the leaf are those bounding lines we were clipping and creating from split lines.

If you need any further explanation, I could right some psuedo code. I''m not very good at explaining these types of concepts in words. Imagine me waving me hands a lot

Share this post


Link to post
Share on other sites
quote:
Once a line is selected to be used as a partition, it cannot be used again, so mark it accordingly . Important note: you also need to mark all colinear lines as unusable in the future as well.


So I was right about removing lines that have already been used in the BSP tree?

quote:

2) Once you have a partition, cut all the lines in you current list by this split into front and back lists. This seems to be where you are having the problems . It could be your intersection math, or you simply add the line to the wrong side.



I was doing some thinking today and realized that perhaps my problem is ignoring entire lines too soon.

For example, if a line A is split into A1 and A2, I mark A as used. This means A2 cannot later be split because all of A has been marked as used.

You noticed I had a fixed-size array of lines. When I determine which lines are in front or behind the splitter, I create a separate linked list of lines. Each element of the linked list points back to the fixed-length array. I think a better solution might be to just add new entries to the fixed-length list (perhaps this should be made into a linked list) when a line is split.

This _seems_ to work fine on paper (my tests were crude, though -- I''ll have to do some more.)

quote:
This goes for that bounding box we defined earlier . However, when we move on to the front and back lists, the split line becomes part of the node boundary, as all colinear lines were ignored from before. You want that bounding box (or shall I say polygon after all the clipping) to go into a seperate list, however, so it isn''t chosed for partitioning. Call your BSPTree function on each of the child lists, and it will recurse beautifully.


I don''t quite get this bounding box idea. If I understand correctly, each node in the BSP tree would now also define a convex polygon representing the area? Each time we subdivide the space, the bounding area is within the previous bounding area?

I think this would dramatically increase the complexity of my code.

---
Bart

Share this post


Link to post
Share on other sites