broli schrieb:
> On Apr 1, 11:49 pm, Andreas Schüle <schu...@[EMAIL PROTECTED]
> wrote:
>> broli schrieb:
>>
>>
>>
>>> On Apr 1, 5:22 pm, Andreas Schüle <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 = (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.
>
> 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.
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?
|
