summaryrefslogtreecommitdiff
path: root/thirdparty/meshoptimizer/clusterizer.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'thirdparty/meshoptimizer/clusterizer.cpp')
-rw-r--r--thirdparty/meshoptimizer/clusterizer.cpp152
1 files changed, 90 insertions, 62 deletions
diff --git a/thirdparty/meshoptimizer/clusterizer.cpp b/thirdparty/meshoptimizer/clusterizer.cpp
index b1f7b359c1..c4672ad606 100644
--- a/thirdparty/meshoptimizer/clusterizer.cpp
+++ b/thirdparty/meshoptimizer/clusterizer.cpp
@@ -283,6 +283,79 @@ static bool appendMeshlet(meshopt_Meshlet& meshlet, unsigned int a, unsigned int
return result;
}
+static unsigned int getNeighborTriangle(const meshopt_Meshlet& meshlet, const Cone* meshlet_cone, unsigned int* meshlet_vertices, const unsigned int* indices, const TriangleAdjacency2& adjacency, const Cone* triangles, const unsigned int* live_triangles, const unsigned char* used, float meshlet_expected_radius, float cone_weight, unsigned int* out_extra)
+{
+ unsigned int best_triangle = ~0u;
+ unsigned int best_extra = 5;
+ float best_score = FLT_MAX;
+
+ for (size_t i = 0; i < meshlet.vertex_count; ++i)
+ {
+ unsigned int index = meshlet_vertices[meshlet.vertex_offset + i];
+
+ unsigned int* neighbors = &adjacency.data[0] + adjacency.offsets[index];
+ size_t neighbors_size = adjacency.counts[index];
+
+ for (size_t j = 0; j < neighbors_size; ++j)
+ {
+ unsigned int triangle = neighbors[j];
+ unsigned int a = indices[triangle * 3 + 0], b = indices[triangle * 3 + 1], c = indices[triangle * 3 + 2];
+
+ unsigned int extra = (used[a] == 0xff) + (used[b] == 0xff) + (used[c] == 0xff);
+
+ // triangles that don't add new vertices to meshlets are max. priority
+ if (extra != 0)
+ {
+ // artificially increase the priority of dangling triangles as they're expensive to add to new meshlets
+ if (live_triangles[a] == 1 || live_triangles[b] == 1 || live_triangles[c] == 1)
+ extra = 0;
+
+ extra++;
+ }
+
+ // since topology-based priority is always more important than the score, we can skip scoring in some cases
+ if (extra > best_extra)
+ continue;
+
+ float score = 0;
+
+ // caller selects one of two scoring functions: geometrical (based on meshlet cone) or topological (based on remaining triangles)
+ if (meshlet_cone)
+ {
+ const Cone& tri_cone = triangles[triangle];
+
+ float distance2 =
+ (tri_cone.px - meshlet_cone->px) * (tri_cone.px - meshlet_cone->px) +
+ (tri_cone.py - meshlet_cone->py) * (tri_cone.py - meshlet_cone->py) +
+ (tri_cone.pz - meshlet_cone->pz) * (tri_cone.pz - meshlet_cone->pz);
+
+ float spread = tri_cone.nx * meshlet_cone->nx + tri_cone.ny * meshlet_cone->ny + tri_cone.nz * meshlet_cone->nz;
+
+ score = getMeshletScore(distance2, spread, cone_weight, meshlet_expected_radius);
+ }
+ else
+ {
+ // each live_triangles entry is >= 1 since it includes the current triangle we're processing
+ score = float(live_triangles[a] + live_triangles[b] + live_triangles[c] - 3);
+ }
+
+ // note that topology-based priority is always more important than the score
+ // this helps maintain reasonable effectiveness of meshlet data and reduces scoring cost
+ if (extra < best_extra || score < best_score)
+ {
+ best_triangle = triangle;
+ best_extra = extra;
+ best_score = score;
+ }
+ }
+ }
+
+ if (out_extra)
+ *out_extra = best_extra;
+
+ return best_triangle;
+}
+
struct KDNode
{
union
@@ -464,13 +537,15 @@ size_t meshopt_buildMeshlets(meshopt_Meshlet* meshlets, unsigned int* meshlet_ve
using namespace meshopt;
assert(index_count % 3 == 0);
- assert(vertex_positions_stride > 0 && vertex_positions_stride <= 256);
+ assert(vertex_positions_stride >= 12 && vertex_positions_stride <= 256);
assert(vertex_positions_stride % sizeof(float) == 0);
assert(max_vertices >= 3 && max_vertices <= kMeshletMaxVertices);
assert(max_triangles >= 1 && max_triangles <= kMeshletMaxTriangles);
assert(max_triangles % 4 == 0); // ensures the caller will compute output space properly as index data is 4b aligned
+ assert(cone_weight >= 0 && cone_weight <= 1);
+
meshopt_Allocator allocator;
TriangleAdjacency2 adjacency = {};
@@ -511,65 +586,18 @@ size_t meshopt_buildMeshlets(meshopt_Meshlet* meshlets, unsigned int* meshlet_ve
for (;;)
{
- unsigned int best_triangle = ~0u;
- unsigned int best_extra = 5;
- float best_score = FLT_MAX;
-
Cone meshlet_cone = getMeshletCone(meshlet_cone_acc, meshlet.triangle_count);
- for (size_t i = 0; i < meshlet.vertex_count; ++i)
- {
- unsigned int index = meshlet_vertices[meshlet.vertex_offset + i];
-
- unsigned int* neighbours = &adjacency.data[0] + adjacency.offsets[index];
- size_t neighbours_size = adjacency.counts[index];
-
- for (size_t j = 0; j < neighbours_size; ++j)
- {
- unsigned int triangle = neighbours[j];
- assert(!emitted_flags[triangle]);
-
- unsigned int a = indices[triangle * 3 + 0], b = indices[triangle * 3 + 1], c = indices[triangle * 3 + 2];
- assert(a < vertex_count && b < vertex_count && c < vertex_count);
-
- unsigned int extra = (used[a] == 0xff) + (used[b] == 0xff) + (used[c] == 0xff);
-
- // triangles that don't add new vertices to meshlets are max. priority
- if (extra != 0)
- {
- // artificially increase the priority of dangling triangles as they're expensive to add to new meshlets
- if (live_triangles[a] == 1 || live_triangles[b] == 1 || live_triangles[c] == 1)
- extra = 0;
-
- extra++;
- }
-
- // since topology-based priority is always more important than the score, we can skip scoring in some cases
- if (extra > best_extra)
- continue;
-
- const Cone& tri_cone = triangles[triangle];
-
- float distance2 =
- (tri_cone.px - meshlet_cone.px) * (tri_cone.px - meshlet_cone.px) +
- (tri_cone.py - meshlet_cone.py) * (tri_cone.py - meshlet_cone.py) +
- (tri_cone.pz - meshlet_cone.pz) * (tri_cone.pz - meshlet_cone.pz);
-
- float spread = tri_cone.nx * meshlet_cone.nx + tri_cone.ny * meshlet_cone.ny + tri_cone.nz * meshlet_cone.nz;
+ unsigned int best_extra = 0;
+ unsigned int best_triangle = getNeighborTriangle(meshlet, &meshlet_cone, meshlet_vertices, indices, adjacency, triangles, live_triangles, used, meshlet_expected_radius, cone_weight, &best_extra);
- float score = getMeshletScore(distance2, spread, cone_weight, meshlet_expected_radius);
-
- // note that topology-based priority is always more important than the score
- // this helps maintain reasonable effectiveness of meshlet data and reduces scoring cost
- if (extra < best_extra || score < best_score)
- {
- best_triangle = triangle;
- best_extra = extra;
- best_score = score;
- }
- }
+ // if the best triangle doesn't fit into current meshlet, the spatial scoring we've used is not very meaningful, so we re-select using topological scoring
+ if (best_triangle != ~0u && (meshlet.vertex_count + best_extra > max_vertices || meshlet.triangle_count >= max_triangles))
+ {
+ best_triangle = getNeighborTriangle(meshlet, NULL, meshlet_vertices, indices, adjacency, triangles, live_triangles, used, meshlet_expected_radius, 0.f, NULL);
}
+ // when we run out of neighboring triangles we need to switch to spatial search; we currently just pick the closest triangle irrespective of connectivity
if (best_triangle == ~0u)
{
float position[3] = {meshlet_cone.px, meshlet_cone.py, meshlet_cone.pz};
@@ -604,16 +632,16 @@ size_t meshopt_buildMeshlets(meshopt_Meshlet* meshlets, unsigned int* meshlet_ve
{
unsigned int index = indices[best_triangle * 3 + k];
- unsigned int* neighbours = &adjacency.data[0] + adjacency.offsets[index];
- size_t neighbours_size = adjacency.counts[index];
+ unsigned int* neighbors = &adjacency.data[0] + adjacency.offsets[index];
+ size_t neighbors_size = adjacency.counts[index];
- for (size_t i = 0; i < neighbours_size; ++i)
+ for (size_t i = 0; i < neighbors_size; ++i)
{
- unsigned int tri = neighbours[i];
+ unsigned int tri = neighbors[i];
if (tri == best_triangle)
{
- neighbours[i] = neighbours[neighbours_size - 1];
+ neighbors[i] = neighbors[neighbors_size - 1];
adjacency.counts[index]--;
break;
}
@@ -687,7 +715,7 @@ meshopt_Bounds meshopt_computeClusterBounds(const unsigned int* indices, size_t
assert(index_count % 3 == 0);
assert(index_count / 3 <= kMeshletMaxTriangles);
- assert(vertex_positions_stride > 0 && vertex_positions_stride <= 256);
+ assert(vertex_positions_stride >= 12 && vertex_positions_stride <= 256);
assert(vertex_positions_stride % sizeof(float) == 0);
(void)vertex_count;
@@ -839,7 +867,7 @@ meshopt_Bounds meshopt_computeMeshletBounds(const unsigned int* meshlet_vertices
using namespace meshopt;
assert(triangle_count <= kMeshletMaxTriangles);
- assert(vertex_positions_stride > 0 && vertex_positions_stride <= 256);
+ assert(vertex_positions_stride >= 12 && vertex_positions_stride <= 256);
assert(vertex_positions_stride % sizeof(float) == 0);
unsigned int indices[kMeshletMaxTriangles * 3];
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-23 05:30:06 +0000