Merge with trunk/2.5 at r25563

Most likely will not compile for others, I'd appreciate any build errors
and missing files reports (I can never seem to get everything committed
and all the build systems working without help).

Porting over the sculpt/multires tools was a breeze,
thanks goes to brecht for a design that didn't exclude
ngons and was easy to port.

Note that I've not tested externally-backed multires
file support yet.  Also, I still need to write version
patch code for some cases.

Some notes:

* Like trunk, topological changes don't update multires right,
  so e.g. subdivide will duplicate multires data on the new faces,
  instead of subdividing it.
* If you set the debug value (ctrl-alt-d) to 1 it'll turn on
  my experiments in speeding up sculpting on higher-res multires
  meshes (but note it makes partial redraw not completely accurate).
* There's a bug where you have to go through editmode to get out
  of sculpt mode, not sure if I inherited or created this myself.

26 files changed, 2043 insertions, 73 deletions

diff --git a/source/blender/blenlib/BLI_blenlib.h b/source/blender/blenlib/BLI_blenlib.h
index cb5f68ed1e0..70f15f0f3af 100644
--- a/source/blender/blenlib/BLI_blenlib.h
+++ b/source/blender/blenlib/BLI_blenlib.h
@@ -78,7 +78,7 @@ extern "C" {
 
 #include "BLI_string.h"
 
-#include "BLI_util.h"
+#include "BLI_path_util.h"
 
 #include "BLI_storage.h"
 
diff --git a/source/blender/blenlib/BLI_listbase.h b/source/blender/blenlib/BLI_listbase.h
index 21b4c83bd88..bd735888f95 100644
--- a/source/blender/blenlib/BLI_listbase.h
+++ b/source/blender/blenlib/BLI_listbase.h
@@ -55,7 +55,7 @@ void BLI_sortlist(struct ListBase *listbase, int (*cmp)(void *, void *));
 void BLI_freelist(struct ListBase *listbase);
 int BLI_countlist(struct ListBase *listbase);
 void BLI_freelinkN(struct ListBase *listbase, void *vlink);
-void BLI_duplicatelist(struct ListBase *list1, struct ListBase *list2);  /* copy from 2 to 1 */
+void BLI_duplicatelist(struct ListBase *list1, const struct ListBase *list2);
 
 /* create a generic list node containing link to provided data */
 struct LinkData *BLI_genericNodeN(void *data);
diff --git a/source/blender/blenlib/BLI_math_base.h b/source/blender/blenlib/BLI_math_base.h
index 4e845ae35d9..af301386920 100644
--- a/source/blender/blenlib/BLI_math_base.h
+++ b/source/blender/blenlib/BLI_math_base.h
@@ -148,6 +148,8 @@ float power_of_2(float f);
 
 float shell_angle_to_dist(float angle);
 
+double double_round(double x, int ndigits);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/source/blender/blenlib/BLI_math_color.h b/source/blender/blenlib/BLI_math_color.h
index b2d14f3ecbd..7444e01c3a6 100644
--- a/source/blender/blenlib/BLI_math_color.h
+++ b/source/blender/blenlib/BLI_math_color.h
@@ -32,10 +32,16 @@
 extern "C" {
 #endif
 
-#define BLI_CS_SMPTE	0
-#define BLI_CS_REC709	1
-#define BLI_CS_CIE		2
+/* primaries */
+#define BLI_XYZ_SMPTE	0
+#define BLI_XYZ_REC709_SRGB	1
+#define BLI_XYZ_CIE		2
 
+/* built-in profiles */
+#define BLI_PR_NONE		0
+#define BLI_PR_SRGB		1
+#define BLI_PR_REC709	2
+	
 /******************* Conversion to RGB ********************/
 
 void hsv_to_rgb(float h, float s, float v, float *r, float *g, float *b);
@@ -53,6 +59,16 @@ void rgb_to_hsv(float r, float g, float b, float *lh, float *ls, float *lv);
 unsigned int rgb_to_cpack(float r, float g, float b);
 unsigned int hsv_to_cpack(float h, float s, float v);
 
+/***************** Profile Transformations ********************/
+
+void gamma_correct(float *c, float gamma);
+float rec709_to_linearrgb(float c);
+float linearrgb_to_rec709(float c);
+float srgb_to_linearrgb(float c);
+float linearrgb_to_srgb(float c);
+void srgb_to_linearrgb_v3_v3(float *col_to, float *col_from);
+void linearrgb_to_srgb_v3_v3(float *col_to, float *col_from);
+	
 /************************** Other *************************/
 
 int constrain_rgb(float *r, float *g, float *b);
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index d54be9d5e03..49d335f6c5c 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -85,6 +85,8 @@ int isect_ray_tri_v3(float p1[3], float d[3],
 	float v0[3], float v1[3], float v2[3], float *lambda, float *uv);
 int isect_ray_tri_threshold_v3(float p1[3], float d[3],
 	float v0[3], float v1[3], float v2[3], float *lambda, float *uv, float threshold);
+int isect_ray_tri_epsilon_v3(float p1[3], float d[3],
+	float v0[3], float v1[3], float v2[3], float *lambda, float *uv, float epsilon);
 
 /* point in polygon */
 int isect_point_tri_v2(float p[2], float a[2], float b[2], float c[2]);
@@ -148,6 +150,12 @@ void sum_or_add_vertex_tangent(void *arena, VertexTangent **vtang,
 void tangent_from_uv(float *uv1, float *uv2, float *uv3,
 	float *co1, float *co2, float *co3, float *n, float *tang);
 
+/********************************* vector clouds******************************/
+
+
+void vcloud_estimate_transform(int list_size, float (*pos)[3], float *weight,float (*rpos)[3], float *rweight,
+							float lloc[3],float rloc[3],float lrot[3][3],float lscale[3][3]);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/source/blender/blenlib/BLI_math_matrix.h b/source/blender/blenlib/BLI_math_matrix.h
index 53476e4d03c..5667fb79332 100644
--- a/source/blender/blenlib/BLI_math_matrix.h
+++ b/source/blender/blenlib/BLI_math_matrix.h
@@ -82,6 +82,7 @@ void mul_m4_v4(float M[4][4], float r[3]);
 void mul_project_m4_v4(float M[4][4], float r[3]);
 
 void mul_m3_v3(float M[3][3], float r[3]);
+void mul_v3_m3v3(float r[3], float M[3][3], float a[3]);
 void mul_transposed_m3_v3(float M[3][3], float r[3]);
 void mul_m3_v3_double(float M[3][3], double r[3]);
 
diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h
index e21c3800acc..e915a9a85f3 100644
--- a/source/blender/blenlib/BLI_math_vector.h
+++ b/source/blender/blenlib/BLI_math_vector.h
@@ -54,6 +54,9 @@ MINLINE void zero_v3(float r[3]);
 MINLINE void copy_v2_v2(float r[2], float a[2]);
 MINLINE void copy_v3_v3(float r[3], float a[3]);
 
+MINLINE void swap_v2_v2(float a[2], float b[2]);
+MINLINE void swap_v3_v3(float a[3], float b[3]);
+
 /********************************* Arithmetic ********************************/
 
 MINLINE void add_v2_v2(float r[2], float a[2]);
@@ -72,6 +75,11 @@ MINLINE void mul_v3_v3fl(float r[3], float a[3], float f);
 MINLINE void mul_v3_v3(float r[3], float a[3]);
 MINLINE void mul_v3_v3v3(float r[3], float a[3], float b[3]);
 
+MINLINE void madd_v3_v3fl(float r[3], float a[3], float f);
+MINLINE void madd_v3_v3v3(float r[3], float a[3], float b[3]);
+MINLINE void madd_v3_v3v3fl(float r[3], float a[3], float b[3], float f);
+MINLINE void madd_v3_v3v3v3(float r[3], float a[3], float b[3], float c[3]);
+
 MINLINE void negate_v3(float r[3]);
 MINLINE void negate_v3_v3(float r[3], float a[3]);
 
@@ -123,6 +131,8 @@ float angle_normalized_v2v2(float a[2], float b[2]);
 float angle_v3v3(float a[2], float b[2]);
 float angle_v3v3v3(float a[2], float b[2], float c[2]);
 float angle_normalized_v3v3(float a[3], float b[3]);
+void angle_tri_v3(float angles[3], const float v1[3], const float v2[3], const float v3[3]);
+void angle_quad_v3(float angles[4], const float v1[3], const float v2[3], const float v3[3], const float v4[3]);
 
 /********************************* Geometry **********************************/
 
@@ -137,8 +147,8 @@ void print_v2(char *str, float a[2]);
 void print_v3(char *str, float a[3]);
 void print_v4(char *str, float a[4]);
 
-void normal_short_to_float_v3(float r[3], short n[3]);
-void normal_float_to_short_v3(short r[3], float n[3]);
+MINLINE void normal_short_to_float_v3(float r[3], short n[3]);
+MINLINE void normal_float_to_short_v3(short r[3], float n[3]);
 
 void minmax_v3_v3v3(float r[3], float min[3], float max[3]);
 
diff --git a/source/blender/blenlib/BLI_util.h b/source/blender/blenlib/BLI_path_util.h
index 7642b71eea0..ca483903d46 100644
--- a/source/blender/blenlib/BLI_util.h
+++ b/source/blender/blenlib/BLI_path_util.h
@@ -61,7 +61,7 @@ void BLI_split_dirfile_basic(const char *string, char *dir, char *file);
 void BLI_join_dirfile(char *string, const char *dir, const char *file);
 void BLI_getlastdir(const char* dir, char *last, int maxlen);
 int BLI_testextensie(const char *str, const char *ext);
-void BLI_uniquename(struct ListBase *list, void *vlink, char defname[], char delim, short name_offs, short len);
+void BLI_uniquename(struct ListBase *list, void *vlink, const char defname[], char delim, short name_offs, short len);
 void BLI_newname(char * name, int add);
 int BLI_stringdec(char *string, char *kop, char *start, unsigned short *numlen);
 void BLI_stringenc(char *string, char *kop, char *start, unsigned short numlen, int pic);
diff --git a/source/blender/blenlib/BLI_pbvh.h b/source/blender/blenlib/BLI_pbvh.h
new file mode 100644
index 00000000000..148d9507c14
--- /dev/null
+++ b/source/blender/blenlib/BLI_pbvh.h
@@ -0,0 +1,219 @@
+/**
+ * A BVH for high poly meshes.
+ * 
+ * $Id$
+ *
+ * ***** 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef BLI_PBVH_H
+#define BLI_PBVH_H
+
+struct MFace;
+struct MVert;
+struct DMGridAdjacency;
+struct DMGridData;
+struct PBVH;
+struct PBVHNode;
+struct ListBase;
+
+typedef struct PBVH PBVH;
+typedef struct PBVHNode PBVHNode;
+
+/* Callbacks */
+
+/* returns 1 if the search should continue from this node, 0 otherwise */
+typedef int (*BLI_pbvh_SearchCallback)(PBVHNode *node, void *data);
+
+typedef void (*BLI_pbvh_HitCallback)(PBVHNode *node, void *data);
+
+/* Building */
+
+PBVH *BLI_pbvh_new(void);
+void BLI_pbvh_build_mesh(PBVH *bvh, struct MFace *faces, struct MVert *verts,
+		    int totface, int totvert);
+void BLI_pbvh_build_grids(PBVH *bvh, struct DMGridData **grids,
+	struct DMGridAdjacency *gridadj, int totgrid,
+	int gridsize, void **gridfaces);
+void BLI_pbvh_free(PBVH *bvh);
+
+/* Hierarchical Search in the BVH, two methods:
+   * for each hit calling a callback
+   * gather nodes in an array (easy to multithread) */
+
+void BLI_pbvh_search_callback(PBVH *bvh,
+	BLI_pbvh_SearchCallback scb, void *search_data,
+	BLI_pbvh_HitCallback hcb, void *hit_data);
+
+void BLI_pbvh_search_gather(PBVH *bvh,
+	BLI_pbvh_SearchCallback scb, void *search_data,
+	PBVHNode ***array, int *tot);
+
+/* Raycast
+   the hit callback is called for all leaf nodes intersecting the ray;
+   it's up to the callback to find the primitive within the leaves that is
+   hit first */
+
+void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitCallback cb, void *data,
+		      float ray_start[3], float ray_normal[3], int original);
+int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
+	float ray_start[3], float ray_normal[3], float *dist);
+
+/* Drawing */
+
+void BLI_pbvh_node_draw(PBVHNode *node, void *data);
+int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data);
+void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3]);
+
+/* Node Access */
+
+typedef enum {
+	PBVH_Leaf = 1,
+
+	PBVH_UpdateNormals = 2,
+	PBVH_UpdateBB = 4,
+	PBVH_UpdateOriginalBB = 8,
+	PBVH_UpdateDrawBuffers = 16,
+	PBVH_UpdateRedraw = 32
+} PBVHNodeFlags;
+
+void BLI_pbvh_node_mark_update(PBVHNode *node);
+
+void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node,
+	int **grid_indices, int *totgrid, int *maxgrid, int *gridsize,
+	struct DMGridData ***griddata, struct DMGridAdjacency **gridadj);
+void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node,
+	int *uniquevert, int *totvert);
+void BLI_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node,
+	int **vert_indices, struct MVert **verts);
+
+void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
+void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
+
+/* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */
+
+void BLI_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]);
+void BLI_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3]);
+void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *totface);
+
+/* Vertex Iterator */
+
+/* this iterator has quite a lot of code, but it's designed to:
+   - allow the compiler to eliminate dead code and variables
+   - spend most of the time in the relatively simple inner loop */
+
+#define PBVH_ITER_ALL		0
+#define PBVH_ITER_UNIQUE	1
+
+typedef struct PBVHVertexIter {
+	/* iteration */
+	int g;
+	int width;
+	int height;
+	int skip;
+	int gx;
+	int gy;
+	int i;
+
+	/* grid */
+	struct DMGridData **grids;
+	struct DMGridData *grid;
+	int *grid_indices;
+	int totgrid;
+	int gridsize;
+
+	/* mesh */
+	struct MVert *mverts;
+	int totvert;
+	int *vert_indices;
+
+	/* result: these are all computed in the macro, but we assume
+	   that compiler optimizations will skip the ones we don't use */
+	struct MVert *mvert;
+	float *co;
+	short *no;
+	float *fno;
+} PBVHVertexIter;
+
+#define BLI_pbvh_vertex_iter_begin(bvh, node, vi, mode) \
+	{ \
+		struct DMGridData **grids; \
+		struct MVert *verts; \
+		int *grid_indices, totgrid, gridsize, *vert_indices, uniq_verts, totvert; \
+		\
+		memset(&vi, 0, sizeof(PBVHVertexIter)); \
+		\
+		BLI_pbvh_node_get_grids(bvh, node, &grid_indices, &totgrid, NULL, &gridsize, &grids, NULL); \
+		BLI_pbvh_node_num_verts(bvh, node, &uniq_verts, &totvert); \
+		BLI_pbvh_node_get_verts(bvh, node, &vert_indices, &verts); \
+		\
+		vi.grids= grids; \
+		vi.grid_indices= grid_indices; \
+		vi.totgrid= (grids)? totgrid: 1; \
+		vi.gridsize= gridsize; \
+		\
+		if(mode == PBVH_ITER_ALL) \
+			vi.totvert = totvert; \
+		else \
+			vi.totvert= uniq_verts; \
+		vi.vert_indices= vert_indices; \
+		vi.mverts= verts; \
+	}\
+	\
+	for(vi.i=0, vi.g=0; vi.g<vi.totgrid; vi.g++) { \
+		if(vi.grids) { \
+			vi.width= vi.gridsize; \
+			vi.height= vi.gridsize; \
+			vi.grid= vi.grids[vi.grid_indices[vi.g]]; \
+			vi.skip= 0; \
+		 	\
+			/*if(mode == PVBH_ITER_UNIQUE) { \
+				vi.grid += subm->grid.offset; \
+				vi.skip= subm->grid.skip; \
+				vi.grid -= skip; \
+			}*/ \
+		} \
+		else { \
+			vi.width= vi.totvert; \
+			vi.height= 1; \
+		} \
+	 	\
+		for(vi.gy=0; vi.gy<vi.height; vi.gy++) { \
+			if(vi.grid) vi.grid += vi.skip; \
+			\
+			for(vi.gx=0; vi.gx<vi.width; vi.gx++, vi.i++) { \
+				if(vi.grid) { \
+					vi.co= vi.grid->co; \
+					vi.fno= vi.grid->no; \
+					vi.grid++; \
+				} \
+				else { \
+					vi.mvert= &vi.mverts[vi.vert_indices[vi.gx]]; \
+					vi.co= vi.mvert->co; \
+					vi.no= vi.mvert->no; \
+				} \
+
+#define BLI_pbvh_vertex_iter_end \
+			} \
+		} \
+	}
+
+
+#endif /* BLI_PBVH_H */
+
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 4ed9eb4b007..00a5440bc75 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -28,6 +28,7 @@ FILE(GLOB SRC intern/*.c)
 
 SET(INC 
 	. ../makesdna ../blenkernel ../../../intern/guardedalloc ../include
+	../gpu
 	${FREETYPE_INCLUDE_DIRS}
 	${ZLIB_INC}
 )
diff --git a/source/blender/blenlib/SConscript b/source/blender/blenlib/SConscript
index fc586de5085..30c8e4dad50 100644
--- a/source/blender/blenlib/SConscript
+++ b/source/blender/blenlib/SConscript
@@ -4,10 +4,11 @@ Import ('env')
 sources = env.Glob('intern/*.c')
 
 cflags=''
-incs = '. ../makesdna ../blenkernel #/intern/guardedalloc ../editors/include'
+incs = '. ../makesdna ../blenkernel #/intern/guardedalloc ../editors/include ../gpu '
+incs += ' ../windowmanager #/extern/glew/include'
 incs += ' ' + env['BF_FREETYPE_INC']
 incs += ' ' + env['BF_ZLIB_INC']
-defs = ''
+defs = 'GLEW_STATIC'
 
 if env['OURPLATFORM'] == 'linux2':
     cflags='-pthread'
diff --git a/source/blender/blenlib/intern/BLI_bfile.c b/source/blender/blenlib/intern/BLI_bfile.c
index d9f6c8ad96f..8e3235bbf23 100644
--- a/source/blender/blenlib/intern/BLI_bfile.c
+++ b/source/blender/blenlib/intern/BLI_bfile.c
@@ -41,7 +41,7 @@
 #include "MEM_guardedalloc.h"
 #include "BKE_utildefines.h"
 #include "BKE_blender.h"
-#include "BLI_util.h"
+#include "BLI_path_util.h"
 #include "BLI_fileops.h"
 #include "BLI_storage.h"
 #include "BLI_bfile.h"
diff --git a/source/blender/blenlib/intern/Makefile b/source/blender/blenlib/intern/Makefile
index f729a4e3fe0..d8aed3ac0ed 100644
--- a/source/blender/blenlib/intern/Makefile
+++ b/source/blender/blenlib/intern/Makefile
@@ -50,6 +50,8 @@ CPPFLAGS += -I../../editors/include/
 # path to zlib
 CPPFLAGS += -I$(NAN_ZLIB)/include
 
+CPPFLAGS += -I../../gpu
+
 ifdef NAN_PTHREADS
   CPPFLAGS += -I$(NAN_PTHREADS)/include
 endif
diff --git a/source/blender/blenlib/intern/bpath.c b/source/blender/blenlib/intern/bpath.c
index cadf8d2bdd1..0df9d9b8db3 100644
--- a/source/blender/blenlib/intern/bpath.c
+++ b/source/blender/blenlib/intern/bpath.c
@@ -60,7 +60,7 @@
 #include "BKE_global.h"
 #include "BKE_image.h" /* so we can check the image's type */
 #include "BKE_main.h" /* so we can access G.main->*.first */
-#include "BKE_sequence.h"
+#include "BKE_sequencer.h"
 #include "BKE_text.h" /* for writing to a textblock */
 #include "BKE_utildefines.h"
 
diff --git a/source/blender/blenlib/intern/listbase.c b/source/blender/blenlib/intern/listbase.c
index b3a4722d6d9..166f4ed029e 100644
--- a/source/blender/blenlib/intern/listbase.c
+++ b/source/blender/blenlib/intern/listbase.c
@@ -343,7 +343,7 @@ int BLI_findindex(ListBase *listbase, void *vlink)
 	return -1;
 }
 
