OCTree or BSP Tree

BSP is commonly used in FPS kind of camera, while in an isometic kind of camera a frustum and an oc/quad/tree would be enough.

Hi,

Octree and BSP are partitioning algorithm. It takes your scene, and organize it in a certain way. After that, you can create a culling altorithm that take advantage of it.

For learning purpose, I'd recommend octrees. They are a loooot more simple to learn / use than BSP.

Edit : BSP / Portals are a lot more efficient for indoor environments, whereas octree is good with big outdoor environments.

Thanx for ur replies .. Well I have learnt OCTree I guess .. I have grasp the whole concept .. These days I am studying BSP Trees .. Have an idea about them but want to implement it .. Wat shud i do .. and any good tutorials for implementing BSP Trees ..

Now some Implementation question, I hope it wont annoy some1 !!, I am always confused whenever I read breaking a polygon(triangle) into two or more polygons while generating BSP Tree .. Will a line (assuming Tree generationg for 2D) not break triangle into two pieces .. how come more than that ? .. Plus any good link for calculating a point/line in a polygon or to the left or right .. I know Plane Equations will help in it .. But i need good link if some can provide ...

Thanx alot anyways

[Edited by - ebikhan on November 17, 2005 4:09:23 AM]

One thing more ... why OCTree for outdoor scenes and BSPTree for indoor .. Wat if I want Z-order for outdoor scenes as well .. Then wudnt I need BSP Trees for outdoor scenes ? Also, Wat techniques shud I used for Back face Culling ?

Quote:

Original post by ebikhan I am always confused whenever I read breaking a polygon(triangle) into two or more polygons while generating BSP Tree .. Will a line (assuming Tree generationg for 2D) not break triangle into two pieces .. how come more than that ?

True. In 2d, a line will always break another line in 2 (assuming they are not parallel). In 3d, when you're building your bsp, one given polygon will break other polygons in 2 assuming the 2 polygons instersect.
Now, what can happen in some cases is, if you only use triangles in your world, breaking a triangle in 2 can generate polygons that are not triangles... If your engine only handles triangles, you would have to take these polygons and break them into triangles. Wich means that, in the case where you *only* want triangles, your bsp splits can generate more than 2 triangles.

Thanx alot for clearing my confusion .. Can u please explain me the question I put in my last post .. or even some1 else can help me ... Any way thanx alot for the help !!!

Quote:

Original post by ebikhan One thing more ... why OCTree for outdoor scenes and BSPTree for indoor .. Wat if I want Z-order for outdoor scenes as well .. Then wudnt I need BSP Trees for outdoor scenes ? Also, Wat techniques shud I used for Back face Culling ?

This is a *very* rough explanation:

While bsp-trees divide the space on the polygon level, octrees divide the space in areas. In outdoor scenes you (generally) have whide open areas wich can have lots of polygons. Using the octree, in which you process your world in equal size areas, everytime you advance in the tree, you can say that a given area is not visible because, for example it's behind the camera. When you say this in the octree you just left out all the polygons in that area, which means that you don't have to process them.

With the bsp tree, this wouldnt work so well because you still had to process those polygons since you would have to visit the whole tree.

One thing you can try is to divide the world in areas and each small sub-area has it's polygons divided by a bsp-tree. You would have one bsp-tree for each sub-area (where the strenght of the bsp-tree lies) and you can skip whole areas using the octree.

Edit:*************************************************************************
Edit1: By the way... these days, unless you're making a software renderer (which is very cool, by the way), bsp-trees are more used for collision detection then for rendering.

Edit2: You also may want to check out kd-trees since they work on the same level as the bsp-trees, but they give you much more flexibility on the choice of where the to put the clipping plane. In the bsp-tree it's very easy for the tree to get unbalanced since you can only divide when you have a polygon.

Are you going to focus in indoor scenes, or a mix of indoor and outdoor scenes?

Thanx alot for the help and time ... Well regarding ur last suggestion I was thinking on it many days ... So it means u agree it is an effective way for Rendering, Collision Detection, Z-order etc.

One thing more can u please clear my one more confusion ... can bsp be used for map file formats ? .. What is the link between BSP Tree and Map File formats ... like i heard abt .BSP Map File Format ... Please clear my confusion ... and where I can get to study on Map File format .. a good link if possible ?.

