22 replies to this topic

[broli86]

Can someone please tell me if this is a correct approach ?


i don't know but it feels something is wrong. what i am doing is
building a table -

triangle id centroid

Now if we want to split along x axis, then sort the records according
to x coordinates. Then use the median triangle as a splitting point.
Put all the records that appear till median including the median into left node and the ones that appear afterwards into right node. For child node,
splitting must be done along y axis, for grandchildren along the z axis. This
is done using a statement like axis = depth % 3 (axis = 0,1 ,2 for x,
y , z respectively. If the split point is split(x,y,z) and parent bounding box was given by vectors minB and maxB then children bounding boxes are given by minB.x, minB.y, minB.z and split.x, maxB.y, maxB.z

May be this is not a good approach but i need a working model in a limited time.

[Reedbeta]

I think it's usually done considering the points in the table to be vertices rather than the centroids of triangles. Also when you put the triangles into the lists you need to make sure that if a triangle crosses the splitting plane (that is, if one vertex is on one side and another vertex is on the other side) you either cut the triangle into two polys along the splitting plane, or leave it intact and put it in the list for both sides. (Which of those choices you want depends on what you're using the kd-tree for.)

[broli86]

Reedbeta said:

I think it's usually done considering the points in the table to be vertices rather than the centroids of triangles. Also when you put the triangles into the lists you need to make sure that if a triangle crosses the splitting plane (that is, if one vertex is on one side and another vertex is on the other side) you either cut the triangle into two polys along the splitting plane, or leave it intact and put it in the list for both sides. (Which of those choices you want depends on what you're using the kd-tree for.)

But why do we take vertices instead of triangle list ?

Another approach that I thought is to build a bounding sphere for every triangle.
Then, based on the centers of all bounding sphere, calcuulate the median bounding sphere center and use this as a split point. Suppose(in 2D) the bounding box is given by maxB(x,y) and minB(x,y) so if the split point is s(x,y). The center of any arbitrary sphere is cen(x,y) We are cutting along x axis first so,

if(cen.x + r < split.x && cen.x-r >= minB.x) /* left box is given by minB, split*/
putinspheretoleftchild();
if(cen.x +r > split.x && cen.x+r <=maxB.x) /*right box is given by split, maxB*/
putinspheretorightchild();

Along with this I intend to have another function that checks whether a sphere intersects an AABB like the one given here
http://www.gamasutra...018/Gomez_4.htm

In seperate if cases, check whether the bounding sphere intersects both the sibling boxes. If yes, then replicate the bounding sphere in both the left child and right child.

[Reedbeta]

Think about it: if you take triangle centroids, you're *guaranteed* to have at least one triangle fall on both sides of the splitting plane, namely the triangle whose centroid you picked as the median. If you use vertex positions then you might be able to find a splitting plane position that actually partitions the geometry.

Your approach with the bounding spheres has the same problem as with the centroids.

Another thing to think about is that it would be nice for the kd-tree to separate geometry from empty space. That is, if you're splitting a box and all the geometry is at one end of it, you'd want to put the splitting plane such that one of the two child nodes is completely empty. In general you want nodes containing geometry to be as small as possible before you start splitting the geometry up. I think the surface-area heuristic (SAH) for choosing splitting planes does this, though I'm not sure.

[broli86]

Reedbeta said:

Think about it: if you take triangle centroids, you're *guaranteed* to have at least one triangle fall on both sides of the splitting plane, namely the triangle whose centroid you picked as the median. If you use vertex positions then you might be able to find a splitting plane position that actually partitions the geometry.

But if I use vertex list, then how will it help while performing ray triangle intersections ? You would need to build a triangle list from the vertex list inside every cell again.

Reedbeta said:

Your approach with the bounding spheres has the same problem as with the centroids.

I doubt that. With bounding spheres, I'm not only checking for spheres which are completely inside the box but also those spheres which intersect both the sibling boxes. I did that with two simple bounding sphere-box intersection test. If bounding sphere intersects both the boxes then it is included both the boxes. There's no harm in creating sphere for every triangle, it does not take much effort to do it and it might further help speed up things while considering the ray-triangle intersections.

Reedbeta said:

Another thing to think about is that it would be nice for the kd-tree to separate geometry from empty space. That is, if you're splitting a box and all the geometry is at one end of it, you'd want to put the splitting plane such that one of the two child nodes is completely empty. In general you want nodes containing geometry to be as small as possible before you start splitting the geometry up. I think the surface-area heuristic (SAH) for choosing splitting planes does this, though I'm not sure.