-void BLI_duplicatelist(ListBase *list1, ListBase *list2)  /* copy from 2 to 1 */
+void BLI_duplicatelist(ListBase *list1, const ListBase *list2)
 {
 	struct Link *link1, *link2;
 	
diff --git a/source/blender/blenlib/intern/math_base.c b/source/blender/blenlib/intern/math_base.c
index f3fe09c088f..3b63b033342 100644
--- a/source/blender/blenlib/intern/math_base.c
+++ b/source/blender/blenlib/intern/math_base.c
@@ -100,7 +100,7 @@ float interpf(float target, float origin, float fac)
  * the distance gets very high, 180d would be inf, but this case isn't valid */
 float shell_angle_to_dist(const float angle)
 {
-	return (angle < SMALL_NUMBER) ? 1.0f : fabsf(1.0f / cosf(angle * (M_PI/180.0f)));
+	return (angle < SMALL_NUMBER) ? 1.0f : fabsf(1.0f / cosf(angle));
 }
 
 /* used for zoom values*/
@@ -109,3 +109,63 @@ float power_of_2(float val)
 	return (float)pow(2, ceil(log(val) / log(2)));
 }
 
+
+/* WARNING: MSVC compiling hack for double_round() */
+#if (WIN32 || WIN64) && !(FREE_WINDOWS)
+
+/* from python 3.1 pymath.c */
+double copysign(double x, double y)
+{
+	/* use atan2 to distinguish -0. from 0. */
+	if (y > 0. || (y == 0. && atan2(y, -1.) > 0.)) {
+		return fabs(x);
+	} else {
+		return -fabs(x);
+	}
+}
+
+/* from python 3.1 pymath.c */
+double round(double x)
+{
+    double absx, y;
+    absx = fabs(x);
+    y = floor(absx);
+    if (absx - y >= 0.5)
+        y += 1.0;
+    return copysign(y, x);
+}
+
+#endif
+
+
+/* from python 3.1 floatobject.c
+ * ndigits must be between 0 and 21 */
+double double_round(double x, int ndigits) {
+	double pow1, pow2, y, z;
+	if (ndigits >= 0) {
+		pow1 = pow(10.0, (double)ndigits);
+		pow2 = 1.0;
+		y = (x*pow1)*pow2;
+		/* if y overflows, then rounded value is exactly x */
+		if (!finite(y))
+			return x;
+	}
+	else {
+		pow1 = pow(10.0, (double)-ndigits);
+		pow2 = 1.0; /* unused; silences a gcc compiler warning */
+		y = x / pow1;
+	}
+
+	z = round(y);
+	if (fabs(y-z) == 0.5)
+		/* halfway between two integers; use round-half-even */
+		z = 2.0*round(y/2.0);
+
+	if (ndigits >= 0)
+		z = (z / pow2) / pow1;
+	else
+		z *= pow1;
+
+	/* if computation resulted in overflow, raise OverflowError */
+	return z;
+}
diff --git a/source/blender/blenlib/intern/math_color.c b/source/blender/blenlib/intern/math_color.c
index 7ae380a1dde..6dbd9c1381f 100644
--- a/source/blender/blenlib/intern/math_color.c
+++ b/source/blender/blenlib/intern/math_color.c
@@ -208,17 +208,17 @@ void rgb_to_hsv(float r, float g, float b, float *lh, float *ls, float *lv)
 void xyz_to_rgb(float xc, float yc, float zc, float *r, float *g, float *b, int colorspace)
 {
 	switch (colorspace) { 
-	case BLI_CS_SMPTE:
+	case BLI_XYZ_SMPTE:
 		*r = (3.50570f	 * xc) + (-1.73964f	 * yc) + (-0.544011f * zc);
 		*g = (-1.06906f	 * xc) + (1.97781f	 * yc) + (0.0351720f * zc);
 		*b = (0.0563117f * xc) + (-0.196994f * yc) + (1.05005f	 * zc);
 		break;
-	case BLI_CS_REC709:
+	case BLI_XYZ_REC709_SRGB:
 		*r = (3.240476f	 * xc) + (-1.537150f * yc) + (-0.498535f * zc);
 		*g = (-0.969256f * xc) + (1.875992f  * yc) + (0.041556f  * zc);
 		*b = (0.055648f	 * xc) + (-0.204043f * yc) + (1.057311f  * zc);
 		break;
-	case BLI_CS_CIE:
+	case BLI_XYZ_CIE:
 		*r = (2.28783848734076f	* xc) + (-0.833367677835217f	* yc) + (-0.454470795871421f	* zc);
 		*g = (-0.511651380743862f * xc) + (1.42275837632178f * yc) + (0.0888930017552939f * zc);
 		*b = (0.00572040983140966f	* xc) + (-0.0159068485104036f	* yc) + (1.0101864083734f	* zc);
@@ -274,6 +274,61 @@ void cpack_to_rgb(unsigned int col, float *r, float *g, float *b)
 	*b /= 255.0f;
 }
 
+/* ********************************* color transforms ********************************* */
+
+
+void gamma_correct(float *c, float gamma)
+{
+	*c = powf((*c), gamma);
+}
+
+float rec709_to_linearrgb(float c)
+{
+	if (c < 0.081f)
+		return (c < 0.0f)? 0.0f: c * (1.0f/4.5f);
+	else
+		return powf((c + 0.099f)*(1.0f/1.099f), (1.0f/0.45f));
+}
+
+float linearrgb_to_rec709(float c)
+{
+	if (c < 0.018f)
+		return (c < 0.0f)? 0.0f: c * 4.5f;
+	else
+		return 1.099f * powf(c, 0.45f) - 0.099f;
+}
+
+float srgb_to_linearrgb(float c)
+{
+	if (c < 0.04045f)
+		return (c < 0.0f)? 0.0f: c * (1.0f/12.92f);
+	else
+		return powf((c + 0.055f)*(1.0f/1.055f), 2.4f);
+}
+
+float linearrgb_to_srgb(float c)
+{
+	if (c < 0.0031308f)
+		return (c < 0.0f)? 0.0f: c * 12.92f;
+	else
+		return  1.055f * powf(c, 1.0f/2.4f) - 0.055f;
+}
+
+void srgb_to_linearrgb_v3_v3(float *col_to, float *col_from)
+{
+	col_to[0] = srgb_to_linearrgb(col_from[0]);
+	col_to[1] = srgb_to_linearrgb(col_from[1]);
+	col_to[2] = srgb_to_linearrgb(col_from[2]);
+}
+
+void linearrgb_to_srgb_v3_v3(float *col_to, float *col_from)
+{
+	col_to[0] = linearrgb_to_srgb(col_from[0]);
+	col_to[1] = linearrgb_to_srgb(col_from[1]);
+	col_to[2] = linearrgb_to_srgb(col_from[2]);
+}
+
+
 void minmax_rgb(short c[])
 {
 	if(c[0]>255) c[0]=255;
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index 0b3ab2f0afc..3e714b384a7 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -458,6 +458,40 @@ int isect_ray_tri_v3(float p1[3], float d[3], float v0[3], float v1[3], float v2
 	return 1;
 }
 
+int isect_ray_tri_epsilon_v3(float p1[3], float d[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv, float epsilon)
+{
+	float p[3], s[3], e1[3], e2[3], q[3];
+	float a, f, u, v;
+	
+	sub_v3_v3v3(e1, v1, v0);
+	sub_v3_v3v3(e2, v2, v0);
+	
+	cross_v3_v3v3(p, d, e2);
+	a = dot_v3v3(e1, p);
+	if (a == 0.0f) return 0;
+	f = 1.0f/a;
+	
+	sub_v3_v3v3(s, p1, v0);
+	
+	cross_v3_v3v3(q, s, e1);
+
+	u = f * dot_v3v3(s, p);
+	if ((u < -epsilon)||(u > 1.0f+epsilon)) return 0;
+	
+	v = f * dot_v3v3(d, q);
+	if ((v < -epsilon)||((u + v) > 1.0f+epsilon)) return 0;
+
+	*lambda = f * dot_v3v3(e2, q);
+	if ((*lambda < 0.0f)) return 0;
+
+	if(uv) {
+		uv[0]= u;
+		uv[1]= v;
+	}
+	
+	return 1;
+}
+
 int isect_ray_tri_threshold_v3(float p1[3], float d[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv, float threshold)
 {
 	float p[3], s[3], e1[3], e2[3], q[3];
@@ -1597,3 +1631,161 @@ void tangent_from_uv(float *uv1, float *uv2, float *uv3, float *co1, float *co2,
 		negate_v3(tang);
 }
 
+/********************************************************/
+
+/* vector clouds */
+/* void vcloud_estimate_transform(int list_size, float (*pos)[3], float *weight,float (*rpos)[3], float *rweight,
+  							   float lloc[3],float rloc[3],float lrot[3][3],float lscale[3][3])
+
+input
+(
+int list_size
+4 lists as pointer to array[list_size]
+1. current pos array of 'new' positions 
+2. current weight array of 'new'weights (may be NULL pointer if you have no weights )
+3. reference rpos array of 'old' positions
+4. reference rweight array of 'old'weights (may be NULL pointer if you have no weights )
+)
+output  
+(
+float lloc[3] center of mass pos
+float rloc[3] center of mass rpos
+float lrot[3][3] rotation matrix
+float lscale[3][3] scale matrix
+pointers may be NULL if not needed
+)
+
+*/
+/* can't believe there is none in math utils */
+float _det_m3(float m2[3][3])
+{
+    float det = 0.f;
+    if (m2){
+    det= m2[0][0]* (m2[1][1]*m2[2][2] - m2[1][2]*m2[2][1])
+        -m2[1][0]* (m2[0][1]*m2[2][2] - m2[0][2]*m2[2][1])
+        +m2[2][0]* (m2[0][1]*m2[1][2] - m2[0][2]*m2[1][1]);
+    }
+    return det;
+}
+
+
+void vcloud_estimate_transform(int list_size, float (*pos)[3], float *weight,float (*rpos)[3], float *rweight,
+							float lloc[3],float rloc[3],float lrot[3][3],float lscale[3][3])
+{
+	float accu_com[3]= {0.0f,0.0f,0.0f}, accu_rcom[3]= {0.0f,0.0f,0.0f};
+	float accu_weight = 0.0f,accu_rweight = 0.0f,eps = 0.000001f;
+
+	int a;
+	/* first set up a nice default response */
+	if (lloc) zero_v3(lloc);
+	if (rloc) zero_v3(rloc);
+	if (lrot) unit_m3(lrot);
+	if (lscale) unit_m3(lscale);
+	/* do com for both clouds */
+	if (pos && rpos && (list_size > 0)) /* paranoya check */
+	{
+		/* do com for both clouds */
+		for(a=0; a<list_size; a++){
+			if (weight){
+				float v[3];
+				copy_v3_v3(v,pos[a]);
+				mul_v3_fl(v,weight[a]);
+				add_v3_v3v3(accu_com,accu_com,v);
+				accu_weight +=weight[a]; 
+			}
+			else add_v3_v3v3(accu_com,accu_com,pos[a]);
+
+			if (rweight){
+				float v[3];
+				copy_v3_v3(v,rpos[a]);
+				mul_v3_fl(v,rweight[a]);
+				add_v3_v3v3(accu_rcom,accu_rcom,v);
+				accu_rweight +=rweight[a]; 
+			}
+			else add_v3_v3v3(accu_rcom,accu_rcom,rpos[a]);
+
+		}
+		if (!weight || !rweight){
+			accu_weight = accu_rweight = list_size;
+		}
+
+		mul_v3_fl(accu_com,1.0f/accu_weight);
+		mul_v3_fl(accu_rcom,1.0f/accu_rweight);
+		if (lloc) copy_v3_v3(lloc,accu_com);
+		if (rloc) copy_v3_v3(rloc,accu_rcom);
+		if (lrot || lscale){ /* caller does not want rot nor scale, strange but legal */
+			/*so now do some reverse engeneering and see if we can split rotation from scale ->Polardecompose*/
+			/* build 'projection' matrix */
+			float m[3][3],mr[3][3],q[3][3],qi[3][3];
+			float va[3],vb[3],stunt[3];
+			float odet,ndet;
+			int i=0,imax=15;
+			zero_m3(m);
+			zero_m3(mr);
+
+			/* build 'projection' matrix */
+			for(a=0; a<list_size; a++){
+				sub_v3_v3v3(va,rpos[a],accu_rcom);
+				/* mul_v3_fl(va,bp->mass);  mass needs renormalzation here ?? */
+				sub_v3_v3v3(vb,pos[a],accu_com);
+				/* mul_v3_fl(va,rp->mass); */
+				m[0][0] += va[0] * vb[0];
+				m[0][1] += va[0] * vb[1];
+				m[0][2] += va[0] * vb[2];
+
+				m[1][0] += va[1] * vb[0];
+				m[1][1] += va[1] * vb[1];
+				m[1][2] += va[1] * vb[2];
+
+				m[2][0] += va[2] * vb[0];
+				m[2][1] += va[2] * vb[1];
+				m[2][2] += va[2] * vb[2];
+
+				/* building the referenc matrix on the fly
+				needed to scale properly later*/
+
+				mr[0][0] += va[0] * va[0];
+				mr[0][1] += va[0] * va[1];
+				mr[0][2] += va[0] * va[2];
+
+				mr[1][0] += va[1] * va[0];
+				mr[1][1] += va[1] * va[1];
+				mr[1][2] += va[1] * va[2];
+
+				mr[2][0] += va[2] * va[0];
+				mr[2][1] += va[2] * va[1];
+				mr[2][2] += va[2] * va[2];
+			}
+			copy_m3_m3(q,m);
+			stunt[0] = q[0][0]; stunt[1] = q[1][1]; stunt[2] = q[2][2];
+			/* renormalizing for numeric stability */
+			mul_m3_fl(q,1.f/len_v3(stunt)); 
+
+			/* this is pretty much Polardecompose 'inline' the algo based on Higham's thesis */
+			/* without the far case ... but seems to work here pretty neat                   */
+			odet = 0.f;
+			ndet = _det_m3(q);
+			while((odet-ndet)*(odet-ndet) > eps && i<imax){
+				invert_m3_m3(qi,q);
+				transpose_m3(qi);
+				add_m3_m3m3(q,q,qi);
+				mul_m3_fl(q,0.5f);
+				odet =ndet;
+				ndet =_det_m3(q);
+				i++;
+			}
+
+			if (i){
+				float scale[3][3];
+				float irot[3][3];
+				if(lrot) copy_m3_m3(lrot,q);
+				invert_m3_m3(irot,q);
+				invert_m3_m3(qi,mr);
+				mul_m3_m3m3(q,m,qi); 
+				mul_m3_m3m3(scale,irot,q); 
+				if(lscale) copy_m3_m3(lscale,scale);
+
+			}
+		}
+	}
+}
diff --git a/source/blender/blenlib/intern/math_matrix.c b/source/blender/blenlib/intern/math_matrix.c
index edab1cc2440..47b99bce8ab 100644
--- a/source/blender/blenlib/intern/math_matrix.c
+++ b/source/blender/blenlib/intern/math_matrix.c
@@ -338,15 +338,19 @@ void mul_m4_v4(float mat[][4], float *vec)
 	vec[3]=x*mat[0][3] + y*mat[1][3] + z*mat[2][3] + mat[3][3]*vec[3];
 }
 
-void mul_m3_v3(float mat[][3], float *vec)
+void mul_v3_m3v3(float r[3], float M[3][3], float a[3])
 {
-	float x,y;
+	r[0]= M[0][0]*a[0] + M[1][0]*a[1] + M[2][0]*a[2];
+	r[1]= M[0][1]*a[0] + M[1][1]*a[1] + M[2][1]*a[2];
+	r[2]= M[0][2]*a[0] + M[1][2]*a[1] + M[2][2]*a[2];
+}
 
-	x=vec[0]; 
-	y=vec[1];
-	vec[0]= x*mat[0][0] + y*mat[1][0] + mat[2][0]*vec[2];
-	vec[1]= x*mat[0][1] + y*mat[1][1] + mat[2][1]*vec[2];
-	vec[2]= x*mat[0][2] + y*mat[1][2] + mat[2][2]*vec[2];
+void mul_m3_v3(float M[3][3], float r[3])
+{
+	float tmp[3];
+
+	mul_v3_m3v3(tmp, M, r);
+	copy_v3_v3(r, tmp);
 }
 
 void mul_transposed_m3_v3(float mat[][3], float *vec)
diff --git a/source/blender/blenlib/intern/math_vector.c b/source/blender/blenlib/intern/math_vector.c
index 502f241c195..3188587a96c 100644
--- a/source/blender/blenlib/intern/math_vector.c
+++ b/source/blender/blenlib/intern/math_vector.c
@@ -145,6 +145,19 @@ float angle_v3v3v3(float *v1, float *v2, float *v3)
 	return angle_normalized_v3v3(vec1, vec2);
 }
 
+/* Return the shortest angle in radians between the 2 vectors */
+float angle_v3v3(float *v1, float *v2)
+{
+	float vec1[3], vec2[3];
+
+	copy_v3_v3(vec1, v1);
+	copy_v3_v3(vec2, v2);
+	normalize_v3(vec1);
+	normalize_v3(vec2);
+
+	return angle_normalized_v3v3(vec1, vec2);
+}
+
 float angle_v2v2v2(float *v1, float *v2, float *v3)
 {
 	float vec1[2], vec2[2];
@@ -164,14 +177,18 @@ float angle_v2v2v2(float *v1, float *v2, float *v3)
 /* Return the shortest angle in radians between the 2 vectors */
 float angle_v2v2(float *v1, float *v2)
 {
-	float vec1[3], vec2[3];
+	float vec1[2], vec2[2];
 
-	copy_v3_v3(vec1, v1);
-	copy_v3_v3(vec2, v2);
-	normalize_v3(vec1);
-	normalize_v3(vec2);
+	vec1[0] = v1[0];
+	vec1[1] = v1[1];
 
-	return angle_normalized_v3v3(vec1, vec2);
+	vec2[0] = v2[0];
+	vec2[1] = v2[1];
+
+	normalize_v2(vec1);
+	normalize_v2(vec2);
+
+	return angle_normalized_v2v2(vec1, vec2);
 }
 
 float angle_normalized_v3v3(float *v1, float *v2)
@@ -205,6 +222,44 @@ float angle_normalized_v2v2(float *v1, float *v2)
 		return 2.0f*(float)saasin(len_v2v2(v2, v1)/2.0f);
 }
 
+void angle_tri_v3(float angles[3], const float v1[3], const float v2[3], const float v3[3])
+{
+	float ed1[3], ed2[3], ed3[3];
+
+	sub_v3_v3v3(ed1, v3, v1);
+	sub_v3_v3v3(ed2, v1, v2);
+	sub_v3_v3v3(ed3, v2, v3);
+
+	normalize_v3(ed1);
+	normalize_v3(ed2);
+	normalize_v3(ed3);
+
+	angles[0]= M_PI - angle_normalized_v3v3(ed1, ed2);
+	angles[1]= M_PI - angle_normalized_v3v3(ed2, ed3);
+	// face_angles[2] = M_PI - angle_normalized_v3v3(ed3, ed1);
+	angles[2]= M_PI - (angles[0] + angles[1]);
+}
+
+void angle_quad_v3(float angles[4], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
+{
+	float ed1[3], ed2[3], ed3[3], ed4[3];
+
+	sub_v3_v3v3(ed1, v4, v1);
+	sub_v3_v3v3(ed2, v1, v2);
+	sub_v3_v3v3(ed3, v2, v3);
+	sub_v3_v3v3(ed4, v3, v4);
+
+	normalize_v3(ed1);
+	normalize_v3(ed2);
+	normalize_v3(ed3);
+	normalize_v3(ed4);
+
+	angles[0]= M_PI - angle_normalized_v3v3(ed1, ed2);
+	angles[1]= M_PI - angle_normalized_v3v3(ed2, ed3);
+	angles[2]= M_PI - angle_normalized_v3v3(ed3, ed4);
+	angles[3]= M_PI - angle_normalized_v3v3(ed4, ed1);
+}
+
 /********************************* Geometry **********************************/
 
 /* Project v1 on v2 */
@@ -292,20 +347,6 @@ void print_v4(char *str, float v[4])
 	printf("%s: %.3f %.3f %.3f %.3f\n", str, v[0], v[1], v[2], v[3]);
 }
 
-void normal_short_to_float_v3(float *out, short *in)
-{
-	out[0] = in[0]*(1.0f/32767.0f);
-	out[1] = in[1]*(1.0f/32767.0f);
-	out[2] = in[2]*(1.0f/32767.0f);
-}
-
-void normal_float_to_short_v3(short *out, float *in)
-{
-	out[0] = (short)(in[0]*32767.0f);
-	out[1] = (short)(in[1]*32767.0f);
-	out[2] = (short)(in[2]*32767.0f);
-}
-
 void minmax_v3_v3v3(float *min, float *max, float *vec)
 {
 	if(min[0]>vec[0]) min[0]= vec[0];
diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c
index 5cb2290ca66..86a115c64ff 100644
--- a/source/blender/blenlib/intern/math_vector_inline.c
+++ b/source/blender/blenlib/intern/math_vector_inline.c
@@ -58,6 +58,19 @@ MINLINE void copy_v3_v3(float r[3], float a[3])
 	r[2]= a[2];
 }
 
+MINLINE void swap_v2_v2(float a[2], float b[2])
+{
+	SWAP(float, a[0], b[0]);
+	SWAP(float, a[1], b[1]);
+}
+
+MINLINE void swap_v3_v3(float a[3], float b[3])
+{
+	SWAP(float, a[0], b[0]);
+	SWAP(float, a[1], b[1]);
+	SWAP(float, a[2], b[2]);
+}
+
 /********************************* Arithmetic ********************************/
 
 MINLINE void add_v2_v2(float *r, float *a)
@@ -139,6 +152,34 @@ MINLINE void mul_v3_v3(float r[3], float a[3])
 	r[2] *= a[2];
 }
 
+MINLINE void madd_v3_v3fl(float r[3], float a[3], float f)
+{
+	r[0] += a[0]*f;
+	r[1] += a[1]*f;
+	r[2] += a[2]*f;
+}
+
+MINLINE void madd_v3_v3v3(float r[3], float a[3], float b[3])
+{
+	r[0] += a[0]*b[0];
+	r[1] += a[1]*b[1];
+	r[2] += a[2]*b[2];
+}
+
+MINLINE void madd_v3_v3v3fl(float r[3], float a[3], float b[3], float f)
+{
+	r[0] = a[0] + b[0]*f;
+	r[1] = a[1] + b[1]*f;
+	r[2] = a[2] + b[2]*f;
+}
+
+MINLINE void madd_v3_v3v3v3(float r[3], float a[3], float b[3], float c[3])
+{
+	r[0] = a[0] + b[0]*c[0];
+	r[1] = a[1] + b[1]*c[1];
+	r[2] = a[2] + b[2]*c[2];
+}
+
 MINLINE void mul_v3_v3v3(float *v, float *v1, float *v2)
 {
 	v[0] = v1[0] * v2[0];
@@ -254,7 +295,6 @@ MINLINE float normalize_v3(float n[3])
 	return d;
 }
 
-
 MINLINE double normalize_dv3(double n[3])
 {
 	double d= n[0]*n[0] + n[1]*n[1] + n[2]*n[2];
@@ -262,18 +302,35 @@ MINLINE double normalize_dv3(double n[3])
 	/* a larger value causes normalize errors in a
 	   scaled down models with camera xtreme close */
 	if(d > 1.0e-35f) {
-		d= 1.0 / sqrt(d);
-		n[0] *= d;
-		n[1] *= d;
-		n[2] *= d;
-	}
-	else {
-		n[0] = n[1] = n[2] = 0.0;
+		double mul;
+
+		d= sqrt(d);
+		mul = 1.0 / d;
+
+		n[0] *= mul;
+		n[1] *= mul;
+		n[2] *= mul;
+	} else {
+		n[0] = n[1] = n[2] = 0;
 		d= 0.0;
 	}
 
 	return d;
 }
 
+MINLINE void normal_short_to_float_v3(float *out, short *in)
+{
+	out[0] = in[0]*(1.0f/32767.0f);
+	out[1] = in[1]*(1.0f/32767.0f);
+	out[2] = in[2]*(1.0f/32767.0f);
+}
+
+MINLINE void normal_float_to_short_v3(short *out, float *in)
+{
+	out[0] = (short)(in[0]*32767.0f);
+	out[1] = (short)(in[1]*32767.0f);
+	out[2] = (short)(in[2]*32767.0f);
+}
+
 #endif /* BLI_MATH_VECTOR_INLINE */
 
diff --git a/source/blender/blenlib/intern/util.c b/source/blender/blenlib/intern/path_util.c
index 39afced92bc..4f987fcd31e 100644
--- a/source/blender/blenlib/intern/util.c
+++ b/source/blender/blenlib/intern/path_util.c
@@ -1,9 +1,5 @@
-/* util.c
- *
- * various string, file, list operations.
- *
- *
- * $Id$
+/**
+ *  $Id$
  *
  * ***** BEGIN GPL LICENSE BLOCK *****
  *
@@ -29,7 +25,8 @@
  * Contributor(s): none yet.
  *
  * ***** END GPL LICENSE BLOCK *****
- * 
+ *
+ * various string, file, list operations.
  */
 
 #include <stdio.h>
@@ -45,12 +42,13 @@
 #include "DNA_listBase.h"
 #include "DNA_userdef_types.h"
 
-#include "BLI_blenlib.h"
+#include "BLI_dynamiclist.h"
+#include "BLI_fileops.h"
+#include "BLI_path_util.h"
+#include "BLI_string.h"
 #include "BLI_storage.h"
 #include "BLI_storage_types.h"
-#include "BLI_dynamiclist.h"
 
-#include "BLI_util.h"
 #include "BKE_utildefines.h"
 
 
@@ -223,7 +221,7 @@ void BLI_newname(char *name, int add)
  *	defname: the name that should be used by default if none is specified already
  *	delim: the character which acts as a delimeter between parts of the name
  */
-void BLI_uniquename(ListBase *list, void *vlink, char defname[], char delim, short name_offs, short len)
+void BLI_uniquename(ListBase *list, void *vlink, const char defname[], char delim, short name_offs, short len)
 {
 	Link *link;
 	char tempname[128];
diff --git a/source/blender/blenlib/intern/pbvh.c b/source/blender/blenlib/intern/pbvh.c
new file mode 100644
index 00000000000..9512e3b9670
--- /dev/null
+++ b/source/blender/blenlib/intern/pbvh.c
@@ -0,0 +1,1304 @@
+/**
+ * $Id$
+ *
+ * ***** 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include <float.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_meshdata_types.h"
+
+#include "BLI_math.h"
+#include "BLI_ghash.h"
+#include "BLI_pbvh.h"
+
+#include "BKE_DerivedMesh.h"
+#include "BKE_mesh.h"
+#include "BKE_utildefines.h"
+
+#include "gpu_buffers.h"
+
+#define LEAF_LIMIT 10000
+
+//#define PERFCNTRS
+
+/* Bitmap */
+typedef char* BLI_bitmap;
+
+BLI_bitmap BLI_bitmap_new(int tot)
+{
+	return MEM_callocN((tot >> 3) + 1, "BLI bitmap");
+}
+
+int BLI_bitmap_get(BLI_bitmap b, int index)
+{
+	return b[index >> 3] & (1 << (index & 7));
+}
+
+void BLI_bitmap_set(BLI_bitmap b, int index)
+{
+	b[index >> 3] |= (1 << (index & 7));
+}
+
+void BLI_bitmap_clear(BLI_bitmap b, int index)
+{
+	b[index >> 3] &= ~(1 << (index & 7));
+}
+
+/* Axis-aligned bounding box */
+typedef struct {
+	float bmin[3], bmax[3];
+} BB;
+
+/* Axis-aligned bounding box with centroid */
+typedef struct {
+	float bmin[3], bmax[3], bcentroid[3];
+} BBC;
+
+struct PBVHNode {
+	/* Opaque handle for drawing code */
+	void *draw_buffers;
+
+	int *vert_indices;
+
+	/* Voxel bounds */
+	BB vb;
+	BB orig_vb;
+
+	/* For internal nodes */
+	int children_offset;
+
+	/* Pointer into bvh prim_indices */
+	int *prim_indices;
+	int *face_vert_indices;
+
+	unsigned int totprim;
+	unsigned int uniq_verts, face_verts;
+
+	char flag;
+};
+
+struct PBVH {
+	PBVHNode *nodes;
+	int node_mem_count, totnode;
+
+	int *prim_indices;
+	int totprim;
+	int totvert;
+
+	int leaf_limit;
+
+	/* Mesh data */
+	MVert *verts;
+	MFace *faces;
+
+	/* Grid Data */
+	DMGridData **grids;
+	DMGridAdjacency *gridadj;
+	void **gridfaces;
+	int totgrid;
+	int gridsize;
+
+	/* Only used during BVH build and update,
+	   don't need to remain valid after */
+	BLI_bitmap vert_bitmap;
+
+#ifdef PERFCNTRS
+	int perf_modified;
+#endif
+};
+
+#define STACK_FIXED_DEPTH	100
+
+typedef struct PBVHStack {
+	PBVHNode *node;
+	int revisiting;
+} PBVHStack;
+
+typedef struct PBVHIter {
+	PBVH *bvh;
+	BLI_pbvh_SearchCallback scb;
+	void *search_data;
+
+	PBVHStack *stack;
+	int stacksize;
+
+	PBVHStack stackfixed[STACK_FIXED_DEPTH];
+	int stackspace;
+} PBVHIter;
+
+static void BB_reset(BB *bb)
+{
+	bb->bmin[0] = bb->bmin[1] = bb->bmin[2] = FLT_MAX;
+	bb->bmax[0] = bb->bmax[1] = bb->bmax[2] = -FLT_MAX;
+}
+
+/* Expand the bounding box to include a new coordinate */
+static void BB_expand(BB *bb, float co[3])
+{
+	int i;
+	for(i = 0; i < 3; ++i) {
+		bb->bmin[i] = MIN2(bb->bmin[i], co[i]);
+		bb->bmax[i] = MAX2(bb->bmax[i], co[i]);
+	}
+}
+
+/* Expand the bounding box to include another bounding box */
+static void BB_expand_with_bb(BB *bb, BB *bb2)
+{
+	int i;
+	for(i = 0; i < 3; ++i) {
+		bb->bmin[i] = MIN2(bb->bmin[i], bb2->bmin[i]);
+		bb->bmax[i] = MAX2(bb->bmax[i], bb2->bmax[i]);
+	}
+}
+
+/* Return 0, 1, or 2 to indicate the widest axis of the bounding box */
+static int BB_widest_axis(BB *bb)
+{
+	float dim[3];
+	int i;
+
+	for(i = 0; i < 3; ++i)
+		dim[i] = bb->bmax[i] - bb->bmin[i];
+
+	if(dim[0] > dim[1]) {
+		if(dim[0] > dim[2])
+			return 0;
+		else
+			return 2;
+	}
+	else {
+		if(dim[1] > dim[2])
+			return 1;
+		else
+			return 2;
+	}
+}
+
+static void BBC_update_centroid(BBC *bbc)
+{
+	int i;
+	for(i = 0; i < 3; ++i)
+		bbc->bcentroid[i] = (bbc->bmin[i] + bbc->bmax[i]) * 0.5f;
+}
+
+/* Not recursive */
+static void update_node_vb(PBVH *bvh, PBVHNode *node)
+{
+	BB vb;
+
+	BB_reset(&vb);
+	
+	if(node->flag & PBVH_Leaf) {
+		PBVHVertexIter vd;
+
+		BLI_pbvh_vertex_iter_begin(bvh, node, vd, PBVH_ITER_ALL) {
+			BB_expand(&vb, vd.co);
+		}
+		BLI_pbvh_vertex_iter_end;
+	}
+	else {
+		BB_expand_with_bb(&vb,
+				  &bvh->nodes[node->children_offset].vb);
+		BB_expand_with_bb(&vb,
+				  &bvh->nodes[node->children_offset + 1].vb);
+	}
+
+	node->vb= vb;
+}
+
+/* Adapted from BLI_kdopbvh.c */
+/* Returns the index of the first element on the right of the partition */
+static int partition_indices(int *prim_indices, int lo, int hi, int axis,
+			     float mid, BBC *prim_bbc)
+{
+	int i=lo, j=hi;
+	for(;;) {
+		for(; prim_bbc[prim_indices[i]].bcentroid[axis] < mid; i++);
+		for(; mid < prim_bbc[prim_indices[j]].bcentroid[axis]; j--);
+		
+		if(!(i < j))
+			return i;
+		
+		SWAP(int, prim_indices[i], prim_indices[j]);
+		i++;
+	}
+}
+
+void check_partitioning(int *prim_indices, int lo, int hi, int axis,
+			       float mid, BBC *prim_bbc, int index_of_2nd_partition)
+{
+	int i;
+	for(i = lo; i <= hi; ++i) {
+		const float c = prim_bbc[prim_indices[i]].bcentroid[axis];
+
+		if((i < index_of_2nd_partition && c > mid) ||
+		   (i > index_of_2nd_partition && c < mid)) {
+			printf("fail\n");
+		}
+	}
+}
+
+static void grow_nodes(PBVH *bvh, int totnode)
+{
+	if(totnode > bvh->node_mem_count) {
+		PBVHNode *prev = bvh->nodes;
+		bvh->node_mem_count *= 1.33;
+		if(bvh->node_mem_count < totnode)
+			bvh->node_mem_count = totnode;
+		bvh->nodes = MEM_callocN(sizeof(PBVHNode) * bvh->node_mem_count,
+					 "bvh nodes");
+		memcpy(bvh->nodes, prev, bvh->totnode * sizeof(PBVHNode));
+		MEM_freeN(prev);
+	}
+
+	bvh->totnode = totnode;
+}
+
+/* Add a vertex to the map, with a positive value for unique vertices and
+   a negative value for additional vertices */
+static int map_insert_vert(PBVH *bvh, GHash *map,
+			    unsigned int *face_verts,
+			    unsigned int *uniq_verts, int vertex)
+{
+	void *value, *key = SET_INT_IN_POINTER(vertex);
+
+	if(!BLI_ghash_haskey(map, key)) {
+		if(BLI_bitmap_get(bvh->vert_bitmap, vertex)) {
+			value = SET_INT_IN_POINTER(-(*face_verts) - 1);
+			++(*face_verts);
+		}
+		else {
+			BLI_bitmap_set(bvh->vert_bitmap, vertex);
+			value = SET_INT_IN_POINTER(*uniq_verts);
+			++(*uniq_verts);
+		}
+		
+		BLI_ghash_insert(map, key, value);
+		return GET_INT_FROM_POINTER(value);
+	}
+	else
+		return GET_INT_FROM_POINTER(BLI_ghash_lookup(map, key));
+}
+
+/* Find vertices used by the faces in this node and update the draw buffers */
+static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node)
+{
+	GHashIterator *iter;
+	GHash *map;
+	int i, j, totface;
+
+	map = BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
+	
+	node->uniq_verts = node->face_verts = 0;
+	totface= node->totprim;
+
+	node->face_vert_indices = MEM_callocN(sizeof(int) *
+					 4*totface, "bvh node face vert indices");
+
+	for(i = 0; i < totface; ++i) {
+		MFace *f = bvh->faces + node->prim_indices[i];
+		int sides = f->v4 ? 4 : 3;
+
+		for(j = 0; j < sides; ++j) {
+			node->face_vert_indices[i*4 + j]= 
+				map_insert_vert(bvh, map, &node->face_verts,
+						&node->uniq_verts, (&f->v1)[j]);
+		}
+	}
+
+	node->vert_indices = MEM_callocN(sizeof(int) *
+					 (node->uniq_verts + node->face_verts),
+					 "bvh node vert indices");
+
+	/* Build the vertex list, unique verts first */
+	for(iter = BLI_ghashIterator_new(map), i = 0;
+	    !BLI_ghashIterator_isDone(iter);
+	    BLI_ghashIterator_step(iter), ++i) {
+		void *value = BLI_ghashIterator_getValue(iter);
+		int ndx = GET_INT_FROM_POINTER(value);
+
+		if(ndx < 0)
+			ndx = -ndx + node->uniq_verts - 1;
+
+		node->vert_indices[ndx] =
+			GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(iter));
+	}
+
+	for(i = 0; i < totface*4; ++i)
+		if(node->face_vert_indices[i] < 0)
+			node->face_vert_indices[i]= -node->face_vert_indices[i] + node->uniq_verts - 1;
+
+	node->draw_buffers =
+		GPU_build_mesh_buffers(map, bvh->verts, bvh->faces,
+				  node->prim_indices,
+				  node->totprim, node->vert_indices,
+				  node->uniq_verts,
+				  node->uniq_verts + node->face_verts);
+
+	BLI_ghash_free(map, NULL, NULL);
+}
+
+static void build_grids_leaf_node(PBVH *bvh, PBVHNode *node)
+{
+	node->draw_buffers =
+		GPU_build_grid_buffers(bvh->grids, node->prim_indices,
+				node->totprim, bvh->gridsize);
+}
+
+/* Recursively build a node in the tree
+
+   vb is the voxel box around all of the primitives contained in
+   this node.
+
+   cb is the bounding box around all the centroids of the primitives
+   contained in this node
+
+   offset and start indicate a range in the array of primitive indices
+*/
+
+void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc,
+	       int offset, int count)
+{
+	int i, axis, end;
+	BB cb_backing;
+
+	/* Decide whether this is a leaf or not */
+	// XXX adapt leaf limit for grids
+	if(count <= bvh->leaf_limit) {
+		bvh->nodes[node_index].flag |= PBVH_Leaf;
+
+		bvh->nodes[node_index].prim_indices = bvh->prim_indices + offset;
+		bvh->nodes[node_index].totprim = count;
+
+		/* Still need vb for searches */
+		BB_reset(&bvh->nodes[node_index].vb);
+		for(i = offset + count - 1; i >= offset; --i) {
+			BB_expand_with_bb(&bvh->nodes[node_index].vb,
+					  (BB*)(prim_bbc +
+						bvh->prim_indices[i]));
+		}
+		
+		if(bvh->faces)
+			build_mesh_leaf_node(bvh, bvh->nodes + node_index);
+		else
+			build_grids_leaf_node(bvh, bvh->nodes + node_index);
+		bvh->nodes[node_index].orig_vb= bvh->nodes[node_index].vb;
+
+		/* Done with this subtree */
+		return;
+	}
+	else {
+		BB_reset(&bvh->nodes[node_index].vb);
+		bvh->nodes[node_index].children_offset = bvh->totnode;
+		grow_nodes(bvh, bvh->totnode + 2);
+
+		if(!cb) {
+			cb = &cb_backing;
+			BB_reset(cb);
+			for(i = offset + count - 1; i >= offset; --i)
+				BB_expand(cb, prim_bbc[bvh->prim_indices[i]].bcentroid);
+		}
+	}
+
+	axis = BB_widest_axis(cb);
+
+	for(i = offset + count - 1; i >= offset; --i) {
+		BB_expand_with_bb(&bvh->nodes[node_index].vb,
+				  (BB*)(prim_bbc + bvh->prim_indices[i]));
+	}
+
+	bvh->nodes[node_index].orig_vb= bvh->nodes[node_index].vb;
+
+	end = partition_indices(bvh->prim_indices, offset, offset + count - 1,
+				axis,
+				(cb->bmax[axis] + cb->bmin[axis]) * 0.5f,
+				prim_bbc);
+	check_partitioning(bvh->prim_indices, offset, offset + count - 1,
+			   axis,
+			   (cb->bmax[axis] + cb->bmin[axis]) * 0.5f,
+			   prim_bbc, end);
+
+	build_sub(bvh, bvh->nodes[node_index].children_offset, NULL,
+		  prim_bbc, offset, end - offset);
+	build_sub(bvh, bvh->nodes[node_index].children_offset + 1, NULL,
+		  prim_bbc, end, offset + count - end);
+}
+
+static void pbvh_build(PBVH *bvh, BB *cb, BBC *prim_bbc, int totprim)
+{
+	int i;
+
+	if(totprim != bvh->totprim) {
+		bvh->totprim = totprim;
+		if(bvh->nodes) MEM_freeN(bvh->nodes);
+		if(bvh->prim_indices) MEM_freeN(bvh->prim_indices);
+		bvh->prim_indices = MEM_callocN(sizeof(int) * totprim,
+						"bvh prim indices");
+		for(i = 0; i < totprim; ++i)
+			bvh->prim_indices[i] = i;
+		bvh->totnode = 0;
+		if(bvh->node_mem_count < 100) {
+			bvh->node_mem_count = 100;
+			bvh->nodes = MEM_callocN(sizeof(PBVHNode) *
+						 bvh->node_mem_count,
+						 "bvh initial nodes");
+		}
+	}
+
+	bvh->totnode = 1;
+	build_sub(bvh, 0, cb, prim_bbc, 0, totprim);
+}
+
+/* Do a full rebuild with on Mesh data structure */
+void BLI_pbvh_build_mesh(PBVH *bvh, MFace *faces, MVert *verts, int totface, int totvert)
+{
+	BBC *prim_bbc = NULL;
+	BB cb;
+	int i, j;
+
+	bvh->faces = faces;
+	bvh->verts = verts;
+	bvh->vert_bitmap = BLI_bitmap_new(totvert);
+	bvh->totvert = totvert;
+	bvh->leaf_limit = LEAF_LIMIT;
+
+	BB_reset(&cb);
+
+	/* For each face, store the AABB and the AABB centroid */
+	prim_bbc = MEM_mallocN(sizeof(BBC) * totface, "prim_bbc");
+
+	for(i = 0; i < totface; ++i) {
+		MFace *f = faces + i;
+		const int sides = f->v4 ? 4 : 3;
+		BBC *bbc = prim_bbc + i;
+
+		BB_reset((BB*)bbc);
+
+		for(j = 0; j < sides; ++j)
+			BB_expand((BB*)bbc, verts[(&f->v1)[j]].co);
+
+		BBC_update_centroid(bbc);
+
+		BB_expand(&cb, bbc->bcentroid);
+	}
+
+	if(totface)
+		pbvh_build(bvh, &cb, prim_bbc, totface);
+
+	MEM_freeN(prim_bbc);
+	MEM_freeN(bvh->vert_bitmap);
+}
+
+/* Do a full rebuild with on Grids data structure */
+void BLI_pbvh_build_grids(PBVH *bvh, DMGridData **grids, DMGridAdjacency *gridadj,
+	int totgrid, int gridsize, void **gridfaces)
+{
+	BBC *prim_bbc = NULL;
+	BB cb;
+	int i, j;
+
+	bvh->grids= grids;
+	bvh->gridadj= gridadj;
+	bvh->gridfaces= gridfaces;
+	bvh->totgrid= totgrid;
+	bvh->gridsize= gridsize;
+	bvh->leaf_limit = MAX2(LEAF_LIMIT/((gridsize-1)*(gridsize-1)), 1);
+
+	BB_reset(&cb);
+
+	/* For each grid, store the AABB and the AABB centroid */
+	prim_bbc = MEM_mallocN(sizeof(BBC) * totgrid, "prim_bbc");
+
+	for(i = 0; i < totgrid; ++i) {
+		DMGridData *grid= grids[i];
+		BBC *bbc = prim_bbc + i;
+
+		BB_reset((BB*)bbc);
+
+		for(j = 0; j < gridsize*gridsize; ++j)
+			BB_expand((BB*)bbc, grid[j].co);
+
+		BBC_update_centroid(bbc);
+
+		BB_expand(&cb, bbc->bcentroid);
+	}
+
+	if(totgrid)
+		pbvh_build(bvh, &cb, prim_bbc, totgrid);
+
+	MEM_freeN(prim_bbc);
+}
+
+PBVH *BLI_pbvh_new(void)
+{
+	PBVH *bvh = MEM_callocN(sizeof(PBVH), "pbvh");
+
+	return bvh;
+}
+
+void BLI_pbvh_free(PBVH *bvh)
+{
+	PBVHNode *node;
+	int i;
+
+	for(i = 0; i < bvh->totnode; ++i) {
+		node= &bvh->nodes[i];
+
+		if(node->flag & PBVH_Leaf) {
+			if(node->draw_buffers)
+				GPU_free_buffers(node->draw_buffers);
+			if(node->vert_indices)
+				MEM_freeN(node->vert_indices);
+			if(node->face_vert_indices)
+				MEM_freeN(node->face_vert_indices);
+		}
+	}
+
+	MEM_freeN(bvh->nodes);
+	MEM_freeN(bvh->prim_indices);
+	MEM_freeN(bvh);
+}
+
+static void pbvh_iter_begin(PBVHIter *iter, PBVH *bvh, BLI_pbvh_SearchCallback scb, void *search_data)
+{
+	iter->bvh= bvh;
+	iter->scb= scb;
+	iter->search_data= search_data;
+
+	iter->stack= iter->stackfixed;
+	iter->stackspace= STACK_FIXED_DEPTH;
+
+	iter->stack[0].node= bvh->nodes;
+	iter->stack[0].revisiting= 0;
+	iter->stacksize= 1;
+}
+
+static void pbvh_iter_end(PBVHIter *iter)
+{
+	if(iter->stackspace > STACK_FIXED_DEPTH)
+		MEM_freeN(iter->stack);
+}
+
+static void pbvh_stack_push(PBVHIter *iter, PBVHNode *node, int revisiting)
+{
+	if(iter->stacksize == iter->stackspace) {
+		PBVHStack *newstack;
+
+		iter->stackspace *= 2;
+		newstack= MEM_callocN(sizeof(PBVHStack)*iter->stackspace, "PBVHStack");
+		memcpy(newstack, iter->stack, sizeof(PBVHStack)*iter->stacksize);
+
+		if(iter->stackspace > STACK_FIXED_DEPTH)
+			MEM_freeN(iter->stack);
+		iter->stack= newstack;
+	}
+
+	iter->stack[iter->stacksize].node= node;
+	iter->stack[iter->stacksize].revisiting= revisiting;
+	iter->stacksize++;
+}
+
+static PBVHNode *pbvh_iter_next(PBVHIter *iter)
+{
+	PBVHNode *node;
+	int revisiting;
+	void *search_data;
+
+	/* purpose here is to traverse tree, visiting child nodes before their
+	   parents, this order is necessary for e.g. computing bounding boxes */
+
+	while(iter->stacksize) {
+		/* pop node */
+		iter->stacksize--;
+		node= iter->stack[iter->stacksize].node;
+		revisiting= iter->stack[iter->stacksize].revisiting;
+
+		/* revisiting node already checked */
+		if(revisiting)
+			return node;
+
+		/* check search callback */
+		search_data= iter->search_data;
+
+		if(iter->scb && !iter->scb(node, search_data))
+			continue; /* don't traverse, outside of search zone */
+
+		if(node->flag & PBVH_Leaf) {
+			/* immediately hit leaf node */
+			return node;
+		}
+		else {
+			/* come back later when children are done */
+			pbvh_stack_push(iter, node, 1);
+
+			/* push two child nodes on the stack */
+			pbvh_stack_push(iter, iter->bvh->nodes+node->children_offset+1, 0);
+			pbvh_stack_push(iter, iter->bvh->nodes+node->children_offset, 0);
+		}
+	}
+
+	return NULL;
+}
+
+void BLI_pbvh_search_gather(PBVH *bvh,
+	BLI_pbvh_SearchCallback scb, void *search_data,
+	PBVHNode ***r_array, int *r_tot)
+{
+	PBVHIter iter;
+	PBVHNode **array= NULL, **newarray, *node;
+	int tot= 0, space= 0;
+
+	pbvh_iter_begin(&iter, bvh, scb, search_data);
+
+	while((node=pbvh_iter_next(&iter))) {
+		if(node->flag & PBVH_Leaf) {
+			if(tot == space) {
+				/* resize array if needed */
+				space= (tot == 0)? 32: space*2;
+				newarray= MEM_callocN(sizeof(PBVHNode)*space, "PBVHNodeSearch");
+
+				if(array) {
+					memcpy(newarray, array, sizeof(PBVHNode)*tot);
+					MEM_freeN(array);
+				}
+
+				array= newarray;
+			}
+
+			array[tot]= node;
+			tot++;
+		}
+	}
+
+	pbvh_iter_end(&iter);
+
+	*r_array= array;
+	*r_tot= tot;
+}
+
+void BLI_pbvh_search_callback(PBVH *bvh,
+	BLI_pbvh_SearchCallback scb, void *search_data,
+	BLI_pbvh_HitCallback hcb, void *hit_data)
+{
+	PBVHIter iter;
+	PBVHNode *node;
+
+	pbvh_iter_begin(&iter, bvh, scb, search_data);
+
+	while((node=pbvh_iter_next(&iter)))
+		if(node->flag & PBVH_Leaf)
+			hcb(node, hit_data);
+
+	pbvh_iter_end(&iter);
+}
+
+static int update_search_cb(PBVHNode *node, void *data_v)
+{
+	int flag= GET_INT_FROM_POINTER(data_v);
+
+	if(node->flag & PBVH_Leaf)
+		return (node->flag & flag);
+	
+	return 1;
+}
+
+static void pbvh_update_normals(PBVH *bvh, PBVHNode **nodes,
+	int totnode, float (*face_nors)[3])
+{
+	float (*vnor)[3];
+	int n;
+
+	if(bvh->grids)
+		return;
+
+	/* could be per node to save some memory, but also means
+	   we have to store for each vertex which node it is in */
+	vnor= MEM_callocN(sizeof(float)*3*bvh->totvert, "bvh temp vnors");
+
+	/* subtle assumptions:
+	   - We know that for all edited vertices, the nodes with faces
+	     adjacent to these vertices have been marked with PBVH_UpdateNormals.
+		 This is true because if the vertex is inside the brush radius, the
+		 bounding box of it's adjacent faces will be as well.
+	   - However this is only true for the vertices that have actually been
+	     edited, not for all vertices in the nodes marked for update, so we
+		 can only update vertices marked with ME_VERT_PBVH_UPDATE.
+	*/
+
+	#pragma omp parallel for private(n) schedule(static)
+	for(n = 0; n < totnode; n++) {
+		PBVHNode *node= nodes[n];
+
+		if((node->flag & PBVH_UpdateNormals)) {
+			int i, j, totface, *faces;
+
+			faces= node->prim_indices;
+			totface= node->totprim;
+
+			for(i = 0; i < totface; ++i) {
+				MFace *f= bvh->faces + faces[i];
+				float fn[3];
+				unsigned int *fv = &f->v1;
+				int sides= (f->v4)? 4: 3;
+
+				if(f->v4)
+					normal_quad_v3(fn, bvh->verts[f->v1].co, bvh->verts[f->v2].co,
+								   bvh->verts[f->v3].co, bvh->verts[f->v4].co);
+				else
+					normal_tri_v3(fn, bvh->verts[f->v1].co, bvh->verts[f->v2].co,
+								  bvh->verts[f->v3].co);
+
+				for(j = 0; j < sides; ++j) {
+					int v= fv[j];
+
+					if(bvh->verts[v].flag & ME_VERT_PBVH_UPDATE) {
+						/* this seems like it could be very slow but profile
+						   does not show this, so just leave it for now? */
+						#pragma omp atomic
+						vnor[v][0] += fn[0];
+						#pragma omp atomic
+						vnor[v][1] += fn[1];
+						#pragma omp atomic
+						vnor[v][2] += fn[2];
+					}
+				}
+
+				if(face_nors)
+					copy_v3_v3(face_nors[faces[i]], fn);
+			}
+		}
+	}
+
+	#pragma omp parallel for private(n) schedule(static)
+	for(n = 0; n < totnode; n++) {
+		PBVHNode *node= nodes[n];
+
+		if(node->flag & PBVH_UpdateNormals) {
+			int i, *verts, totvert;
+
+			verts= node->vert_indices;
+			totvert= node->uniq_verts;
+
+			for(i = 0; i < totvert; ++i) {
+				const int v = verts[i];
+				MVert *mvert= &bvh->verts[v];
+
+				if(mvert->flag & ME_VERT_PBVH_UPDATE) {
+					float no[3];
+
+					copy_v3_v3(no, vnor[v]);
+					normalize_v3(no);
+					
+					mvert->no[0] = (short)(no[0]*32767.0f);
+					mvert->no[1] = (short)(no[1]*32767.0f);
+					mvert->no[2] = (short)(no[2]*32767.0f);
+					
+					mvert->flag &= ~ME_VERT_PBVH_UPDATE;
+				}
+			}
+
+			node->flag &= ~PBVH_UpdateNormals;
+		}
+	}
+
+	MEM_freeN(vnor);
+}
+
+static void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes,
+	int totnode, int flag)
+{
+	int n;
+
+	/* update BB, redraw flag */
+	#pragma omp parallel for private(n) schedule(static)
+	for(n = 0; n < totnode; n++) {
+		PBVHNode *node= nodes[n];
+
+		if((flag & PBVH_UpdateBB) && (node->flag & PBVH_UpdateBB))
+			/* don't clear flag yet, leave it for flushing later */
+			update_node_vb(bvh, node);
+
+		if((flag & PBVH_UpdateOriginalBB) && (node->flag & PBVH_UpdateOriginalBB))
+			node->orig_vb= node->vb;
+
+		if((flag & PBVH_UpdateRedraw) && (node->flag & PBVH_UpdateRedraw))
+			node->flag &= ~PBVH_UpdateRedraw;
+	}
+}
+
+static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode)
+{
+	PBVHNode *node;
+	int n;
+
+	/* can't be done in parallel with OpenGL */
+	for(n = 0; n < totnode; n++) {
+		node= nodes[n];
+
+		if(node->flag & PBVH_UpdateDrawBuffers) {
+			if(bvh->grids) {
+				GPU_update_grid_buffers(node->draw_buffers,
+						   bvh->grids,
+						   node->prim_indices,
+						   node->totprim,
+						   bvh->gridsize);
+			}
+			else {
+				GPU_update_mesh_buffers(node->draw_buffers,
+						   bvh->verts,
+						   node->vert_indices,
+						   node->uniq_verts +
+						   node->face_verts);
+			}
+
+			node->flag &= ~PBVH_UpdateDrawBuffers;
+		}
+	}
+}
+
+static int pbvh_flush_bb(PBVH *bvh, PBVHNode *node, int flag)
+{
+	int update= 0;
+
+	/* difficult to multithread well, we just do single threaded recursive */
+	if(node->flag & PBVH_Leaf) {
+		if(flag & PBVH_UpdateBB) {
+			update |= (node->flag & PBVH_UpdateBB);
+			node->flag &= ~PBVH_UpdateBB;
+		}
+
+		if(flag & PBVH_UpdateOriginalBB) {
+			update |= (node->flag & PBVH_UpdateOriginalBB);
+			node->flag &= ~PBVH_UpdateOriginalBB;
+		}
+
+		return update;
+	}
+	else {
+		update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset, flag);
+		update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset + 1, flag);
+
+		if(update & PBVH_UpdateBB)
+			update_node_vb(bvh, node);
+		if(update & PBVH_UpdateOriginalBB)
+			node->orig_vb= node->vb;
+	}
+
+	return update;
+}
+
+void BLI_pbvh_update(PBVH *bvh, int flag, float (*face_nors)[3])
+{
+	PBVHNode **nodes;
+	int totnode;
+
+	BLI_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(flag),
+		&nodes, &totnode);
+
+	if(flag & PBVH_UpdateNormals)
+		pbvh_update_normals(bvh, nodes, totnode, face_nors);
+
+	if(flag & (PBVH_UpdateBB|PBVH_UpdateOriginalBB|PBVH_UpdateRedraw))
+		pbvh_update_BB_redraw(bvh, nodes, totnode, flag);
+
+	if(flag & PBVH_UpdateDrawBuffers)
+		pbvh_update_draw_buffers(bvh, nodes, totnode);
+
+	if(flag & (PBVH_UpdateBB|PBVH_UpdateOriginalBB))
+		pbvh_flush_bb(bvh, bvh->nodes, flag);
+
+	if(nodes) MEM_freeN(nodes);
+}
+
+void BLI_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3])
+{
+	PBVHIter iter;
+	PBVHNode *node;
+	BB bb;
+
+	BB_reset(&bb);
+
+	pbvh_iter_begin(&iter, bvh, NULL, NULL);
+
+	while((node=pbvh_iter_next(&iter)))
+		if(node->flag & PBVH_UpdateRedraw)
+			BB_expand_with_bb(&bb, &node->vb);
+
+	pbvh_iter_end(&iter);
+
+	copy_v3_v3(bb_min, bb.bmin);
+	copy_v3_v3(bb_max, bb.bmax);
+}
+
+void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *totface)
+{
+	PBVHIter iter;
+	PBVHNode *node;
+	GHashIterator *hiter;
+	GHash *map;
+	void *face, **faces;
+	int i, tot;
+
+	map = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
+
+	pbvh_iter_begin(&iter, bvh, NULL, NULL);
+
+	while((node=pbvh_iter_next(&iter))) {
+		if(node->flag & PBVH_UpdateNormals) {
+			for(i = 0; i < node->totprim; ++i) {
+				face= bvh->gridfaces[node->prim_indices[i]];
+				if(!BLI_ghash_lookup(map, face))
+					BLI_ghash_insert(map, face, face);
+			}
+
+			if(clear)
+				node->flag &= ~PBVH_UpdateNormals;
+		}
+	}
+
+	pbvh_iter_end(&iter);
+	
+	tot= BLI_ghash_size(map);
+	if(tot == 0) {
+		*totface= 0;
+		*gridfaces= NULL;
+		BLI_ghash_free(map, NULL, NULL);
+		return;
+	}
+
+	faces= MEM_callocN(sizeof(void*)*tot, "PBVH Grid Faces");
+
+	for(hiter = BLI_ghashIterator_new(map), i = 0;
+	    !BLI_ghashIterator_isDone(hiter);
+	    BLI_ghashIterator_step(hiter), ++i)
+		faces[i]= BLI_ghashIterator_getKey(hiter);
+
+	BLI_ghash_free(map, NULL, NULL);
+
+	*totface= tot;
+	*gridfaces= faces;
+}
+
+/***************************** Node Access ***********************************/
+
+void BLI_pbvh_node_mark_update(PBVHNode *node)
+{
+	node->flag |= PBVH_UpdateNormals|PBVH_UpdateBB|PBVH_UpdateOriginalBB|PBVH_UpdateDrawBuffers|PBVH_UpdateRedraw;
+}
+
+void BLI_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node, int **vert_indices, MVert **verts)
+{
+	if(vert_indices) *vert_indices= node->vert_indices;
+	if(verts) *verts= bvh->verts;
+}
+
+void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node, int *uniquevert, int *totvert)
+{
+	if(bvh->grids) {
+		if(totvert) *totvert= node->totprim*bvh->gridsize*bvh->gridsize;
+		if(uniquevert) *uniquevert= *totvert;
+	}
+	else {
+		if(totvert) *totvert= node->uniq_verts + node->face_verts;
+		if(uniquevert) *uniquevert= node->uniq_verts;
+	}
+}
+
+void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node, int **grid_indices, int *totgrid, int *maxgrid, int *gridsize, DMGridData ***griddata, DMGridAdjacency **gridadj)
+{
+	if(bvh->grids) {
+		if(grid_indices) *grid_indices= node->prim_indices;
+		if(totgrid) *totgrid= node->totprim;
+		if(maxgrid) *maxgrid= bvh->totgrid;
+		if(gridsize) *gridsize= bvh->gridsize;
+		if(griddata) *griddata= bvh->grids;
+		if(gridadj) *gridadj= bvh->gridadj;
+	}
+	else {
+		if(grid_indices) *grid_indices= NULL;
+		if(totgrid) *totgrid= 0;
+		if(maxgrid) *maxgrid= 0;
+		if(gridsize) *gridsize= 0;
+		if(griddata) *griddata= NULL;
+		if(gridadj) *gridadj= NULL;
+	}
+}
+
+void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
+{
+	copy_v3_v3(bb_min, node->vb.bmin);
+	copy_v3_v3(bb_max, node->vb.bmax);
+}
+
+void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
+{
+	copy_v3_v3(bb_min, node->orig_vb.bmin);
+	copy_v3_v3(bb_max, node->orig_vb.bmax);
+}
+
+/********************************* Raycast ***********************************/
+
+typedef struct {
+	/* Ray */
+	float start[3];
+	int sign[3];
+	float inv_dir[3];
+	int original;
+} RaycastData;
+
+/* Adapted from here: http://www.gamedev.net/community/forums/topic.asp?topic_id=459973 */
+static int ray_aabb_intersect(PBVHNode *node, void *data_v)
+{
+	RaycastData *ray = data_v;
+	float bb_min[3], bb_max[3], bbox[2][3];
+	float tmin, tmax, tymin, tymax, tzmin, tzmax;
+
+	if(ray->original)
+		BLI_pbvh_node_get_original_BB(node, bb_min, bb_max);
+	else
+		BLI_pbvh_node_get_BB(node, bb_min, bb_max);
+	
+	copy_v3_v3(bbox[0], bb_min);
+	copy_v3_v3(bbox[1], bb_max);
+
+	tmin = (bbox[ray->sign[0]][0] - ray->start[0]) * ray->inv_dir[0];
+	tmax = (bbox[1-ray->sign[0]][0] - ray->start[0]) * ray->inv_dir[0];
+
+	tymin = (bbox[ray->sign[1]][1] - ray->start[1]) * ray->inv_dir[1];
+	tymax = (bbox[1-ray->sign[1]][1] - ray->start[1]) * ray->inv_dir[1];
+
+	if((tmin > tymax) || (tymin > tmax))
+		return 0;
+	if(tymin > tmin)
+		tmin = tymin;
+	if(tymax < tmax)
+		tmax = tymax;
+
+	tzmin = (bbox[ray->sign[2]][2] - ray->start[2]) * ray->inv_dir[2];
+	tzmax = (bbox[1-ray->sign[2]][2] - ray->start[2]) * ray->inv_dir[2];
+
+	if((tmin > tzmax) || (tzmin > tmax))
+		return 0;
+	
+	return 1;
+
+	/* XXX: Not sure about this? 
+	   if(tzmin > tmin)
+	   tmin = tzmin;
+	   if(tzmax < tmax)
+	   tmax = tzmax;
+	   return ((tmin < t1) && (tmax > t0));
+	*/
+
+}
+
+void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitCallback cb, void *data,
+		      float ray_start[3], float ray_normal[3], int original)
+{
+	RaycastData rcd;
+
+	copy_v3_v3(rcd.start, ray_start);
+	rcd.inv_dir[0] = 1.0f / ray_normal[0];
+	rcd.inv_dir[1] = 1.0f / ray_normal[1];
+	rcd.inv_dir[2] = 1.0f / ray_normal[2];
+	rcd.sign[0] = rcd.inv_dir[0] < 0;
+	rcd.sign[1] = rcd.inv_dir[1] < 0;
+	rcd.sign[2] = rcd.inv_dir[2] < 0;
+	rcd.original = original;
+
+	BLI_pbvh_search_callback(bvh, ray_aabb_intersect, &rcd, cb, data);
+}
+
+/* XXX: Code largely copied from bvhutils.c, could be unified */
+/* Returns 1 if a better intersection has been found */
+static int ray_face_intersection(float ray_start[3], float ray_normal[3],
+				 float *t0, float *t1, float *t2, float *t3,
+				 float *fdist)
+{
+	int hit = 0;
+
+	do
+	{	
+		float dist = FLT_MAX;
+			
+		if(!isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t1, t2,
+					 &dist, NULL, 0.1f))
+			dist = FLT_MAX;
+
+		if(dist >= 0 && dist < *fdist) {
+			hit = 1;
+			*fdist = dist;
+		}
+
+		t1 = t2;
+		t2 = t3;
+		t3 = NULL;
+
+	} while(t2);
+
+	return hit;
+}
+
+int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
+	float ray_start[3], float ray_normal[3], float *dist)
+{
+	int hit= 0;
+
+	if(bvh->faces) {
+		MVert *vert = bvh->verts;
+		int *faces= node->prim_indices;
+		int *face_verts= node->face_vert_indices;
+		int totface= node->totprim;
+		int i;
+
+		for(i = 0; i < totface; ++i) {
+			MFace *f = bvh->faces + faces[i];
+
+			if(origco) {
+				/* intersect with backuped original coordinates */
+				hit |= ray_face_intersection(ray_start, ray_normal,
+							 origco[face_verts[i*4+0]],
+							 origco[face_verts[i*4+1]],
+							 origco[face_verts[i*4+2]],
+							 f->v4? origco[face_verts[i*4+3]]: NULL,
+							 dist);
+			}
+			else {
+				/* intersect with current coordinates */
+				hit |= ray_face_intersection(ray_start, ray_normal,
+							 vert[f->v1].co,
+							 vert[f->v2].co,
+							 vert[f->v3].co,
+							 f->v4 ? vert[f->v4].co : NULL,
+							 dist);
+			}
+		}
+	}
+	else {
+		int totgrid= node->totprim;
+		int gridsize= bvh->gridsize;
+		int i, x, y;
+
+		for(i = 0; i < totgrid; ++i) {
+			DMGridData *grid= bvh->grids[node->prim_indices[i]];
+
+			for(y = 0; y < gridsize-1; ++y) {
+				for(x = 0; x < gridsize-1; ++x) {
+					if(origco) {
+						hit |= ray_face_intersection(ray_start, ray_normal,
+									 origco[y*gridsize + x],
+									 origco[y*gridsize + x+1],
+									 origco[(y+1)*gridsize + x+1],
+									 origco[(y+1)*gridsize + x],
+									 dist);
+					}
+					else {
+						hit |= ray_face_intersection(ray_start, ray_normal,
+									 grid[y*gridsize + x].co,
+									 grid[y*gridsize + x+1].co,
+									 grid[(y+1)*gridsize + x+1].co,
+									 grid[(y+1)*gridsize + x].co,
+									 dist);
+					}
+				}
+			}
+
+			if(origco)
+				origco += gridsize*gridsize;
+		}
+	}
+
+	return hit;
+}
+
+#include "BIF_gl.h"
+#include "BIF_glutil.h"
+
+void BLI_pbvh_node_draw(PBVHNode *node, void *data)
+{
+#if 0
+	/* XXX: Just some quick code to show leaf nodes in different colors */
+	float col[3]; int i;
+
+	if(0) { //is_partial) {
+		col[0] = (rand() / (float)RAND_MAX); col[1] = col[2] = 0.6;
+	}
+	else {
+		srand((long long)node);
+		for(i = 0; i < 3; ++i)
+			col[i] = (rand() / (float)RAND_MAX) * 0.3 + 0.7;
+	}
+	glMaterialfv(GL_FRONT_AND_BACK, GL_DIFFUSE, col);
+
+	glColor3f(1, 0, 0);
+#endif
+	GPU_draw_buffers(node->draw_buffers);
+}
+
+/* Adapted from:
+   http://www.gamedev.net/community/forums/topic.asp?topic_id=512123
+   Returns true if the AABB is at least partially within the frustum
+   (ok, not a real frustum), false otherwise.
+*/
+int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data)
+{
+	float (*planes)[4] = data;
+	int i, axis;
+	float vmin[3], vmax[3], bb_min[3], bb_max[3];
+
+	BLI_pbvh_node_get_BB(node, bb_min, bb_max);
+
+	for(i = 0; i < 4; ++i) { 
+		for(axis = 0; axis < 3; ++axis) {
+			if(planes[i][axis] > 0) { 
+				vmin[axis] = bb_min[axis];
+				vmax[axis] = bb_max[axis];
+			}
+			else {
+				vmin[axis] = bb_max[axis];
+				vmax[axis] = bb_min[axis];
+			}
+		}
+		
+		if(dot_v3v3(planes[i], vmin) + planes[i][3] > 0)
+			return 0;
+	} 
+
+	return 1;
+}
+
+void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3])
+{
+	BLI_pbvh_update(bvh, PBVH_UpdateNormals|PBVH_UpdateDrawBuffers, face_nors);
+
+	if(planes) {
+		BLI_pbvh_search_callback(bvh, BLI_pbvh_node_planes_contain_AABB,
+				planes, BLI_pbvh_node_draw, NULL);
+	}
+	else {
+		BLI_pbvh_search_callback(bvh, NULL, NULL, BLI_pbvh_node_draw, NULL);
+	}
+}
+
diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c
index b89adbefc79..4265ee088eb 100644
--- a/source/blender/blenlib/intern/scanfill.c
+++ b/source/blender/blenlib/intern/scanfill.c
@@ -35,12 +35,11 @@
 
 #include "MEM_guardedalloc.h"
 
