OpenSubdiv: Keep explicit storage of base mesh faces

Allows to perform comparison by doing linear comparison of indices.

Before cyclic match was used to deal with possibly changed winding from
OpenSubdiv side.

Speeds up comparison (and hence improves FPS), makes code more reliable
nut uses more memory.

5 files changed, 132 insertions, 150 deletions

diff --git a/intern/opensubdiv/internal/topology/mesh_topology.cc b/intern/opensubdiv/internal/topology/mesh_topology.cc
index 483595dbfe1..ae7c1e069b6 100644
--- a/intern/opensubdiv/internal/topology/mesh_topology.cc
+++ b/intern/opensubdiv/internal/topology/mesh_topology.cc
@@ -23,7 +23,7 @@
 namespace blender {
 namespace opensubdiv {
 
-MeshTopology::MeshTopology() : num_vertices_(0), num_edges_(0)
+MeshTopology::MeshTopology() : num_vertices_(0), num_edges_(0), num_faces_(0)
 {
 }
 
@@ -168,5 +168,45 @@ void MeshTopology::ensureEdgeTagsSize(int num_edges)
   }
 }
 
+////////////////////////////////////////////////////////////////////////////////
+// Faces.
+
+void MeshTopology::setNumFaces(int num_faces)
+{
+  num_faces_ = num_faces;
+
+  faces_.resize(num_faces);
+}
+
+int MeshTopology::getNumFaces() const
+{
+  return num_faces_;
+}
+
+FaceTopology &MeshTopology::getFace(int face_index)
+{
+  const MeshTopology *const_this = this;
+  return const_cast<FaceTopology &>(const_this->getFace(face_index));
+}
+const FaceTopology &MeshTopology::getFace(int face_index) const
+{
+  assert(face_index >= 0);
+  assert(face_index < getNumFaces());
+
+  return faces_[face_index];
+}
+
+void MeshTopology::setNumFaceVertices(int face_index, int num_face_vertices)
+{
+  FaceTopology &face = getFace(face_index);
+  face.setNumVertices(num_face_vertices);
+}
+
+void MeshTopology::setFaceVertexIndices(int face_index, int *face_vertex_indices)
+{
+  FaceTopology &face = getFace(face_index);
+  face.setVertexIndices(face_vertex_indices);
+}
+
 }  // namespace opensubdiv
 }  // namespace blender
diff --git a/intern/opensubdiv/internal/topology/mesh_topology.h b/intern/opensubdiv/internal/topology/mesh_topology.h
index 6edbc59b230..196d79c87df 100644
--- a/intern/opensubdiv/internal/topology/mesh_topology.h
+++ b/intern/opensubdiv/internal/topology/mesh_topology.h
@@ -19,6 +19,8 @@
 #ifndef OPENSUBDIV_MESH_TOPOLOGY_H_
 #define OPENSUBDIV_MESH_TOPOLOGY_H_
 
+#include <cstring>
+
 #include "internal/base/memory.h"
 #include "internal/base/type.h"
 
@@ -43,6 +45,37 @@ class EdgeTopology {
   int v2 = -1;
 };
 
