Cycles microdisplacement: Support for Catmull-Clark subdivision via OpenSubdiv

Enables Catmull-Clark subdivision meshes with support for creases and attribute
subdivision. Still waiting on OpenSubdiv to fully support face varying
interpolation for subdividing uv coordinates tho. Also there may be some
inconsistencies with Blender's subdivision which will be resolved at a
later time.

Code for reading patch tables and creating patch maps is borrowed
from OpenSubdiv.

Reviewed By: brecht

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

3 files changed, 358 insertions, 4 deletions

diff --git a/intern/cycles/subd/CMakeLists.txt b/intern/cycles/subd/CMakeLists.txt
index db497013693..9265299e82b 100644
--- a/intern/cycles/subd/CMakeLists.txt
+++ b/intern/cycles/subd/CMakeLists.txt
@@ -16,6 +16,7 @@ set(SRC
 	subd_dice.cpp
 	subd_patch.cpp
 	subd_split.cpp
+	subd_patch_table.cpp
 )
 
 set(SRC_HEADERS
@@ -24,10 +25,6 @@ set(SRC_HEADERS
 	subd_split.h
 )
 
-if(WITH_CYCLES_OPENSUBDIV)
-	add_definitions(-DWITH_OPENSUBDIV)
-endif()
-
 include_directories(${INC})
 include_directories(SYSTEM ${INC_SYS})
 
diff --git a/intern/cycles/subd/subd_patch_table.cpp b/intern/cycles/subd/subd_patch_table.cpp
new file mode 100644
index 00000000000..a32533bbf3e
--- /dev/null
+++ b/intern/cycles/subd/subd_patch_table.cpp
@@ -0,0 +1,294 @@
+/*
+ * Based on code from OpenSubdiv released under this license:
+ *
+ * Copyright 2014 DreamWorks Animation LLC.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "Apache License")
+ * with the following modification; you may not use this file except in
+ * compliance with the Apache License and the following modification to it:
+ * Section 6. Trademarks. is deleted and replaced with:
+ *
+ * 6. Trademarks. This License does not grant permission to use the trade
+ *   names, trademarks, service marks, or product names of the Licensor
+ *   and its affiliates, except as required to comply with Section 4(c) of
+ *   the License and to reproduce the content of the NOTICE file.
+ *
+ * You may obtain a copy of the Apache License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the Apache License with the above modification is
+ * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the Apache License for the specific
+ * language governing permissions and limitations under the Apache License.
+ *
+ */
+
+#include "subd_patch_table.h"
+#include "kernel_types.h"
+
+#include "util_math.h"
+
+#ifdef WITH_OPENSUBDIV
+#include <opensubdiv/far/patchTable.h>
+#endif
+
+CCL_NAMESPACE_BEGIN
+
+#ifdef WITH_OPENSUBDIV
+
+using namespace OpenSubdiv;
+
+/* functions for building patch maps */
+
+struct PatchMapQuadNode {
+	/* sets all the children to point to the patch of index */
+	void set_child(int index)
+	{
+		for (int i = 0; i < 4; i++) {
+			children[i] = index | PATCH_MAP_NODE_IS_SET | PATCH_MAP_NODE_IS_LEAF;
+		}
+	}
+
+	/* sets the child in quadrant to point to the node or patch of the given index */
+	void set_child(unsigned char quadrant, int index, bool is_leaf=true)
+	{
+		assert(quadrant < 4);
+		children[quadrant] = index | PATCH_MAP_NODE_IS_SET | (is_leaf ? PATCH_MAP_NODE_IS_LEAF : 0);
+	}
+
+	uint children[4];
+};
+
+template<class T>
+static int resolve_quadrant(T& median, T& u, T& v)
+{
+	int quadrant = -1;
+
+	if(u < median) {
+		if(v < median) {
+			quadrant = 0;
+		}
+		else {
+			quadrant = 1;
+			v -= median;
+		}
+	}
+	else {
+		if(v < median) {
+			quadrant = 3;
+		}
+		else {
+			quadrant = 2;
+			v -= median;
+		}
+		u -= median;
+	}
+
+	return quadrant;
+}
+
+static void build_patch_map(PackedPatchTable& table, OpenSubdiv::Far::PatchTable* patch_table, int offset)
+{
+	int num_faces = 0;
+
+	for(int array = 0; array < table.num_arrays; array++) {
+		Far::ConstPatchParamArray params = patch_table->GetPatchParams(array);
+
+		for(int j = 0; j < patch_table->GetNumPatches(array); j++) {
+			num_faces = max(num_faces, (int)params[j].GetFaceId());
+		}
+	}
+	num_faces++;
+
+	vector<PatchMapQuadNode> quadtree;
+	quadtree.reserve(num_faces + table.num_patches);
+	quadtree.resize(num_faces);
+
+	/* adjust offsets to make indices relative to the table */
+	int handle_index = -(table.num_patches * PATCH_HANDLE_SIZE);
+	offset += table.total_size();
+
+	/* populate the quadtree from the FarPatchArrays sub-patches */
+	for(int array = 0; array < table.num_arrays; array++) {
+		Far::ConstPatchParamArray params = patch_table->GetPatchParams(array);
+
+		for(int i = 0; i < patch_table->GetNumPatches(array); i++, handle_index += PATCH_HANDLE_SIZE) {
+			const Far::PatchParam& param = params[i];
+			unsigned short depth = param.GetDepth();
+
+			PatchMapQuadNode* node = &quadtree[params[i].GetFaceId()];
+
+			if(depth == (param.NonQuadRoot() ? 1 : 0)) {
+				/* special case : regular BSpline face w/ no sub-patches */
+				node->set_child(handle_index + offset);
+				continue;
+			}
+
+			int u = param.GetU();
+			int v = param.GetV();
+			int pdepth = param.NonQuadRoot() ? depth-2 : depth-1;
+			int half = 1 << pdepth;
+
+			for(int j = 0; j < depth; j++) {
+				int delta = half >> 1;
+
+				int quadrant = resolve_quadrant(half, u, v);
+				assert(quadrant >= 0);
+
+				half = delta;
+
+				if(j == pdepth) {
+					/* we have reached the depth of the sub-patch : add a leaf */
+					assert(!(node->children[quadrant] & PATCH_MAP_NODE_IS_SET));
+					node->set_child(quadrant, handle_index + offset, true);
+					break;
+				}
+				else {
+					/* travel down the child node of the corresponding quadrant */
+					if(!(node->children[quadrant] & PATCH_MAP_NODE_IS_SET)) {
+						/* create a new branch in the quadrant */
+						quadtree.push_back(PatchMapQuadNode());
+
+						int idx = (int)quadtree.size() - 1;
+						node->set_child(quadrant, idx*4 + offset, false);
+
+						node = &quadtree[idx];
+					}
+					else {
+						/* travel down an existing branch */
+						uint idx = node->children[quadrant] & PATCH_MAP_NODE_INDEX_MASK;
+						node = &(quadtree[(idx - offset)/4]);
+					}
+				}
+			}
+		}
+	}
+
+	/* copy into table */
+	assert(table.table.size() == table.total_size());
+	uint map_offset = table.total_size();
+
+	table.num_nodes = quadtree.size() * 4;
+	table.table.resize(table.total_size());
+
+	uint* data = &table.table[map_offset];
+
+	for(int i = 0; i < quadtree.size(); i++) {
+		for(int j = 0; j < 4; j++) {
+			assert(quadtree[i].children[j] & PATCH_MAP_NODE_IS_SET);
+			*(data++) = quadtree[i].children[j];
+		}
+	}
+}
+
+#endif
+
+/* packed patch table functions */
+
+size_t PackedPatchTable::total_size()
+{
+	return num_arrays * PATCH_ARRAY_SIZE +
+		   num_indices +
+		   num_patches * (PATCH_PARAM_SIZE + PATCH_HANDLE_SIZE) +
+		   num_nodes * PATCH_NODE_SIZE;
+}
+
+void PackedPatchTable::pack(Far::PatchTable* patch_table, int offset)
+{
+	num_arrays = 0;
+	num_patches = 0;
+	num_indices = 0;
+	num_nodes = 0;
+
+#ifdef WITH_OPENSUBDIV
+	num_arrays = patch_table->GetNumPatchArrays();
+
+	for(int i = 0; i < num_arrays; i++) {
+		int patches = patch_table->GetNumPatches(i);
+		int num_control = patch_table->GetPatchArrayDescriptor(i).GetNumControlVertices();
+
+		num_patches += patches;
+		num_indices += patches * num_control;
+	}
+
+	table.resize(total_size());
+	uint* data = &table[0];
+
+	uint* array = data;
+	uint* index = array + num_arrays * PATCH_ARRAY_SIZE;
+	uint* param = index + num_indices;
+	uint* handle = param + num_patches * PATCH_PARAM_SIZE;
+
+	uint current_param = 0;
+
+	for(int i = 0; i < num_arrays; i++) {
+		*(array++) = patch_table->GetPatchArrayDescriptor(i).GetType();
+		*(array++) = patch_table->GetNumPatches(i);
+		*(array++) = (index - data) + offset;
+		*(array++) = (param - data) + offset;
+
+		Far::ConstIndexArray indices = patch_table->GetPatchArrayVertices(i);
+
+		for(int j = 0; j < indices.size(); j++) {
+			*(index++) = indices[j];
+		}
+
+		const Far::PatchParamTable& param_table = patch_table->GetPatchParamTable();
+
+		int num_control = patch_table->GetPatchArrayDescriptor(i).GetNumControlVertices();
+		int patches = patch_table->GetNumPatches(i);
+
+		for(int j = 0; j < patches; j++, current_param++) {
+			*(param++) = param_table[current_param].field0;
+			*(param++) = param_table[current_param].field1;
+
+			*(handle++) = (array - data) - PATCH_ARRAY_SIZE + offset;
+			*(handle++) = (param - data) - PATCH_PARAM_SIZE + offset;
+			*(handle++) = j * num_control;
+		}
+	}
+
+	build_patch_map(*this, patch_table, offset);
+#endif
+}
+
+void PackedPatchTable::copy_adjusting_offsets(uint* dest, int doffset)
+{
+	uint* src = &table[0];
+
+	/* arrays */
+	for(int i = 0; i < num_arrays; i++) {
+		*(dest++) = *(src++);
+		*(dest++) = *(src++);
+		*(dest++) = *(src++) + doffset;
+		*(dest++) = *(src++) + doffset;
+	}
+
+	/* indices */
+	for(int i = 0; i < num_indices; i++) {
+		*(dest++) = *(src++);
+	}
+
+	/* params */
+	for(int i = 0; i < num_patches; i++) {
+		*(dest++) = *(src++);
+		*(dest++) = *(src++);
+	}
+
+	/* handles */
+	for(int i = 0; i < num_patches; i++) {
+		*(dest++) = *(src++) + doffset;
+		*(dest++) = *(src++) + doffset;
+		*(dest++) = *(src++);
+	}
+
+	/* nodes */
+	for(int i = 0; i < num_nodes; i++) {
+		*(dest++) = *(src++) + doffset;
+	}
+}
+
+CCL_NAMESPACE_END
+
diff --git a/intern/cycles/subd/subd_patch_table.h b/intern/cycles/subd/subd_patch_table.h
new file mode 100644
index 00000000000..c8c7ecf9e47
--- /dev/null
+++ b/intern/cycles/subd/subd_patch_table.h
@@ -0,0 +1,63 @@
+/*
+ * Copyright 2011-2016 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 __SUBD_PATCH_TABLE_H__
+#define __SUBD_PATCH_TABLE_H__
+
+#include "util_types.h"
+#include "util_vector.h"
+
+#ifdef WITH_OPENSUBDIV
+#ifdef _MSC_VER
+#  include "iso646.h"
+#endif
+
+#include <opensubdiv/far/patchTable.h>
+#endif
+
+CCL_NAMESPACE_BEGIN
+
+#ifdef WITH_OPENSUBDIV
+using namespace OpenSubdiv;
+#else
+/* forward declare for when OpenSubdiv is unavailable */
+namespace Far { struct PatchTable; }
+#endif
+
+#define PATCH_ARRAY_SIZE 4
+#define PATCH_PARAM_SIZE 2
+#define PATCH_HANDLE_SIZE 3
+#define PATCH_NODE_SIZE 1
+
+struct PackedPatchTable {
+	vector<uint> table;
+
+	size_t num_arrays;
+	size_t num_indices;
+	size_t num_patches;
+	size_t num_nodes;
+
+	/* calculated size from num_* members */
+	size_t total_size();
+
+	void pack(Far::PatchTable* patch_table, int offset = 0);
+	void copy_adjusting_offsets(uint* dest, int doffset);
+};
+
+CCL_NAMESPACE_END
+
+#endif /* __SUBD_PATCH_TABLE_H__ */
+