From a6e1ee0f51aa5570b20aad658365dec896f8c9b8 Mon Sep 17 00:00:00 2001 From: hgn Date: Thu, 30 Jun 2022 04:09:47 +0100 Subject: [PATCH] move scene bh to bvh.h --- bvh.h | 16 +- player.h | 16 +- rigidbody.h | 4 +- scene.h | 555 +++++++--------------------------------------------- world.h | 10 +- 5 files changed, 89 insertions(+), 512 deletions(-) diff --git a/bvh.h b/bvh.h index c841939..a6a7468 100644 --- a/bvh.h +++ b/bvh.h @@ -13,7 +13,9 @@ * 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 ) + * 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 ) */ typedef struct bh_node bh_node; @@ -43,7 +45,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,7 +54,7 @@ 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 ) @@ -130,10 +131,11 @@ static void bh_subdivide( bh_tree *bh, u32 inode ) bh_subdivide( bh, ir ); } -static void bh_create( bh_tree *bh, bh_system *sys, u32 item_count ) +static void bh_create( bh_tree *bh, bh_system *sys, void *user, u32 item_count ) { bh->system = sys; - bh->nodes = malloc( sys->item_size * (item_count*2-1) ); + bh->user = user; + bh->nodes = malloc( sizeof(bh_node) * (item_count*2-1) ); bh_node *root = &bh->nodes[0]; bh->node_count = 1; @@ -146,7 +148,7 @@ 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 ); + bh->nodes = realloc( bh->nodes, sizeof(bh_node) * bh->node_count ); vg_success( "BVH done, size: %u/%u\n", bh->node_count, (item_count*2-1) ); } @@ -202,7 +204,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 ++; } diff --git a/player.h b/player.h index 984d4e3..7ab0e63 100644 --- a/player.h +++ b/player.h @@ -3,6 +3,7 @@ #include "common.h" #include "character.h" +#include "bvh.h" static int freecam = 0; static float k_walkspeed = 2.0f; @@ -644,7 +645,7 @@ static void player_walkgrid_samplepole( struct grid_sample *s ) u32 geo[256]; v3f tri[3]; - int len = bvh_select_triangles( &world.geo, region, geo, 256 ); + int len = bh_select( &world.geo.bhtris, region, geo, 256 ); const float k_minworld_y = -2000.0f; @@ -655,7 +656,7 @@ static void player_walkgrid_samplepole( struct grid_sample *s ) for( int i=0; ivertex_count ); } -float scene_tree_sway = 0.1f; - -#if 0 -static void scene_foliage_shader_use(void) -{ - SHADER_USE( shader_debug_vcol ); - - glUniformMatrix4fv( SHADER_UNIFORM( shader_debug_vcol, "uPv" ), - 1, GL_FALSE, (float *)vg_pv ); - - glUniform1i( SHADER_UNIFORM( shader_debug_vcol, "uMode" ), debugview ); - glUniform1i( SHADER_UNIFORM( shader_debug_vcol, "uTexMain" ), 0 ); - - glUniform1i( SHADER_UNIFORM( shader_debug_vcol, "uTexGradients" ), 1 ); - vg_tex2d_bind( &tex_gradients, 1 ); - - glUniform1i( SHADER_UNIFORM( shader_debug_vcol, "uTexNoise" ), 2 ); - glActiveTexture( GL_TEXTURE2 ); - glBindTexture( GL_TEXTURE_2D, tex_dual_noise ); - - glUniform1f( SHADER_UNIFORM( shader_debug_vcol, "uTime" ), vg_time ); - glUniform1f( SHADER_UNIFORM( shader_debug_vcol, "uSwayAmt" ), - scene_tree_sway ); -} -#endif - static void scene_bind( scene *pscene ) { mesh_bind( &pscene->mesh ); @@ -263,298 +244,75 @@ static void scene_register(void) { } - -/* Physics segment */ - -static int triangle_raycast2d( v3f pA, v3f pB, v3f pC, v3f ray, float *height ) -{ - v2f v0, v1, v2, vp, vp2; - float d, bca = 0.f, bcb = 0.f, bcc = 0.f; - - v0[0] = pB[0] - pA[0]; - v0[1] = pB[2] - pA[2]; - v1[0] = pC[0] - pA[0]; - v1[1] = pC[2] - pA[2]; - v2[0] = pB[0] - pC[0]; - v2[1] = pB[2] - pC[2]; - - d = 1.f / (v0[0]*v1[1] - v1[0]*v0[1]); - -#if 0 - /* Backface culling */ - if( v2_cross( v0, v1 ) > 0.f ) - return; -#endif - - vp[0] = ray[0] - pA[0]; - vp[1] = ray[2] - pA[2]; - - if( v2_cross( v0, vp ) > 0.f ) return 0; - if( v2_cross( vp, v1 ) > 0.f ) return 0; - - vp2[0] = ray[0] - pB[0]; - vp2[1] = ray[2] - pB[2]; - - if( v2_cross( vp2, v2 ) > 0.f ) return 0; - - bcb = (vp[0]*v1[1] - v1[0]*vp[1]) * d; - bcc = (v0[0]*vp[1] - vp[0]*v0[1]) * d; - bca = 1.f - bcb - bcc; - - *height = pA[1]*bca + pB[1]*bcb + pC[1]*bcc; - return 1; -} - -/* Temporary */ -static int sample_scene_height( scene *pscene, v3f pos, v3f norm ) -{ - for( int i=0; iindice_count/3; i++ ) - { - u32 *tri = &pscene->indices[i*3]; - - float *pA = pscene->verts[tri[0]].co, - *pB = pscene->verts[tri[1]].co, - *pC = pscene->verts[tri[2]].co; - - float height; - if( triangle_raycast2d( pA, pB, pC, pos, &height )) - { - pos[1] = height; - - if( norm ) - { - v3f v0, v1; - v3_sub( pA, pB, v0 ); - v3_sub( pC, pB, v1 ); - v3_cross( v1, v0, norm ); - v3_normalize( norm ); - } - - return 1; - } - } - return 0; -} - -static void sample_scene_normal( scene *pscene, v3f pos, v3f normal ) -{ - for( int i=0; iindice_count/3; i++ ) - { - u32 *tri = &pscene->indices[i*3]; - - float height; - if( triangle_raycast2d( - pscene->verts[ tri[0] ].co, - pscene->verts[ tri[1] ].co, - pscene->verts[ tri[2] ].co, pos, &height )) - { - v3f v0, v1; - - v3_sub( pscene->verts[ tri[1] ].co, - pscene->verts[ tri[0] ].co, - v0 ); - - v3_sub( pscene->verts[ tri[2] ].co, - pscene->verts[ tri[0] ].co, - v1 ); - - v3_cross( v0, v1, normal ); - v3_normalize( normal ); - return; - } - } - - normal[0] = 0.0f; - normal[1] = 1.0f; - normal[2] = 0.0f; -} - - /* - * - * - * TODO: THIS SHIT IS DEPRECATED FOR THE NEW SHIT IN BVH.H - * - * + * BVH implementation */ -struct bvh_node +static void scene_bh_expand_bound( void *user, boxf bound, u32 item_index ) { - boxf bbx; - - /* if il is 0, this is a leaf */ - u32 il, count; - union{ u32 ir, start; }; -}; - -static void bvh_update_bounds( scene *s, u32 inode ) -{ - bvh_node *node = &s->bvh.nodes[ inode ]; - - box_init_inf( node->bbx ); - for( u32 i=0; icount; i++ ) - { - u32 idx = node->start+i; - model_vert *pa = &s->verts[ s->indices[idx*3+0] ], - *pb = &s->verts[ s->indices[idx*3+1] ], - *pc = &s->verts[ s->indices[idx*3+2] ]; - - box_addpt( node->bbx, pa->co ); - box_addpt( node->bbx, pb->co ); - box_addpt( node->bbx, pc->co ); - } -} - -static void bvh_subdiv( scene *s, u32 inode ) -{ - bvh_node *node = &s->bvh.nodes[ inode ]; - - v3f extent; - v3_sub( node->bbx[1], node->bbx[0], extent ); - - int axis = 0; - if( extent[1] > extent[0] ) axis = 1; - if( extent[2] > extent[axis] ) axis = 2; - - float split = node->bbx[0][axis] + extent[axis]*0.5f; - - float avg = 0.0; - for( u32 t=0; tcount; t++ ) - { - u32 *ti = &s->indices[(node->start+t)*3]; - float a = s->verts[ti[0]].co[axis], - b = s->verts[ti[1]].co[axis], - c = s->verts[ti[2]].co[axis]; - avg += (a+b+c) * (1.0f/3.0f); - } - avg /= (float)node->count; - - split = avg; - - i32 i = node->start, - j = i + node->count-1; + scene *s = user; + model_vert *pa = &s->verts[ s->indices[item_index*3+0] ], + *pb = &s->verts[ s->indices[item_index*3+1] ], + *pc = &s->verts[ s->indices[item_index*3+2] ]; - while( i <= j ) - { - u32 *ti = &s->indices[i*3]; - - float a = s->verts[ti[0]].co[axis], - b = s->verts[ti[1]].co[axis], - c = s->verts[ti[2]].co[axis]; - - if( (a+b+c) * (1.0f/3.0f) < split ) - i ++; - else - { - /* Swap triangle indices */ - u32 *tj = &s->indices[j*3]; - u32 temp[3]; - temp[0] = ti[0]; - temp[1] = ti[1]; - temp[2] = ti[2]; - - ti[0] = tj[0]; - ti[1] = tj[1]; - ti[2] = tj[2]; - - tj[0] = temp[0]; - tj[1] = temp[1]; - tj[2] = temp[2]; - - j --; - } - } - - u32 left_count = i - node->start; - if( left_count == 0 || left_count == node->count ) return; - - u32 il = s->bvh.node_count ++, - ir = s->bvh.node_count ++; - - struct bvh_node *lnode = &s->bvh.nodes[il], - *rnode = &s->bvh.nodes[ir]; - - lnode->start = node->start; - lnode->count = left_count; - rnode->start = i; - rnode->count = node->count - left_count; - - node->il = il; - node->ir = ir; - node->count = 0; - - bvh_update_bounds( s, il ); - bvh_update_bounds( s, ir ); - bvh_subdiv( s, il ); - bvh_subdiv( s, ir ); + box_addpt( bound, pa->co ); + box_addpt( bound, pb->co ); + box_addpt( bound, pc->co ); } -static void bvh_create( scene *s ) +static float scene_bh_centroid( void *user, u32 item_index, int axis ) { - u32 triangle_count = s->indice_count / 3; - s->bvh.nodes = malloc( sizeof(struct bvh_node) * (triangle_count*2-1) ); - - bvh_node *root = &s->bvh.nodes[0]; - s->bvh.node_count = 1; - - root->il = 0; - root->ir = 0; - root->count = triangle_count; - root->start = 0; - - bvh_update_bounds( s, 0 ); - bvh_subdiv( s, 0 ); + scene *s = user; + model_vert *pa = &s->verts[ s->indices[item_index*3+0] ], + *pb = &s->verts[ s->indices[item_index*3+1] ], + *pc = &s->verts[ s->indices[item_index*3+2] ]; - s->bvh.nodes = - realloc( s->bvh.nodes, sizeof(struct bvh_node) * s->bvh.node_count ); - - vg_success( "BVH done, size: %u/%u\n", s->bvh.node_count, - (triangle_count*2-1) ); + return (pa->co[axis] + pb->co[axis] + pc->co[axis]) * (1.0f/3.0f); } -static void bvh_debug_node( scene *s, u32 inode, v3f pos, u32 colour ) +static void scene_bh_swap( void *user, u32 ia, u32 ib ) { - struct bvh_node *node = &s->bvh.nodes[ inode ]; + scene *s = user; - if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) && - (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) ) - { - if( !node->count ) - { - vg_line_boxf( node->bbx, colour ); + u32 *ti = &s->indices[ia*3]; + u32 *tj = &s->indices[ib*3]; - bvh_debug_node( s, node->il, pos, colour ); - bvh_debug_node( s, node->ir, pos, colour ); - } - else - { - vg_line_boxf( node->bbx, 0xff00ff00 ); - for( u32 i=0; icount; i++ ) - { - u32 idx = (node->start+i)*3; + u32 temp[3]; + temp[0] = ti[0]; + temp[1] = ti[1]; + temp[2] = ti[2]; - model_vert *pa = &s->verts[ s->indices[ idx+0 ] ], - *pb = &s->verts[ s->indices[ idx+1 ] ], - *pc = &s->verts[ s->indices[ idx+2 ] ]; + ti[0] = tj[0]; + ti[1] = tj[1]; + ti[2] = tj[2]; - vg_line( pa->co, pb->co, 0xff0000ff ); - vg_line( pb->co, pc->co, 0xff0000ff ); - vg_line( pc->co, pa->co, 0xff0000ff ); - } - } - } + tj[0] = temp[0]; + tj[1] = temp[1]; + tj[2] = temp[2]; } -static void bvh_debug( scene *s, v3f pos ) +static void scene_bh_debug( void *user, u32 item_index ) { - bvh_debug_node( s, 0, pos, 0x4000ffa8 ); + scene *s = user; + u32 idx = item_index*3; + model_vert *pa = &s->verts[ s->indices[ idx+0 ] ], + *pb = &s->verts[ s->indices[ idx+1 ] ], + *pc = &s->verts[ s->indices[ idx+2 ] ]; + + vg_line( pa->co, pb->co, 0xff0000ff ); + vg_line( pb->co, pc->co, 0xff0000ff ); + vg_line( pc->co, pa->co, 0xff0000ff ); } -static int bvh_ray_tri( scene *sc, u32 *tri, v3f co, v3f dir, ray_hit *hit ) +static int scene_bh_ray( void *user, u32 index, v3f co, v3f dir, ray_hit *hit ) { + scene *s = user; v3f positions[3]; + + u32 *tri = &s->indices[ index*3 ]; + for( int i=0; i<3; i++ ) - v3_copy( sc->verts[tri[i]].co, positions[i] ); + v3_copy( s->verts[tri[i]].co, positions[i] ); float t; if(ray_tri( positions, co, dir, &t )) @@ -570,89 +328,24 @@ static int bvh_ray_tri( scene *sc, u32 *tri, v3f co, v3f dir, ray_hit *hit ) return 0; } -static int bvh_ray( scene *s, u32 inode, v3f co, v3f dir, ray_hit *hit ) +static bh_system bh_system_scene = { -#if 0 - bvh_node *node = &s->bvh.nodes[ inode ]; - - if( !ray_aabb( node->bbx, co, dir, hit->dist )) - return 0; - - int count = 0; - - if( node->count ) - { - for( u32 i=0; icount; i++ ) - { - u32 *indices = &s->indices[ (node->start+i)*3 ]; - count += bvh_ray_tri( s, indices, co, dir, hit ); - } - } - else - { - count += bvh_ray( s, node->il, co, dir, hit ); - count += bvh_ray( s, node->ir, co, dir, hit ); - } - - return count; -#endif - - int count = 0; - u32 stack[100]; - u32 depth = 2; - - stack[0] = 0; - stack[1] = s->bvh.nodes[0].il; - stack[2] = s->bvh.nodes[0].ir; - - while(depth) - { - bvh_node *inode = &s->bvh.nodes[ stack[depth] ]; - if( ray_aabb( inode->bbx, co, dir, hit->dist ) ) - { - if( inode->count ) - { - for( u32 i=0; icount; i++ ) - { - u32 *indices = &s->indices[ (inode->start+i)*3 ]; - count += bvh_ray_tri( s, indices, co, dir, hit ); - } - - depth --; - } - else - { - if( depth+1 >= vg_list_size(stack) ) - { - vg_error( "Maximum stack reached!\n" ); - return count; - } - - stack[depth] = inode->il; - stack[depth+1] = inode->ir; - depth ++; - } - } - else - { - depth --; - } - } - - return count; -} + .expand_bound = scene_bh_expand_bound, + .item_centroid = scene_bh_centroid, + .item_swap = scene_bh_swap, + .item_debug = scene_bh_debug, + .cast_ray = scene_bh_ray +}; -static int bvh_raycast( scene *s, v3f co, v3f dir, ray_hit *hit ) +/* + * An extra step is added onto the end to calculate the hit normal + */ +static int scene_raycast( scene *s, v3f co, v3f dir, ray_hit *hit ) { - v3f pb; - v3_muladds( co, dir, hit->dist, pb ); - - int count = bvh_ray( s, 0, co, dir, hit ); + int count = bh_ray( &s->bhtris, 0, co, dir, hit ); if( count ) { - //vg_line( co, pb, 0xff00ffff ); - v3f v0, v1; float *pa = s->verts[hit->tri[0]].co, @@ -665,128 +358,14 @@ static int bvh_raycast( scene *s, v3f co, v3f dir, ray_hit *hit ) v3_normalize( hit->normal ); v3_muladds( co, dir, hit->dist, hit->pos ); } - else - { - //vg_line( co, pb, 0xff0000ff ); - } return count; } -static int bvh_select_triangles( scene *s, boxf box, u32 *triangles, int len ) +static void scene_bh_create( scene *s ) { - /* TODO: use this stack system on the raycast function */ - int count = 0; - u32 stack[100]; - u32 depth = 2; - - stack[0] = 0; - stack[1] = s->bvh.nodes[0].il; - stack[2] = s->bvh.nodes[0].ir; - - while(depth) - { - bvh_node *inode = &s->bvh.nodes[ stack[depth] ]; - if( box_overlap( inode->bbx, box ) ) - { - if( inode->count ) - { - if( count + inode->count >= len ) - { - vg_error( "Maximum buffer reached!\n" ); - return count; - } - - for( u32 i=0; icount; i++ ) - triangles[ count ++ ] = (inode->start+i)*3; - - depth --; - } - else - { - if( depth+1 >= vg_list_size(stack) ) - { - vg_error( "Maximum stack reached!\n" ); - return count; - } - - stack[depth] = inode->il; - stack[depth+1] = inode->ir; - depth ++; - } - } - else - { - depth --; - } - } - - return count; -} - -static int bvh_scene_sample_node_h( scene *s, u32 inode, v3f pos, v3f norm ) -{ - bvh_node *node = &s->bvh.nodes[ inode ]; - - if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) && - (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) ) - { - if( !node->count ) - { - if( bvh_scene_sample_node_h( s, node->il, pos, norm )) return 1; - if( bvh_scene_sample_node_h( s, node->ir, pos, norm )) return 1; - } - else - { - for( u32 i=0; icount; i++ ) - { - u32 idx = (node->start+i)*3; - model_vert *pa = &s->verts[ s->indices[ idx+0 ] ], - *pb = &s->verts[ s->indices[ idx+1 ] ], - *pc = &s->verts[ s->indices[ idx+2 ] ]; - - float height; - if( triangle_raycast2d( pa->co, pb->co, pc->co, pos, &height )) - { - pos[1] = height; - - if( norm ) - { - v3f v0, v1; - v3_sub( pa->co, pb->co, v0 ); - v3_sub( pc->co, pb->co, v1 ); - v3_cross( v1, v0, norm ); - v3_normalize( norm ); - } - - return 1; - } - } - } - } - - return 0; -} - -static int bvh_scene_sample_h( scene *s, v3f pos, v3f norm) -{ - return bvh_scene_sample_node_h( s, 0, pos, norm ); -} - -static int bvh_scene_sample( scene *s, v3f pos, ray_hit *hit ) -{ - hit->dist = INFINITY; - - v3f ray_pos; - v3_add( pos, (v3f){0.0f,4.0f,0.0f}, ray_pos ); - - if( bvh_raycast( s, ray_pos, (v3f){0.0f,-1.0f,0.0f}, hit )) - { - pos[1] = hit->pos[1]; - return 1; - } - - return 0; + u32 triangle_count = s->indice_count / 3; + bh_create( &s->bhtris, &bh_system_scene, s, triangle_count ); } #endif diff --git a/world.h b/world.h index 7272b80..ea5a5c4 100644 --- a/world.h +++ b/world.h @@ -36,8 +36,6 @@ static struct gworld } world; - - static void render_world( m4x4f projection, m4x3f camera ) { render_sky( camera ); @@ -63,7 +61,7 @@ static void ray_world_get_tri( ray_hit *hit, v3f tri[3] ) static int ray_world( v3f pos, v3f dir, ray_hit *hit ) { - return bvh_raycast( &world.geo, pos, dir, hit ); + return scene_raycast( &world.geo, pos, dir, hit ); } static int ray_hit_is_ramp( ray_hit *hit ) @@ -150,7 +148,7 @@ static void world_load(void) } scene_upload( &world.geo ); - bvh_create( &world.geo ); + scene_bh_create( &world.geo ); water_compute_depth( world.geo.bbx ); @@ -238,8 +236,8 @@ static void world_load(void) free( mfoliage ); scene_upload( &world.foliage ); - world.bhcubes.user = world.temp_rbs; - bh_create( &world.bhcubes, &bh_system_rigidbodies, world.rb_count ); + bh_create( &world.bhcubes, + &bh_system_rigidbodies, world.temp_rbs, world.rb_count ); } #endif /* WORLD_H */ -- 2.25.1