OpenSubdiv: Correct topology cpmparator

This fixes following errors:

- The code didn't work correctly for edges reconstructed by
  the OpenSubdiv's topology refiner (due to indexing
  difference).

- Sharpness of non-manifold and boundary edges was not
  working correctly.

4 files changed, 366 insertions, 55 deletions

diff --git a/intern/opensubdiv/CMakeLists.txt b/intern/opensubdiv/CMakeLists.txt
index e145500e019..e6ad305ffc7 100644
--- a/intern/opensubdiv/CMakeLists.txt
+++ b/intern/opensubdiv/CMakeLists.txt
@@ -75,6 +75,7 @@ if(WITH_OPENSUBDIV)
 		internal/opensubdiv_converter_orient_impl.h
 		internal/opensubdiv_device_context_cuda.h
 		internal/opensubdiv_device_context_opencl.h
+		internal/opensubdiv_edge_map.h
 		internal/opensubdiv_evaluator_internal.h
 		internal/opensubdiv_gl_mesh_draw.h
 		internal/opensubdiv_gl_mesh_fvar.h
diff --git a/intern/opensubdiv/internal/opensubdiv_edge_map.h b/intern/opensubdiv/internal/opensubdiv_edge_map.h
new file mode 100644
index 00000000000..8825f663c15
--- /dev/null
+++ b/intern/opensubdiv/internal/opensubdiv_edge_map.h
@@ -0,0 +1,159 @@
+// Copyright 2019 Blender Foundation. All rights reserved.
+//
+// This program is free software; you can redistribute it and/or
+// modify it under the terms of the GNU General Public License
+// as published by the Free Software Foundation; either version 2
+// of the License, or (at your option) any later version.
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software Foundation,
+// Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+//
+// Author: Sergey Sharybin
+
+#ifndef OPENSUBDIV_EDGE_MAP_H_
+#define OPENSUBDIV_EDGE_MAP_H_
+
+#include "internal/opensubdiv_util.h"
+
+namespace opensubdiv_capi {
+
+// Helper class to ease dealing with edge indexing.
+// Simply takes care of ensuring order of vertices is strictly defined.
+class EdgeKey {
+ public:
+  inline EdgeKey();
+  inline EdgeKey(int v1, int v2);
+
+  inline size_t hash() const;
+  inline bool operator==(const EdgeKey& other) const;
+
+  // These indices are guaranteed to be so v1 < v2.
+  int v1;
+  int v2;
+};
+
+// Map from an edge defined by its verticies index to a custom tag value.
+template<typename T>
+class EdgeTagMap {
+ public:
+  typedef EdgeKey key_type;
+  typedef T value_type;
+
+  inline EdgeTagMap();
+
+  // Modifiers.
+  inline void clear();
+  inline void insert(const key_type& key, const value_type& value);
+  inline void insert(int v1, int v2, const value_type& value);
+
+  // Lookup.
+  value_type& at(const key_type& key);
+  value_type& at(key_type&& key);
+  value_type& at(int v1, int v2);
+
+  value_type& operator[](const key_type& key);
+  value_type& operator[](key_type&& key);
+
+ protected:
+  unordered_map<key_type, value_type> edge_tags_;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+// Implementation.
+
+// EdgeKey.
+
+EdgeKey::EdgeKey()
+    : v1(-1),
+      v2(-1) {
+}
+
+EdgeKey::EdgeKey(int v1, int v2) {
+  assert(v1 >= 0);
+  assert(v2 >= 0);
+  assert(v1 != v2);
+  if (v1 < v2) {
+    this->v1 = v1;
+    this->v2 = v2;
+  } else {
+    this->v1 = v2;
+    this->v2 = v1;
+  }
+}
+
+size_t EdgeKey::hash() const {
+  return (static_cast<uint64_t>(v1) << 32) | v2;
+}
+
+bool EdgeKey::operator==(const EdgeKey& other) const {
+  return v1 == other.v1 &&
+         v2 == other.v2;
+}
+
+// EdgeTagMap.
+
+template<typename T>
+EdgeTagMap<T>::EdgeTagMap() {
+}
+
+template<typename T>
+void EdgeTagMap<T>::clear() {
+  edge_tags_.clear();
+}
+
+template<typename T>
+void EdgeTagMap<T>::insert(const key_type& key, const value_type& value) {
+  edge_tags_.insert(make_pair(key, value));
+}
+
+template<typename T>
+void EdgeTagMap<T>::insert(int v1, int v2, const value_type& value) {
+  insert(EdgeKey(v1, v2), value);
+}
+
+template<typename T>
+typename EdgeTagMap<T>::value_type& EdgeTagMap<T>::at(const key_type& key) {
+  return edge_tags_.at[key];
+}
+
+template<typename T>
+typename EdgeTagMap<T>::value_type& EdgeTagMap<T>::at(key_type&& key) {
+  return edge_tags_.at[key];
+}
+
+template<typename T>
+typename EdgeTagMap<T>::value_type& EdgeTagMap<T>::at(int v1, int v2) {
+  return edge_tags_.at(EdgeKey(v1, v2));
+}
+
+template<typename T>
+typename EdgeTagMap<T>::value_type& EdgeTagMap<T>::operator[](
+    const key_type& key) {
+  return edge_tags_[key];
+}
+
+template<typename T>
+typename EdgeTagMap<T>::value_type& EdgeTagMap<T>::operator[](key_type&& key) {
+  return edge_tags_[key];
+}
+
+}  // namespace opensubdiv_capi
+
+namespace std {
+
+template <>
+struct hash<opensubdiv_capi::EdgeKey> {
+  std::size_t operator()(const opensubdiv_capi::EdgeKey& key) const {
+    return key.hash();
+  }
+};
+
+}  // namespace std
+
+#endif  // OPENSUBDIV_EDGE_MAP_H_
diff --git a/intern/opensubdiv/internal/opensubdiv_topology_refiner.cc b/intern/opensubdiv/internal/opensubdiv_topology_refiner.cc
index 296e373c31f..cbd076b256e 100644
--- a/intern/opensubdiv/internal/opensubdiv_topology_refiner.cc
+++ b/intern/opensubdiv/internal/opensubdiv_topology_refiner.cc
@@ -23,6 +23,7 @@
 #include "MEM_guardedalloc.h"
 #include "internal/opensubdiv_converter_factory.h"
 #include "internal/opensubdiv_converter_internal.h"
+#include "internal/opensubdiv_edge_map.h"
 #include "internal/opensubdiv_internal.h"
 #include "internal/opensubdiv_topology_refiner_internal.h"
 #include "internal/opensubdiv_util.h"
@@ -152,7 +153,7 @@ void fillFacePtexIndexOffset(const OpenSubdiv_TopologyRefiner* topology_refiner,
   }
 }
 
