numerous input and physics

[carveJwlIkooP6JGAAIwe30JlM.git] / bvh.h

diff --git a/bvh.h b/bvh.h
index c841939d0cab9d40f7c0741bc637eac5711d8314..9e4528604d59c8cf205f20d3d172b671102085e1 100644 (file)
--- a/bvh.h
+++ b/bvh.h
@@ -1,3 +1,7 @@
+/*
+ * Copyright (C) 2021-2022 Mt.ZERO Software, Harry Godden - All Rights Reserved
+ */
+
 #ifndef BVH_H
 #define BVH_H
 #include "common.h"
@@ -13,29 +17,32 @@
  *   user: a pointer back the base of the data you are ordering
  *   system: the system we created above which will deal with the data
  *
- * call bh_create( bh_tree *bh, u32 item_count, u32 item_size )
+ * call bh_create( bh_tree *bh, u32 item_count )
+ * VG_STATIC int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit )
+ * VG_STATIC int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
  */
 
 typedef struct bh_node bh_node;
 typedef struct bh_tree bh_tree;
 typedef struct bh_system bh_system;
 
-struct bh_node
-{
-   boxf bbx;
-
-   /* if il is 0, this is a leaf */
-   u32 il, count;
-   union{ u32 ir, start; };
-};
-
 struct bh_tree
 {
-   bh_node *nodes;
    u32 node_count;
 
    bh_system *system;
    void *user;
+   u32 max_per_leaf;
+
+   struct bh_node
+   {
+      boxf bbx;
+
+      /* if il is 0, this is a leaf */
+      u32 il, count;
+      union{ u32 ir, start; };
+   } 
+   nodes[];
 };
 
 struct bh_system
@@ -43,7 +50,6 @@ struct bh_system
    void  (*expand_bound)( void *user, boxf bound, u32 item_index );
    float (*item_centroid)( void *user, u32 item_index, int axis );
    void  (*item_swap)( void *user, u32 ia, u32 ib );
-   u32 item_size;
 
    /*
     * Optional:
@@ -53,10 +59,10 @@ struct bh_system
     */
 
    void  (*item_debug)( void *user, u32 item_index );
-   int   (*cast_ray)( void *user, v3f co, v3f dir, ray_hit *hit );
+   int   (*cast_ray)( void *user, u32 index, v3f co, v3f dir, ray_hit *hit );
 };
 
-static void bh_update_bounds( bh_tree *bh, u32 inode )
+VG_STATIC void bh_update_bounds( bh_tree *bh, u32 inode )
 {
    bh_node *node = &bh->nodes[ inode ];
 
@@ -68,10 +74,13 @@ static void bh_update_bounds( bh_tree *bh, u32 inode )
    }
 }
 
-static void bh_subdivide( bh_tree *bh, u32 inode )
+VG_STATIC void bh_subdivide( bh_tree *bh, u32 inode )
 {
    bh_node *node = &bh->nodes[ inode ];
 
+   if( node->count <= bh->max_per_leaf )
+      return;
+
    v3f extent;
    v3_sub( node->bbx[1], node->bbx[0], extent );
 
@@ -123,17 +132,31 @@ static void bh_subdivide( bh_tree *bh, u32 inode )
    node->ir = ir;
    node->count = 0;
 
-   /* TODO: Implement max depth, or stack */
    bh_update_bounds( bh, il );
    bh_update_bounds( bh, ir );
    bh_subdivide( bh, il );
    bh_subdivide( bh, ir );
 }
 
-static void bh_create( bh_tree *bh, bh_system *sys, u32 item_count )
+VG_STATIC bh_tree *bh_create( void *lin_alloc, bh_system *system, 
+                              void *user, u32 item_count, u32 max_per_leaf )
 {
-   bh->system = sys;
-   bh->nodes = malloc( sys->item_size * (item_count*2-1) );
+   assert( max_per_leaf > 0 );
+
+   if( item_count == 0 )
+   {
+      bh_tree *bh = vg_linear_alloc( lin_alloc, sizeof(bh_tree) );
+      bh->node_count = 0;
+      bh->system = system;
+      bh->user = user;
+      return bh;
+   }
+
+   u32 totsize = sizeof(bh_tree) + sizeof(bh_node)*(item_count*2-1);
+   bh_tree *bh = vg_linear_alloc( lin_alloc, totsize );
+   bh->system = system;
+   bh->user = user;
+   bh->max_per_leaf = max_per_leaf;
 
    bh_node *root = &bh->nodes[0];
    bh->node_count = 1;
@@ -146,11 +169,14 @@ static void bh_create( bh_tree *bh, bh_system *sys, u32 item_count )
    bh_update_bounds( bh, 0 );
    bh_subdivide( bh, 0 );
 
-   bh->nodes = realloc( bh->nodes, sys->item_size * bh->node_count );
+   totsize = sizeof(bh_tree) + sizeof(bh_node) * bh->node_count;
+   bh = vg_linear_resize( lin_alloc, bh, totsize );
+
    vg_success( "BVH done, size: %u/%u\n", bh->node_count, (item_count*2-1) );
+   return bh;
 }
 
-static void bh_debug_node( bh_tree *bh, u32 inode, v3f pos, u32 colour )
+VG_STATIC void bh_debug_node( bh_tree *bh, u32 inode, v3f pos, u32 colour )
 {
    bh_node *node = &bh->nodes[ inode ];
 
@@ -180,8 +206,11 @@ static void bh_debug_node( bh_tree *bh, u32 inode, v3f pos, u32 colour )
    }
 }
 
-static int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit )
+VG_STATIC int bh_ray( bh_tree *bh, v3f co, v3f dir, ray_hit *hit )
 {
+   if( bh->node_count < 2 )
+      return 0;
+
    int count = 0;
    u32 stack[100];
    u32 depth = 2;
@@ -202,7 +231,7 @@ static int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit )
                u32 idx = inode->start+i;
 
                if( bh->system->cast_ray )
-                  count += bh->system->cast_ray( bh->user, co, dir, hit );
+                  count += bh->system->cast_ray( bh->user, idx, co, dir, hit );
                else
                   count ++;
             }
@@ -231,8 +260,11 @@ static int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit )
    return count;
 }
 
-static int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
+VG_STATIC int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
 {
+   if( bh->node_count < 2 )
+      return 0;
+
    int count = 0;
    u32 stack[100];
    u32 depth = 2;
@@ -249,10 +281,7 @@ static int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
          if( inode->count )
          {
             if( count + inode->count >= len )
-            {
-               vg_error( "Maximum buffer reached!\n" );
                return count;
-            }
 
             for( u32 i=0; i<inode->count; i++ )
                buffer[ count ++ ] = inode->start+i;