Fix T99532: New OBJ importer in some cases fails to import faces

The importer code was written under incorrect assumption that vertex
data (v, vn, vt commands etc.) are grouped by object, i.e. follow the
o command, and that each object has its own vertex data commands. This
is not the case -- all the vertex data in the whole OBJ file is
"global", with no relation to any objects/groups; it's just that the
faces belong to the object, and then they pull in any vertices they
like.

This patch fixes this incorrect assumption in the importer:

- Vertex data is now properly global; no need to track some sort of
  "offsets" per object like it was doing before.
- For each object, face definitions track the minimum & maximum vertex
  indices referenced by the object, and then all that vertex range is
  created in the final Blender object. Note: it might be (unusual, but
  possible) that an object does not reference a sequential range of
  vertices, e.g. just a single face with vertex indices 1, 10, 100 --
  the resulting Blender mesh will have all the 100 vertices (some
  "loose" without belonging to a face). It should be possible to track
  the used vertices exactly (e.g. with a vector set), but I haven't
  done that for performance reasons.

Reviewed By: Howard Trickey
Differential Revision: https://developer.blender.org/D15410

# Conflicts:
#	source/blender/io/wavefront_obj/importer/obj_import_file_reader.cc
#	source/blender/io/wavefront_obj/importer/obj_import_mesh.cc
#	source/blender/io/wavefront_obj/importer/obj_import_objects.hh
#	source/blender/io/wavefront_obj/tests/obj_importer_tests.cc