+class FaceTopology {
+ public:
+  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;
+};
+
 class EdgeTopologyTag {
  public:
   float sharpness = 0.0f;
@@ -88,6 +121,19 @@ class MeshTopology {
   float getEdgeSharpness(int edge_index) const;
 
   //////////////////////////////////////////////////////////////////////////////
+  // Faces.
+
+  void setNumFaces(int num_faces);
+
+  int getNumFaces() const;
+
+  FaceTopology &getFace(int face_index);
+  const FaceTopology &getFace(int face_index) const;
+
+  void setNumFaceVertices(int face_index, int num_face_vertices);
+  void setFaceVertexIndices(int face_index, int *face_vertex_indices);
+
+  //////////////////////////////////////////////////////////////////////////////
   // Comparison.
 
   // Check whether this topology refiner defines same topology as the given
@@ -113,6 +159,9 @@ class MeshTopology {
   vector<EdgeTopology> edges_;
   vector<EdgeTopologyTag> edge_tags_;
 
+  int num_faces_;
+  vector<FaceTopology> faces_;
+
   MEM_CXX_CLASS_ALLOC_FUNCS("MeshTopology");
 };
 
diff --git a/intern/opensubdiv/internal/topology/mesh_topology_compare.cc b/intern/opensubdiv/internal/topology/mesh_topology_compare.cc
index c8ae0638bed..a2561568c71 100644
--- a/intern/opensubdiv/internal/topology/mesh_topology_compare.cc
+++ b/intern/opensubdiv/internal/topology/mesh_topology_compare.cc
@@ -19,8 +19,11 @@
 #include "internal/topology/mesh_topology.h"
 
 #include <cassert>
+#include <cstring>
 #include <opensubdiv/sdc/crease.h>
 
+#include "internal/base/type.h"
+
 #include "opensubdiv_converter_capi.h"
 
 namespace blender {
@@ -42,7 +45,7 @@ int getEffectiveNumEdges(const OpenSubdiv_Converter *converter)
   return converter->getNumEdges(converter);
 }
 
-bool isEqualEdgeGeometry(const MeshTopology &mesh_topology, const OpenSubdiv_Converter *converter)
+bool isEqualGeometryEdge(const MeshTopology &mesh_topology, const OpenSubdiv_Converter *converter)
 {
   const int num_requested_edges = getEffectiveNumEdges(converter);
   if (num_requested_edges != mesh_topology.getNumEdges()) {
@@ -63,11 +66,43 @@ bool isEqualEdgeGeometry(const MeshTopology &mesh_topology, const OpenSubdiv_Con
   return true;
 }
 
+// Faces.
+
+bool isEqualGeometryFace(const MeshTopology &mesh_topology, const OpenSubdiv_Converter *converter)
+{
+  const int num_requested_faces = converter->getNumFaces(converter);
+  if (num_requested_faces != mesh_topology.getNumFaces()) {
+    return false;
+  }
+
+  vector<int> vertices_of_face;
+  for (int face_index = 0; face_index < num_requested_faces; ++face_index) {
+    const FaceTopology &current_face = mesh_topology.getFace(face_index);
+
+    int num_face_vertices = converter->getNumFaceVertices(converter, face_index);
+    if (current_face.getNumVertices() != num_face_vertices) {
+      return false;
+    }
+
+    vertices_of_face.resize(num_face_vertices);
+    converter->getFaceVertices(converter, face_index, vertices_of_face.data());
+
+    if (current_face.vertex_indices != vertices_of_face) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
 // Geometry comparison entry point.
 
 bool isEqualGeometry(const MeshTopology &mesh_topology, const OpenSubdiv_Converter *converter)
 {
-  if (!isEqualEdgeGeometry(mesh_topology, converter)) {
+  if (!isEqualGeometryEdge(mesh_topology, converter)) {
+    return false;
+  }
+  if (!isEqualGeometryFace(mesh_topology, converter)) {
     return false;
   }
 
diff --git a/intern/opensubdiv/internal/topology/topology_refiner_factory.cc b/intern/opensubdiv/internal/topology/topology_refiner_factory.cc
index 239a8447f47..c01cf158668 100644
--- a/intern/opensubdiv/internal/topology/topology_refiner_factory.cc
+++ b/intern/opensubdiv/internal/topology/topology_refiner_factory.cc
@@ -52,6 +52,7 @@ template<>
 inline bool TopologyRefinerFactory<TopologyRefinerData>::resizeComponentTopology(
     TopologyRefiner &refiner, const TopologyRefinerData &cb_data)
 {
+  using blender::opensubdiv::FaceTopology;
   using blender::opensubdiv::MeshTopology;
 
   const OpenSubdiv_Converter *converter = cb_data.converter;
@@ -81,9 +82,11 @@ inline bool TopologyRefinerFactory<TopologyRefinerData>::resizeComponentTopology
 
   // Faces and face-vertices.
   const int num_faces = converter->getNumFaces(converter);
+  base_mesh_topology->setNumFaces(num_faces);
   setNumBaseFaces(refiner, num_faces);
   for (int face_index = 0; face_index < num_faces; ++face_index) {
     const int num_face_vertices = converter->getNumFaceVertices(converter, face_index);
+    base_mesh_topology->setNumFaceVertices(face_index, num_face_vertices);
     setNumBaseFaceVertices(refiner, face_index, num_face_vertices);
   }
 
@@ -147,6 +150,8 @@ inline bool TopologyRefinerFactory<TopologyRefinerData>::assignComponentTopology
   for (int face_index = 0; face_index < num_faces; ++face_index) {
     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]);
   }
 
   // If converter does not provide full topology, we are done.
diff --git a/intern/opensubdiv/internal/topology/topology_refiner_impl_compare.cc b/intern/opensubdiv/internal/topology/topology_refiner_impl_compare.cc
index 3506d93b7aa..41727d5664a 100644
--- a/intern/opensubdiv/internal/topology/topology_refiner_impl_compare.cc
+++ b/intern/opensubdiv/internal/topology/topology_refiner_impl_compare.cc
@@ -86,150 +86,6 @@ bool checkPreliminaryMatches(const TopologyRefinerImpl *topology_refiner_impl,
 }
 
 ////////////////////////////////////////////////////////////////////////////////
-// Geometry comparison.
-
-// A thin wrapper around index like array which does cyclic access. This means,
-// it basically does indices[requested_index % num_indices].
-//
-// NOTE: This array does not own the memory.
-//
-// TODO(sergey): Consider moving this to a more reusable place.
-class CyclicArray {
- public:
-  typedef int value_type;
-  typedef int size_type;
-  static constexpr size_type npos = -1;
-
-  explicit CyclicArray(const std::vector<int> &data) : data_(data.data()), size_(data.size())
-  {
-  }
-
-  explicit CyclicArray(const OpenSubdiv::Far::ConstIndexArray &data)
-      : data_(&data[0]), size_(data.size())
-  {
-  }
-
-  inline value_type operator[](int index) const
-  {
-    assert(index >= 0);
-    // TODO(sergey): Check whether doing check for element index exceeding total
-    // number of indices prior to modulo helps performance.
-    return data_[index % size()];
-  }
-
-  inline size_type size() const
-  {
-    return size_;
-  }
-
-  // Find index of first occurrence of a given value.
-  inline size_type find(const value_type value) const
-  {
-    const int num_indices = size();
-    for (size_type i = 0; i < num_indices; ++i) {
-      if (value == (*this)[i]) {
-        return i;
-      }
-    }
-    return npos;
-  }
-
- protected:
-  const value_type *data_;
-  const size_type size_;
-};
-
-bool compareCyclicForward(const CyclicArray &array_a,
-                          const int start_a,
-                          const CyclicArray &array_b,
-                          const int start_b)
-{
-  const int num_elements = array_a.size();
-  for (int i = 0; i < num_elements; ++i) {
-    if (array_a[start_a + i] != array_b[start_b + i]) {
-      return false;
-    }
-  }
-  return true;
-}
-
-bool compareCyclicBackward(const CyclicArray &array_a,
-                           const int start_a,
-                           const CyclicArray &array_b,
-                           const int start_b)
-{
-  const int num_elements = array_a.size();
-  // TODO(sergey): Some optimization might be possible with memcmp trickery.
-  for (int i = 0; i < num_elements; ++i) {
-    if (array_a[start_a + (num_elements - i - 1)] != array_b[start_b + (num_elements - i - 1)]) {
-      return false;
-    }
-  }
-  return true;
-}
-
-// Utility function dedicated for checking whether whether vertices indices
-// used by two faces match.
-// The tricky part here is that we can't trust 1:1 array match here, since it's
-// possible that OpenSubdiv oriented edges of a face to make it compatible with
-// an internal representation of non-manifold meshes.
-//
-// TODO(sergey): Check whether this is needed, ot whether OpenSubdiv is only
-// creating edges in a proper orientation without modifying indices of face
-// vertices.
-bool checkVerticesOfFacesMatch(const CyclicArray &indices_a, const CyclicArray &indices_b)
-{
-  if (indices_a.size() != indices_b.size()) {
-    return false;
-  }
-  // "Align" the arrays so we know first matched element.
-  const int start_b = indices_b.find(indices_a[0]);
-  if (start_b == indices_b.npos) {
-    return false;
-  }
-  // Check match in both directions, for the case OpenSubdiv did orient face in
-  // a way which made normals more consistent internally.
-  if (compareCyclicForward(indices_a, 0, indices_b, start_b)) {
-    return true;
-  }
-  if (compareCyclicBackward(indices_a, 0, indices_b, start_b)) {
-    return true;
-  }
-  return false;
-}
-
-bool checkGeometryFacesMatch(const TopologyRefinerImpl *topology_refiner_impl,
-                             const OpenSubdiv_Converter *converter)
-{
-  using OpenSubdiv::Far::ConstIndexArray;
-  using OpenSubdiv::Far::TopologyLevel;
-  const TopologyLevel &base_level = getOSDTopologyBaseLevel(topology_refiner_impl);
-  const int num_faces = base_level.GetNumFaces();
-  // TODO(sergey): Consider using data structure which keeps handful of
-  // elements on stack before doing heep allocation.
-  vector<int> conv_face_vertices;
-  for (int face_index = 0; face_index < num_faces; ++face_index) {
-    const ConstIndexArray &face_vertices = base_level.GetFaceVertices(face_index);
-    const int num_face_vertices = face_vertices.size();
-    if (num_face_vertices != converter->getNumFaceVertices(converter, face_index)) {
-      return false;
-    }
-    conv_face_vertices.resize(num_face_vertices);
-    converter->getFaceVertices(converter, face_index, &conv_face_vertices[0]);
-    if (!checkVerticesOfFacesMatch(CyclicArray(conv_face_vertices), CyclicArray(face_vertices))) {
-      return false;
-    }
-  }
-  return true;
-}
-
-bool checkGeometryMatches(const TopologyRefinerImpl *topology_refiner_impl,
-                          const OpenSubdiv_Converter *converter)
-{
-  return checkGeometryFacesMatch(topology_refiner_impl, converter);
-}
-
-////////////////////////////////////////////////////////////////////////////////
 // Compare attributes which affects on topology.
 
 bool checkSingleUVLayerMatch(const OpenSubdiv::Far::TopologyLevel &base_level,
@@ -286,9 +142,6 @@ bool TopologyRefinerImpl::isEqualToConverter(const OpenSubdiv_Converter *convert
   if (!blender::opensubdiv::checkPreliminaryMatches(this, converter)) {
     return false;
   }
-  if (!blender::opensubdiv::checkGeometryMatches(this, converter)) {
-    return false;
-  }
   if (!blender::opensubdiv::checkTopologyAttributesMatch(this, converter)) {
     return false;
   }