Yea, I would definitely think about this one becauase it seems very efficient but right now I'm really bound by time.

[Reedbeta]

broli86 said:

You would need to build a triangle list from the vertex list inside every cell again.

Not at all. You just use the vertex positions to determine the location of the splitting plane, then take your original triangles and put each into one or both of the child nodes.

Do you understand my point about how if you use centroids, the splitting plane always crosses at least one triangle? If you use bounding spheres, the center of each sphere is (depending on how you calculate it) the centroid or approximately the centroid of the triangle. So taking the median of bounding sphere positions is likely to give you the same problem. It's not an issue of figuring out which triangles go into which child node, that's easy (and you really *don't* need bounding spheres for it). It's an issue of choosing an efficient position for the splitting plane.

[broli86]

Reedbeta said:

Not at all. You just use the vertex positions to determine the location of the splitting plane, then take your original triangles and put each into one or both of the child nodes

Ok, if you say this is an efficient way of finding split points then I will surely do it that way. But I think it is good idea to have a bounding sphere around every triangle and to place spheres into child nodes. It doesn't harm to calculate the spheres anyway. It makes the tests look extremely easy(look below). On the other hand, if you have plain triangles it can become difficult because then you need to take care of triangle-box intersections. Alternatively, one can have boxes around the triangles too but again, it involves writing seperate algo for box-box intersection

Reedbeta said:

Do you understand my point about how if you use centroids, the splitting plane always crosses at least one triangle? If you use bounding spheres, the center of each sphere is (depending on how you calculate it) the centroid or approximately the centroid of the triangle. So taking the median of bounding sphere positions is likely to give you the same problem. It's not an issue of figuring out which triangles go into which child node, that's easy (and you really *don't* need bounding spheres for it). It's an issue of choosing an efficient position for the splitting plane.

I think there is little miscommunication over here. I do understand what you are trying saying. You are saying that there may be a case where a sphere may overlap with the splitting plane causing it to be divided into two different boxes, but I have dealt with this situation by replicating such spheres in both the sibling boxes. Here's my sample code(which I have modified) when the splitting axis is the X axis. cen(x,y,z) is the center of a bounding sphere and split(x,y,z) defines the splitting location.

if(cen.x + r <= split.x) putspheretoleftchild();
else
if(cen.x - r >= split.x) putspheretorightchild();
else
{
putspheretoleftchild();
putspheretorightchild();
}

In the above code, if the sphere overlaps with the splitting plane, then in that case both the if's will fail and the else action will be taken which will put the sphere into both the sibling boxes. For other spheres which lie perfectly within the limits of the boxes, there is no problem at all. I hope you can understand what I'm saying.

[Reedbeta]

broli86 said:

You are saying that there may be a case where a sphere may overlap with the splitting plane causing it to be divided into two different boxes

I'm saying there's *guaranteed* to be such a case if you pick a sphere center as the location of the splitting plane. Not "there may be", there WILL be.

And yes, I know you can handle it by putting the sphere into two different boxes. That's not my point. My point is it's *inefficient* to choose splitting planes that force you to do that. You can make a better kd-tree if you choose splitting planes that don't cut your geometry, whenever possible.

broli86 said:

On the other hand, if you have plain triangles it can become difficult because then you need to take care of triangle-box intersections.

No, you only need to test if the triangles hit the splitting plane, which is extremely simple (just check which side of the plane each vertex is on, and if you've chosen the median of the vertices as the splitting plane location, then you actually already know which vertices are on which side). You don't need to test against the other sides of the box. You can have bounding spheres for each triangle if you want but I really don't see that they are useful at all in building the kd-tree.

[broli86]

Reedbeta said:

I'm saying there's *guaranteed* to be such a case if you pick a sphere center as the location of the splitting plane. Not "there may be", there WILL be.

And yes, I know you can handle it by putting the sphere into two different boxes. That's not my point. My point is it's *inefficient* to choose splitting planes that force you to do that. You can make a better kd-tree if you choose splitting planes that don't cut your geometry, whenever possible.

now i realize what you are saying. it is indeed a horrible method.

Reedbeta said:

No, you only need to test if the triangles hit the splitting plane, which is extremely simple (just check which side of the plane each vertex is on, and if you've chosen the median of the vertices as the splitting plane location, then you actually already know which vertices are on which side). You don't need to test against the other sides of the box.

suppose 1 vertex lies on left side of the plane and the 2 vertices lie on the right side, then should this triangle be included in both boxes ?

With this method, will there ever be a situation where a part of the triangle willl be inside a box but none of the vertices lie in it ?

Also, I would like to know how one should determine the stopping criterion in the recursive building of kd tree. IS the following ok ?

if(kdnode->numberofvertices <= MAXVERTICES || depth > DEPTHLIMIT || kdnode->ntriangles <= MAXTRIANGLES)

I plan to use a data structure like below

typedef struct kdnode_struct
{
vector maxB, minB;
vector split;
struct kdnode_struct *left, *right;
vertex *v;
triangle *t;
int maxvertices, maxtriangles;
}kdnode;

[broli86]

ok so i just started building up my tree and i am having a little
problem here. my object consists of 1200 triangles. I have found the
split point for the root bounding box. Now whwn the box is split
across x axis what i do is -

for all triangles
{
if( all xcoordinates of triangle vertices <= split.x
left_count++;
if(all x coordinates of triangle vertices >= split.x)
right_count++;
else /* which means the triangle gets cut by split plane */
{
/*put into both children */

left_count++;
right_count++;

}
}

strangely when i include else condition and try to print the value of
lefT_count and right_count for testing, i get values of 1200 and 1200
but when I remove it, I get 581 and 581 which is quite realistic(infact it is very good). but1200 and 1200 is ridiculous when you consider that there are only 1200 triangles to begin with.

Now, my question is what is going wrong here.

[Reedbeta]

broli86 said:

suppose 1 vertex lies on left side of the plane and the 2 vertices lie on the right side, then should this triangle be included in both boxes ?

Yep.

Quote

With this method, will there ever be a situation where a part of the triangle willl be inside a box but none of the vertices lie in it ?

Maybe. If you have a really big floor triangle, let's say, and there is a table or something standing on it, the kd-tree might subdivide space around the table in such a way that the big floor triangle passes through some nodes without any of its vertices being in those nodes. That's okay though as long as the floor triangle is listed in all the nodes it passes through (and it will be, if you make sure to include it in both children anytime it crosses the splitting plane).

Quote

Also, I would like to know how one should determine the stopping criterion in the recursive building of kd tree. IS the following ok ?

if(kdnode->numberofvertices <= MAXVERTICES || depth > DEPTHLIMIT || kdnode->ntriangles <= MAXTRIANGLES)

That looks fine, only that the vertices part and the triangles part might be redundant, since usually numberofvertices is approximately some constant * ntriangles (constant might be 3 for a triangle soup, or something less if you use tri-stripping or it's an indexed mesh).

Quote

I plan to use a data structure like below

typedef struct kdnode_struct
{
vector maxB, minB;
vector split;
struct kdnode_struct *left, *right;
vertex *v;
triangle *t;
int maxvertices, maxtriangles;
}kdnode;

That's fine, but you could save a little bit of space using a union:

struct kdnode_struct
{
    vector minB, maxB;
    int axis; // splitting axis: 0 = x, 1 = y, 2 = z, -1 = leaf node (no split)
    float split;
    union {
        struct {
            // Used only if axis != -1
            kdnode_struct *left, *right;
        };
        struct {
            // Used if axis == -1
            vertex *v;
            triangle *t;
            int maxvertices, maxtriangles;
        };
    };
};

[Reedbeta]

Shouldn't that second 'if' statement be an 'else if'?

[broli86]

Reedbeta said:

Yep.



Maybe. If you have a really big floor triangle, let's say, and there is a table or something standing on it, the kd-tree might subdivide space around the table in such a way that the big floor triangle passes through some nodes without any of its vertices being in those nodes. That's okay though as long as the floor triangle is listed in all the nodes it passes through (and it will be, if you make sure to include it in both children anytime it crosses the splitting plane).



That looks fine, only that the vertices part and the triangles part might be redundant, since usually numberofvertices is approximately some constant * ntriangles (constant might be 3 for a triangle soup, or something less if you use tri-stripping or it's an indexed mesh).



That's fine, but you could save a little bit of space using a union:

struct kdnode_struct

{

    vector minB, maxB;

    int axis; // splitting axis: 0 = x, 1 = y, 2 = z, -1 = leaf node (no split)

    float split;

    union {

        struct {

            // Used only if axis != -1

            kdnode_struct *left, *right;

        };

        struct {

            // Used if axis == -1

            vertex *v;

            triangle *t;

            int maxvertices, maxtriangles;

        };

    };

};

thanks!

[broli86]

Reedbeta said:

Shouldn't that second 'if' statement be an 'else if'?

I did some changes


for all triangles
{

a = condition that x coordinates of all vertices are <= split.x
b = condition that x coordinates of all vertices that are >= split.x

if(a)
left_count++;
else
if(b)
right_count++;
else
if(!a && !b)
{
left_count++;
right_count++;
}

}

Now with the above code, I get left_count as 1200 and right_count 619

When I did not have the else if(!a && !b), I was getting 581 and 581 which is 1162 i.e. triangles which are only in left and only in right. So that means triangles which are on both sides totals to about 38. I believe 619 for right_count is correct but theres something fishy about lefT_count which should also be 619 or so in my opinion.

[Reedbeta]

The last "!a && !b" condition is not necessary, since the last 'else' clause will automatically be executed if neither a nor b is true. But, that logic looks right to me so I don't know why you're getting 1200 for left_count; I'd suggest double-checking your initialization code and the code that computes 'a' and 'b'.

An even simpler way to write it would be:

if (at least one vertex has x <= split.x)
    left_count++;

if (at least one vertex has x >= split.x)
    right_count++;

[broli86]

Reedbeta said:

The last "!a && !b" condition is not necessary, since the last 'else' clause will automatically be executed if neither a nor b is true. But, that logic looks right to me so I don't know why you're getting 1200 for left_count; I'd suggest double-checking your initialization code and the code that computes 'a' and 'b'.

An even simpler way to write it would be:

if (at least one vertex has x <= split.x)

    left_count++;


if (at least one vertex has x >= split.x)

    right_count++;

I think this can be done as follows

Suppose a, b, c are three coordinates of the triangle. Now we can define a condition x as -

lc = a.x <= split.x || b.x <= split.x || c.x <= split.x;

The above conditions is same as your if(atleast one vertex has x <= split.x)

Similarly the condition if(atleast one vertex has x > = split.x can be written as

rc = a.x >= split.x || b.x >= split.x || c.x >= split.x


Now do a check like below

if(lc)
left_count++;
if(rc)
right_count++;

Is this correct ?

Another thing which bothers me is that my data structure for triangles contains 3 indices to vertex list. Now when the vertex list is getting sorted for a particular node, the triangle list will obviously get disturbed. This is leading to confusion. I am thinking of changing my triangle data strucutre such that it stores the coordinates of vertices itself so that no issues ariise.

[Reedbeta]

broli86 said:

I think this can be done as follows
...
Is this correct ?

Yes, that looks right to me.

Quote

Another thing which bothers me is that my data structure for triangles contains 3 indices to vertex list. Now when the vertex list is getting sorted for a particular node, the triangle list will obviously get disturbed. This is leading to confusion. I am thinking of changing my triangle data strucutre such that it stores the coordinates of vertices itself so that no issues ariise.

Instead of sorting the vertices directly in the vertex array, you could create an array containing pointers to all the vertices and sort that instead. Then you don't disturb the actual vertex array that the triangle indices refer to.

[broli86]

Reedbeta said:

Instead of sorting the vertices directly in the vertex array, you could create an array containing pointers to all the vertices and sort that instead. Then you don't disturb the actual vertex array that the triangle indices refer to.

Sigh, I already changed the triangle data structure. I guess it causes a little bit of redundancy because you have already have vertex coordinates in vertex list but then again there's nothing fundamentally wrong with doing it. Infact it proves more helpful in certain situations.
The results that i am getting are quit good -

1st split (Along x axis)
left right
680 triangles 680 triangles

2nd split(left child and right child along y axis)

left left left right

380 380 380 380


Then 171 171 etc etc. The code got some what repetitive because you have to do more or less the same thing for x, y and z cuts. So i just copy pasted once i wrote for axis = x.

Btw, with regards to kd tree traversal, do you think it is a good idea to use the slab method ? Also in my program, the ray can undergo multiple reflections but for my purposes i am only taking two at the most. You can easily determine whether ray hits the object or not using kd traversal(top bottom) but what to do once a ray has hit an object and another ray is reflected from the surface and again intersects some other triangle ? I don't see how kd tree will bail me out here. In that case I might have to check everyone of these reflected rays for intersection with every triangle. Am I right ?

[Reedbeta]

You just restart the reflected ray in the kd-tree from the top. Just treat it exactly the same as the first ray.

[broli86]

can i post my code here ?