I've been trying to implement a BSP Tree into my opengl engine for a couple days now, and it the way the bsp tree works has always bothered me. The fact that you have to split polygons up for every plane intersection, seems just too... ineffecient, or BAD. I know why we need to but maybe their is a way around it. Instead of splitting the polys up during the construction of the bsp tree, what if you ensure that every poly/quad is broken up into triangles before you render anything? (the video card does that anyways, so why not save it the time)

   ______
 __|     |___________
 | |     |           |
 | |     |           |
 |_|     |_____      |
   |     |_____|     |_
   |           |     | |
   |           |     | |
   |___________|     |_|
               |_____|
 

This is the problem we have with rendering polygons... (above)

   ______
 __|\    |___________
 | | \   |          /|
 | |  \  |        /  |
 |_|   \ |_____ /    |
   |    \|_____|\    |_
   |    /      | \   | |
   |  /        |  \  | |
   |/__________|   \ |_|
               |____\|
 

but if we brake it up to triangles before hand we CANNOT have this problem. Please exuse the horrible ASCII art. But anyways to the point! If I have nothing but triangles in my scene, can I build a bsp tree in exactly the same way, minus the nasty polygon splitting, and still get the same result? So what do you think? Would it work... I'm trying it myself but I also code the bsp tree at the same time. (I'm guessing that wasn't the most intellegent idea on my part but it's ok) So I need you opinion... Yes/No/Brilliant/What the hell where you thinking.... any of thing along those lines is acceptable Thanks!! Nehe! Thanks for staying with us! Stupid ASCII Art... oh i know the back polygons aren't divided could make it look good... [edited by - Shadow_0f_Light on April 20, 2003 11:33:54 PM]

the idea of BSP trees is that you splitt every polygon which spans another one into front and back polygons and add these to a front or back list of the node

it s all recursive

in fact this creats lots of unnecessary polygons and vertices which you actually dont need

the solution is
create the BSP tree as i explained above and setup an additional stack for the unsplitted polys

not when ever you splitt a polygon you store the index of the unsplitted polygon in your new ones

once you are done with building your tree you convert your unsplitted polygons from the second tree to triangles to render them with vertex arrays
and then replace the splitted faces with the unsplitted ones


carmack thought about this method as he started doom3 since doom uses high polygonal environments where BSP trees would create tons of unnecessarry faces