Merge branch 'hair_guides' into hair_guides_groominghair_guides_grooming

7 files changed, 239 insertions, 15 deletions

diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c
index 700000b7717..80a2957d907 100644
--- a/source/blender/blenlib/intern/BLI_kdtree.c
+++ b/source/blender/blenlib/intern/BLI_kdtree.c
@@ -774,7 +774,12 @@ int BLI_kdtree_calc_duplicates_fast(
 			if (ELEM(duplicates[index], -1, index)) {
 				p.search = index;
 				copy_v3_v3(p.search_co, tree->nodes[node_index].co);
+				int found_prev = found;
 				deduplicate_recursive(&p, tree->root);
+				if (found != found_prev) {
+					/* Prevent chains of doubles. */
+					duplicates[index] = index;
+				}
 			}
 		}
 		MEM_freeN(order);
@@ -786,7 +791,12 @@ int BLI_kdtree_calc_duplicates_fast(
 			if (ELEM(duplicates[index], -1, index)) {
 				p.search = index;
 				copy_v3_v3(p.search_co, tree->nodes[node_index].co);
+				int found_prev = found;
 				deduplicate_recursive(&p, tree->root);
+				if (found != found_prev) {
+					/* Prevent chains of doubles. */
+					duplicates[index] = index;
+				}
 			}
 		}
 	}
diff --git a/source/blender/blenlib/intern/hash_mm3.c b/source/blender/blenlib/intern/hash_mm3.c
new file mode 100644
index 00000000000..105c1f46832
--- /dev/null
+++ b/source/blender/blenlib/intern/hash_mm3.c
@@ -0,0 +1,147 @@
+/*
+ * ***** 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.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ *
+ * Copyright (C) 2018 Blender Foundation.
+ *
+ */
+
+/** \file blender/blenlib/intern/hash_mm3.c
+ *  \ingroup bli
+ *
+ *  Functions to compute Murmur3 hash key.
+ *
+ * This Code is based on alShaders/Cryptomatte/MurmurHash3.h:
+ *
+ * MurmurHash3 was written by Austin Appleby, and is placed in the public
+ * domain. The author hereby disclaims copyright to this source code.
+ *
+ */
+
+#include "BLI_compiler_compat.h"
+#include "BLI_compiler_attrs.h"
+#include "BLI_hash_mm3.h"  /* own include */
+
+#if defined(_MSC_VER)
+#  include <stdlib.h>
+#  define ROTL32(x,y) _rotl(x,y)
+#  define BIG_CONSTANT(x) (x)
+
+/* Other compilers */
+#else	/* defined(_MSC_VER) */
+static inline uint32_t rotl32(uint32_t x, int8_t r)
+{
+	return (x << r) | (x >> (32 - r));
+}
+#  define ROTL32(x,y) rotl32(x,y)
+#  define BIG_CONSTANT(x) (x##LLU)
+#endif /* !defined(_MSC_VER) */
+
+/* Block read - if your platform needs to do endian-swapping or can only
+ * handle aligned reads, do the conversion here
+ */
+
+BLI_INLINE uint32_t getblock32(const uint32_t * p, int i)
+{
+	return p[i];
+}
+
+BLI_INLINE uint64_t getblock64(const uint64_t * p, int i)
+{
+	return p[i];
+}
+
+/* Finalization mix - force all bits of a hash block to avalanche */
+
+BLI_INLINE uint32_t fmix32(uint32_t h)
+{
+	h ^= h >> 16;
+	h *= 0x85ebca6b;
+	h ^= h >> 13;
+	h *= 0xc2b2ae35;
+	h ^= h >> 16;
+
+	return h;
+}
+
+BLI_INLINE uint64_t fmix64(uint64_t k)
+{
+	k ^= k >> 33;
+	k *= BIG_CONSTANT(0xff51afd7ed558ccd);
+	k ^= k >> 33;
+	k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
+	k ^= k >> 33;
+
+	return k;
+}
+
+uint32_t BLI_hash_mm3(const unsigned char *in, size_t len, uint32_t seed)
+{
+	const uint8_t *data = (const uint8_t *)in;
+	const int nblocks = len / 4;
+
+	uint32_t h1 = seed;
+
+	const uint32_t c1 = 0xcc9e2d51;
+	const uint32_t c2 = 0x1b873593;
+
+	/* body */
+
+	const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
+
+	for (int i = -nblocks; i; i++) {
+		uint32_t k1 = getblock32(blocks, i);
+
+		k1 *= c1;
+		k1 = ROTL32(k1, 15);
+		k1 *= c2;
+
+		h1 ^= k1;
+		h1 = ROTL32(h1, 13);
+		h1 = h1 * 5 + 0xe6546b64;
+	}
+
+	/* tail */
+
+	const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
+
+	uint32_t k1 = 0;
+
+	switch (len & 3) {
+		case 3:
+			k1 ^= tail[2] << 16;
+			ATTR_FALLTHROUGH;
+		case 2:
+			k1 ^= tail[1] << 8;
+			ATTR_FALLTHROUGH;
+		case 1:
+			k1 ^= tail[0];
+			k1 *= c1;
+			k1 = ROTL32(k1, 15);
+			k1 *= c2;
+			h1 ^= k1;
+	}
+
+	/* finalization */
+
+	h1 ^= len;
+
+	h1 = fmix32(h1);
+
+	return h1;
+}
diff --git a/source/blender/blenlib/intern/listbase.c b/source/blender/blenlib/intern/listbase.c
index 568448327bd..80b8a8d041c 100644
--- a/source/blender/blenlib/intern/listbase.c
+++ b/source/blender/blenlib/intern/listbase.c
@@ -578,6 +578,9 @@ void *BLI_findstring(const ListBase *listbase, const char *id, const int offset)
 	Link *link = NULL;
 	const char *id_iter;
 
