Merge from trunk 16122-16307

9 files changed, 253 insertions, 37 deletions

diff --git a/source/blender/blenlib/BLI_editVert.h b/source/blender/blenlib/BLI_editVert.h
index d42663e17c7..447f6a2a485 100644
--- a/source/blender/blenlib/BLI_editVert.h
+++ b/source/blender/blenlib/BLI_editVert.h
@@ -38,6 +38,8 @@
 #include "DNA_customdata_types.h"
 #include "DNA_mesh_types.h"
 
+#include "BLO_sys_types.h" // for intptr_t support
+
 struct DerivedMesh;
 struct RetopoPaintData;
 
@@ -53,7 +55,7 @@ typedef struct EditVert
 		struct EditEdge *e;
 		struct EditFace *f;
 		void            *p;
-		long             l;
+		intptr_t         l;
 		float            fp;
 	} tmp;
 	float no[3]; /*vertex normal */
@@ -95,7 +97,7 @@ typedef struct EditEdge
 		struct EditEdge *e;
 		struct EditFace *f;
 		void            *p;
-		long             l;
+		intptr_t         l;
 		float			fp;
 	} tmp;
 	short f1, f2;	/* short, f1 is (ab)used in subdiv */
@@ -122,7 +124,7 @@ typedef struct EditFace
 		struct EditEdge *e;
 		struct EditFace *f;
 		void            *p;
-		long             l;
+		intptr_t         l;
 		float			fp;
 	} tmp;
 	float n[3], cent[3];
diff --git a/source/blender/blenlib/BLI_rand.h b/source/blender/blenlib/BLI_rand.h
index 0e534783c17..266aa347aff 100644
--- a/source/blender/blenlib/BLI_rand.h
+++ b/source/blender/blenlib/BLI_rand.h
@@ -44,6 +44,7 @@ struct RNG*	rng_new			(unsigned int seed);
 void		rng_free		(struct RNG* rng);
 
 void		rng_seed		(struct RNG* rng, unsigned int seed);
+void rng_srandom(struct RNG *rng, unsigned int seed);
 int			rng_getInt		(struct RNG* rng);
 double		rng_getDouble	(struct RNG* rng);
 float		rng_getFloat	(struct RNG* rng);
diff --git a/source/blender/blenlib/BLI_winstuff.h b/source/blender/blenlib/BLI_winstuff.h
index 11150075bac..3bb63506c95 100644
--- a/source/blender/blenlib/BLI_winstuff.h
+++ b/source/blender/blenlib/BLI_winstuff.h
@@ -61,6 +61,10 @@
 
 	// These definitions are also in arithb for simplicity
 
+#ifdef __cplusplus
+extern "C" {
+#endif
+
 #ifndef M_PI
 #define M_PI		3.14159265358979323846
 #endif
@@ -116,5 +120,9 @@ int closedir (DIR *dp);
 void get_default_root(char *root);
 int check_file_chars(char *filename);
 
+#ifdef __cplusplus
+}
+#endif
+
 #endif /* __WINSTUFF_H__ */
 
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c
index 227cb8f5e9a..e9271ca3bb5 100644
--- a/source/blender/blenlib/intern/BLI_ghash.c
+++ b/source/blender/blenlib/intern/BLI_ghash.c
@@ -34,6 +34,8 @@
 #include "MEM_guardedalloc.h"
 #include "BLI_ghash.h"
 
+#include "BLO_sys_types.h" // for intptr_t support
+
 #ifdef HAVE_CONFIG_H
 #include <config.h>
 #endif
