X-Git-Url: https://harrygodden.com/git/?a=blobdiff_plain;f=bvh.h;h=9e4528604d59c8cf205f20d3d172b671102085e1;hb=ec0918b2ef17a71418a57417689fd3042915aeeb;hp=27e23b5af516dd0fc8ae809b7c6844400741cf7d;hpb=ecc4dfbfb3adf91d2dfc03ba0ec9a821fcc2390c;p=carveJwlIkooP6JGAAIwe30JlM.git

diff --git a/bvh.h b/bvh.h
index 27e23b5..9e45286 100644
--- 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"
@@ -14,30 +18,31 @@
  *   system: the system we created above which will deal with the data
  *
  * call bh_create( bh_tree *bh, u32 item_count )
- * static int bh_ray( bh_tree *bh, u32 inode, v3f co, v3f dir, ray_hit *hit )
- * static int bh_select( bh_tree *bh, boxf box, u32 *buffer, int len )
+ * 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
@@ -57,7 +62,7 @@ struct bh_system
    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 ];
 
@@ -69,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 );
 
@@ -124,18 +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, void *user, 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;
+   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->nodes = malloc( sizeof(bh_node) * (item_count*2-1) );
+   bh->max_per_leaf = max_per_leaf;
 
    bh_node *root = &bh->nodes[0];
    bh->node_count = 1;
@@ -148,11 +169,14 @@ static void bh_create( bh_tree *bh, bh_system *sys, void *user, u32 item_count )
    bh_update_bounds( bh, 0 );
    bh_subdivide( bh, 0 );
 
-   bh->nodes = realloc( bh->nodes, sizeof(bh_node) * 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 ];
 
@@ -182,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;
@@ -233,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;