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 ?
How to free a dynamically allocated kdtree ?
Hi, I have created a kdtree (dynamically) using median cut approach
and now i want to free it. Here's my data structure :
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:
If I were using your structure, I'd make the union anonymous and probably rename nonleaf to composite, or group.
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.
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.
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 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.
Quote:Original post by dmatterQuote: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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement