-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; i<node->count; 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;
-
- /* To beat: 121,687 / 136,579
- * 136,375
- */
-
- float avg = 0.0;
- for( u32 t=0; t<node->count; 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)/3.0;
- }
- avg /= (float)node->count;
-
- split = avg;
-
- i32 i = node->start,
- j = i + node->count-1;
-
- 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) / 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 );
-}
-
-static void bvh_create( scene *s )
-{
- 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 );
-
- 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) );
-}
-
-static void bvh_debug_node( scene *s, u32 inode, v3f pos, u32 colour )
-{
- struct 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 )
- {
- vg_line_boxf( node->bbx, colour );
-
- 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; i<node->count; 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 ] ];
-
- vg_line( pa->co, pb->co, 0xff0000ff );
- vg_line( pb->co, pc->co, 0xff0000ff );
- vg_line( pc->co, pa->co, 0xff0000ff );
- }
- }
- }
-}
-
-static void bvh_debug( scene *s, v3f pos )
-{
- bvh_debug_node( s, 0, pos, 0x4000ffa8 );
-}
-
-typedef struct ray_hit ray_hit;
-struct ray_hit
-{
- float dist;
- u32 *tri;
- v3f pos, normal;
-};
-
-int ray_aabb( boxf box, v3f co, v3f dir, float dist )
-{
- v3f v0, v1;
- float tmin, tmax;
-
- v3_sub( box[0], co, v0 );
- v3_sub( box[1], co, v1 );
- v3_div( v0, dir, v0 );
- v3_div( v1, dir, v1 );
-
- tmin = vg_minf( v0[0], v1[0] );
- tmax = vg_maxf( v0[0], v1[0] );
- tmin = vg_maxf( tmin, vg_minf( v0[1], v1[1] ));
- tmax = vg_minf( tmax, vg_maxf( v0[1], v1[1] ));
- tmin = vg_maxf( tmin, vg_minf( v0[2], v1[2] ));
- tmax = vg_minf( tmax, vg_maxf( v0[2], v1[2] ));
-
- return tmax >= tmin && tmin < dist && tmax > 0;
-}
-
-static int bvh_ray_tri( scene *sc, u32 *tri, v3f co, v3f dir, ray_hit *hit )
-{
- v3f positions[3];
- for( int i=0; i<3; i++ )
- v3_copy( sc->verts[tri[i]].co, positions[i] );
-
- float t;
- if(ray_tri( positions, co, dir, &t ))
- {
- if( t < hit->dist )
- {
- hit->dist = t;
- hit->tri = tri;
- return 1;
- }
- }
-
- return 0;
-}
-
-static int bvh_ray( scene *s, u32 inode, v3f co, v3f dir, ray_hit *hit )
-{
- 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; i<node->count; 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;
-}
-
-static int bvh_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 );
-
- if( count )
- {
- //vg_line( co, pb, 0xff00ffff );
-
- v3f v0, v1;
-
- float *pa = s->verts[hit->tri[0]].co,
- *pb = s->verts[hit->tri[1]].co,
- *pc = s->verts[hit->tri[2]].co;
-
- v3_sub( pa, pb, v0 );
- v3_sub( pc, pb, v1 );
- v3_cross( v1, v0, hit->normal );
- 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 )
-{
- /* 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; i<inode->count; 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; i<node->count; 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;
-}
-
-#endif