# help required wiht BSP tree

11 replies to this topic

### #1broli86

Member

• Members
• 81 posts

Posted 01 April 2008 - 09:37 AM

I've decided to use BSP tree for my object which has been converted
into triangular mesh. The subdivision plane that i use builds the BSP
tree by subdividing along the center of x, y, or z bounds But the
biggest problem I'm facing right now is how to deal with situations
where a triangle is spanning across the plane ?? In this case part of
traingle is in one bounding volume and the other part is in the
sibling bounding volume. How to deal with this ??

Also, what happens is that when you have calculated geometry
preprocessing data structures like half edge data structure, then you
have to constantly change things which makes it even more complicated.
For eg. when a plane interesects a triangle, then it is split into two
polygons, you have to subdivide these polygons into n-2 triangles and
then change the half edge structure again and again. If someone can provide a link to a good BSP tree code it will be even more helpful

### #2Wernaeh

Senior Member

• Members
• 368 posts

Posted 01 April 2008 - 10:56 AM

Hey there :)

Why exactly do you want to use a BSP tree ? These are quite oldfashioned these days...

Also, to me it sounds like you are building some kind of AB-Octree mixture if you are talking about dividing through the center of some boundary volume. With BSP trees, you use the planes your polygons are located on as subdivision hyperplanes.

For the spanning problem, this again depends on how you want to use your BSP tree:

If you intend to use the convex interior half-spaces formed by a true (see above!) bsp on a closed, polygonal surface, you need to split your triangles with the plane. Here, it becomes helpful if you use a data structure which allows for multi-point, convex polygons (i.e. quads, and so on). However, the splitting you described is the only solution there. With regards to additional data structures, depending on performance, it might be a good idea to issue a total rebuild after bsp tree generation.

However, if you are just using the bsp tree as a means to get a hierarchial representation of your polygon soup, you may very well get around splitting: Instead of splitting, just create two entries for the spanning element, one on each side of the node. This for instance works well with collision detection.

Hope this helps,

Cheers,
- Wernaeh
Some call me mathematician, some just call me computer guy. Yet, I prefer the term professional weirdo :)

### #3broli86

Member

• Members
• 81 posts

Posted 01 April 2008 - 11:46 AM

Thank you very much for your help buddy.

Wernaeh said:

Hey there :)

Why exactly do you want to use a BSP tree ? These are quite oldfashioned these days...

I'm sorry I'm really a begginer in this area so my knowledge is really limited.
But can you please tell which data structure is the most recommended these days ? I was initially having a bounding sphere for the entire object but to me it seems you can't have spatial subdivision with a sphere. Although, with sphere, determining intersection is too simple.

Wernaeh said:

Also, to me it sounds like you are building some kind of AB-Octree mixture if you are talking about dividing through the center of some boundary volume. With BSP trees, you use the planes your polygons are located on as subdivision hyperplanes.

Yes you are right here. But what I'm talking about is a axis aligned BSP tree(as opposed to polygon aligned BSP tree which you were talking about) which is (as you rightly said) similar to octree. But unlike octree, I'm not going to have 8 children per node. There will be only 2. First I will divide the node along x axis, then the children along y axis, then grandchildren along z axis. Its cyclical.

http://tog.acm.org/G...s/gemsiii/bsp.c

^^ Something like this (look into subdivide function)

Wernaeh said:

For the spanning problem, this again depends on how you want to use your BSP tree:

If you intend to use the convex interior half-spaces formed by a true (see above!) bsp on a closed, polygonal surface, you need to split your triangles with the plane. Here, it becomes helpful if you use a data structure which allows for multi-point, convex polygons (i.e. quads, and so on). However, the splitting you described is the only solution there. With regards to additional data structures, depending on performance, it might be a good idea to issue a total rebuild after bsp tree generation.

However, if you are just using the bsp tree as a means to get a hierarchial representation of your polygon soup, you may very well get around splitting: Instead of splitting, just create two entries for the spanning element, one on each side of the node. This for instance works well with collision detection.

Hope this helps,

