14#include "uthash/uthash.h"
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);
112 size_t * index_map = NULL;
122 index_map[i] = entry->
index;
135 for (
int i = 0; i < mesh->
tris.
count; i++)
139 for (
int j = 0; j < 3; j++)
141 size_t i0 = index_map[f->
indices[j]];
142 size_t i1 = index_map[f->
indices[(j+1)%3]];
180 for (
int i = 0; i < mesh->
tris.
count; i++)
197 MeshFace * mf = &fs[tri_indices[i]];
201 if (i == j || tri_indices[i] == tri_indices[j])
208 *idx = tri_indices[j];
226 if (index_map) free(index_map);
236 if (mn->
free)
continue;
238 if (strcmp(mn->
name, name) == 0)
return i;
257 for (
int i = 0; i < faces->
count; i++)
259 for (
int j = 0; j < 3; j++)
267 for (
int k = 0; k < out_verts.
count; k++)
291 *in_verts = out_verts;
306 for (
int i = 0; i < in_faces->
count; i++)
309 for (
int j = 0; j < 3; j++)
315 for (
int k = 0; k < new_points.
count; k++)
340 free(in_vertices->
buffer);
341 *in_vertices = new_points;
352 int * indices =
CAST_VEC(hull_indices,
int);
354 for (
int f = 0; f < hull_indices.
count; f++)
357 MeshFace * face = &faces[indices[f]];
375 for (
int i = 0; i < 3; i++)
378 int * horizon_counts =
CAST_VEC(*counts,
int);
386 for (
int h = 0; h < edges->
count; h++)
390 vec3 a0 = points[edge->
ab[0]];
391 vec3 b0 = points[edge->
ab[1]];
419 vec3 A = points[p_idx];
439 *i = hull_faces->
count-1;
452 Vector * visible_faces_indices,
458 int * indices =
CAST_VEC(*hull_indices,
int);
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++)
466 MeshFace * face = &faces[indices[visible_indices[f]]];
471 int * counts =
CAST_VEC(*horizon_counts,
int);
473 for (
int f = 0; f < visible_faces_indices->
count; f++)
479 for (
int h = 0; h < horizon_edges->
count; h++)
490 visible_faces_indices->
count = 0;
491 horizon_edges->
count = 0;
492 horizon_counts->
count = 0;
560 float lowest = INFINITY;
568 if (points[i].x < lowest) {
569 lowest = points[i].
x;
578 if (points[i].y < lowest) {
579 lowest = points[i].
y;
587 if (points[i].z < lowest) {
588 lowest = points[i].
z;
608 vec3 A = points[lowest_index];
615 size_t a_idx = lowest_index;
622 if (dist > best_dist)
629 if (best_dist <= eps)
650 if (dist > best_dist)
658 if (best_dist <= eps)
681 float dist = fabsf(
vec3_dot(AP, normal));
682 if (dist > best_dist)
691 if (best_dist <= eps)
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);
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);
745 printf(
"RECOMPUTING\n");
759 printf(
"RECOMPUTING\n");
773 printf(
"RECOMPUTING\n");
798 for (
int j = 0; j < 4; j++)
800 for (
int p = 0; p < 3; p++)
803 if (
vec3_equal(points[i], points[hf[j].indices[p]], 0.01f))
806 for (
int l = 0; l < dc; l++)
808 if (
vec3_equal(points[i], points[dup[l]], 0.01f))
820 Vector visible_faces_indices;
827 init_vector(&visible_faces_indices, 0,
sizeof(
int));
830 int * indices =
CAST_VEC(hull_indices,
int);
835 hull_indices.
count = 4;
842 for (
int j = 0; j < 4; j++)
852 int * indices =
CAST_VEC(hull_indices,
int);
853 for (
int f = 0; f < hull_indices.
count; f++)
856 MeshFace * face = &faces[indices[f]];
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++)
872 MeshFace * face = &faces[indices[visible_indices[f]]];
877 int * counts =
CAST_VEC(horizon_counts,
int);
879 for (
int f = 0; f < visible_faces_indices.
count; f++)
886 for (
int h = 0; h < horizon_edges.
count; h++)
897 visible_faces_indices.
count = 0;
898 horizon_edges.
count = 0;
899 horizon_counts.
count = 0;
903 free(visible_faces_indices.
buffer);
904 free(horizon_edges.
buffer);
905 free(horizon_counts.
buffer);
907 int * hi =
CAST_VEC(hull_indices,
int);
915 for (
int i = 0; i < hull_indices.
count; i++)
918 new_hulls[i] = faces[hi[i]];
920 for (
int p = 0; p < 3; p++)
923 bool is_unique =
true;
925 for (
int v = 0; v < unique_vertices.
count; v++)
929 if (
vec3_equal(points[new_hulls[i].indices[p]],
uv[v], 0.001f))
939 *v = points[new_hulls[i].
indices[p]];
951 free(hull_indices.
buffer);
983 for (
int g = 0; g < groups.
count; g++) {
988 bool contiguous_found =
false;
993 MeshFace * tri2 = &tris[indices[j]];
996 if (contiguous_found)
1026 for (
int g = 0; g < groups.
count; g++) {
1029 size_t * points = malloc(group->
indices.
count * 16 *
sizeof(
size_t));
1030 int point_count = 0;
1031 float bottom = INFINITY, top = -INFINITY;
1037 MeshFace * tri = &tris[indices[j]];
1039 points[point_count++] = tri->
indices[
A];
1040 points[point_count++] = tri->
indices[
B];
1041 points[point_count++] = tri->
indices[
C];
1054 if (point_count > 0) {
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))
1074 unique_points[unique_count++] = points[i];
1078 if (unique_count < 3) {
1079 fprintf(stderr,
"Warning: not enough unique points to form a hull.\n");
1082 free(unique_points);
1092 free(unique_points);
1102 for (
int i = 0; i < groups.
count; i++)
1105 if (gs[i].indices.buffer) free(gs[i].indices.buffer);
Vector mesh_nodes
MeshNodes.
Globals GLOBALS
Engine Globals.
Vector adjacent_indices
size_t indices.
Adjacent triangles for each MeshFace on a Mesh.
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.
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)
float vec3_dist(vec3 a, vec3 b)
float vec3_dot(vec3 a, vec3 b)
vec3 vec3_normalize(vec3 v)
vec3 vec3_scale(vec3 a, float b)
vec3 vec3_sub(vec3 a, vec3 b)
vec3 vec3_add(vec3 a, vec3 b)
float vec3_length(vec3 v)
int find_mn_by_name(char name[256])
Finds a Mesh inside of Globals.meshes via string.
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)
void check_horizon_edges(MeshFace *face, Vector vertices, Vector *edges, Vector *counts)
WeldedEntry * welded_table
void incremental_hull(ConvexHull *hull)
Deduplicates vertices.
WeldedVertexKey get_welded_key(vec3 pos, float epsilon)
Quantizes a position to its voxel boundary to be used as a WeldedVertexKey.
EdgePairEntry * edge_pair_table
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)
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...
bool setup_initial_hull_points(ConvexHull *hull)
int pick_lowest_point(ConvexHull *hull)
void build_adjacency_map(Mesh *mesh)
Builds a map of TriangleAdjacency over adjacent MeshFaces on the Mesh.
void compute_mesh_hulls(ConvexHull *hull)
Combines contiguous triangles with same normals into one face.
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.
void deduplicate(Vector *in_verts, Vector *faces)
Deduplicates vertices.
Mesh functions that modify and initialize Mesh data.
bool is_similar_plane(vec3 n1, vec3 n2, vec3 p1, vec3 p2, float epsilon)
void init_vector(Vector *v, size_t i, size_t type_size)
bool vec3_equal(vec3 a, vec3 b, float eps)
void compute_aabb_from_points(vec3 *points, int point_count, AABB *aabb)
float triangle_area(vec3 a, vec3 b, vec3 c)
void compute_hull_faces(vec3 *points, size_t *indices, size_t count, size_t *out_hull, size_t *out_count, vec3 normal)
bool mesh_faces_are_contiguous(MeshFace *a, vec3 *a_verts, MeshFace *b, vec3 *b_verts)
void * vector_expand(Vector *v, size_t i)
#define CAST_VEC(vec, type)
#define REMOVE_FROM_VEC(vec, index, type)
vec3 compute_tri_normal(vec3 a, vec3 b, vec3 c)