Raytrace modifications from the Render Branch.

These should not have any effect on render results, except in some cases with
you have overlapping faces, where the noise seems to be slightly reduced.

There are some performance improvements, for simple scenes I wouldn't expect
more than 5-10% to be cut off the render time, for sintel scenes we got about
50% on average, that's with millions of polygons on intel quad cores. This
because memory access / cache misses were the main bottleneck for those scenes,
and the optimizations improve that.

Interal changes:

* Remove RE_raytrace.h, raytracer is now only used by render engine again.
* Split non-public parts rayobject.h into rayobject_internal.h, hopefully
 makes it clearer how the API is used.
* Added rayintersection.h to contain some of the stuff from RE_raytrace.h
* Change Isect.vec/labda to Isect.dir/dist, previously vec was sometimes
  normalized and sometimes not, confusing... now dir is always normalized
  and dist contains the distance.
* Change VECCOPY and similar to BLI_math functions.
* Force inlining of auxiliary functions for ray-triangle/quad intersection,
  helps a few percentages.
* Reorganize svbvh code so all the traversal functions are in one file
* Don't do test for root so that push_childs can be inlined
* Make shadow a template parameter so it doesn't need to be runtime checked
* Optimization in raytree building, was computing bounding boxes more often
  than necessary.
* Leave out logf() factor in SAH, makes tree build quicker with no
  noticeable influence on raytracing on performance?
* Set max childs to 4, simplifies traversal code a bit, but also seems
  to help slightly in general.
* Store child pointers and child bb just as fixed arrays of size 4 in nodes,
  nearly all nodes have this many children, so overall it actually reduces
  memory usage a bit and avoids a pointer indirection.

1 files changed, 124 insertions, 0 deletions

diff --git a/source/blender/render/intern/include/rayintersection.h b/source/blender/render/intern/include/rayintersection.h
new file mode 100644
index 00000000000..5a8b989abbc
--- /dev/null
+++ b/source/blender/render/intern/include/rayintersection.h
@@ -0,0 +1,124 @@
+/**
+ * $Id: rayintersection.h 29491 2010-06-16 18:57:23Z blendix $
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. 
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2007 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ * RE_raytrace.h: ray tracing api, can be used independently from the renderer. 
+ */
+
+#ifndef __RENDER_RAYINTERSECTION_H__
+#define __RENDER_RAYINTERSECTION_H__
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct RayObject;
+
+/* Ray Hints */
+
+#define RE_RAY_LCTS_MAX_SIZE	256
+#define RT_USE_LAST_HIT			/* last shadow hit is reused before raycasting on whole tree */
+//#define RT_USE_HINT			/* last hit object is reused before raycasting on whole tree */
+
+typedef struct LCTSHint {
+	int size;
+	struct RayObject *stack[RE_RAY_LCTS_MAX_SIZE];
+} LCTSHint;
+
+typedef struct RayHint {
+	union { LCTSHint lcts; } data;
+} RayHint;
+
+/* Ray Intersection */
+
+typedef struct Isect {
+	/* ray start, direction (normalized vector), and max distance. on hit,
+	   the distance is modified to be the distance to the hit point. */
+	float start[3];
+	float dir[3];
+	float dist;
+
+	/* precomputed values to accelerate bounding box intersection */
+	int bv_index[6];
+	float idot_axis[3];
+
+	/* intersection options */
+	int mode;				/* RE_RAY_SHADOW, RE_RAY_MIRROR, RE_RAY_SHADOW_TRA */
+	int lay;				/* -1 default, set for layer lamps */
+	int skip;				/* skip flags */
+	int check;				/* check flags */
+	void *userdata;			/* used by bake check */
+
+	/* hit information */
+	float u, v;
+	int isect;				/* which half of quad */
+	
+	struct {
+		void *ob;
+		void *face;
+	} hit, orig;
+	
+	/* last hit optimization */
+	struct RayObject *last_hit;
+
+	/* hints */
+#ifdef RT_USE_HINT
+	RayTraceHint *hint, *hit_hint;
+#endif
+	RayHint *hint;
+	
+	/* ray counter */
+#ifdef RE_RAYCOUNTER
+	RayCounter *raycounter;
+#endif
+} Isect;
+
+/* ray types */
+#define RE_RAY_SHADOW 0
+#define RE_RAY_MIRROR 1
+#define RE_RAY_SHADOW_TRA 2
+
+/* skip options */
+#define RE_SKIP_CULLFACE                (1 << 0)
+/* if using this flag then *face should be a pointer to a VlakRen */
+#define RE_SKIP_VLR_NEIGHBOUR           (1 << 1)
+
+/* check options */
+#define RE_CHECK_VLR_NONE               0
+#define RE_CHECK_VLR_RENDER             1
+#define RE_CHECK_VLR_NON_SOLID_MATERIAL 2
+#define RE_CHECK_VLR_BAKE               3
+
+/* arbitrary, but can't use e.g. FLT_MAX because of precision issues */
+#define RE_RAYTRACE_MAXDIST	1e15f
+#define RE_RAYTRACE_EPSILON 0.0f
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __RENDER_RAYINTERSECTION_H__ */
+