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.

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<Geometry> &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<int> vertices_;
+  Map<int, int> global_to_local_vertices_;
   /** Edges written in the file in addition to (or even without polygon) elements. */
   Vector<MEdge> 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)},