4 files changed, 90 insertions, 90 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 f801bb1d3fa..6dd696d0c21 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
@@ -20,31 +20,24 @@ using std::string;
 /**
  * Based on the properties of the given Geometry instance, create a new Geometry instance
  * or return the previous one.
- *
- * Also update index offsets which should always happen if a new Geometry instance is created.
  */
 static Geometry *create_geometry(Geometry *const prev_geometry,
                                  const eGeometryType new_type,
                                  StringRef name,
-                                 const GlobalVertices &global_vertices,
-                                 Vector<std::unique_ptr<Geometry>> &r_all_geometries,
-                                 VertexIndexOffset &r_offset)
+                                 Vector<std::unique_ptr<Geometry>> &r_all_geometries)
 {
   auto new_geometry = [&]() {
     r_all_geometries.append(std::make_unique<Geometry>());
     Geometry *g = r_all_geometries.last().get();
     g->geom_type_ = new_type;
     g->geometry_name_ = name.is_empty() ? "New object" : name;
-    g->vertex_start_ = global_vertices.vertices.size();
-    r_offset.set_index_offset(g->vertex_start_);
     return g;
   };
 
   if (prev_geometry && prev_geometry->geom_type_ == GEOM_MESH) {
     /* After the creation of a Geometry instance, at least one element has been found in the OBJ
-     * file that indicates that it is a mesh (basically anything but the vertex positions). */
-    if (!prev_geometry->face_elements_.is_empty() || prev_geometry->has_vertex_normals_ ||
-        !prev_geometry->edges_.is_empty()) {
+     * file that indicates that it is a mesh (faces or edges). */
+    if (!prev_geometry->face_elements_.is_empty() || !prev_geometry->edges_.is_empty()) {
       return new_geometry();
     }
     if (new_type == GEOM_MESH) {
@@ -67,19 +60,14 @@ static Geometry *create_geometry(Geometry *const prev_geometry,
   return new_geometry();
 }
 
-static void geom_add_vertex(Geometry *geom,
-                            const StringRef line,
-                            GlobalVertices &r_global_vertices)
+static void geom_add_vertex(const StringRef line, GlobalVertices &r_global_vertices)
 {
   float3 vert;
   parse_floats(line, 0.0f, vert, 3);
   r_global_vertices.vertices.append(vert);
-  geom->vertex_count_++;
 }
 
-static void geom_add_vertex_normal(Geometry *geom,
-                                   const StringRef line,
-                                   GlobalVertices &r_global_vertices)
+static void geom_add_vertex_normal(const StringRef line, GlobalVertices &r_global_vertices)
 {
   float3 normal;
   parse_floats(line, 0.0f, normal, 3);
@@ -88,7 +76,6 @@ static void geom_add_vertex_normal(Geometry *geom,
    * normalized. */
   normalize_v3(normal);
   r_global_vertices.vertex_normals.append(normal);
-  geom->has_vertex_normals_ = true;
 }
 
 static void geom_add_uv_vertex(const StringRef line, GlobalVertices &r_global_vertices)
@@ -98,25 +85,23 @@ static void geom_add_uv_vertex(const StringRef line, GlobalVertices &r_global_ve
   r_global_vertices.uv_vertices.append(uv);
 }
 
-static void geom_add_edge(Geometry *geom,
-                          StringRef line,
-                          const VertexIndexOffset &offsets,
-                          GlobalVertices &r_global_vertices)
+static void geom_add_edge(Geometry *geom, StringRef line, GlobalVertices &r_global_vertices)
 {
   int edge_v1, edge_v2;
   line = parse_int(line, -1, edge_v1);
   line = parse_int(line, -1, edge_v2);
   /* Always keep stored indices non-negative and zero-based. */
-  edge_v1 += edge_v1 < 0 ? r_global_vertices.vertices.size() : -offsets.get_index_offset() - 1;
-  edge_v2 += edge_v2 < 0 ? r_global_vertices.vertices.size() : -offsets.get_index_offset() - 1;
+  edge_v1 += edge_v1 < 0 ? r_global_vertices.vertices.size() : -1;
+  edge_v2 += edge_v2 < 0 ? r_global_vertices.vertices.size() : -1;
   BLI_assert(edge_v1 >= 0 && edge_v2 >= 0);
   geom->edges_.append({static_cast<uint>(edge_v1), static_cast<uint>(edge_v2)});
+  geom->track_vertex_index(edge_v1);
+  geom->track_vertex_index(edge_v2);
 }
 
 static void geom_add_polygon(Geometry *geom,
                              StringRef line,
                              const GlobalVertices &global_vertices,
-                             const VertexIndexOffset &offsets,
                              const int material_index,
                              const int group_index,
                              const bool shaded_smooth)
@@ -155,8 +140,7 @@ static void geom_add_polygon(Geometry *geom,
       }
     }
     /* Always keep stored indices non-negative and zero-based. */
-    corner.vert_index += corner.vert_index < 0 ? global_vertices.vertices.size() :
-                                                 -offsets.get_index_offset() - 1;
+    corner.vert_index += corner.vert_index < 0 ? global_vertices.vertices.size() : -1;
     if (corner.vert_index < 0 || corner.vert_index >= global_vertices.vertices.size()) {
       fprintf(stderr,
               "Invalid vertex index %i (valid range [0, %zu)), ignoring face\n",
@@ -164,6 +148,9 @@ static void geom_add_polygon(Geometry *geom,
               (size_t)global_vertices.vertices.size());
       face_valid = false;
     }
+    else {
+      geom->track_vertex_index(corner.vert_index);
+    }
     if (got_uv) {
       corner.uv_vert_index += corner.uv_vert_index < 0 ? global_vertices.uv_vertices.size() : -1;
       if (corner.uv_vert_index < 0 || corner.uv_vert_index >= global_vertices.uv_vertices.size()) {
@@ -177,7 +164,7 @@ static void geom_add_polygon(Geometry *geom,
     /* Ignore corner normal index, if the geometry does not have any normals.
      * Some obj files out there do have face definitions that refer to normal indices,
      * without any normals being present (T98782). */
-    if (got_normal && geom->has_vertex_normals_) {
+    if (got_normal && !global_vertices.vertex_normals.is_empty()) {
       corner.vertex_normal_index += corner.vertex_normal_index < 0 ?
                                         global_vertices.vertex_normals.size() :
                                         -1;
@@ -210,17 +197,14 @@ static void geom_add_polygon(Geometry *geom,
 
 static Geometry *geom_set_curve_type(Geometry *geom,
                                      const StringRef rest_line,
-                                     const GlobalVertices &global_vertices,
                                      const StringRef group_name,
-                                     VertexIndexOffset &r_offsets,
                                      Vector<std::unique_ptr<Geometry>> &r_all_geometries)
 {
   if (rest_line.find("bspline") == StringRef::not_found) {
     std::cerr << "Curve type not supported:'" << rest_line << "'" << std::endl;
     return geom;
   }
-  geom = create_geometry(
-      geom, GEOM_CURVE, group_name, global_vertices, r_all_geometries, r_offsets);
+  geom = create_geometry(geom, GEOM_CURVE, group_name, r_all_geometries);
   geom->nurbs_element_.group_ = group_name;
   return geom;
 }
@@ -350,9 +334,7 @@ void OBJParser::parse(Vector<std::unique_ptr<Geometry>> &r_all_geometries,
   BLI_strncpy(ob_name, BLI_path_basename(import_params_.filepath), FILE_MAXFILE);
   BLI_path_extension_replace(ob_name, FILE_MAXFILE, "");
 
-  VertexIndexOffset offsets;
-  Geometry *curr_geom = create_geometry(
-      nullptr, GEOM_MESH, ob_name, r_global_vertices, r_all_geometries, offsets);
+  Geometry *curr_geom = create_geometry(nullptr, GEOM_MESH, ob_name, r_all_geometries);
 
   /* State variables: once set, they remain the same for the remaining
    * elements in the object. */
@@ -424,10 +406,10 @@ void OBJParser::parse(Vector<std::unique_ptr<Geometry>> &r_all_geometries,
       /* Most common things that start with 'v': vertices, normals, UVs. */
       if (line[0] == 'v') {
         if (parse_keyword(line, "v")) {
-          geom_add_vertex(curr_geom, line, r_global_vertices);
+          geom_add_vertex(line, r_global_vertices);
         }
         else if (parse_keyword(line, "vn")) {
-          geom_add_vertex_normal(curr_geom, line, r_global_vertices);
+          geom_add_vertex_normal(line, r_global_vertices);
         }
         else if (parse_keyword(line, "vt")) {
           geom_add_uv_vertex(line, r_global_vertices);
@@ -438,22 +420,20 @@ void OBJParser::parse(Vector<std::unique_ptr<Geometry>> &r_all_geometries,
         geom_add_polygon(curr_geom,
                          line,
                          r_global_vertices,
-                         offsets,
                          state_material_index,
-                         state_group_index, /* TODO was wrongly material name! */
+                         state_group_index,
                          state_shaded_smooth);
       }
       /* Faces. */
       else if (parse_keyword(line, "l")) {
-        geom_add_edge(curr_geom, line, offsets, r_global_vertices);
+        geom_add_edge(curr_geom, line, r_global_vertices);
       }
       /* Objects. */
       else if (parse_keyword(line, "o")) {
         state_shaded_smooth = false;
         state_group_name = "";
         state_material_name = "";
-        curr_geom = create_geometry(
-            curr_geom, GEOM_MESH, line.trim(), r_global_vertices, r_all_geometries, offsets);
+        curr_geom = create_geometry(curr_geom, GEOM_MESH, line.trim(), r_all_geometries);
       }
       /* Groups. */
       else if (parse_keyword(line, "g")) {
@@ -487,8 +467,7 @@ void OBJParser::parse(Vector<std::unique_ptr<Geometry>> &r_all_geometries,
       }
       /* Curve related things. */
       else if (parse_keyword(line, "cstype")) {
-        curr_geom = geom_set_curve_type(
-            curr_geom, line, r_global_vertices, state_group_name, offsets, r_all_geometries);
+        curr_geom = geom_set_curve_type(curr_geom, line, state_group_name, r_all_geometries);
       }
       else if (parse_keyword(line, "deg")) {
         geom_set_curve_degree(curr_geom, line);
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 2f5f160afaf..e80ea32ab22 100644
--- a/source/blender/io/wavefront_obj/importer/obj_import_mesh.cc
+++ b/source/blender/io/wavefront_obj/importer/obj_import_mesh.cc
@@ -30,13 +30,17 @@ Object *MeshFromGeometry::create_mesh(Main *bmain,
                                       Map<std::string, Material *> &created_materials,
                                       const OBJImportParams &import_params)
 {
+  const int64_t tot_verts_object{mesh_geometry_.get_vertex_count()};
+  if (tot_verts_object <= 0) {
+    /* Empty mesh */
+    return nullptr;
+  }
   std::string ob_name{mesh_geometry_.geometry_name_};
   if (ob_name.empty()) {
     ob_name = "Untitled";
   }
   fixup_invalid_faces();
 
-  const int64_t tot_verts_object{mesh_geometry_.vertex_count_};
   /* Total explicitly imported edges, not the ones belonging the polygons to be created. */
   const int64_t tot_edges{mesh_geometry_.edges_.size()};
   const int64_t tot_face_elems{mesh_geometry_.face_elements_.size()};
@@ -151,9 +155,9 @@ void MeshFromGeometry::fixup_invalid_faces()
 
 void MeshFromGeometry::create_vertices(Mesh *mesh)
 {
-  const int tot_verts_object{mesh_geometry_.vertex_count_};
+  const int tot_verts_object{mesh_geometry_.get_vertex_count()};
   for (int i = 0; i < tot_verts_object; ++i) {
-    int vi = mesh_geometry_.vertex_start_ + i;
+    int vi = mesh_geometry_.vertex_index_min_ + i;
     if (vi < global_vertices_.vertices.size()) {
       copy_v3_v3(mesh->mvert[i].co, global_vertices_.vertices[vi]);
     }
@@ -168,7 +172,7 @@ void MeshFromGeometry::create_vertices(Mesh *mesh)
 void MeshFromGeometry::create_polys_loops(Mesh *mesh, bool use_vertex_groups)
 {
   mesh->dvert = nullptr;
-  const int64_t total_verts = mesh_geometry_.vertex_count_;
+  const int64_t total_verts = mesh_geometry_.get_vertex_count();
   if (use_vertex_groups && total_verts && mesh_geometry_.has_vertex_groups_) {
     mesh->dvert = static_cast<MDeformVert *>(
         CustomData_add_layer(&mesh->vdata, CD_MDEFORMVERT, CD_CALLOC, nullptr, total_verts));
@@ -202,7 +206,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;
+      mloop.v = curr_corner.vert_index - mesh_geometry_.vertex_index_min_;
 
       /* Setup vertex group data, if needed. */
       if (!mesh->dvert) {
@@ -229,14 +233,14 @@ void MeshFromGeometry::create_vertex_groups(Object *obj)
 void MeshFromGeometry::create_edges(Mesh *mesh)
 {
   const int64_t tot_edges{mesh_geometry_.edges_.size()};
-  const int64_t total_verts{mesh_geometry_.vertex_count_};
+  const int64_t total_verts{mesh_geometry_.get_vertex_count()};
   UNUSED_VARS_NDEBUG(total_verts);
   for (int i = 0; i < tot_edges; ++i) {
     const MEdge &src_edge = mesh_geometry_.edges_[i];
     MEdge &dst_edge = mesh->medge[i];
-    BLI_assert(src_edge.v1 < total_verts && src_edge.v2 < total_verts);
-    dst_edge.v1 = src_edge.v1;
-    dst_edge.v2 = src_edge.v2;
+    dst_edge.v1 = src_edge.v1 - mesh_geometry_.vertex_index_min_;
+    dst_edge.v2 = src_edge.v2 - mesh_geometry_.vertex_index_min_;
+    BLI_assert(dst_edge.v1 < total_verts && dst_edge.v2 < total_verts);
     dst_edge.flag = ME_LOOSEEDGE;
   }
 
@@ -311,10 +315,8 @@ void MeshFromGeometry::create_materials(Main *bmain,
 
 void MeshFromGeometry::create_normals(Mesh *mesh)
 {
-  /* NOTE: Needs more clarity about what is expected in the viewport if the function works. */
-
   /* No normal data: nothing to do. */
-  if (global_vertices_.vertex_normals.is_empty() || !mesh_geometry_.has_vertex_normals_) {
+  if (global_vertices_.vertex_normals.is_empty()) {
     return;
   }
 
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 9356d120f04..3ec783c7640 100644
--- a/source/blender/io/wavefront_obj/importer/obj_import_objects.hh
+++ b/source/blender/io/wavefront_obj/importer/obj_import_objects.hh
@@ -19,8 +19,7 @@
 namespace blender::io::obj {
 
 /**
- * List of all vertex and UV vertex coordinates in an OBJ file accessible to any
- * Geometry instance at any time.
+ * All vertex positions, normals, UVs, colors in the OBJ file.
  */
 struct GlobalVertices {
   Vector<float3> vertices;
@@ -29,27 +28,6 @@ struct GlobalVertices {
 };
 
 /**
- * Keeps track of the vertices that belong to other Geometries.
- * Needed only for MLoop.v and MEdge.v1 which needs vertex indices ranging from (0 to total
- * vertices in the mesh) as opposed to the other OBJ indices ranging from (0 to total vertices
- * in the global list).
- */
-struct VertexIndexOffset {
- private:
-  int offset_ = 0;
-
- public:
-  void set_index_offset(const int64_t total_vertices)
-  {
-    offset_ = total_vertices;
-  }
-  int64_t get_index_offset() const
-  {
-    return offset_;
-  }
-};
-
-/**
  * A face's corner in an OBJ file. In Blender, it translates to a mloop vertex.
  */
 struct PolyCorner {
@@ -100,8 +78,8 @@ struct Geometry {
   Map<std::string, int> material_indices_;
   Vector<std::string> material_order_;
 
-  int vertex_start_ = 0;
-  int vertex_count_ = 0;
+  int vertex_index_min_ = INT_MAX;
+  int vertex_index_max_ = -1;
   /** Edges written in the file in addition to (or even without polygon) elements. */
   Vector<MEdge> edges_;
 
@@ -109,10 +87,21 @@ struct Geometry {
   Vector<PolyElem> face_elements_;
 
   bool has_invalid_polys_ = false;
-  bool has_vertex_normals_ = false;
   bool has_vertex_groups_ = false;
   NurbsElement nurbs_element_;
   int total_loops_ = 0;
+
+  int get_vertex_count() const
+  {
+    if (vertex_index_max_ < vertex_index_min_)
+      return 0;
+    return vertex_index_max_ - vertex_index_min_ + 1;
+  }
+  void track_vertex_index(int index)
+  {
+    vertex_index_min_ = std::min(vertex_index_min_, index);
+    vertex_index_max_ = std::max(vertex_index_max_, index);
+  }
 };
 
 }  // namespace blender::io::obj
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 faccac7d079..4c7e06e5a00 100644
--- a/source/blender/io/wavefront_obj/tests/obj_importer_tests.cc
+++ b/source/blender/io/wavefront_obj/tests/obj_importer_tests.cc
@@ -148,6 +148,36 @@ TEST_F(obj_importer_test, import_cube)
   import_and_check("cube.obj", expect, std::size(expect), 1);
 }
 
+TEST_F(obj_importer_test, import_cube_o_after_verts)
+{
+  Expectation expect[] = {
+      {"OBCube", OB_MESH, 8, 12, 6, 24, float3(1, 1, -1), float3(-1, 1, 1)},
+      {
+          "OBActualCube",
+          OB_MESH,
+          8,
+          12,
+          6,
+          24,
+          float3(-1, -1, 1),
+          float3(1, -1, -1),
+          float3(0, 0, 1),
+      },
+      {
+          "OBSparseTri",
+          OB_MESH,
+          6,
+          3,
+          1,
+          3,
+          float3(1, -1, 1),
+          float3(-2, -2, 2),
+          float3(-0.2357f, 0.9428f, 0.2357f),
+      },
+  };
+  import_and_check("cube_o_after_verts.obj", expect, std::size(expect), 2);
+}
+
 TEST_F(obj_importer_test, import_suzanne_all_data)
 {
   Expectation expect[] = {
@@ -283,13 +313,13 @@ TEST_F(obj_importer_test, import_faces_invalid_or_with_holes)
        float3(1, 0, -1)},
       {"OBFaceQuadDupSomeVerts_BecomesOneQuadUsing4Verts",
        OB_MESH,
-       8,
+       4,
        4,
        1,
        4,
        float3(3, 0, -2),
-       float3(6, 0, -1)},
-      {"OBFaceTriDupVert_Becomes1Tri", OB_MESH, 8, 3, 1, 3, float3(-2, 0, 3), float3(1, 0, 4)},
+       float3(7, 0, -2)},
+      {"OBFaceTriDupVert_Becomes1Tri", OB_MESH, 3, 3, 1, 3, float3(-2, 0, 3), float3(2, 0, 7)},
       {"OBFaceAllVertsDup_BecomesOneOverlappingFaceUsingAllVerts",
        OB_MESH,
        8,
@@ -306,7 +336,7 @@ TEST_F(obj_importer_test, import_faces_invalid_or_with_holes)
        8,
        float3(8, 0, -2),
        float3(11, 0, -1)},
-      {"OBFaceJustTwoVerts_IsSkipped", OB_MESH, 8, 0, 0, 0, float3(8, 0, 3), float3(11, 0, 4)},
+      {"OBFaceJustTwoVerts_IsSkipped", OB_MESH, 2, 0, 0, 0, float3(8, 0, 3), float3(8, 0, 7)},
   };
   import_and_check("faces_invalid_or_with_holes.obj", expect, std::size(expect), 0);
 }
@@ -317,12 +347,12 @@ TEST_F(obj_importer_test, import_invalid_indices)
       {"OBCube", OB_MESH, 8, 12, 6, 24, float3(1, 1, -1), float3(-1, 1, 1)},
       {"OBQuad",
        OB_MESH,
-       4,
+       3,
        3,
        1,
        3,
        float3(-2, 0, -2),
-       float3(2, 0, -2),
+       float3(2, 0, 2),
        float3(0, 1, 0),
        float2(0.5f, 0.25f)},
   };
@@ -335,12 +365,12 @@ TEST_F(obj_importer_test, import_invalid_syntax)
       {"OBCube", OB_MESH, 8, 12, 6, 24, float3(1, 1, -1), float3(-1, 1, 1)},
       {"OBObjectWithAReallyLongNameToCheckHowImportHandlesNamesThatAreLon",
        OB_MESH,
-       10, /* Note: right now parses some invalid obj syntax as valid vertices. */
+       3,
        3,
        1,
        3,
        float3(1, 2, 3),
-       float3(10, 11, 12),
+       float3(7, 8, 9),
        float3(0, 1, 0),
        float2(0.5f, 0.25f)},
   };