diff options
Diffstat (limited to 'thirdparty/meshoptimizer/simplifier.cpp')
| -rw-r--r-- | thirdparty/meshoptimizer/simplifier.cpp | 321 |
1 files changed, 208 insertions, 113 deletions
diff --git a/thirdparty/meshoptimizer/simplifier.cpp b/thirdparty/meshoptimizer/simplifier.cpp index b195a8cb5d..942db14461 100644 --- a/thirdparty/meshoptimizer/simplifier.cpp +++ b/thirdparty/meshoptimizer/simplifier.cpp @@ -6,7 +6,6 @@ #include <math.h> #include <string.h> - #ifndef TRACE #define TRACE 0 #endif @@ -15,6 +14,12 @@ #include <stdio.h> #endif +#if TRACE +#define TRACESTATS(i) stats[i]++; +#else +#define TRACESTATS(i) (void)0 +#endif + // This work is based on: // Michael Garland and Paul S. Heckbert. Surface simplification using quadric error metrics. 1997 // Michael Garland. Quadric-based polygonal surface simplification. 1999 @@ -26,28 +31,37 @@ namespace meshopt struct EdgeAdjacency { + struct Edge + { + unsigned int next; + unsigned int prev; + }; + unsigned int* counts; unsigned int* offsets; - unsigned int* data; + Edge* data; }; -static void buildEdgeAdjacency(EdgeAdjacency& adjacency, const unsigned int* indices, size_t index_count, size_t vertex_count, meshopt_Allocator& allocator) +static void prepareEdgeAdjacency(EdgeAdjacency& adjacency, size_t index_count, size_t vertex_count, meshopt_Allocator& allocator) { - size_t face_count = index_count / 3; - - // allocate arrays adjacency.counts = allocator.allocate<unsigned int>(vertex_count); adjacency.offsets = allocator.allocate<unsigned int>(vertex_count); - adjacency.data = allocator.allocate<unsigned int>(index_count); + adjacency.data = allocator.allocate<EdgeAdjacency::Edge>(index_count); +} + +static void updateEdgeAdjacency(EdgeAdjacency& adjacency, const unsigned int* indices, size_t index_count, size_t vertex_count, const unsigned int* remap) +{ + size_t face_count = index_count / 3; // fill edge counts memset(adjacency.counts, 0, vertex_count * sizeof(unsigned int)); for (size_t i = 0; i < index_count; ++i) { - assert(indices[i] < vertex_count); + unsigned int v = remap ? remap[indices[i]] : indices[i]; + assert(v < vertex_count); - adjacency.counts[indices[i]]++; + adjacency.counts[v]++; } // fill offset table @@ -66,9 +80,24 @@ static void buildEdgeAdjacency(EdgeAdjacency& adjacency, const unsigned int* ind { unsigned int a = indices[i * 3 + 0], b = indices[i * 3 + 1], c = indices[i * 3 + 2]; - adjacency.data[adjacency.offsets[a]++] = b; - adjacency.data[adjacency.offsets[b]++] = c; - adjacency.data[adjacency.offsets[c]++] = a; + if (remap) + { + a = remap[a]; + b = remap[b]; + c = remap[c]; + } + + adjacency.data[adjacency.offsets[a]].next = b; + adjacency.data[adjacency.offsets[a]].prev = c; + adjacency.offsets[a]++; + + adjacency.data[adjacency.offsets[b]].next = c; + adjacency.data[adjacency.offsets[b]].prev = a; + adjacency.offsets[b]++; + + adjacency.data[adjacency.offsets[c]].next = a; + adjacency.data[adjacency.offsets[c]].prev = b; + adjacency.offsets[c]++; } // fix offsets that have been disturbed by the previous pass @@ -209,10 +238,10 @@ const unsigned char kHasOpposite[Kind_Count][Kind_Count] = { static bool hasEdge(const EdgeAdjacency& adjacency, unsigned int a, unsigned int b) { unsigned int count = adjacency.counts[a]; - const unsigned int* data = adjacency.data + adjacency.offsets[a]; + const EdgeAdjacency::Edge* edges = adjacency.data + adjacency.offsets[a]; for (size_t i = 0; i < count; ++i) - if (data[i] == b) + if (edges[i].next == b) return true; return false; @@ -234,11 +263,11 @@ static void classifyVertices(unsigned char* result, unsigned int* loop, unsigned unsigned int vertex = unsigned(i); unsigned int count = adjacency.counts[vertex]; - const unsigned int* data = adjacency.data + adjacency.offsets[vertex]; + const EdgeAdjacency::Edge* edges = adjacency.data + adjacency.offsets[vertex]; for (size_t j = 0; j < count; ++j) { - unsigned int target = data[j]; + unsigned int target = edges[j].next; if (!hasEdge(adjacency, target, vertex)) { @@ -249,10 +278,7 @@ static void classifyVertices(unsigned char* result, unsigned int* loop, unsigned } #if TRACE - size_t lockedstats[4] = {}; -#define TRACELOCKED(i) lockedstats[i]++; -#else -#define TRACELOCKED(i) (void)0 + size_t stats[4] = {}; #endif for (size_t i = 0; i < vertex_count; ++i) @@ -278,7 +304,7 @@ static void classifyVertices(unsigned char* result, unsigned int* loop, unsigned else { result[i] = Kind_Locked; - TRACELOCKED(0); + TRACESTATS(0); } } else if (wedge[wedge[i]] == i) @@ -299,20 +325,20 @@ static void classifyVertices(unsigned char* result, unsigned int* loop, unsigned else { result[i] = Kind_Locked; - TRACELOCKED(1); + TRACESTATS(1); } } else { result[i] = Kind_Locked; - TRACELOCKED(2); + TRACESTATS(2); } } else { // more than one vertex maps to this one; we don't have classification available result[i] = Kind_Locked; - TRACELOCKED(3); + TRACESTATS(3); } } else @@ -325,7 +351,7 @@ static void classifyVertices(unsigned char* result, unsigned int* loop, unsigned #if TRACE printf("locked: many open edges %d, disconnected seam %d, many seam edges %d, many wedges %d\n", - int(lockedstats[0]), int(lockedstats[1]), int(lockedstats[2]), int(lockedstats[3])); + int(stats[0]), int(stats[1]), int(stats[2]), int(stats[3])); #endif } @@ -333,11 +359,8 @@ struct Vector3 { float x, y, z; }; -// -- GODOT start -- -//static void rescalePositions(Vector3* result, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride) -static float rescalePositions(Vector3* result, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride) -// -- GODOT end -- +static float rescalePositions(Vector3* result, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride) { size_t vertex_stride_float = vertex_positions_stride / sizeof(float); @@ -348,9 +371,12 @@ static float rescalePositions(Vector3* result, const float* vertex_positions_dat { const float* v = vertex_positions_data + i * vertex_stride_float; - result[i].x = v[0]; - result[i].y = v[1]; - result[i].z = v[2]; + if (result) + { + result[i].x = v[0]; + result[i].y = v[1]; + result[i].z = v[2]; + } for (int j = 0; j < 3; ++j) { @@ -367,18 +393,19 @@ static float rescalePositions(Vector3* result, const float* vertex_positions_dat extent = (maxv[1] - minv[1]) < extent ? extent : (maxv[1] - minv[1]); extent = (maxv[2] - minv[2]) < extent ? extent : (maxv[2] - minv[2]); - float scale = extent == 0 ? 0.f : 1.f / extent; - - for (size_t i = 0; i < vertex_count; ++i) + if (result) { - result[i].x = (result[i].x - minv[0]) * scale; - result[i].y = (result[i].y - minv[1]) * scale; - result[i].z = (result[i].z - minv[2]) * scale; + float scale = extent == 0 ? 0.f : 1.f / extent; + + for (size_t i = 0; i < vertex_count; ++i) + { + result[i].x = (result[i].x - minv[0]) * scale; + result[i].y = (result[i].y - minv[1]) * scale; + result[i].z = (result[i].z - minv[2]) * scale; + } } -// -- GODOT start -- - return extent; -// -- GODOT end -- + return extent; } struct Quadric @@ -594,6 +621,48 @@ static void fillEdgeQuadrics(Quadric* vertex_quadrics, const unsigned int* indic } } +// does triangle ABC flip when C is replaced with D? +static bool hasTriangleFlip(const Vector3& a, const Vector3& b, const Vector3& c, const Vector3& d) +{ + Vector3 eb = {b.x - a.x, b.y - a.y, b.z - a.z}; + Vector3 ec = {c.x - a.x, c.y - a.y, c.z - a.z}; + Vector3 ed = {d.x - a.x, d.y - a.y, d.z - a.z}; + + Vector3 nbc = {eb.y * ec.z - eb.z * ec.y, eb.z * ec.x - eb.x * ec.z, eb.x * ec.y - eb.y * ec.x}; + Vector3 nbd = {eb.y * ed.z - eb.z * ed.y, eb.z * ed.x - eb.x * ed.z, eb.x * ed.y - eb.y * ed.x}; + + return nbc.x * nbd.x + nbc.y * nbd.y + nbc.z * nbd.z < 0; +} + +static bool hasTriangleFlips(const EdgeAdjacency& adjacency, const Vector3* vertex_positions, const unsigned int* collapse_remap, unsigned int i0, unsigned int i1) +{ + assert(collapse_remap[i0] == i0); + assert(collapse_remap[i1] == i1); + + const Vector3& v0 = vertex_positions[i0]; + const Vector3& v1 = vertex_positions[i1]; + + const EdgeAdjacency::Edge* edges = &adjacency.data[adjacency.offsets[i0]]; + size_t count = adjacency.counts[i0]; + + for (size_t i = 0; i < count; ++i) + { + unsigned int a = collapse_remap[edges[i].next]; + unsigned int b = collapse_remap[edges[i].prev]; + + // skip triangles that get collapsed + // note: this is mathematically redundant as if either of these is true, the dot product in hasTriangleFlip should be 0 + if (a == i1 || b == i1) + continue; + + // early-out when at least one triangle flips due to a collapse + if (hasTriangleFlip(vertex_positions[a], vertex_positions[b], v0, v1)) + return true; + } + + return false; +} + static size_t pickEdgeCollapses(Collapse* collapses, const unsigned int* indices, size_t index_count, const unsigned int* remap, const unsigned char* vertex_kind, const unsigned int* loop) { size_t collapse_count = 0; @@ -704,7 +773,7 @@ static void dumpEdgeCollapses(const Collapse* collapses, size_t collapse_count, for (int k0 = 0; k0 < Kind_Count; ++k0) for (int k1 = 0; k1 < Kind_Count; ++k1) if (ckinds[k0][k1]) - printf("collapses %d -> %d: %d, min error %e\n", k0, k1, int(ckinds[k0][k1]), cerrors[k0][k1]); + printf("collapses %d -> %d: %d, min error %e\n", k0, k1, int(ckinds[k0][k1]), ckinds[k0][k1] ? sqrtf(cerrors[k0][k1]) : 0.f); } static void dumpLockedCollapses(const unsigned int* indices, size_t index_count, const unsigned char* vertex_kind) @@ -772,22 +841,38 @@ static void sortEdgeCollapses(unsigned int* sort_order, const Collapse* collapse } } -static size_t performEdgeCollapses(unsigned int* collapse_remap, unsigned char* collapse_locked, Quadric* vertex_quadrics, const Collapse* collapses, size_t collapse_count, const unsigned int* collapse_order, const unsigned int* remap, const unsigned int* wedge, const unsigned char* vertex_kind, size_t triangle_collapse_goal, float error_goal, float error_limit) +static size_t performEdgeCollapses(unsigned int* collapse_remap, unsigned char* collapse_locked, Quadric* vertex_quadrics, const Collapse* collapses, size_t collapse_count, const unsigned int* collapse_order, const unsigned int* remap, const unsigned int* wedge, const unsigned char* vertex_kind, const Vector3* vertex_positions, const EdgeAdjacency& adjacency, size_t triangle_collapse_goal, float error_limit, float& result_error) { size_t edge_collapses = 0; size_t triangle_collapses = 0; + // most collapses remove 2 triangles; use this to establish a bound on the pass in terms of error limit + // note that edge_collapse_goal is an estimate; triangle_collapse_goal will be used to actually limit collapses + size_t edge_collapse_goal = triangle_collapse_goal / 2; + +#if TRACE + size_t stats[4] = {}; +#endif + for (size_t i = 0; i < collapse_count; ++i) { const Collapse& c = collapses[collapse_order[i]]; + TRACESTATS(0); + if (c.error > error_limit) break; - if (c.error > error_goal && triangle_collapses > triangle_collapse_goal / 10) + if (triangle_collapses >= triangle_collapse_goal) break; - if (triangle_collapses >= triangle_collapse_goal) + // we limit the error in each pass based on the error of optimal last collapse; since many collapses will be locked + // as they will share vertices with other successfull collapses, we need to increase the acceptable error by some factor + float error_goal = edge_collapse_goal < collapse_count ? 1.5f * collapses[collapse_order[edge_collapse_goal]].error : FLT_MAX; + + // on average, each collapse is expected to lock 6 other collapses; to avoid degenerate passes on meshes with odd + // topology, we only abort if we got over 1/6 collapses accordingly. + if (c.error > error_goal && triangle_collapses > triangle_collapse_goal / 6) break; unsigned int i0 = c.v0; @@ -800,7 +885,19 @@ static size_t performEdgeCollapses(unsigned int* collapse_remap, unsigned char* // it's important to not move the vertices twice since it complicates the tracking/remapping logic // it's important to not move other vertices towards a moved vertex to preserve error since we don't re-rank collapses mid-pass if (collapse_locked[r0] | collapse_locked[r1]) + { + TRACESTATS(1); + continue; + } + + if (hasTriangleFlips(adjacency, vertex_positions, collapse_remap, r0, r1)) + { + // adjust collapse goal since this collapse is invalid and shouldn't factor into error goal + edge_collapse_goal++; + + TRACESTATS(2); continue; + } assert(collapse_remap[r0] == r0); assert(collapse_remap[r1] == r1); @@ -842,8 +939,18 @@ static size_t performEdgeCollapses(unsigned int* collapse_remap, unsigned char* // border edges collapse 1 triangle, other edges collapse 2 or more triangle_collapses += (vertex_kind[i0] == Kind_Border) ? 1 : 2; edge_collapses++; + + result_error = result_error < c.error ? c.error : result_error; } +#if TRACE + float error_goal_perfect = edge_collapse_goal < collapse_count ? collapses[collapse_order[edge_collapse_goal]].error : 0.f; + + printf("removed %d triangles, error %e (goal %e); evaluated %d/%d collapses (done %d, skipped %d, invalid %d)\n", + int(triangle_collapses), sqrtf(result_error), sqrtf(error_goal_perfect), + int(stats[0]), int(collapse_count), int(edge_collapses), int(stats[1]), int(stats[2])); +#endif + return edge_collapses; } @@ -1151,10 +1258,7 @@ unsigned int* meshopt_simplifyDebugLoop = 0; unsigned int* meshopt_simplifyDebugLoopBack = 0; #endif -// -- GODOT start -- -//size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error) -size_t meshopt_simplify(unsigned int *destination, const unsigned int *indices, size_t index_count, const float *vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float *r_resulting_error) -// -- GODOT end -- +size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float* out_result_error) { using namespace meshopt; @@ -1169,7 +1273,8 @@ size_t meshopt_simplify(unsigned int *destination, const unsigned int *indices, // build adjacency information EdgeAdjacency adjacency = {}; - buildEdgeAdjacency(adjacency, indices, index_count, vertex_count, allocator); + prepareEdgeAdjacency(adjacency, index_count, vertex_count, allocator); + updateEdgeAdjacency(adjacency, indices, index_count, vertex_count, NULL); // build position remap that maps each vertex to the one with identical position unsigned int* remap = allocator.allocate<unsigned int>(vertex_count); @@ -1198,10 +1303,7 @@ size_t meshopt_simplify(unsigned int *destination, const unsigned int *indices, #endif Vector3* vertex_positions = allocator.allocate<Vector3>(vertex_count); -// -- GODOT start -- - //rescalePositions(vertex_positions, vertex_positions_data, vertex_count, vertex_positions_stride); - float extent = rescalePositions(vertex_positions, vertex_positions_data, vertex_count, vertex_positions_stride); -// -- GODOT end -- + rescalePositions(vertex_positions, vertex_positions_data, vertex_count, vertex_positions_stride); Quadric* vertex_quadrics = allocator.allocate<Quadric>(vertex_count); memset(vertex_quadrics, 0, vertex_count * sizeof(Quadric)); @@ -1212,13 +1314,9 @@ size_t meshopt_simplify(unsigned int *destination, const unsigned int *indices, if (result != indices) memcpy(result, indices, index_count * sizeof(unsigned int)); -// -- GODOT start -- #if TRACE size_t pass_count = 0; - //float worst_error = 0; #endif - float worst_error = 0; -// -- GODOT end -- Collapse* edge_collapses = allocator.allocate<Collapse>(index_count); unsigned int* collapse_order = allocator.allocate<unsigned int>(index_count); @@ -1226,18 +1324,16 @@ size_t meshopt_simplify(unsigned int *destination, const unsigned int *indices, unsigned char* collapse_locked = allocator.allocate<unsigned char>(vertex_count); size_t result_count = index_count; + float result_error = 0; // target_error input is linear; we need to adjust it to match quadricError units float error_limit = target_error * target_error; -// -- GODOT start -- - if (r_resulting_error) { - *r_resulting_error = 1.0; - } -// -- GODOT end -- - while (result_count > target_index_count) { + // note: throughout the simplification process adjacency structure reflects welded topology for result-in-progress + updateEdgeAdjacency(adjacency, result, result_count, vertex_count, remap); + size_t edge_collapse_count = pickEdgeCollapses(edge_collapses, result, result_count, remap, vertex_kind, loop); // no edges can be collapsed any more due to topology restrictions @@ -1252,23 +1348,18 @@ size_t meshopt_simplify(unsigned int *destination, const unsigned int *indices, sortEdgeCollapses(collapse_order, edge_collapses, edge_collapse_count); - // most collapses remove 2 triangles; use this to establish a bound on the pass in terms of error limit - // note that edge_collapse_goal is an estimate; triangle_collapse_goal will be used to actually limit collapses size_t triangle_collapse_goal = (result_count - target_index_count) / 3; - size_t edge_collapse_goal = triangle_collapse_goal / 2; - - // we limit the error in each pass based on the error of optimal last collapse; since many collapses will be locked - // as they will share vertices with other successfull collapses, we need to increase the acceptable error by this factor - const float kPassErrorBound = 1.5f; - - float error_goal = edge_collapse_goal < edge_collapse_count ? edge_collapses[collapse_order[edge_collapse_goal]].error * kPassErrorBound : FLT_MAX; for (size_t i = 0; i < vertex_count; ++i) collapse_remap[i] = unsigned(i); memset(collapse_locked, 0, vertex_count); - size_t collapses = performEdgeCollapses(collapse_remap, collapse_locked, vertex_quadrics, edge_collapses, edge_collapse_count, collapse_order, remap, wedge, vertex_kind, triangle_collapse_goal, error_goal, error_limit); +#if TRACE + printf("pass %d: ", int(pass_count++)); +#endif + + size_t collapses = performEdgeCollapses(collapse_remap, collapse_locked, vertex_quadrics, edge_collapses, edge_collapse_count, collapse_order, remap, wedge, vertex_kind, vertex_positions, adjacency, triangle_collapse_goal, error_limit, result_error); // no edges can be collapsed any more due to hitting the error limit or triangle collapse limit if (collapses == 0) @@ -1280,37 +1371,11 @@ size_t meshopt_simplify(unsigned int *destination, const unsigned int *indices, size_t new_count = remapIndexBuffer(result, result_count, collapse_remap); assert(new_count < result_count); -// -- GODOT start -- -//#if TRACE - float pass_error = 0.f; - for (size_t i = 0; i < edge_collapse_count; ++i) - { - Collapse& c = edge_collapses[collapse_order[i]]; - - if (collapse_remap[c.v0] == c.v1) - pass_error = c.error; - } - - //pass_count++; - worst_error = (worst_error < pass_error) ? pass_error : worst_error; - -#if TRACE - pass_count++; - printf("pass %d: triangles: %d -> %d, collapses: %d/%d (goal: %d), error: %e (limit %e goal %e)\n", int(pass_count), int(result_count / 3), int(new_count / 3), int(collapses), int(edge_collapse_count), int(edge_collapse_goal), pass_error, error_limit, error_goal); -#endif -// -- GODOT end -- - result_count = new_count; } -// -- GODOT start -- - if (r_resulting_error) { - *r_resulting_error = sqrt(worst_error) * extent; - } -// -- GODOT end -- - #if TRACE - printf("passes: %d, worst error: %e\n", int(pass_count), worst_error); + printf("result: %d triangles, error: %e; total %d passes\n", int(result_count), sqrtf(result_error), int(pass_count)); #endif #if TRACE > 1 @@ -1328,10 +1393,14 @@ size_t meshopt_simplify(unsigned int *destination, const unsigned int *indices, memcpy(meshopt_simplifyDebugLoopBack, loopback, vertex_count * sizeof(unsigned int)); #endif + // result_error is quadratic; we need to remap it back to linear + if (out_result_error) + *out_result_error = sqrtf(result_error); + return result_count; } -size_t meshopt_simplifySloppy(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count) +size_t meshopt_simplifySloppy(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float* out_result_error) { using namespace meshopt; @@ -1343,9 +1412,6 @@ size_t meshopt_simplifySloppy(unsigned int* destination, const unsigned int* ind // we expect to get ~2 triangles/vertex in the output size_t target_cell_count = target_index_count / 6; - if (target_cell_count == 0) - return 0; - meshopt_Allocator allocator; Vector3* vertex_positions = allocator.allocate<Vector3>(vertex_count); @@ -1362,18 +1428,25 @@ size_t meshopt_simplifySloppy(unsigned int* destination, const unsigned int* ind const int kInterpolationPasses = 5; // invariant: # of triangles in min_grid <= target_count - int min_grid = 0; + int min_grid = int(1.f / (target_error < 1e-3f ? 1e-3f : target_error)); int max_grid = 1025; size_t min_triangles = 0; size_t max_triangles = index_count / 3; + // when we're error-limited, we compute the triangle count for the min. size; this accelerates convergence and provides the correct answer when we can't use a larger grid + if (min_grid > 1) + { + computeVertexIds(vertex_ids, vertex_positions, vertex_count, min_grid); + min_triangles = countTriangles(vertex_ids, indices, index_count); + } + // instead of starting in the middle, let's guess as to what the answer might be! triangle count usually grows as a square of grid size... int next_grid_size = int(sqrtf(float(target_cell_count)) + 0.5f); for (int pass = 0; pass < 10 + kInterpolationPasses; ++pass) { - assert(min_triangles < target_index_count / 3); - assert(max_grid - min_grid > 1); + if (min_triangles >= target_index_count / 3 || max_grid - min_grid <= 1) + break; // we clamp the prediction of the grid size to make sure that the search converges int grid_size = next_grid_size; @@ -1402,16 +1475,18 @@ size_t meshopt_simplifySloppy(unsigned int* destination, const unsigned int* ind max_triangles = triangles; } - if (triangles == target_index_count / 3 || max_grid - min_grid <= 1) - break; - // we start by using interpolation search - it usually converges faster // however, interpolation search has a worst case of O(N) so we switch to binary search after a few iterations which converges in O(logN) next_grid_size = (pass < kInterpolationPasses) ? int(tip + 0.5f) : (min_grid + max_grid) / 2; } if (min_triangles == 0) + { + if (out_result_error) + *out_result_error = 1.f; + return 0; + } // build vertex->cell association by mapping all vertices with the same quantized position to the same cell size_t table_size = hashBuckets2(vertex_count); @@ -1434,18 +1509,26 @@ size_t meshopt_simplifySloppy(unsigned int* destination, const unsigned int* ind fillCellRemap(cell_remap, cell_errors, cell_count, vertex_cells, cell_quadrics, vertex_positions, vertex_count); + // compute error + float result_error = 0.f; + + for (size_t i = 0; i < cell_count; ++i) + result_error = result_error < cell_errors[i] ? cell_errors[i] : result_error; + // collapse triangles! // note that we need to filter out triangles that we've already output because we very frequently generate redundant triangles between cells :( size_t tritable_size = hashBuckets2(min_triangles); unsigned int* tritable = allocator.allocate<unsigned int>(tritable_size); size_t write = filterTriangles(destination, tritable, tritable_size, indices, index_count, vertex_cells, cell_remap); - assert(write <= target_index_count); #if TRACE - printf("result: %d cells, %d triangles (%d unfiltered)\n", int(cell_count), int(write / 3), int(min_triangles)); + printf("result: %d cells, %d triangles (%d unfiltered), error %e\n", int(cell_count), int(write / 3), int(min_triangles), sqrtf(result_error)); #endif + if (out_result_error) + *out_result_error = sqrtf(result_error); + return write; } @@ -1560,3 +1643,15 @@ size_t meshopt_simplifyPoints(unsigned int* destination, const float* vertex_pos return cell_count; } + +float meshopt_simplifyScale(const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride) +{ + using namespace meshopt; + + assert(vertex_positions_stride > 0 && vertex_positions_stride <= 256); + assert(vertex_positions_stride % sizeof(float) == 0); + + float extent = rescalePositions(NULL, vertex_positions, vertex_count, vertex_positions_stride); + + return extent; +} |