View Full Version : BSP Trees

23-12-2002, 07:43 AM
I've started on creating my own 3D engine for a first person shooter game (we'll see where it ends) and I need some sort of depth sorting algorithm. I've picked BSP Trees to do this, since quake uses them too, however I have two questions:
-> Which is better a BSP Tree or and Octree?

-> Where can I find understandable information and preferably a good piece of sourcecode, I must have read dozens of tutorials, most of them specifying C++ pseudo code which explains only the pieces I allready understood.

Thanks in advance! :)

25-12-2002, 09:59 PM
From my understanding of it, you'd be better off with a BSP tree for indoor scenes and an octree for outdoor ones (terrain, that sort of thing). The downside with BSPs is that they take a fair time to compile, which means that you won't get much dynamic scenery.

I'll convert Nate Miller's BSP tutorial for you sometime soon (and perhaps the gametutorials stuff, if nobody has done so before -- maybe at Sulaco?). In the mean time, have a look here (http://www.cs.sun.ac.za/~henri/advgfx.html) for BSP code (note that it's in Direct3D, not OpenGL, though...).

(Aside: Shining Force for the Sega Megadrive rocks. 8))

26-12-2002, 04:38 PM
Thank you AliMonster! :)

I tried converting Nate Millers BSP tutorial myself and even though it didn't crash after the conversion it doesn't work either so my conversion kinda sucks! :)

I only learned the basics of C++ and on my school that never involved components (don't ask me why the only answer I can give u is that my teachers never understood their subjects) so I only understand the basics of it, so I probably did something wrong somewhere ! ;)

Thanks in advance for converting it for me!

P.S. The gametutorials stuff, is that the BSP Quake 3 level viewer? If so than there is a conversion of that on sulaco! ;)

26-12-2002, 10:43 PM
P.S. The gametutorials stuff, is that the BSP Quake 3 level viewer? If so than there is a conversion of that on sulaco! ;)

Well I thought it was.
It dieffinatly seems to be but I dont have Quake3.

I might buy it some time soonish.

But as to which is better. {Oct or BSP}
From what I've seen. It's a religious war.
My 2cents is, Design a level in somthing you know.
Even just draw it out on paper.

Get a good idea of how you want it to look and act like. Indoor, outdoor or a combo of both.

Then get into some format you can easly minipulate. After that.
Try different ideas. Run different formatters over it and load them.

I'm currently writteing and api {more or less} / engine for the usual. {games, demos and job interviews.} I've got a working map editor which produces .ini files.

Not an effcient format but it's easy then reading binary data. {with your eyes looking for errors}
At the moment I'm not worried about load times.

Once I've loaded it, I format it in memory to what I want. Agine the load time sucks but its the pricipal I want at the moment.

I was thinking of writting up this in a tut series. One map style and the different ways of tackleing the same problem. I.e rendering it as fast as possible.


27-12-2002, 08:04 AM
Sounds like a good idea, there aren't many tutorials that explain stuff like that, well not in the full though. I have read many tutorials on BSP Tree rendering and the thing was that some had really bad pseudo code and others just explained the basic functions you needed, which I understand about now but just couldn't implement! :)

The thing I'm trying to write is a 3D engine for first-person shooter games, I want to start out simple, but wish to move on to bigger things after that, my official goal is something like American Army online, however I think I'll manage to make something like that in 10 years or so, but it's a goal to work to and I would be happy if I would be able to make a Doom-like engine that uses better textures at the moment! :)

28-12-2002, 10:41 PM
Here ya go: nate_bsp.zip (http://www.alistairkeys.co.uk/download/nate_bsp.zip) (153K)

One approximately converted BSP tutorial for ya ;). Apologies for the delay, btw - I've been playing megadrive games on an emulator pretty much non-stop :roll:

Cursor keys = move
L = toggle wireframe view
B = show bounding areas for nodes or whatever

A side note about that tutorial: BAD NAMES FOR VARIABLES :evil: Why did Nate call something "n" when he mean "normal"? Why "v" instead of "vertices"? Why "flist" instead of "facelist"? Why "d" instead of "distance"? Dammit, don't let me catch any of your code looking like that [points to each DGDev member in turn]. If I do find that... there will be consequences :evil:.

28-12-2002, 10:43 PM
Oh, btw, the most interesting code is in bsp.pas and PlayingGameState.pas. The rest is just a copy-and-paste framework I use when converting stuff over from C++ to Delphi (some of it probably isn't even used there).

29-12-2002, 09:09 AM
Man AliMonster I just wanna give you a BIG kiss! However since I can't reach you from here and men normally don't do that, I'll just say a big THANK YOU very much! :)

Don't worry about the delay, I'm very very happy you did this for me and I didn't expect you to do it this fast allready I know how busy you all are.

It also gave me some time to try out some new stuff and write my very own BSP tree builder, which worked except for the tiny little difference that the level I used (nates map) looked like one big plane on my screen, so somewhere something went VERY wrong, but it helped me understand the basics! :)

I'll look into the code and learn how to do it. I understand the basics of BSP trees allready, however implementing it into code is much more difficult (however reading about it improved my math skills enormously, so for anyone who has trouble with vector mathematics try building a BSP tree! :P ).

I don't know why Nate used those variables, but I see that a lot in C++ examples, I was reading the Graphic Programmers Blackbooks part on BSP trees (very interesting stuff btw) by Michael Abrash and his algorithms used about the same variable names N for normal nx for the x of the normal, v for vector etc... Makes it really hard to read!

Okay, Thanks again AliMonster! I owe you ! ;)

30-12-2002, 10:26 PM
Would people be interested in a quick conversion of the GameTutorials
Quake3 Bsp tut?

Is there one already done or is this something new'ish?

I was going to delphi'ise it a bit but the logic will be the same.


31-12-2002, 06:45 AM
There is one at sulaco (http://www.sulaco.co.za/)

02-01-2003, 10:20 PM
Lion: I read your post after starting the conversion. I decided to try and finish it anyway.

What I need now is some webspace.

It's done but it's aquite a bit slower than the C version.
It also dosn't do muti-texturing yet. I'll finnish that tonight.

It's more or less a straight conversion, but I am using dynamic arrays and setlength rather than raw allocated buffers.

Would this account for the speed loss? I'm just wondering if it's a memory pageing issue, or is there some slow down when accessing elements?

02-01-2003, 10:23 PM
dynamic arrays are quite slow (well actually the resizing is slow), a TList might speed up the process quite a bit... not sure how to use it with records though, although there is an example in the Delphi help :)

If you need to store the demo for a while I can upload it to my lycos webspace or you can request your own webspace at lycos they provide 50 megs for free! :)

02-01-2003, 11:32 PM
I'm not resizing while in the mail loop so I don't think its that..
I should have sent it to work so I could run a profiler or 2 over it.

I'm going to try and find some free webspace..
Lion, where do you sign up for the free space at lycos?