Jump to content
  • Advertisement
Sign in to follow this  
broli86

How to free a dynamically allocated kdtree ?

This topic is 3641 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I have created a kdtree (dynamically) using median cut approach and now i want to free it. Here's my data structure :
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;
I tried to think over a few methods like postorder traversal etc but it won't work in this scenario. what to do ?

Share this post


Link to post
Share on other sites
Advertisement
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);
}


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

Share this post


Link to post
Share on other sites
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);
}



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

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


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.


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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

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.

Share this post


Link to post
Share on other sites
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.



Yes, its a double pointer i.e. **kd sorry for that mistake. IF that is solved, I think it should work.

Share this post


Link to post
Share on other sites
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.


I use Pelles C and it doesn't allow that.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!