Cadef ... Right now I am learning more and more knowledge ... So please explain the best and worst cases ( if possible ) in all three scenarios i.e Indoor, Ourdoor and mixture of them ..

Thanx for ur help!!!

Quote:

Original post by ebikhan Thanx alot for the help and time ... Well regarding ur last suggestion I was thinking on it many days ... So it means u agree it is an effective way for Rendering, Collision Detection, Z-order etc. One thing more can u please clear my one more confusion ... can bsp be used for map file formats ? .. What is the link between BSP Tree and Map File formats ... like i heard abt .BSP Map File Format ... Please clear my confusion ... and where I can get to study on Map File format .. a good link if possible ?.

The Map file format is text-only and describes a typical quake world. This format has nothing to do whith bsps. What ID/Carmack did was to start with a map file and create a bsp tree from it. The result of this process was a new kind of file: the .bsp file. This is the one used for the actually rendering in quake.

Note: i've never actually delve into the quake engine, so i'm talking from the top of my head from what i've read. Feel free to correct me if i'm wrong.

Quote:

Original post by ebikhan Cadef ... Right now I am learning more and more knowledge ... So please explain the best and worst cases ( if possible ) in all three scenarios i.e Indoor, Ourdoor and mixture of them .. Thanx for ur help!!!

If your just starting off, the best method is to use Octrees, it is the simplest. What language are you using? (VB,C++,etc) And what renderer? DirectX/OpenGL?

Agar urdu aap kay lee ashan ha, phir urdu maraysaat bolo, kyukay engrazi apka pala zuban nay lugta ha. ;)

haan yaar ... OCTree tow thand hay ... us say agay ki bataooo ... I am using C++ and OpenGL ... btw can u please now tell me where will be OCTree give good performance and where will BSP Tree .. You can imagine i want to create a hybrid scene i.e. Indoor and Outdoor both ! ... So any1 help on it ?

Thanx anyways ... bari nawazish apki ;)

This is wat I read in one Post here on Gamenet on BSP Trees:-

Cut space in half. Is object Right or Left?
Cut it in half again. Ask same question
Work that down to object level and thats a BST( I think.)
(http://www.gamedev.net/community/forums/topic.asp?topic_id=217291)

How do I know Is object On Left or Right ? .. I will have to use maths here .. the plane equations ,right ? Correct me if I am wrong.

Plus wat is kd-tree . Any good help on it.

Thanx alot every1 for ur kind help.

The difference between the k-d tree and the bsp trees lies essentialy on how you choose the partition plane to sub-divide the world. The k-d tree is more flexible in this aspect.

I suggest doing what Pragma said on that link you gaved: check Havran phd thesis (http://www.mpi-sb.mpg.de/~havran/DISSVH/phdthesis.html). The thesis is very directed towards raytracing, but the description he gives about the several different data-structures (BSP, KD-Trees, OCTrees,...) is very good!

An OCTree essentially splits a 3D scene into cubes. The scene is then sorted into cubes. You check the top-level cube. If it is visible, test the 4 child cubes. Keep going until there are no children to test. Then only render the scene polygons which are in the visible cubes.

Quote:

Original post by CadeF An OCTree essentially splits a 3D scene into cubes. The scene is then sorted into cubes. You check the top-level cube. If it is visible, test the 4 child cubes. Keep going until there are no children to test. Then only render the scene polygons which are in the visible cubes.

You're describing a quad tree :) An octree has 8 children.

Our team used an octree at first, but later moved on to the Kd-tree/AABB-tree (using the median as cutplane, to keep the tree balanced).

@bikhan:

Yes, you need to calculate the distance from a each point of the triangle to a plane. If all are negative it's on the negative side; if all are positive, it's on the positive side. Otherwise it's either on the plane or it needs to be cut.

(Or you can keep the triangles in-tact and extend the AABB's).

These days I am working on BSP Trees. How do i find a point lies in a triangle or not. I have generated equation for the plane but it doesnt work for A(0, 0, 0) B(10,0,0) and C(20,10,0). Can some one help me on it ?

I am trying to find out where is point. On front face or back-face or on the plane . SO now any help.

Thanx anyway.