#ifndef BVH_H
#define BVH_H
#include "common.h"
-#include "distq.h"
/*
* Usage:
return bh;
}
-VG_STATIC void bh_debug_node( bh_tree *bh, u32 inode, v3f pos, u32 colour )
+/*
+ * Draw items in this leaf node.
+ * *item_debug() must be set!
+ */
+VG_STATIC void bh_debug_leaf( bh_tree *bh, bh_node *node )
+{
+ vg_line_boxf( node->bbx, 0xff00ff00 );
+
+ if( bh->system->item_debug )
+ {
+ for( u32 i=0; i<node->count; i++ )
+ {
+ u32 idx = node->start+i;
+ bh->system->item_debug( bh->user, idx );
+ }
+ }
+}
+
+/*
+ * Trace the bh tree all the way down to the leaf nodes where pos is inside
+ */
+VG_STATIC void bh_debug_trace( bh_tree *bh, u32 inode, v3f pos, u32 colour )
{
bh_node *node = &bh->nodes[ inode ];
{
vg_line_boxf( node->bbx, colour );
- bh_debug_node( bh, node->il, pos, colour );
- bh_debug_node( bh, node->ir, pos, colour );
+ bh_debug_trace( bh, node->il, pos, colour );
+ bh_debug_trace( bh, node->ir, pos, colour );
}
else
{
- vg_line_boxf( node->bbx, 0xff00ff00 );
-
if( bh->system->item_debug )
- {
- for( u32 i=0; i<node->count; i++ )
- {
- u32 idx = node->start+i;
- bh->system->item_debug( bh->user, idx );
- }
- }
+ bh_debug_leaf( bh, node );
}
}
}
{
bh_node *inode = &bh->nodes[ it->stack[it->depth].id ];
- if( box_overlap( inode->bbx, box ) )
+ /* Only process overlapping nodes */
+ if( !box_overlap( inode->bbx, box ) )
{
- if( inode->count )
+ it->depth --;
+ continue;
+ }
+
+ if( inode->count )
+ {
+ if( it->i < inode->count )
{
- if( it->i < inode->count )
- {
- *em = inode->start+it->i;
- it->i ++;
- return 1;
- }
- else
- {
- it->depth --;
- it->i = 0;
- }
+ *em = inode->start+it->i;
+ it->i ++;
+ return 1;
}
else
{
- if( it->depth+1 >= vg_list_size(it->stack) )
- {
- vg_error( "Maximum stack reached!\n" );
- return 0;
- }
-
- it->stack[it->depth ].id = inode->il;
- it->stack[it->depth+1].id = inode->ir;
- it->depth ++;
+ it->depth --;
it->i = 0;
}
}
else
{
- it->depth --;
+ if( it->depth+1 >= vg_list_size(it->stack) )
+ {
+ vg_error( "Maximum stack reached!\n" );
+ return 0;
+ }
+
+ it->stack[it->depth ].id = inode->il;
+ it->stack[it->depth+1].id = inode->ir;
+ it->depth ++;
+ it->i = 0;
}
}