Cheers,
- Wernaeh

I didn't really get your point over here but what I want to do is accelerate my ray tracing software so that instead of checking all the triangles, I need to check only a few. I want to create a binary tree of bounding boxes like this and then traverse it to quickly determine the intersection (or collision detection as you put it).

When splitting a bounding box into left child and right child, it is easy to classify traingles which are totally on one side as they satisfy the following condition -

min.x > = vertex[i].x < = max.x
min.y > = vertex[i].y < = max.y
min. z > = vertex[i].z <= max.z

i = 0...3

These type of triangles can be straight away put into the appropriate buffer. But the problem, like i said, is for traingles which span the plane. When a triangle is cut by a plane, it is divided into two polygons.

### #4rouncer

Senior Member

• Members
• 2722 posts

Posted 01 April 2008 - 12:02 PM

For spacial division I just use octrees or grids, they are the only 2 i learnt.
bsp's confused me because they dont seem to split the world into even
groups.(do you find that an issue?)

Grids are just 3d arrays, and they waste tonnes of ram but they have the
quickest insert and delete of any spacial division technique.

Any form of tree based apon a heirarchy takes longer to build.

A grid will waste any other form of spacial division if your doing a proximity
weld of verts (welding them together due to their 3d proximity.)

I think this splitting of a triangle when it crosses over the boundary is only
for some specific algorythm - usually you just use id's of your entities and you
just repeat the id's across the boundaries, thats the only thing that makes
sense to me.

### #5broli86

Member

• Members
• 81 posts

Posted 01 April 2008 - 12:24 PM

rouncer said:

For spacial division I just use octrees or grids, they are the only 2 i learnt.
bsp's confused me because they dont seem to split the world into even
groups.(do you find that an issue?)

Do you know of any source codes for octree or grid ??

I think if you have implemented the octree, then you must have surely come across this same problem about traingle spanning across the plane ??

rouncer said:

Grids are just 3d arrays, and they waste tonnes of ram but they have the
quickest insert and delete of any spacial division technique.

Any form of tree based apon a heirarchy takes longer to build.

A grid will waste any other form of spacial division if your doing a proximity
weld of verts (welding them together due to their 3d proximity.)

I think this splitting of a triangle when it crosses over the boundary is only
for some specific algorythm - usually you just use id's of your entities and you
just repeat the id's across the boundaries, thats the only thing that makes
sense to me.

Yes the id's can be repeated across the boundaries, that's one idea. I wonder about the efficiency in this approach though.

### #6Kenneth Gorking

Senior Member

• Members
• 939 posts

Posted 01 April 2008 - 12:31 PM

broli86 said:

Yes you are right here. But what I'm talking about is a axis aligned BSP tree(as opposed to polygon aligned BSP tree which you were talking about) which is (as you rightly said) similar to octree. But unlike octree, I'm not going to have 8 children per node. There will be only 2. First I will divide the node along x axis, then the children along y axis, then grandchildren along z axis. Its cyclical.
What you are refering to is called a kd-tree. This ray-tracing tutorial has more details on how to use it.
"Stupid bug! You go squish now!!" - Homer Simpson

### #7rouncer

Senior Member

• Members
• 2722 posts

Posted 01 April 2008 - 12:40 PM

Theres no efficiency problem with repeating id's, the object that gathers the
symbols could gather same symbol twice i guess, but its no biggy - it keeps
things simple.

if a triangle is right on the edge of a octree division - itll either go into one
side or the other, so I guess you should put it in both to be careful.

Spacial division is no big deal, you do it however you feel like its not that
difficult.

### #8broli86

Member

• Members
• 81 posts

Posted 01 April 2008 - 12:44 PM

Kenneth Gorking said:

What you are refering to is called a kd-tree. This ray-tracing tutorial has more details on how to use it.

But in k-d tree the splitting plane is not passing through the mid points of x, y or z bounds. instead, geometric average of all centroids is taken and then the splitting plane is assumed to pass through it.

### #9broli86

Member

• Members
• 81 posts

