enum bh_query_type{
k_bh_query_box,
- k_bh_query_ray
+ k_bh_query_ray,
+ k_bh_query_range
}
query;
f32 max_dist;
}
ray;
+
+ struct {
+ v3f co;
+ f32 dist_sqr;
+ }
+ range;
};
i32 depth, i;
};
-VG_STATIC void bh_iter_init_box( i32 root, bh_iter *it, boxf box ){
- it->query = k_bh_query_box;
+VG_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;
+}
+
+VG_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 );
}
VG_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;
- it->stack[0].id = root;
- it->stack[0].depth = 0;
- it->depth = 0;
- it->i = 0;
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;
}
+VG_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.
+ */
VG_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->query == k_bh_query_box )
- q = box_overlap( inode->bbx, it->box.box );
- else
- q = ray_aabb1( inode->bbx, it->ray.co,
- it->ray.inv_dir, it->ray.max_dist );
+ 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 --;