OpenSubdiv: Optimize faces storage in mesh topology

Avoid per-face pointer and allocation: store everything as continuous
arrays.

Memory footprint for 1.5M faces:

- Theoretical worst case (all vertices and edges have crease) memory
  goes down from 114 MiB to 96 MiB (15% improvement).

  This case is not currently achievable since Blender does not expose
  vertex crease yet.

- Current real life worst case (all edges have crease) memory goes
  down from 108 MiB to 90 MiB (17% improvement).

- Best case (no creases at all) memory goes down from 96 MiB to 78 MiB
  (19% improvement).

4 files changed, 118 insertions, 55 deletions

diff --git a/intern/opensubdiv/internal/topology/mesh_topology.cc b/intern/opensubdiv/internal/topology/mesh_topology.cc
index 5fb06744e83..4ff168cc508 100644
--- a/intern/opensubdiv/internal/topology/mesh_topology.cc
+++ b/intern/opensubdiv/internal/topology/mesh_topology.cc
@@ -183,7 +183,9 @@ void MeshTopology::setNumFaces(int num_faces)
 {
   num_faces_ = num_faces;
 
-  faces_.resize(num_faces);
+  // NOTE: Extra element to store fake face past the last real one to make it
+  // possible to calculate number of verticies in the last face.
+  faces_first_vertex_index_.resize(num_faces + 1, 0);
 }
 
 int MeshTopology::getNumFaces() const
@@ -196,8 +198,8 @@ void MeshTopology::setNumFaceVertices(int face_index, int num_face_vertices)
   assert(face_index >= 0);
   assert(face_index < getNumFaces());
 
-  Face &face = faces_[face_index];
-  face.setNumVertices(num_face_vertices);
+  faces_first_vertex_index_[face_index + 1] = faces_first_vertex_index_[face_index] +
+                                              num_face_vertices;
 }
 
 int MeshTopology::getNumFaceVertices(int face_index) const
@@ -205,27 +207,67 @@ int MeshTopology::getNumFaceVertices(int face_index) const
   assert(face_index >= 0);
   assert(face_index < getNumFaces());
 
-  const Face &face = faces_[face_index];
-  return face.getNumVertices();
+  return faces_first_vertex_index_[face_index + 1] - faces_first_vertex_index_[face_index];
 }
 
-void MeshTopology::setFaceVertexIndices(int face_index, int *face_vertex_indices)
+void MeshTopology::setFaceVertexIndices(int face_index,
+                                        int num_face_vertex_indices,
+                                        const int *face_vertex_indices)
 {
   assert(face_index >= 0);
   assert(face_index < getNumFaces());
+  assert(num_face_vertex_indices == getNumFaceVertices(face_index));
 
-  Face &face = faces_[face_index];
-  face.setVertexIndices(face_vertex_indices);
+  int *face_vertex_indices_storage = getFaceVertexIndicesStorage(face_index);
+  memcpy(face_vertex_indices_storage, face_vertex_indices, sizeof(int) * num_face_vertex_indices);
 }
 
 bool MeshTopology::isFaceVertexIndicesEqual(int face_index,
-                                            const vector<int> &expected_vertices_of_face) const
+                                            int num_expected_face_vertex_indices,
+                                            const int *expected_face_vertex_indices) const
 {
   assert(face_index >= 0);
   assert(face_index < getNumFaces());
 
-  const Face &face = faces_[face_index];
-  return face.vertex_indices == expected_vertices_of_face;
+  if (getNumFaceVertices(face_index) != num_expected_face_vertex_indices) {
+    return false;
+  }
+
+  const int *face_vertex_indices_storage = getFaceVertexIndicesStorage(face_index);
+  return memcmp(face_vertex_indices_storage,
+                expected_face_vertex_indices,
+                sizeof(int) * num_expected_face_vertex_indices) == 0;
+}
+
+bool MeshTopology::isFaceVertexIndicesEqual(int face_index,
+                                            const vector<int> &expected_face_vertex_indices) const
+{
+  return isFaceVertexIndicesEqual(
+      face_index, expected_face_vertex_indices.size(), expected_face_vertex_indices.data());
+}
+
+int *MeshTopology::getFaceVertexIndicesStorage(int face_index)
+{
+  const MeshTopology *const_this = this;
+  return const_cast<int *>(const_this->getFaceVertexIndicesStorage(face_index));
+}
+const int *MeshTopology::getFaceVertexIndicesStorage(int face_index) const
+{
+  assert(face_index >= 0);
+  assert(face_index < getNumFaces());
+
+  const int offset = faces_first_vertex_index_[face_index];
+  return face_vertex_indices_.data() + offset;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// Pipeline related.
+
+void MeshTopology::finishResizeTopology()
+{
+  if (!faces_first_vertex_index_.empty()) {
+    face_vertex_indices_.resize(faces_first_vertex_index_.back());
+  }
 }
 
 }  // namespace opensubdiv
