I'm trying to build a kdtree for a 3d object. An object contains
vertices(3d vectors) and triangles (triangular mesh structure). The
idea behind using a kdtree is to split the bounding box(a minimum
volume box which encompasses the entire object) at the root node (i.e.
the one which contains the object itself) recursively into smaller
boxes until some stopping condition is satisfied ( I'm using a
combination of depth and maximum permissible triangles inside a box).
The box at the root node will be split along the x axis, the two
resulting children along y axis and the grandchildren along z axis.
This is repeated in a cyclical fashion. I'm splitting the box at the
point which resembles the median point of all vertices inside a given
box. The triangles are split by comparing the three vertex coordinates
against the split point and they can be put in either left child ,
right child or both children(in case when the triangle intersects
splitting plane). I can also use some other criterion like mid point
but median is supposed to give a better split. I want to use this kd
tree for accelerating my ray tracing procedure. With a kdtree, all you
have to do is check against intersection between a ray and the
boxes(which is extremely fast) until you reach a leaf node (which
contains a minimum number of triangles). Now all you need to do is
test for intersection against a minimal number of triangles which is a
lot faster than checking for intersection of every ray with every
triangle in the mesh. Ultimately, almost every triangle can be traced
to a leaf node (which will not be further split btw).
Here's the data structure that I have written for kd tree node
typedef struct kdnode_s
{
/* bounding box */
bbox box;
/* 0 - split along x axis , 1 - split along y axis, 2 - split along
z axis */
int splitplane;
union
{
/* Used only for non-leaf nodes i.e. split plane != -1 */
struct
{
struct kdnode_s *child[2]; /* pointers to two children */
double split; /* splitting coordinate */
}nonleaf;
/* Used for leaf nodes i.e. split plane = -1 */
struct
{
int ntriangles; /* number of triangles in node */
triangle **triptrlist; /* pointer to an array of pointers to
triangles */
}leaf;
}u;
}kdnode;
Note that I do not store the vertex list in every kd tree node, I
don't think its necessary because
ultimately we are only using the vertex list for finding split point,
its the triangles that we are interested in.
Now the function(smaller version) which partitions the kd tree looks
as follows:
/
************************************************** ************************************************** ***************************/
/* The arguments to this subidivide_kdtree
function:
*/
/* kd - pointer to kd tree node. Initially pointer of root node is
passed. */
/* m - pointer to the
mesh
*/
/* depth - depth of subidivision (0 when calling for first
time)
*/
/* maxdepth - maximum depth permissible (passed as argument when
calling for first time) */
/* maxtriangles - maximum number of triangles permissible
*/
/* pvertptrlist - parent vertex list */
/* ptriptrlist - parent triangle ptr
list
*/
/* pnvert - number of vertices in parent
node
*/
/* pntri - number of triangles in parent
node
*/
/
************************************************** ************************************************** ********************/
int subdivide_kdtree(kdnode *kd, mesh *m, int depth, int maxdepth, int
maxtriangles,
vector **pvertptrlist, triangle *ptriptrlist, int
pnvert, int pntri)
{
/* cntri - number of triangles in child, cnvert - number of
triangles in child */
int i, j, k, cntri, cnvert;
triangle **ctriptrlist; /* pointer to child triangle pointer array
*/
vector **cvertptrlist; /* pointer to child vertices pointer array */
int flag = 0; /* error flag */
kd->splitplane = -1; /* initialize current node as the leaf node */
kd->u.leaf.ntriangles = pntri;
kd->u.leaf.triptrlist = ptriptrlist;
/* If this condition is true, then its a non leaf node which will be
divided */
if(pntri maxtriangles && (depth < maxdepth))
{
kd->splitplane = depth % 3;
/* sort the array of pointers */
quicksort(pvertptrlist, 0, pnvert - 1, kd->splitplane);
/* find the split point for parent node */
kd->u.nonleaf.split = find_split_point(pvertptrlist, pnvert - 1,
kd->splitplane);
/* process both children nodes */
for(i = 0; i < 2; i++)
{
/* Allocate memory and perform other initializations for both
children */
/* Now partition the parent vertex and triangle list */
cnvert = 0;
for(j = 0; j < pnvert; j++)
{
/* Count number of vertices inside current child box being
processed */
if(vertex_inside_box(pvertptrlist[j]->coord[kd->splitplane],
kd->u.nonleaf.split, i))
cnvert += 1;
}
/* Allocate memory for child vertex pointer list */
cvertptrlist = malloc(sizeof(vector *) * cnvert);
/* Put the parent vertices into child node */
cnvert = 0;
for(j = 0; j < pnvert; j++)
{
if(vertex_inside_box(pvertlist[j]->coord[kd->splitplane], kd-
>u.nonleaf.split, i))
cvertlist[cnvert++] = pvertlist[j];
}
/* Do similar steps for partitioning the triangle */
flag = subdivide_kdtree(kd->u.nonleaf.child[i], m, depth + 1,
maxdepth,
maxtriangles, cvertptrlist,ctriptrlist,
cnvert, cntri);
}
}
return (flag);
}