View Full Version : BSP Trees in OpenGL

01-14-2002, 10:47 PM
Hello to you reader!
A long time ago i had read about bsp trees in a book called "3D games:Rendering and software technology" but i didn't paid any attension to it because i was very new to OpenGL.
Now, 2 years later, i am reading every resource i can found on bsp trees because i found that they make your code faster, and because my PC is a little old (PMMX 233MHz with Riva 128) i want to speed things up a little.
Now comes the problem. I had read the BSP FAQ that i found in OpenGL.org(yes it is here!!!) and i changed the pseudo code making the appropriate changes. Finally i was able to render a small scene. BUT i have found that my tree is not balanced at all. Also, when i have many polygon intersections the result is not the best. Where can i find a more detailed resource about BSP trees ???
If i make it someday work the way it must work, and i disable OpenGL's DEPTH_TEST, will the result be the same as rendering the original model with GL_DEPTH_TEST???
Is there a special algorithm for selecting the best BSP partition plane???
How can i do Hidden Surface Removal using BSP trees???
And Now THE Question :
How can i compute new texture coordinates for the splitted polygons??
The real proplem is when after a split the new polygons don't have the same amount of points as the original polygon.
And something that has nothing to do with OpenGL but with C++ : Why i can't include a vector<> inside a vector<> with the wanted results??? Let me explain.
I have a model class (GEModel3D) which includes a polygons vector (vector<GEPolygon3D> ). The GEPolygon3D class also includes a vector that keep the vertex id (vector<int> VertID). That way i can keep polygons with any number of vertices (theoritically). But when i render the model, the result is only the first polygon on the list.Not all of the model.If i render the polygons in GL_POINT mode then the result IS all of the models points. If anyone understood what i am taking about and had the same problem please inform me.
And don't forget,the main problem is BSPs.

I apologise if the topic is not appropriate for that forum but i don't know any other forum, person or thing to ask and talk about such things.

Thanks in advance.


PS. The GE in front of the classes means Game Engine (Lightning Game Engine specifically). The Thing that i will finish some day.

[This message has been edited by HellRaiZer (edited 01-15-2002).]

01-15-2002, 03:10 AM
huh huh http://www.opengl.org/discussion_boards/ubb/smile.gif

01-15-2002, 04:33 AM

I donīt know how YOU find the best splitting plane, but I once read something like this:

a = count polys completely on the left side of the plane
b = count polys completely on the right side of the plane
c = count polys which have to be split (because they are left and right)

score = |a-b| + 2*c

|a-b| means a-b and if that is negative you take the positive value (I canīt remember the word for this ;-)

The plane, which has the lowest score is the best, because there are only few polys that have to be split (2*c has more effect on the equation) and there is nearly the same amount of polys left and right.

I am not sure, if this is the correct equation, but it should be.

To your question about if they are drawn right when you disable depth-testing:

You can use the tree in two different ways (itīs just one line of code, that differs).
You go the tree along and draw first the polys that are, lets say, at the left node and then the ones, that are on the right node. This also means, that you first go along on the left side of your tree and then on the right side.
(I donīt know exactly how you implemented it so it could be different in your code.)

If you do it this way, you draw from back to front, that means first you draw the polys far away and then the ones near.
This would mean, if you disable depth-testing, it will still look the same.

But you can do another way, that might be better for performance (you have to test it on your own).

You go the tree along and do it exactly the other way round. You first draw the polys on the right side instead of the ones of the left side. This also means, that you first go along the tree on the right side.

This would mean you draw the polys in front to back order, that means first the ones near and then the ones far away.

Of course, then you need the depth-test. But this may have a great speed advantage, especially with many polys, because you donīt draw the thousand polys, that are behind the wall and at the end the one wall-poly which blocks the sight on all the other ones, but you first draw the wall and everytime you want to draw a poly, that is behind the wall, opengl realizes, that it is farther away and doesnīt draw it.

I hope I could help you.


01-15-2002, 10:53 AM
Hi all!

Jan, but when you say:

want to draw a poly, that is behind the wall, opengl realizes, that it is farther away and doesnīt draw it.

isn't it the same as drawing the polys without a BSP? http://www.opengl.org/discussion_boards/ubb/confused.gif Depth sort slows down a lot the application, I think it's faster to go along the tree on the left side, as you say, and disable the Z-buffer. Isn't it?

And, HellRaiZer,

How can I do Hidden Surface Removal using BSP trees???
BSP is just a sorting algorithm. I don't know if there is any way to do that. I don't think so... And if it's possible, it will be probably very hard to do.


01-15-2002, 11:18 AM
|a-b| means a-b and if that is negative you take the positive value (I canīt remember the word for this ;-)

It's called the absolute value. http://www.opengl.org/discussion_boards/ubb/tongue.gif

01-15-2002, 07:06 PM
One way to calculate tex coords for a split polygon is:

A and B are the two split points, one on each side of the splitting plane.
P is the intersection of line AB and the splitting plane

struct point
vertex pos;
float tx, ty;

// Calculate the distance between A and B
float dAB = A.pos.distance( B.pos );

// Calculate distance between A and
float dAP = A.pos.distance( P.pos );

// Find new texture x coordinate
float txInc = B.tx - A.tx;
float txPInc = ( txInc * dAP ) / dAB;
P.tx = A.tx + txPInc;

// Find texture y coordinate
float tyInc = B.ty -A.ty;
float tyPInc = ( tyInc * dAP ) / dAB;
P.ty = A.ty + tyPInc;

By the way, a better way to get a BSP tree is instead of storing polygons in the nodes you store a reference to an unsplit polygon. When you do a rendering traversal, you can place the node's polygons into a vertex array os something similar and after traversing the tree you render all the polygons that you touched, that way you don't need to bother with splitting polygons, plus you'll get way better performance.