diff --git a/intern/opensubdiv/internal/topology/mesh_topology.h b/intern/opensubdiv/internal/topology/mesh_topology.h
index aef521fbd44..fd3267df38b 100644
--- a/intern/opensubdiv/internal/topology/mesh_topology.h
+++ b/intern/opensubdiv/internal/topology/mesh_topology.h
@@ -32,6 +32,25 @@ namespace opensubdiv {
 // Simplified representation of mesh topology.
 // Only includes parts of actual mesh topology which is needed to perform
 // comparison between Application side and OpenSubddiv side.
+//
+// NOTE: It is an optimized storage which requires special order of topology
+// specification. Basically, counters is to be set prior to anything else, in
+// the following manner:
+//
+//   MeshTopology mesh_topology;
+//
+//   mesh_topology.setNumVertices(...);
+//   mesh_topology.setNumEdges(...);
+//   mesh_topology.setNumFaces(...);
+//
+//   for (...) {
+//     mesh_topology.setNumFaceVertices(...);
+//   }
+//
+//   mesh_topology.finishResizeTopology();
+//
+//   /* it is now possible to set vertices of edge, vertices of face, and
+//    * sharpness. */
 class MeshTopology {
  public:
   MeshTopology();
@@ -78,10 +97,25 @@ class MeshTopology {
   void setNumFaceVertices(int face_index, int num_face_vertices);
   int getNumFaceVertices(int face_index) const;
 
-  void setFaceVertexIndices(int face_index, int *face_vertex_indices);
+  void setFaceVertexIndices(int face_index,
+                            int num_face_vertex_indices,
+                            const int *face_vertex_indices);
 
   bool isFaceVertexIndicesEqual(int face_index,
-                                const vector<int> &expected_vertices_of_face) const;
+                                int num_expected_face_vertex_indices,
+                                const int *expected_face_vertex_indices) const;
+  bool isFaceVertexIndicesEqual(int face_index,
+                                const vector<int> &expected_face_vertex_indices) const;
+
+  //////////////////////////////////////////////////////////////////////////////
+  // Pipeline related.
+
+  // This function is to be called when number of vertices, edges, faces, and
+  // face-verticies are known.
+  //
+  // Usually is called from the end of topology refiner factory's
+  // resizeComponentTopology().
+  void finishResizeTopology();
 
   //////////////////////////////////////////////////////////////////////////////
   // Comparison.
@@ -102,6 +136,10 @@ class MeshTopology {
   void ensureVertexTagsSize(int num_vertices);
   void ensureEdgeTagsSize(int num_edges);
 
+  // Get pointer to the memory where face vertex indices are stored.
+  int *getFaceVertexIndicesStorage(int face_index);
+  const int *getFaceVertexIndicesStorage(int face_index) const;
+
   struct VertexTag {
     float sharpness = 0.0f;
   };
@@ -120,36 +158,6 @@ class MeshTopology {
     float sharpness = 0.0f;
   };
 
-  struct Face {
-    void setNumVertices(int num_vertices)
-    {
-      vertex_indices.resize(num_vertices, -1);
-    }
-
-    void setVertexIndices(int *face_vertex_indices)
-    {
-      memcpy(vertex_indices.data(), face_vertex_indices, sizeof(int) * vertex_indices.size());
-    }
-
-    bool isValid() const
-    {
-      for (int vertex_index : vertex_indices) {
-        if (vertex_index < 0) {
-          return false;
-        }
-      }
-
-      return true;
-    }
-
-    int getNumVertices() const
-    {
-      return vertex_indices.size();
-    }
-
-    vector<int> vertex_indices;
-  };
-
   int num_vertices_;
   vector<VertexTag> vertex_tags_;
 
@@ -158,7 +166,14 @@ class MeshTopology {
   vector<EdgeTag> edge_tags_;
 
   int num_faces_;
-  vector<Face> faces_;
+
+  // Continuous array of all verticies of all faces:
+  //  [vertex indices of face 0][vertex indices of face 1] .. [vertex indices of face n].
+  vector<int> face_vertex_indices_;
+
+  // Indexed by face contains index within face_vertex_indices_ which corresponds
+  // to the element which contains first vertex of the face.
+  vector<int> faces_first_vertex_index_;
 
   MEM_CXX_CLASS_ALLOC_FUNCS("MeshTopology");
 };
diff --git a/intern/opensubdiv/internal/topology/mesh_topology_test.cc b/intern/opensubdiv/internal/topology/mesh_topology_test.cc
index e80dab38fa3..5fb58c37add 100644
--- a/intern/opensubdiv/internal/topology/mesh_topology_test.cc
+++ b/intern/opensubdiv/internal/topology/mesh_topology_test.cc
@@ -27,6 +27,7 @@ TEST(MeshTopology, TrivialVertexSharpness)
   MeshTopology mesh_topology;
 
   mesh_topology.setNumVertices(3);
+  mesh_topology.finishResizeTopology();
 
   mesh_topology.setVertexSharpness(0, 0.1f);
   mesh_topology.setVertexSharpness(1, 0.2f);
@@ -42,6 +43,7 @@ TEST(MeshTopology, TrivialEdgeSharpness)
 
   mesh_topology.setNumVertices(8);
   mesh_topology.setNumEdges(3);
+  mesh_topology.finishResizeTopology();
 
   mesh_topology.setEdgeVertexIndices(0, 0, 1);
   mesh_topology.setEdgeVertexIndices(1, 1, 2);
@@ -60,29 +62,30 @@ TEST(MeshTopology, TrivialFaceTopology)
   MeshTopology mesh_topology;
 
   mesh_topology.setNumFaces(3);
+  mesh_topology.setNumFaceVertices(0, 4);
+  mesh_topology.setNumFaceVertices(1, 3);
+  mesh_topology.setNumFaceVertices(2, 5);
+  mesh_topology.finishResizeTopology();
+
+  EXPECT_EQ(mesh_topology.getNumFaceVertices(0), 4);
+  EXPECT_EQ(mesh_topology.getNumFaceVertices(1), 3);
+  EXPECT_EQ(mesh_topology.getNumFaceVertices(2), 5);
 
   {
-    mesh_topology.setNumFaceVertices(0, 4);
     int vertex_indices[] = {0, 1, 2, 3};
-    mesh_topology.setFaceVertexIndices(0, vertex_indices);
+    mesh_topology.setFaceVertexIndices(0, 4, vertex_indices);
   }
 
   {
-    mesh_topology.setNumFaceVertices(1, 3);
     int vertex_indices[] = {4, 5, 6};
-    mesh_topology.setFaceVertexIndices(1, vertex_indices);
+    mesh_topology.setFaceVertexIndices(1, 3, vertex_indices);
   }
 
   {
-    mesh_topology.setNumFaceVertices(2, 5);
     int vertex_indices[] = {7, 8, 9, 10, 11};
-    mesh_topology.setFaceVertexIndices(2, vertex_indices);
+    mesh_topology.setFaceVertexIndices(2, 5, vertex_indices);
   }
 
-  EXPECT_EQ(mesh_topology.getNumFaceVertices(0), 4);
-  EXPECT_EQ(mesh_topology.getNumFaceVertices(1), 3);
-  EXPECT_EQ(mesh_topology.getNumFaceVertices(2), 5);
-
   EXPECT_TRUE(mesh_topology.isFaceVertexIndicesEqual(0, {{0, 1, 2, 3}}));
   EXPECT_FALSE(mesh_topology.isFaceVertexIndicesEqual(0, {{10, 1, 2, 3}}));
   EXPECT_FALSE(mesh_topology.isFaceVertexIndicesEqual(0, {{0, 1, 2}}));
diff --git a/intern/opensubdiv/internal/topology/topology_refiner_factory.cc b/intern/opensubdiv/internal/topology/topology_refiner_factory.cc
index 5a84c45101b..e0c5e18e504 100644
--- a/intern/opensubdiv/internal/topology/topology_refiner_factory.cc
+++ b/intern/opensubdiv/internal/topology/topology_refiner_factory.cc
@@ -94,6 +94,7 @@ inline bool TopologyRefinerFactory<TopologyRefinerData>::resizeComponentTopology
   // The rest is needed to define relations between faces-of-edge and
   // edges-of-vertex, which is not available for partially specified mesh.
   if (!converter->specifiesFullTopology(converter)) {
+    base_mesh_topology->finishResizeTopology();
     return true;
   }
 
@@ -113,6 +114,7 @@ inline bool TopologyRefinerFactory<TopologyRefinerData>::resizeComponentTopology
     setNumBaseVertexFaces(refiner, vertex_index, num_vert_faces);
   }
 
+  base_mesh_topology->finishResizeTopology();
   return true;
 }
 
@@ -149,7 +151,8 @@ inline bool TopologyRefinerFactory<TopologyRefinerData>::assignComponentTopology
     IndexArray dst_face_verts = getBaseFaceVertices(refiner, face_index);
     converter->getFaceVertices(converter, face_index, &dst_face_verts[0]);
 
-    base_mesh_topology->setFaceVertexIndices(face_index, &dst_face_verts[0]);
+    base_mesh_topology->setFaceVertexIndices(
+        face_index, dst_face_verts.size(), &dst_face_verts[0]);
   }
 
   // If converter does not provide full topology, we are done.