-#include "BLI_blenlib.h"
-
-#include "BLI_util.h"
 #include "DNA_listBase.h"
 #include "DNA_mesh_types.h"
+
 #include "BLI_editVert.h"
+#include "BLI_listbase.h"
 #include "BLI_math.h"
 #include "BLI_scanfill.h"
 #include "BLI_callbacks.h"
diff --git a/source/blender/blenlib/intern/storage.c b/source/blender/blenlib/intern/storage.c
index dbf1f5100a6..c830e5fc2c8 100644
--- a/source/blender/blenlib/intern/storage.c
+++ b/source/blender/blenlib/intern/storage.c
@@ -87,13 +87,13 @@
 #include "MEM_guardedalloc.h"
 
 #include "DNA_listBase.h"
-#include "BLI_blenlib.h"
-#include "BLI_storage.h"
-#include "BLI_storage_types.h"
 
-#include "BLI_util.h"
+#include "BLI_listbase.h"
 #include "BLI_linklist.h"
-
+#include "BLI_path_util.h"
+#include "BLI_storage.h"
+#include "BLI_storage_types.h"
+#include "BLI_string.h"
 #include "BKE_utildefines.h"
 
 /* vars: */
diff --git a/source/blender/blenlib/intern/winstuff.c b/source/blender/blenlib/intern/winstuff.c
index 16295fc2680..107ece8ebed 100644
--- a/source/blender/blenlib/intern/winstuff.c
+++ b/source/blender/blenlib/intern/winstuff.c
@@ -39,8 +39,8 @@
 
 #include "MEM_guardedalloc.h"
 
-#include "BLI_blenlib.h"
-#include "BLI_util.h"
+#include "BLI_path_util.h"
+#include "BLI_string.h"
 #define WIN32_SKIP_HKEY_PROTECTION		// need to use HKEY
 #include "BLI_winstuff.h"