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, 152 insertions, 0 deletions

diff --git a/intern/cycles/bvh/bvh_build.h b/intern/cycles/bvh/bvh_build.h
new file mode 100644
index 00000000000..1fa1951d7f2
--- /dev/null
+++ b/intern/cycles/bvh/bvh_build.h
@@ -0,0 +1,152 @@
+/*
+ * Adapted from code copyright 2009-2010 NVIDIA Corporation
+ * Modifications Copyright 2011, 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 __BVH_BUILD_H__
+#define __BVH_BUILD_H__
+
+#include <float.h>
+
+#include "bvh.h"
+
+#include "util_boundbox.h"
+#include "util_vector.h"
+
+CCL_NAMESPACE_BEGIN
+
+class BVHParams;
+class Mesh;
+class Object;
+class Progress;
+
+/* BVH Builder */
+
+class BVHBuild
+{
+public:
+	struct Reference
+	{
+		int prim_index;
+		int prim_object;
+		BoundBox bounds;
+
+		Reference()
+		{
+		}
+	};
+
+	struct NodeSpec
+	{
+		int num;
+		BoundBox bounds;
+
+		NodeSpec()
+		{
+			num = 0;
+		}
+	};
+
+	BVHBuild(
+		const vector<Object*>& objects,
+		vector<int>& prim_index,
+		vector<int>& prim_object,
+		const BVHParams& params,
+		Progress& progress);
+	~BVHBuild();
+
+	BVHNode *run();
+
+protected:
+	/* adding references */
+	void add_reference_mesh(NodeSpec& root, Mesh *mesh, int i);
+	void add_reference_object(NodeSpec& root, Object *ob, int i);
+	void add_references(NodeSpec& root);
+
+	/* building */
+	BVHNode *build_node(const NodeSpec& spec, int level, float progress_start, float progress_end);
+	BVHNode *create_leaf_node(const NodeSpec& spec);
+	BVHNode *create_object_leaf_nodes(const Reference *ref, int num);
+
+	void progress_update(float progress_start, float progress_end);
+
+	/* object splits */
+	struct ObjectSplit
+	{
+		float sah;
+		int dim;
+		int num_left;
+		BoundBox left_bounds;
+		BoundBox right_bounds;
+
+		ObjectSplit()
+		: sah(FLT_MAX), dim(0), num_left(0)
+		{
+		}
+	};
+
+	ObjectSplit find_object_split(const NodeSpec& spec, float nodeSAH);
+	void do_object_split(NodeSpec& left, NodeSpec& right, const NodeSpec& spec, const ObjectSplit& split);
+
+	/* spatial splits */
+	struct SpatialSplit
+	{
+		float sah;
+		int dim;
+		float pos;
+
+		SpatialSplit()
+		: sah(FLT_MAX), dim(0), pos(0.0f)
+		{
+		}
+	};
+
+	struct SpatialBin
+	{
+		BoundBox bounds;
+		int enter;
+		int exit;
+	};
+
+	SpatialSplit find_spatial_split(const NodeSpec& spec, float nodeSAH);
+	void do_spatial_split(NodeSpec& left, NodeSpec& right, const NodeSpec& spec, const SpatialSplit& split);
+	void split_reference(Reference& left, Reference& right, const Reference& ref, int dim, float pos);
+
+	/* objects and primitive references */
+	vector<Object*> objects;
+	vector<Reference> references;
+
+	/* output primitive indexes and objects */
+	vector<int>& prim_index;
+	vector<int>& prim_object;
+
+	/* build parameters */
+	BVHParams params;
+
+	/* progress reporting */
+	Progress& progress;
+	double progress_start_time;
+	int progress_num_duplicates;
+
+	/* spatial splitting */
+	float spatial_min_overlap;
+	vector<BoundBox> spatial_right_bounds;
+	SpatialBin spatial_bins[3][BVHParams::NUM_SPATIAL_BINS];
+};
+
+CCL_NAMESPACE_END
+
+#endif /* __BVH_BUILD_H__ */
+