diff options
author | Lukas Tönne <lukas.toenne@gmail.com> | 2018-08-12 14:52:49 +0300 |
---|---|---|
committer | Lukas Tönne <lukas.toenne@gmail.com> | 2018-08-12 14:52:49 +0300 |
commit | dc2d841b7c50565302af2986d62ddbd29c332acd (patch) | |
tree | 324f234e56fde77fb80dfdef0c7c21f01968f71b /source/blender/blenlib | |
parent | 27b28e437d974ebbafa234205941c07aa0ab546c (diff) | |
parent | 4b6fa4d897a0bb3252b16383492b526d2cef3920 (diff) |
Merge branch 'blender2.8' into hair_guideshair_guides
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_array_utils.h | 2 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_bitmap.h | 6 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_compiler_compat.h | 6 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_hash_mm3.h | 40 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_math_vector.h | 6 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_rand.h | 3 | ||||
-rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdtree.c | 10 | ||||
-rw-r--r-- | source/blender/blenlib/intern/hash_mm3.c | 147 | ||||
-rw-r--r-- | source/blender/blenlib/intern/listbase.c | 3 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 38 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_vector.c | 21 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_vector_inline.c | 23 | ||||
-rw-r--r-- | source/blender/blenlib/intern/rand.c | 12 |
14 files changed, 298 insertions, 21 deletions
diff --git a/source/blender/blenlib/BLI_array_utils.h b/source/blender/blenlib/BLI_array_utils.h index 9a510bcfc3b..da03063b245 100644 --- a/source/blender/blenlib/BLI_array_utils.h +++ b/source/blender/blenlib/BLI_array_utils.h @@ -41,7 +41,7 @@ void _bli_array_permute( const unsigned int *index, void *arr_temp); #define BLI_array_permute(arr, arr_len, order) \ _bli_array_permute(arr, arr_len, sizeof(*(arr)), order, NULL) -#define BLI_array_permute_ex(arr, arr_len, index, arr_temp) \ +#define BLI_array_permute_ex(arr, arr_len, order, arr_temp) \ _bli_array_permute(arr, arr_len, sizeof(*(arr)), order, arr_temp) int _bli_array_findindex(const void *arr, unsigned int arr_len, size_t arr_stride, const void *p); diff --git a/source/blender/blenlib/BLI_bitmap.h b/source/blender/blenlib/BLI_bitmap.h index 82704e95fdd..03390a0dbcd 100644 --- a/source/blender/blenlib/BLI_bitmap.h +++ b/source/blender/blenlib/BLI_bitmap.h @@ -70,6 +70,12 @@ typedef unsigned int BLI_bitmap; ((_bitmap)[(_index) >> _BITMAP_POWER] & \ (1u << ((_index) & _BITMAP_MASK)))) +#define BLI_BITMAP_TEST_AND_SET_ATOMIC(_bitmap, _index) \ + (CHECK_TYPE_ANY(_bitmap, BLI_bitmap *, const BLI_bitmap *), \ + (atomic_fetch_and_or_uint32((uint32_t*)&(_bitmap)[(_index) >> _BITMAP_POWER], \ + (1u << ((_index) & _BITMAP_MASK))) & \ + (1u << ((_index) & _BITMAP_MASK)))) + #define BLI_BITMAP_TEST_BOOL(_bitmap, _index) \ (CHECK_TYPE_ANY(_bitmap, BLI_bitmap *, const BLI_bitmap *), \ (BLI_BITMAP_TEST(_bitmap, _index) != 0)) diff --git a/source/blender/blenlib/BLI_compiler_compat.h b/source/blender/blenlib/BLI_compiler_compat.h index 0726e3bb343..2b53975a106 100644 --- a/source/blender/blenlib/BLI_compiler_compat.h +++ b/source/blender/blenlib/BLI_compiler_compat.h @@ -32,11 +32,7 @@ # define alloca _alloca #endif -#if defined(__cplusplus) && ((__cplusplus >= 201103L) || defined(_MSC_VER)) -# define HAS_CPP11_FEATURES -#endif - -#if (defined(__GNUC__) || defined(__clang__)) && defined(HAS_CPP11_FEATURES) +#if (defined(__GNUC__) || defined(__clang__)) && defined(__cplusplus) extern "C++" { /* Some magic to be sure we don't have reference in the type. */ template<typename T> static inline T decltype_helper(T x) { return x; } diff --git a/source/blender/blenlib/BLI_hash_mm3.h b/source/blender/blenlib/BLI_hash_mm3.h new file mode 100644 index 00000000000..93bf963c9a4 --- /dev/null +++ b/source/blender/blenlib/BLI_hash_mm3.h @@ -0,0 +1,40 @@ +/* + * ***** 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 ***** + */ + +#ifndef __BLI_HASH_MM3_H__ +#define __BLI_HASH_MM3_H__ + +/** \file BLI_hash_mm3.h + * \ingroup bli + */ + +#include "BLI_sys_types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +uint32_t BLI_hash_mm3(const unsigned char *data, size_t len, uint32_t seed); + +#ifdef __cplusplus +} +#endif + +#endif /* __BLI_HASH_MM2A_H__ */ diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h index 20852f8fc82..0a9258f47ac 100644 --- a/source/blender/blenlib/BLI_math_vector.h +++ b/source/blender/blenlib/BLI_math_vector.h @@ -78,6 +78,9 @@ MINLINE void zero_v3_int(int r[3]); MINLINE void copy_v2_v2_int(int r[2], const int a[2]); MINLINE void copy_v3_v3_int(int r[3], const int a[3]); MINLINE void copy_v4_v4_int(int r[4], const int a[4]); +/* int <-> float */ +MINLINE void copy_v2fl_v2i(float r[2], const int a[2]); +MINLINE void round_v2i_v2fl(int r[2], const float a[2]); /* double -> float */ MINLINE void copy_v2fl_v2db(float r[2], const double a[2]); MINLINE void copy_v3fl_v3db(float r[3], const double a[3]); @@ -169,6 +172,7 @@ MINLINE double dot_v3db_v3fl(const double a[3], const float b[3]) ATTR_WARN_UNUS MINLINE float cross_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT; MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3]); +MINLINE void cross_v3_v3v3_hi_prec(float r[3], const float a[3], const float b[3]); MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3]); @@ -353,6 +357,8 @@ void range_vn_u(unsigned int *array_tar, const int size, const unsigned int star void range_vn_fl(float *array_tar, const int size, const float start, const float step); void negate_vn(float *array_tar, const int size); 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); +void mul_vn_vnvn(float *array_tar, const float *array_src_a, const float *array_src_b, const int size); void mul_vn_fl(float *array_tar, const int size, const float f); void mul_vn_vn_fl(float *array_tar, const float *array_src, const int size, const float f); void add_vn_vn(float *array_tar, const float *array_src, const int size); diff --git a/source/blender/blenlib/BLI_rand.h b/source/blender/blenlib/BLI_rand.h index 612151b7ea2..f7dea562393 100644 --- a/source/blender/blenlib/BLI_rand.h +++ b/source/blender/blenlib/BLI_rand.h @@ -64,6 +64,9 @@ void BLI_rng_shuffle_array(struct RNG *rng, void *data, unsigned int elem /** Note that skipping is as slow as generating n numbers! */ void BLI_rng_skip(struct RNG *rng, int n) ATTR_NONNULL(1); +/* fill an array with random numbers */ +void BLI_array_frand(float *ar, int count, unsigned int seed); + /** Return a pseudo-random (hash) float from an integer value */ float BLI_hash_frand(unsigned int seed) ATTR_WARN_UNUSED_RESULT; diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 61f53f938e2..9621a759f3c 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -74,6 +74,7 @@ set(SRC intern/gsqueue.c intern/hash_md5.c intern/hash_mm2a.c + intern/hash_mm3.c intern/jitter_2d.c intern/lasso_2d.c intern/list_sort_impl.h @@ -158,6 +159,7 @@ set(SRC BLI_hash.h BLI_hash_md5.h BLI_hash_mm2a.h + BLI_hash_mm3.h BLI_heap.h BLI_iterator.h BLI_jitter_2d.h 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; |