Cycles microdisplacement: ngons and attributes for subdivision meshes

This adds support for ngons and attributes on subdivision meshes. Ngons are
needed for proper attribute interpolation as well as correct Catmull-Clark
subdivision. Several changes are made to achieve this:

- new primitive `SubdFace` added to `Mesh`
- 3 more textures are used to store info on patches from subd meshes
- Blender export uses loop interface instead of tessface for subd meshes
- `Attribute` class is updated with a simplified way to pass primitive counts
  around and to support ngons.
- extra points for ngons are generated for O(1) attribute interpolation
- curves are temporally disabled on subd meshes to avoid various bugs with
  implementation
- old unneeded code is removed from `subd/`
- various fixes and improvements

Reviewed By: brecht

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

4 files changed, 290 insertions, 5 deletions

diff --git a/intern/cycles/kernel/geom/geom.h b/intern/cycles/kernel/geom/geom.h
index d2c7edb11ea..493afdc4f62 100644
--- a/intern/cycles/kernel/geom/geom.h
+++ b/intern/cycles/kernel/geom/geom.h
@@ -18,6 +18,7 @@
 #include "geom_attribute.h"
 #include "geom_object.h"
 #include "geom_triangle.h"
+#include "geom_subd_triangle.h"
 #include "geom_triangle_intersect.h"
 #include "geom_motion_triangle.h"
 #include "geom_motion_curve.h"
diff --git a/intern/cycles/kernel/geom/geom_attribute.h b/intern/cycles/kernel/geom/geom_attribute.h
index c7364e9edac..5d78cf8f9fc 100644
--- a/intern/cycles/kernel/geom/geom_attribute.h
+++ b/intern/cycles/kernel/geom/geom_attribute.h
@@ -25,6 +25,24 @@ CCL_NAMESPACE_BEGIN
  * Lookup of attributes is different between OSL and SVM, as OSL is ustring
  * based while for SVM we use integer ids. */
 
+ccl_device_inline uint subd_triangle_patch(KernelGlobals *kg, const ShaderData *sd);
+
+ccl_device_inline uint attribute_primitive_type(KernelGlobals *kg, const ShaderData *sd)
+{
+#ifdef __HAIR__
+	if(ccl_fetch(sd, type) & PRIMITIVE_ALL_CURVE) {
+		return ATTR_PRIM_CURVE;
+	}
+	else
+#endif
+	if(subd_triangle_patch(kg, sd) != ~0) {
+		return ATTR_PRIM_SUBD;
+	}
+	else {
+		return ATTR_PRIM_TRIANGLE;
+	}
+}
+
 /* Find attribute based on ID */
 
 ccl_device_inline int find_attribute(KernelGlobals *kg, const ShaderData *sd, uint id, AttributeElement *elem)