@@ -256,11 +258,7 @@ int BLI_ghashutil_ptrcmp(void *a, void *b) {
 }
 
 unsigned int BLI_ghashutil_inthash(void *ptr) {
-#if defined(_WIN64)
-	unsigned __int64 key = (unsigned __int64)ptr;
-#else
-	unsigned long key = (unsigned long)ptr;
-#endif
+	uintptr_t key = (uintptr_t)ptr;
 
 	key += ~(key << 16);
 	key ^=  (key >>  5);
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index 9671551a7f1..989e516d161 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -46,6 +46,7 @@
 
 
 #define MAX_TREETYPE 32
+#define DEFAULT_FIND_NEAREST_HEAP_SIZE 1024
 
 typedef struct BVHNode
 {
@@ -81,7 +82,7 @@ typedef struct BVHOverlapData
 typedef struct BVHNearestData
 {
 	BVHTree *tree;
-	float	*co;
+	const float	*co;
 	BVHTree_NearestPointCallback callback;
 	void	*userdata;
 	float proj[13];			//coordinates projection over axis
@@ -119,6 +120,72 @@ static float KDOP_AXES[13][3] =
 {0, 1.0, -1.0}
 };
 
+/*
+ * Generic push and pop heap
+ */
+#define PUSH_HEAP_BODY(HEAP_TYPE,PRIORITY,heap,heap_size)	\
+{													\
+	HEAP_TYPE element = heap[heap_size-1];			\
+	int child = heap_size-1;						\
+	while(child != 0)								\
+	{												\
+		int parent = (child-1) / 2;					\
+		if(PRIORITY(element, heap[parent]))			\
+		{											\
+			heap[child] = heap[parent];				\
+			child = parent;							\
+		}											\
+		else break;									\
+	}												\
+	heap[child] = element;							\
+}
+
+#define POP_HEAP_BODY(HEAP_TYPE, PRIORITY,heap,heap_size)	\
+{													\
+	HEAP_TYPE element = heap[heap_size-1];			\
+	int parent = 0;									\
+	while(parent < (heap_size-1)/2 )				\
+	{												\
+		int child2 = (parent+1)*2;					\
+		if(PRIORITY(heap[child2-1], heap[child2]))	\
+			--child2;								\
+													\
+		if(PRIORITY(element, heap[child2]))			\
+			break;									\
+													\
+		heap[parent] = heap[child2];				\
+		parent = child2;							\
+	}												\
+	heap[parent] = element;							\
+}
+
+int ADJUST_MEMORY(void *local_memblock, void **memblock, int new_size, int *max_size, int size_per_item)
+{
+	int   new_max_size = *max_size * 2;
+	void *new_memblock = NULL;
+
+	if(new_size <= *max_size)
+		return TRUE;
+
+	if(*memblock == local_memblock)
+	{
+		new_memblock = malloc( size_per_item * new_max_size );
+		memcpy( new_memblock, *memblock, size_per_item * *max_size );
+	}
+	else
+		new_memblock = realloc(*memblock, size_per_item * new_max_size );
+
+	if(new_memblock)
+	{
+		*memblock = new_memblock;
+		*max_size = new_max_size;
+		return TRUE;
+	}
+	else
+		return FALSE;
+}
+
+
 //////////////////////////////////////////////////////////////////////////////////////////////////////
 // Introsort 
 // with permission deriven from the following Java code:
@@ -634,6 +701,18 @@ static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array,
 	BVHBuildHelper data;
 	int depth;
 
+	//Most of bvhtree code relies on 1-leaf trees having at least one branch
+	//We handle that special case here
+	if(num_leafs == 1)
+	{
+		BVHNode *root = branches_array+0;
+		refit_kdop_hull(tree, root, 0, num_leafs);
+		root->main_axis = get_largest_axis(root->bv) / 2;
+		root->totnode = 1;
+		root->children[0] = leafs_array[0];		
+		return;
+	}
+
 	branches_array--;	//Implicit trees use 1-based indexs
 	
 	build_implicit_tree_helper(tree, &data);
@@ -722,6 +801,11 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
 		return NULL;
 
 	tree = (BVHTree *)MEM_callocN(sizeof(BVHTree), "BVHTree");
+
+	//tree epsilon must be >= FLT_EPSILON
+	//so that tangent rays can still hit a bounding volume..
+	//this bug would show up when casting a ray aligned with a kdop-axis and with an edge of 2 faces
+	epsilon = MAX2(FLT_EPSILON, epsilon);
 	
 	if(tree)
 	{
@@ -1114,15 +1198,18 @@ static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *near
 }
 
 
-// TODO: use a priority queue to reduce the number of nodes looked on
-static void dfs_find_nearest(BVHNearestData *data, BVHNode *node)
+typedef struct NodeDistance
 {
-	int i;
-	float nearest[3], sdist;
+	BVHNode *node;
+	float dist;
 
-	sdist = calc_nearest_point(data, node, nearest);
-	if(sdist >= data->nearest.dist) return;
+} NodeDistance;
 
+#define NodeDistance_priority(a,b)	( (a).dist < (b).dist )
+
+// TODO: use a priority queue to reduce the number of nodes looked on
+static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node)
+{
 	if(node->totnode == 0)
 	{
 		if(data->callback)
@@ -1130,17 +1217,129 @@ static void dfs_find_nearest(BVHNearestData *data, BVHNode *node)
 		else
 		{
 			data->nearest.index	= node->index;
-			VECCOPY(data->nearest.co, nearest);
-			data->nearest.dist	= sdist;
+			data->nearest.dist	= calc_nearest_point(data, node, data->nearest.co);
 		}
 	}
 	else
 	{
-		for(i=0; i != node->totnode; i++)
-			dfs_find_nearest(data, node->children[i]);
+		//Better heuristic to pick the closest node to dive on
+		int i;
+		float nearest[3];
+
+		if(data->proj[ node->main_axis ] <= node->children[0]->bv[node->main_axis*2+1])
+		{
+
+			for(i=0; i != node->totnode; i++)
+			{
+				if( calc_nearest_point(data, node->children[i], nearest) >= data->nearest.dist) continue;
+				dfs_find_nearest_dfs(data, node->children[i]);
+			}
+		}
+		else
+		{
+			for(i=node->totnode-1; i >= 0 ; i--)
+			{
+				if( calc_nearest_point(data, node->children[i], nearest) >= data->nearest.dist) continue;
+				dfs_find_nearest_dfs(data, node->children[i]);
+			}
+		}
 	}
 }
 
+static void dfs_find_nearest_begin(BVHNearestData *data, BVHNode *node)
+{
+	float nearest[3], sdist;
+	sdist = calc_nearest_point(data, node, nearest);
+	if(sdist >= data->nearest.dist) return;
+	dfs_find_nearest_dfs(data, node);
+}
+
+
+static void NodeDistance_push_heap(NodeDistance *heap, int heap_size)
+PUSH_HEAP_BODY(NodeDistance, NodeDistance_priority, heap, heap_size)
+
+static void NodeDistance_pop_heap(NodeDistance *heap, int heap_size)
+POP_HEAP_BODY(NodeDistance, NodeDistance_priority, heap, heap_size)
+
+//NN function that uses an heap.. this functions leads to an optimal number of min-distance
+//but for normal tri-faces and BV 6-dop.. a simple dfs with local heuristics (as implemented
+//in source/blender/blenkernel/intern/shrinkwrap.c) works faster.
+//
+//It may make sense to use this function if the callback queries are very slow.. or if its impossible
+//to get a nice heuristic
+//
+//this function uses "malloc/free" instead of the MEM_* because it intends to be openmp safe
+static void bfs_find_nearest(BVHNearestData *data, BVHNode *node)
+{
+	int i;
+	NodeDistance default_heap[DEFAULT_FIND_NEAREST_HEAP_SIZE];
+	NodeDistance *heap=default_heap, current;
+	int heap_size = 0, max_heap_size = sizeof(default_heap)/sizeof(default_heap[0]);
+	float nearest[3];
+
+	int callbacks = 0, push_heaps = 0;
+
+	if(node->totnode == 0)
+	{
+		dfs_find_nearest_dfs(data, node);
+		return;
+	}
+
+	current.node = node;
+	current.dist = calc_nearest_point(data, node, nearest);
+
+	while(current.dist < data->nearest.dist)
+	{
+//		printf("%f : %f\n", current.dist, data->nearest.dist);
+		for(i=0; i< current.node->totnode; i++)
+		{
+			BVHNode *child = current.node->children[i];
+			if(child->totnode == 0)
+			{
+				callbacks++;
+				dfs_find_nearest_dfs(data, child);
+			}
+			else
+			{
+				//adjust heap size
+				if(heap_size >= max_heap_size
+				&& ADJUST_MEMORY(default_heap, (void**)&heap, heap_size+1, &max_heap_size, sizeof(heap[0])) == FALSE)
+				{
+					printf("WARNING: bvh_find_nearest got out of memory\n");
+
+					if(heap != default_heap)
+						free(heap);
+
+					return;
+				}
+
+				heap[heap_size].node = current.node->children[i];
+				heap[heap_size].dist = calc_nearest_point(data, current.node->children[i], nearest);
+
+				if(heap[heap_size].dist >= data->nearest.dist) continue;
+				heap_size++;
+
+				NodeDistance_push_heap(heap, heap_size);
+	//			PUSH_HEAP_BODY(NodeDistance, NodeDistance_priority, heap, heap_size);
+				push_heaps++;
+			}
+		}
+		
+		if(heap_size == 0) break;
+
+		current = heap[0];
+		NodeDistance_pop_heap(heap, heap_size);
+//		POP_HEAP_BODY(NodeDistance, NodeDistance_priority, heap, heap_size);
+		heap_size--;
+	}
+
+//	printf("hsize=%d, callbacks=%d, pushs=%d\n", heap_size, callbacks, push_heaps);
+
+	if(heap != default_heap)
+		free(heap);
+}
+
+
 int BLI_bvhtree_find_nearest(BVHTree *tree, const float *co, BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
 {
 	int i;
@@ -1172,7 +1371,7 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float *co, BVHTreeNearest *nea
 
 	//dfs search
 	if(root)
-		dfs_find_nearest(&data, root);
+		dfs_find_nearest_begin(&data, root);
 
 	//copy back results
 	if(nearest)
@@ -1212,7 +1411,7 @@ static float ray_nearest_hit(BVHRayCastData *data, BVHNode *node)
 			float ll = (bv[0] - data->ray.origin[i]) / data->ray_dot_axis[i];
 			float lu = (bv[1] - data->ray.origin[i]) / data->ray_dot_axis[i];
 
-			if(data->ray_dot_axis[i] > 0)
+			if(data->ray_dot_axis[i] > 0.0f)
 			{
 				if(ll > low)   low = ll;
 				if(lu < upper) upper = lu;
@@ -1252,7 +1451,7 @@ static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
 	else
 	{
 		//pick loop direction to dive into the tree (based on ray direction and split axis)
-		if(data->ray_dot_axis[ node->main_axis ] > 0)
+		if(data->ray_dot_axis[ node->main_axis ] > 0.0f)
 		{
 			for(i=0; i != node->totnode; i++)
 			{
@@ -1289,7 +1488,7 @@ int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, BVHTr
 	{
 		data.ray_dot_axis[i] = INPR( data.ray.direction, KDOP_AXES[i]);
 
-		if(fabs(data.ray_dot_axis[i]) < 1e-7)
+		if(fabs(data.ray_dot_axis[i]) < FLT_EPSILON)
 			data.ray_dot_axis[i] = 0.0;
 	}
 
diff --git a/source/blender/blenlib/intern/fileops.c b/source/blender/blenlib/intern/fileops.c
index 96de5e99f4f..2acbbbe6712 100644
--- a/source/blender/blenlib/intern/fileops.c
+++ b/source/blender/blenlib/intern/fileops.c
@@ -62,6 +62,8 @@
 #include "BKE_utildefines.h"
 #include <errno.h>
 
+#include "BLO_sys_types.h" // for intptr_t support
+
 /* implementations: */
 char *first_slash(char *string) {
 	char *ffslash, *fbslash;
@@ -72,7 +74,7 @@ char *first_slash(char *string) {
 	if (!ffslash) return fbslash;
 	else if (!fbslash) return ffslash;
 	
-	if ((long)ffslash < (long)fbslash) return ffslash;
+	if ((intptr_t)ffslash < (intptr_t)fbslash) return ffslash;
 	else return fbslash;
 }
 
@@ -85,7 +87,7 @@ char *BLI_last_slash(const char *string) {
 	if (!lfslash) return lbslash; 
 	else if (!lbslash) return lfslash;
 	
-	if ((long)lfslash < (long)lbslash) return lbslash;
+	if ((intptr_t)lfslash < (intptr_t)lbslash) return lbslash;
 	else return lfslash;
 }
 
diff --git a/source/blender/blenlib/intern/psfont.c b/source/blender/blenlib/intern/psfont.c
index 498c87cdef9..216246dcdd7 100644
--- a/source/blender/blenlib/intern/psfont.c
+++ b/source/blender/blenlib/intern/psfont.c
@@ -43,6 +43,8 @@
 #include "DNA_packedFile_types.h"
 #include "DNA_curve_types.h"
 
+#include "BLO_sys_types.h" // for intptr_t support
+
 #ifdef HAVE_CONFIG_H
 #include <config.h>
 #endif
@@ -54,7 +56,7 @@ typedef struct chardesc {
     short llx, lly;		/* bounding box */
     short urx, ury;
     short *data;		/* char data */
-    long datalen;		
+    intptr_t datalen;		
 } chardesc;
 
 typedef struct objfnt {
diff --git a/source/blender/blenlib/intern/rand.c b/source/blender/blenlib/intern/rand.c
index ccc478203fe..c484a307393 100644
--- a/source/blender/blenlib/intern/rand.c
+++ b/source/blender/blenlib/intern/rand.c
@@ -81,6 +81,16 @@ void rng_seed(RNG *rng, unsigned int seed) {
 	rng->X= (((r_uint64) seed)<<16) | LOWSEED;
 }
 
+void rng_srandom(RNG *rng, unsigned int seed) {
+	extern unsigned char hash[];	// noise.c
+	
+	rng_seed(rng, seed + hash[seed & 255]);
+	seed= rng_getInt(rng);
+	rng_seed(rng, seed + hash[seed & 255]);
+	seed= rng_getInt(rng);
+	rng_seed(rng, seed + hash[seed & 255]);
+}
+
 int rng_getInt(RNG *rng) {
 	rng->X= (MULTIPLIER*rng->X + ADDEND)&MASK;
 	return (int) (rng->X>>17);
@@ -132,13 +142,7 @@ void BLI_srand(unsigned int seed) {
 
 /* using hash table to create better seed */
 void BLI_srandom(unsigned int seed) {
-	extern unsigned char hash[];	// noise.c
-	
-	rng_seed(&theBLI_rng, seed + hash[seed & 255]);
-	seed= rng_getInt(&theBLI_rng);
-	rng_seed(&theBLI_rng, seed + hash[seed & 255]);
-	seed= rng_getInt(&theBLI_rng);
-	rng_seed(&theBLI_rng, seed + hash[seed & 255]);
+	rng_srandom(&theBLI_rng, seed);
 }
 
 int BLI_rand(void) {
diff --git a/source/blender/blenlib/intern/util.c b/source/blender/blenlib/intern/util.c
index 48ebf770e1b..a31121148e3 100644
--- a/source/blender/blenlib/intern/util.c
+++ b/source/blender/blenlib/intern/util.c
@@ -1970,7 +1970,7 @@ void BLI_timestr(double _time, char *str)
 
 int BLI_int_from_pointer(void *poin)
 {
-	long lval= (long)poin;
+	intptr_t lval= (intptr_t)poin;
 	
 	return (int)(lval>>3);
 }
@@ -1978,17 +1978,17 @@ int BLI_int_from_pointer(void *poin)
 void *BLI_pointer_from_int(int val)
 {
 	static int firsttime= 1;
-	static long basevalue= 0;
+	static intptr_t basevalue= 0;
 	
 	if(firsttime) {
 		void *poin= malloc(10000);
-		basevalue= (long)poin;
+		basevalue= (intptr_t)poin;
 		basevalue &= ~PMASK;
 		printf("base: %d pointer %p\n", basevalue, poin); /* debug */
 		firsttime= 0;
 		free(poin);
 	}
-	return (void *)(basevalue | (((long)val)<<3));
+	return (void *)(basevalue | (((intptr_t)val)<<3));
 }
 
 #else