Cycles render engine, initial commit. This is the engine itself, blender modifications and build instructions will follow later.

Cycles uses code from some great open source projects, many thanks them:

* BVH building and traversal code from NVidia's "Understanding the Efficiency of Ray Traversal on GPUs":
http://code.google.com/p/understanding-the-efficiency-of-ray-traversal-on-gpus/
* Open Shading Language for a large part of the shading system:
http://code.google.com/p/openshadinglanguage/
* Blender for procedural textures and a few other nodes.
* Approximate Catmull Clark subdivision from NVidia Mesh tools:
http://code.google.com/p/nvidia-mesh-tools/
* Sobol direction vectors from:
http://web.maths.unsw.edu.au/~fkuo/sobol/
* Film response functions from:
http://www.cs.columbia.edu/CAVE/software/softlib/dorf.php

1 files changed, 309 insertions, 0 deletions

diff --git a/intern/cycles/subd/subd_mesh.cpp b/intern/cycles/subd/subd_mesh.cpp
new file mode 100644
index 00000000000..8ed4854b786
--- /dev/null
+++ b/intern/cycles/subd/subd_mesh.cpp
@@ -0,0 +1,309 @@
+/*
+ * Original code in the public domain -- castanyo@yahoo.es
+ * 
+ * Modifications copyright (c) 2011, Blender Foundation.
+ * All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+
+#include "subd_build.h"
+#include "subd_edge.h"
+#include "subd_face.h"
+#include "subd_mesh.h"
+#include "subd_patch.h"
+#include "subd_split.h"
+#include "subd_vert.h"
+
+#include "util_debug.h"
+#include "util_foreach.h"
+
+CCL_NAMESPACE_BEGIN
+
+SubdMesh::SubdMesh()
+{
+}
+
+SubdMesh::~SubdMesh()
+{
+	pair<Key, SubdEdge*> em;
+
+	foreach(SubdVert *vertex, verts)
+		delete vertex;
+	foreach(em, edge_map)
+		delete em.second;
+	foreach(SubdFace *face, faces)
+		delete face;
+
+	verts.clear();
+	edges.clear();
+	edge_map.clear();
+	faces.clear();
+}
+
+SubdVert *SubdMesh::add_vert(const float3& co)
+{
+	SubdVert *v = new SubdVert(verts.size());
+	v->co = co;
+	verts.push_back(v);
+
+	return v;
+}
+
+SubdFace *SubdMesh::add_face(int v0, int v1, int v2)
+{
+	int index[3] = {v0, v1, v2};
+	return add_face(index, 3);
+}
+
+SubdFace *SubdMesh::add_face(int v0, int v1, int v2, int v3)
+{
+	int index[4] = {v0, v1, v2, v3};
+	return add_face(index, 4);
+}
+
+SubdFace *SubdMesh::add_face(int *index, int num)
+{
+	/* test non-manifold cases */
+	if(!can_add_face(index, num)) {
+		/* we could try to add face in opposite winding instead .. */
+		fprintf(stderr, "Warning: non manifold mesh, invalid face '%lu'.\n", faces.size());
+		return NULL;
+	}
+	
+	SubdFace *f = new SubdFace(faces.size());
+	
+	SubdEdge *first_edge = NULL;
+	SubdEdge *last = NULL;
+	SubdEdge *current = NULL;
+
+	/* add edges */
+	for(int i = 0; i < num-1; i++) {
+		current = add_edge(index[i], index[i+1]);
+		assert(current != NULL);
+		
+		current->face = f;
+		
+		if(last != NULL) {
+			last->next = current;
+			current->prev = last;
+		}
+		else
+			first_edge = current;
+		
+		last = current;
+	}
+
+	current = add_edge(index[num-1], index[0]);
+	assert(current != NULL);
+	
+	current->face = f;
+
+	last->next = current;
+	current->prev = last;
+
+	current->next = first_edge;
+	first_edge->prev = current;
+
+	f->edge = first_edge;
+	faces.push_back(f);
+
+	return f;
+}
+
+bool SubdMesh::can_add_face(int *index, int num)
+{
+	/* manifold check */
+	for(int i = 0; i < num-1; i++)
+		if(!can_add_edge(index[i], index[i+1]))
+			return false;
+
+	return can_add_edge(index[num-1], index[0]);
+}
+
+bool SubdMesh::can_add_edge(int i, int j)
+{
+	/* check for degenerate edge */
+	if(i == j)
+		return false;
+
+	/* make sure edge has not been added yet. */
+	return find_edge(i, j) == NULL;
+}
+
+SubdEdge *SubdMesh::add_edge(int i, int j)
+{
+	SubdEdge *edge;
+
+	/* find pair */
+	SubdEdge *pair = find_edge(j, i);
+
+	if(pair != NULL) {
+		/* create edge with same id */
+		edge = new SubdEdge(pair->id + 1);
+		
+		/* link edge pairs */
+		edge->pair = pair;
+		pair->pair = edge;
+		
+		/* not sure this is necessary? */
+		pair->vert->edge = pair;
+	}
+	else {
+		/* create edge */
+		edge = new SubdEdge(2*edges.size());
+		
+		/* add only unpaired edges */
+		edges.push_back(edge);
+	}
+	
+	/* assign vertex and put into map */
+	edge->vert = verts[i];
+	edge_map[Key(i, j)] = edge;
+	
+	/* face and next are set by add_face */
+	
+	return edge;
+}
+
+SubdEdge *SubdMesh::find_edge(int i, int j)
+{
+	map<Key, SubdEdge*>::const_iterator it = edge_map.find(Key(i, j));
+
+	return (it == edge_map.end())? NULL: it->second;
+}
+
+bool SubdMesh::link_boundary()
+{
+	/* link boundary edges once the mesh has been created */
+	int num = 0;
+	
+	/* create boundary edges */
+	int num_edges = edges.size();
+
+	for(int e = 0; e < num_edges; e++) {
+		SubdEdge *edge = edges[e];
+
+		if(edge->pair == NULL) {
+			SubdEdge *pair = new SubdEdge(edge->id + 1);
+
+			int i = edge->from()->id;
+			int j = edge->to()->id;
+
+			assert(edge_map.find(Key(j, i)) == edge_map.end());
+
+			pair->vert = verts[j];
+			edge_map[Key(j, i)] = pair;
+			
+			edge->pair = pair;
+			pair->pair = edge;
+			
+			num++;
+		}
+	}
+
+	/* link boundary edges */
+	for(int e = 0; e < num_edges; e++) {
+		SubdEdge *edge = edges[e];
+
+		if(edge->pair->face == NULL)
+			link_boundary_edge(edge->pair);
+	}
+	
+	/* detect boundary intersections */
+	int boundaryIntersections = 0;
+	int num_verts = verts.size();
+
+	for(int v = 0; v < num_verts; v++) {
+		SubdVert *vertex = verts[v];
+
+		int boundarySubdEdges = 0;
+		for(SubdVert::EdgeIterator it(vertex->edges()); !it.isDone(); it.advance())
+			if(it.current()->is_boundary())
+				boundarySubdEdges++;
+
+		if(boundarySubdEdges > 2) {
+			assert((boundarySubdEdges & 1) == 0);
+			boundaryIntersections++;
+		}
+	}
+
+	if(boundaryIntersections != 0) {
+		fprintf(stderr, "Invalid mesh, boundary intersections found!\n");
+		return false;
+	}
+
+	return true;
+}
+
+void SubdMesh::link_boundary_edge(SubdEdge *edge)
+{
+	/* link this boundary edge. */
+
+	/* make sure next pointer has not been set. */
+	assert(edge->face == NULL);
+	assert(edge->next == NULL);
+		
+	SubdEdge *next = edge;
+
+	while(next->pair->face != NULL) {
+		/* get pair prev */
+		SubdEdge *e = next->pair->next;
+
+		while(e->next != next->pair)
+			e = e->next;
+
+		next = e;
+	}
+
+	edge->next = next->pair;
+	next->pair->prev = edge;
+	
+	/* adjust vertex edge, so that it's the boundary edge. (required for is_boundary()) */
+	if(edge->vert->edge != edge)
+		edge->vert->edge = edge;
+}
+
+void SubdMesh::tesselate(DiagSplit *split, bool linear, Mesh *mesh, int shader, bool smooth)
+{
+	SubdBuilder *builder = SubdBuilder::create(linear);
+	int num_faces = faces.size();
+		        
+	for(int f = 0; f < num_faces; f++) {
+		SubdFace *face = faces[f];
+		Patch *patch = builder->run(face);
+
+		if(patch->is_triangle())
+			split->split_triangle(mesh, patch, shader, smooth);
+		else
+			split->split_quad(mesh, patch, shader, smooth);
+
+		delete patch;
+	}
+
+	delete builder;
+}
+
+CCL_NAMESPACE_END
+