On Apr 1, 11:49 pm, Andreas Sch=FCle <schu...@[EMAIL PROTECTED]
> wrote:
> broli schrieb:
>
>
>
> > On Apr 1, 5:22 pm, Andreas Sch=FCle <schu...@[EMAIL PROTECTED]
> wrote:
> >> 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?
>
> > 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 ?
>
> 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 =3D (maxB - minB) / 2
>
> Next, divide into components:
>
> x =3D (bbD.x, 0, 0)
> y =3D (0, bbD.y, 0)
> z =3D (0, 0, bbD.z)
>
> Through addition of the components x,y,z to minB you can get any point
> of the child bounding boxes.
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 > =3D vertex[i].x < =3D max.x
min.y > =3D vertex[i].y < =3D max.y
min. z > =3D vertex[i].z <=3D max.z
i =3D 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.
........................................
|
|
