1 files changed, 236 insertions, 0 deletions
diff --git a/intern/cycles/subd/subd_ring.cpp b/intern/cycles/subd/subd_ring.cpp
new file mode 100644
index 00000000000..cbd12e60da0
--- /dev/null
+++ b/intern/cycles/subd/subd_ring.cpp
@@ -0,0 +1,236 @@
+/*
+ * Copyright 2006, NVIDIA Corporation Ignacio Castano <icastano@nvidia.com>
+ * 
+ * Modifications copyright (c) 2011, Blender Foundation.
+ * All rights reserved.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+#include "subd_face.h"
+#include "subd_ring.h"
+#include "subd_stencil.h"
+#include "subd_vert.h"
+
+#include "util_algorithm.h"
+#include "util_debug.h"
+#include "util_math.h"
+
+CCL_NAMESPACE_BEGIN
+
+/* Utility for sorting verts by index */
+
+class vertex_compare
+{
+public:
+	const vector<int>& index;
+	vertex_compare(const vector<int>& index_) : index(index_) {}
+	bool operator()(int a, int b) const { return index[a] < index[b]; }
+};
+
+/* Subd Face Ring */
+
+SubdFaceRing::SubdFaceRing(SubdFace *face, SubdEdge *firstEdge)
+{
+	m_face = face;
+	m_firstEdge = firstEdge;
+	m_num_edges = face->num_edges();
+
+	assert(m_num_edges == 3 || m_num_edges == 4);
+
+	initVerts();
+}
+
+int SubdFaceRing::num_verts()
+{
+	return m_verts.size();
+}
+
+SubdVert *SubdFaceRing::vertexAt(int i)
+{
+	return m_verts[i];
+}
+
+int SubdFaceRing::vert_index(SubdVert *vertex)
+{
+	int count = this->num_verts();
+
+	for(int i = 0; i < count; i++)
+		if(m_verts[i] == vertex)
+			return i;
+	
+	assert(0);
+	return 0;
+}
+
+void SubdFaceRing::evaluate_stencils(float3 *P, StencilMask *mask, int num)
+{
+	/* first we sort verts by id. this way verts will always be added
+	   in the same order to ensure the exact same float ops happen for control
+	   points of other patches, so we get water-tight patches */
+	int num_verts = m_verts.size();
+
+	vector<int> vmap(num_verts);
+	vector<int> vertid(num_verts);
+
+	for(int v = 0; v < num_verts; v++) {
+		vmap[v] = v;
+		vertid[v] = m_verts[v]->id;
+	}
+
+	sort(vmap.begin(), vmap.end(), vertex_compare(vertid));
+
+	/* then evaluate the stencils */
+	for(int j = 0; j < num; j++) {
+		float3 p = make_float3(0.0f, 0.0f, 0.0f);
+
+		for(int i = 0; i < num_verts; i++) {
+			int idx = vmap[i];
+			p += m_verts[idx]->co * mask[j][idx];
+		}
+
+		P[j] = p;
+	}
+}
+
+bool SubdFaceRing::is_triangle()
+{
+	return m_num_edges == 3;
+}
+
+bool SubdFaceRing::is_quad()
+{
+	return m_num_edges == 4;
+}
+
+int SubdFaceRing::num_edges()
+{
+	return m_num_edges;
+}
+
+bool SubdFaceRing::is_regular(SubdFace *face)
+{
+	if(!is_quad(face))
+		return false;
+
+	for(SubdFace::EdgeIterator it(face->edges()); !it.isDone(); it.advance()) {
+		SubdEdge *edge = it.current();
+
+		/* regular faces don't have boundary edges */
+		if(edge->is_boundary())
+			return false;
+
+		/* regular faces only have ordinary verts */
+		if(edge->vert->valence() != 4)
+			return false;
+
+		/* regular faces are only adjacent to quads */
+		for(SubdVert::EdgeIterator eit(edge); !eit.isDone(); eit.advance())
+			if(eit.current()->face == NULL || eit.current()->face->num_edges() != 4)
+				return false;
+	}
+
+	return true;
+}
+
+bool SubdFaceRing::is_triangle(SubdFace *face)
+{
+	return face->num_edges() == 3;
+}
+bool SubdFaceRing::is_quad(SubdFace *face)
+{
+	return face->num_edges() == 4;
+}
+
+bool SubdFaceRing::is_boundary(SubdFace *face)
+{
+	/* note that face->is_boundary() returns a different result. That function
+	   returns true when any of the *edges* are on the boundary. however, this
+	   function returns true if any of the face *verts* are on the boundary.  */
+
+	for(SubdFace::EdgeIterator it(face->edges()); !it.isDone(); it.advance()) {
+		SubdEdge *edge = it.current();
+
+		if(edge->vert->is_boundary())
+			return true;
+	}
+
+	return false;
+}
+
+void SubdFaceRing::initVerts()
+{
+	m_verts.reserve(16);
+
+	/* add face verts */
+	for(SubdFace::EdgeIterator it(m_firstEdge); !it.isDone(); it.advance()) {
+		SubdEdge *edge = it.current();
+		m_verts.push_back(edge->from());
+	}
+	
+	// @@ Add support for non manifold surfaces!
+	// The fix: 
+	// - not all colocals should point to the same edge.
+	// - multiple colocals could belong to different boundaries, make sure they point to the right one.
+
+	// @@ When the face neighborhood wraps that could result in overlapping stencils. 
+
+	// Add surronding verts.
+	for(SubdFace::EdgeIterator it(m_firstEdge); !it.isDone(); it.advance()) {
+		SubdEdge *firstEdge = it.current();
+	
+		int i = 0;
+
+		/* traverse edges around vertex */
+		for(SubdVert::ReverseEdgeIterator eit(firstEdge); !eit.isDone(); eit.advance(), i++) {
+			SubdEdge *edge = eit.current();
+
+			assert(edge->from()->co == firstEdge->from()->co);
+
+			add_vert(edge->to());
+
+			if(edge->face != NULL)
+				add_vert(edge->next->to());
+		}
+
+		assert(i == firstEdge->from()->valence());
+	}
+}
+
+
+void SubdFaceRing::add_vert(SubdVert *vertex)
+{
+	/* avoid having duplicate verts */
+	if(!has_vert(vertex))
+		m_verts.push_back(vertex);
+}
+
+bool SubdFaceRing::has_vert(SubdVert *vertex)
+{
+	int num_verts = m_verts.size();
+
+	for(int i = 0; i < num_verts; i++)
+		if(m_verts[i]->co == vertex->co)
+			return true;
+
+	return false;
+}
+
+CCL_NAMESPACE_END
+