Posted 01 April 2008 - 12:57 PM

rouncer said:

Theres no efficiency problem with repeating id's, the object that gathers the
symbols could gather same symbol twice i guess, but its no biggy - it keeps
things simple.

if a triangle is right on the edge of a octree division - itll either go into one
side or the other, so I guess you should put it in both to be careful.

Spacial division is no big deal, you do it however you feel like its not that
difficult.

Ok, can you also please tell me how you implemented octree ? In octree you are simulatenously cutting thorugh center of box with 3 planes coplanar to XY, YZ and ZX planes. How did you store the bounds for each of the 8 children ??

I tried octree with following data structure -

struct octree
{

struct octree *child[8];
vector minB, maxB;
Triangle *list;

};

typedef octree octree;

octree *root;

.............
.............

Now suppose we have a root bounding box, now how to subdivide this into 8 children ??

### #10Reedbeta

DevMaster Staff

• 5307 posts
• LocationBellevue, WA

Posted 01 April 2008 - 03:52 PM

broli86 said:

But in k-d tree the splitting plane is not passing through the mid points of x, y or z bounds. instead, geometric average of all centroids is taken and then the splitting plane is assumed to pass through it.

It's still a kd-tree. You can determine the location of the splitting plane in any of a number of different ways, whether the midpoint, centroid, surface-area heuristic (SAH), etc...

Quote

In octree you are simulatenously cutting thorugh center of box with 3 planes coplanar to XY, YZ and ZX planes. How did you store the bounds for each of the 8 children ??

Typically you have a bounding box for each node (which at the root of the octree covers the whole scene) then it's just split at the midpoint in each axis to form 8 smaller boxes. But you could use other schemes for finding the splitting plane positions too, if you wanted.
reedbeta.com - developer blog, OpenGL demos, and other projects

### #11broli86

Member

• Members
• 81 posts

Posted 01 April 2008 - 04:21 PM

Reedbeta said:

Typically you have a bounding box for each node (which at the root of the octree covers the whole scene) then it's just split at the midpoint in each axis to form 8 smaller boxes. But you could use other schemes for finding the splitting plane positions too, if you wanted.

Hello, one method I just though of is as follows..please critique

find the AABB for the object i.e. minB and maxB vectors.

Then determine the length(max.x-min.x), breadth(max.y - min.y) and height ( max.z - min.z). After this,

L = length/2, B = breadth/2, H = height/2

Then, since we know values of all the 8 corners, use these to find the corners for each of the cells..
For eg at corner (xmin, ymin, zmin) -

(xmin , ymin, zmin)
(xmin + L, ymin, zmin)
(xmin + L, ymin + B, zmin)
(xmin + L, ymin, zmin)

Then for the four corners above, simply add height to zmin in each of the above. It is easy to determine the minB and maxB vectors through this with simple comparisons. This gives one cell. Similarly traverse to 7 other corners and determine 7 cells.
To determine which triangles are inside a particular cell use simple test like

min.x > = vertex[i].x < = max.x
min.y > = vertex[i].y < = max.y
min. z > = vertex[i].z <= max.z

i = 0...3

For triangles which are coplanar with splitting plane, their id's will be automatically repeated in other cell and the ones that are spanning across the plane must also be dealt with in the same way.

Make the routine a recursive one ...

octree(BBox, length, width, height, number_of_triangles_in_list, tri *list)
{

if(length && width && heigth <= some tolerance value || number_of_triangles_in_list <= some tolerance value)
Make the 8 children of the box as NULL
return;
........
........

octree(BBox, length/2, width/2, height/2, number_of_triangles_in_list, list);

}

For traversal, start with the root node and check which of the 8 cells the ray is hitting. Find that cell and further traverse until you reach a leaf node for which children are all NULL.

### #12Reedbeta

DevMaster Staff

• 5307 posts
• LocationBellevue, WA

Posted 01 April 2008 - 04:48 PM

Yes, that is the classic octree algorithm.
reedbeta.com - developer blog, OpenGL demos, and other projects

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users