Cycles: Stitching of subdivided and displaced meshes

This patch stitches the vertices along patch edges so that cracks can
no longer form when applying subdivision or displacement a mesh.

Subpatches are now formed in a way that ensures vertex indices along
subpatch edges are equal for adjacent subpatches. A mapping of vertices
along patch edges is built to preform stitching. Overall performance is
roughly the same, some gains were made in splitting, but some was lost
in stitching.

This fixes:
- T49049 (cracks between patches from material and uv seams)
- T49048 (discontinuous normals with true displacement)

Reviewers: sergey, brecht

Differential Revision: https://developer.blender.org/D3692

4 files changed, 146 insertions, 73 deletions

diff --git a/intern/cycles/render/mesh.cpp b/intern/cycles/render/mesh.cpp
index c7e0430fe7e..3d2cc98d38b 100644
--- a/intern/cycles/render/mesh.cpp
+++ b/intern/cycles/render/mesh.cpp
@@ -560,6 +560,9 @@ void Mesh::clear(bool preserve_voxel_data)
 
   used_shaders.clear();
 
+  vert_to_stitching_key_map.clear();
+  vert_stitching_map.clear();
+
   if (!preserve_voxel_data) {
     geometry_flags = GEOMETRY_NONE;
   }
diff --git a/intern/cycles/render/mesh.h b/intern/cycles/render/mesh.h
index 50b1f0e69f1..4a24a9c2656 100644
--- a/intern/cycles/render/mesh.h
+++ b/intern/cycles/render/mesh.h
@@ -283,6 +283,14 @@ class Mesh : public Node {
 
   size_t num_subd_verts;
 
+ private:
+  unordered_map<int, int> vert_to_stitching_key_map; /* real vert index -> stitching index */
+  unordered_multimap<int, int>
+      vert_stitching_map; /* stitching index -> multiple real vert indices */
+  friend class DiagSplit;
+  friend class MeshManager;
+
+ public:
   /* Functions */
   Mesh();
   ~Mesh();
diff --git a/intern/cycles/render/mesh_displace.cpp b/intern/cycles/render/mesh_displace.cpp
index 5ae9348d83e..6a6c2fbb3eb 100644
--- a/intern/cycles/render/mesh_displace.cpp
+++ b/intern/cycles/render/mesh_displace.cpp
@@ -22,7 +22,9 @@
 #include "render/shader.h"
 
 #include "util/util_foreach.h"
+#include "util/util_map.h"
 #include "util/util_progress.h"
+#include "util/util_set.h"
 
 CCL_NAMESPACE_BEGIN
 
@@ -184,6 +186,38 @@ bool MeshManager::displace(
 
   d_output.free();
 
+  /* stitch */
+  unordered_set<int> stitch_keys;
+  for (pair<int, int> i : mesh->vert_to_stitching_key_map) {
+    stitch_keys.insert(i.second); /* stitching index */
+  }
+
+  typedef unordered_multimap<int, int>::iterator map_it_t;
+
+  for (int key : stitch_keys) {
+    pair<map_it_t, map_it_t> verts = mesh->vert_stitching_map.equal_range(key);
+
+    float3 pos = make_float3(0.0f, 0.0f, 0.0f);
+    int num = 0;
+
+    for (map_it_t v = verts.first; v != verts.second; ++v) {
+      int vert = v->second;
+
+      pos += mesh->verts[vert];
+      num++;
+    }
+
+    if (num <= 1) {
+      continue;
+    }
+
+    pos *= 1.0f / num;
+
+    for (map_it_t v = verts.first; v != verts.second; ++v) {
+      mesh->verts[v->second] = pos;
+    }
+  }
+
   /* for displacement method both, we only need to recompute the face
    * normals, as bump mapping in the shader will already alter the
    * vertex normal, so we start from the non-displaced vertex normals
@@ -238,7 +272,25 @@ bool MeshManager::displace(
     for (size_t i = 0; i < num_triangles; i++) {
       if (tri_has_true_disp[i]) {
         for (size_t j = 0; j < 3; j++) {
-          vN[mesh->get_triangle(i).v[j]] += fN[i];
+          int vert = mesh->get_triangle(i).v[j];
+          vN[vert] += fN[i];
+
+          /* add face normals to stitched vertices */
+          if (stitch_keys.size()) {
+            map_it_t key = mesh->vert_to_stitching_key_map.find(vert);
+
+            if (key != mesh->vert_to_stitching_key_map.end()) {
+              pair<map_it_t, map_it_t> verts = mesh->vert_stitching_map.equal_range(key->second);
+
+              for (map_it_t v = verts.first; v != verts.second; ++v) {
+                if (v->second == vert) {
+                  continue;
+                }
+
+                vN[v->second] += fN[i];
+              }
+            }
+          }
         }
       }
     }
