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

3 files changed, 30 insertions, 0 deletions

diff --git a/intern/cycles/util/CMakeLists.txt b/intern/cycles/util/CMakeLists.txt
index 4f1c82897cc..a6a6b6704f0 100644
--- a/intern/cycles/util/CMakeLists.txt
+++ b/intern/cycles/util/CMakeLists.txt
@@ -55,6 +55,7 @@ set(SRC_HEADERS
   util_boundbox.h
   util_debug.h
   util_defines.h
+  util_deque.h
   util_guarded_allocator.cpp
   util_foreach.h
   util_function.h
diff --git a/intern/cycles/util/util_deque.h b/intern/cycles/util/util_deque.h
new file mode 100644
index 00000000000..ccac961aa7d
--- /dev/null
+++ b/intern/cycles/util/util_deque.h
@@ -0,0 +1,28 @@
+/*
+ * Copyright 2011-2018 Blender Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __UTIL_DEQUE_H__
+#define __UTIL_DEQUE_H__
+
+#include <deque>
+
+CCL_NAMESPACE_BEGIN
+
+using std::deque;
+
+CCL_NAMESPACE_END
+
+#endif /* __UTIL_DEQUE_H__ */
diff --git a/intern/cycles/util/util_map.h b/intern/cycles/util/util_map.h
index 8385b08dd5a..f1b2522362f 100644
--- a/intern/cycles/util/util_map.h
+++ b/intern/cycles/util/util_map.h
@@ -25,6 +25,7 @@ CCL_NAMESPACE_BEGIN
 using std::map;
 using std::pair;
 using std::unordered_map;
+using std::unordered_multimap;
 
 template<typename T> static void map_free_memory(T &data)
 {