Untitled
Loading...
Searching...
No Matches
mesh.c
Go to the documentation of this file.
1
6#include <math.h>
7#include <assert.h>
8#include <stdio.h>
9#include <string.h>
10#include "utilities/types.h"
11#include "utilities/utilities.h"
12#include "utilities/mathf.h"
13#include "core/mesh.h"
14#include "uthash/uthash.h"
15
16typedef struct WeldedVertexKey
17{
18 int32_t x;
19 int32_t y;
20 int32_t z;
22
23typedef struct WeldedEntry
24{
26 size_t index;
27 UT_hash_handle hh;
28
30
31typedef struct EdgePairKey
32{
33 int32_t a;
34 int32_t b;
35
37
38typedef struct EdgePairEntry
39{
42 UT_hash_handle hh;
43
45
53static WeldedVertexKey get_welded_key(vec3 pos, float epsilon);
54
60static void clean_up_hull(Vector * in_vertices, Vector * in_faces);
61
72static void check_face_visibility(vec3 p, Vector vertices, Vector hull_faces, Vector hull_indices, Vector * visible_faces_indices);
73
74static void check_horizon_edges(MeshFace * face, Vector vertices, Vector * edges, Vector * counts);
75static void add_horizon_face_to_hull_faces(size_t p_idx, HorizonEdge e, Vector vertices, vec3 center, Vector * hull_faces, Vector * hull_indices, bool epa);
76static int pick_lowest_point(ConvexHull * hull);
77static bool setup_initial_hull_points(ConvexHull * hull);
78
79// ADJACENCY MAP
80// Builds a map of triangles that are adjacent by storing references per triangle. Uses UTHASH.
81
82static WeldedVertexKey get_welded_key(vec3 pos, float epsilon)
83{
85 key.x = (int32_t)floorf(pos.x / epsilon);
86 key.y = (int32_t)floorf(pos.y / epsilon);
87 key.z = (int32_t)floorf(pos.z / epsilon);
88 return key;
89}
90
91
93static WeldedEntry * welded_table = NULL;
94
95
97{
98
99 if (!mesh->tri_adjacency)
100 {
101
102 mesh->tri_adjacency = calloc(mesh->tris.count, sizeof(TriangleAdjacency));
103 }
104 else
105 {
106 free(mesh->tri_adjacency);
107 mesh->tri_adjacency = calloc(mesh->tris.count, sizeof(TriangleAdjacency));
108 }
109 MeshFace * fs = CAST_VEC(mesh->tris, MeshFace);
110 Point * pts = CAST_VEC(mesh->vertices, Point);
111 WeldedVertexKey * keys = NULL;
112 size_t * index_map = NULL;
113 index_map = calloc(mesh->vertices.count, sizeof(size_t));
114 for (int i = 0; i < mesh->vertices.count; i++)
115 {
116 WeldedVertexKey key = get_welded_key(pts[i].pos, 0.0001f);
117 WeldedEntry * entry = NULL;
118
119 HASH_FIND(hh, welded_table, &key, sizeof(WeldedVertexKey), entry);
120 if (entry)
121 {
122 index_map[i] = entry->index;
123 }
124 else
125 {
126
127 WeldedEntry * z = malloc(sizeof(WeldedEntry));
128 memset(z, 0, sizeof(WeldedEntry));
129 z->key = key;
130 z->index = i;
131 index_map[i] = i;
132 HASH_ADD(hh, welded_table, key, sizeof(WeldedVertexKey), z);
133 }
134 }
135 for (int i = 0; i < mesh->tris.count; i++)
136 {
137
138 MeshFace * f = &fs[i];
139 for (int j = 0; j < 3; j++)
140 {
141 size_t i0 = index_map[f->indices[j]];
142 size_t i1 = index_map[f->indices[(j+1)%3]];
143
144 EdgePairKey ep;
145 if (i0 < i1)
146 {
147 ep = (EdgePairKey){i0, i1};
148 }
149 else
150 {
151 ep = (EdgePairKey){i1, i0};
152
153 }
154 EdgePairEntry * epe = NULL;
155 HASH_FIND(hh, edge_pair_table, &ep, sizeof(EdgePairKey), epe);
156 if (epe)
157 {
158 // add on to entry
159 size_t * v = vector_expand(&epe->tris, 1);
160 *v = i;
161
162 }
163 else
164 {
165 // add entry
166 EdgePairEntry * z = malloc(sizeof(EdgePairEntry));
167 memset(z, 0, sizeof(EdgePairEntry));
168 z->key = ep;
169 init_vector(&z->tris, 1, sizeof(size_t));
170 size_t * v = CAST_VEC(z->tris, size_t);
171 *v = i;
172 HASH_ADD(hh, edge_pair_table, key, sizeof(EdgePairKey), z);
173 }
174
175 }
176
177
178 }
179
180 for (int i = 0; i < mesh->tris.count; i++)
181 {
182
183 init_vector(&mesh->tri_adjacency[i].adjacent_indices, 0, sizeof(size_t));
184
185 }
186
187 EdgePairEntry * s;
188 EdgePairEntry * tmp;
189
190 HASH_ITER(hh, edge_pair_table, s, tmp){
191
192
193 size_t * tri_indices = CAST_VEC(s->tris, size_t);
194 for (int i = 0; i < s->tris.count; i++)
195 {
196
197 MeshFace * mf = &fs[tri_indices[i]];
198 for (int j = 0; j < s->tris.count; j++)
199 {
200
201 if (i == j || tri_indices[i] == tri_indices[j])
202 {
203 continue;
204 }
205
206
207 size_t * idx = vector_expand(&mesh->tri_adjacency[tri_indices[i]].adjacent_indices, 1);
208 *idx = tri_indices[j];
209 }
210 }
211
212
213 if (s->tris.buffer) free(s->tris.buffer);
214 HASH_DEL(edge_pair_table, s);
215 free(s);
216 }
217
218 WeldedEntry * s0;
219 WeldedEntry * tmp0;
220 HASH_ITER(hh, welded_table, s0, tmp0){
221
222
223 HASH_DEL(welded_table, s0);
224 free(s0);
225 }
226 if (index_map) free(index_map);
227}
228
229int find_mn_by_name(char name[256])
230{
231
233 for (int i = 0; i < GLOBALS.mesh_nodes.count; i++)
234 {
235 MeshNode * mn = &mns[i];
236 if (mn->free) continue;
237
238 if (strcmp(mn->name, name) == 0) return i;
239
240 }
241 return -1;
242
243
244}
245
246
247
248void deduplicate(Vector * in_verts, Vector * faces)
249{
250
251 MeshFace * tris = CAST_VEC(*faces, MeshFace);
252 vec3 * in_pts = CAST_VEC(*in_verts, vec3);
253 Vector out_verts;
254 init_vector(&out_verts, 0, sizeof(vec3));
255
256
257 for (int i = 0; i < faces->count; i++)
258 {
259 for (int j = 0; j < 3; j++)
260 {
261
262 MeshFace * f = &tris[i];
263 vec3 pt = in_pts[f->indices[j]];
264 bool unique = true;
265
266 vec3 * verts = CAST_VEC(out_verts, vec3);
267 for (int k = 0; k < out_verts.count; k++)
268 {
269 vec3 v = verts[k];
270 if (vec3_equal(pt, v, 0.01f))
271 {
272 unique = false;
273 f->indices[j] = k;
274 break;
275 }
276 }
277
278 if (unique)
279 {
280 vec3 * point = vector_expand(&out_verts, 1);
281 *point = pt;
282
283 f->indices[j] = out_verts.count-1;
284
285 }
286 }
287
288 }
289
290 free(in_verts->buffer);
291 *in_verts = out_verts;
292}
293
294
295
296// remove extraneous points from hull that aren't referenced by faces
297static void clean_up_hull(Vector * in_vertices, Vector * in_faces)
298{
299
300 deduplicate(in_vertices, in_faces);
301
302 Vector new_points;
303 init_vector(&new_points, 0, sizeof(vec3));
304 MeshFace * faces = CAST_VEC(*in_faces, MeshFace);
305 vec3 * old_vertices = CAST_VEC(*in_vertices, vec3);
306 for (int i = 0; i < in_faces->count; i++)
307 {
308 MeshFace * face = &faces[i];
309 for (int j = 0; j < 3; j++)
310 {
311 vec3 p = old_vertices[face->indices[j]];
312
313 bool is_new = true;
314
315 for (int k = 0; k < new_points.count; k++)
316 {
317 vec3 * np = CAST_VEC(new_points, vec3);
318 if (vec3_equal(p, np[k], 0.01f))
319 {
320 is_new = false;
321
322 face->indices[j] = k;
323 break;
324
325 }
326 }
327
328 if (is_new)
329 {
330 vec3 * new_pt = vector_expand(&new_points, 1);
331 *new_pt = p;
332 face->indices[j] = new_points.count - 1;
333 }
334
335
336 }
337
338 }
339 // printf("%p\n", hull->vertices.buffer);
340 free(in_vertices->buffer);
341 *in_vertices = new_points;
342
343}
344
345
346
347
348// INCREMENTAL HULL
349static void check_face_visibility(vec3 p, Vector vertices, Vector hull_faces, Vector hull_indices, Vector * visible_faces_indices)
350{
351 MeshFace * faces = CAST_VEC(hull_faces, MeshFace);
352 int * indices = CAST_VEC(hull_indices, int);
353 vec3 * points = CAST_VEC(vertices, vec3);
354 for (int f = 0; f < hull_indices.count; f++)
355 {
356
357 MeshFace * face = &faces[indices[f]];
358 float d = vec3_dot(vec3_sub(p, points[face->indices[0]]), face->normal);
359 if ((d) > 0.0f)
360 {
361 int * vfi = vector_expand(visible_faces_indices, 1);
362 *vfi = f;
363 }
364
365 }
366}
367
368
369
370static void check_horizon_edges(MeshFace * face, Vector vertices, Vector * edges, Vector * counts)
371{
372
373 vec3 * points = CAST_VEC(vertices, vec3);
374 float eps = 0.001f;
375 for (int i = 0; i < 3; i++)
376 {
377 HorizonEdge * horizon_edges = CAST_VEC(*edges, HorizonEdge);
378 int * horizon_counts = CAST_VEC(*counts, int);
379 HorizonEdge c;
380 c.ab[0] = face->indices[i];
381 vec3 a = points[face->indices[i]];
382 c.ab[1] = face->indices[(i+1) % 3];
383 vec3 b = points[face->indices[(i+1) % 3]];
384 bool found = false;
385
386 for (int h = 0; h < edges->count; h++)
387 {
388
389 HorizonEdge * edge = &horizon_edges[h];
390 vec3 a0 = points[edge->ab[0]];
391 vec3 b0 = points[edge->ab[1]];
392
393 // It may be correct to only check the opposite orientation (a == b, b == a)
394 if ((vec3_equal(a0, a, eps) && vec3_equal(b0, b, eps) ||
395 (vec3_equal(b0, a, eps) && vec3_equal(a0, b, eps))))
396 {
397 horizon_counts[h]++;
398 found = true;
399 }
400
401 }
402 if (found == false)
403 {
404 HorizonEdge * ep = vector_expand(edges, 1);
405 *ep = c;
406 int * count = vector_expand(counts, 1);
407 *count = 1;
408 }
409 }
410
411}
412
413
414
415static void add_horizon_face_to_hull_faces(size_t p_idx, HorizonEdge e, Vector vertices, vec3 center, Vector * hull_faces, Vector * hull_indices, bool epa)
416{
417
418 vec3 * points = CAST_VEC(vertices, vec3);
419 vec3 A = points[p_idx];
420 vec3 B = points[e.ab[0]];
421 vec3 C = points[e.ab[1]];
422
423 MeshFace * f = vector_expand(hull_faces, 1);
424
425 f->indices[0] = p_idx;
426 f->indices[1] = e.ab[0];
427 f->indices[2] = e.ab[1];
428 f->normal = compute_tri_normal(A, B, C);
429 if (vec3_dot(vec3_sub(center, A), f->normal) > 0)
430 {
431
432 f->indices[0] = e.ab[0];
433 f->indices[1] = p_idx;
434 f->normal = compute_tri_normal(B, A, C);
435 }
436 assert(vec3_dot(vec3_sub(center, A), f->normal) <= 0);
437
438 int * i = vector_expand(hull_indices, 1);
439 *i = hull_faces->count-1;
440}
441
442
443static void expand_hull
444 (
445 vec3 p,
446 int index,
447 Vector * vertices,
448 Vector * hull_faces,
449 Vector * hull_indices,
450 Vector * horizon_edges,
451 Vector * horizon_counts,
452 Vector * visible_faces_indices,
453 vec3 centroid
454 )
455{
456
457 MeshFace * faces = CAST_VEC(*hull_faces, MeshFace);
458 int * indices = CAST_VEC(*hull_indices, int);
459
460 check_face_visibility(p, *vertices, *hull_faces, *hull_indices, visible_faces_indices);
461
462 if (visible_faces_indices->count <= 0) return;
463 int * visible_indices = CAST_VEC(*visible_faces_indices, int);
464 for (int f = 0; f < visible_faces_indices->count; f++)
465 {
466 MeshFace * face = &faces[indices[visible_indices[f]]];
467 check_horizon_edges(face, *vertices, horizon_edges, horizon_counts);
468 }
469
470 // delete visible faces from master list
471 int * counts = CAST_VEC(*horizon_counts, int);
472
473 for (int f = 0; f < visible_faces_indices->count; f++)
474 {
475 REMOVE_FROM_VEC(hull_indices, visible_indices[f] - f, int);
476 }
477
478 HorizonEdge * edges = CAST_VEC(*horizon_edges, HorizonEdge);
479 for (int h = 0; h < horizon_edges->count; h++)
480 {
481 HorizonEdge * edge = &edges[h];
482 if (counts[h] == 1)
483 {
484 // connect p to horizon edges
485 add_horizon_face_to_hull_faces(index, *edge, *vertices, centroid, hull_faces, hull_indices, true);
486
487 }
488 }
489
490 visible_faces_indices->count = 0;
491 horizon_edges->count = 0;
492 horizon_counts->count = 0;
493
494}
495
496
497
498// notes on incremental hull
499// start with a point cloud of deduplicated vertices
500// mesh must be convex already (use a decomposition algo)
501// before adding new face, check length(n) < eps, if so skip (degenerate faces)
502
503// start with 4 points:
504// pick a random point
505// find furthest point from that point
506// find futhest point from that edge:
507// ab = B - A
508// ap = P - A
509// dist = length(cross(ap, ab)) / length(ab)
510// if cross(B-A,C-A) is zero, there is no triangle
511// if d < eps always, all points are colinear, this is 2D.
512
513// find furthest point from that triangle:
514 // a = reference point
515 // n = normalize(cross(B-A, C-A))
516 // dist = fabsf(dot(P-A,n))
517 // if (dist == 0) always, hull is degenerate
518// for each face:
519 // compute normal
520 // find tetrahedron vert that is not on the face (ABC would be D)
521 // d = dot(D-A, n)
522 // if d > 0, the normal must be flipped, swap two vertices
523
524// now we have a tetrahedron, compute center
525 // center = (A+B+C+D) * 0.25f
526
527// for each point:
528 // determine visibility:
529 // for each face:
530 // d = (dot(P-A, face normal))
531 // test fabsf(d) < eps
532 // if (d > 0)
533 // add to visible faces
534 // if (d < 0)
535 // not visible
536 // if (d == 0)
537 // point lies on plane
538
539 // find horizon edges:
540 // for each visible face:
541 // count edges that are shared between visible faces
542 // if count == 1, this is a horizon edge
543 // delete visible faces from master list
544 // connect P to each horizon edge and emit new faces to master list
545 // for each new face, compute normal and verify it faces correctly:
546 // if (dot(center - face_vertex, n) > 0) flip normal (swap two vertices)
547
548
549
550
551
553{
554 AXIS longest;
555 if (hull->aabb.extents.x >= hull->aabb.extents.y && hull->aabb.extents.x >= hull->aabb.extents.z) longest = X;
556 if (hull->aabb.extents.y >= hull->aabb.extents.x && hull->aabb.extents.y >= hull->aabb.extents.z) longest = Y;
557 if (hull->aabb.extents.z >= hull->aabb.extents.x && hull->aabb.extents.z >= hull->aabb.extents.y) longest = Z;
558
559 int index = 0;
560 float lowest = INFINITY;
561 vec3 * points = CAST_VEC(hull->vertices, vec3);
562 switch(longest)
563 {
564 case X:
565 {
566 for (int i = 0; i < hull->vertices.count; i++)
567 {
568 if (points[i].x < lowest) {
569 lowest = points[i].x;
570 index = i;
571 }
572 }
573 }
574 break;
575 case Y:
576 for (int i = 0; i < hull->vertices.count; i++)
577 {
578 if (points[i].y < lowest) {
579 lowest = points[i].y;
580 index = i;
581 }
582 }
583 break;
584 case Z:
585 for (int i = 0; i < hull->vertices.count; i++)
586 {
587 if (points[i].z < lowest) {
588 lowest = points[i].z;
589 index = i;
590 }
591 }
592 break;
593 }
594
595 return index;
596
597}
598
599
600
602{
603
604 int lowest_index = pick_lowest_point(hull);
605 vec3 * points = CAST_VEC(hull->vertices, vec3);
606 printf("POINTS: %p %zu\n", points, hull->vertices.count);
607 // ConvexHull * hull = &mesh->hull;
608 vec3 A = points[lowest_index];
609 vec3 B; vec3 C; vec3 D;
610
611
612 float eps = 0.001f;
613 float best_dist = 0;
614 vec3 best;
615 size_t a_idx = lowest_index;
616 size_t b_idx = 0;
617 size_t c_idx = 0;
618 size_t d_idx = 0;
619 for (int i = 0; i < hull->vertices.count; i++)
620 {
621 float dist = fabsf(vec3_dist(A, points[i]));
622 if (dist > best_dist)
623 {
624 best_dist = dist;
625 best = points[i];
626 b_idx = i;
627 }
628 }
629 if (best_dist <= eps)
630 {
631 printf("B\n");
632 return false;
633 }
634 else
635 {
636
637 B = best;
638 }
639
640
641 vec3 AB = vec3_sub(B, A);
642 float ab_len = vec3_length(AB);
643 best_dist = 0;
644
645 for (int i = 0; i < hull->vertices.count; i++)
646 {
647 vec3 P = points[i];
648 vec3 AP = vec3_sub(P, A);
649 float dist = vec3_length(vec3_cross(AP, AB)) / ab_len;
650 if (dist > best_dist)
651 {
652 best_dist = dist;
653 best = P;
654 c_idx = i;
655 }
656
657 }
658 if (best_dist <= eps)
659 {
660 return false;
661 }
662 else
663 {
664
665 C = best;
666 }
667
668 if (fabsf(vec3_length(vec3_cross(vec3_sub(B, A), vec3_sub(C, A)))) <= 0.001f)
669 {
670 return false;
671 }
672
673
675 best_dist = 0;
676
677 for (int i = 0; i < hull->vertices.count; i++)
678 {
679 vec3 P = points[i];
680 vec3 AP = vec3_sub(P, A);
681 float dist = fabsf(vec3_dot(AP, normal));
682 if (dist > best_dist)
683 {
684 best_dist = dist;
685 best = P;
686 d_idx = i;
687 }
688
689 }
690
691 if (best_dist <= eps)
692 {
693 return false;
694 }
695 else
696 {
697
698 D = best;
699 }
700
701
702 printf("A: %f %f %f B: %f %f %f C: %f %f %f D: %f %f %f\n", A.x, A.y, A.z, B.x, B.y, B.z, C.x, C.y, C.z, D.x, D.y, D.z);
703 init_vector(&hull->faces, 0, sizeof(MeshFace));
704
705 vector_expand(&hull->faces, 4);
706 hull->faces.count = 4;
707 MeshFace * faces = CAST_VEC(hull->faces, MeshFace);
708
709 // vec3 AB = vec3_sub(B, A);
710 vec3 AC = vec3_sub(C, A);
711 vec3 AD = vec3_sub(D, A);
712 vec3 BC = vec3_sub(C, B);
713 vec3 BD = vec3_sub(D, B);
714 vec3 CD = vec3_sub(D, C);
715 vec3 DA = vec3_sub(A, D);
716 vec3 DC = vec3_sub(C, D);
717
718 faces[0].indices[0] = a_idx;
719 faces[0].indices[1] = b_idx;
720 faces[0].indices[2] = c_idx;
721
722 vec3 center = vec3_add(vec3_add(vec3_add(A, B), C), D);
723 center = vec3_scale(center, 0.25f);
724 hull->centroid = center;
725 printf("CENTER: %f %f %f\n", center.x, center.y, center.z);
726 printf("A: %f %f %f B: %f %f %f C: %f %f %f D: %f %f %f\n", A.x, A.y, A.z, B.x, B.y, B.z, C.x, C.y, C.z, D.x, D.y, D.z);
727 faces[0].normal = compute_tri_normal(A, B, C);
728 if (vec3_dot(vec3_sub(D, A), faces[0].normal) > 0)
729 {
730 faces[0].indices[0] = b_idx;
731 faces[0].indices[1] = a_idx;
732 faces[0].normal = compute_tri_normal(B, A, C);
733 }
734 faces[1].indices[0] = b_idx;
735 faces[1].indices[1] = d_idx;
736 faces[1].indices[2] = c_idx;
737 faces[1].normal = compute_tri_normal(B, D, C);
738 if (vec3_dot(vec3_sub(A, B), faces[1].normal) > 0)
739 {
740 faces[1].indices[0] = d_idx;
741 faces[1].indices[1] = b_idx;
742 faces[1].normal = compute_tri_normal(D, B, C);
743 if (vec3_dot(vec3_sub(A, B), faces[1].normal) > 0)
744 {
745 printf("RECOMPUTING\n");
746 }
747 }
748 faces[2].indices[0] = d_idx;
749 faces[2].indices[1] = a_idx;
750 faces[2].indices[2] = c_idx;
751 faces[2].normal = compute_tri_normal(D, A, C);
752 if (vec3_dot(vec3_sub(B, D), faces[2].normal) > 0)
753 {
754 faces[2].indices[0] = a_idx;
755 faces[2].indices[1] = d_idx;
756 faces[2].normal = compute_tri_normal(A, D, C);
757 if (vec3_dot(vec3_sub(B, D), faces[2].normal) > 0)
758 {
759 printf("RECOMPUTING\n");
760 }
761 }
762 faces[3].indices[0] = a_idx;
763 faces[3].indices[1] = b_idx;
764 faces[3].indices[2] = d_idx;
765 faces[3].normal = compute_tri_normal(A, B, D);
766 if (vec3_dot(vec3_sub(C, A), faces[3].normal) > 0)
767 {
768 faces[3].indices[0] = b_idx;
769 faces[3].indices[1] = a_idx;
770 faces[3].normal = compute_tri_normal(B, A, D);
771 if (vec3_dot(vec3_sub(C, A), faces[3].normal) > 0)
772 {
773 printf("RECOMPUTING\n");
774 }
775 }
776 return true;
777
778}
779
780
781
783{
784
785 // Simplex s;
786 // decompose(mesh);
787
788 if (!setup_initial_hull_points(hull)) return;
789
790 printf("SETUP\n");
791
792 vec3 * points = CAST_VEC(hull->vertices, vec3);
793 int dup[4];
794 int dc = 0;
795 MeshFace * hf = CAST_VEC(hull->faces, MeshFace);
796 for (int i = 0; i < hull->vertices.count; i++)
797 {
798 for (int j = 0; j < 4; j++)
799 {
800 for (int p = 0; p < 3; p++)
801 {
802
803 if (vec3_equal(points[i], points[hf[j].indices[p]], 0.01f))
804 {
805 bool skip = false;
806 for (int l = 0; l < dc; l++)
807 {
808 if (vec3_equal(points[i], points[dup[l]], 0.01f))
809 {
810 skip = true;
811 }
812 }
813 if (!skip)
814 dup[dc++] = i;
815 }
816 }
817 }
818 }
819
820 Vector visible_faces_indices;
821 Vector horizon_edges;
822 Vector horizon_counts;
823 Vector hull_indices;
824
825 init_vector(&horizon_edges, 0, sizeof(HorizonEdge));
826 init_vector(&horizon_counts, 0, sizeof(int));
827 init_vector(&visible_faces_indices, 0, sizeof(int));
828 init_vector(&hull_indices, 0, sizeof(int));
829 vector_expand(&hull_indices, 4);
830 int * indices = CAST_VEC(hull_indices, int);
831 indices[0] = 0;
832 indices[1] = 1;
833 indices[2] = 2;
834 indices[3] = 3;
835 hull_indices.count = 4;
836
837
838 for (int i = 0; i < hull->vertices.count; i++)
839 {
840 bool di = false;
841 vec3 p = points[i];
842 for (int j = 0; j < 4; j++)
843 {
844 if (dup[j] == i)
845 {
846
847 di = true;
848 }
849 }
850 if (di) continue;
851 MeshFace * faces = CAST_VEC(hull->faces, MeshFace);
852 int * indices = CAST_VEC(hull_indices, int);
853 for (int f = 0; f < hull_indices.count; f++)
854 {
855
856 MeshFace * face = &faces[indices[f]];
857 float d = vec3_dot(vec3_sub(p, points[face->indices[0]]), face->normal);
858 // if ((d) > 0.01f)
859 if ((d) > 0.0f)
860 {
861 int * vfi = vector_expand(&visible_faces_indices, 1);
862 *vfi = f;
863 }
864
865 }
866 // check_face_visibility(p, mesh->hull.vertices, mesh->hull.faces, hull_indices, &visible_faces_indices);
867
868 if (visible_faces_indices.count <= 0) continue;
869 int * visible_indices = CAST_VEC(visible_faces_indices, int);
870 for (int f = 0; f < visible_faces_indices.count; f++)
871 {
872 MeshFace * face = &faces[indices[visible_indices[f]]];
873 check_horizon_edges(face, hull->vertices, &horizon_edges, &horizon_counts);
874 }
875
876 // delete visible faces from master list
877 int * counts = CAST_VEC(horizon_counts, int);
878
879 for (int f = 0; f < visible_faces_indices.count; f++)
880 {
881 // remove_int_from_vec(&hull_indices, visible_indices[f] - f);
882 REMOVE_FROM_VEC(&hull_indices, visible_indices[f] - f, int);
883 }
884
885 HorizonEdge * edges = CAST_VEC(horizon_edges, HorizonEdge);
886 for (int h = 0; h < horizon_edges.count; h++)
887 {
888 HorizonEdge * edge = &edges[h];
889 if (counts[h] == 1)
890 {
891 // connect p to horizon edges
892 add_horizon_face_to_hull_faces(i, *edge, hull->vertices, hull->centroid, &hull->faces, &hull_indices, false);
893
894 }
895 }
896
897 visible_faces_indices.count = 0;
898 horizon_edges.count = 0;
899 horizon_counts.count = 0;
900 // expand_hull(p, i, &mesh->hull.vertices, &mesh->hull.faces, &hull_indices, &horizon_edges, &horizon_counts, &visible_faces_indices, mesh->hull.centroid);
901
902 }
903 free(visible_faces_indices.buffer);
904 free(horizon_edges.buffer);
905 free(horizon_counts.buffer);
906
907 int * hi = CAST_VEC(hull_indices, int);
908
909 MeshFace * new_hulls = malloc(hull_indices.count * sizeof(MeshFace));
910
911 MeshFace * faces = CAST_VEC(hull->faces, MeshFace);
912 Vector unique_vertices;
913 init_vector(&unique_vertices, 0, sizeof(vec3));
914
915 for (int i = 0; i < hull_indices.count; i++)
916 {
917
918 new_hulls[i] = faces[hi[i]];
919
920 for (int p = 0; p < 3; p++)
921 {
922
923 bool is_unique = true;
924 vec3 * uv = CAST_VEC(unique_vertices, vec3);
925 for (int v = 0; v < unique_vertices.count; v++)
926 {
927
928
929 if (vec3_equal(points[new_hulls[i].indices[p]], uv[v], 0.001f))
930 {
931 is_unique = false;
932 new_hulls[i].indices[p] = v;
933 break;
934 }
935 }
936 if (is_unique)
937 {
938 vec3 * v = vector_expand(&unique_vertices, 1);
939 *v = points[new_hulls[i].indices[p]];
940 new_hulls[i].indices[p] = unique_vertices.count-1;
941 }
942 }
943
944 }
945 MeshFace * old_hulls = hull->faces.buffer;
946 hull->faces.buffer = new_hulls;
947 free(old_hulls);
948 hull->faces.count = hull_indices.count;
949 hull->faces.capacity = hull_indices.capacity;
950
951 free(hull_indices.buffer);
952 free(hull->vertices.buffer);
953
954 hull->vertices = unique_vertices;
955 clean_up_hull(&hull->vertices, &hull->faces);
957
958}
959
960
961
963{
964
965 Vector groups;
966 init_vector(&groups, 0, sizeof(TriangleGroup));
967 init_vector(&hull->hull_faces, 0, sizeof(HullFace));
968
969 MeshFace * tris = CAST_VEC(hull->faces, MeshFace);
970 vec3 * pts = CAST_VEC(hull->vertices, vec3);
971
972
973 for (int i = 0; i < hull->faces.count; i++){
974
975 MeshFace * tri = &tris[i];
976
977 if (triangle_area(pts[tri->indices[A]], pts[tri->indices[B]], pts[tri->indices[C]]) < 0.001f) continue;
978
979 bool added = false;
980
981 TriangleGroup * tri_groups = CAST_VEC(groups, TriangleGroup);
982
983 for (int g = 0; g < groups.count; g++) {
984
985 TriangleGroup * group = &tri_groups[g];
986
987 if (is_similar_plane(tri->normal, group->normal, pts[tri->indices[A]], group->ref_point, 0.001f)) {
988 bool contiguous_found = false;
989 size_t * indices = CAST_VEC(group->indices, size_t);
990 for (int j = 0; j < group->indices.count; j++)
991 {
992
993 MeshFace * tri2 = &tris[indices[j]];
994 if (mesh_faces_are_contiguous(tri, pts, tri2, pts)) contiguous_found = true;
995 }
996 if (contiguous_found)
997 {
998 size_t * index = vector_expand(&group->indices, 1);
999 *index = i;
1000 added = true;
1001 break;
1002 }
1003
1004
1005 }
1006
1007 }
1008
1009 if (!added) {
1010
1011 TriangleGroup * group = vector_expand(&groups, 1);
1012
1013 init_vector(&group->indices, 0, sizeof(size_t));
1014 group->normal = tri->normal;
1015
1016 group->ref_point = pts[tri->indices[A]];
1017
1018
1019 size_t * index = vector_expand(&group->indices, 1);
1020 *index = i;
1021
1022 }
1023 }
1024
1025 TriangleGroup * tri_groups = CAST_VEC(groups, TriangleGroup);
1026 for (int g = 0; g < groups.count; g++) {
1027
1028 TriangleGroup * group = &tri_groups[g];
1029 size_t * points = malloc(group->indices.count * 16 * sizeof(size_t));
1030 int point_count = 0;
1031 float bottom = INFINITY, top = -INFINITY;
1032 size_t * indices = CAST_VEC(group->indices, size_t);
1033
1034
1035 for (int j = 0; j < group->indices.count; j++) {
1036
1037 MeshFace * tri = &tris[indices[j]];
1038
1039 points[point_count++] = tri->indices[A];
1040 points[point_count++] = tri->indices[B];
1041 points[point_count++] = tri->indices[C];
1042
1043
1044 // printf("TRI: %zu\n", indices[j]);
1045
1046 if (pts[tri->indices[A]].z > top) top = pts[tri->indices[A]].z;
1047 if (pts[tri->indices[B]].z > top) top = pts[tri->indices[B]].z;
1048 if (pts[tri->indices[C]].z > top) top = pts[tri->indices[C]].z;
1049 if (pts[tri->indices[A]].z < bottom) bottom = pts[tri->indices[A]].z;
1050 if (pts[tri->indices[B]].z < bottom) bottom = pts[tri->indices[B]].z;
1051 if (pts[tri->indices[C]].z < bottom) bottom = pts[tri->indices[C]].z;
1052 }
1053
1054 if (point_count > 0) {
1055 // if (all_colinear(points, point_count)) {
1056 // fprintf(stderr, "Warning: all points colinear, skipping hull.\n");
1057 // free(points);
1058 // continue;
1059 // }
1060
1061 size_t * unique_points = malloc(point_count * sizeof(size_t));
1062 int unique_count = 0;
1063 for (int i = 0; i < point_count; i++) {
1064 bool exists = false;
1065 for (int j = 0; j < unique_count; j++) {
1066 if (vec3_equal(pts[points[i]], pts[unique_points[j]], 0.001f))
1067 {
1068
1069 exists = true;
1070 break;
1071 }
1072 }
1073 if (!exists) {
1074 unique_points[unique_count++] = points[i];
1075 }
1076 }
1077
1078 if (unique_count < 3) {
1079 fprintf(stderr, "Warning: not enough unique points to form a hull.\n");
1080
1081
1082 free(unique_points);
1083 free(points);
1084 continue;
1085 }
1086
1087 HullFace * hf = vector_expand(&hull->hull_faces, 1);
1088 hf->count = 0;
1089 hf->normal = group->normal;
1090 compute_hull_faces(pts, unique_points, unique_count, hf->indices, &hf->count, group->normal);
1091
1092 free(unique_points);
1093 }
1094 free(points);
1095 }
1096
1097 // printf("GROUPS: %zu\n", groups.count);
1098 TriangleGroup * gs = (TriangleGroup*)groups.buffer;
1099 if (groups.buffer)
1100 {
1101
1102 for (int i = 0; i < groups.count; i++)
1103 {
1104 // TriangleGroup * group = &(CAST_VEC(groups, TriangleGroup))[i];
1105 if (gs[i].indices.buffer) free(gs[i].indices.buffer);
1106 // free(group->indices.buffer);
1107 }
1108 free(groups.buffer);
1109 }
1110
1111}
1112
Vector mesh_nodes
MeshNodes.
Globals GLOBALS
Engine Globals.
Definition main.c:310
Vector adjacent_indices
size_t indices.
Adjacent triangles for each MeshFace on a Mesh.
in vec2 uv
Vector hull_faces
HullFaces that are generated after incremental_hull() that combine contiguous triangles into singular...
Vector vertices
Points that initially copy the Mesh vertices but then are deduplicated and modified in incremental_hu...
vec3 normal
The group's normal.
Vector faces
MeshFaces that initially copy the Mesh faces but then are modified in incremental_hull().
vec3 centroid
The center of the hull.
AABB aabb
The bounding box of the hull.
Vector indices
size_t indices of each MeshFace that indexes into ConvexHull.faces.
vec3 ref_point
A point on the plane.
CollisionPoints epa(CollisionData a_cd, CollisionData b_cd, mat4 a_mat, mat4 b_mat, mat4 a_inv, mat4 b_inv, Simplex *s, EPAWorkspace *EW)
The Expanding Polytope Algorithm - expands a polytope in a loop as it becomes a polyhedron.
Definition GJK.c:452
Convex Hulls that are generated via incremental hull for non-static meshes.
Groups of contiguous triangles with the same plane that are combined via jarvis marching.
char name[256]
The name generated on loading from file.
bool free
If the MeshNode can be replaced.
MeshNodes that describe the position of Meshes, GLTF nodes for GLTFAnimations, or hold references to ...
TriangleAdjacency * tri_adjacency
Adjacent triangles allocated per MeshFace.
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.
vec3 vec3_cross(vec3 a, vec3 b)
Definition mathf.h:80
float vec3_dist(vec3 a, vec3 b)
Definition mathf.h:318
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
vec3 vec3_add(vec3 a, vec3 b)
Definition mathf.h:286
float vec3_length(vec3 v)
Definition mathf.h:328
int find_mn_by_name(char name[256])
Finds a Mesh inside of Globals.meshes via string.
Definition mesh.c:229
int32_t b
Definition mesh.c:34
int32_t x
Definition mesh.c:18
void add_horizon_face_to_hull_faces(size_t p_idx, HorizonEdge e, Vector vertices, vec3 center, Vector *hull_faces, Vector *hull_indices, bool epa)
Definition mesh.c:415
UT_hash_handle hh
Definition mesh.c:42
void check_horizon_edges(MeshFace *face, Vector vertices, Vector *edges, Vector *counts)
Definition mesh.c:370
int32_t y
Definition mesh.c:19
WeldedEntry * welded_table
Definition mesh.c:93
void incremental_hull(ConvexHull *hull)
Deduplicates vertices.
Definition mesh.c:782
WeldedVertexKey get_welded_key(vec3 pos, float epsilon)
Quantizes a position to its voxel boundary to be used as a WeldedVertexKey.
Definition mesh.c:82
EdgePairEntry * edge_pair_table
Definition mesh.c:92
int32_t z
Definition mesh.c:20
size_t index
Definition mesh.c:26
void expand_hull(vec3 p, int index, Vector *vertices, Vector *hull_faces, Vector *hull_indices, Vector *horizon_edges, Vector *horizon_counts, Vector *visible_faces_indices, vec3 centroid)
Definition mesh.c:444
void clean_up_hull(Vector *in_vertices, Vector *in_faces)
Removes extraneous points from a ConvexHull that aren't referenced by its HullFaces after running inc...
Definition mesh.c:297
bool setup_initial_hull_points(ConvexHull *hull)
Definition mesh.c:601
Vector tris
Definition mesh.c:41
int pick_lowest_point(ConvexHull *hull)
Definition mesh.c:552
EdgePairKey key
Definition mesh.c:40
void build_adjacency_map(Mesh *mesh)
Builds a map of TriangleAdjacency over adjacent MeshFaces on the Mesh.
Definition mesh.c:96
void compute_mesh_hulls(ConvexHull *hull)
Combines contiguous triangles with same normals into one face.
Definition mesh.c:962
WeldedVertexKey key
Definition mesh.c:25
void check_face_visibility(vec3 p, Vector vertices, Vector hull_faces, Vector hull_indices, Vector *visible_faces_indices)
Checks what faces are visible (facing) the given point.
Definition mesh.c:349
int32_t a
Definition mesh.c:33
UT_hash_handle hh
Definition mesh.c:27
void deduplicate(Vector *in_verts, Vector *faces)
Deduplicates vertices.
Definition mesh.c:248
Definition mesh.c:39
Definition mesh.c:24
Mesh functions that modify and initialize Mesh data.
vec3 normal
Definition types.h:284
int ab[2]
Definition types.h:243
@ B
Definition types.h:26
@ A
Definition types.h:26
@ C
Definition types.h:26
@ D
Definition types.h:26
float x
Definition types.h:12
size_t indices[3]
Definition types.h:283
float y
Definition types.h:12
float z
Definition types.h:12
size_t count
Definition types.h:209
vec3 normal
Definition types.h:324
AXIS
Definition types.h:30
@ Y
Definition types.h:31
@ X
Definition types.h:31
@ Z
Definition types.h:31
size_t count
Definition types.h:323
size_t capacity
Definition types.h:209
void * buffer
Definition types.h:210
size_t indices[64]
Definition types.h:322
Definition types.h:218
Definition types.h:12
bool is_similar_plane(vec3 n1, vec3 n2, vec3 p1, vec3 p2, float epsilon)
Definition utilities.c:330
void init_vector(Vector *v, size_t i, size_t type_size)
Definition utilities.c:74
bool vec3_equal(vec3 a, vec3 b, float eps)
Definition utilities.c:541
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 compute_hull_faces(vec3 *points, size_t *indices, size_t count, size_t *out_hull, size_t *out_count, vec3 normal)
Definition utilities.c:718
bool mesh_faces_are_contiguous(MeshFace *a, vec3 *a_verts, MeshFace *b, vec3 *b_verts)
Definition utilities.c:578
void * vector_expand(Vector *v, size_t i)
Definition utilities.c:49
#define CAST_VEC(vec, type)
Definition utilities.h:134
#define REMOVE_FROM_VEC(vec, index, type)
Definition utilities.h:276
vec3 compute_tri_normal(vec3 a, vec3 b, vec3 c)
Definition utilities.h:254