+	if (id == NULL)
+		return NULL;
+
 	for (link = listbase->first; link; link = link->next) {
 		id_iter = ((const char *)link) + offset;
 
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index dd1213bd03c..5055a29b79d 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -2763,30 +2763,38 @@ bool isect_ray_aabb_v3(
 	return true;
 }
 
-/*
- * Test a bounding box (AABB) for ray intersection
- * assumes the ray is already local to the boundbox space
+/**
+ * Test a bounding box (AABB) for ray intersection.
+ * Assumes the ray is already local to the boundbox space.
+ *
+ * \note: \a direction should be normalized if you intend to use the \a tmin or \a tmax distance results!
  */
 bool isect_ray_aabb_v3_simple(
         const float orig[3], const float dir[3],
         const float bb_min[3], const float bb_max[3],
         float *tmin, float *tmax)
 {
-	double t[7];
+	double t[6];
 	float hit_dist[2];
-	t[1] = (double)(bb_min[0] - orig[0]) / dir[0];
-	t[2] = (double)(bb_max[0] - orig[0]) / dir[0];
-	t[3] = (double)(bb_min[1] - orig[1]) / dir[1];
-	t[4] = (double)(bb_max[1] - orig[1]) / dir[1];
-	t[5] = (double)(bb_min[2] - orig[2]) / dir[2];
-	t[6] = (double)(bb_max[2] - orig[2]) / dir[2];
-	hit_dist[0] = (float)fmax(fmax(fmin(t[1], t[2]), fmin(t[3], t[4])), fmin(t[5], t[6]));
-	hit_dist[1] = (float)fmin(fmin(fmax(t[1], t[2]), fmax(t[3], t[4])), fmax(t[5], t[6]));
-	if ((hit_dist[1] < 0 || hit_dist[0] > hit_dist[1]))
+	const double invdirx = (dir[0] > 1e-35f || dir[0] < -1e-35f) ? 1.0 / (double)dir[0] : DBL_MAX;
+	const double invdiry = (dir[1] > 1e-35f || dir[1] < -1e-35f) ? 1.0 / (double)dir[1] : DBL_MAX;
+	const double invdirz = (dir[2] > 1e-35f || dir[2] < -1e-35f) ? 1.0 / (double)dir[2] : DBL_MAX;
+	t[0] = (double)(bb_min[0] - orig[0]) * invdirx;
+	t[1] = (double)(bb_max[0] - orig[0]) * invdirx;
+	t[2] = (double)(bb_min[1] - orig[1]) * invdiry;
+	t[3] = (double)(bb_max[1] - orig[1]) * invdiry;
+	t[4] = (double)(bb_min[2] - orig[2]) * invdirz;
+	t[5] = (double)(bb_max[2] - orig[2]) * invdirz;
+	hit_dist[0] = (float)fmax(fmax(fmin(t[0], t[1]), fmin(t[2], t[3])), fmin(t[4], t[5]));
+	hit_dist[1] = (float)fmin(fmin(fmax(t[0], t[1]), fmax(t[2], t[3])), fmax(t[4], t[5]));
+	if ((hit_dist[1] < 0.0f || hit_dist[0] > hit_dist[1])) {
 		return false;
+	}
 	else {
-		if (tmin) *tmin = hit_dist[0];
-		if (tmax) *tmax = hit_dist[1];
+		if (tmin)
+			*tmin = hit_dist[0];
+		if (tmax)
+			*tmax = hit_dist[1];
 		return true;
 	}
 }
diff --git a/source/blender/blenlib/intern/math_vector.c b/source/blender/blenlib/intern/math_vector.c
index d6e48fa59e7..acb4ee87f69 100644
--- a/source/blender/blenlib/intern/math_vector.c
+++ b/source/blender/blenlib/intern/math_vector.c
@@ -1096,6 +1096,27 @@ void negate_vn_vn(float *array_tar, const float *array_src, const int size)
 	}
 }
 
