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.
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.
|
