-static void bh_iter_init_generic( i32 root, bh_iter *it ){
- it->stack[0].id = root;
- it->stack[0].depth = 0;
- it->depth = 0;
- it->i = 0;
-}
-
-static void bh_iter_init_box( i32 root, bh_iter *it, boxf box ){
- bh_iter_init_generic( root, it );
- it->query = k_bh_query_box;
-
- box_copy( box, it->box.box );
-}
-
-static void bh_iter_init_ray( i32 root, bh_iter *it, v3f co,
- v3f dir, f32 max_dist ){
- bh_iter_init_generic( root, it );
- it->query = k_bh_query_ray;
-
- v3_div( (v3f){1.0f,1.0f,1.0f}, dir, it->ray.inv_dir );
- v3_copy( co, it->ray.co );
- it->ray.max_dist = max_dist;
-}
-
-static void bh_iter_init_range( i32 root, bh_iter *it, v3f co, f32 range ){
- bh_iter_init_generic( root, it );
- it->query = k_bh_query_range;
-
- v3_copy( co, it->range.co );
- it->range.dist_sqr = range*range;
-}
-
-/* NOTE: does not compute anything beyond the leaf level. element level tests
- * should be implemented by the users code.
- *
- * this is like a 'broad phase only' deal.
- */
-static i32 bh_next( bh_tree *bh, bh_iter *it, i32 *em ){
- while( it->depth >= 0 ){
- bh_node *inode = &bh->nodes[ it->stack[it->depth].id ];
-
- /* Only process overlapping nodes */
- i32 q = 0;
-
- if( it->i ) /* already checked */
- q = 1;
- else{
- if( it->query == k_bh_query_box )
- q = box_overlap( inode->bbx, it->box.box );
- else if( it->query == k_bh_query_ray )
- q = ray_aabb1( inode->bbx, it->ray.co,
- it->ray.inv_dir, it->ray.max_dist );
- else {
- v3f nearest;
- closest_point_aabb( it->range.co, inode->bbx, nearest );
-
- if( v3_dist2( nearest, it->range.co ) <= it->range.dist_sqr )
- q = 1;
- }
- }
-
- if( !q ){
- it->depth --;
- continue;
- }
-
- if( inode->count ){
- if( it->i < inode->count ){
- *em = inode->start+it->i;
- it->i ++;
- return 1;
- }
- else{
- it->depth --;
- it->i = 0;
- }
- }
- 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->i = 0;
- }
- }
-
- return 0;
-}
-
-static int bh_closest_point( bh_tree *bh, v3f pos,
- v3f closest, float max_dist )
-{
- if( bh->node_count < 2 )
- return -1;
-
- max_dist = max_dist*max_dist;
-
- int queue[ 128 ],
- depth = 0,
- best_item = -1;
-
- queue[0] = 0;
-
- while( depth >= 0 ){
- bh_node *inode = &bh->nodes[ queue[depth] ];
-
- v3f p1;
- closest_point_aabb( pos, inode->bbx, p1 );
-
- /* branch into node if its closer than current best */
- float node_dist = v3_dist2( pos, p1 );
- if( node_dist < max_dist ){
- if( inode->count ){
- for( int i=0; i<inode->count; i++ ){
- v3f p2;
- bh->system->item_closest( bh->user, inode->start+i, pos, p2 );
-
- float item_dist = v3_dist2( pos, p2 );
- if( item_dist < max_dist ){
- max_dist = item_dist;
- v3_copy( p2, closest );
- best_item = inode->start+i;
- }
- }
-
- depth --;
- }
- else{
- queue[depth] = inode->il;
- queue[depth+1] = inode->ir;
-
- depth ++;
- }
- }
- else
- depth --;
- }
-
- return best_item;
-}