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.

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

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;
@@ -87,6 +120,19 @@ class MeshTopology {
   void setEdgeSharpness(int edge_index, float sharpness);
   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.
 
@@ -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");
 };
 

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;
   }
 

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.

intern/opensubdiv/internal/topology/topology_refiner_impl_compare.cc

@@ -85,150 +85,6 @@ bool checkPreliminaryMatches(const TopologyRefinerImpl *topology_refiner_impl,
          checkGeometryCountersMatches(topology_refiner_impl, converter);
 }
 
-////////////////////////////////////////////////////////////////////////////////
-// 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.
 
@@ -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;
   }