Hope that wasn't too confusing


01-15-2002, 09:42 PM
Hello again!
Thanks a lot people, for your replies.
Marcos thank you for the code. I'll try it and see if it works(if i understood it right).
To Nemesis:
The only reason i tried to make BSPs is because i had read that they help very much with the Hidden Surface Removal problem. Every resource thet i had read was saying that plus many other wonderfull things that BSPs help you to implement. But i can't find anything talking about how to do it.

Thanks again.

PS: And Masm, what the hell that suppose to mean???????????????????????(no offence).
By the way, has your "name" anything to do with the assembler(huh huh).

01-15-2002, 11:09 PM
could you give me some links to those resources you are talking about? I would like to read them.


01-16-2002, 09:10 PM
Ok Nemesis lets start.
First of all we have two (2) books:
1) 3D Games : Advanced Rendering and Software technology
2) 3D Graphics Programming : Games and Beyond

Then we have some links:
1) BSP FAQ included in this site (yes www.OpenGL.org) (http://www.OpenGL.org))
2) http://www.geocities.com/pcgpe/bsp.html
3) http://www.cs.wpi.edu/~matt/courses/cs563/talks/bsp/bsp.html
4) http://www-2.cs.cmu.edu/afs/andrew/scs/cs/15-463/pub/www/notes/bsp.html (for more links)
5) try google with the keywords "BSP trees" ,"BSP trees using opengl" etc.
You will find many things to read but all of them includes the same things with different words. That's why i am here asking about BSP Trees using OpenGL


01-17-2002, 12:31 AM

Thank you very much, HellRaiZer.
As I have read in those resources, you certainly can use a BSP to perform hidden surface removal, but you have to traverse it from front to back and use another algorithm to test if the polygons are visible. When I said it would be hard to do, I was thinking of traversing the tree the other way, from back to front (the classical one http://www.opengl.org/discussion_boards/ubb/wink.gif ).
Then, the second way that Jan was talking about has not much sense. You cannot let OpenGL test it cause then you will have to enable the Z-buffer. You will have to test it by yourself.
And I think it will be faster, specially if the BSP is very big.
I'll try to implement that http://www.opengl.org/discussion_boards/ubb/smile.gif


01-17-2002, 12:45 AM

01-17-2002, 10:55 PM
To Nemesis:
If you succeed implementing the front to back rendering for hidden surface removal PLEASE e-mail me or send a message here.
My e-mail is : hellraizer@in.gr
I have read in the first book i mentioned above (it is "Real-time rendering" not "Advnced") that the front to back rendering uses algorithms such as frustum culling, clipping and back-face culling for doing hideen surface removal. It also talks about the "stencil" (in general, not OpenGL's one) buffer, but if you try to use OpenGL's one you failed with your goal/target. The target is NOT to render polygons that are not seen by the viewpoint.
Again if you find a way or the necessary algorithms for hidden surface removal using BSP trees PLEASE e-mail me.

To Masm and SoniC:
Are you familiar with the situation????
If you are, and you know how to solve the problem tell the solution to others. It could help more than sending stupid messages.


01-17-2002, 11:52 PM
hi again!
i just wrote huh huh as i found your question pretty huge(but that's nothing) & relating many really very complex algorithms like finding best BSP tree, which is said to be NP-Complete problem; ok there r several heuristic(?) approaches that can do it quite well; don't know but one of the best way to do this was probably found by ID Software, even though John Carmack wrote somewhere that 10 times overdraw on one pixel was not rare in Quake first....and disabling DEPTH-TESTING has (i guess) nothing to do with speeding up BSP's http://www.opengl.org/discussion_boards/ubb/smile.gif...

01-18-2002, 12:26 AM

> and disabling DEPTH-TESTING has (i guess)
> nothing to do with speeding up BSP's

well... I didn't say that. BSP's can be used instead of Z-buffer, they are usually faster. That's because I said it hasn't much sense (usually...) to use them together.

If I'm wrong, let me know.

To HellRaiZer:
OK, if I succeed I will e-mail you. I already have the back-to-front algorithm.


01-20-2002, 10:58 PM
Hello again to all of you!!!!!!!!
For those who cares about the subject.
I have made a part af the solution to the problem. The idea is based on using many different algorithms to cull surfaces that are not want to be drawn(????? is that make any sense). First of all i use the classical back to front algorithm.But the steps of doing HSR are as follows:
1) You classify the viewpoint with every partition plane.
2) If the viewpoint is IN_BACK_OF the partition plane you don't draw the POLYGONS coplanar to that plane.
3) That way we have back face culling.
4) After back face culling we check every polygon that passes the previous step with the view frustum. if it passes that too then we draw the polygon.

I know this want much more work but i have seen results with it and i wanted to share them with you. After all i made the question and i must answer(???).
The test i made is:
From a Lightwave Object with 1300 polygons (some kind of a stand/castle) the minimum number of polygons that will be drawn is 0 (yes zero, if anyone succeeds the frustum culling), and the maximum is 717 if you watch the whole object from distance.
And now the fps : 100.0f for the first situation and 32.0f for the second. And my computer is a little old (PMMX 233MHz with Riva 128/ZX)
And i dont' use polygon splitting (because the code i have doesn't work as it has to), but i try to balance the tree by pushing the shared polygons to the side with the less of them. For that reason i use GL_DEPTH_TEST. I know it is wrong but since i make my SplitPolygon() function i don't have a choice. By the way, if i render all the polygons normally, without any bsp or culling algo i take a 10-12 fps depending on how much of the object you see (OpenGL auto-culling).

I hope that helps.
If anyone can tell me how to improve the above algo, please inform me.

Thenks again for your cooperation.