-//////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
 // Face-varying data.
 
 int getNumFVarChannels(
@@ -185,7 +186,7 @@ const int* getFaceFVarValueIndices(
   return &base_level->GetFaceFVarValues(face_index, channel)[0];
 }
 
-//////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
 // Internal helpers.
 
 void assignFunctionPointers(OpenSubdiv_TopologyRefiner* topology_refiner) {
@@ -249,6 +250,7 @@ void openSubdiv_deleteTopologyRefiner(
 ////////////////////////////////////////////////////////////////////////////////
 // Comparison with converter.
 
+namespace opensubdiv_capi {
 namespace {
 
 ///////////////////////////////////////////////////////////
@@ -279,7 +281,7 @@ bool checkOptionsMatches(
   return true;
 }
 
-bool checkGeometryCoountersMatches(
+bool checkGeometryCountersMatches(
     const OpenSubdiv::Far::TopologyRefiner* topology_refiner,
     const OpenSubdiv_Converter* converter) {
   using OpenSubdiv::Far::TopologyLevel;
@@ -295,32 +297,115 @@ bool checkPreliminaryMatches(
     const OpenSubdiv_Converter* converter) {
   return checkSchemeTypeMatches(topology_refiner, converter) &&
          checkOptionsMatches(topology_refiner, converter) &&
-         checkGeometryCoountersMatches(topology_refiner, converter);
+         checkGeometryCountersMatches(topology_refiner, converter);
 }
 
 ///////////////////////////////////////////////////////////
 // Geometry comparison.
 
-bool checkGeometryEdgesMatch(
-    const OpenSubdiv::Far::TopologyRefiner* topology_refiner,
-    const OpenSubdiv_Converter* converter) {
-  using OpenSubdiv::Far::ConstIndexArray;
-  using OpenSubdiv::Far::TopologyLevel;
-  const TopologyLevel& base_level = topology_refiner->GetLevel(0);
-  const int num_edges = base_level.GetNumEdges();
-  for (int edge_index = 0; edge_index < num_edges; ++edge_index) {
-    const ConstIndexArray& edge_vertices =
-        base_level.GetEdgeVertices(edge_index);
-    int conv_edge_vertices[2];
-    converter->getEdgeVertices(converter, edge_index, conv_edge_vertices);
-    if (conv_edge_vertices[0] != edge_vertices[0] ||
-        conv_edge_vertices[1] != edge_vertices[1]) {
+// 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 verticies 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.
+bool checkVerticesOfFacesMatch(const CyclicArray& indices_a,
+                               const CyclicArray& indices_b) {
+  if (indices_a.size() != indices_a.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 OpenSubdiv::Far::TopologyRefiner* topology_refiner,
     const OpenSubdiv_Converter* converter) {
@@ -341,32 +426,8 @@ bool checkGeometryFacesMatch(
     }
     conv_face_vertices.resize(num_face_vertices);
     converter->getFaceVertices(converter, face_index, &conv_face_vertices[0]);
-    // Check face-vertex indices in the direct order (assuming topology
-    // orientation is disabled or did not flip order of the face-vertices).
-    //
-    // TODO(sergey): Can we simply memcmp() with OpenSubdiv's array?
-    bool direct_match = true;
-    for (int face_vertex_index = 0; face_vertex_index < num_face_vertices;
-         ++face_vertex_index) {
-      if (conv_face_vertices[face_vertex_index] !=
-          face_vertices[face_vertex_index]) {
-        direct_match = false;
-        break;
-      }
-    }
-    if (!direct_match) {
-      // If face didn't match in direct direction we also test if it matches in
-      // reversed direction. This is because conversion might reverse loops to
-      // make normals consistent.
-#ifdef OPENSUBDIV_ORIENT_TOPOLOGY
-      for (int face_vertex_index = 0; face_vertex_index < num_face_vertices;
-           ++face_vertex_index) {
-        if (conv_face_vertices[face_vertex_index] !=
-            face_vertices[num_face_vertices - face_vertex_index - 1]) {
-          return false;
-        }
-      }
-#endif
+    if (!checkVerticesOfFacesMatch(CyclicArray(conv_face_vertices),
+                                   CyclicArray(face_vertices))) {
       return false;
     }
   }
@@ -376,45 +437,128 @@ bool checkGeometryFacesMatch(
 bool checkGeometryMatches(
     const OpenSubdiv::Far::TopologyRefiner* topology_refiner,
     const OpenSubdiv_Converter* converter) {
-  return checkGeometryEdgesMatch(topology_refiner, converter) &&
-         checkGeometryFacesMatch(topology_refiner, converter);
+  // NOTE: Since OpenSubdiv's topology refiner doesn't contain loose edges, we
+  // are only checking for faces to be matched. Changes in edges we don't care
+  // here too much (they'll be checked for creases changes later).
+  return checkGeometryFacesMatch(topology_refiner, converter);
 }
 
 ///////////////////////////////////////////////////////////
 // Compare attributes which affects on topology
 
-bool checkEdgeSharpnessMatch(
+inline bool checkSingleEdgeSharpnessMatch(
+    const OpenSubdiv::Far::TopologyLevel& base_level,
+    int base_level_edge_index,
+    const OpenSubdiv_Converter* converter,
+    int converter_edge_index) {
+  // NOTE: Boundary and non-manifold edges are internally forced to an infinite
+  // sharpness. So we can not reliably compare those.
+  //
+  // TODO(sergey): Watch for NON_MANIFOLD_SHARP option.
+  if (base_level.IsEdgeBoundary(base_level_edge_index) ||
+      base_level.IsEdgeNonManifold(base_level_edge_index)) {
+    return true;
+  }
+  const float sharpness = base_level.GetEdgeSharpness(base_level_edge_index);
+  const float converter_sharpness =
+      converter->getEdgeSharpness(converter, converter_edge_index);
+  if (sharpness != converter_sharpness) {
+    return false;
+  }
+  return true;
+}
+
+inline bool checkSingleEdgeTagMatch(
+    const OpenSubdiv::Far::TopologyLevel& base_level,
+    int base_level_edge_index,
+    const OpenSubdiv_Converter* converter,
+    int converter_edge_index) {
+  return checkSingleEdgeSharpnessMatch(base_level, base_level_edge_index,
+                                       converter, converter_edge_index);
+}
+
+// Compares edge tags between topology refiner and converter in a case when
+// converter specifies a full topology.
+// This is simplest loop, since we know that order of edges matches.
+bool checkEdgeTagsMatchFullTopology(
+    const OpenSubdiv::Far::TopologyRefiner* topology_refiner,
+    const OpenSubdiv_Converter* converter) {
+  using OpenSubdiv::Far::ConstIndexArray;
+  using OpenSubdiv::Far::TopologyLevel;
+  const TopologyLevel& base_level = topology_refiner->GetLevel(0);
+  const int num_edges = base_level.GetNumEdges();
+  for (int edge_index = 0; edge_index < num_edges; ++edge_index) {
+    if (!checkSingleEdgeTagMatch(
+        base_level, edge_index, converter, edge_index)) {
+      return false;
+    }
+  }
+  return true;
+}
+
+// Compares tags of edges in the case when orientation of edges is left up to
+// OpenSubdiv. In this case we do need to take care of mapping edges from the
+// converter to current topology refiner, since the order is not guaranteed.
+bool checkEdgeTagsMatchAutoOrient(
     const OpenSubdiv::Far::TopologyRefiner* topology_refiner,
     const OpenSubdiv_Converter* converter) {
   using OpenSubdiv::Far::ConstIndexArray;
   using OpenSubdiv::Far::TopologyLevel;
   const TopologyLevel& base_level = topology_refiner->GetLevel(0);
   const int num_edges = base_level.GetNumEdges();
+  // Create mapping for quick lookup of edge index from its verticies indices.
+  //
+  // TODO(sergey): Consider caching it in some sort of wrapper around topology
+  // refiner.
+  EdgeTagMap<int> edge_map;
   for (int edge_index = 0; edge_index < num_edges; ++edge_index) {
-    const float sharpness = base_level.GetEdgeSharpness(edge_index);
-    const float conv_sharpness =
-        converter->getEdgeSharpness(converter, edge_index);
-    if (sharpness != conv_sharpness) {
+    ConstIndexArray edge_vertices = base_level.GetEdgeVertices(edge_index);
+    edge_map.insert(edge_vertices[0], edge_vertices[1], edge_index);
+  }
+  // Compare all edges.
+  for (int converter_edge_index = 0;
+       converter_edge_index < num_edges;
+       ++converter_edge_index) {
+    // Get edge verticies indices, and lookup corresponding edge index in the
+    // base topology level.
+    int edge_vertices[2];
+    converter->getEdgeVertices(converter, converter_edge_index, edge_vertices);
+    const int base_level_edge_index = edge_map.at(
+        edge_vertices[0], edge_vertices[1]);
+    // Perform actual test.
+    if (!checkSingleEdgeTagMatch(
+        base_level, base_level_edge_index, converter, converter_edge_index)) {
       return false;
     }
   }
   return true;
 }
 
+bool checkEdgeTagsMatch(
+    const OpenSubdiv::Far::TopologyRefiner* topology_refiner,
+    const OpenSubdiv_Converter* converter) {
+  if (converter->specifiesFullTopology(converter)) {
+    return checkEdgeTagsMatchFullTopology(topology_refiner, converter);
+  } else {
+    return checkEdgeTagsMatchAutoOrient(topology_refiner, converter);
+  }
+}
+
 bool checkTopologyAttributesMatch(
     const OpenSubdiv::Far::TopologyRefiner* topology_refiner,
     const OpenSubdiv_Converter* converter) {
-  return checkEdgeSharpnessMatch(topology_refiner, converter);
+  return checkEdgeTagsMatch(topology_refiner, converter);
 }
 
 }  // namespace
+}  // namespace opensubdiv_capi
 
 bool openSubdiv_topologyRefinerCompareWithConverter(
     const OpenSubdiv_TopologyRefiner* topology_refiner,
     const OpenSubdiv_Converter* converter) {
   const OpenSubdiv::Far::TopologyRefiner* refiner =
       getOSDTopologyRefiner(topology_refiner);
-  return (checkPreliminaryMatches(refiner, converter) &&
-          checkGeometryMatches(refiner, converter) &&
-          checkTopologyAttributesMatch(refiner, converter));
+  return (opensubdiv_capi::checkPreliminaryMatches(refiner, converter) &&
+          opensubdiv_capi::checkGeometryMatches(refiner, converter) &&
+          opensubdiv_capi::checkTopologyAttributesMatch(refiner, converter));
 }
diff --git a/intern/opensubdiv/internal/opensubdiv_util.h b/intern/opensubdiv/internal/opensubdiv_util.h
index e7123d9d97b..1e4ed1b0d54 100644
--- a/intern/opensubdiv/internal/opensubdiv_util.h
+++ b/intern/opensubdiv/internal/opensubdiv_util.h
@@ -20,20 +20,27 @@
 #ifndef OPENSUBDIV_UTIL_H_
 #define OPENSUBDIV_UTIL_H_
 
+#include <stdint.h>
+
 #include <algorithm>
+#include <cassert>
 #include <vector>
 #include <stack>
 #include <string>
+#include <unordered_map>
 #include <utility>
 
 namespace opensubdiv_capi {
 
 using std::fill;
+using std::make_pair;
 using std::max;
 using std::min;
+using std::pair;
 using std::stack;
 using std::string;
 using std::swap;
+using std::unordered_map;
 using std::vector;
 
 #define foreach(x, y) for (x : y)