Untitled
Loading...
Searching...
No Matches
acceleration.c
Go to the documentation of this file.
1
6
7#include "core/camera.h"
8
9#include "utilities/mathf.h"
10#include "mesh.h"
11#include "utilities/types.h"
12#include "utilities/utilities.h"
13#include <math.h>
14#include "render/render.h"
15#include "load/init.h"
16
20static void swap_size_t(size_t * a, size_t * b);
21
28static void assign_next_nodes(BVHNode * nodes, int index, int next);
29
38static bool BVH_slab_test_aabb(RayHit * hit, AABB aabb, vec3 origin, vec3 inv_dir);
39
51static void ray_traverse_mesh_bvh(Mesh * m, MeshNode * mn, BVHNode * nodes, vec3 inv_pos, vec3 mod_dir, vec3 inv_dir, RayHit * hit, bool check_normal);
52
64static void ray_traverse_scene_bvh(SceneData * sd, BVHNode * nodes, vec3 origin, vec3 dir, vec3 mod_dir, vec3 inv_dir, RayHit * hit, bool check_normal);
65
66
75static void process_collision_node(Mesh * m, MeshNode * mn, BVHNode * node, vec3 proposed, CollisionPoints * p);
76
87static bool subdivide_scene_bvh(Vector * bvh_nodes, size_t * indices, AABB * aabbs, int pidx, int depth, int axes_tried);
88
97static bool subdivide_mesh_tri_bvh(Mesh * mesh, int pidx, int depth, int axes_tried);
109static bool subdivide_light_bvh(Vector * bvh_nodes, size_t * indices, AABB * aabbs, Light * lights, int pidx, int depth, int axes_tried);
110
111static void swap_size_t(size_t * a, size_t * b)
112{
113 size_t c = *a;
114 *a = *b;
115 *b = c;
116}
117
118static void assign_next_nodes(BVHNode * nodes, int index, int next)
119{
120
121 BVHNode * node = &nodes[index];
122
123 node->next = next;
124 if (node->left != -1)
125 {
126 assign_next_nodes(nodes, node->left, node->right);
127
128 assign_next_nodes(nodes, node->right, next);
129 }
130
131}
132
133
134static bool BVH_slab_test_aabb(RayHit * hit, AABB aabb, vec3 origin, vec3 inv_dir)
135{
136
137 float tx1 = (aabb.min_x - origin.x) * inv_dir.x;
138 float tx2 = (aabb.max_x - origin.x) * inv_dir.x;
139 float ty1 = (aabb.min_y - origin.y) * inv_dir.y;
140 float ty2 = (aabb.max_y - origin.y) * inv_dir.y;
141 float tz1 = (aabb.min_z - origin.z) * inv_dir.z;
142 float tz2 = (aabb.max_z - origin.z) * inv_dir.z;
143 float txmin = fminf(tx1, tx2);
144 float txmax = fmaxf(tx1, tx2);
145 float tymin = fminf(ty1, ty2);
146 float tymax = fmaxf(ty1, ty2);
147 float tzmin = fminf(tz1, tz2);
148 float tzmax = fmaxf(tz1, tz2);
149
150 float t_enter = fmaxf(txmin, fmaxf(tymin, tzmin));
151
152 float t_exit = fminf(txmax, fminf(tymax, tzmax));
153
154 return (t_exit >= fmaxf(0.0f, t_enter) && t_enter < hit->t);
155}
156
157bool ray_intersects_aabb(AABB aabb, vec3 origin, vec3 dir, vec3 inv_dir)
158{
159
160 float tx1 = (aabb.min_x - origin.x) * inv_dir.x;
161 float tx2 = (aabb.max_x - origin.x) * inv_dir.x;
162 float ty1 = (aabb.min_y - origin.y) * inv_dir.y;
163 float ty2 = (aabb.max_y - origin.y) * inv_dir.y;
164 float tz1 = (aabb.min_z - origin.z) * inv_dir.z;
165 float tz2 = (aabb.max_z - origin.z) * inv_dir.z;
166 float txmin = fminf(tx1, tx2);
167 float txmax = fmaxf(tx1, tx2);
168 float tymin = fminf(ty1, ty2);
169 float tymax = fmaxf(ty1, ty2);
170 float tzmin = fminf(tz1, tz2);
171 float tzmax = fmaxf(tz1, tz2);
172
173 float t_enter = fmaxf(txmin, fmaxf(tymin, tzmin));
174
175 float t_exit = fminf(txmax, fminf(tymax, tzmax));
176
177 if (t_enter > t_exit) return false;
178 if (t_exit < 0) return false;
179
180 return true;
181}
182bool ray_intersects_aabb_with_point(AABB aabb, vec3 origin, vec3 dir, vec3 inv_dir, vec3 * intersection_point)
183{
184
185 float tx1 = (aabb.min_x - origin.x) * inv_dir.x;
186 float tx2 = (aabb.max_x - origin.x) * inv_dir.x;
187 float ty1 = (aabb.min_y - origin.y) * inv_dir.y;
188 float ty2 = (aabb.max_y - origin.y) * inv_dir.y;
189 float tz1 = (aabb.min_z - origin.z) * inv_dir.z;
190 float tz2 = (aabb.max_z - origin.z) * inv_dir.z;
191 float txmin = fminf(tx1, tx2);
192 float txmax = fmaxf(tx1, tx2);
193 float tymin = fminf(ty1, ty2);
194 float tymax = fmaxf(ty1, ty2);
195 float tzmin = fminf(tz1, tz2);
196 float tzmax = fmaxf(tz1, tz2);
197
198 float t_enter = fmaxf(txmin, fmaxf(tymin, tzmin));
199
200 float t_exit = fminf(txmax, fminf(tymax, tzmax));
201
202 if (t_enter > t_exit) return false;
203 if (t_exit < 0) return false;
204
205 if (t_enter < 0)
206 {
207 *intersection_point = vec3_add(origin, vec3_scale(dir, t_exit));
208 }
209 else
210 {
211 *intersection_point = vec3_add(origin, vec3_scale(dir, t_enter));
212 }
213 return true;
214}
215
216
217
218static const float RAY_EPS = 1e-6f;
219
220bool ray_intersects_obb_with_point(OBB obb, vec3 origin, vec3 dir, vec3 * intersection_point) {
221
222 vec3 axis_x = (vec3){obb.rot.a0, obb.rot.a1, obb.rot.a2};
223 vec3 axis_y = (vec3){obb.rot.b0, obb.rot.b1, obb.rot.b2};
224 vec3 axis_z = (vec3){obb.rot.c0, obb.rot.c1, obb.rot.c2};
225
226 vec3 center = obb.center;
227
228 vec3 rel = vec3_sub(origin, center);
229
230 vec3 local_orig = {
231 vec3_dot(rel, axis_x),
232 vec3_dot(rel, axis_y),
233 vec3_dot(rel, axis_z)
234 };
235
236 vec3 norm_dir = dir;
237 norm_dir = vec3_normalize(norm_dir);
238
239 vec3 local_dir = {
240 vec3_dot(norm_dir, axis_x),
241 vec3_dot(norm_dir, axis_y),
242 vec3_dot(norm_dir, axis_z)
243 };
244 float tmin = -INFINITY;
245 float tmax = INFINITY;
246
247 if (fabsf(local_dir.x) < RAY_EPS) {
248 if (local_orig.x < -obb.extents.x || local_orig.x > obb.extents.x) return false;
249 } else {
250 float invd = 1.0f / local_dir.x;
251 float t1 = (-obb.extents.x - local_orig.x) * invd;
252 float t2 = ( obb.extents.x - local_orig.x) * invd;
253 if (t1 > t2) { float tmp = t1; t1 = t2; t2 = tmp; }
254 if (t1 > tmin) tmin = t1;
255 if (t2 < tmax) tmax = t2;
256 if (tmin > tmax) return false;
257 }
258
259 if (fabsf(local_dir.y) < RAY_EPS) {
260 if (local_orig.y < -obb.extents.y || local_orig.y > obb.extents.y) return false;
261 } else {
262 float invd = 1.0f / local_dir.y;
263 float t1 = (-obb.extents.y - local_orig.y) * invd;
264 float t2 = ( obb.extents.y - local_orig.y) * invd;
265 if (t1 > t2) { float tmp = t1; t1 = t2; t2 = tmp; }
266 if (t1 > tmin) tmin = t1;
267 if (t2 < tmax) tmax = t2;
268 if (tmin > tmax) return false;
269 }
270
271 if (fabsf(local_dir.z) < RAY_EPS) {
272 if (local_orig.z < -obb.extents.z || local_orig.z > obb.extents.z) return false;
273 } else {
274 float invd = 1.0f / local_dir.z;
275 float t1 = (-obb.extents.z - local_orig.z) * invd;
276 float t2 = ( obb.extents.z - local_orig.z) * invd;
277 if (t1 > t2) { float tmp = t1; t1 = t2; t2 = tmp; }
278 if (t1 > tmin) tmin = t1;
279 if (t2 < tmax) tmax = t2;
280 if (tmin > tmax) return false;
281 }
282
283 if (tmax < 0.0f) return false;
284
285 if (tmin < 0.0f)
286 {
287 *intersection_point = vec3_add(origin, vec3_scale(dir, tmax));
288 return true;
289 }
290
291 *intersection_point = vec3_add(origin, vec3_scale(dir, tmin));
292
293 return true;
294
295}
296
297
298
299static void ray_traverse_mesh_bvh(Mesh * m, MeshNode * mn, BVHNode * nodes, vec3 inv_pos, vec3 mod_dir, vec3 inv_dir, RayHit * hit, bool check_normal)
300{
301
302 int ni = 0;
303 while (ni >= 0)
304 {
305 BVHNode * node = &nodes[ni];
306 if (!BVH_slab_test_aabb(hit, node->aabb, inv_pos, inv_dir))
307 {
308 ni = node->next;
309 continue;
310 }
311
312 if (node->left == -1 && node->right == -1)
313 {
314 size_t * mesh_indices = m->bvh_indices;
315
316 MeshFace * mfs = CAST_VEC(m->tris, MeshFace);
317 Point * pts = CAST_VEC(m->vertices, Point);
318
319 for (int j = 0; j < node->count; j++)
320 {
321 MeshFace * mf = &mfs[mesh_indices[j + node->first_index]];
322 vec3 pA = pts[mf->indices[0]].pos;
323 vec3 pB = pts[mf->indices[1]].pos;
324 vec3 pC = pts[mf->indices[2]].pos;
325
326 float tri_t;
327 vec3 hit_pos;
328 vec3 b = {0,0,0};
330 inv_pos,
331 mod_dir,
332 pA,
333 pB,
334 pC,
335 &tri_t, &hit_pos, &b)) {
336
337 bool col = false;
338 if (check_normal)
339 {
340 col = tri_t < hit->t && vec3_dot(mf->normal, mod_dir) < 0;
341 }
342 else
343 {
344 col = tri_t < hit->t;
345 }
346 if (col && tri_t < hit->t) {
347 hit->pos = hit_pos;
348 hit->t = tri_t;
349 hit->mesh_node_idx = mn->id;
350 hit->tri = mesh_indices[j + node->first_index];
351 hit->b0 = b.x;
352 hit->b1 = b.y;
353 hit->b2 = b.z;
354 hit->hit = HIT_STATIC;
355 }
356 }
357
358 }
359
360 ni = node->next;
361 }
362 else
363 {
364 ni = node->left;
365 }
366
367 }
368
369
370}
371
372
373static void ray_traverse_scene_bvh(SceneData * sd, BVHNode * nodes, vec3 origin, vec3 dir, vec3 mod_dir, vec3 inv_dir, RayHit * hit, bool check_normal)
374{
375
376 int ni = 0;
377 while (ni >= 0)
378 {
379
380 BVHNode * node = &nodes[ni];
381 if (!BVH_slab_test_aabb(hit, node->aabb, origin, inv_dir))
382 {
383 ni = node->next;
384 continue;
385 }
386
387 if (node->left == -1 && node->right == -1)
388 {
389 Mesh * meshes = CAST_VEC(GLOBALS.meshes, Mesh);
391
392 for (int i = 0; i < node->count; i++)
393 {
394 MeshNode * mn = &mns[sd->bvh_indices[i + node->first_index]];
395 if (mn->mesh == -1 || mn->free) continue;
396 Mesh * m = &meshes[mn->mesh];
397 BVHNode * mnodes = CAST_VEC(m->nodes, BVHNode);
398
399 mat4 mod;
400 m4_inverse((float*)&mod, (float*)&mn->global_matrix);
401 vec3 pm = mat4_mul_point(mod, origin);
402 vec3 md = mat4_mul_direction(mod, mod_dir);
403 vec3 inv_md = (vec3){1.0f/md.x, 1.0f/md.y, 1.0f/md.z};
404 if (m->static_mesh)
405 {
406 ray_traverse_mesh_bvh(m, mn, mnodes, pm, md, inv_md, hit, check_normal);
407 }
408 else
409 {
410 vec3 intersection;
413 for (int j = 0; j < 24; j++)
414 {
415 DEBUG_LINES[DEBUG_LINE_COUNT + j].color = (vec3){0,1,0};
416 }
417 DEBUG_LINE_COUNT += 24;
418 if (ray_intersects_aabb_with_point(m->aabb, pm, dir, inv_md, &intersection))
419 {
420
421
422 float t = vec3_length(vec3_sub(origin, intersection));
423 if (t < hit->t)
424 {
425
426 hit->pos = intersection;
427 hit->t = t;
428 hit->mesh_node_idx = sd->bvh_indices[i + node->first_index];
430
431 }
432 }
433 }
434 }
435 ni = node->next;
436 }
437 else
438 {
439 ni = node->left;
440 }
441
442 }
443
444}
445
446
447
448RayHit raycast_scene(vec3 start, vec3 dir, float initial_t, bool check_normal)
449{
450
451 RayHit hit;
452 hit.hit = 0;
453 hit.t = initial_t;
455 vec3 inv_dir = {(dir.x == 0) ? 100000.0f : 1.0f/dir.x, (dir.y == 0) ? 100000.0f : 1.0f/dir.y, (dir.z == 0) ? 100000.0f : 1.0f/dir.z};
456
457 ray_traverse_scene_bvh(&GLOBALS.scene_data, nodes, start, dir, dir, inv_dir, &hit, check_normal);
460 {
462 }
463
464 return hit;
465
466}
467
468
469
470static void process_collision_node(Mesh * m, MeshNode * mn, BVHNode * node, vec3 proposed, CollisionPoints * p)
471{
472
473 MeshFace * fs = CAST_VEC(m->tris, MeshFace);
474 Point * v = CAST_VEC(m->vertices, Point);
475 size_t * li = m->bvh_indices;
476 int tris = 0;
477 for (int k = 0; k < node->count; k++)
478 {
479
480 MeshFace * f = &fs[li[k + node->first_index]];
481 mat4 model = mn->global_matrix;
482 mat4 tp = m4_transpose(model);
483 mat4 inv;
484 m4_inverse((float*)&inv, (float*)&tp);
485 vec3 A = mat4_mul_point(mn->global_matrix, v[f->indices[0]].pos);
486 vec3 B = mat4_mul_point(mn->global_matrix, v[f->indices[1]].pos);
487 vec3 C = mat4_mul_point(mn->global_matrix, v[f->indices[2]].pos);
489
490 tris++;
492 if (collision(proposed, (vec3[]){A, B, C}, nr, &pt))
493 {
494 if (pt.d > p->d)
495 {
496 *p = pt;
497 p->bias_impulse = 0;
498 p->normal_impulse = 0;
499 p->tangent_impulse = 0;
500 p->d = pt.d;
501 p->normal = nr;
502 p->collision = true;
503 p->mnB = mn->id;
504 p->pcB = mn->pc;
505 }
506 }
507
508 }
509}
510
511
512
513// TODO make this non-recursive
514bool traverse_collision_bvh(Mesh * m, MeshNode * mn, BVHNode * nodes, BVHNode * node, vec3 proposed, vec3 inv_p, CollisionPoints * p)
515{
516
517 AABB aabb = node->aabb;
518
519 float eps = 0.21f;
520
521 aabb.min_x -= eps;
522 aabb.min_y -= eps;
523 aabb.min_z -= eps;
524 aabb.max_x += eps;
525 aabb.max_y += eps;
526 aabb.max_z += eps;
527
528
529 if (!point_in_aabb(inv_p, &aabb))
530 {
531 return false;
532 }
533
534 if (node->left == -1 && node->right == -1)
535 {
536 process_collision_node(m, mn, node, proposed, p);
537 }
538
539 if (node->left >= 0)
540 {
541
542 BVHNode * left = &nodes[node->left];
543
544 traverse_collision_bvh(m, mn, nodes, left, proposed, inv_p, p);
545 }
546 if (node->right >= 0)
547 {
548
549 BVHNode * right = &nodes[node->right];
550
551 traverse_collision_bvh(m, mn, nodes, right, proposed, inv_p, p);
552 }
553 return false;
554
555}
556
557
558
559
560
561
562static bool subdivide_scene_bvh(Vector * bvh_nodes, size_t * indices, AABB * aabbs, int pidx, int depth, int axes_tried)
563{
564
565
566 BVHNode * nodes = CAST_VEC(*bvh_nodes, BVHNode);
567 BVHNode * parent = &nodes[pidx];
568
569 AXIS longest;
570 if (parent->aabb.extents.x >= parent->aabb.extents.y && parent->aabb.extents.x >= parent->aabb.extents.z)
571 {
572 longest = X;
573 }
574 if (parent->aabb.extents.y >= parent->aabb.extents.x && parent->aabb.extents.y >= parent->aabb.extents.z) longest = Y;
575 if (parent->aabb.extents.z >= parent->aabb.extents.x && parent->aabb.extents.z >= parent->aabb.extents.y) longest = Z;
576
577 AXIS second_longest;
578 AXIS third_longest;
579 switch(longest)
580 {
581 case X:
582
583 if (parent->aabb.extents.y > parent->aabb.extents.z)
584 {
585 second_longest = Y;
586 third_longest = Z;
587 }
588 else
589 {
590 second_longest = Z;
591 third_longest = Y;
592 }
593 if (axes_tried == 1)
594 {
595 longest = second_longest;
596 }
597 else
598 {
599 longest = third_longest;
600 }
601 break;
602 case Y:
603 if (parent->aabb.extents.x > parent->aabb.extents.z)
604 {
605 second_longest = X;
606 third_longest = Z;
607 }
608 else
609 {
610 second_longest = Z;
611 third_longest = X;
612 }
613 if (axes_tried == 1)
614 {
615 longest = second_longest;
616 }
617 else
618 {
619 longest = third_longest;
620 }
621 break;
622 case Z:
623 if (parent->aabb.extents.y > parent->aabb.extents.x)
624 {
625 second_longest = Y;
626 third_longest = X;
627 }
628 else
629 {
630 second_longest = X;
631 third_longest = Y;
632 }
633 if (axes_tried == 1)
634 {
635 longest = second_longest;
636 }
637 else
638 {
639 longest = third_longest;
640 }
641 break;
642 }
643
644
645 BVHNode left_child = {0}, right_child = {0};
646 left_child.parent = pidx;
647 right_child.parent = pidx;
648
649 vec3 split_pos = parent->aabb.center;
650
651 int i = parent->first_index;
652 int j = parent->first_index + parent->count - 1;
653
654 switch(longest)
655 {
656 case X:
657
658 {
659 float split_pos = parent->aabb.min_x + parent->aabb.extents.x;
660
661 while (i <= j)
662 {
663 AABB tr = aabbs[indices[i]];
664 if (tr.center.x < split_pos)
665 {
666
667 i++;
668 }
669 else
670 {
671 swap_size_t(&indices[i], &indices[j--]);
672 }
673 }
674
675 }
676 break;
677 case Y:
678 {
679 float split_pos = parent->aabb.min_y + parent->aabb.extents.y;
680
681 while (i <= j)
682 {
683 AABB tr = aabbs[indices[i]];
684 if (tr.center.y < split_pos)
685 {
686
687 i++;
688 }
689 else
690 {
691 swap_size_t(&indices[i], &indices[j--]);
692 }
693 }
694 }
695 break;
696 case Z:
697 {
698 float split_pos = parent->aabb.min_z + parent->aabb.extents.z;
699
700 while (i <= j)
701 {
702 AABB tr = aabbs[indices[i]];
703 if (tr.center.z < split_pos)
704 {
705
706 i++;
707 }
708 else
709 {
710 swap_size_t(&indices[i], &indices[j--]);
711 }
712 }
713 }
714 break;
715 }
716
717 size_t left_count = i - parent->first_index;
718 left_child.first_index = parent->first_index;
719 left_child.count = left_count;
720 right_child.first_index = i;
721 right_child.count = parent->count - left_count;
722
723
724
725 left_child.aabb.min_x = INFINITY;
726 left_child.aabb.min_y = INFINITY;
727 left_child.aabb.min_z = INFINITY;
728 left_child.aabb.max_x = -INFINITY;
729 left_child.aabb.max_y = -INFINITY;
730 left_child.aabb.max_z = -INFINITY;
731
732 AABB * left_aabb = &left_child.aabb;
733
734 for (int k = left_child.first_index; k < left_child.first_index + left_child.count; k++)
735 {
736 AABB tr = aabbs[indices[k]];
737
738 if (tr.min_x < left_aabb->min_x) left_aabb->min_x = tr.min_x;
739 if (tr.min_y < left_aabb->min_y) left_aabb->min_y = tr.min_y;
740 if (tr.min_z < left_aabb->min_z) left_aabb->min_z = tr.min_z;
741 if (tr.max_x > left_aabb->max_x) left_aabb->max_x = tr.max_x;
742 if (tr.max_y > left_aabb->max_y) left_aabb->max_y = tr.max_y;
743 if (tr.max_z > left_aabb->max_z) left_aabb->max_z = tr.max_z;
744
745 }
746
747 calculate_aabb_extents(left_aabb);
748
749
750 right_child.aabb.min_x = INFINITY;
751 right_child.aabb.min_y = INFINITY;
752 right_child.aabb.min_z = INFINITY;
753 right_child.aabb.max_x = -INFINITY;
754 right_child.aabb.max_y = -INFINITY;
755 right_child.aabb.max_z = -INFINITY;
756
757 AABB * right_aabb = &right_child.aabb;
758
759 for (int k = right_child.first_index; k < right_child.first_index + right_child.count; k++)
760 {
761 AABB tr = aabbs[indices[k]];
762 if (tr.min_x < right_aabb->min_x) right_aabb->min_x = tr.min_x;
763 if (tr.min_y < right_aabb->min_y) right_aabb->min_y = tr.min_y;
764 if (tr.min_z < right_aabb->min_z) right_aabb->min_z = tr.min_z;
765 if (tr.max_x > right_aabb->max_x) right_aabb->max_x = tr.max_x;
766 if (tr.max_y > right_aabb->max_y) right_aabb->max_y = tr.max_y;
767 if (tr.max_z > right_aabb->max_z) right_aabb->max_z = tr.max_z;
768
769
770 }
771
772 calculate_aabb_extents(right_aabb);
773
774
775
776
777 const int split_margin = 0;
778 bool can_split = (right_child.count > split_margin || left_count > split_margin);
779 bool can_leaf = !(right_child.count > split_margin || left_count > split_margin) || axes_tried == 2;
780 bool did_split = (left_count == 0 || right_child.count == 0);
781 if (!can_split || axes_tried == 2)
782 {
783 parent = &nodes[pidx];
784
785 size_t found_indices = 0;
786
787 float eps = 0.01f;
788
789 parent->aabb.min_x -= eps;
790 parent->aabb.min_y -= eps;
791 parent->aabb.min_z -= eps;
792 parent->aabb.max_x += eps;
793 parent->aabb.max_y += eps;
794 parent->aabb.max_z += eps;
795
797
798 parent->left = -1;
799 parent->right = -1;
800 parent->next = -1;
801 parent->index = bvh_nodes->count - 1;
802
803
804 return false;
805 }
806 else if (did_split)
807 {
808
809 subdivide_scene_bvh(bvh_nodes, indices, aabbs, bvh_nodes->count-1, depth, axes_tried + 1);
810 return true;
811
812 }
813
814 parent = &nodes[pidx];
815
816
817 left_child.left = -1;
818 left_child.right = -1;
819 BVHNode * left = vector_expand(bvh_nodes, 1);
820 *left = left_child;
821 left->index = bvh_nodes->count-1;
822 nodes = CAST_VEC(*bvh_nodes, BVHNode);
823 parent = &nodes[pidx];
824 parent->left = bvh_nodes->count-1;
825 bool divided = subdivide_scene_bvh(bvh_nodes, indices, aabbs, bvh_nodes->count-1, depth + 1, 0);
826 nodes = CAST_VEC(*bvh_nodes, BVHNode);
827 parent = &nodes[pidx];
828
829 right_child.left = -1;
830 right_child.right = -1;
831 BVHNode * right = vector_expand(bvh_nodes, 1);
832 *right = right_child;
833 right->index = bvh_nodes->count-1;
834 nodes = CAST_VEC(*bvh_nodes, BVHNode);
835 parent = &nodes[pidx];
836 parent->right = bvh_nodes->count-1;
837 divided = subdivide_scene_bvh(bvh_nodes, indices, aabbs, bvh_nodes->count-1, depth + 1, 0);
838 nodes = CAST_VEC(*bvh_nodes, BVHNode);
839 parent = &nodes[pidx];
840
841 return true;
842
843
844
845}
846
847
848
849
851{
852
854 AABB * aabb = &sd->aabb;
855 aabb->min_x = INFINITY;
856 aabb->min_y = INFINITY;
857 aabb->min_z = INFINITY;
858 aabb->max_x = -INFINITY;
859 aabb->max_y = -INFINITY;
860 aabb->max_z = -INFINITY;
861
864
865
866 for (int i = 0; i < GLOBALS.mesh_nodes.count; i++)
867 {
868
869 MeshNode * mn = &mns[i];
870 Mesh * m = &ms[mn->mesh];
871 if (mn->free) continue;
873 if (a.min_x < aabb->min_x) aabb->min_x = a.min_x;
874 if (a.min_y < aabb->min_y) aabb->min_y = a.min_y;
875 if (a.min_z < aabb->min_z) aabb->min_z = a.min_z;
876 if (a.max_x > aabb->max_x) aabb->max_x = a.max_x;
877 if (a.max_y > aabb->max_y) aabb->max_y = a.max_y;
878 if (a.max_z > aabb->max_z) aabb->max_z = a.max_z;
879
880 }
881 float ex_x = fabsf(aabb->max_x - aabb->min_x) / 2;
882 float ex_y = fabsf(aabb->max_y - aabb->min_y) / 2;
883 float ex_z = fabsf(aabb->max_z - aabb->min_z) / 2;
884 float mid_x = ex_x + aabb->min_x;
885 float mid_y = ex_y + aabb->min_y;
886 float mid_z = ex_z + aabb->min_z;
887
888 aabb->center = (vec3){mid_x, mid_y, mid_z};
889 aabb->extents = (vec3){ex_x, ex_y, ex_z};
890
891 if (sd->bvh_indices) free(sd->bvh_indices);
892 if (sd->bvh_nodes.buffer) free(sd->bvh_nodes.buffer);
893
894 sd->bvh_indices = malloc(sizeof(size_t) * GLOBALS.mesh_nodes.count);
895 AABB * aabbs = malloc(sizeof(AABB) * GLOBALS.mesh_nodes.count);
896 init_vector(&sd->bvh_nodes, 0, sizeof(BVHNode));
897
898 int bvh_indices_count = 0;
899 for (int i = 0; i < GLOBALS.mesh_nodes.count; i++)
900 {
901 if (mns[i].mesh == -1 || mns[i].free)
902 {
903 continue;
904 }
905 sd->bvh_indices[bvh_indices_count++] = i;
906 Mesh * m = &ms[mns[i].mesh];
907 aabbs[i] = transform_aabb_by_model_matrix(m->aabb, mns[i].global_matrix);
908 }
909
910 sd->bvh_indices_count = bvh_indices_count;
911
912
913 BVHNode * root = vector_expand(&sd->bvh_nodes, 1);
914 root->left = -1;
915 root->right = -1;
916 root->parent = -1;
917 root->first_index = 0;
918 root->index = 0;
919 root->count = bvh_indices_count;
920 root->aabb = sd->aabb;
921 root->next = -1;
922
923 subdivide_scene_bvh(&sd->bvh_nodes, sd->bvh_indices, aabbs, 0, 0, 0);
924
925
926 BVHNode * nodes = CAST_VEC(sd->bvh_nodes, BVHNode);
927 assign_next_nodes(nodes, 0, -1);
928
929 free(aabbs);
930}
931
932
933
934
935
936static bool subdivide_mesh_tri_bvh(Mesh * mesh, int pidx, int depth, int axes_tried)
937{
938
939 BVHNode * nodes = CAST_VEC(mesh->nodes, BVHNode);
940 BVHNode * parent = &nodes[pidx];
941 size_t * bvh_indices = mesh->bvh_indices;
942
943
944 AXIS longest;
945 if (parent->aabb.extents.x >= parent->aabb.extents.y && parent->aabb.extents.x >= parent->aabb.extents.z) longest = X;
946 if (parent->aabb.extents.y >= parent->aabb.extents.x && parent->aabb.extents.y >= parent->aabb.extents.z) longest = Y;
947 if (parent->aabb.extents.z >= parent->aabb.extents.x && parent->aabb.extents.z >= parent->aabb.extents.y) longest = Z;
948
949 AXIS second_longest;
950 AXIS third_longest;
951 switch(longest)
952 {
953 case X:
954
955 if (parent->aabb.extents.y > parent->aabb.extents.z)
956 {
957 second_longest = Y;
958 third_longest = Z;
959 }
960 else
961 {
962 second_longest = Z;
963 third_longest = Y;
964 }
965 if (axes_tried == 1)
966 {
967 longest = second_longest;
968 }
969 else
970 {
971 longest = third_longest;
972 }
973 break;
974 case Y:
975 if (parent->aabb.extents.x > parent->aabb.extents.z)
976 {
977 second_longest = X;
978 third_longest = Z;
979 }
980 else
981 {
982 second_longest = Z;
983 third_longest = X;
984 }
985 if (axes_tried == 1)
986 {
987 longest = second_longest;
988 }
989 else
990 {
991 longest = third_longest;
992 }
993 break;
994 case Z:
995 if (parent->aabb.extents.y > parent->aabb.extents.x)
996 {
997 second_longest = Y;
998 third_longest = X;
999 }
1000 else
1001 {
1002 second_longest = X;
1003 third_longest = Y;
1004 }
1005 if (axes_tried == 1)
1006 {
1007 longest = second_longest;
1008 }
1009 else
1010 {
1011 longest = third_longest;
1012 }
1013 break;
1014 }
1015 BVHNode left_child = {0}, right_child = {0};
1016 left_child.parent = pidx;
1017 right_child.parent = pidx;
1018
1019 vec3 split_pos = parent->aabb.center;
1020
1021
1022 int i = parent->first_index;
1023 int j = parent->first_index + parent->count - 1;
1024 Point * pts = CAST_VEC(mesh->vertices, Point);
1025 MeshFace * faces = CAST_VEC(mesh->tris, MeshFace);
1026 AABB * aabbs = CAST_VEC(mesh->tri_aabbs, AABB);
1027
1028 vec3 clip_plane;
1029 vec3 clip_point;
1030
1031
1032
1033
1034
1035 switch(longest)
1036 {
1037 case X:
1038
1039 {
1040 float split_pos = parent->aabb.min_x + parent->aabb.extents.x;
1041 while (i <= j)
1042 {
1043 MeshFace * m = &faces[bvh_indices[i]];
1044 AABB * aabb = &aabbs[bvh_indices[i]];
1045 if (aabb->center.x < split_pos)
1046 {
1047
1048 i++;
1049 }
1050 else
1051 {
1052 swap_size_t(&bvh_indices[i], &bvh_indices[j--]);
1053 }
1054 }
1055
1056 }
1057 break;
1058 case Y:
1059 {
1060 float split_pos = parent->aabb.min_y + parent->aabb.extents.y;
1061
1062 while (i <= j)
1063 {
1064 MeshFace * m = &faces[bvh_indices[i]];
1065 AABB * aabb = &aabbs[bvh_indices[i]];
1066 if (aabb->center.y < split_pos)
1067 {
1068
1069 i++;
1070 }
1071 else
1072 {
1073 swap_size_t(&bvh_indices[i], &bvh_indices[j--]);
1074 }
1075 }
1076 }
1077 break;
1078 case Z:
1079 {
1080 float split_pos = parent->aabb.min_z + parent->aabb.extents.z;
1081
1082 while (i <= j)
1083 {
1084 MeshFace * m = &faces[bvh_indices[i]];
1085 AABB * aabb = &aabbs[bvh_indices[i]];
1086 if (aabb->center.z < split_pos)
1087 {
1088
1089 i++;
1090 }
1091 else
1092 {
1093 swap_size_t(&bvh_indices[i], &bvh_indices[j--]);
1094 }
1095 }
1096 }
1097 break;
1098 }
1099
1100
1101 size_t left_count = i - parent->first_index;
1102 left_child.first_index = parent->first_index;
1103 left_child.count = left_count;
1104 right_child.first_index = i;
1105 right_child.count = parent->count - left_count;
1106
1107 left_child.aabb.min_x = INFINITY;
1108 left_child.aabb.min_y = INFINITY;
1109 left_child.aabb.min_z = INFINITY;
1110 left_child.aabb.max_x = -INFINITY;
1111 left_child.aabb.max_y = -INFINITY;
1112 left_child.aabb.max_z = -INFINITY;
1113
1114 AABB * left_aabb = &left_child.aabb;
1115
1116 for (int k = left_child.first_index; k < left_child.first_index + left_child.count; k++)
1117 {
1118
1119 AABB * aabb = &aabbs[bvh_indices[k]];
1120
1121 if (aabb->min_x < left_aabb->min_x) left_aabb->min_x = aabb->min_x;
1122 if (aabb->min_y < left_aabb->min_y) left_aabb->min_y = aabb->min_y;
1123 if (aabb->min_z < left_aabb->min_z) left_aabb->min_z = aabb->min_z;
1124 if (aabb->max_x > left_aabb->max_x) left_aabb->max_x = aabb->max_x;
1125 if (aabb->max_y > left_aabb->max_y) left_aabb->max_y = aabb->max_y;
1126 if (aabb->max_z > left_aabb->max_z) left_aabb->max_z = aabb->max_z;
1127
1128 }
1129 calculate_aabb_extents(left_aabb);
1130
1131
1132 right_child.aabb.min_x = INFINITY;
1133 right_child.aabb.min_y = INFINITY;
1134 right_child.aabb.min_z = INFINITY;
1135 right_child.aabb.max_x = -INFINITY;
1136 right_child.aabb.max_y = -INFINITY;
1137 right_child.aabb.max_z = -INFINITY;
1138
1139 AABB * right_aabb = &right_child.aabb;
1140
1141 for (int k = right_child.first_index; k < right_child.first_index + right_child.count; k++)
1142 {
1143
1144 AABB * aabb = &aabbs[bvh_indices[k]];
1145
1146 if (aabb->min_x < right_aabb->min_x) right_aabb->min_x = aabb->min_x;
1147 if (aabb->min_y < right_aabb->min_y) right_aabb->min_y = aabb->min_y;
1148 if (aabb->min_z < right_aabb->min_z) right_aabb->min_z = aabb->min_z;
1149 if (aabb->max_x > right_aabb->max_x) right_aabb->max_x = aabb->max_x;
1150 if (aabb->max_y > right_aabb->max_y) right_aabb->max_y = aabb->max_y;
1151 if (aabb->max_z > right_aabb->max_z) right_aabb->max_z = aabb->max_z;
1152
1153 }
1154
1155 calculate_aabb_extents(right_aabb);
1156
1157 const int split_margin = 3;
1158 bool can_split = (right_child.count > split_margin || left_count > split_margin);
1159 bool can_leaf = !(right_child.count > split_margin || left_count > split_margin) || axes_tried == 2;
1160 bool did_split = (left_count == 0 || right_child.count == 0);
1161 if (!can_split || axes_tried == 2)
1162 {
1163 parent = &nodes[pidx];
1164 MeshFace * faces = CAST_VEC(mesh->tris, MeshFace);
1165
1166 size_t found_indices = 0;
1167
1168 float eps = 0.01f;
1169
1170 parent->aabb.min_x -= eps;
1171 parent->aabb.min_y -= eps;
1172 parent->aabb.min_z -= eps;
1173 parent->aabb.max_x += eps;
1174 parent->aabb.max_y += eps;
1175 parent->aabb.max_z += eps;
1176
1177 calculate_aabb_extents(&parent->aabb);
1178
1179 parent->left = -1;
1180 parent->right = -1;
1181 parent->next = -1;
1182 parent->index = mesh->nodes.count - 1;
1183
1184
1185
1186 return false;
1187 }
1188 else if (did_split)
1189 {
1190
1191 bool divided = subdivide_mesh_tri_bvh(mesh, mesh->nodes.count-1, depth, axes_tried+1);
1192
1193 return true;
1194 }
1195
1196 parent = &nodes[pidx];
1197
1198
1199 left_child.left = -1;
1200 left_child.right = -1;
1201 BVHNode * left = vector_expand(&mesh->nodes, 1);
1202 *left = left_child;
1203 left->index = mesh->nodes.count-1;
1204 nodes = CAST_VEC(mesh->nodes, BVHNode);
1205 parent = &nodes[pidx];
1206 parent->left = mesh->nodes.count-1;
1207 bool divided = subdivide_mesh_tri_bvh(mesh, mesh->nodes.count-1, depth + 1, 0);
1208 nodes = CAST_VEC(mesh->nodes, BVHNode);
1209 parent = &nodes[pidx];
1210
1211 right_child.left = -1;
1212 right_child.right = -1;
1213 BVHNode * right = vector_expand(&mesh->nodes, 1);
1214 *right = right_child;
1215 right->index = mesh->nodes.count-1;
1216 nodes = CAST_VEC(mesh->nodes, BVHNode);
1217 parent = &nodes[pidx];
1218 parent->right = mesh->nodes.count-1;
1219 divided = subdivide_mesh_tri_bvh(mesh, mesh->nodes.count-1, depth + 1, 0);
1220 nodes = CAST_VEC(mesh->nodes, BVHNode);
1221 parent = &nodes[pidx];
1222
1223 return true;
1224
1225
1226
1227}
1228
1229
1230// tri bvh over a mesh
1232{
1233
1234 init_vector(&mesh->nodes, 0, sizeof(BVHNode));
1235
1236 BVHNode * root = vector_expand(&mesh->nodes, 1);
1237
1238 root->aabb = mesh->aabb;
1239 root->first_index = 0;
1240 root->count = mesh->tris.count;
1241 root->left = -1;
1242 root->right = -1;
1243 root->parent = -1;
1244 root->next = -1;
1245 root->index = mesh->nodes.count-1;
1246
1247 mesh->bvh_indices = malloc(sizeof(size_t) * mesh->tris.count);
1248 init_vector(&mesh->tri_aabbs, mesh->tris.count, sizeof(AABB));
1249 AABB * aabbs = CAST_VEC(mesh->tri_aabbs, AABB);
1250 MeshFace * mfs = CAST_VEC(mesh->tris, MeshFace);
1251 Point * pts = CAST_VEC(mesh->vertices, Point);
1252 size_t * indices = malloc(sizeof(size_t) * mesh->tris.count);
1253 for (int i = 0; i < mesh->tris.count; i++)
1254 {
1255 MeshFace * mf = &mfs[i];
1256 indices[i] = i;
1257 mesh->bvh_indices[i] = i;
1258
1259
1260 compute_aabb_from_points((vec3[]){pts[mf->indices[0]].pos, pts[mf->indices[1]].pos, pts[mf->indices[2]].pos}, 3, &aabbs[i]);
1261
1262 }
1263
1264 subdivide_mesh_tri_bvh(mesh, mesh->nodes.count-1, 0, 0);
1265
1266
1267 BVHNode * nodes = CAST_VEC(mesh->nodes, BVHNode);
1268
1269 assign_next_nodes(nodes, 0, -1);
1270
1271
1272 free(indices);
1273
1274
1275}
1276
1277
1278static bool subdivide_light_bvh(Vector * bvh_nodes, size_t * indices, AABB * aabbs, Light * lights, int pidx, int depth, int axes_tried)
1279{
1280
1281
1282 BVHNode * nodes = CAST_VEC(*bvh_nodes, BVHNode);
1283 BVHNode * parent = &nodes[pidx];
1284
1285 AXIS longest;
1286 if (parent->aabb.extents.x >= parent->aabb.extents.y && parent->aabb.extents.x >= parent->aabb.extents.z)
1287 {
1288 longest = X;
1289 }
1290 if (parent->aabb.extents.y >= parent->aabb.extents.x && parent->aabb.extents.y >= parent->aabb.extents.z) longest = Y;
1291 if (parent->aabb.extents.z >= parent->aabb.extents.x && parent->aabb.extents.z >= parent->aabb.extents.y) longest = Z;
1292
1293 AXIS second_longest;
1294 AXIS third_longest;
1295 switch(longest)
1296 {
1297 case X:
1298
1299 if (parent->aabb.extents.y > parent->aabb.extents.z)
1300 {
1301 second_longest = Y;
1302 third_longest = Z;
1303 }
1304 else
1305 {
1306 second_longest = Z;
1307 third_longest = Y;
1308 }
1309 if (axes_tried == 1)
1310 {
1311 longest = second_longest;
1312 }
1313 else
1314 {
1315 longest = third_longest;
1316 }
1317 break;
1318 case Y:
1319 if (parent->aabb.extents.x > parent->aabb.extents.z)
1320 {
1321 second_longest = X;
1322 third_longest = Z;
1323 }
1324 else
1325 {
1326 second_longest = Z;
1327 third_longest = X;
1328 }
1329 if (axes_tried == 1)
1330 {
1331 longest = second_longest;
1332 }
1333 else
1334 {
1335 longest = third_longest;
1336 }
1337 break;
1338 case Z:
1339 if (parent->aabb.extents.y > parent->aabb.extents.x)
1340 {
1341 second_longest = Y;
1342 third_longest = X;
1343 }
1344 else
1345 {
1346 second_longest = X;
1347 third_longest = Y;
1348 }
1349 if (axes_tried == 1)
1350 {
1351 longest = second_longest;
1352 }
1353 else
1354 {
1355 longest = third_longest;
1356 }
1357 break;
1358 }
1359
1360
1361 // size_t * bvh_indices = sd->bvh_indices;
1362
1363 BVHNode left_child = {0}, right_child = {0};
1364 left_child.parent = pidx;
1365 right_child.parent = pidx;
1366
1367 vec3 split_pos = parent->aabb.center;
1368
1369 int i = parent->first_index;
1370 int j = parent->first_index + parent->count - 1;
1371 // vec3 * pts = CAST_VEC(hull->vertices, vec3);
1372 // MeshFace * faces = CAST_VEC(hull->faces, MeshFace);
1373 // AABB * aabbs = CAST_VEC(mesh, AABB);
1374
1375
1376 // size_t * bvh_indices = CAST_VEC(sd->bvh_indices, size_t);
1377 vec3 clip_plane;
1378 vec3 clip_point;
1379
1380 switch(longest)
1381 {
1382 case X:
1383
1384 {
1385 float split_pos = parent->aabb.min_x + parent->aabb.extents.x;
1386
1387 while (i <= j)
1388 {
1389 AABB tr = aabbs[indices[i]];
1390 if (tr.center.x < split_pos)
1391 {
1392
1393 i++;
1394 }
1395 else
1396 {
1397 swap_size_t(&indices[i], &indices[j--]);
1398 }
1399 }
1400
1401 }
1402 break;
1403 case Y:
1404 {
1405 float split_pos = parent->aabb.min_y + parent->aabb.extents.y;
1406
1407 while (i <= j)
1408 {
1409 AABB tr = aabbs[indices[i]];
1410 if (tr.center.y < split_pos)
1411 {
1412
1413 i++;
1414 }
1415 else
1416 {
1417 swap_size_t(&indices[i], &indices[j--]);
1418 }
1419 }
1420 }
1421 break;
1422 case Z:
1423 {
1424 float split_pos = parent->aabb.min_z + parent->aabb.extents.z;
1425
1426 while (i <= j)
1427 {
1428 AABB tr = aabbs[indices[i]];
1429 if (tr.center.z < split_pos)
1430 {
1431
1432 i++;
1433 }
1434 else
1435 {
1436 swap_size_t(&indices[i], &indices[j--]);
1437 }
1438 }
1439 }
1440 break;
1441 }
1442
1443 size_t left_count = i - parent->first_index;
1444 left_child.first_index = parent->first_index;
1445 left_child.count = left_count;
1446 right_child.first_index = i;
1447 right_child.count = parent->count - left_count;
1448
1449
1450
1451 left_child.aabb.min_x = INFINITY;
1452 left_child.aabb.min_y = INFINITY;
1453 left_child.aabb.min_z = INFINITY;
1454 left_child.aabb.max_x = -INFINITY;
1455 left_child.aabb.max_y = -INFINITY;
1456 left_child.aabb.max_z = -INFINITY;
1457
1458 AABB * left_aabb = &left_child.aabb;
1459
1460 float left_flux = 0.0f;
1461 float left_em_flux = 0.0f;
1462 for (int k = left_child.first_index; k < left_child.first_index + left_child.count; k++)
1463 {
1464 AABB tr = aabbs[indices[k]];
1465 Light * l = &lights[indices[k]];
1466 if (l->light_type == DIRECTIONAL_LIGHT) continue;
1467
1468 if (l->light_type == AREA_LIGHT)
1469 {
1470 left_em_flux += l->power;
1471 }
1472 if (tr.min_x < left_aabb->min_x) left_aabb->min_x = tr.min_x;
1473 if (tr.min_y < left_aabb->min_y) left_aabb->min_y = tr.min_y;
1474 if (tr.min_z < left_aabb->min_z) left_aabb->min_z = tr.min_z;
1475 if (tr.max_x > left_aabb->max_x) left_aabb->max_x = tr.max_x;
1476 if (tr.max_y > left_aabb->max_y) left_aabb->max_y = tr.max_y;
1477 if (tr.max_z > left_aabb->max_z) left_aabb->max_z = tr.max_z;
1478 left_flux += l->power;
1479
1480 }
1481
1482 calculate_aabb_extents(left_aabb);
1483
1484 left_child.flux = left_flux;
1485 left_child.emissive_flux = left_em_flux;
1486
1487 right_child.aabb.min_x = INFINITY;
1488 right_child.aabb.min_y = INFINITY;
1489 right_child.aabb.min_z = INFINITY;
1490 right_child.aabb.max_x = -INFINITY;
1491 right_child.aabb.max_y = -INFINITY;
1492 right_child.aabb.max_z = -INFINITY;
1493
1494 AABB * right_aabb = &right_child.aabb;
1495
1496 float right_flux = 0.0f;
1497 float right_em_flux = 0.0f;
1498 for (int k = right_child.first_index; k < right_child.first_index + right_child.count; k++)
1499 {
1500
1501 AABB tr = aabbs[indices[k]];
1502 Light * l = &lights[indices[k]];
1503 if (l->light_type == DIRECTIONAL_LIGHT) continue;
1504
1505 if (l->light_type == AREA_LIGHT)
1506 {
1507 right_em_flux += l->power;
1508 }
1509 if (tr.min_x < right_aabb->min_x) right_aabb->min_x = tr.min_x;
1510 if (tr.min_y < right_aabb->min_y) right_aabb->min_y = tr.min_y;
1511 if (tr.min_z < right_aabb->min_z) right_aabb->min_z = tr.min_z;
1512 if (tr.max_x > right_aabb->max_x) right_aabb->max_x = tr.max_x;
1513 if (tr.max_y > right_aabb->max_y) right_aabb->max_y = tr.max_y;
1514 if (tr.max_z > right_aabb->max_z) right_aabb->max_z = tr.max_z;
1515 right_flux += l->power;
1516
1517 }
1518
1519 calculate_aabb_extents(right_aabb);
1520 right_child.flux = right_flux;
1521 right_child.emissive_flux = right_em_flux;
1522
1523
1524
1525
1526 const int split_margin = 3;
1527 bool can_split = (right_child.count > split_margin || left_count > split_margin);
1528 bool can_leaf = !(right_child.count > split_margin || left_count > split_margin) || axes_tried == 2;
1529 bool did_split = (left_count == 0 || right_child.count == 0);
1530 if (!can_split || axes_tried == 2)
1531 {
1532 parent = &nodes[pidx];
1533
1534 size_t found_indices = 0;
1535
1536 float eps = 0.01f;
1537
1538 parent->aabb.min_x -= eps;
1539 parent->aabb.min_y -= eps;
1540 parent->aabb.min_z -= eps;
1541 parent->aabb.max_x += eps;
1542 parent->aabb.max_y += eps;
1543 parent->aabb.max_z += eps;
1544
1545 calculate_aabb_extents(&parent->aabb);
1546
1547 parent->left = -1;
1548 parent->right = -1;
1549 parent->next = -1;
1550 parent->index = bvh_nodes->count - 1;
1551
1552
1553 return false;
1554 }
1555 else if (did_split)
1556 {
1557
1558 subdivide_scene_bvh(bvh_nodes, indices, aabbs, bvh_nodes->count-1, depth, axes_tried + 1);
1559 return true;
1560
1561 }
1562
1563 parent = &nodes[pidx];
1564
1565
1566 left_child.left = -1;
1567 left_child.right = -1;
1568 BVHNode * left = vector_expand(bvh_nodes, 1);
1569 *left = left_child;
1570 left->index = bvh_nodes->count-1;
1571 nodes = CAST_VEC(*bvh_nodes, BVHNode);
1572 parent = &nodes[pidx];
1573 parent->left = bvh_nodes->count-1;
1574 bool divided = subdivide_scene_bvh(bvh_nodes, indices, aabbs, bvh_nodes->count-1, depth + 1, 0);
1575 nodes = CAST_VEC(*bvh_nodes, BVHNode);
1576 parent = &nodes[pidx];
1577
1578 right_child.left = -1;
1579 right_child.right = -1;
1580 BVHNode * right = vector_expand(bvh_nodes, 1);
1581 *right = right_child;
1582 right->index = bvh_nodes->count-1;
1583 nodes = CAST_VEC(*bvh_nodes, BVHNode);
1584 parent = &nodes[pidx];
1585 parent->right = bvh_nodes->count-1;
1586 divided = subdivide_scene_bvh(bvh_nodes, indices, aabbs, bvh_nodes->count-1, depth + 1, 0);
1587 nodes = CAST_VEC(*bvh_nodes, BVHNode);
1588 parent = &nodes[pidx];
1589
1590 return true;
1591
1592
1593
1594}
1595
1596
1597
1598
1599
1601{
1602
1604 Mesh * meshes = CAST_VEC(GLOBALS.meshes, Mesh);
1607
1608 AABB parent_aabb;
1609 parent_aabb.min_x = INFINITY;
1610 parent_aabb.min_y = INFINITY;
1611 parent_aabb.min_z = INFINITY;
1612 parent_aabb.max_x = -INFINITY;
1613 parent_aabb.max_y = -INFINITY;
1614 parent_aabb.max_z = -INFINITY;
1615
1616 float total_flux = 0.0f;
1617 float emissive_flux = 0.0f;
1619 uint32_t directional_lights = 0;
1620 for (int i = 0; i < GLOBALS.lights.count; i++)
1621 {
1622
1623 Light * l = &ls[i];
1624 float lum = (l->rgb.x * 0.2126f) + (l->rgb.y * 0.7152f) + (l->rgb.z * 0.0722f);
1625 float power;
1627 *new_light = *l;
1628 new_light->lum = lum;
1629
1630 if (l->light_type == POINT_LIGHT)
1631 {
1632
1633 power = lum * l->intensity * M_PI * 4;
1634 new_light->power = power;
1635 }
1636 else if (l->light_type == SPOT_LIGHT)
1637 {
1638
1639 power = lum * l->intensity * M_PI * 2 * (1.0f - cosf(new_light->outer_angle));
1640 new_light->power = power;
1641 }
1642 if (l->light_type == DIRECTIONAL_LIGHT)
1643 {
1644 power = 0.0f;
1645 new_light->power = 0.0f;
1646 directional_lights++;
1647 }
1648 else
1649 {
1650
1651 new_light->area.center = new_light->pos;
1652 new_light->area.extents = (vec3){0, 0, 0};
1653 calculate_aabb_bounds(&new_light->area);
1654 if (new_light->area.min_x < parent_aabb.min_x) parent_aabb.min_x = new_light->area.min_x;
1655 if (new_light->area.min_y < parent_aabb.min_y) parent_aabb.min_y = new_light->area.min_y;
1656 if (new_light->area.min_z < parent_aabb.min_z) parent_aabb.min_z = new_light->area.min_z;
1657 if (new_light->area.max_x > parent_aabb.max_x) parent_aabb.max_x = new_light->area.max_x;
1658 if (new_light->area.max_y > parent_aabb.max_y) parent_aabb.max_y = new_light->area.max_y;
1659 if (new_light->area.max_z > parent_aabb.max_z) parent_aabb.max_z = new_light->area.max_z;
1660
1661
1662 total_flux += power;
1663 }
1664 }
1665
1666
1668
1669 float * matem = malloc(sizeof(float) * GLOBALS.materials.count);
1670 for (int i = 0; i < GLOBALS.materials.count; i++)
1671 {
1672 Material * mat = &mats[i];
1673 float em_len = vec4_length(mat->ke);
1674 float str = mat->emissive_strength;
1675 matem[i] = em_len * str;
1676 }
1677
1678 for (int i = 0; i < GLOBALS.scene_data.bvh_indices_count; i++)
1679 {
1680
1681 MeshNode * mn = &mns[GLOBALS.scene_data.bvh_indices[i]];
1682 if (mn->mesh == -1 || mn->free) continue;
1683 if (mn->static_mesh == 0) continue;
1684 Mesh * m = &meshes[mn->mesh];
1685 MeshFace * mfs = CAST_VEC(m->tris, MeshFace);
1686 Point * pts = CAST_VEC(m->vertices, Point);
1687 for (int j = 0; j < m->tris.count; j++)
1688 {
1689
1690 MeshFace * mf = &mfs[m->bvh_indices[j]];
1691 Material * mat = &mats[mf->material_id];
1692 float val = matem[mf->material_id];
1693 float area = triangle_area(pts[mf->indices[0]].pos, pts[mf->indices[1]].pos, pts[mf->indices[2]].pos);
1694 if (val > 0)
1695 {
1696
1699 l->threshold = 0.0006f;
1700 l->A = mat4_mul_point(mn->global_matrix, pts[mf->indices[0]].pos);
1701 l->B = mat4_mul_point(mn->global_matrix, pts[mf->indices[1]].pos);
1702 l->C = mat4_mul_point(mn->global_matrix, pts[mf->indices[2]].pos);
1705
1707 l->surface_area = area;
1708 float lum = (l->rgb.x * 0.2126f) + (l->rgb.y * 0.7152f) + (l->rgb.z * 0.0722f);
1709 float power = l->surface_area * lum * M_PI;
1710 l->lum = lum;
1711 l->power = power;
1712
1713 l->radius = sqrtf((lum * area) / (M_PI * l->threshold));
1714 l->mesh = i;
1715 l->tri = j;
1716 l->area.center = triangle_centroid(l->A, l->B, l->C);
1717 l->area.extents = (vec3){0.01, 0.01, 0.01};
1719 if (l->area.min_x < parent_aabb.min_x) parent_aabb.min_x = l->area.min_x;
1720 if (l->area.min_y < parent_aabb.min_y) parent_aabb.min_y = l->area.min_y;
1721 if (l->area.min_z < parent_aabb.min_z) parent_aabb.min_z = l->area.min_z;
1722 if (l->area.max_x > parent_aabb.max_x) parent_aabb.max_x = l->area.max_x;
1723 if (l->area.max_y > parent_aabb.max_y) parent_aabb.max_y = l->area.max_y;
1724 if (l->area.max_z > parent_aabb.max_z) parent_aabb.max_z = l->area.max_z;
1725 total_flux += power;
1726
1727 emissive_flux += power;
1728 }
1729 }
1730 }
1731
1732 free(matem);
1733 if (GLOBALS.scene_data.light_bvh.lights.count <= 0) return;
1734
1739
1740
1742
1743 calculate_aabb_extents(&parent_aabb);
1744
1745 uint32_t bvh_size = GLOBALS.scene_data.light_bvh.lights.count - directional_lights;
1746 GLOBALS.scene_data.light_bvh.indices = calloc(bvh_size, sizeof(size_t));
1747
1748 AABB * aabbs = malloc(sizeof(AABB) * GLOBALS.scene_data.light_bvh.lights.count);
1749
1751 uint32_t count = 0;
1752
1754 for (int i = 0; i < GLOBALS.scene_data.light_bvh.lights.count; i++)
1755 {
1756 if (new_lights[i].light_type == DIRECTIONAL_LIGHT) continue;
1758 aabbs[i] = new_lights[i].area;
1759 }
1760
1761
1763 root->left = -1;
1764 root->right = -1;
1765 root->parent = -1;
1766 root->first_index = 0;
1767 root->index = 0;
1769 root->aabb = parent_aabb;
1770 root->next = -1;
1771 root->flux = total_flux;
1772 root->emissive_flux = emissive_flux;
1773
1775
1777 assign_next_nodes(nodes, 0, -1);
1778
1779 free(aabbs);
1780
1781}
1782
1783
void init_scene_bvh()
Initializes or updates the pre-existing scene bvh based on all mesh nodes with valid meshes.
RayHit raycast_scene(vec3 start, vec3 dir, float initial_t, bool check_normal)
Raycasts through the scene and finds closest intersection to meshes.
bool ray_intersects_aabb(AABB aabb, vec3 origin, vec3 dir, vec3 inv_dir)
Checks if a ray intersects an aabb.
void process_collision_node(Mesh *m, MeshNode *mn, BVHNode *node, vec3 proposed, CollisionPoints *p)
Processes Player collision against a static MeshNode's triangle BVH node.
bool subdivide_scene_bvh(Vector *bvh_nodes, size_t *indices, AABB *aabbs, int pidx, int depth, int axes_tried)
Subdivides the SceneData's MeshNodes into a BVH.
bool BVH_slab_test_aabb(RayHit *hit, AABB aabb, vec3 origin, vec3 inv_dir)
Slab test for BVH.
void ray_traverse_mesh_bvh(Mesh *m, MeshNode *mn, BVHNode *nodes, vec3 inv_pos, vec3 mod_dir, vec3 inv_dir, RayHit *hit, bool check_normal)
Traverses a Mesh's triangle BVH.
bool subdivide_light_bvh(Vector *bvh_nodes, size_t *indices, AABB *aabbs, Light *lights, int pidx, int depth, int axes_tried)
Subdivides the SceneData's Lights into a BVH.
void ray_traverse_scene_bvh(SceneData *sd, BVHNode *nodes, vec3 origin, vec3 dir, vec3 mod_dir, vec3 inv_dir, RayHit *hit, bool check_normal)
Traverses a SceneData's MeshNode BVH.
const float RAY_EPS
void init_mesh_tri_bvh(Mesh *mesh)
Initializes the bvh for a mesh's triangles.
void build_light_bvh()
Initializes a bvh for all current lights and emissive triangles in the scene, and sets the flux up fo...
void assign_next_nodes(BVHNode *nodes, int index, int next)
Assigns next nodes for stackless traversal top-down.
void swap_size_t(size_t *a, size_t *b)
Swaps a and b.
bool ray_intersects_obb_with_point(OBB obb, vec3 origin, vec3 dir, vec3 *intersection_point)
Checks if a ray intersects an obb and outputs an intersection point.
bool subdivide_mesh_tri_bvh(Mesh *mesh, int pidx, int depth, int axes_tried)
Subdivides the Mesh's triangles into a BVH.
bool ray_intersects_aabb_with_point(AABB aabb, vec3 origin, vec3 dir, vec3 inv_dir, vec3 *intersection_point)
Checks if a ray intersects an aabb and outputs an intersection point.
bool traverse_collision_bvh(Mesh *m, MeshNode *mn, BVHNode *nodes, BVHNode *node, vec3 proposed, vec3 inv_p, CollisionPoints *p)
Traverses the mesh bvh to find collisions based on point vs aabb within a certain epsilon for player ...
RayHit ray_intersects_triangle(vec3 origin, vec3 dir, vec3 a, vec3 b, vec3 c)
RayHit hit
bool collision(vec3 proposed, vec3 pts[3], vec3 normal, CollisionPoints *p)
Definition camera.c:443
vec3 rot(vec3 M[3], vec3 a)
Refer to Ken Perlin's 2 joint IK implmentation.
Definition camera.c:1004
Functions for camera.
AABBBounds transform_aabb_by_model_matrix(MeshNode mn, mat4 mat)
LightBVH light_bvh
The LightBVH, required for baking lighting.
int bvh_indices_count
Vector mesh_nodes
MeshNodes.
@ AREA_LIGHT
@ POINT_LIGHT
@ SPOT_LIGHT
@ DIRECTIONAL_LIGHT
Vector lights
The Lights that were created (emissive triangles become AREA_LIGHTS).
SceneData scene_data
SceneData that is more-so scene specific.
Vector bvh_nodes
Vector meshes
Meshes.
Globals GLOBALS
Engine Globals.
Definition main.c:310
Vector lights
Lights.
Vector materials
Materials.
AABB aabb
AABB over the entire scene.
size_t * indices
The indices sorted when initialized.
Vector nodes
Each node of the BVH.
size_t * bvh_indices
size_t indices_count
The amount of indices on init (some lights are omitted).
The data for the current scene.
PhysicsComponent * pcB
float d
Length of B-A.
vec3 normal
The collision normal from B into A.
Points that track collision data such as direction, penetration depth, and more to generate Manifolds...
float intensity
The intensity of the Light.
size_t id
The ID inside of Globals.mesh_nodes.
vec3 pos
Position of light.
vec3 extents
Definition dynamic.frag:23
LightType light_type
The type of Light.
vec3 center
Definition dynamic.frag:15
float lum
The luminosity for importance sampling.
PhysicsComponent * pc
The physics controller initialized based on data from this MeshNode.
vec3 normal
float surface_area
The surface area of the triangle.
float power
The power for importance sampling.
int tri
The MeshFace this corresponds to.
float outer_angle
Outer angle for SPOT_LIGHTs.
bool free
If the MeshNode can be replaced.
float emissive_strength
vec4 ke
Emissive.
int mesh
The Mesh it references.
float radius
The radius of the Light.
int mesh
The MeshNode this corresponds to.
mat3 rot
Definition types.h:49
vec3 rgb
Color of the light.
bool static_mesh
If this mesh is static (DrawArrays) or dynamic (DrawElements), used to indicate Lightmap status.
float threshold
The threshold (how far a light reaches).
AABB area
The physical area of AREA_LIGHTs.
The CPU side structure for Lights.
The Materials parsed in from scene files that determine rendering pipeline setup, uploads,...
MeshNodes that describe the position of Meshes, GLTF nodes for GLTFAnimations, or hold references to ...
Oriented Bounding Boxes.
Definition dynamic.frag:14
Important globals for the entire engine and initialization functions that are mainly called on engine...
bool static_mesh
This Mesh is static and must create a BVH or if not it must perform incremental_hull.
size_t * bvh_indices
Indices for the BVH, sorted as the BVH is generated.
AABB aabb
The AABB of the mesh.
Vector tri_aabbs
AABBs for each triangle inside of this Mesh.
Vector nodes
BVHNodes.
Vector tris
The MeshFaces.
Vector vertices
The Points.
A Mesh with geometry data that is either initialized as static or dynamic and split into SubMeshes.
int DEBUG_LINE_COUNT
Definition main.c:282
DebugVertex DEBUG_LINES[DEBUG_LINES_MAX]
Definition main.c:281
float vec3_dot(vec3 a, vec3 b)
Definition mathf.h:322
vec3 vec3_normalize(vec3 v)
Definition mathf.h:46
vec3 vec3_scale(vec3 a, float b)
Definition mathf.h:248
vec3 vec3_sub(vec3 a, vec3 b)
Definition mathf.h:266
float vec4_length(vec4 v)
Definition mathf.h:332
vec3 vec3_add(vec3 a, vec3 b)
Definition mathf.h:286
bool m4_inverse(float out[16], const float m[16])
Definition mathf.h:164
float vec3_length(vec3 v)
Definition mathf.h:328
Mesh functions that modify and initialize Mesh data.
float flux
The total light flux of this node.
int next
The pointer to the next node (either right child or parent's right child) for recursion-less traversa...
int index
The index of the node inside of the array.
int right
Right child.
int parent
Parent.
AABB aabb
The bounding box of all of this node's children.
int left
Left child.
float emissive_flux
The only-emissive flux.
Nodes for the acceleration structures of BVHs.
void aabb_to_vertices(DebugVertex *out, AABB *aabb, vec3 offset)
Transfers an AABB to DebufVertex for a wireframe (GL_LINES).
Definition render.c:475
The main render pass, data GPU uploads, and SSBO management.
float c2
Definition types.h:20
float a0
Definition types.h:20
vec3 normal
Definition types.h:284
float a1
Definition types.h:20
int material_id
Definition types.h:285
float c0
Definition types.h:20
@ B
Definition types.h:26
@ A
Definition types.h:26
@ C
Definition types.h:26
float b1
Definition types.h:263
float x
Definition types.h:12
float b0
Definition types.h:20
float max_z
Definition types.h:39
float b1
Definition types.h:20
size_t mesh_node_idx
Definition types.h:259
float min_x
Definition types.h:37
float max_y
Definition types.h:38
size_t indices[3]
Definition types.h:283
float y
Definition types.h:12
float b2
Definition types.h:264
vec3 pos
Definition types.h:220
float z
Definition types.h:12
size_t count
Definition types.h:209
float min_z
Definition types.h:39
float b0
Definition types.h:262
float min_y
Definition types.h:38
size_t tri
Definition types.h:260
AXIS
Definition types.h:30
@ Y
Definition types.h:31
@ X
Definition types.h:31
@ Z
Definition types.h:31
float b2
Definition types.h:20
void * buffer
Definition types.h:210
float a2
Definition types.h:20
@ HIT_DYNAMIC
Definition types.h:251
@ HIT_STATIC
Definition types.h:250
float c1
Definition types.h:20
float max_x
Definition types.h:37
Definition types.h:218
Definition types.h:20
Definition types.h:21
Definition types.h:12
void init_vector(Vector *v, size_t i, size_t type_size)
Definition utilities.c:74
void calculate_aabb_extents(AABB *aabb)
Definition utilities.c:298
void compute_aabb_from_points(vec3 *points, int point_count, AABB *aabb)
Definition utilities.c:768
float triangle_area(vec3 a, vec3 b, vec3 c)
Definition utilities.c:318
void calculate_aabb_bounds(AABB *aabb)
Definition utilities.c:305
void * vector_expand(Vector *v, size_t i)
Definition utilities.c:49
vec3 mat3_mul_vec3(mat3 m, vec3 v)
Definition utilities.h:498
bool point_in_aabb(vec3 p, AABB *aabb)
Definition utilities.h:214
#define CAST_VEC(vec, type)
Definition utilities.h:134
vec3 mat4_mul_direction(const mat4 m, vec3 v)
Definition utilities.h:323
mat3 mat3_inverse_transpose(mat3 m)
Definition utilities.h:576
vec3 mat4_mul_point(mat4 m, vec3 v)
Definition utilities.h:313
vec3 vec4_to_vec3(vec4 v)
Definition utilities.h:165
mat3 mat3_from_mat4(const mat4 *m)
Definition utilities.h:490
mat4 m4_transpose(mat4 in)
Definition utilities.h:525
#define M_PI
Definition utilities.h:52
vec3 triangle_centroid(vec3 A, vec3 B, vec3 C)
Definition utilities.h:640