+void mul_vn_vn(float *array_tar, const float *array_src, const int size)
+{
+	float *tar = array_tar + (size - 1);
+	const float *src = array_src + (size - 1);
+	int i = size;
+	while (i--) {
+		*(tar--) *= *(src--);
+	}
+}
+
+void mul_vn_vnvn(float *array_tar, const float *array_src_a, const float *array_src_b, const int size)
+{
+	float *tar = array_tar + (size - 1);
+	const float *src_a = array_src_a + (size - 1);
+	const float *src_b = array_src_b + (size - 1);
+	int i = size;
+	while (i--) {
+		*(tar--) = *(src_a--) * *(src_b--);
+	}
+}
+
 void mul_vn_fl(float *array_tar, const int size, const float f)
 {
 	float *array_pt = array_tar + (size - 1);
diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c
index 4c40921edb6..c4535eacefa 100644
--- a/source/blender/blenlib/intern/math_vector_inline.c
+++ b/source/blender/blenlib/intern/math_vector_inline.c
@@ -192,6 +192,19 @@ MINLINE void copy_v4_v4_int(int r[4], const int a[4])
 	r[3] = a[3];
 }
 
+/* int <-> float */
+MINLINE void round_v2i_v2fl(int r[2], const float a[2])
+{
+	r[0] = (int)roundf(a[0]);
+	r[1] = (int)roundf(a[1]);
+}
+
+MINLINE void copy_v2fl_v2i(float r[2], const int a[2])
+{
+	r[0] = (float)a[0];
+	r[1] = (float)a[1];
+}
+
 /* double -> float */
 MINLINE void copy_v2fl_v2db(float r[2], const double a[2])
 {
@@ -753,6 +766,16 @@ MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
 	r[2] = a[0] * b[1] - a[1] * b[0];
 }
 
+/* cross product suffers from severe precision loss when vectors are
+ * nearly parallel or opposite; doing the computation in double helps a lot */
+MINLINE void cross_v3_v3v3_hi_prec(float r[3], const float a[3], const float b[3])
+{
+	BLI_assert(r != a && r != b);
+	r[0] = (float)((double)a[1] * (double)b[2] - (double)a[2] * (double)b[1]);
+	r[1] = (float)((double)a[2] * (double)b[0] - (double)a[0] * (double)b[2]);
+	r[2] = (float)((double)a[0] * (double)b[1] - (double)a[1] * (double)b[0]);
+}
+
 /* Newell's Method */
 /* excuse this fairly specific function,
  * its used for polygon normals all over the place
diff --git a/source/blender/blenlib/intern/rand.c b/source/blender/blenlib/intern/rand.c
index 9e56ce6b2cf..8613a0ea6dd 100644
--- a/source/blender/blenlib/intern/rand.c
+++ b/source/blender/blenlib/intern/rand.c
@@ -265,6 +265,18 @@ void BLI_rng_skip(RNG *rng, int n)
 
 /***/
 
+/* fill an array with random numbers */
+void BLI_array_frand(float *ar, int count, unsigned int seed)
+{
+	RNG rng;
+
+	BLI_rng_srandom(&rng, seed);
+
+	for (int i = 0; i < count; i++) {
+		ar[i] = BLI_rng_get_float(&rng);
+	}
+}
+
 float BLI_hash_frand(unsigned int seed)
 {
 	RNG rng;