+
+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 )
+{
+ float const kEpsilon = 0.00001f;
+
+ v3f v0, v1, h, s, q, n;
+ float a,f,u,v,t;
+
+ float *pa = sc->verts[tri[0]].co,
+ *pb = sc->verts[tri[1]].co,
+ *pc = sc->verts[tri[2]].co;
+
+ v3_sub( pb, pa, v0 );
+ v3_sub( pc, pa, v1 );
+ v3_cross( dir, v1, h );
+ v3_cross( v0, v1, n );
+
+ if( v3_dot( n, dir ) > 0.0f ) /* Backface culling */
+ return 0;
+
+ /* Parralel */
+ a = v3_dot( v0, h );
+ if( a > -kEpsilon && a < kEpsilon )
+ return 0;
+
+ f = 1.0f/a;
+ v3_sub( co, pa, s );
+
+ u = f * v3_dot(s, h);
+ if( u < 0.0f || u > 1.0f )
+ return 0;
+
+ v3_cross( s, v0, q );
+ v = f * v3_dot( dir, q );
+ if( v < 0.0f || u+v > 1.0f )
+ return 0;
+
+ t = f * v3_dot(v1, q);
+ if( t > kEpsilon && t < hit->dist )
+ {
+ hit->dist = t;
+ hit->tri = tri;
+ return 1;
+ }
+ else 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_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