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_copy_slice( scene *pscene, submodel *sm )
 185 {
 186    sm->indice_start = pscene->submesh.indice_start;
 187    sm->indice_count = pscene->indice_count - sm->indice_start;
 188
 189    sm->vertex_start = pscene->submesh.vertex_start;
 190    sm->vertex_count = pscene->vertex_count - sm->vertex_start;
 191
 192    pscene->submesh.indice_start = pscene->indice_count;
 193    pscene->submesh.vertex_start = pscene->vertex_count;
 194 }
 195
 196 static void scene_shadow_sphere( scene *pscene, v3f sphere,
 197       v4f params, v3f lightdir )
 198 {
 199    for( int i=0; i<pscene->vertex_count; i++ )
 200    {
 201       model_vert *vert = &pscene->verts[i];
 202
 203       v3f delta;
 204       v3_sub( sphere, vert->co, delta );
 205
 206       float d = v3_dot( lightdir, delta );
 207       v3f closest;
 208
 209       v3_muls( lightdir, d, closest );
 210       float dist = v3_dist( closest, delta ),
 211             shading = vg_maxf( dist - params[0], 0.0f );
 212
 213       shading = vg_minf( shading * params[1], 1.0f );
 214       vert->colour[1] *= shading;
 215    }
 216 }
 217
 218 static void scene_shadow_gradient( scene *pscene, int comp,
 219       float start, float length )
 220 {
 221    float scale = 1.0f / length;
 222
 223    for( int i=0; i<pscene->vertex_count; i++ )
 224    {
 225       model_vert *vert = &pscene->verts[i];
 226       float shading = start + vert->co[comp] * scale;
 227
 228       vert->colour[1] = shading;
 229    }
 230 }
 231
 232
 233 /*
 234  * Experimental SDF based shadows
 235  *
 236  * https://iquilezles.org/articles/distfunctions/
 237  */
 238 static float sd_cone( v3f co, sdf_primative *prim )
 239 {
 240    float bound = prim->info[1]*1.75f;
 241    if( v3_dist2( prim->origin, co ) > bound*bound )
 242       return 999999.9f;
 243
 244    v3f p;
 245    v3_sub( co, prim->origin, p );
 246
 247    float h = prim->info[1];
 248    v2f c = { prim->info[2], prim->info[3] };
 249
 250    v2f q, w, a, b;
 251    v2_muls( (v2f){ c[0]/c[1], -1.0f }, h, q );
 252
 253    w[0] = v2_length( (v2f){ p[0], p[2] } );
 254    w[1] = p[1];
 255
 256    v2_muladds( w, q, -vg_clampf( v2_dot(w,q)/v2_dot(q,q), 0.0f, 1.0f ), a );
 257    v2_muladd( w, q, (v2f){ vg_clampf( w[0]/q[0], 0.0f, 1.0f ), 1.0f }, b );
 258
 259    float k = vg_signf( q[1] ),
 260          d = vg_minf( v2_dot( a,a ), v2_dot( b,b ) ),
 261          s = vg_maxf( k*(w[0]*q[1]-w[1]*q[0]), k*(w[1]-q[1]) );
 262
 263    return sqrtf(d)*vg_signf(s);
 264 }
 265
 266 #define CACHE_AMBIENT_SHAPES
 267
 268 static float scene_ambient_sample( scene *pscene, v3f pos, v3f dir )
 269 {
 270    float accum = 0.0f;
 271
 272 #ifdef CACHE_AMBIENT_SHAPES
 273    static struct shadower *local_shadowers[32];
 274    static int local_shadower_count = 0;
 275    static v3f local_shadower_last = { -99999.9f, -999999.9f, -9999999.9f };
 276
 277    if( v3_dist2( pos, local_shadower_last ) > 10.0f*10.0f )
 278    {
 279       local_shadower_count = 0;
 280       v3_copy( pos, local_shadower_last );
 281
 282       for( int k=0; k<pscene->shadower_count; k++ )
 283       {
 284          struct shadower *shadower = &pscene->shadowers[k];
 285
 286          if( sd_cone( pos, &shadower->sdf ) <= 20.0f )
 287          {
 288             local_shadowers[ local_shadower_count ++ ] = shadower;
 289             if( local_shadower_count == vg_list_size( local_shadowers ) )
 290                break;
 291          }
 292       }
 293    }
 294 #endif
 295
 296    for( int j=0; j<5; j++ )
 297    {
 298       v3f tracepos;
 299       v3_muladds( pos, dir, 1.5f*(float)j, tracepos );
 300
 301       float mindist = 99999.9f;
 302
 303 #ifndef CACHE_AMBIENT_SHAPES
 304
 305       for( int k=0; k<pscene->shadower_count; k++ ){
 306          struct shadower *shadower = &pscene->shadowers[k];
 307 #else
 308
 309       for( int k=0; k<local_shadower_count; k++ ){
 310          struct shadower *shadower = local_shadowers[k];
 311 #endif
 312
 313          float dist = vg_maxf( 0.0f, sd_cone( tracepos, &shadower->sdf ));
 314          mindist = vg_minf( mindist, dist );
 315       }
 316
 317
 318       accum += vg_clampf( 1.0f - mindist, 0.0f, 1.0f )*0.2f;
 319    }
 320
 321    return accum;
 322 }
 323
 324 #define DYNAMIC_GRID
 325 #define JUST_DO_EVERY_VERT
 326
 327 static void scene_compute_occlusion( scene *pscene )
 328 {
 329    v3f sundir = { 0.2f, 0.9f, 0.2f };
 330    v3_normalize( sundir );
 331
 332    /* TODO: Make this sample grid be dynamically required.
 333     *
 334     *   1. Only resample the light grid (1x1x1), when a vertex is outside the
 335     *      current cube
 336     *
 337     *   2. Reorder all vertices so that each group of vertices that fit in a
 338     *      cube are next to eachother in the buffer. This will save cache
 339     *      misses.
 340     *
 341     *      for the sorting algorithm, i think we can already assume that *most
 342     *      vertices will be quite close to eachother. so instead of doing an
 343     *      exhaustive search we can reorder 1k chunks at a time.
 344     */
 345
 346    v3f sample_area;
 347    v3_sub( pscene->bbx[1], pscene->bbx[0], sample_area );
 348    v3_ceil( sample_area, sample_area );
 349    int ax = sample_area[0],
 350        ay = sample_area[1],
 351        az = sample_area[2];
 352
 353 #ifndef DYNAMIC_GRID
 354    float *samplegrid = malloc( ax*ay*az* sizeof(float) );
 355
 356    for( int x=0; x<ax; x++ ){
 357    for( int y=0; y<ay; y++ ){
 358    for( int z=0; z<az; z++ )
 359    {
 360       v3f sample_pos = { x,y,z };
 361       v3_add( pscene->bbx[0], sample_pos, sample_pos );
 362       float accum = scene_ambient_sample( pscene, sample_pos, sundir );
 363
 364       samplegrid[x + y*ax + z*ax*ay] = accum;
 365    }}}
 366 #else
 367    v3i cube_pos = { -999999, -999999, -999999 };
 368    int cube_resamples = 0, hits = 0, misses = 0;
 369
 370    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;
 371 #endif
 372
 373    for( int i=0; i<pscene->vertex_count; i++ )
 374    {
 375       model_vert *vert = &pscene->verts[i];
 376       v3f rel, q;
 377
 378 #ifndef DYNAMIC_GRID
 379       v3_sub( vert->co, pscene->bbx[0], q );
 380 #else
 381       v3_copy( vert->co, q );
 382 #endif
 383
 384       v3_floor( q, rel );
 385       v3_sub( q, rel, q );
 386
 387       int x=rel[0],
 388           y=rel[1],
 389           z=rel[2];
 390
 391 #ifndef JUST_DO_EVERY_VERT
 392 #ifndef DYNAMIC_GRID
 393       x = VG_MIN(x,ax-2);
 394       y = VG_MIN(y,ay-2);
 395       z = VG_MIN(z,az-2);
 396       x = VG_MAX(x,0);
 397       y = VG_MAX(y,0);
 398       z = VG_MAX(z,0);
 399
 400       float
 401          s0 = samplegrid[ x    +  y*ax    + z*ax*ay],
 402          s1 = samplegrid[(x+1) +  y*ax    + z*ax*ay],
 403          s2 = samplegrid[ x    + (y+1)*ax + z*ax*ay],
 404          s3 = samplegrid[(x+1) + (y+1)*ax + z*ax*ay],
 405          s4 = samplegrid[ x    +  y*ax    + (z+1)*ax*ay],
 406          s5 = samplegrid[(x+1) +  y*ax    + (z+1)*ax*ay],
 407          s6 = samplegrid[ x    + (y+1)*ax + (z+1)*ax*ay],
 408          s7 = samplegrid[(x+1) + (y+1)*ax + (z+1)*ax*ay],
 409 #else
 410       if( x!=cube_pos[0] || y!=cube_pos[1] || z!=cube_pos[2] )
 411       {
 412          cube_pos[0] = x;
 413          cube_pos[1] = y;
 414          cube_pos[2] = z;
 415
 416          s0 = scene_ambient_sample( pscene, (v3f){ x,y,z }, sundir );
 417          s1 = scene_ambient_sample( pscene, (v3f){ x+1,y,z }, sundir );
 418          s2 = scene_ambient_sample( pscene, (v3f){ x,y+1,z }, sundir );
 419          s3 = scene_ambient_sample( pscene, (v3f){ x+1,y+1,z }, sundir );
 420          s4 = scene_ambient_sample( pscene, (v3f){ x,y,z+1 }, sundir );
 421          s5 = scene_ambient_sample( pscene, (v3f){ x+1,y,z+1 }, sundir );
 422          s6 = scene_ambient_sample( pscene, (v3f){ x,y+1,z+1 }, sundir );
 423          s7 = scene_ambient_sample( pscene, (v3f){ x+1,y+1,z+1 }, sundir );
 424
 425          cube_resamples += 8;
 426          misses ++;
 427       }
 428       else
 429          hits ++;
 430
 431       float
 432 #endif
 433
 434          s0_s1 = vg_lerpf( s0, s1, q[0] ),
 435          s2_s3 = vg_lerpf( s2, s3, q[0] ),
 436          s4_s5 = vg_lerpf( s4, s5, q[0] ),
 437          s6_s7 = vg_lerpf( s6, s7, q[0] ),
 438
 439          s0s1_s2s3 = vg_lerpf( s0_s1, s2_s3, q[1] ),
 440          s4s5_s6s7 = vg_lerpf( s4_s5, s6_s7, q[1] ),
 441          s0s1s2s3_s4s5s6s7 = vg_lerpf( s0s1_s2s3, s4s5_s6s7, q[2] );
 442
 443       vert->colour[1] = s0s1s2s3_s4s5s6s7;
 444 #else
 445       vert->colour[1] = scene_ambient_sample( pscene, vert->co, sundir );
 446 #endif
 447    }
 448
 449 #ifndef DYNAMIC_GRID
 450    int cube_resamples = -1, misses = 0, hits = 0;
 451 #endif
 452
 453    int static_samples = ax*ay*az,
 454        vertex_samples = pscene->vertex_count;
 455
 456    if( cube_resamples < static_samples )
 457       vg_success( "Walking cube beat static grid (%d<%d. %d)!\n",
 458          cube_resamples, static_samples, vertex_samples );
 459    else
 460       vg_warn( "Walking cube was worse than static grid (%d<%d. %d).\n",
 461          cube_resamples, static_samples, vertex_samples );
 462
 463    vg_info( "Hits; %d, misses: %d\n", hits, misses );
 464
 465 #ifndef DYNAMIC_GRID
 466    free( samplegrid );
 467 #endif
 468
 469    return;
 470
 471    for( int i=0; i<pscene->vertex_count; i++ )
 472    {
 473       model_vert *vert = &pscene->verts[i];
 474       float accum = 0.0f;
 475
 476       for( int j=0; j<5; j++ )
 477       {
 478          v3f tracepos;
 479          v3_copy( vert->co, tracepos );
 480          v3_muladds( tracepos, sundir, 1.5f*(float)j, tracepos );
 481
 482          float mindist = 99999.9f;
 483
 484          for( int k=0; k<pscene->shadower_count; k++ )
 485          {
 486             struct shadower *shadower = &pscene->shadowers[k];
 487             float dist = vg_maxf( 0.0f, sd_cone( tracepos, &shadower->sdf ));
 488             mindist = vg_minf( mindist, dist );
 489          }
 490
 491          accum += vg_clampf( 1.0f - mindist, 0.0f, 1.0f )*0.2f;
 492       }
 493
 494       vert->colour[1] = vg_minf( accum, 1.0f );
 495    }
 496 }
 497
 498 static void scene_upload( scene *pscene )
 499 {
 500    mesh_upload( &pscene->mesh,
 501          pscene->verts, pscene->vertex_count,
 502          pscene->indices, pscene->indice_count );
 503
 504    vg_info( "Scene upload\n" );
 505    vg_info( "   indices:%u\n", pscene->indice_count );
 506    vg_info( "   verts:%u\n", pscene->vertex_count );
 507 }
 508
 509 float scene_tree_sway = 0.1f;
 510
 511 #if 0
 512 static void scene_foliage_shader_use(void)
 513 {
 514    SHADER_USE( shader_debug_vcol );
 515
 516         glUniformMatrix4fv( SHADER_UNIFORM( shader_debug_vcol, "uPv" ),
 517          1, GL_FALSE, (float *)vg_pv );
 518
 519    glUniform1i( SHADER_UNIFORM( shader_debug_vcol, "uMode" ), debugview );
 520    glUniform1i( SHADER_UNIFORM( shader_debug_vcol, "uTexMain" ), 0 );
 521
 522    glUniform1i( SHADER_UNIFORM( shader_debug_vcol, "uTexGradients" ), 1 );
 523    vg_tex2d_bind( &tex_gradients, 1 );
 524
 525    glUniform1i( SHADER_UNIFORM( shader_debug_vcol, "uTexNoise" ), 2 );
 526    glActiveTexture( GL_TEXTURE2 );
 527    glBindTexture( GL_TEXTURE_2D, tex_dual_noise );
 528
 529    glUniform1f( SHADER_UNIFORM( shader_debug_vcol, "uTime" ), vg_time );
 530    glUniform1f( SHADER_UNIFORM( shader_debug_vcol, "uSwayAmt" ),
 531          scene_tree_sway );
 532 }
 533 #endif
 534
 535 static void scene_bind( scene *pscene )
 536 {
 537    mesh_bind( &pscene->mesh );
 538 }
 539
 540 static void scene_draw( scene *pscene )
 541 {
 542    mesh_drawn( 0, pscene->indice_count );
 543 }
 544
 545 static void scene_debugsdf( scene *pscene )
 546 {
 547    for( int i=0; i<pscene->shadower_count; i++ )
 548    {
 549       struct shadower *shadower = &pscene->shadowers[i];
 550
 551       v3f base, side;
 552       v3_copy( shadower->sdf.origin, base );
 553       base[1] -= shadower->sdf.info[1];
 554       v3_copy( base, side );
 555       side[0] += shadower->sdf.info[0];
 556
 557       vg_line2( shadower->sdf.origin, base, 0xff00ff00, 0xff0000ff );
 558       vg_line2( side, base, 0xff00ff00, 0xff0000ff );
 559       vg_line( side, shadower->sdf.origin, 0xff00ff00 );
 560    }
 561
 562    v3f p0 = { pscene->bbx[0][0], pscene->bbx[0][1], pscene->bbx[0][2] },
 563        p1 = { pscene->bbx[0][0], pscene->bbx[1][1], pscene->bbx[0][2] },
 564        p2 = { pscene->bbx[1][0], pscene->bbx[1][1], pscene->bbx[0][2] },
 565        p3 = { pscene->bbx[1][0], pscene->bbx[0][1], pscene->bbx[0][2] },
 566
 567        p4 = { pscene->bbx[0][0], pscene->bbx[0][1], pscene->bbx[1][2] },
 568        p5 = { pscene->bbx[0][0], pscene->bbx[1][1], pscene->bbx[1][2] },
 569        p6 = { pscene->bbx[1][0], pscene->bbx[1][1], pscene->bbx[1][2] },
 570        p7 = { pscene->bbx[1][0], pscene->bbx[0][1], pscene->bbx[1][2] };
 571
 572    u32 col = 0xffff00c8;
 573    vg_line( p0, p1, col );
 574    vg_line( p1, p2, col );
 575    vg_line( p2, p3, col );
 576    vg_line( p3, p0, col );
 577
 578    vg_line( p4, p5, col );
 579    vg_line( p5, p6, col );
 580    vg_line( p6, p7, col );
 581    vg_line( p7, p4, col );
 582
 583    vg_line( p0, p4, col );
 584    vg_line( p1, p5, col );
 585    vg_line( p2, p6, col );
 586    vg_line( p3, p7, col );
 587 }
 588
 589 static void scene_register(void)
 590 {
 591 }
 592
 593
 594 /* Physics segment */
 595
 596 static int triangle_raycast2d( v3f pA, v3f pB, v3f pC, v3f ray, float *height )
 597 {
 598         v2f v0, v1, v2, vp, vp2;
 599         float d, bca = 0.f, bcb = 0.f, bcc = 0.f;
 600
 601    v0[0] = pB[0] - pA[0];
 602    v0[1] = pB[2] - pA[2];
 603    v1[0] = pC[0] - pA[0];
 604    v1[1] = pC[2] - pA[2];
 605    v2[0] = pB[0] - pC[0];
 606    v2[1] = pB[2] - pC[2];
 607
 608         d = 1.f / (v0[0]*v1[1] - v1[0]*v0[1]);
 609
 610 #if 0
 611         /* Backface culling */
 612         if( v2_cross( v0, v1 ) > 0.f )
 613                 return;
 614 #endif
 615
 616    vp[0] = ray[0] - pA[0];
 617    vp[1] = ray[2] - pA[2];
 618
 619    if( v2_cross( v0, vp ) > 0.f ) return 0;
 620    if( v2_cross( vp, v1 ) > 0.f ) return 0;
 621
 622    vp2[0] = ray[0] - pB[0];
 623    vp2[1] = ray[2] - pB[2];
 624
 625    if( v2_cross( vp2, v2 ) > 0.f ) return 0;
 626
 627    bcb = (vp[0]*v1[1] - v1[0]*vp[1]) * d;
 628    bcc = (v0[0]*vp[1] - vp[0]*v0[1]) * d;
 629    bca = 1.f - bcb - bcc;
 630
 631    *height = pA[1]*bca + pB[1]*bcb + pC[1]*bcc;
 632    return 1;
 633 }
 634
 635 /* Temporary */
 636 static int sample_scene_height( scene *pscene, v3f pos, v3f norm )
 637 {
 638    for( int i=0; i<pscene->indice_count/3; i++ )
 639    {
 640       u32 *tri = &pscene->indices[i*3];
 641
 642       float *pA = pscene->verts[tri[0]].co,
 643             *pB = pscene->verts[tri[1]].co,
 644             *pC = pscene->verts[tri[2]].co;
 645
 646       float height;
 647       if( triangle_raycast2d( pA, pB, pC, pos, &height ))
 648       {
 649          pos[1] = height;
 650
 651          if( norm )
 652          {
 653             v3f v0, v1;
 654             v3_sub( pA, pB, v0 );
 655             v3_sub( pC, pB, v1 );
 656             v3_cross( v1, v0, norm );
 657             v3_normalize( norm );
 658          }
 659
 660          return 1;
 661       }
 662    }
 663    return 0;
 664 }
 665
 666 static void sample_scene_normal( scene *pscene, v3f pos, v3f normal )
 667 {
 668    for( int i=0; i<pscene->indice_count/3; i++ )
 669    {
 670       u32 *tri = &pscene->indices[i*3];
 671
 672       float height;
 673       if( triangle_raycast2d(
 674             pscene->verts[ tri[0] ].co,
 675             pscene->verts[ tri[1] ].co,
 676             pscene->verts[ tri[2] ].co, pos, &height ))
 677       {
 678          v3f v0, v1;
 679
 680          v3_sub( pscene->verts[ tri[1] ].co,
 681                  pscene->verts[ tri[0] ].co,
 682                  v0 );
 683
 684          v3_sub( pscene->verts[ tri[2] ].co,
 685                  pscene->verts[ tri[0] ].co,
 686                  v1 );
 687
 688          v3_cross( v0, v1, normal );
 689          v3_normalize( normal );
 690          return;
 691       }
 692    }
 693
 694    normal[0] = 0.0f;
 695    normal[1] = 1.0f;
 696    normal[2] = 0.0f;
 697 }
 698
 699 struct bvh_node
 700 {
 701    boxf bbx;
 702
 703    /* if il is 0, this is a leaf */
 704    u32 il, count;
 705    union{ u32 ir, start; };
 706 };
 707
 708 static void bvh_update_bounds( scene *s, u32 inode )
 709 {
 710    bvh_node *node = &s->bvh.nodes[ inode ];
 711
 712    box_init_inf( node->bbx );
 713    for( u32 i=0; i<node->count; i++ )
 714    {
 715       u32 idx = node->start+i;
 716       model_vert *pa = &s->verts[ s->indices[idx*3+0] ],
 717                  *pb = &s->verts[ s->indices[idx*3+1] ],
 718                  *pc = &s->verts[ s->indices[idx*3+2] ];
 719
 720      box_addpt( node->bbx, pa->co );
 721      box_addpt( node->bbx, pb->co );
 722      box_addpt( node->bbx, pc->co );
 723    }
 724 }
 725
 726 static void bvh_subdiv( scene *s, u32 inode )
 727 {
 728    bvh_node *node = &s->bvh.nodes[ inode ];
 729
 730    v3f extent;
 731    v3_sub( node->bbx[1], node->bbx[0], extent );
 732
 733    int axis = 0;
 734    if( extent[1] > extent[0] ) axis = 1;
 735    if( extent[2] > extent[axis] ) axis = 2;
 736
 737    float split = node->bbx[0][axis] + extent[axis]*0.5f;
 738
 739    /* To beat: 121,687 / 136,579
 740     *          136,375
 741     */
 742
 743    float avg = 0.0;
 744    for( u32 t=0; t<node->count; t++ )
 745    {
 746       u32 *ti = &s->indices[(node->start+t)*3];
 747       float a = s->verts[ti[0]].co[axis],
 748              b = s->verts[ti[1]].co[axis],
 749              c = s->verts[ti[2]].co[axis];
 750       avg += (a+b+c)/3.0;
 751    }
 752    avg /= (float)node->count;
 753
 754    split = avg;
 755
 756    i32 i = node->start,
 757        j = i + node->count-1;
 758
 759    while( i <= j )
 760    {
 761       u32 *ti = &s->indices[i*3];
 762
 763       float a = s->verts[ti[0]].co[axis],
 764             b = s->verts[ti[1]].co[axis],
 765             c = s->verts[ti[2]].co[axis];
 766
 767       if( ((a+b+c) / 3.0f) < split )
 768          i ++;
 769       else
 770       {
 771          /* Swap triangle indices */
 772          u32 *tj = &s->indices[j*3];
 773          u32 temp[3];
 774          temp[0] = ti[0];
 775          temp[1] = ti[1];
 776          temp[2] = ti[2];
 777
 778          ti[0] = tj[0];
 779          ti[1] = tj[1];
 780          ti[2] = tj[2];
 781
 782          tj[0] = temp[0];
 783          tj[1] = temp[1];
 784          tj[2] = temp[2];
 785
 786          j --;
 787       }
 788    }
 789
 790    u32 left_count = i - node->start;
 791    if( left_count == 0 || left_count == node->count ) return;
 792
 793    u32 il = s->bvh.node_count ++,
 794        ir = s->bvh.node_count ++;
 795
 796    struct bvh_node *lnode = &s->bvh.nodes[il],
 797                    *rnode = &s->bvh.nodes[ir];
 798
 799    lnode->start = node->start;
 800    lnode->count = left_count;
 801    rnode->start = i;
 802    rnode->count = node->count - left_count;
 803
 804    node->il = il;
 805    node->ir = ir;
 806    node->count = 0;
 807
 808    bvh_update_bounds( s, il );
 809    bvh_update_bounds( s, ir );
 810    bvh_subdiv( s, il );
 811    bvh_subdiv( s, ir );
 812 }
 813
 814 static void bvh_create( scene *s )
 815 {
 816    u32 triangle_count = s->indice_count / 3;
 817    s->bvh.nodes = malloc( sizeof(struct bvh_node) * (triangle_count*2-1) );
 818
 819    bvh_node *root = &s->bvh.nodes[0];
 820    s->bvh.node_count = 1;
 821
 822    root->il = 0;
 823    root->ir = 0;
 824    root->count = triangle_count;
 825    root->start = 0;
 826
 827    bvh_update_bounds( s, 0 );
 828    bvh_subdiv( s, 0 );
 829
 830    s->bvh.nodes =
 831       realloc( s->bvh.nodes, sizeof(struct bvh_node) * s->bvh.node_count );
 832
 833    vg_success( "BVH done, size: %u/%u\n", s->bvh.node_count,
 834                                           (triangle_count*2-1) );
 835 }
 836
 837 static void bvh_debug_node( scene *s, u32 inode, v3f pos, u32 colour )
 838 {
 839    struct bvh_node *node = &s->bvh.nodes[ inode ];
 840
 841    if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) &&
 842        (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) )
 843    {
 844       if( !node->count )
 845       {
 846          vg_line_boxf( node->bbx, colour );
 847
 848          bvh_debug_node( s, node->il, pos, colour );
 849          bvh_debug_node( s, node->ir, pos, colour );
 850       }
 851       else
 852       {
 853          vg_line_boxf( node->bbx, 0xff00ff00 );
 854          for( u32 i=0; i<node->count; i++ )
 855          {
 856             u32 idx = (node->start+i)*3;
 857
 858             model_vert *pa = &s->verts[ s->indices[ idx+0 ] ],
 859                        *pb = &s->verts[ s->indices[ idx+1 ] ],
 860                        *pc = &s->verts[ s->indices[ idx+2 ] ];
 861
 862             vg_line( pa->co, pb->co, 0xff0000ff );
 863             vg_line( pb->co, pc->co, 0xff0000ff );
 864             vg_line( pc->co, pa->co, 0xff0000ff );
 865          }
 866       }
 867    }
 868 }
 869
 870 static void bvh_debug( scene *s, v3f pos )
 871 {
 872    bvh_debug_node( s, 0, pos, 0x4000ffa8 );
 873 }
 874
 875 typedef struct ray_hit ray_hit;
 876 struct ray_hit
 877 {
 878    float dist;
 879    u32 *tri;
 880    v3f pos, normal;
 881 };
 882
 883 int ray_aabb( boxf box, v3f co, v3f dir, float dist )
 884 {
 885    v3f v0, v1;
 886    float tmin, tmax;
 887
 888    v3_sub( box[0], co, v0 );
 889    v3_sub( box[1], co, v1 );
 890    v3_div( v0, dir, v0 );
 891    v3_div( v1, dir, v1 );
 892
 893    tmin = vg_minf( v0[0], v1[0] );
 894    tmax = vg_maxf( v0[0], v1[0] );
 895    tmin = vg_maxf( tmin, vg_minf( v0[1], v1[1] ));
 896    tmax = vg_minf( tmax, vg_maxf( v0[1], v1[1] ));
 897    tmin = vg_maxf( tmin, vg_minf( v0[2], v1[2] ));
 898    tmax = vg_minf( tmax, vg_maxf( v0[2], v1[2] ));
 899
 900    return tmax >= tmin && tmin < dist && tmax > 0;
 901 }
 902
 903 static int bvh_ray_tri( scene *sc, u32 *tri, v3f co, v3f dir, ray_hit *hit )
 904 {
 905    float const kEpsilon = 0.00001f;
 906
 907    v3f v0, v1, h, s, q, n;
 908    float a,f,u,v,t;
 909
 910    float *pa = sc->verts[tri[0]].co,
 911          *pb = sc->verts[tri[1]].co,
 912          *pc = sc->verts[tri[2]].co;
 913
 914    v3_sub( pb, pa, v0 );
 915    v3_sub( pc, pa, v1 );
 916    v3_cross( dir, v1, h );
 917    v3_cross( v0, v1, n );
 918
 919    if( v3_dot( n, dir ) > 0.0f ) /* Backface culling */
 920       return 0;
 921
 922    /* Parralel */
 923    a = v3_dot( v0, h );
 924    if( a > -kEpsilon && a < kEpsilon )
 925       return 0;
 926
 927    f = 1.0f/a;
 928    v3_sub( co, pa, s );
 929
 930    u = f * v3_dot(s, h);
 931    if( u < 0.0f || u > 1.0f )
 932       return 0;
 933
 934    v3_cross( s, v0, q );
 935    v = f * v3_dot( dir, q );
 936    if( v < 0.0f || u+v > 1.0f )
 937       return 0;
 938
 939    t = f * v3_dot(v1, q);
 940    if( t > kEpsilon && t < hit->dist )
 941    {
 942       hit->dist = t;
 943       hit->tri = tri;
 944       return 1;
 945    }
 946    else return 0;
 947 }
 948
 949 static int bvh_ray( scene *s, u32 inode, v3f co, v3f dir, ray_hit *hit )
 950 {
 951    bvh_node *node = &s->bvh.nodes[ inode ];
 952
 953    if( !ray_aabb( node->bbx, co, dir, hit->dist ))
 954       return 0;
 955
 956    int count = 0;
 957
 958    if( node->count )
 959    {
 960       for( u32 i=0; i<node->count; i++ )
 961       {
 962          u32 *indices = &s->indices[ (node->start+i)*3 ];
 963          count += bvh_ray_tri( s, indices, co, dir, hit );
 964       }
 965    }
 966    else
 967    {
 968       count += bvh_ray( s, node->il, co, dir, hit );
 969       count += bvh_ray( s, node->ir, co, dir, hit );
 970    }
 971
 972    return count;
 973 }
 974
 975 static int bvh_raycast( scene *s, v3f co, v3f dir, ray_hit *hit )
 976 {
 977    v3f pb;
 978    v3_muladds( co, dir, hit->dist, pb );
 979
 980    int count = bvh_ray( s, 0, co, dir, hit );
 981
 982    if( count )
 983    {
 984       //vg_line( co, pb, 0xff00ffff );
 985
 986       v3f v0, v1;
 987
 988       float *pa = s->verts[hit->tri[0]].co,
 989             *pb = s->verts[hit->tri[1]].co,
 990             *pc = s->verts[hit->tri[2]].co;
 991
 992       v3_sub( pa, pb, v0 );
 993       v3_sub( pc, pb, v1 );
 994       v3_cross( v1, v0, hit->normal );
 995       v3_normalize( hit->normal );
 996       v3_muladds( co, dir, hit->dist, hit->pos );
 997    }
 998    else
 999    {
1000       //vg_line( co, pb, 0xff0000ff );
1001    }
1002
1003    return count;
1004 }
1005
1006 static int bvh_scene_sample_node_h( scene *s, u32 inode, v3f pos, v3f norm )
1007 {
1008    bvh_node *node = &s->bvh.nodes[ inode ];
1009
1010    if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) &&
1011        (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) )
1012    {
1013       if( !node->count )
1014       {
1015          if( bvh_scene_sample_node_h( s, node->il, pos, norm )) return 1;
1016          if( bvh_scene_sample_node_h( s, node->ir, pos, norm )) return 1;
1017       }
1018       else
1019       {
1020          for( u32 i=0; i<node->count; i++ )
1021          {
1022             u32 idx = (node->start+i)*3;
1023             model_vert *pa = &s->verts[ s->indices[ idx+0 ] ],
1024                        *pb = &s->verts[ s->indices[ idx+1 ] ],
1025                        *pc = &s->verts[ s->indices[ idx+2 ] ];
1026
1027             float height;
1028             if( triangle_raycast2d( pa->co, pb->co, pc->co, pos, &height ))
1029             {
1030                pos[1] = height;
1031
1032                if( norm )
1033                {
1034                   v3f v0, v1;
1035                   v3_sub( pa->co, pb->co, v0 );
1036                   v3_sub( pc->co, pb->co, v1 );
1037                   v3_cross( v1, v0, norm );
1038                   v3_normalize( norm );
1039                }
1040
1041                return 1;
1042             }
1043          }
1044       }
1045    }
1046
1047    return 0;
1048 }
1049
1050 static int bvh_scene_sample_h( scene *s, v3f pos, v3f norm)
1051 {
1052    return bvh_scene_sample_node_h( s, 0, pos, norm );
1053 }
1054
1055 static int bvh_scene_sample( scene *s, v3f pos, ray_hit *hit )
1056 {
1057    hit->dist = INFINITY;
1058
1059    v3f ray_pos;
1060    v3_add( pos, (v3f){0.0f,4.0f,0.0f}, ray_pos );
1061
1062    if( bvh_raycast( s, ray_pos, (v3f){0.0f,-1.0f,0.0f}, hit ))
1063    {
1064       pos[1] = hit->pos[1];
1065       return 1;
1066    }
1067
1068    return 0;
1069 }
1070
1071 #endif