typedef struct kdnode_s
{
    bbox box; /* Bounding box */
    char split_plane; /* 0:- x, 1:- y, 2 : z  -1 : leaf*/
    union
    {
        struct
        {
            struct kdnode_s *child[2]; /* two child nodes
            double split; /* split point */

        }nonleaf;

        struct
        {
            unsigned long nt; /* no: of triangles in node */
            triangle **tpa; /* triangle list */

        }leaf;

    }u;

}kdnode;

Quote:Original post by dmatter
You could do it with a recursive function to traverse the tree depth first, then freeing the nodes as it climbs back up.

Something like:

void free_kd_tree(kdnode *node){    int is_leaf = node->split_pane == -1;    if (is_leaf)    {        free_trangles(node->u.leaf.tpa, node->u.leaf.nt);    }    else    {        free_kd_tree(node->u.nonleaf.child[0]);        free_kd_tree(node->u.nonleaf.child[1]);    }    free(node);}

void kill kd tree(kdnode *kd){    if(*kd != NULL)    {        if ((*kd)->split_plane == -1)        {            kill_kd_tree(*kd);            *kd = NULL;        }        else        {            kill_kd_tree(&kd->u.nonleaf.child[0]);            kill_kd_tree(&kd->u.nonleaf.child[1]);                    if ((*kd)->u.nonleaf.child[0] == NULL             && (*kd)->u.nonleaf.child[1] == NULL)            {                kill_kd_node(*kd);                *kd = NULL;            }        }    }}

Quote:
If I were using your structure, I'd make the union anonymous and probably rename nonleaf to composite, or group.

Quote:Original post by broli86
I understand but I'm using C langauge and it seems anonymous structures and unions within structures are only allowed by *some* implementations. It is not considered as standard.

Quote:Original post by dmatter

Quote:Original post by broli86
Thanks, but shouldn't there be a if (node != NULL) test in the body of your function.

Yeah, I left out error checking...

void free_kd_tree(kdnode *node){    if (node == NULL)        return;    /* same as before */}

The reason I left this out is two fold: one for clarity, and two because the above check is a bit sub-optimal if you can guarantee your kdtree's composite nodes will never have null children.

Quote:I have also tried an implementation, not sure if it would work though:

<snip>

There are allusions to a working function there but not quite.
Two things I notice are that, based on your dereferences, you perhaps meant to make *kd a pointer to a pointer, **kd. Also if the split_pane is -1 then you get stuck in a recursive loop with no base case to stop it.

Quote:I'm using C langauge and it seems anonymous structures and unions within structures are only allowed by *some* implementations. It is not considered as standard.

Seems that anonymous structures and unions are actually a C++ feature - I had thought they were a carry-over from C or at least in C99, oh well.

Quote:Original post by Sneftel

I don't know of any modern C compilers which don't allow it. It may not be in the C89 standard, but it's a de facto standard.