X-Git-Url: https://harrygodden.com/git/?a=blobdiff_plain;f=bvh.h;h=e79e3ddc6866ab7d012bfd30952d0fc8eebc3230;hb=2a238d32da833812e837cf38e16a7685c98db5c3;hp=491756acb0db460df2d5e697002b9b5e5e560169;hpb=777083e1f715a26d3f68be4ba5bdf2cbcaa84a05;p=carveJwlIkooP6JGAAIwe30JlM.git

diff --git a/bvh.h b/bvh.h
index 491756a..e79e3dd 100644
--- a/bvh.h
+++ b/bvh.h
@@ -5,7 +5,6 @@
 #ifndef BVH_H
 #define BVH_H
 #include "common.h"
-#include "distq.h"
 
 /*
  * Usage:
@@ -155,7 +154,7 @@ VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system,
    }
 
    u32 totsize = sizeof(bh_tree) + sizeof(bh_node)*(item_count*2-1);
-   bh_tree *bh = vg_linear_alloc( lin_alloc, totsize );
+   bh_tree *bh = vg_linear_alloc( lin_alloc, vg_align8(totsize) );
    bh->system = system;
    bh->user = user;
    bh->max_per_leaf = max_per_leaf;
@@ -178,7 +177,28 @@ VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system,
    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 ];
 
@@ -189,21 +209,13 @@ VG_STATIC void bh_debug_node( bh_tree *bh, u32 inode, v3f pos, u32 colour )
       {
          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 );
       }
    }
 }
@@ -288,39 +300,39 @@ VG_STATIC int bh_next( bh_tree *bh, bh_iter *it, boxf box, int *em )
    {
       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;
       }
    }