From d76583cb4a16315c196f07f4acb9340f341bee47 Mon Sep 17 00:00:00 2001 From: Aras Pranckevicius Date: Wed, 10 Aug 2022 13:34:42 +0300 Subject: Fix T100302: New OBJ importer produces too many vertices when faces don't span a continuous range As part of the previous fix (D15410), the importer got code to track min & max vertex indices used as part of the mesh faces. However, if faces refer to a "sparse" (i.e. non-contiguous) subset of all vertices, then the imported mesh would contain all the vertices between min & max range. Replace that with proper tracking of actually used vertex indices for each imported mesh. Fixes T100302. This does affect import performance a tiny bit, e.g. importing Blender 3.0 splash scene goes 21.7s -> 22.1s, and importing rungholt.obj goes 2.37s -> 2.48s. Importer related tests have a bunch of vertex changes in them, since now vertices are added in the order that the faces are referring to them. Which incidentally matches the order that the Python based importer was creating them too. --- .../importer/obj_import_file_reader.cc | 3 +- .../io/wavefront_obj/importer/obj_import_mesh.cc | 14 ++-- .../wavefront_obj/importer/obj_import_objects.hh | 25 +++++-- .../io/wavefront_obj/tests/obj_importer_tests.cc | 86 +++++++++++----------- 4 files changed, 71 insertions(+), 57 deletions(-) diff --git a/source/blender/io/wavefront_obj/importer/obj_import_file_reader.cc b/source/blender/io/wavefront_obj/importer/obj_import_file_reader.cc index 8594603867f..7069e1185e0 100644 --- a/source/blender/io/wavefront_obj/importer/obj_import_file_reader.cc +++ b/source/blender/io/wavefront_obj/importer/obj_import_file_reader.cc @@ -406,8 +406,7 @@ static void use_all_vertices_if_no_faces(Geometry *geom, all_geometries.begin(), all_geometries.end(), [](const std::unique_ptr &g) { return g->get_vertex_count() == 0; })) { - geom->track_vertex_index(0); - geom->track_vertex_index(global_vertices.vertices.size() - 1); + geom->track_all_vertices(global_vertices.vertices.size()); } } } diff --git a/source/blender/io/wavefront_obj/importer/obj_import_mesh.cc b/source/blender/io/wavefront_obj/importer/obj_import_mesh.cc index d7b2bc2e67c..e62470588ec 100644 --- a/source/blender/io/wavefront_obj/importer/obj_import_mesh.cc +++ b/source/blender/io/wavefront_obj/importer/obj_import_mesh.cc @@ -157,17 +157,17 @@ void MeshFromGeometry::fixup_invalid_faces() void MeshFromGeometry::create_vertices(Mesh *mesh) { - const int tot_verts_object{mesh_geometry_.get_vertex_count()}; - for (int i = 0; i < tot_verts_object; ++i) { - int vi = mesh_geometry_.vertex_index_min_ + i; + int mi = 0; + for (int vi : mesh_geometry_.vertices_) { if (vi < global_vertices_.vertices.size()) { - copy_v3_v3(mesh->mvert[i].co, global_vertices_.vertices[vi]); + copy_v3_v3(mesh->mvert[mi].co, global_vertices_.vertices[vi]); } else { std::cerr << "Vertex index:" << vi << " larger than total vertices:" << global_vertices_.vertices.size() << " ." << std::endl; } + ++mi; } } @@ -208,7 +208,7 @@ void MeshFromGeometry::create_polys_loops(Mesh *mesh, bool use_vertex_groups) const PolyCorner &curr_corner = mesh_geometry_.face_corners_[curr_face.start_index_ + idx]; MLoop &mloop = mesh->mloop[tot_loop_idx]; tot_loop_idx++; - mloop.v = curr_corner.vert_index - mesh_geometry_.vertex_index_min_; + mloop.v = mesh_geometry_.global_to_local_vertices_.lookup_default(curr_corner.vert_index, 0); /* Setup vertex group data, if needed. */ if (!mesh->dvert) { @@ -240,8 +240,8 @@ void MeshFromGeometry::create_edges(Mesh *mesh) for (int i = 0; i < tot_edges; ++i) { const MEdge &src_edge = mesh_geometry_.edges_[i]; MEdge &dst_edge = mesh->medge[i]; - dst_edge.v1 = src_edge.v1 - mesh_geometry_.vertex_index_min_; - dst_edge.v2 = src_edge.v2 - mesh_geometry_.vertex_index_min_; + dst_edge.v1 = mesh_geometry_.global_to_local_vertices_.lookup_default(src_edge.v1, 0); + dst_edge.v2 = mesh_geometry_.global_to_local_vertices_.lookup_default(src_edge.v2, 0); BLI_assert(dst_edge.v1 < total_verts && dst_edge.v2 < total_verts); dst_edge.flag = ME_LOOSEEDGE; } diff --git a/source/blender/io/wavefront_obj/importer/obj_import_objects.hh b/source/blender/io/wavefront_obj/importer/obj_import_objects.hh index 9f0079d7c53..f48b6dd55e8 100644 --- a/source/blender/io/wavefront_obj/importer/obj_import_objects.hh +++ b/source/blender/io/wavefront_obj/importer/obj_import_objects.hh @@ -9,6 +9,7 @@ #include "BKE_lib_id.h" #include "BLI_map.hh" +#include "BLI_math_base.hh" #include "BLI_math_vec_types.hh" #include "BLI_vector.hh" #include "BLI_vector_set.hh" @@ -92,6 +93,8 @@ struct Geometry { int vertex_index_min_ = INT_MAX; int vertex_index_max_ = -1; + VectorSet vertices_; + Map global_to_local_vertices_; /** Edges written in the file in addition to (or even without polygon) elements. */ Vector edges_; @@ -105,14 +108,26 @@ struct Geometry { int get_vertex_count() const { - if (vertex_index_max_ < vertex_index_min_) - return 0; - return vertex_index_max_ - vertex_index_min_ + 1; + return (int)vertices_.size(); } void track_vertex_index(int index) { - vertex_index_min_ = std::min(vertex_index_min_, index); - vertex_index_max_ = std::max(vertex_index_max_, index); + if (vertices_.add(index)) { + global_to_local_vertices_.add_new(index, (int)vertices_.size() - 1); + } + math::min_inplace(vertex_index_min_, index); + math::max_inplace(vertex_index_max_, index); + } + void track_all_vertices(int count) + { + vertices_.reserve(count); + global_to_local_vertices_.reserve(count); + for (int i = 0; i < count; ++i) { + vertices_.add(i); + global_to_local_vertices_.add(i, i); + } + vertex_index_min_ = 0; + vertex_index_max_ = count - 1; } }; diff --git a/source/blender/io/wavefront_obj/tests/obj_importer_tests.cc b/source/blender/io/wavefront_obj/tests/obj_importer_tests.cc index 339f672c3e0..63c827d385f 100644 --- a/source/blender/io/wavefront_obj/tests/obj_importer_tests.cc +++ b/source/blender/io/wavefront_obj/tests/obj_importer_tests.cc @@ -153,7 +153,7 @@ TEST_F(obj_importer_test, import_cube) 12, 6, 24, - float3(-1, -1, 1), + float3(1, -1, 1), float3(1, -1, -1), float3(-0.57735f, 0.57735f, -0.57735f)}, }; @@ -171,19 +171,19 @@ TEST_F(obj_importer_test, import_cube_o_after_verts) 12, 6, 24, - float3(-1, -1, 1), + float3(1, -1, 1), float3(1, -1, -1), float3(0, 0, 1), }, { "OBSparseTri", OB_MESH, - 6, + 3, 3, 1, 3, - float3(1, -1, 1), float3(-2, -2, 2), + float3(-1, -1, -1), float3(-0.2357f, 0.9428f, 0.2357f), }, }; @@ -200,8 +200,8 @@ TEST_F(obj_importer_test, import_suzanne_all_data) 1005, 500, 1968, - float3(-0.4375f, 0.164062f, 0.765625f), - float3(0.4375f, 0.164062f, 0.765625f), + float3(-0.5f, 0.09375f, 0.6875f), + float3(0.546875f, 0.054688f, 0.578125f), float3(-0.6040f, -0.5102f, 0.6122f), float2(0.692094f, 0.40191f)}, }; @@ -306,7 +306,7 @@ TEST_F(obj_importer_test, import_materials) { Expectation expect[] = { {"OBCube", OB_MESH, 8, 12, 6, 24, float3(1, 1, -1), float3(-1, 1, 1)}, - {"OBmaterials", OB_MESH, 8, 12, 6, 24, float3(-1, -1, 1), float3(1, -1, -1)}, + {"OBmaterials", OB_MESH, 8, 12, 6, 24, float3(1, -1, 1), float3(1, -1, -1)}, }; import_and_check("materials.obj", expect, std::size(expect), 4, 8); } @@ -322,7 +322,7 @@ TEST_F(obj_importer_test, import_cubes_with_textures_rel) 6, 24, float3(1, 1, -1), - float3(-1, -1, 1), + float3(1, -1, -1), float3(0, 1, 0), float2(0.9935f, 0.0020f)}, {"OBCubeTiledTex", @@ -332,7 +332,7 @@ TEST_F(obj_importer_test, import_cubes_with_textures_rel) 6, 24, float3(4, 1, -1), - float3(2, -1, 1), + float3(4, -1, -1), float3(0, 1, 0), float2(0.9935f, 0.0020f)}, {"OBCubeTiledTexFromAnotherFolder", @@ -342,7 +342,7 @@ TEST_F(obj_importer_test, import_cubes_with_textures_rel) 6, 24, float3(7, 1, -1), - float3(5, -1, 1), + float3(7, -1, -1), float3(0, 1, 0), float2(0.9935f, 0.0020f)}, }; @@ -433,15 +433,15 @@ TEST_F(obj_importer_test, import_all_objects) {"OBCube", OB_MESH, 8, 12, 6, 24, float3(1, 1, -1), float3(-1, 1, 1)}, /* .obj file has empty EmptyText and EmptyMesh objects; these are ignored and skipped */ {"OBBezierCurve", OB_MESH, 13, 12, 0, 0, float3(-1, -2, 0), float3(1, -2, 0)}, - {"OBBlankCube", OB_MESH, 8, 13, 7, 26, float3(1, 1, -1), float3(-1, 1, 1), float3(0, 0, 1)}, + {"OBBlankCube", OB_MESH, 8, 13, 7, 26, float3(1, 1, 1), float3(-1, 1, -1), float3(0, 0, 1)}, {"OBMaterialCube", OB_MESH, 8, 13, 7, 26, - float3(28, 1, -1), - float3(26, 1, 1), + float3(26, -1, -1), + float3(28, -1, -1), float3(-1, 0, 0)}, {"OBNurbsCircle", OB_MESH, @@ -451,15 +451,15 @@ TEST_F(obj_importer_test, import_all_objects) 0, float3(3.292893f, -2.707107f, 0), float3(3.369084f, -2.77607f, 0)}, - {"OBNurbsCircle.001", OB_MESH, 4, 4, 0, 0, float3(2, -3, 0), float3(3, -2, 0)}, + {"OBNurbsCircle.001", OB_MESH, 4, 4, 0, 0, float3(3, -2, 0), float3(2, -1, 0)}, {"OBParticleCube", OB_MESH, 8, 13, 7, 26, - float3(22, 1, -1), - float3(20, 1, 1), + float3(22, 1, 1), + float3(20, 1, -1), float3(0, 0, 1)}, {"OBShapeKeyCube", OB_MESH, @@ -467,8 +467,8 @@ TEST_F(obj_importer_test, import_all_objects) 13, 7, 26, - float3(19, 1, -1), - float3(17, 1, 1), + float3(19, 1, 2), + float3(17, 1, -1), float3(-0.4082f, -0.4082f, 0.8165f)}, {"OBSmoothCube", OB_MESH, @@ -476,8 +476,8 @@ TEST_F(obj_importer_test, import_all_objects) 13, 7, 26, - float3(4, 1, -1), - float3(2, 1, 1), + float3(4, 1, 1), + float3(2, 1, -1), float3(0.5774f, 0.5773f, 0.5774f)}, {"OBSurface", OB_MESH, @@ -485,7 +485,7 @@ TEST_F(obj_importer_test, import_all_objects) 480, 224, 896, - float3(7.292893f, -2.707107f, -1), + float3(7.292893f, -2.707107f, -0.714285f), float3(7.525872f, -2.883338f, 1), float3(-0.7071f, -0.7071f, 0), float2(0, 0.142857f)}, @@ -495,7 +495,7 @@ TEST_F(obj_importer_test, import_all_objects) 480, 225, 900, - float3(12.5f, -2.5f, 0.694444f), + float3(12.56667f, -2.5f, 0.72037f), float3(13.5f, -1.5f, 0.694444f), float3(-0.3246f, -0.3531f, 0.8775f), float2(0, 0.066667f)}, @@ -516,7 +516,7 @@ TEST_F(obj_importer_test, import_all_objects) 1024, 4096, float3(5.34467f, -2.65533f, -0.176777f), - float3(5.232792f, -2.411795f, -0.220835f), + float3(5.158205f, -2.234695f, -0.220835f), float3(-0.5042f, -0.5042f, -0.7011f), float2(0, 1)}, {"OBTaperCube", @@ -525,8 +525,8 @@ TEST_F(obj_importer_test, import_all_objects) 208, 104, 416, - float3(24.444445f, 0.502543f, -0.753814f), - float3(23.790743f, 0.460522f, -0.766546f), + float3(24.316156f, 0.345556f, 0.796778f), + float3(23.551804f, 0.389113f, -0.639607f), float3(-0.0546f, 0.1716f, 0.9837f)}, {"OBText", OB_MESH, @@ -534,8 +534,8 @@ TEST_F(obj_importer_test, import_all_objects) 345, 171, 513, - float3(1.75f, -9.458f, 0), - float3(0.587f, -9.406f, 0), + float3(1.583f, -9.621f, 0), + float3(0.351f, -10.0f, 0), float3(0, 0, 1), float2(0.017544f, 0)}, {"OBUVCube", @@ -544,8 +544,8 @@ TEST_F(obj_importer_test, import_all_objects) 13, 7, 26, - float3(7, 1, -1), - float3(5, 1, 1), + float3(7, 1, 1), + float3(5, 1, -1), float3(0, 0, 1), float2(0.654526f, 0.579873f)}, {"OBUVImageCube", @@ -554,8 +554,8 @@ TEST_F(obj_importer_test, import_all_objects) 13, 7, 26, - float3(10, 1, -1), - float3(8, 1, 1), + float3(10, 1, 1), + float3(8, 1, -1), float3(0, 0, 1), float2(0.654526f, 0.579873f)}, {"OBVColCube", @@ -564,8 +564,8 @@ TEST_F(obj_importer_test, import_all_objects) 13, 7, 26, - float3(13, 1, -1), - float3(11, 1, 1), + float3(13, 1, 1), + float3(11, 1, -1), float3(0, 0, 1), float2(0, 0), float4(0.0f, 0.002125f, 1.0f, 1.0f)}, @@ -575,8 +575,8 @@ TEST_F(obj_importer_test, import_all_objects) 13, 7, 26, - float3(16, 1, -1), - float3(14, 1, 1), + float3(16, 1, 1), + float3(14, 1, -1), float3(0, 0, 1)}, }; import_and_check("all_objects.obj", expect, std::size(expect), 7); @@ -593,7 +593,7 @@ TEST_F(obj_importer_test, import_cubes_vertex_colors) 6, 24, float3(1.0f, 1.0f, -3.812445f), - float3(-1.0f, -1.0f, -1.812445f), + float3(1.0f, -1.0f, -3.812445f), float3(0, 0, 0), float2(0, 0), float4(0.89627f, 0.036889f, 0.47932f, 1.0f)}, @@ -604,7 +604,7 @@ TEST_F(obj_importer_test, import_cubes_vertex_colors) 6, 24, float3(3.481967f, 1.0f, -3.812445f), - float3(1.481967f, -1.0f, -1.812445f), + float3(3.481967f, -1.0f, -3.812445f), float3(0, 0, 0), float2(0, 0), float4(1.564582f, 0.039217f, 0.664309f, 1.0f)}, @@ -615,7 +615,7 @@ TEST_F(obj_importer_test, import_cubes_vertex_colors) 6, 24, float3(-4.725068f, -1.0f, 1.0f), - float3(-2.725068f, 1.0f, -1.0f), + float3(-2.725068f, -1.0f, 1.0f), float3(0, 0, 0), float2(0, 0), float4(0.270498f, 0.47932f, 0.262251f, 1.0f)}, @@ -626,7 +626,7 @@ TEST_F(obj_importer_test, import_cubes_vertex_colors) 6, 24, float3(-4.550208f, -1.0f, -1.918042f), - float3(-2.550208f, 1.0f, -3.918042f)}, + float3(-2.550208f, -1.0f, -1.918042f)}, {"OBCubeVertexByte", OB_MESH, 8, @@ -634,7 +634,7 @@ TEST_F(obj_importer_test, import_cubes_vertex_colors) 6, 24, float3(1.0f, 1.0f, -1.0f), - float3(-1.0f, -1.0f, 1.0f), + float3(1.0f, -1.0f, -1.0f), float3(0, 0, 0), float2(0, 0), float4(0.846873f, 0.027321f, 0.982123f, 1.0f)}, @@ -645,7 +645,7 @@ TEST_F(obj_importer_test, import_cubes_vertex_colors) 6, 24, float3(3.392028f, 1.0f, -1.0f), - float3(1.392028f, -1.0f, 1.0f), + float3(3.392028f, -1.0f, -1.0f), float3(0, 0, 0), float2(0, 0), float4(49.99467f, 0.027321f, 0.982123f, 1.0f)}, @@ -664,7 +664,7 @@ TEST_F(obj_importer_test, import_cubes_vertex_colors_mrgb) 6, 24, float3(4, 1, -1), - float3(2, -1, 1), + float3(4, -1, -1), float3(0, 0, 0), float2(0, 0), float4(0.8714f, 0.6308f, 0.5271f, 1.0f)}, @@ -675,7 +675,7 @@ TEST_F(obj_importer_test, import_cubes_vertex_colors_mrgb) 6, 24, float3(1, 1, -1), - float3(-1, -1, 1), + float3(1, -1, -1), float3(0, 0, 0), float2(0, 0), float4(0.6038f, 0.3185f, 0.1329f, 1.0f)}, -- cgit v1.2.3