Archived

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

A 3D environment; BSP trees?

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

Recommended Posts

Im sitting here programming every wall in my 3d environment manually; its annoying. How can I "load" a level from a file? Or better yet, what the hell is a BSP tree? Im really concerned with collision detection too if you have any tutorials. thanks!

Share on other sites
1. To load levels or models from a 3d mesh try using this...
http://lib3ds.sourceforge.net/
It can load .3ds files which can be made in 3D Studio Max including textures....

2. For BSP trees.. try doing a search on them or try Botmans Half-Life Map viewer which supports Half-Life map .bsp trees in OpenGL...( you can get the source for it too)
http://www.planethalflife.com/botman/bsp_tool.shtml

3. For collision detection i recommed...
ColDet - 3D Collision Detection Library
http://photoneffect.com/coldet/
Which by the way *seemlessly* intergrates with OpenGL... there are even some examples of modified NeHe source that work with it.

Share on other sites
quote:
Original post by Anonymous Poster
1. To load levels or models from a 3d mesh try using this...
http://lib3ds.sourceforge.net/

2. For BSP trees.. try doing a search on them or try Botmans Half-Life Map viewer which supports Half-Life map .bsp trees in OpenGL...( you can get the source for it too)
http://www.planethalflife.com/botman/bsp_tool.shtml

3. For collision detection i recommed...
ColDet - 3D Collision Detection Library
http://photoneffect.com/coldet/
Which by the way *seemlessly* intergrates with OpenGL..

ouh fuck above 2) for BS-trees try to find some map-viewer sources supports that OpenGL and that ... i can''t stand... errr, maybe you should before that read some information about BS-trees, lol. That''s very funny, IT''S not NEVER right way to take others SRC and use it, RIGHT WAY is learn stuffs and implement them fully on your *OWN*.

and 3) ouh fuck... PLEASE, learn little bit 3d-programming and you can implement cd your own, common way is that simple: concanate camera system +SPHERE(for your camera) - TRIANGLE intersection algorithm +calc pushback vector if intersection is happened.

sorry, but i can''t stand above anonymous sender. maybe he tried to help you, but definitely wrong way.

Share on other sites
I have to agree with rickpeek. I understand that the Anonymous Poster was just trying to help, but what he was recommending is certainly not the way to go about making anything decent.

First, let me clarify some things. There are *.bsp format files, which contain the maps for games based on the Quake I, II, and III engines. A BSP tree is not a file format. Although *.bsp files contain a BSP tree, they also contain additional information.

What IS a BSP tree then? Think of it this way. You have a world. Find a face (wall, ceiling, etc) in it, and divide the world in half along that plane. Now you have two areas. Find a face in each of these, dividing them. Now you have 4. Continue splitting the world into sections by its faces until each section has no more faces that can be split against. As you can see, there is one master "parent" in this tree, and that is the whole world. It has two "children," which are the areas on either side of the first splitting plane. Each of these two areas (which are called "nodes" in the tree) in turn has children, and so on. Now picture these relationships expressed in a family tree. That is a BSP tree.

Now what the heck is a BSP tree useful for? It''s a way of sorting your level front-to-back. Its based on the principle that nothing on the far side of a plane can be in front of anything on the near side of the plane. That''s a pretty common-sense idea! But as you split the world into smaller and smaller sections, eventually you can draw the entire world back-to-front perfectly. This, however, isn''t what they''re used for nowadays. Now, if anything, they''re used to draw the world front-to-back. The reason for this is that, since the graphics card checks to see if the pixel its about to draw is behind the oneon the screen before drawing it, you can avoid drawing a great many pixels that way, instead of drawing pixels on top of pixels on top of pixels.

Even this isn''t the primary purpose of a BSP tree nowadays though. Now, what is done is this: For each leaf node, it is calculated what other leaf nodes can be seen from it, and this information is stored in a file (like the *.bsp files I mentioned earlier). Then, as you run through a map, only the areas that are potentially visible from where you are are even considered. If a map has two rooms connected by twisting hallways, then, if you''re in one room, the other room won''t be drawn. This is called occlusion culling. In this case, it is precalculated.

There''s a good article on BSP trees here: http://www-2.cs.cmu.edu/afs/andrew/scs/cs/15-463/pub/www/notes/bsp_tutorial.pdf

If you want to be able to walk through large levels with any efficiency, then you''ll need to have some kind of data structure for sorting your world geometry. If not a BSP tree, then an octree, or even a uniform grid. (Or for terrains, a quadtree)

Now, about collision-detection. First, you need to realize something. All OpenGL does is draw stuff. The end. If, by "programming every wall in your 3d environment manually" you mean writing lots of glVertex3f(...) commands, then there''s no practical way for you to do collision detection. All OpenGL does is draw stuff!! What you need is a data structure of some sort - it can be something as simple as an array of triangles - that you draw using OpenGL. If you have such a data structure, then you can do collision detection. The better your structure, the faster it will be.

There''s a really simple method of storing a world that dates back to the days of Wolfenstein. Store it as a 2d array of blocks. There are two kinds of blocks, solid and empty. Empty blocks are rendered just as a ceiling and floor; solid blocks also have walls. Your level is stored in a grid. I''m sure you can figure out collision detection with this system!! You can even do simple occlusion culling very easily with such a system. On top of all that, you can make maps in an image editor, jut using black and white pixels to represent blocks and emty space.

A more vesataile system, which is in some ways more complicated and in some ways simpler, is just to have, as I mentioned before, an array of triangles, something like this:
  struct vertex{ float x, y, z;};struct triangle{ vertex verts[3];};triangle * map = new triangle[NUMBER_OF_TRIS_IN_MAP];

How do you do collision detection with this second technique? You need to iterate through each triangle, and test to see if the sphere representing your camera and it intersect. The simplest way to do that is to find the intersection of that sphere and the plane containing that triangle, and then checking to see if that intersection point is within the three verteces.

Both methods are simple. The first is too constraining to really look good, but is efficient. The second is too inefficient to run well, but can hold any geometry. If you were doing anything serious, you would have to use a better system, like a BSP tree or octree.

I hope that helps.

Share on other sites
Thank you for your help so far.

That first example from above is much like the world that I was creating; ALSO inspired by Wolfenstein. I had a 2D array, and a function that would scan the array for a 1 and draw a block. (it was composed of 0's and 1's)

ANYWAY! Enough off topic crap from me. =) I understand what BSP trees are, and now they make for sense. No wonder my game would lag so much; It was drawing so much!

Now what else was there; Ah yes. I have concluded by many tutorials that collision detection is best used with object collision detection. Like, erecting a sphere around my camera, then checking if it collides with something, right?

Well, with blocks, it sounds like it would be fairly easy. But what about something else? Can you give an example? By something else, I am referring to, well, anything.

The basics steps, as described in a tutorial on the opengl.org site, are the following:

1. Record the coordinates of the camera
2. record the coordinates of the object
3. if(camera_coords=object_coords) then stop movement

Yes? no? It sounds right, I guess...

But I just don't get how I would detect smacking into something. There is one height for my camera, so would I just run through an array of data and say that if ever the camera coords are equal to any coords in the big array of wall positions, then stop?

Oy vey, maybe I should get some coffee...

Thanks again to all who are posting to help my poor little mind, especially TerranFury.

Edited by - zeus_ on November 25, 2001 1:33:57 PM

Share on other sites
Oh also; You mentioned a method that allows OpenGL to only draw what you see (in a sense)... Is there an order of functions that enable that? Or is that one of those long and difficult things that I should read a tutorial to learn about?

Thanks again!