scene.h

   1 #ifndef SCENE_H
   2 #define SCENE_H
   3
   4 #include "vg/vg.h"
   5 #include "model.h"
   6
   7 typedef struct scene scene;
   8 typedef struct bvh_node bvh_node;
   9
  10 struct scene
  11 {
  12    glmesh mesh;
  13
  14    model_vert *verts;
  15    u32 *indices;
  16
  17    struct
  18    {
  19       bvh_node *nodes;
  20       u32 node_count;
  21    }
  22    bvh;
  23
  24    u32 vertex_count,
  25        indice_count,
  26        vertex_cap,
  27        indice_cap;
  28
  29    boxf bbx;
  30
  31    struct shadower
  32    {
  33       sdf_primative sdf;
  34       esdf_type sdf_type;
  35    }
  36    *shadowers;
  37
  38    u32 shadower_count,
  39        shadower_cap;
  40
  41    submodel submesh;
  42 };
  43
  44 GLuint tex_dual_noise;
  45
  46 static void scene_init( scene *pscene )
  47 {
  48    pscene->verts = NULL;
  49    pscene->indices = NULL;
  50    pscene->vertex_count = 0;
  51    pscene->indice_count = 0;
  52    pscene->shadowers = NULL;
  53    pscene->shadower_count = 0;
  54    pscene->shadower_cap = 0;
  55    pscene->submesh.indice_start = 0;
  56    pscene->submesh.indice_count = 0;
  57
  58    v3_fill( pscene->bbx[0],  999999.9f );
  59    v3_fill( pscene->bbx[1], -999999.9f );
  60
  61    static int noise_ready = 0;
  62    if( !noise_ready )
  63    {
  64       noise_ready = 1;
  65
  66       u8 *buf = malloc( 256*256*2 );
  67
  68       for( int i=0; i<256*256; i++ )
  69       {
  70          u8 val = rand()&0xff;
  71          buf[i*2] = val;
  72       }
  73
  74       for( int y=0; y<256; y++ )
  75       {
  76          for( int x=0; x<256; x++ )
  77          {
  78             u8 *pr = &buf[(y*256+x)*2],
  79                *pg = &buf[(((y+17)&0xff)*256+((x+37)&0xff))*2+1];
  80             *pg = *pr;
  81          }
  82       }
  83
  84       /* TODO: This texture should be delted somewhere */
  85       glGenTextures( 1, &tex_dual_noise );
  86       glBindTexture( GL_TEXTURE_2D, tex_dual_noise );
  87       glTexImage2D( GL_TEXTURE_2D, 0, GL_RG, 256, 256, 0, GL_RG,
  88             GL_UNSIGNED_BYTE, buf );
  89
  90       vg_tex2d_linear();
  91       vg_tex2d_repeat();
  92
  93       free( buf );
  94    }
  95 }
  96
  97 static void *buffer_reserve( void *buffer, u32 count, u32 *cap, u32 amount,
  98       size_t emsize )
  99 {
 100    if( count+amount > *cap )
 101    {
 102       *cap = VG_MAX( (*cap)*2, (*cap)+amount );
 103
 104       return realloc( buffer, (*cap) * emsize );
 105    }
 106
 107    return buffer;
 108 }
 109
 110 /*
 111  * Append a model into the scene with a given transform
 112  */
 113 static void scene_add_model( scene *pscene, model *mdl, submodel *submodel,
 114       v3f pos, float yaw, float scale )
 115 {
 116    pscene->verts = buffer_reserve( pscene->verts, pscene->vertex_count,
 117          &pscene->vertex_cap, submodel->vertex_count, sizeof(model_vert) );
 118    pscene->indices = buffer_reserve( pscene->indices, pscene->indice_count,
 119          &pscene->indice_cap, submodel->indice_count, sizeof(u32) );
 120
 121    if( submodel->sdf_type )
 122    {
 123       pscene->shadowers = buffer_reserve( pscene->shadowers,
 124             pscene->shadower_count, &pscene->shadower_cap, 1,
 125             sizeof( struct shadower ));
 126
 127       struct shadower *shadower =
 128          &pscene->shadowers[ pscene->shadower_count ++ ];
 129
 130       shadower->sdf = submodel->sdf;
 131       shadower->sdf_type = submodel->sdf_type;
 132
 133       v2_muls( shadower->sdf.info, scale, shadower->sdf.info );
 134       v3_muls( shadower->sdf.origin, scale, shadower->sdf.origin );
 135       v3_add( pos, shadower->sdf.origin, shadower->sdf.origin );
 136    }
 137
 138    /* Transform and place vertices */
 139    model_vert *src_verts = submodel_vert_data( mdl, submodel );
 140    u32 *src_indices = submodel_indice_data( mdl, submodel );
 141
 142    m4x3f mtx;
 143    m4x3_identity( mtx );
 144    m4x3_translate( mtx, pos );
 145    m4x3_rotate_y( mtx, yaw );
 146    m4x3_scale( mtx, scale );
 147
 148    boxf bbxnew;
 149    box_copy( submodel->bbx, bbxnew );
 150    m4x3_transform_aabb( mtx, bbxnew );
 151    box_concat( pscene->bbx, bbxnew );
 152
 153    m3x3f rotation;
 154    m4x3_to_3x3( mtx, rotation );
 155
 156    float rand_hue = vg_randf();
 157
 158    for( u32 i=0; i<submodel->vertex_count; i++ )
 159    {
 160       model_vert *pvert = &pscene->verts[ pscene->vertex_count+i ],
 161                  *src = &src_verts[ i ];
 162
 163       m4x3_mulv( mtx, src->co, pvert->co );
 164       m3x3_mulv( rotation, src->norm, pvert->norm );
 165
 166       v4_copy( src->colour, pvert->colour );
 167       v2_copy( src->uv, pvert->uv );
 168
 169       float rel_y = src->co[1] / submodel->bbx[1][1];
 170       pvert->colour[0] = rel_y;
 171       pvert->colour[2] = rand_hue;
 172    }
 173
 174    for( u32 i=0; i<submodel->indice_count; i++ )
 175    {
 176       u32 *pidx = &pscene->indices[ pscene->indice_count+i ];
 177       *pidx = src_indices[i] + pscene->vertex_count;
 178    }
 179
 180    pscene->vertex_count += submodel->vertex_count;
 181    pscene->indice_count += submodel->indice_count;
 182 }
 183
 184 static void scene_add_foliage( scene *pscene, model *mdl, submodel *submodel,
 185       m4x3f transform )
 186 {
 187    pscene->verts = buffer_reserve( pscene->verts, pscene->vertex_count,
 188          &pscene->vertex_cap, submodel->vertex_count, sizeof(model_vert) );
 189    pscene->indices = buffer_reserve( pscene->indices, pscene->indice_count,
 190          &pscene->indice_cap, submodel->indice_count, sizeof(u32) );
 191
 192    /* Transform and place vertices */
 193    model_vert *src_verts = submodel_vert_data( mdl, submodel );
 194    u32 *src_indices = submodel_indice_data( mdl, submodel );
 195
 196    boxf bbxnew;
 197    box_copy( submodel->bbx, bbxnew );
 198    m4x3_transform_aabb( transform, bbxnew );
 199    box_concat( pscene->bbx, bbxnew );
 200
 201    float rand_hue = vg_randf();
 202    for( u32 i=0; i<submodel->vertex_count; i++ )
 203    {
 204       model_vert *pvert = &pscene->verts[ pscene->vertex_count+i ],
 205                  *src = &src_verts[ i ];
 206
 207       m4x3_mulv( transform, src->co, pvert->co );
 208       m3x3_mulv( transform, src->norm, pvert->norm );
 209
 210       v4_copy( src->colour, pvert->colour );
 211       v2_copy( src->uv, pvert->uv );
 212
 213       float rel_y = src->co[1] / submodel->bbx[1][1];
 214       pvert->colour[0] = rel_y;
 215       pvert->colour[2] = rand_hue;
 216    }
 217
 218    for( u32 i=0; i<submodel->indice_count; i++ )
 219    {
 220       u32 *pidx = &pscene->indices[ pscene->indice_count+i ];
 221       *pidx = src_indices[i] + pscene->vertex_count;
 222    }
 223
 224    pscene->vertex_count += submodel->vertex_count;
 225    pscene->indice_count += submodel->indice_count;
 226 }
 227
 228 static void scene_copy_slice( scene *pscene, submodel *sm )
 229 {
 230    sm->indice_start = pscene->submesh.indice_start;
 231    sm->indice_count = pscene->indice_count - sm->indice_start;
 232
 233    sm->vertex_start = pscene->submesh.vertex_start;
 234    sm->vertex_count = pscene->vertex_count - sm->vertex_start;
 235
 236    pscene->submesh.indice_start = pscene->indice_count;
 237    pscene->submesh.vertex_start = pscene->vertex_count;
 238 }
 239
 240 static void scene_shadow_sphere( scene *pscene, v3f sphere,
 241       v4f params, v3f lightdir )
 242 {
 243    for( int i=0; i<pscene->vertex_count; i++ )
 244    {
 245       model_vert *vert = &pscene->verts[i];
 246
 247       v3f delta;
 248       v3_sub( sphere, vert->co, delta );
 249
 250       float d = v3_dot( lightdir, delta );
 251       v3f closest;
 252
 253       v3_muls( lightdir, d, closest );
 254       float dist = v3_dist( closest, delta ),
 255             shading = vg_maxf( dist - params[0], 0.0f );
 256
 257       shading = vg_minf( shading * params[1], 1.0f );
 258       vert->colour[1] *= shading;
 259    }
 260 }
 261
 262 static void scene_shadow_gradient( scene *pscene, int comp,
 263       float start, float length )
 264 {
 265    float scale = 1.0f / length;
 266
 267    for( int i=0; i<pscene->vertex_count; i++ )
 268    {
 269       model_vert *vert = &pscene->verts[i];
 270       float shading = start + vert->co[comp] * scale;
 271
 272       vert->colour[1] = shading;
 273    }
 274 }
 275
 276
 277 /*
 278  * Experimental SDF based shadows
 279  *
 280  * https://iquilezles.org/articles/distfunctions/
 281  */
 282 static float sd_cone( v3f co, sdf_primative *prim )
 283 {
 284    float bound = prim->info[1]*1.75f;
 285    if( v3_dist2( prim->origin, co ) > bound*bound )
 286       return 999999.9f;
 287
 288    v3f p;
 289    v3_sub( co, prim->origin, p );
 290
 291    float h = prim->info[1];
 292    v2f c = { prim->info[2], prim->info[3] };
 293
 294    v2f q, w, a, b;
 295    v2_muls( (v2f){ c[0]/c[1], -1.0f }, h, q );
 296
 297    w[0] = v2_length( (v2f){ p[0], p[2] } );
 298    w[1] = p[1];
 299
 300    v2_muladds( w, q, -vg_clampf( v2_dot(w,q)/v2_dot(q,q), 0.0f, 1.0f ), a );
 301    v2_muladd( w, q, (v2f){ vg_clampf( w[0]/q[0], 0.0f, 1.0f ), 1.0f }, b );
 302
 303    float k = vg_signf( q[1] ),
 304          d = vg_minf( v2_dot( a,a ), v2_dot( b,b ) ),
 305          s = vg_maxf( k*(w[0]*q[1]-w[1]*q[0]), k*(w[1]-q[1]) );
 306
 307    return sqrtf(d)*vg_signf(s);
 308 }
 309
 310 #define CACHE_AMBIENT_SHAPES
 311
 312 static float scene_ambient_sample( scene *pscene, v3f pos, v3f dir )
 313 {
 314    float accum = 0.0f;
 315
 316 #ifdef CACHE_AMBIENT_SHAPES
 317    static struct shadower *local_shadowers[32];
 318    static int local_shadower_count = 0;
 319    static v3f local_shadower_last = { -99999.9f, -999999.9f, -9999999.9f };
 320
 321    if( v3_dist2( pos, local_shadower_last ) > 10.0f*10.0f )
 322    {
 323       local_shadower_count = 0;
 324       v3_copy( pos, local_shadower_last );
 325
 326       for( int k=0; k<pscene->shadower_count; k++ )
 327       {
 328          struct shadower *shadower = &pscene->shadowers[k];
 329
 330          if( sd_cone( pos, &shadower->sdf ) <= 20.0f )
 331          {
 332             local_shadowers[ local_shadower_count ++ ] = shadower;
 333             if( local_shadower_count == vg_list_size( local_shadowers ) )
 334                break;
 335          }
 336       }
 337    }
 338 #endif
 339
 340    for( int j=0; j<5; j++ )
 341    {
 342       v3f tracepos;
 343       v3_muladds( pos, dir, 1.5f*(float)j, tracepos );
 344
 345       float mindist = 99999.9f;
 346
 347 #ifndef CACHE_AMBIENT_SHAPES
 348
 349       for( int k=0; k<pscene->shadower_count; k++ ){
 350          struct shadower *shadower = &pscene->shadowers[k];
 351 #else
 352
 353       for( int k=0; k<local_shadower_count; k++ ){
 354          struct shadower *shadower = local_shadowers[k];
 355 #endif
 356
 357          float dist = vg_maxf( 0.0f, sd_cone( tracepos, &shadower->sdf ));
 358          mindist = vg_minf( mindist, dist );
 359       }
 360
 361
 362       accum += vg_clampf( 1.0f - mindist, 0.0f, 1.0f )*0.2f;
 363    }
 364
 365    return accum;
 366 }
 367
 368 #define DYNAMIC_GRID
 369 #define JUST_DO_EVERY_VERT
 370
 371 static void scene_compute_occlusion( scene *pscene )
 372 {
 373    v3f sundir = { 0.2f, 0.9f, 0.2f };
 374    v3_normalize( sundir );
 375
 376    /* TODO: Make this sample grid be dynamically required.
 377     *
 378     *   1. Only resample the light grid (1x1x1), when a vertex is outside the
 379     *      current cube
 380     *
 381     *   2. Reorder all vertices so that each group of vertices that fit in a
 382     *      cube are next to eachother in the buffer. This will save cache
 383     *      misses.
 384     *
 385     *      for the sorting algorithm, i think we can already assume that *most
 386     *      vertices will be quite close to eachother. so instead of doing an
 387     *      exhaustive search we can reorder 1k chunks at a time.
 388     */
 389
 390    v3f sample_area;
 391    v3_sub( pscene->bbx[1], pscene->bbx[0], sample_area );
 392    v3_ceil( sample_area, sample_area );
 393    int ax = sample_area[0],
 394        ay = sample_area[1],
 395        az = sample_area[2];
 396
 397 #ifndef DYNAMIC_GRID
 398    float *samplegrid = malloc( ax*ay*az* sizeof(float) );
 399
 400    for( int x=0; x<ax; x++ ){
 401    for( int y=0; y<ay; y++ ){
 402    for( int z=0; z<az; z++ )
 403    {
 404       v3f sample_pos = { x,y,z };
 405       v3_add( pscene->bbx[0], sample_pos, sample_pos );
 406       float accum = scene_ambient_sample( pscene, sample_pos, sundir );
 407
 408       samplegrid[x + y*ax + z*ax*ay] = accum;
 409    }}}
 410 #else
 411    v3i cube_pos = { -999999, -999999, -999999 };
 412    int cube_resamples = 0, hits = 0, misses = 0;
 413
 414    float s0=0.0f,s1=0.0f,s2=0.0f,s3=0.0f,s4=0.0f,s5=0.0f,s6=0.0f,s7=0.0f;
 415 #endif
 416
 417    for( int i=0; i<pscene->vertex_count; i++ )
 418    {
 419       model_vert *vert = &pscene->verts[i];
 420       v3f rel, q;
 421
 422 #ifndef DYNAMIC_GRID
 423       v3_sub( vert->co, pscene->bbx[0], q );
 424 #else
 425       v3_copy( vert->co, q );
 426 #endif
 427
 428       v3_floor( q, rel );
 429       v3_sub( q, rel, q );
 430
 431       int x=rel[0],
 432           y=rel[1],
 433           z=rel[2];
 434
 435 #ifndef JUST_DO_EVERY_VERT
 436 #ifndef DYNAMIC_GRID
 437       x = VG_MIN(x,ax-2);
 438       y = VG_MIN(y,ay-2);
 439       z = VG_MIN(z,az-2);
 440       x = VG_MAX(x,0);
 441       y = VG_MAX(y,0);
 442       z = VG_MAX(z,0);
 443
 444       float
 445          s0 = samplegrid[ x    +  y*ax    + z*ax*ay],
 446          s1 = samplegrid[(x+1) +  y*ax    + z*ax*ay],
 447          s2 = samplegrid[ x    + (y+1)*ax + z*ax*ay],
 448          s3 = samplegrid[(x+1) + (y+1)*ax + z*ax*ay],
 449          s4 = samplegrid[ x    +  y*ax    + (z+1)*ax*ay],
 450          s5 = samplegrid[(x+1) +  y*ax    + (z+1)*ax*ay],
 451          s6 = samplegrid[ x    + (y+1)*ax + (z+1)*ax*ay],
 452          s7 = samplegrid[(x+1) + (y+1)*ax + (z+1)*ax*ay],
 453 #else
 454       if( x!=cube_pos[0] || y!=cube_pos[1] || z!=cube_pos[2] )
 455       {
 456          cube_pos[0] = x;
 457          cube_pos[1] = y;
 458          cube_pos[2] = z;
 459
 460          s0 = scene_ambient_sample( pscene, (v3f){ x,y,z }, sundir );
 461          s1 = scene_ambient_sample( pscene, (v3f){ x+1,y,z }, sundir );
 462          s2 = scene_ambient_sample( pscene, (v3f){ x,y+1,z }, sundir );
 463          s3 = scene_ambient_sample( pscene, (v3f){ x+1,y+1,z }, sundir );
 464          s4 = scene_ambient_sample( pscene, (v3f){ x,y,z+1 }, sundir );
 465          s5 = scene_ambient_sample( pscene, (v3f){ x+1,y,z+1 }, sundir );
 466          s6 = scene_ambient_sample( pscene, (v3f){ x,y+1,z+1 }, sundir );
 467          s7 = scene_ambient_sample( pscene, (v3f){ x+1,y+1,z+1 }, sundir );
 468
 469          cube_resamples += 8;
 470          misses ++;
 471       }
 472       else
 473          hits ++;
 474
 475       float
 476 #endif
 477
 478          s0_s1 = vg_lerpf( s0, s1, q[0] ),
 479          s2_s3 = vg_lerpf( s2, s3, q[0] ),
 480          s4_s5 = vg_lerpf( s4, s5, q[0] ),
 481          s6_s7 = vg_lerpf( s6, s7, q[0] ),
 482
 483          s0s1_s2s3 = vg_lerpf( s0_s1, s2_s3, q[1] ),
 484          s4s5_s6s7 = vg_lerpf( s4_s5, s6_s7, q[1] ),
 485          s0s1s2s3_s4s5s6s7 = vg_lerpf( s0s1_s2s3, s4s5_s6s7, q[2] );
 486
 487       vert->colour[1] = s0s1s2s3_s4s5s6s7;
 488 #else
 489       vert->colour[1] = scene_ambient_sample( pscene, vert->co, sundir );
 490 #endif
 491    }
 492
 493 #ifndef DYNAMIC_GRID
 494    int cube_resamples = -1, misses = 0, hits = 0;
 495 #endif
 496
 497    int static_samples = ax*ay*az,
 498        vertex_samples = pscene->vertex_count;
 499
 500    if( cube_resamples < static_samples )
 501       vg_success( "Walking cube beat static grid (%d<%d. %d)!\n",
 502          cube_resamples, static_samples, vertex_samples );
 503    else
 504       vg_warn( "Walking cube was worse than static grid (%d<%d. %d).\n",
 505          cube_resamples, static_samples, vertex_samples );
 506
 507    vg_info( "Hits; %d, misses: %d\n", hits, misses );
 508
 509 #ifndef DYNAMIC_GRID
 510    free( samplegrid );
 511 #endif
 512
 513    return;
 514
 515    for( int i=0; i<pscene->vertex_count; i++ )
 516    {
 517       model_vert *vert = &pscene->verts[i];
 518       float accum = 0.0f;
 519
 520       for( int j=0; j<5; j++ )
 521       {
 522          v3f tracepos;
 523          v3_copy( vert->co, tracepos );
 524          v3_muladds( tracepos, sundir, 1.5f*(float)j, tracepos );
 525
 526          float mindist = 99999.9f;
 527
 528          for( int k=0; k<pscene->shadower_count; k++ )
 529          {
 530             struct shadower *shadower = &pscene->shadowers[k];
 531             float dist = vg_maxf( 0.0f, sd_cone( tracepos, &shadower->sdf ));
 532             mindist = vg_minf( mindist, dist );
 533          }
 534
 535          accum += vg_clampf( 1.0f - mindist, 0.0f, 1.0f )*0.2f;
 536       }
 537
 538       vert->colour[1] = vg_minf( accum, 1.0f );
 539    }
 540 }
 541
 542 static void scene_upload( scene *pscene )
 543 {
 544    mesh_upload( &pscene->mesh,
 545          pscene->verts, pscene->vertex_count,
 546          pscene->indices, pscene->indice_count );
 547
 548    vg_info( "Scene upload\n" );
 549    vg_info( "   indices:%u\n", pscene->indice_count );
 550    vg_info( "   verts:%u\n", pscene->vertex_count );
 551 }
 552
 553 float scene_tree_sway = 0.1f;
 554
 555 #if 0
 556 static void scene_foliage_shader_use(void)
 557 {
 558    SHADER_USE( shader_debug_vcol );
 559
 560         glUniformMatrix4fv( SHADER_UNIFORM( shader_debug_vcol, "uPv" ),
 561          1, GL_FALSE, (float *)vg_pv );
 562
 563    glUniform1i( SHADER_UNIFORM( shader_debug_vcol, "uMode" ), debugview );
 564    glUniform1i( SHADER_UNIFORM( shader_debug_vcol, "uTexMain" ), 0 );
 565
 566    glUniform1i( SHADER_UNIFORM( shader_debug_vcol, "uTexGradients" ), 1 );
 567    vg_tex2d_bind( &tex_gradients, 1 );
 568
 569    glUniform1i( SHADER_UNIFORM( shader_debug_vcol, "uTexNoise" ), 2 );
 570    glActiveTexture( GL_TEXTURE2 );
 571    glBindTexture( GL_TEXTURE_2D, tex_dual_noise );
 572
 573    glUniform1f( SHADER_UNIFORM( shader_debug_vcol, "uTime" ), vg_time );
 574    glUniform1f( SHADER_UNIFORM( shader_debug_vcol, "uSwayAmt" ),
 575          scene_tree_sway );
 576 }
 577 #endif
 578
 579 static void scene_bind( scene *pscene )
 580 {
 581    mesh_bind( &pscene->mesh );
 582 }
 583
 584 static void scene_draw( scene *pscene )
 585 {
 586    mesh_drawn( 0, pscene->indice_count );
 587 }
 588
 589 static void scene_debugsdf( scene *pscene )
 590 {
 591    for( int i=0; i<pscene->shadower_count; i++ )
 592    {
 593       struct shadower *shadower = &pscene->shadowers[i];
 594
 595       v3f base, side;
 596       v3_copy( shadower->sdf.origin, base );
 597       base[1] -= shadower->sdf.info[1];
 598       v3_copy( base, side );
 599       side[0] += shadower->sdf.info[0];
 600
 601       vg_line2( shadower->sdf.origin, base, 0xff00ff00, 0xff0000ff );
 602       vg_line2( side, base, 0xff00ff00, 0xff0000ff );
 603       vg_line( side, shadower->sdf.origin, 0xff00ff00 );
 604    }
 605
 606    v3f p0 = { pscene->bbx[0][0], pscene->bbx[0][1], pscene->bbx[0][2] },
 607        p1 = { pscene->bbx[0][0], pscene->bbx[1][1], pscene->bbx[0][2] },
 608        p2 = { pscene->bbx[1][0], pscene->bbx[1][1], pscene->bbx[0][2] },
 609        p3 = { pscene->bbx[1][0], pscene->bbx[0][1], pscene->bbx[0][2] },
 610
 611        p4 = { pscene->bbx[0][0], pscene->bbx[0][1], pscene->bbx[1][2] },
 612        p5 = { pscene->bbx[0][0], pscene->bbx[1][1], pscene->bbx[1][2] },
 613        p6 = { pscene->bbx[1][0], pscene->bbx[1][1], pscene->bbx[1][2] },
 614        p7 = { pscene->bbx[1][0], pscene->bbx[0][1], pscene->bbx[1][2] };
 615
 616    u32 col = 0xffff00c8;
 617    vg_line( p0, p1, col );
 618    vg_line( p1, p2, col );
 619    vg_line( p2, p3, col );
 620    vg_line( p3, p0, col );
 621
 622    vg_line( p4, p5, col );
 623    vg_line( p5, p6, col );
 624    vg_line( p6, p7, col );
 625    vg_line( p7, p4, col );
 626
 627    vg_line( p0, p4, col );
 628    vg_line( p1, p5, col );
 629    vg_line( p2, p6, col );
 630    vg_line( p3, p7, col );
 631 }
 632
 633 static void scene_register(void)
 634 {
 635 }
 636
 637
 638 /* Physics segment */
 639
 640 static int triangle_raycast2d( v3f pA, v3f pB, v3f pC, v3f ray, float *height )
 641 {
 642         v2f v0, v1, v2, vp, vp2;
 643         float d, bca = 0.f, bcb = 0.f, bcc = 0.f;
 644
 645    v0[0] = pB[0] - pA[0];
 646    v0[1] = pB[2] - pA[2];
 647    v1[0] = pC[0] - pA[0];
 648    v1[1] = pC[2] - pA[2];
 649    v2[0] = pB[0] - pC[0];
 650    v2[1] = pB[2] - pC[2];
 651
 652         d = 1.f / (v0[0]*v1[1] - v1[0]*v0[1]);
 653
 654 #if 0
 655         /* Backface culling */
 656         if( v2_cross( v0, v1 ) > 0.f )
 657                 return;
 658 #endif
 659
 660    vp[0] = ray[0] - pA[0];
 661    vp[1] = ray[2] - pA[2];
 662
 663    if( v2_cross( v0, vp ) > 0.f ) return 0;
 664    if( v2_cross( vp, v1 ) > 0.f ) return 0;
 665
 666    vp2[0] = ray[0] - pB[0];
 667    vp2[1] = ray[2] - pB[2];
 668
 669    if( v2_cross( vp2, v2 ) > 0.f ) return 0;
 670
 671    bcb = (vp[0]*v1[1] - v1[0]*vp[1]) * d;
 672    bcc = (v0[0]*vp[1] - vp[0]*v0[1]) * d;
 673    bca = 1.f - bcb - bcc;
 674
 675    *height = pA[1]*bca + pB[1]*bcb + pC[1]*bcc;
 676    return 1;
 677 }
 678
 679 /* Temporary */
 680 static int sample_scene_height( scene *pscene, v3f pos, v3f norm )
 681 {
 682    for( int i=0; i<pscene->indice_count/3; i++ )
 683    {
 684       u32 *tri = &pscene->indices[i*3];
 685
 686       float *pA = pscene->verts[tri[0]].co,
 687             *pB = pscene->verts[tri[1]].co,
 688             *pC = pscene->verts[tri[2]].co;
 689
 690       float height;
 691       if( triangle_raycast2d( pA, pB, pC, pos, &height ))
 692       {
 693          pos[1] = height;
 694
 695          if( norm )
 696          {
 697             v3f v0, v1;
 698             v3_sub( pA, pB, v0 );
 699             v3_sub( pC, pB, v1 );
 700             v3_cross( v1, v0, norm );
 701             v3_normalize( norm );
 702          }
 703
 704          return 1;
 705       }
 706    }
 707    return 0;
 708 }
 709
 710 static void sample_scene_normal( scene *pscene, v3f pos, v3f normal )
 711 {
 712    for( int i=0; i<pscene->indice_count/3; i++ )
 713    {
 714       u32 *tri = &pscene->indices[i*3];
 715
 716       float height;
 717       if( triangle_raycast2d(
 718             pscene->verts[ tri[0] ].co,
 719             pscene->verts[ tri[1] ].co,
 720             pscene->verts[ tri[2] ].co, pos, &height ))
 721       {
 722          v3f v0, v1;
 723
 724          v3_sub( pscene->verts[ tri[1] ].co,
 725                  pscene->verts[ tri[0] ].co,
 726                  v0 );
 727
 728          v3_sub( pscene->verts[ tri[2] ].co,
 729                  pscene->verts[ tri[0] ].co,
 730                  v1 );
 731
 732          v3_cross( v0, v1, normal );
 733          v3_normalize( normal );
 734          return;
 735       }
 736    }
 737
 738    normal[0] = 0.0f;
 739    normal[1] = 1.0f;
 740    normal[2] = 0.0f;
 741 }
 742
 743 struct bvh_node
 744 {
 745    boxf bbx;
 746
 747    /* if il is 0, this is a leaf */
 748    u32 il, count;
 749    union{ u32 ir, start; };
 750 };
 751
 752 static void bvh_update_bounds( scene *s, u32 inode )
 753 {
 754    bvh_node *node = &s->bvh.nodes[ inode ];
 755
 756    box_init_inf( node->bbx );
 757    for( u32 i=0; i<node->count; i++ )
 758    {
 759       u32 idx = node->start+i;
 760       model_vert *pa = &s->verts[ s->indices[idx*3+0] ],
 761                  *pb = &s->verts[ s->indices[idx*3+1] ],
 762                  *pc = &s->verts[ s->indices[idx*3+2] ];
 763
 764      box_addpt( node->bbx, pa->co );
 765      box_addpt( node->bbx, pb->co );
 766      box_addpt( node->bbx, pc->co );
 767    }
 768 }
 769
 770 static void bvh_subdiv( scene *s, u32 inode )
 771 {
 772    bvh_node *node = &s->bvh.nodes[ inode ];
 773
 774    v3f extent;
 775    v3_sub( node->bbx[1], node->bbx[0], extent );
 776
 777    int axis = 0;
 778    if( extent[1] > extent[0] ) axis = 1;
 779    if( extent[2] > extent[axis] ) axis = 2;
 780
 781    float split = node->bbx[0][axis] + extent[axis]*0.5f;
 782
 783    /* To beat: 121,687 / 136,579
 784     *          136,375
 785     */
 786
 787    float avg = 0.0;
 788    for( u32 t=0; t<node->count; t++ )
 789    {
 790       u32 *ti = &s->indices[(node->start+t)*3];
 791       float a = s->verts[ti[0]].co[axis],
 792              b = s->verts[ti[1]].co[axis],
 793              c = s->verts[ti[2]].co[axis];
 794       avg += (a+b+c)/3.0;
 795    }
 796    avg /= (float)node->count;
 797
 798    split = avg;
 799
 800    i32 i = node->start,
 801        j = i + node->count-1;
 802
 803    while( i <= j )
 804    {
 805       u32 *ti = &s->indices[i*3];
 806
 807       float a = s->verts[ti[0]].co[axis],
 808             b = s->verts[ti[1]].co[axis],
 809             c = s->verts[ti[2]].co[axis];
 810
 811       if( ((a+b+c) / 3.0f) < split )
 812          i ++;
 813       else
 814       {
 815          /* Swap triangle indices */
 816          u32 *tj = &s->indices[j*3];
 817          u32 temp[3];
 818          temp[0] = ti[0];
 819          temp[1] = ti[1];
 820          temp[2] = ti[2];
 821
 822          ti[0] = tj[0];
 823          ti[1] = tj[1];
 824          ti[2] = tj[2];
 825
 826          tj[0] = temp[0];
 827          tj[1] = temp[1];
 828          tj[2] = temp[2];
 829
 830          j --;
 831       }
 832    }
 833
 834    u32 left_count = i - node->start;
 835    if( left_count == 0 || left_count == node->count ) return;
 836
 837    u32 il = s->bvh.node_count ++,
 838        ir = s->bvh.node_count ++;
 839
 840    struct bvh_node *lnode = &s->bvh.nodes[il],
 841                    *rnode = &s->bvh.nodes[ir];
 842
 843    lnode->start = node->start;
 844    lnode->count = left_count;
 845    rnode->start = i;
 846    rnode->count = node->count - left_count;
 847
 848    node->il = il;
 849    node->ir = ir;
 850    node->count = 0;
 851
 852    bvh_update_bounds( s, il );
 853    bvh_update_bounds( s, ir );
 854    bvh_subdiv( s, il );
 855    bvh_subdiv( s, ir );
 856 }
 857
 858 static void bvh_create( scene *s )
 859 {
 860    u32 triangle_count = s->indice_count / 3;
 861    s->bvh.nodes = malloc( sizeof(struct bvh_node) * (triangle_count*2-1) );
 862
 863    bvh_node *root = &s->bvh.nodes[0];
 864    s->bvh.node_count = 1;
 865
 866    root->il = 0;
 867    root->ir = 0;
 868    root->count = triangle_count;
 869    root->start = 0;
 870
 871    bvh_update_bounds( s, 0 );
 872    bvh_subdiv( s, 0 );
 873
 874    s->bvh.nodes =
 875       realloc( s->bvh.nodes, sizeof(struct bvh_node) * s->bvh.node_count );
 876
 877    vg_success( "BVH done, size: %u/%u\n", s->bvh.node_count,
 878                                           (triangle_count*2-1) );
 879 }
 880
 881 static void bvh_debug_node( scene *s, u32 inode, v3f pos, u32 colour )
 882 {
 883    struct bvh_node *node = &s->bvh.nodes[ inode ];
 884
 885    if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) &&
 886        (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) )
 887    {
 888       if( !node->count )
 889       {
 890          vg_line_boxf( node->bbx, colour );
 891
 892          bvh_debug_node( s, node->il, pos, colour );
 893          bvh_debug_node( s, node->ir, pos, colour );
 894       }
 895       else
 896       {
 897          vg_line_boxf( node->bbx, 0xff00ff00 );
 898          for( u32 i=0; i<node->count; i++ )
 899          {
 900             u32 idx = (node->start+i)*3;
 901
 902             model_vert *pa = &s->verts[ s->indices[ idx+0 ] ],
 903                        *pb = &s->verts[ s->indices[ idx+1 ] ],
 904                        *pc = &s->verts[ s->indices[ idx+2 ] ];
 905
 906             vg_line( pa->co, pb->co, 0xff0000ff );
 907             vg_line( pb->co, pc->co, 0xff0000ff );
 908             vg_line( pc->co, pa->co, 0xff0000ff );
 909          }
 910       }
 911    }
 912 }
 913
 914 static void bvh_debug( scene *s, v3f pos )
 915 {
 916    bvh_debug_node( s, 0, pos, 0x4000ffa8 );
 917 }
 918
 919 typedef struct ray_hit ray_hit;
 920 struct ray_hit
 921 {
 922    float dist;
 923    u32 *tri;
 924    v3f pos, normal;
 925 };
 926
 927 int ray_aabb( boxf box, v3f co, v3f dir, float dist )
 928 {
 929    v3f v0, v1;
 930    float tmin, tmax;
 931
 932    v3_sub( box[0], co, v0 );
 933    v3_sub( box[1], co, v1 );
 934    v3_div( v0, dir, v0 );
 935    v3_div( v1, dir, v1 );
 936
 937    tmin = vg_minf( v0[0], v1[0] );
 938    tmax = vg_maxf( v0[0], v1[0] );
 939    tmin = vg_maxf( tmin, vg_minf( v0[1], v1[1] ));
 940    tmax = vg_minf( tmax, vg_maxf( v0[1], v1[1] ));
 941    tmin = vg_maxf( tmin, vg_minf( v0[2], v1[2] ));
 942    tmax = vg_minf( tmax, vg_maxf( v0[2], v1[2] ));
 943
 944    return tmax >= tmin && tmin < dist && tmax > 0;
 945 }
 946
 947 static int bvh_ray_tri( scene *sc, u32 *tri, v3f co, v3f dir, ray_hit *hit )
 948 {
 949    v3f positions[3];
 950    for( int i=0; i<3; i++ )
 951       v3_copy( sc->verts[tri[i]].co, positions[i] );
 952
 953    float t;
 954    if(ray_tri( positions, co, dir, &t ))
 955    {
 956       if( t < hit->dist )
 957       {
 958          hit->dist = t;
 959          hit->tri = tri;
 960          return 1;
 961       }
 962    }
 963
 964    return 0;
 965 }
 966
 967 static int bvh_ray( scene *s, u32 inode, v3f co, v3f dir, ray_hit *hit )
 968 {
 969    bvh_node *node = &s->bvh.nodes[ inode ];
 970
 971    if( !ray_aabb( node->bbx, co, dir, hit->dist ))
 972       return 0;
 973
 974    int count = 0;
 975
 976    if( node->count )
 977    {
 978       for( u32 i=0; i<node->count; i++ )
 979       {
 980          u32 *indices = &s->indices[ (node->start+i)*3 ];
 981          count += bvh_ray_tri( s, indices, co, dir, hit );
 982       }
 983    }
 984    else
 985    {
 986       count += bvh_ray( s, node->il, co, dir, hit );
 987       count += bvh_ray( s, node->ir, co, dir, hit );
 988    }
 989
 990    return count;
 991 }
 992
 993 static int bvh_raycast( scene *s, v3f co, v3f dir, ray_hit *hit )
 994 {
 995    v3f pb;
 996    v3_muladds( co, dir, hit->dist, pb );
 997
 998    int count = bvh_ray( s, 0, co, dir, hit );
 999
1000    if( count )
1001    {
1002       //vg_line( co, pb, 0xff00ffff );
1003
1004       v3f v0, v1;
1005
1006       float *pa = s->verts[hit->tri[0]].co,
1007             *pb = s->verts[hit->tri[1]].co,
1008             *pc = s->verts[hit->tri[2]].co;
1009
1010       v3_sub( pa, pb, v0 );
1011       v3_sub( pc, pb, v1 );
1012       v3_cross( v1, v0, hit->normal );
1013       v3_normalize( hit->normal );
1014       v3_muladds( co, dir, hit->dist, hit->pos );
1015    }
1016    else
1017    {
1018       //vg_line( co, pb, 0xff0000ff );
1019    }
1020
1021    return count;
1022 }
1023
1024 static int bvh_select_triangles( scene *s, boxf box, u32 *triangles, int len )
1025 {
1026    /* TODO: use this stack system on the raycast function */
1027    int count = 0;
1028    u32 stack[100];
1029    u32 depth = 2;
1030
1031    stack[0] = 0;
1032    stack[1] = s->bvh.nodes[0].il;
1033    stack[2] = s->bvh.nodes[0].ir;
1034
1035    while(depth)
1036    {
1037       bvh_node *inode = &s->bvh.nodes[ stack[depth] ];
1038       if( box_overlap( inode->bbx, box ) )
1039       {
1040          if( inode->count )
1041          {
1042             if( count + inode->count >= len )
1043             {
1044                vg_error( "Maximum buffer reached!\n" );
1045                return count;
1046             }
1047
1048             for( u32 i=0; i<inode->count; i++ )
1049                triangles[ count ++ ] = (inode->start+i)*3;
1050
1051             depth --;
1052          }
1053          else
1054          {
1055             if( depth+1 >= vg_list_size(stack) )
1056             {
1057                vg_error( "Maximum stack reached!\n" );
1058                return count;
1059             }
1060
1061             stack[depth] = inode->il;
1062             stack[depth+1] = inode->ir;
1063             depth ++;
1064          }
1065       }
1066       else
1067       {
1068          depth --;
1069       }
1070    }
1071
1072    return count;
1073 }
1074
1075 static int bvh_scene_sample_node_h( scene *s, u32 inode, v3f pos, v3f norm )
1076 {
1077    bvh_node *node = &s->bvh.nodes[ inode ];
1078
1079    if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) &&
1080        (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) )
1081    {
1082       if( !node->count )
1083       {
1084          if( bvh_scene_sample_node_h( s, node->il, pos, norm )) return 1;
1085          if( bvh_scene_sample_node_h( s, node->ir, pos, norm )) return 1;
1086       }
1087       else
1088       {
1089          for( u32 i=0; i<node->count; i++ )
1090          {
1091             u32 idx = (node->start+i)*3;
1092             model_vert *pa = &s->verts[ s->indices[ idx+0 ] ],
1093                        *pb = &s->verts[ s->indices[ idx+1 ] ],
1094                        *pc = &s->verts[ s->indices[ idx+2 ] ];
1095
1096             float height;
1097             if( triangle_raycast2d( pa->co, pb->co, pc->co, pos, &height ))
1098             {
1099                pos[1] = height;
1100
1101                if( norm )
1102                {
1103                   v3f v0, v1;
1104                   v3_sub( pa->co, pb->co, v0 );
1105                   v3_sub( pc->co, pb->co, v1 );
1106                   v3_cross( v1, v0, norm );
1107                   v3_normalize( norm );
1108                }
1109
1110                return 1;
1111             }
1112          }
1113       }
1114    }
1115
1116    return 0;
1117 }
1118
1119 static int bvh_scene_sample_h( scene *s, v3f pos, v3f norm)
1120 {
1121    return bvh_scene_sample_node_h( s, 0, pos, norm );
1122 }
1123
1124 static int bvh_scene_sample( scene *s, v3f pos, ray_hit *hit )
1125 {
1126    hit->dist = INFINITY;
1127
1128    v3f ray_pos;
1129    v3_add( pos, (v3f){0.0f,4.0f,0.0f}, ray_pos );
1130
1131    if( bvh_raycast( s, ray_pos, (v3f){0.0f,-1.0f,0.0f}, hit ))
1132    {
1133       pos[1] = hit->pos[1];
1134       return 1;
1135    }
1136
1137    return 0;
1138 }
1139
1140 #endif