summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--editor/import/scene_importer_mesh.cpp46
-rw-r--r--modules/meshoptimizer/register_types.cpp4
-rw-r--r--scene/resources/surface_tool.cpp2
-rw-r--r--scene/resources/surface_tool.h4
-rw-r--r--thirdparty/README.md2
-rw-r--r--thirdparty/meshoptimizer/indexcodec.cpp2
-rw-r--r--thirdparty/meshoptimizer/meshoptimizer.h20
-rw-r--r--thirdparty/meshoptimizer/simplifier.cpp38
8 files changed, 91 insertions, 27 deletions
diff --git a/editor/import/scene_importer_mesh.cpp b/editor/import/scene_importer_mesh.cpp
index cd7d58c6f6..620437af0e 100644
--- a/editor/import/scene_importer_mesh.cpp
+++ b/editor/import/scene_importer_mesh.cpp
@@ -140,6 +140,12 @@ void EditorSceneImporterMesh::generate_lods() {
if (!SurfaceTool::simplify_func) {
return;
}
+ if (!SurfaceTool::simplify_scale_func) {
+ return;
+ }
+ if (!SurfaceTool::simplify_sloppy_func) {
+ return;
+ }
for (int i = 0; i < surfaces.size(); i++) {
if (surfaces[i].primitive != Mesh::PRIMITIVE_TRIANGLES) {
@@ -157,20 +163,52 @@ void EditorSceneImporterMesh::generate_lods() {
int min_indices = 10;
int index_target = indices.size() / 2;
- print_line("total: " + itos(indices.size()));
+ print_line("Total indices: " + itos(indices.size()));
+ float mesh_scale = SurfaceTool::simplify_scale_func((const float *)vertices_ptr, vertex_count, sizeof(Vector3));
+ const float target_error = 1e-3f;
+ float abs_target_error = target_error / mesh_scale;
while (index_target > min_indices) {
float error;
Vector<int> new_indices;
new_indices.resize(indices.size());
- size_t new_len = SurfaceTool::simplify_func((unsigned int *)new_indices.ptrw(), (const unsigned int *)indices.ptr(), indices.size(), (const float *)vertices_ptr, vertex_count, sizeof(Vector3), index_target, 1e20, &error);
- print_line("shoot for " + itos(index_target) + ", got " + itos(new_len) + " distance " + rtos(error));
+ size_t new_len = SurfaceTool::simplify_func((unsigned int *)new_indices.ptrw(), (const unsigned int *)indices.ptr(), indices.size(), (const float *)vertices_ptr, vertex_count, sizeof(Vector3), index_target, abs_target_error, &error);
if ((int)new_len > (index_target * 120 / 100)) {
+ // Attribute discontinuities break normals.
+ bool is_sloppy = false;
+ if (is_sloppy) {
+ abs_target_error = target_error / mesh_scale;
+ index_target = new_len;
+ while (index_target > min_indices) {
+ Vector<int> sloppy_new_indices;
+ sloppy_new_indices.resize(indices.size());
+ new_len = SurfaceTool::simplify_sloppy_func((unsigned int *)sloppy_new_indices.ptrw(), (const unsigned int *)indices.ptr(), indices.size(), (const float *)vertices_ptr, vertex_count, sizeof(Vector3), index_target, abs_target_error, &error);
+ if ((int)new_len > (index_target * 120 / 100)) {
+ break; // 20 percent tolerance
+ }
+ sloppy_new_indices.resize(new_len);
+ Surface::LOD lod;
+ lod.distance = error * mesh_scale;
+ abs_target_error = lod.distance;
+ if (Math::is_equal_approx(abs_target_error, 0.0f)) {
+ return;
+ }
+ lod.indices = sloppy_new_indices;
+ print_line("Lod " + itos(surfaces.write[i].lods.size()) + " shoot for " + itos(index_target / 3) + " triangles, got " + itos(new_len / 3) + " triangles. Distance " + rtos(lod.distance) + ". Use simplify sloppy.");
+ surfaces.write[i].lods.push_back(lod);
+ index_target /= 2;
+ }
+ }
break; // 20 percent tolerance
}
new_indices.resize(new_len);
Surface::LOD lod;
- lod.distance = error;
+ lod.distance = error * mesh_scale;
+ abs_target_error = lod.distance;
+ if (Math::is_equal_approx(abs_target_error, 0.0f)) {
+ return;
+ }
lod.indices = new_indices;
+ print_line("Lod " + itos(surfaces.write[i].lods.size()) + " shoot for " + itos(index_target / 3) + " triangles, got " + itos(new_len / 3) + " triangles. Distance " + rtos(lod.distance));
surfaces.write[i].lods.push_back(lod);
index_target /= 2;
}
diff --git a/modules/meshoptimizer/register_types.cpp b/modules/meshoptimizer/register_types.cpp
index 71cd9f4dcb..a03310f518 100644
--- a/modules/meshoptimizer/register_types.cpp
+++ b/modules/meshoptimizer/register_types.cpp
@@ -35,9 +35,13 @@
void register_meshoptimizer_types() {
SurfaceTool::optimize_vertex_cache_func = meshopt_optimizeVertexCache;
SurfaceTool::simplify_func = meshopt_simplify;
+ SurfaceTool::simplify_scale_func = meshopt_simplifyScale;
+ SurfaceTool::simplify_sloppy_func = meshopt_simplifySloppy;
}
void unregister_meshoptimizer_types() {
SurfaceTool::optimize_vertex_cache_func = nullptr;
SurfaceTool::simplify_func = nullptr;
+ SurfaceTool::simplify_scale_func = nullptr;
+ SurfaceTool::simplify_sloppy_func = nullptr;
}
diff --git a/scene/resources/surface_tool.cpp b/scene/resources/surface_tool.cpp
index c1c87be42d..dbf5268762 100644
--- a/scene/resources/surface_tool.cpp
+++ b/scene/resources/surface_tool.cpp
@@ -35,6 +35,8 @@
SurfaceTool::OptimizeVertexCacheFunc SurfaceTool::optimize_vertex_cache_func = nullptr;
SurfaceTool::SimplifyFunc SurfaceTool::simplify_func = nullptr;
+SurfaceTool::SimplifyScaleFunc SurfaceTool::simplify_scale_func = nullptr;
+SurfaceTool::SimplifySloppyFunc SurfaceTool::simplify_sloppy_func = nullptr;
bool SurfaceTool::Vertex::operator==(const Vertex &p_vertex) const {
if (vertex != p_vertex.vertex) {
diff --git a/scene/resources/surface_tool.h b/scene/resources/surface_tool.h
index dcb689bfc0..ea6069e7c1 100644
--- a/scene/resources/surface_tool.h
+++ b/scene/resources/surface_tool.h
@@ -78,6 +78,10 @@ public:
static OptimizeVertexCacheFunc optimize_vertex_cache_func;
typedef size_t (*SimplifyFunc)(unsigned int *destination, const unsigned int *indices, size_t index_count, const float *vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float *r_error);
static SimplifyFunc simplify_func;
+ typedef float (*SimplifyScaleFunc)(const float *vertex_positions, size_t vertex_count, size_t vertex_positions_stride);
+ static SimplifyScaleFunc simplify_scale_func;
+ typedef size_t (*SimplifySloppyFunc)(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);
+ static SimplifySloppyFunc simplify_sloppy_func;
private:
struct VertexHasher {
diff --git a/thirdparty/README.md b/thirdparty/README.md
index 5d03458b69..6df303015b 100644
--- a/thirdparty/README.md
+++ b/thirdparty/README.md
@@ -344,7 +344,7 @@ File extracted from upstream release tarball:
## meshoptimizer
- Upstream: https://github.com/zeux/meshoptimizer
-- Version: git (e4e43fe36e7a8705e602e7ca2f9fb795ded1d0b9, 2020)
+- Version: git (e3f53f66e7a35b9b8764bee478589d79e34fa698, 2021)
- License: MIT
Files extracted from upstream repository:
diff --git a/thirdparty/meshoptimizer/indexcodec.cpp b/thirdparty/meshoptimizer/indexcodec.cpp
index 5c35eb43ae..e4495b8586 100644
--- a/thirdparty/meshoptimizer/indexcodec.cpp
+++ b/thirdparty/meshoptimizer/indexcodec.cpp
@@ -108,7 +108,7 @@ static unsigned int decodeVByte(const unsigned char*& data)
for (int i = 0; i < 4; ++i)
{
unsigned char group = *data++;
- result |= (group & 127) << shift;
+ result |= unsigned(group & 127) << shift;
shift += 7;
if (group < 128)
diff --git a/thirdparty/meshoptimizer/meshoptimizer.h b/thirdparty/meshoptimizer/meshoptimizer.h
index 4071f0a371..1714000384 100644
--- a/thirdparty/meshoptimizer/meshoptimizer.h
+++ b/thirdparty/meshoptimizer/meshoptimizer.h
@@ -262,7 +262,7 @@ MESHOPTIMIZER_EXPERIMENTAL void meshopt_decodeFilterExp(void* buffer, size_t ver
* The resulting index buffer references vertices from the original vertex buffer.
* If the original vertex data isn't required, creating a compact vertex buffer using meshopt_optimizeVertexFetch is recommended.
*
- * destination must contain enough space for the *source* index buffer (since optimization is iterative, this means index_count elements - *not* target_index_count!)
+ * destination must contain enough space for the target index buffer, worst case is index_count elements (*not* target_index_count)!
* vertex_positions should have float3 position in the first 12 bytes of each vertex - similar to glVertexPointer
* target_error represents the error relative to mesh extents that can be tolerated, e.g. 0.01 = 1% deformation
* result_error can be NULL; when it's not NULL, it will contain the resulting (relative) error after simplification
@@ -272,15 +272,17 @@ MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplify(unsigned int* destination, co
/**
* Experimental: Mesh simplifier (sloppy)
* Reduces the number of triangles in the mesh, sacrificing mesh apperance for simplification performance
- * The algorithm doesn't preserve mesh topology but is always able to reach target triangle count.
+ * The algorithm doesn't preserve mesh topology but can stop short of the target goal based on target error.
* Returns the number of indices after simplification, with destination containing new index data
* The resulting index buffer references vertices from the original vertex buffer.
* If the original vertex data isn't required, creating a compact vertex buffer using meshopt_optimizeVertexFetch is recommended.
*
- * destination must contain enough space for the target index buffer
+ * destination must contain enough space for the target index buffer, worst case is index_count elements (*not* target_index_count)!
* vertex_positions should have float3 position in the first 12 bytes of each vertex - similar to glVertexPointer
+ * target_error represents the error relative to mesh extents that can be tolerated, e.g. 0.01 = 1% deformation
+ * result_error can be NULL; when it's not NULL, it will contain the resulting (relative) error after simplification
*/
-MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplifySloppy(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count);
+MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplifySloppy(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float* result_error);
/**
* Experimental: Point cloud simplifier
@@ -289,7 +291,7 @@ MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplifySloppy(unsigned int* destinati
* The resulting index buffer references vertices from the original vertex buffer.
* If the original vertex data isn't required, creating a compact vertex buffer using meshopt_optimizeVertexFetch is recommended.
*
- * destination must contain enough space for the target index buffer
+ * destination must contain enough space for the target index buffer (target_vertex_count elements)
* vertex_positions should have float3 position in the first 12 bytes of each vertex - similar to glVertexPointer
*/
MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplifyPoints(unsigned int* destination, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_vertex_count);
@@ -533,7 +535,7 @@ inline int meshopt_decodeIndexSequence(T* destination, size_t index_count, const
template <typename T>
inline size_t meshopt_simplify(T* destination, const T* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float* result_error = 0);
template <typename T>
-inline size_t meshopt_simplifySloppy(T* destination, const T* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count);
+inline size_t meshopt_simplifySloppy(T* destination, const T* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float* result_error = 0);
template <typename T>
inline size_t meshopt_stripify(T* destination, const T* indices, size_t index_count, size_t vertex_count, T restart_index);
template <typename T>
@@ -855,12 +857,12 @@ inline size_t meshopt_simplify(T* destination, const T* indices, size_t index_co
}
template <typename T>
-inline size_t meshopt_simplifySloppy(T* destination, const T* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count)
+inline size_t meshopt_simplifySloppy(T* destination, const T* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float* result_error)
{
meshopt_IndexAdapter<T> in(0, indices, index_count);
- meshopt_IndexAdapter<T> out(destination, 0, target_index_count);
+ meshopt_IndexAdapter<T> out(destination, 0, index_count);
- return meshopt_simplifySloppy(out.data, in.data, index_count, vertex_positions, vertex_count, vertex_positions_stride, target_index_count);
+ return meshopt_simplifySloppy(out.data, in.data, index_count, vertex_positions, vertex_count, vertex_positions_stride, target_index_count, target_error, result_error);
}
template <typename T>
diff --git a/thirdparty/meshoptimizer/simplifier.cpp b/thirdparty/meshoptimizer/simplifier.cpp
index 5205b01172..942db14461 100644
--- a/thirdparty/meshoptimizer/simplifier.cpp
+++ b/thirdparty/meshoptimizer/simplifier.cpp
@@ -1400,7 +1400,7 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices,
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;
@@ -1412,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);
@@ -1431,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;
@@ -1471,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);
@@ -1503,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;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 03:16:17 +0000