@@ -34,9 +52,7 @@ ccl_device_inline int find_attribute(KernelGlobals *kg, const ShaderData *sd, ui
 
 	/* for SVM, find attribute by unique id */
 	uint attr_offset = ccl_fetch(sd, object)*kernel_data.bvh.attributes_map_stride;
-#ifdef __HAIR__
-	attr_offset = (ccl_fetch(sd, type) & PRIMITIVE_ALL_CURVE)? attr_offset + ATTR_PRIM_CURVE: attr_offset;
-#endif
+	attr_offset += attribute_primitive_type(kg, sd);
 	uint4 attr_map = kernel_tex_fetch(__attributes_map, attr_offset);
 	
 	while(attr_map.x != id) {
diff --git a/intern/cycles/kernel/geom/geom_primitive.h b/intern/cycles/kernel/geom/geom_primitive.h
index b1b1e919e00..44734d1b70d 100644
--- a/intern/cycles/kernel/geom/geom_primitive.h
+++ b/intern/cycles/kernel/geom/geom_primitive.h
@@ -26,7 +26,10 @@ CCL_NAMESPACE_BEGIN
 ccl_device float primitive_attribute_float(KernelGlobals *kg, const ShaderData *sd, AttributeElement elem, int offset, float *dx, float *dy)
 {
 	if(ccl_fetch(sd, type) & PRIMITIVE_ALL_TRIANGLE) {
-		return triangle_attribute_float(kg, sd, elem, offset, dx, dy);
+		if(subd_triangle_patch(kg, sd) == ~0)
+			return triangle_attribute_float(kg, sd, elem, offset, dx, dy);
+		else
+			return subd_triangle_attribute_float(kg, sd, elem, offset, dx, dy);
 	}
 #ifdef __HAIR__
 	else if(ccl_fetch(sd, type) & PRIMITIVE_ALL_CURVE) {
@@ -48,7 +51,10 @@ ccl_device float primitive_attribute_float(KernelGlobals *kg, const ShaderData *
 ccl_device float3 primitive_attribute_float3(KernelGlobals *kg, const ShaderData *sd, AttributeElement elem, int offset, float3 *dx, float3 *dy)
 {
 	if(ccl_fetch(sd, type) & PRIMITIVE_ALL_TRIANGLE) {
-		return triangle_attribute_float3(kg, sd, elem, offset, dx, dy);
+		if(subd_triangle_patch(kg, sd) == ~0)
+			return triangle_attribute_float3(kg, sd, elem, offset, dx, dy);
+		else
+			return subd_triangle_attribute_float3(kg, sd, elem, offset, dx, dy);
 	}
 #ifdef __HAIR__
 	else if(ccl_fetch(sd, type) & PRIMITIVE_ALL_CURVE) {
diff --git a/intern/cycles/kernel/geom/geom_subd_triangle.h b/intern/cycles/kernel/geom/geom_subd_triangle.h
new file mode 100644
index 00000000000..e4597aba56e
--- /dev/null
+++ b/intern/cycles/kernel/geom/geom_subd_triangle.h
@@ -0,0 +1,262 @@
+/*
+ * 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.
+ */
+
+/* Functions for retrieving attributes on triangles produced from subdivision meshes */
+
+CCL_NAMESPACE_BEGIN
+
+/* Patch index for triangle, -1 if not subdivision triangle */
+
+ccl_device_inline uint subd_triangle_patch(KernelGlobals *kg, const ShaderData *sd)
+{
+	return kernel_tex_fetch(__tri_patch, ccl_fetch(sd, prim));
+}
+
+/* UV coords of triangle within patch */
+
+ccl_device_inline void subd_triangle_patch_uv(KernelGlobals *kg, const ShaderData *sd, float2 uv[3])
+{
+	uint4 tri_vindex = kernel_tex_fetch(__tri_vindex, ccl_fetch(sd, prim));
+
+	uv[0] = kernel_tex_fetch(__tri_patch_uv, tri_vindex.x);
+	uv[1] = kernel_tex_fetch(__tri_patch_uv, tri_vindex.y);
+	uv[2] = kernel_tex_fetch(__tri_patch_uv, tri_vindex.z);
+}
+
+/* Vertex indices of patch */
+
+ccl_device_inline uint4 subd_triangle_patch_indices(KernelGlobals *kg, int patch)
+{
+	uint4 indices;
+
+	indices.x = kernel_tex_fetch(__patches, patch+0);
+	indices.y = kernel_tex_fetch(__patches, patch+1);
+	indices.z = kernel_tex_fetch(__patches, patch+2);
+	indices.w = kernel_tex_fetch(__patches, patch+3);
+
+	return indices;
+}
+
+/* Originating face for patch */
+
+ccl_device_inline uint subd_triangle_patch_face(KernelGlobals *kg, int patch)
+{
+	return kernel_tex_fetch(__patches, patch+4);
+}
+
+/* Number of corners on originating face */
+
+ccl_device_inline uint subd_triangle_patch_num_corners(KernelGlobals *kg, int patch)
+{
+	return kernel_tex_fetch(__patches, patch+5) & 0xffff;
+}
+
+/* Indices of the four corners that are used by the patch */
+
+ccl_device_inline void subd_triangle_patch_corners(KernelGlobals *kg, int patch, int corners[4])
+{
+	uint4 data;
+
+	data.x = kernel_tex_fetch(__patches, patch+4);
+	data.y = kernel_tex_fetch(__patches, patch+5);
+	data.z = kernel_tex_fetch(__patches, patch+6);
+	data.w = kernel_tex_fetch(__patches, patch+7);
+
+	int num_corners = data.y & 0xffff;
+
+	if(num_corners == 4) {
+		/* quad */
+		corners[0] = data.z;
+		corners[1] = data.z+1;
+		corners[2] = data.z+2;
+		corners[3] = data.z+3;
+	}
+	else {
+		/* ngon */
+		int c = data.y >> 16;
+
+		corners[0] = data.z + c;
+		corners[1] = data.z + mod(c+1, num_corners);
+		corners[2] = data.w;
+		corners[3] = data.z + mod(c-1, num_corners);
+	}
+}
+
+/* Reading attributes on various subdivision triangle elements */
+
+ccl_device float subd_triangle_attribute_float(KernelGlobals *kg, const ShaderData *sd, AttributeElement elem, int offset, float *dx, float *dy)
+{
+	int patch = subd_triangle_patch(kg, sd);
+
+	if(elem == ATTR_ELEMENT_FACE) {
+		if(dx) *dx = 0.0f;
+		if(dy) *dy = 0.0f;
+
+		return kernel_tex_fetch(__attributes_float, offset + subd_triangle_patch_face(kg, patch));
+	}
+	else if(elem == ATTR_ELEMENT_VERTEX || elem == ATTR_ELEMENT_VERTEX_MOTION) {
+		float2 uv[3];
+		subd_triangle_patch_uv(kg, sd, uv);
+		uint4 v = subd_triangle_patch_indices(kg, patch);
+
+		float a, b, c;
+
+		float f0 = kernel_tex_fetch(__attributes_float, offset + v.x);
+		float f1 = kernel_tex_fetch(__attributes_float, offset + v.y);
+		float f2 = kernel_tex_fetch(__attributes_float, offset + v.z);
+		float f3 = kernel_tex_fetch(__attributes_float, offset + v.w);
+
+		if(subd_triangle_patch_num_corners(kg, patch) != 4) {
+			f1 = (f1+f0)*0.5f;
+			f3 = (f3+f0)*0.5f;
+		}
+
+		a = mix(mix(f0, f1, uv[0].x), mix(f3, f2, uv[0].x), uv[0].y);
+		b = mix(mix(f0, f1, uv[1].x), mix(f3, f2, uv[1].x), uv[1].y);
+		c = mix(mix(f0, f1, uv[2].x), mix(f3, f2, uv[2].x), uv[2].y);
+
+#ifdef __RAY_DIFFERENTIALS__
+		if(dx) *dx = ccl_fetch(sd, du).dx*a + ccl_fetch(sd, dv).dx*b - (ccl_fetch(sd, du).dx + ccl_fetch(sd, dv).dx)*c;
+		if(dy) *dy = ccl_fetch(sd, du).dy*a + ccl_fetch(sd, dv).dy*b - (ccl_fetch(sd, du).dy + ccl_fetch(sd, dv).dy)*c;
+#endif
+
+		return ccl_fetch(sd, u)*a + ccl_fetch(sd, v)*b + (1.0f - ccl_fetch(sd, u) - ccl_fetch(sd, v))*c;
+	}
+	else if(elem == ATTR_ELEMENT_CORNER) {
+		int corners[4];
+		subd_triangle_patch_corners(kg, patch, corners);
+
+		float2 uv[3];
+		subd_triangle_patch_uv(kg, sd, uv);
+
+		float a, b, c;
+
+		float f0 = kernel_tex_fetch(__attributes_float, corners[0] + offset);
+		float f1 = kernel_tex_fetch(__attributes_float, corners[1] + offset);
+		float f2 = kernel_tex_fetch(__attributes_float, corners[2] + offset);
+		float f3 = kernel_tex_fetch(__attributes_float, corners[3] + offset);
+
+		if(subd_triangle_patch_num_corners(kg, patch) != 4) {
+			f1 = (f1+f0)*0.5f;
+			f3 = (f3+f0)*0.5f;
+		}
+
+		a = mix(mix(f0, f1, uv[0].x), mix(f3, f2, uv[0].x), uv[0].y);
+		b = mix(mix(f0, f1, uv[1].x), mix(f3, f2, uv[1].x), uv[1].y);
+		c = mix(mix(f0, f1, uv[2].x), mix(f3, f2, uv[2].x), uv[2].y);
+
+#ifdef __RAY_DIFFERENTIALS__
+		if(dx) *dx = ccl_fetch(sd, du).dx*a + ccl_fetch(sd, dv).dx*b - (ccl_fetch(sd, du).dx + ccl_fetch(sd, dv).dx)*c;
+		if(dy) *dy = ccl_fetch(sd, du).dy*a + ccl_fetch(sd, dv).dy*b - (ccl_fetch(sd, du).dy + ccl_fetch(sd, dv).dy)*c;
+#endif
+
+		return ccl_fetch(sd, u)*a + ccl_fetch(sd, v)*b + (1.0f - ccl_fetch(sd, u) - ccl_fetch(sd, v))*c;
+	}
+	else {
+		if(dx) *dx = 0.0f;
+		if(dy) *dy = 0.0f;
+
+		return 0.0f;
+	}
+}
+
+ccl_device float3 subd_triangle_attribute_float3(KernelGlobals *kg, const ShaderData *sd, AttributeElement elem, int offset, float3 *dx, float3 *dy)
+{
+	int patch = subd_triangle_patch(kg, sd);
+
+	if(elem == ATTR_ELEMENT_FACE) {
+		if(dx) *dx = make_float3(0.0f, 0.0f, 0.0f);
+		if(dy) *dy = make_float3(0.0f, 0.0f, 0.0f);
+
+		return float4_to_float3(kernel_tex_fetch(__attributes_float3, offset + subd_triangle_patch_face(kg, patch)));
+	}
+	else if(elem == ATTR_ELEMENT_VERTEX || elem == ATTR_ELEMENT_VERTEX_MOTION) {
+		float2 uv[3];
+		subd_triangle_patch_uv(kg, sd, uv);
+		uint4 v = subd_triangle_patch_indices(kg, patch);
+
+		float3 a, b, c;
+
+		float3 f0 = float4_to_float3(kernel_tex_fetch(__attributes_float3, offset + v.x));
+		float3 f1 = float4_to_float3(kernel_tex_fetch(__attributes_float3, offset + v.y));
+		float3 f2 = float4_to_float3(kernel_tex_fetch(__attributes_float3, offset + v.z));
+		float3 f3 = float4_to_float3(kernel_tex_fetch(__attributes_float3, offset + v.w));
+
+		if(subd_triangle_patch_num_corners(kg, patch) != 4) {
+			f1 = (f1+f0)*0.5f;
+			f3 = (f3+f0)*0.5f;
+		}
+
+		a = mix(mix(f0, f1, uv[0].x), mix(f3, f2, uv[0].x), uv[0].y);
+		b = mix(mix(f0, f1, uv[1].x), mix(f3, f2, uv[1].x), uv[1].y);
+		c = mix(mix(f0, f1, uv[2].x), mix(f3, f2, uv[2].x), uv[2].y);
+
+#ifdef __RAY_DIFFERENTIALS__
+		if(dx) *dx = ccl_fetch(sd, du).dx*a + ccl_fetch(sd, dv).dx*b - (ccl_fetch(sd, du).dx + ccl_fetch(sd, dv).dx)*c;
+		if(dy) *dy = ccl_fetch(sd, du).dy*a + ccl_fetch(sd, dv).dy*b - (ccl_fetch(sd, du).dy + ccl_fetch(sd, dv).dy)*c;
+#endif
+
+		return ccl_fetch(sd, u)*a + ccl_fetch(sd, v)*b + (1.0f - ccl_fetch(sd, u) - ccl_fetch(sd, v))*c;
+	}
+	else if(elem == ATTR_ELEMENT_CORNER || elem == ATTR_ELEMENT_CORNER_BYTE) {
+		int corners[4];
+		subd_triangle_patch_corners(kg, patch, corners);
+
+		float2 uv[3];
+		subd_triangle_patch_uv(kg, sd, uv);
+
+		float3 a, b, c;
+		float3 f0, f1, f2, f3;
+
+		if(elem == ATTR_ELEMENT_CORNER) {
+			f0 = float4_to_float3(kernel_tex_fetch(__attributes_float3, corners[0] + offset));
+			f1 = float4_to_float3(kernel_tex_fetch(__attributes_float3, corners[1] + offset));
+			f2 = float4_to_float3(kernel_tex_fetch(__attributes_float3, corners[2] + offset));
+			f3 = float4_to_float3(kernel_tex_fetch(__attributes_float3, corners[3] + offset));
+		}
+		else {
+			f0 = color_byte_to_float(kernel_tex_fetch(__attributes_uchar4, corners[0] + offset));
+			f1 = color_byte_to_float(kernel_tex_fetch(__attributes_uchar4, corners[1] + offset));
+			f2 = color_byte_to_float(kernel_tex_fetch(__attributes_uchar4, corners[2] + offset));
+			f3 = color_byte_to_float(kernel_tex_fetch(__attributes_uchar4, corners[3] + offset));
+		}
+
+		if(subd_triangle_patch_num_corners(kg, patch) != 4) {
+			f1 = (f1+f0)*0.5f;
+			f3 = (f3+f0)*0.5f;
+		}
+
+		a = mix(mix(f0, f1, uv[0].x), mix(f3, f2, uv[0].x), uv[0].y);
+		b = mix(mix(f0, f1, uv[1].x), mix(f3, f2, uv[1].x), uv[1].y);
+		c = mix(mix(f0, f1, uv[2].x), mix(f3, f2, uv[2].x), uv[2].y);
+
+#ifdef __RAY_DIFFERENTIALS__
+		if(dx) *dx = ccl_fetch(sd, du).dx*a + ccl_fetch(sd, dv).dx*b - (ccl_fetch(sd, du).dx + ccl_fetch(sd, dv).dx)*c;
+		if(dy) *dy = ccl_fetch(sd, du).dy*a + ccl_fetch(sd, dv).dy*b - (ccl_fetch(sd, du).dy + ccl_fetch(sd, dv).dy)*c;
+#endif
+
+		return ccl_fetch(sd, u)*a + ccl_fetch(sd, v)*b + (1.0f - ccl_fetch(sd, u) - ccl_fetch(sd, v))*c;
+	}
+	else {
+		if(dx) *dx = make_float3(0.0f, 0.0f, 0.0f);
+		if(dy) *dy = make_float3(0.0f, 0.0f, 0.0f);
+
+		return make_float3(0.0f, 0.0f, 0.0f);
+	}
+}
+
+CCL_NAMESPACE_END
+