CHGICKEN
[carveJwlIkooP6JGAAIwe30JlM.git] / 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 float const kEpsilon = 0.00001f;
950
951 v3f v0, v1, h, s, q, n;
952 float a,f,u,v,t;
953
954 float *pa = sc->verts[tri[0]].co,
955 *pb = sc->verts[tri[1]].co,
956 *pc = sc->verts[tri[2]].co;
957
958 v3_sub( pb, pa, v0 );
959 v3_sub( pc, pa, v1 );
960 v3_cross( dir, v1, h );
961 v3_cross( v0, v1, n );
962
963 if( v3_dot( n, dir ) > 0.0f ) /* Backface culling */
964 return 0;
965
966 /* Parralel */
967 a = v3_dot( v0, h );
968 if( a > -kEpsilon && a < kEpsilon )
969 return 0;
970
971 f = 1.0f/a;
972 v3_sub( co, pa, s );
973
974 u = f * v3_dot(s, h);
975 if( u < 0.0f || u > 1.0f )
976 return 0;
977
978 v3_cross( s, v0, q );
979 v = f * v3_dot( dir, q );
980 if( v < 0.0f || u+v > 1.0f )
981 return 0;
982
983 t = f * v3_dot(v1, q);
984 if( t > kEpsilon && t < hit->dist )
985 {
986 hit->dist = t;
987 hit->tri = tri;
988 return 1;
989 }
990 else return 0;
991 }
992
993 static int bvh_ray( scene *s, u32 inode, v3f co, v3f dir, ray_hit *hit )
994 {
995 bvh_node *node = &s->bvh.nodes[ inode ];
996
997 if( !ray_aabb( node->bbx, co, dir, hit->dist ))
998 return 0;
999
1000 int count = 0;
1001
1002 if( node->count )
1003 {
1004 for( u32 i=0; i<node->count; i++ )
1005 {
1006 u32 *indices = &s->indices[ (node->start+i)*3 ];
1007 count += bvh_ray_tri( s, indices, co, dir, hit );
1008 }
1009 }
1010 else
1011 {
1012 count += bvh_ray( s, node->il, co, dir, hit );
1013 count += bvh_ray( s, node->ir, co, dir, hit );
1014 }
1015
1016 return count;
1017 }
1018
1019 static int bvh_raycast( scene *s, v3f co, v3f dir, ray_hit *hit )
1020 {
1021 v3f pb;
1022 v3_muladds( co, dir, hit->dist, pb );
1023
1024 int count = bvh_ray( s, 0, co, dir, hit );
1025
1026 if( count )
1027 {
1028 //vg_line( co, pb, 0xff00ffff );
1029
1030 v3f v0, v1;
1031
1032 float *pa = s->verts[hit->tri[0]].co,
1033 *pb = s->verts[hit->tri[1]].co,
1034 *pc = s->verts[hit->tri[2]].co;
1035
1036 v3_sub( pa, pb, v0 );
1037 v3_sub( pc, pb, v1 );
1038 v3_cross( v1, v0, hit->normal );
1039 v3_normalize( hit->normal );
1040 v3_muladds( co, dir, hit->dist, hit->pos );
1041 }
1042 else
1043 {
1044 //vg_line( co, pb, 0xff0000ff );
1045 }
1046
1047 return count;
1048 }
1049
1050 static int bvh_scene_sample_node_h( scene *s, u32 inode, v3f pos, v3f norm )
1051 {
1052 bvh_node *node = &s->bvh.nodes[ inode ];
1053
1054 if( (pos[0] >= node->bbx[0][0] && pos[0] <= node->bbx[1][0]) &&
1055 (pos[2] >= node->bbx[0][2] && pos[2] <= node->bbx[1][2]) )
1056 {
1057 if( !node->count )
1058 {
1059 if( bvh_scene_sample_node_h( s, node->il, pos, norm )) return 1;
1060 if( bvh_scene_sample_node_h( s, node->ir, pos, norm )) return 1;
1061 }
1062 else
1063 {
1064 for( u32 i=0; i<node->count; i++ )
1065 {
1066 u32 idx = (node->start+i)*3;
1067 model_vert *pa = &s->verts[ s->indices[ idx+0 ] ],
1068 *pb = &s->verts[ s->indices[ idx+1 ] ],
1069 *pc = &s->verts[ s->indices[ idx+2 ] ];
1070
1071 float height;
1072 if( triangle_raycast2d( pa->co, pb->co, pc->co, pos, &height ))
1073 {
1074 pos[1] = height;
1075
1076 if( norm )
1077 {
1078 v3f v0, v1;
1079 v3_sub( pa->co, pb->co, v0 );
1080 v3_sub( pc->co, pb->co, v1 );
1081 v3_cross( v1, v0, norm );
1082 v3_normalize( norm );
1083 }
1084
1085 return 1;
1086 }
1087 }
1088 }
1089 }
1090
1091 return 0;
1092 }
1093
1094 static int bvh_scene_sample_h( scene *s, v3f pos, v3f norm)
1095 {
1096 return bvh_scene_sample_node_h( s, 0, pos, norm );
1097 }
1098
1099 static int bvh_scene_sample( scene *s, v3f pos, ray_hit *hit )
1100 {
1101 hit->dist = INFINITY;
1102
1103 v3f ray_pos;
1104 v3_add( pos, (v3f){0.0f,4.0f,0.0f}, ray_pos );
1105
1106 if( bvh_raycast( s, ray_pos, (v3f){0.0f,-1.0f,0.0f}, hit ))
1107 {
1108 pos[1] = hit->pos[1];
1109 return 1;
1110 }
1111
1112 return 0;
1113 }
1114
1115 #endif