@@ -289,8 +341,27 @@ bool MeshManager::displace(
         for (size_t i = 0; i < num_triangles; i++) {
           if (tri_has_true_disp[i]) {
             for (size_t j = 0; j < 3; j++) {
+              int vert = mesh->get_triangle(i).v[j];
               float3 fN = compute_face_normal(mesh->get_triangle(i), mP);
-              mN[mesh->get_triangle(i).v[j]] += fN;
+              mN[vert] += fN;
+
+              /* add face normals to stitched vertices */
+              if (stitch_keys.size()) {
+                map_it_t key = mesh->vert_to_stitching_key_map.find(vert);
+
+                if (key != mesh->vert_to_stitching_key_map.end()) {
+                  pair<map_it_t, map_it_t> verts = mesh->vert_stitching_map.equal_range(
+                      key->second);
+
+                  for (map_it_t v = verts.first; v != verts.second; ++v) {
+                    if (v->second == vert) {
+                      continue;
+                    }
+
+                    mN[v->second] += fN;
+                  }
+                }
+              }
             }
           }
         }
diff --git a/intern/cycles/render/mesh_subdivision.cpp b/intern/cycles/render/mesh_subdivision.cpp
index 46c8240fb71..a5a35fc049e 100644
--- a/intern/cycles/render/mesh_subdivision.cpp
+++ b/intern/cycles/render/mesh_subdivision.cpp
@@ -24,6 +24,7 @@
 
 #include "util/util_foreach.h"
 #include "util/util_algorithm.h"
+#include "util/util_hash.h"
 
 CCL_NAMESPACE_BEGIN
 
@@ -318,6 +319,9 @@ class OsdData {
 struct OsdPatch : Patch {
   OsdData *osd_data;
 
+  OsdPatch()
+  {
+  }
   OsdPatch(OsdData *data) : osd_data(data)
   {
   }
@@ -358,11 +362,6 @@ struct OsdPatch : Patch {
       *N = (t != 0.0f) ? *N / t : make_float3(0.0f, 0.0f, 1.0f);
     }
   }
-
-  BoundBox bound()
-  {
-    return BoundBox::empty;
-  }
 };
 
 #endif
@@ -397,29 +396,62 @@ void Mesh::tessellate(DiagSplit *split)
   Attribute *attr_vN = subd_attributes.find(ATTR_STD_VERTEX_NORMAL);
   float3 *vN = attr_vN->data_float3();
 
+  /* count patches */
+  int num_patches = 0;
   for (int f = 0; f < num_faces; f++) {
     SubdFace &face = subd_faces[f];
 
     if (face.is_quad()) {
-      /* quad */
-      QuadDice::SubPatch subpatch;
+      num_patches++;
+    }
+    else {
+      num_patches += face.num_corners;
+    }
+  }
 
-      LinearQuadPatch quad_patch;
+  /* build patches from faces */
 #ifdef WITH_OPENSUBDIV
-      OsdPatch osd_patch(&osd_data);
+  if (subdivision_type == SUBDIVISION_CATMULL_CLARK) {
+    vector<OsdPatch> osd_patches(num_patches, &osd_data);
+    OsdPatch *patch = osd_patches.data();
 
-      if (subdivision_type == SUBDIVISION_CATMULL_CLARK) {
-        osd_patch.patch_index = face.ptex_offset;
+    for (int f = 0; f < num_faces; f++) {
+      SubdFace &face = subd_faces[f];
 
-        subpatch.patch = &osd_patch;
+      if (face.is_quad()) {
+        patch->patch_index = face.ptex_offset;
+        patch->from_ngon = false;
+        patch->shader = face.shader;
+        patch++;
+      }
+      else {
+        for (int corner = 0; corner < face.num_corners; corner++) {
+          patch->patch_index = face.ptex_offset + corner;
+          patch->from_ngon = true;
+          patch->shader = face.shader;
+          patch++;
+        }
       }
-      else
+    }
+
+    /* split patches */
+    split->split_patches(osd_patches.data(), sizeof(OsdPatch));
+  }
+  else
 #endif
-      {
-        float3 *hull = quad_patch.hull;
-        float3 *normals = quad_patch.normals;
+  {
+    vector<LinearQuadPatch> linear_patches(num_patches);
+    LinearQuadPatch *patch = linear_patches.data();
+
+    for (int f = 0; f < num_faces; f++) {
+      SubdFace &face = subd_faces[f];
 
-        quad_patch.patch_index = face.ptex_offset;
+      if (face.is_quad()) {
+        float3 *hull = patch->hull;
+        float3 *normals = patch->normals;
+
+        patch->patch_index = face.ptex_offset;
+        patch->from_ngon = false;
 
         for (int i = 0; i < 4; i++) {
           hull[i] = verts[subd_face_corners[face.start_corner + i]];
@@ -440,55 +472,11 @@ void Mesh::tessellate(DiagSplit *split)
         swap(hull[2], hull[3]);
         swap(normals[2], normals[3]);
 
-        subpatch.patch = &quad_patch;
+        patch->shader = face.shader;
+        patch++;
       }
-
-      subpatch.patch->shader = face.shader;
-
-      /* Quad faces need to be split at least once to line up with split ngons, we do this
-       * here in this manner because if we do it later edge factors may end up slightly off.
-       */
-      subpatch.P00 = make_float2(0.0f, 0.0f);
-      subpatch.P10 = make_float2(0.5f, 0.0f);
-      subpatch.P01 = make_float2(0.0f, 0.5f);
-      subpatch.P11 = make_float2(0.5f, 0.5f);
-      split->split_quad(subpatch.patch, &subpatch);
-
-      subpatch.P00 = make_float2(0.5f, 0.0f);
-      subpatch.P10 = make_float2(1.0f, 0.0f);
-      subpatch.P01 = make_float2(0.5f, 0.5f);
-      subpatch.P11 = make_float2(1.0f, 0.5f);
-      split->split_quad(subpatch.patch, &subpatch);
-
-      subpatch.P00 = make_float2(0.0f, 0.5f);
-      subpatch.P10 = make_float2(0.5f, 0.5f);
-      subpatch.P01 = make_float2(0.0f, 1.0f);
-      subpatch.P11 = make_float2(0.5f, 1.0f);
-      split->split_quad(subpatch.patch, &subpatch);
-
-      subpatch.P00 = make_float2(0.5f, 0.5f);
-      subpatch.P10 = make_float2(1.0f, 0.5f);
-      subpatch.P01 = make_float2(0.5f, 1.0f);
-      subpatch.P11 = make_float2(1.0f, 1.0f);
-      split->split_quad(subpatch.patch, &subpatch);
-    }
-    else {
-      /* ngon */
-#ifdef WITH_OPENSUBDIV
-      if (subdivision_type == SUBDIVISION_CATMULL_CLARK) {
-        OsdPatch patch(&osd_data);
-
-        patch.shader = face.shader;
-
-        for (int corner = 0; corner < face.num_corners; corner++) {
-          patch.patch_index = face.ptex_offset + corner;
-
-          split->split_quad(&patch);
-        }
-      }
-      else
-#endif
-      {
+      else {
+        /* ngon */
         float3 center_vert = make_float3(0.0f, 0.0f, 0.0f);
         float3 center_normal = make_float3(0.0f, 0.0f, 0.0f);
 
@@ -499,13 +487,13 @@ void Mesh::tessellate(DiagSplit *split)
         }
 
         for (int corner = 0; corner < face.num_corners; corner++) {
-          LinearQuadPatch patch;
-          float3 *hull = patch.hull;
-          float3 *normals = patch.normals;
+          float3 *hull = patch->hull;
+          float3 *normals = patch->normals;
 
-          patch.patch_index = face.ptex_offset + corner;
+          patch->patch_index = face.ptex_offset + corner;
+          patch->from_ngon = true;
 
-          patch.shader = face.shader;
+          patch->shader = face.shader;
 
           hull[0] =
               verts[subd_face_corners[face.start_corner + mod(corner + 0, face.num_corners)]];
@@ -537,10 +525,13 @@ void Mesh::tessellate(DiagSplit *split)
             }
           }
 
-          split->split_quad(&patch);
+          patch++;
         }
       }
     }
+
+    /* split patches */
+    split->split_patches(linear_patches.data(), sizeof(LinearQuadPatch));
   }
 
   /* interpolate center points for attributes */