bounding volume hierarchy/space partition

[broli]

I have an object which is converted into triangular mesh. I have found
the AABB of the entire object So I would like to know what bounding
volume hierarchy/ space partition methods are possible. I would also
like to know if it would have been easier with a bounding sphere ?
What are the BV hierarchy/space partition methods in case of boundary
sphere ? I looked up BSP trees but I could not understand how they
choose the splitting planes. I came across codes for BSP in graphics
gems.

[Andreas Schüle]

Hi Broli,

broli schrieb:

> I have an object which is converted into triangular mesh. I have found
> the AABB of the entire object So I would like to know what bounding
> volume hierarchy/ space partition methods are possible. I would also
> like to know if it would have been easier with a bounding sphere ?
> What are the BV hierarchy/space partition methods in case of boundary
> sphere ?

In general BV's are used for collision detection or visibility checks.
BV may affect the decision process of your algorithm about splitting the
space enclosed of the BV.

I looked up BSP trees but I could not understand how they
> choose the splitting planes. I came across codes for BSP in graphics
> gems.

BSP doesn't oblige you to a specific way how to choose the splitting plane.

Usually the splitting plane is chosen like this:

Choose a triangle out of your triangular mesh (your set of triangles)
which splits all other triangles in two subsets with about the same
size. Do this until your subsets contains a single triangle at leaf.

example:

Triangle findBestSplitter(TriangleSet set) {
for all triangles in set do with t {
use t as spliting plane and generate two triangle subsets

if (my decision function says all right) {
return t as the best splitter
}
}
}

regards,
Andreas Schüle

[broli]

Thank you very much.

What I'm thinking is to build 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 ??

[Andreas Schüle]

broli schrieb:

> Thank you very much.
>
> What I'm thinking is to build 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 ??

If your triangle lies exactly on your splitting plane, then add it to
the side where triangle's normal is pointing to.

What do you expect to achieve with BSP?

[broli]

No, Im speaking of the situation where your triangle is intersecting
the splitting plane.

I have also been considering octree .In octree you are simulatenously
cutting thorugh center of box with 3 planes coplanar to XY, YZ and ZX
planes. However, I could not understand how to calculate 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 ?

[Andreas Schüle]

broli schrieb:

Don't you mean with it how to split a list of triangles by a plane?

Computation of new bounding boxes without splitting:

In your case the splitting is always done at bounding box center. Your
root bounding box is represented through the points minB and maxB.

First, get the half diagonal of your bounding box:

bbD = (maxB - minB) / 2

Next, divide into components:

x = (bbD.x, 0, 0)
y = (0, bbD.y, 0)
z = (0, 0, bbD.z)

Through addition of the components x,y,z to minB you can get any point
of the child bounding boxes.

[broli]

yeah i did something similar for octree.

I found the height, length and breadth.

Now once we know minB and maxB, it is easy to find the 8 corners of
the parent BB.

With these 8 corners you can determine the 8 corners of all the 8
children.

For eg. if the corner of parent BB is xmin, ymin, zmin then the child
node is given as

xmin, ymin, zmin
xmin + L/2, ymin, zmin
xmin + L/2 , ymin + B/2, zmin
zmin, ymin + B/2, zmin

This gives the 4 corners of the cell at the bottom face. TO find the 4
corners at the top face, simply add H/2 to zmin.

The coordinates can be sorted to find minB and maxB

That would give you one child cell. Similarly do it for all 8 corners
and you get 8 children

But even with this you have following cases -

1. The triangle is completely inside a bounding box. This is easy to
check -

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

i = 0...3

2. The triangle is coplanar with the partition ebtween two cells. Even
we haven't used any splitting plane or anything still there is a
partition between two adjacent cells. What I'm planning to do in this
situation is copy the id of the triangle to both the adjacent cells.

3. The triangle is passing through a box in such a way that none of
the vertices are inside the box. For this, I plan to use triangle-box
intersection. Store the id's of such triangles in every box to which
they belong.

[Andreas Schüle]

You're right. I would do it the same way you have described. Do you
optimize for visibility checks or use the octree for collision detection?

[broli]

On Apr 7, 2:09 pm, Andreas Schüle <schu...@gmx.c

> You're right. I would do it the same way you have described. Do you
> optimize for visibility checks or use the octree for collision detection?

Well, I switched to kd-trees now ..

I'm using these data structures for collision detection