diff options
Diffstat (limited to 'source/blender/blenlib')
30 files changed, 1010 insertions, 163 deletions
diff --git a/source/blender/blenlib/BLI_array.h b/source/blender/blenlib/BLI_array.h index d3bb3401d7e..80e865ded62 100644 --- a/source/blender/blenlib/BLI_array.h +++ b/source/blender/blenlib/BLI_array.h @@ -146,6 +146,17 @@ void _bli_array_grow_func(void **arr_p, */ #define BLI_array_fake_user(arr) ((void)_##arr##_len, (void)_##arr##_static) +/** + * Trim excess items from the array (when they exist). + */ +#define BLI_array_trim(arr) \ + { \ + if (_bli_array_totalsize_dynamic(arr) != _##arr##_len) { \ + arr = MEM_reallocN(arr, sizeof(*arr) * _##arr##_len); \ + } \ + } \ + ((void)0) + /** \} */ /* -------------------------------------------------------------------- */ diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh index a580f12851e..91dfc81ae27 100644 --- a/source/blender/blenlib/BLI_array.hh +++ b/source/blender/blenlib/BLI_array.hh @@ -278,18 +278,20 @@ class Array { } /** - * Return a reference to the last element in the array. - * This invokes undefined behavior when the array is empty. + * Return a reference to the nth last element. + * This invokes undefined behavior when the array is too short. */ - const T &last() const + const T &last(const int64_t n = 0) const { - BLI_assert(size_ > 0); - return *(data_ + size_ - 1); + BLI_assert(n >= 0); + BLI_assert(n < size_); + return *(data_ + size_ - 1 - n); } - T &last() + T &last(const int64_t n = 0) { - BLI_assert(size_ > 0); - return *(data_ + size_ - 1); + BLI_assert(n >= 0); + BLI_assert(n < size_); + return *(data_ + size_ - 1 - n); } /** diff --git a/source/blender/blenlib/BLI_bounds.hh b/source/blender/blenlib/BLI_bounds.hh new file mode 100644 index 00000000000..d20382ed500 --- /dev/null +++ b/source/blender/blenlib/BLI_bounds.hh @@ -0,0 +1,75 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#pragma once + +/** \file + * \ingroup bli + * + * Generic algorithms for finding the largest and smallest elements in a span. + */ + +#include <optional> + +#include "BLI_math_vector.hh" +#include "BLI_task.hh" + +namespace blender::bounds { + +template<typename T> struct MinMaxResult { + T min; + T max; +}; + +/** + * Find the smallest and largest values element-wise in the span. + */ +template<typename T> static std::optional<MinMaxResult<T>> min_max(Span<T> values) +{ + if (values.is_empty()) { + return std::nullopt; + } + return threading::parallel_reduce( + values.index_range(), + 1024, + MinMaxResult<T>(), + [&](IndexRange range, const MinMaxResult<T> &init) { + MinMaxResult<T> result = init; + for (const int i : range) { + math::min_max(values[i], result.min, result.max); + } + return result; + }, + [](const MinMaxResult<T> &a, const MinMaxResult<T> &b) { + return MinMaxResult<T>{math::min(a.min, b.min), math::max(a.max, b.max)}; + }); +} + +/** + * Find the smallest and largest values element-wise in the span, adding the radius to each element + * first. The template type T is expected to have an addition operator implemented with RadiusT. + */ +template<typename T, typename RadiusT> +static std::optional<MinMaxResult<T>> min_max_with_radii(Span<T> values, Span<RadiusT> radii) +{ + BLI_assert(values.size() == radii.size()); + if (values.is_empty()) { + return std::nullopt; + } + return threading::parallel_reduce( + values.index_range(), + 1024, + MinMaxResult<T>(), + [&](IndexRange range, const MinMaxResult<T> &init) { + MinMaxResult<T> result = init; + for (const int i : range) { + result.min = math::min(values[i] - radii[i], result.min); + result.max = math::max(values[i] + radii[i], result.max); + } + return result; + }, + [](const MinMaxResult<T> &a, const MinMaxResult<T> &b) { + return MinMaxResult<T>{math::min(a.min, b.min), math::max(a.max, b.max)}; + }); +} + +} // namespace blender::bounds diff --git a/source/blender/blenlib/BLI_enumerable_thread_specific.hh b/source/blender/blenlib/BLI_enumerable_thread_specific.hh index 339f02dce0f..51bf8d06cf1 100644 --- a/source/blender/blenlib/BLI_enumerable_thread_specific.hh +++ b/source/blender/blenlib/BLI_enumerable_thread_specific.hh @@ -3,7 +3,25 @@ #pragma once #ifdef WITH_TBB -# include <tbb/enumerable_thread_specific.h> + +# ifdef WITH_TBB +/* Quiet top level deprecation message, unrelated to API usage here. */ +# if defined(WIN32) && !defined(NOMINMAX) +/* TBB includes Windows.h which will define min/max macros causing issues + * when we try to use std::min and std::max later on. */ +# define NOMINMAX +# define TBB_MIN_MAX_CLEANUP +# endif +# include <tbb/enumerable_thread_specific.h> +# ifdef WIN32 +/* We cannot keep this defined, since other parts of the code deal with this on their own, leading + * to multiple define warnings unless we un-define this, however we can only undefine this if we + * were the ones that made the definition earlier. */ +# ifdef TBB_MIN_MAX_CLEANUP +# undef NOMINMAX +# endif +# endif +# endif #endif #include <atomic> diff --git a/source/blender/blenlib/BLI_hash_tables.hh b/source/blender/blenlib/BLI_hash_tables.hh index 40b20dbd84f..334634613a2 100644 --- a/source/blender/blenlib/BLI_hash_tables.hh +++ b/source/blender/blenlib/BLI_hash_tables.hh @@ -8,6 +8,7 @@ * This file contains code that can be shared between different hash table implementations. */ +#include <algorithm> #include <cmath> #include "BLI_allocator.hh" diff --git a/source/blender/blenlib/BLI_index_mask.hh b/source/blender/blenlib/BLI_index_mask.hh index 7f4e7be543b..3decd8b9441 100644 --- a/source/blender/blenlib/BLI_index_mask.hh +++ b/source/blender/blenlib/BLI_index_mask.hh @@ -209,6 +209,18 @@ class IndexMask { return indices_.is_empty(); } + bool contained_in(const IndexRange range) const + { + if (indices_.is_empty()) { + return true; + } + if (range.size() < indices_.size()) { + return false; + } + return indices_.first() >= range.first() && indices_.last() <= range.last(); + } + + IndexMask slice(int64_t start, int64_t size) const; IndexMask slice(IndexRange slice) const; /** * Create a sub-mask that is also shifted to the beginning. @@ -229,6 +241,30 @@ class IndexMask { * so that the first index in the output is zero. */ IndexMask slice_and_offset(IndexRange slice, Vector<int64_t> &r_new_indices) const; + + /** + * Get a new mask that contains all the indices that are not in the current mask. + * If necessary, the indices referenced by the new mask are inserted in #r_new_indices. + */ + IndexMask invert(const IndexRange full_range, Vector<int64_t> &r_new_indices) const; + + /** + * Get all contiguous index ranges within the mask. + */ + Vector<IndexRange> extract_ranges() const; + + /** + * Similar to #extract ranges, but works on the inverted mask. So the returned ranges are + * in-between the indices in the mask. + * + * Using this method is generally more efficient than first inverting the index mask and then + * extracting the ranges. + * + * If #r_skip_amounts is passed in, it will contain the number of indices that have been skipped + * before each range in the return value starts. + */ + Vector<IndexRange> extract_ranges_invert(const IndexRange full_range, + Vector<int64_t> *r_skip_amounts) const; }; } // namespace blender diff --git a/source/blender/blenlib/BLI_index_mask_ops.hh b/source/blender/blenlib/BLI_index_mask_ops.hh new file mode 100644 index 00000000000..48a1f27a2fa --- /dev/null +++ b/source/blender/blenlib/BLI_index_mask_ops.hh @@ -0,0 +1,60 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#pragma once + +/** \file + * \ingroup bli + * + * This is separate from `BLI_index_mask.hh` because it includes headers just `IndexMask` shouldn't + * depend on. + */ + +#include "BLI_enumerable_thread_specific.hh" +#include "BLI_index_mask.hh" +#include "BLI_task.hh" +#include "BLI_vector.hh" + +namespace blender::index_mask_ops { + +namespace detail { +IndexMask find_indices_based_on_predicate__merge( + IndexMask indices_to_check, + threading::EnumerableThreadSpecific<Vector<Vector<int64_t>>> &sub_masks, + Vector<int64_t> &r_indices); +} // namespace detail + +/** + * Evaluate the #predicate for all indices in #indices_to_check and return a mask that contains all + * indices where the predicate was true. + * + * #r_indices indices is only used if necessary. + */ +template<typename Predicate> +inline IndexMask find_indices_based_on_predicate(const IndexMask indices_to_check, + const int64_t parallel_grain_size, + Vector<int64_t> &r_indices, + const Predicate &predicate) +{ + /* Evaluate predicate in parallel. Since the size of the final mask is not known yet, many + * smaller vectors have to be filled with all indices where the predicate is true. Those smaller + * vectors are joined afterwards. */ + threading::EnumerableThreadSpecific<Vector<Vector<int64_t>>> sub_masks; + threading::parallel_for( + indices_to_check.index_range(), parallel_grain_size, [&](const IndexRange range) { + const IndexMask sub_mask = indices_to_check.slice(range); + Vector<int64_t> masked_indices; + for (const int64_t i : sub_mask) { + if (predicate(i)) { + masked_indices.append(i); + } + } + if (!masked_indices.is_empty()) { + sub_masks.local().append(std::move(masked_indices)); + } + }); + + /* This part doesn't have to be in the header. */ + return detail::find_indices_based_on_predicate__merge(indices_to_check, sub_masks, r_indices); +} + +} // namespace blender::index_mask_ops diff --git a/source/blender/blenlib/BLI_math_base.hh b/source/blender/blenlib/BLI_math_base.hh new file mode 100644 index 00000000000..6a988eda8a9 --- /dev/null +++ b/source/blender/blenlib/BLI_math_base.hh @@ -0,0 +1,104 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later + * Copyright 2022 Blender Foundation. */ + +#pragma once + +/** \file + * \ingroup bli + */ + +#include <algorithm> +#include <cmath> +#include <type_traits> + +#include "BLI_math_base_safe.h" +#include "BLI_math_vec_types.hh" +#include "BLI_utildefines.h" + +#ifdef WITH_GMP +# include "BLI_math_mpq.hh" +#endif + +namespace blender::math { + +template<typename T> inline bool is_zero(const T &a) +{ + return a == T(0); +} + +template<typename T> inline bool is_any_zero(const T &a) +{ + return is_zero(a); +} + +template<typename T> inline T abs(const T &a) +{ + return std::abs(a); +} + +template<typename T> inline T min(const T &a, const T &b) +{ + return std::min(a, b); +} + +template<typename T> inline T max(const T &a, const T &b) +{ + return std::max(a, b); +} + +template<typename T> inline T clamp(const T &a, const T &min, const T &max) +{ + return std::clamp(a, min, max); +} + +template<typename T, BLI_ENABLE_IF((is_math_float_type<T>))> inline T mod(const T &a, const T &b) +{ + return std::fmod(a, b); +} + +template<typename T, BLI_ENABLE_IF((is_math_float_type<T>))> +inline T safe_mod(const T &a, const T &b) +{ + return (b != 0) ? std::fmod(a, b) : 0; +} + +template<typename T> inline void min_max(const T &value, T &min, T &max) +{ + min = math::min(value, min); + max = math::max(value, max); +} + +template<typename T, BLI_ENABLE_IF((is_math_float_type<T>))> +inline T safe_divide(const T &a, const T &b) +{ + return (b != 0) ? a / b : T(0.0f); +} + +template<typename T, BLI_ENABLE_IF((is_math_float_type<T>))> inline T floor(const T &a) +{ + return std::floor(a); +} + +template<typename T, BLI_ENABLE_IF((is_math_float_type<T>))> inline T ceil(const T &a) +{ + return std::ceil(a); +} + +template<typename T, BLI_ENABLE_IF((is_math_float_type<T>))> inline T fract(const T &a) +{ + return a - std::floor(a); +} + +template<typename T, BLI_ENABLE_IF((is_math_float_type<T>))> +inline T interpolate(const T &a, const T &b, const T &t) +{ + return a * (1 - t) + b * t; +} + +template<typename T, BLI_ENABLE_IF((is_math_float_type<T>))> +inline T midpoint(const T &a, const T &b) +{ + return (a + b) * T(0.5); +} + +} // namespace blender::math diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index 3d2ac5688ff..4bba84f2e29 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -303,6 +303,9 @@ float dist_squared_to_projected_aabb_simple(const float projmat[4][4], const float bbmin[3], const float bbmax[3]); +/** Returns the distance between two 2D line segments. */ +float dist_seg_seg_v2(const float a1[3], const float a2[3], const float b1[3], const float b2[3]); + float closest_to_ray_v3(float r_close[3], const float p[3], const float ray_orig[3], diff --git a/source/blender/blenlib/BLI_math_vec_types.hh b/source/blender/blenlib/BLI_math_vec_types.hh index 8e897870098..389307e331d 100644 --- a/source/blender/blenlib/BLI_math_vec_types.hh +++ b/source/blender/blenlib/BLI_math_vec_types.hh @@ -14,6 +14,10 @@ #include "BLI_utildefines.h" +#ifdef WITH_GMP +# include "BLI_math_mpq.hh" +#endif + namespace blender { /* clang-format off */ @@ -60,16 +64,6 @@ template<typename T> uint64_t vector_hash(const T &vec) return result; } -template<typename T> inline bool is_any_zero(const T &a) -{ - for (int i = 0; i < T::type_length; i++) { - if (a[i] == T::base_type(0)) { - return true; - } - } - return false; -} - } // namespace math template<typename T, int Size> struct vec_base : public vec_struct_base<T, Size> { @@ -349,7 +343,9 @@ template<typename T, int Size> struct vec_base : public vec_struct_base<T, Size> friend vec_base operator/(const vec_base &a, const vec_base &b) { - BLI_assert(!math::is_any_zero(b)); + for (int i = 0; i < Size; i++) { + BLI_assert(b[i] != T(0)); + } BLI_VEC_OP_IMPL(ret, i, ret[i] = a[i] / b[i]); } @@ -361,7 +357,9 @@ template<typename T, int Size> struct vec_base : public vec_struct_base<T, Size> friend vec_base operator/(T a, const vec_base &b) { - BLI_assert(!math::is_any_zero(b)); + for (int i = 0; i < Size; i++) { + BLI_assert(b[i] != T(0)); + } BLI_VEC_OP_IMPL(ret, i, ret[i] = a / b[i]); } @@ -505,7 +503,9 @@ template<typename T, int Size> struct vec_base : public vec_struct_base<T, Size> BLI_INT_OP(T) friend vec_base operator%(const vec_base &a, const vec_base &b) { - BLI_assert(!math::is_any_zero(b)); + for (int i = 0; i < Size; i++) { + BLI_assert(b[i] != T(0)); + } BLI_VEC_OP_IMPL(ret, i, ret[i] = a[i] % b[i]); } @@ -579,4 +579,13 @@ using double2 = vec_base<double, 2>; using double3 = vec_base<double, 3>; using double4 = vec_base<double, 4>; +template<typename T> +inline constexpr bool is_math_float_type = (std::is_floating_point_v<T> +#ifdef WITH_GMP + || std::is_same_v<T, mpq_class> +#endif +); + +template<typename T> inline constexpr bool is_math_integral_type = std::is_integral_v<T>; + } // namespace blender diff --git a/source/blender/blenlib/BLI_math_vector.hh b/source/blender/blenlib/BLI_math_vector.hh index d2ef2a1c5c8..7c848eeb145 100644 --- a/source/blender/blenlib/BLI_math_vector.hh +++ b/source/blender/blenlib/BLI_math_vector.hh @@ -15,10 +15,6 @@ #include "BLI_span.hh" #include "BLI_utildefines.h" -#ifdef WITH_GMP -# include "BLI_math_mpq.hh" -#endif - namespace blender::math { #ifndef NDEBUG @@ -33,277 +29,303 @@ namespace blender::math { # define BLI_ASSERT_UNIT(v) (void)(v) #endif -#define bT typename T::base_type - -#ifdef WITH_GMP -# define BLI_ENABLE_IF_FLT_VEC(T) \ - BLI_ENABLE_IF((std::is_floating_point_v<typename T::base_type> || \ - std::is_same_v<typename T::base_type, mpq_class>)) -#else -# define BLI_ENABLE_IF_FLT_VEC(T) BLI_ENABLE_IF((std::is_floating_point_v<typename T::base_type>)) -#endif - -#define BLI_ENABLE_IF_INT_VEC(T) BLI_ENABLE_IF((std::is_integral_v<typename T::base_type>)) - -template<typename T> inline bool is_zero(const T &a) +template<typename T, int Size> inline bool is_zero(const vec_base<T, Size> &a) { - for (int i = 0; i < T::type_length; i++) { - if (a[i] != bT(0)) { + for (int i = 0; i < Size; i++) { + if (a[i] != T(0)) { return false; } } return true; } -template<typename T> inline T abs(const T &a) +template<typename T, int Size> inline bool is_any_zero(const vec_base<T, Size> &a) { - T result; - for (int i = 0; i < T::type_length; i++) { + for (int i = 0; i < Size; i++) { + if (a[i] == T(0)) { + return true; + } + } + return false; +} + +template<typename T, int Size> inline vec_base<T, Size> abs(const vec_base<T, Size> &a) +{ + vec_base<T, Size> result; + for (int i = 0; i < Size; i++) { result[i] = a[i] >= 0 ? a[i] : -a[i]; } return result; } -template<typename T> inline T min(const T &a, const T &b) +template<typename T, int Size> +inline vec_base<T, Size> min(const vec_base<T, Size> &a, const vec_base<T, Size> &b) { - T result; - for (int i = 0; i < T::type_length; i++) { + vec_base<T, Size> result; + for (int i = 0; i < Size; i++) { result[i] = a[i] < b[i] ? a[i] : b[i]; } return result; } -template<typename T> inline T max(const T &a, const T &b) +template<typename T, int Size> +inline vec_base<T, Size> max(const vec_base<T, Size> &a, const vec_base<T, Size> &b) { - T result; - for (int i = 0; i < T::type_length; i++) { + vec_base<T, Size> result; + for (int i = 0; i < Size; i++) { result[i] = a[i] > b[i] ? a[i] : b[i]; } return result; } -template<typename T> inline T clamp(const T &a, const T &min_v, const T &max_v) +template<typename T, int Size> +inline T clamp(const vec_base<T, Size> &a, + const vec_base<T, Size> &min, + const vec_base<T, Size> &max) { - T result = a; - for (int i = 0; i < T::type_length; i++) { - CLAMP(result[i], min_v[i], max_v[i]); + vec_base<T, Size> result = a; + for (int i = 0; i < Size; i++) { + std::clamp(result[i], min[i], max[i]); } return result; } -template<typename T> inline T clamp(const T &a, const bT &min_v, const bT &max_v) +template<typename T, int Size> +inline vec_base<T, Size> clamp(const vec_base<T, Size> &a, const T &min, const T &max) { - T result = a; - for (int i = 0; i < T::type_length; i++) { - CLAMP(result[i], min_v, max_v); + vec_base<T, Size> result = a; + for (int i = 0; i < Size; i++) { + std::clamp(result[i], min, max); } return result; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T mod(const T &a, const T &b) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> mod(const vec_base<T, Size> &a, const vec_base<T, Size> &b) { - T result; - for (int i = 0; i < T::type_length; i++) { + vec_base<T, Size> result; + for (int i = 0; i < Size; i++) { BLI_assert(b[i] != 0); result[i] = std::fmod(a[i], b[i]); } return result; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T mod(const T &a, bT b) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> mod(const vec_base<T, Size> &a, const T &b) { BLI_assert(b != 0); - T result; - for (int i = 0; i < T::type_length; i++) { + vec_base<T, Size> result; + for (int i = 0; i < Size; i++) { result[i] = std::fmod(a[i], b); } return result; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T safe_mod(const T &a, const T &b) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline T safe_mod(const vec_base<T, Size> &a, const vec_base<T, Size> &b) { - T result; - for (int i = 0; i < T::type_length; i++) { + vec_base<T, Size> result; + for (int i = 0; i < Size; i++) { result[i] = (b[i] != 0) ? std::fmod(a[i], b[i]) : 0; } return result; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T safe_mod(const T &a, bT b) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline T safe_mod(const vec_base<T, Size> &a, const T &b) { if (b == 0) { - return T(0.0f); + return vec_base<T, Size>(0); } - T result; - for (int i = 0; i < T::type_length; i++) { + vec_base<T, Size> result; + for (int i = 0; i < Size; i++) { result[i] = std::fmod(a[i], b); } return result; } -template<typename T> inline void min_max(const T &vector, T &min_vec, T &max_vec) +template<typename T, int Size> +inline void min_max(const vec_base<T, Size> &vector, + vec_base<T, Size> &min, + vec_base<T, Size> &max) { - min_vec = min(vector, min_vec); - max_vec = max(vector, max_vec); + min = math::min(vector, min); + max = math::max(vector, max); } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T safe_divide(const T &a, const T &b) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> safe_divide(const vec_base<T, Size> &a, const vec_base<T, Size> &b) { - T result; - for (int i = 0; i < T::type_length; i++) { + vec_base<T, Size> result; + for (int i = 0; i < Size; i++) { result[i] = (b[i] == 0) ? 0 : a[i] / b[i]; } return result; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T safe_divide(const T &a, const bT b) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> safe_divide(const vec_base<T, Size> &a, const T &b) { - return (b != 0) ? a / b : T(0.0f); + return (b != 0) ? a / b : vec_base<T, Size>(0.0f); } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T floor(const T &a) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> floor(const vec_base<T, Size> &a) { - T result; - for (int i = 0; i < T::type_length; i++) { + vec_base<T, Size> result; + for (int i = 0; i < Size; i++) { result[i] = std::floor(a[i]); } return result; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T ceil(const T &a) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> ceil(const vec_base<T, Size> &a) { - T result; - for (int i = 0; i < T::type_length; i++) { + vec_base<T, Size> result; + for (int i = 0; i < Size; i++) { result[i] = std::ceil(a[i]); } return result; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T fract(const T &a) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> fract(const vec_base<T, Size> &a) { - T result; - for (int i = 0; i < T::type_length; i++) { + vec_base<T, Size> result; + for (int i = 0; i < Size; i++) { result[i] = a[i] - std::floor(a[i]); } return result; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline bT dot(const T &a, const T &b) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline T dot(const vec_base<T, Size> &a, const vec_base<T, Size> &b) { - bT result = a[0] * b[0]; - for (int i = 1; i < T::type_length; i++) { + T result = a[0] * b[0]; + for (int i = 1; i < Size; i++) { result += a[i] * b[i]; } return result; } -template<typename T> inline bT length_manhattan(const T &a) +template<typename T, int Size> inline T length_manhattan(const vec_base<T, Size> &a) { - bT result = std::abs(a[0]); - for (int i = 1; i < T::type_length; i++) { + T result = std::abs(a[0]); + for (int i = 1; i < Size; i++) { result += std::abs(a[i]); } return result; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline bT length_squared(const T &a) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline T length_squared(const vec_base<T, Size> &a) { return dot(a, a); } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline bT length(const T &a) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline T length(const vec_base<T, Size> &a) { return std::sqrt(length_squared(a)); } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline bT distance_manhattan(const T &a, const T &b) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline T distance_manhattan(const vec_base<T, Size> &a, const vec_base<T, Size> &b) { return length_manhattan(a - b); } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline bT distance_squared(const T &a, const T &b) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline T distance_squared(const vec_base<T, Size> &a, const vec_base<T, Size> &b) { return length_squared(a - b); } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline bT distance(const T &a, const T &b) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline T distance(const vec_base<T, Size> &a, const vec_base<T, Size> &b) { return length(a - b); } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T reflect(const T &incident, const T &normal) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> reflect(const vec_base<T, Size> &incident, + const vec_base<T, Size> &normal) { BLI_ASSERT_UNIT(normal); return incident - 2.0 * dot(normal, incident) * normal; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> -inline T refract(const T &incident, const T &normal, const bT eta) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> refract(const vec_base<T, Size> &incident, + const vec_base<T, Size> &normal, + const T &eta) { float dot_ni = dot(normal, incident); float k = 1.0f - eta * eta * (1.0f - dot_ni * dot_ni); if (k < 0.0f) { - return T(0.0f); + return vec_base<T, Size>(0.0f); } return eta * incident - (eta * dot_ni + sqrt(k)) * normal; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T project(const T &p, const T &v_proj) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> project(const vec_base<T, Size> &p, const vec_base<T, Size> &v_proj) { if (UNLIKELY(is_zero(v_proj))) { - return T(0.0f); + return vec_base<T, Size>(0.0f); } return v_proj * (dot(p, v_proj) / dot(v_proj, v_proj)); } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> -inline T normalize_and_get_length(const T &v, bT &out_length) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> normalize_and_get_length(const vec_base<T, Size> &v, T &out_length) { out_length = length_squared(v); /* A larger value causes normalize errors in a scaled down models with camera extreme close. */ - constexpr bT threshold = std::is_same_v<bT, double> ? 1.0e-70 : 1.0e-35f; + constexpr T threshold = std::is_same_v<T, double> ? 1.0e-70 : 1.0e-35f; if (out_length > threshold) { out_length = sqrt(out_length); return v / out_length; } /* Either the vector is small or one of it's values contained `nan`. */ out_length = 0.0; - return T(0.0); + return vec_base<T, Size>(0.0); } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T normalize(const T &v) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> normalize(const vec_base<T, Size> &v) { - bT len; + T len; return normalize_and_get_length(v, len); } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T), BLI_ENABLE_IF((T::type_length == 3))> -inline T cross(const T &a, const T &b) +template<typename T, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, 3> cross(const vec_base<T, 3> &a, const vec_base<T, 3> &b) { return {a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x}; } -template<typename T, - BLI_ENABLE_IF((std::is_same_v<bT, float>)), - BLI_ENABLE_IF((T::type_length == 3))> -inline T cross_high_precision(const T &a, const T &b) +inline vec_base<float, 3> cross_high_precision(const vec_base<float, 3> &a, + const vec_base<float, 3> &b) { return {(float)((double)a.y * b.z - (double)a.z * b.y), (float)((double)a.z * b.x - (double)a.x * b.z), (float)((double)a.x * b.y - (double)a.y * b.x)}; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T), BLI_ENABLE_IF((T::type_length == 3))> -inline T cross_poly(Span<T> poly) +template<typename T, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, 3> cross_poly(Span<vec_base<T, 3>> poly) { /* Newell's Method. */ int nv = static_cast<int>(poly.size()); if (nv < 3) { - return T(0, 0, 0); + return vec_base<T, 3>(0, 0, 0); } - const T *v_prev = &poly[nv - 1]; - const T *v_curr = &poly[0]; - T n(0, 0, 0); + const vec_base<T, 3> *v_prev = &poly[nv - 1]; + const vec_base<T, 3> *v_curr = &poly[0]; + vec_base<T, 3> n(0, 0, 0); for (int i = 0; i < nv;) { n[0] = n[0] + ((*v_prev)[1] - (*v_curr)[1]) * ((*v_prev)[2] + (*v_curr)[2]); n[1] = n[1] + ((*v_prev)[2] - (*v_curr)[2]) * ((*v_prev)[0] + (*v_curr)[0]); @@ -317,25 +339,31 @@ inline T cross_poly(Span<T> poly) return n; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T interpolate(const T &a, const T &b, bT t) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> interpolate(const vec_base<T, Size> &a, + const vec_base<T, Size> &b, + const T &t) { return a * (1 - t) + b * t; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> inline T midpoint(const T &a, const T &b) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> midpoint(const vec_base<T, Size> &a, const vec_base<T, Size> &b) { return (a + b) * 0.5; } -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> -inline T faceforward(const T &vector, const T &incident, const T &reference) +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +inline vec_base<T, Size> faceforward(const vec_base<T, Size> &vector, + const vec_base<T, Size> &incident, + const vec_base<T, Size> &reference) { return (dot(reference, incident) < 0) ? vector : -vector; } -template<typename T> inline int dominant_axis(const T &a) +template<typename T> inline int dominant_axis(const vec_base<T, 3> &a) { - T b = abs(a); + vec_base<T, 3> b = abs(a); return ((b.x > b.y) ? ((b.x > b.z) ? 0 : 2) : ((b.y > b.z) ? 1 : 2)); } @@ -348,14 +376,13 @@ template<typename T> struct isect_result { LINE_LINE_EXACT = 1, LINE_LINE_CROSS = 2, } kind; - bT lambda; + typename T::base_type lambda; }; -template<typename T, BLI_ENABLE_IF_FLT_VEC(T)> -isect_result<T> isect_seg_seg(const T &v1, const T &v2, const T &v3, const T &v4); - -#undef BLI_ENABLE_IF_FLT_VEC -#undef BLI_ENABLE_IF_INT_VEC -#undef bT +template<typename T, int Size, BLI_ENABLE_IF((is_math_float_type<T>))> +isect_result<vec_base<T, Size>> isect_seg_seg(const vec_base<T, Size> &v1, + const vec_base<T, Size> &v2, + const vec_base<T, Size> &v3, + const vec_base<T, Size> &v4); } // namespace blender::math diff --git a/source/blender/blenlib/BLI_memory_utils.hh b/source/blender/blenlib/BLI_memory_utils.hh index dd6b8463d84..a7cad5461b4 100644 --- a/source/blender/blenlib/BLI_memory_utils.hh +++ b/source/blender/blenlib/BLI_memory_utils.hh @@ -544,3 +544,31 @@ Container &move_assign_container(Container &dst, Container &&src) noexcept( } } // namespace blender + +namespace blender::detail { + +template<typename Func> struct ScopedDeferHelper { + Func func; + + ~ScopedDeferHelper() + { + func(); + } +}; + +} // namespace blender::detail + +#define BLI_SCOPED_DEFER_NAME1(a, b) a##b +#define BLI_SCOPED_DEFER_NAME2(a, b) BLI_SCOPED_DEFER_NAME1(a, b) +#define BLI_SCOPED_DEFER_NAME(a) BLI_SCOPED_DEFER_NAME2(_scoped_defer_##a##_, __LINE__) + +/** + * Execute the given function when the current scope ends. This can be used to cheaply implement + * some RAII-like behavior for C types that don't support it. Long term, the types we want to use + * this with should either be converted to C++ or get a proper C++ API. Until then, this function + * can help avoid common resource leakages. + */ +#define BLI_SCOPED_DEFER(function_to_defer) \ + auto BLI_SCOPED_DEFER_NAME(func) = (function_to_defer); \ + blender::detail::ScopedDeferHelper<decltype(BLI_SCOPED_DEFER_NAME(func))> \ + BLI_SCOPED_DEFER_NAME(helper){std::move(BLI_SCOPED_DEFER_NAME(func))}; diff --git a/source/blender/blenlib/BLI_path_util.h b/source/blender/blenlib/BLI_path_util.h index b4427b1dc2a..7b3e3e983f0 100644 --- a/source/blender/blenlib/BLI_path_util.h +++ b/source/blender/blenlib/BLI_path_util.h @@ -298,7 +298,7 @@ bool BLI_path_parent_dir_until_exists(char *path) ATTR_NONNULL(); bool BLI_path_abs(char *path, const char *basepath) ATTR_NONNULL(); /** * Replaces "#" character sequence in last slash-separated component of `path` - * with frame as decimal integer, with leading zeroes as necessary, to make digits digits. + * with frame as decimal integer, with leading zeroes as necessary, to make digits. */ bool BLI_path_frame(char *path, int frame, int digits) ATTR_NONNULL(); /** diff --git a/source/blender/blenlib/BLI_span.hh b/source/blender/blenlib/BLI_span.hh index d82f21a57ff..9ab096094de 100644 --- a/source/blender/blenlib/BLI_span.hh +++ b/source/blender/blenlib/BLI_span.hh @@ -307,13 +307,14 @@ template<typename T> class Span { } /** - * Returns a reference to the last element in the array. This invokes undefined behavior when the - * array is empty. + * Returns a reference to the nth last element. This invokes undefined behavior when the span is + * too short. */ - constexpr const T &last() const + constexpr const T &last(const int64_t n = 0) const { - BLI_assert(size_ > 0); - return data_[size_ - 1]; + BLI_assert(n >= 0); + BLI_assert(n < size_); + return data_[size_ - 1 - n]; } /** @@ -673,13 +674,14 @@ template<typename T> class MutableSpan { } /** - * Returns a reference to the last element. This invokes undefined behavior when the array is - * empty. + * Returns a reference to the nth last element. This invokes undefined behavior when the span is + * too short. */ - constexpr T &last() const + constexpr T &last(const int64_t n = 0) const { - BLI_assert(size_ > 0); - return data_[size_ - 1]; + BLI_assert(n >= 0); + BLI_assert(n < size_); + return data_[size_ - 1 - n]; } /** diff --git a/source/blender/blenlib/BLI_vector.hh b/source/blender/blenlib/BLI_vector.hh index d5d33b8a000..da9ab9c313e 100644 --- a/source/blender/blenlib/BLI_vector.hh +++ b/source/blender/blenlib/BLI_vector.hh @@ -639,18 +639,20 @@ class Vector { } /** - * Return a reference to the last element in the vector. - * This invokes undefined behavior when the vector is empty. + * Return a reference to the nth last element. + * This invokes undefined behavior when the vector is too short. */ - const T &last() const + const T &last(const int64_t n = 0) const { - BLI_assert(this->size() > 0); - return *(end_ - 1); + BLI_assert(n >= 0); + BLI_assert(n < this->size()); + return *(end_ - 1 - n); } - T &last() + T &last(const int64_t n = 0) { - BLI_assert(this->size() > 0); - return *(end_ - 1); + BLI_assert(n >= 0); + BLI_assert(n < this->size()); + return *(end_ - 1 - n); } /** diff --git a/source/blender/blenlib/BLI_virtual_array.hh b/source/blender/blenlib/BLI_virtual_array.hh index d697590b946..16fd706c99d 100644 --- a/source/blender/blenlib/BLI_virtual_array.hh +++ b/source/blender/blenlib/BLI_virtual_array.hh @@ -667,7 +667,7 @@ template<typename T> class VArrayCommon { } /** - * Returns the internally used span of the virtual array. This invokes undefined behavior is the + * Returns the internally used span of the virtual array. This invokes undefined behavior if the * virtual array is not stored as a span internally. */ Span<T> get_internal_span() const diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 29015084679..6e3e84f6495 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -162,6 +162,7 @@ set(SRC BLI_bitmap_draw_2d.h BLI_blenlib.h BLI_boxpack_2d.h + BLI_bounds.hh BLI_buffer.h BLI_color.hh BLI_compiler_attrs.h @@ -202,6 +203,7 @@ set(SRC BLI_heap.h BLI_heap_simple.h BLI_index_mask.hh + BLI_index_mask_ops.hh BLI_index_range.hh BLI_inplace_priority_queue.hh BLI_iterator.h @@ -220,6 +222,7 @@ set(SRC BLI_map.hh BLI_map_slots.hh BLI_math.h + BLI_math_base.hh BLI_math_base.h BLI_math_base_safe.h BLI_math_bits.h @@ -238,6 +241,7 @@ set(SRC BLI_math_vec_mpq_types.hh BLI_math_vec_types.hh BLI_math_vector.h + BLI_math_vector.hh BLI_memarena.h BLI_memblock.h BLI_memiter.h @@ -306,6 +310,9 @@ set(SRC BLI_winstuff.h PIL_time.h PIL_time_utildefines.h + + # Without these files listed, they aren't known to CMake. + ../../../extern/json/include/json.hpp ) set(LIB @@ -394,6 +401,7 @@ if(WITH_GTESTS) tests/BLI_array_store_test.cc tests/BLI_array_test.cc tests/BLI_array_utils_test.cc + tests/BLI_bounds_test.cc tests/BLI_color_test.cc tests/BLI_delaunay_2d_test.cc tests/BLI_disjoint_set_test.cc diff --git a/source/blender/blenlib/intern/delaunay_2d.cc b/source/blender/blenlib/intern/delaunay_2d.cc index cb0ba763c94..b7dbd7d679c 100644 --- a/source/blender/blenlib/intern/delaunay_2d.cc +++ b/source/blender/blenlib/intern/delaunay_2d.cc @@ -1691,7 +1691,7 @@ void fill_crossdata_for_intersect(const FatCo<T> &curco, BLI_assert(se_vcva->vert == vc && se_vcva->next->vert == va); BLI_assert(se_vcvb->vert == vc && se_vcvb->next->vert == vb); UNUSED_VARS_NDEBUG(vc); - auto isect = isect_seg_seg<vec2<T>>(va->co.exact, vb->co.exact, curco.exact, v2->co.exact); + auto isect = isect_seg_seg(va->co.exact, vb->co.exact, curco.exact, v2->co.exact); T &lambda = isect.lambda; switch (isect.kind) { case isect_result<vec2<T>>::LINE_LINE_CROSS: { @@ -2556,10 +2556,10 @@ template<typename T> void detect_holes(CDT_state<T> *cdt_state) if (e->symedges[0].face->visit_index == e->symedges[1].face->visit_index) { continue; /* Don't count hits on edges between faces in same region. */ } - auto isect = isect_seg_seg<vec2<T>>(ray_end.exact, - mid.exact, - e->symedges[0].vert->co.exact, - e->symedges[1].vert->co.exact); + auto isect = isect_seg_seg(ray_end.exact, + mid.exact, + e->symedges[0].vert->co.exact, + e->symedges[1].vert->co.exact); switch (isect.kind) { case isect_result<vec2<T>>::LINE_LINE_CROSS: { hits++; diff --git a/source/blender/blenlib/intern/index_mask.cc b/source/blender/blenlib/intern/index_mask.cc index b55de6a9264..1e301bc5fb9 100644 --- a/source/blender/blenlib/intern/index_mask.cc +++ b/source/blender/blenlib/intern/index_mask.cc @@ -1,9 +1,15 @@ /* SPDX-License-Identifier: GPL-2.0-or-later */ #include "BLI_index_mask.hh" +#include "BLI_index_mask_ops.hh" namespace blender { +IndexMask IndexMask::slice(int64_t start, int64_t size) const +{ + return this->slice(IndexRange(start, size)); +} + IndexMask IndexMask::slice(IndexRange slice) const { return IndexMask(indices_.slice(slice)); @@ -30,4 +36,161 @@ IndexMask IndexMask::slice_and_offset(const IndexRange slice, Vector<int64_t> &r return IndexMask(r_new_indices.as_span()); } +IndexMask IndexMask::invert(const IndexRange full_range, Vector<int64_t> &r_new_indices) const +{ + BLI_assert(this->contained_in(full_range)); + if (full_range.size() == indices_.size()) { + return {}; + } + if (indices_.is_empty()) { + return full_range; + } + r_new_indices.clear(); + + const Vector<IndexRange> ranges = this->extract_ranges_invert(full_range, nullptr); + for (const IndexRange &range : ranges) { + for (const int64_t index : range) { + r_new_indices.append(index); + } + } + return r_new_indices.as_span(); +} + +Vector<IndexRange> IndexMask::extract_ranges() const +{ + Vector<IndexRange> ranges; + int64_t range_start = 0; + while (range_start < indices_.size()) { + int64_t current_range_end = range_start + 1; + int64_t step_size = 1; + + while (true) { + const int64_t possible_range_end = current_range_end + step_size; + if (possible_range_end > indices_.size()) { + break; + } + if (!this->slice(range_start, possible_range_end - range_start).is_range()) { + break; + } + current_range_end = possible_range_end; + step_size *= 2; + } + + /* This step size was tried already, no need to try it again. */ + step_size /= 2; + + while (step_size > 0) { + const int64_t possible_range_end = current_range_end + step_size; + step_size /= 2; + if (possible_range_end > indices_.size()) { + continue; + } + if (!this->slice(range_start, possible_range_end - range_start).is_range()) { + continue; + } + current_range_end = possible_range_end; + } + + ranges.append(IndexRange{indices_[range_start], current_range_end - range_start}); + range_start = current_range_end; + } + return ranges; +} + +Vector<IndexRange> IndexMask::extract_ranges_invert(const IndexRange full_range, + Vector<int64_t> *r_skip_amounts) const +{ + BLI_assert(this->contained_in(full_range)); + const Vector<IndexRange> ranges = this->extract_ranges(); + Vector<IndexRange> inverted_ranges; + + int64_t skip_amount = 0; + int64_t next_start = full_range.start(); + for (const int64_t i : ranges.index_range()) { + const IndexRange range = ranges[i]; + if (range.start() > next_start) { + inverted_ranges.append({next_start, range.start() - next_start}); + if (r_skip_amounts != nullptr) { + r_skip_amounts->append(skip_amount); + } + } + next_start = range.one_after_last(); + skip_amount += range.size(); + } + if (next_start < full_range.one_after_last()) { + inverted_ranges.append({next_start, full_range.one_after_last() - next_start}); + if (r_skip_amounts != nullptr) { + r_skip_amounts->append(skip_amount); + } + } + return inverted_ranges; +} + } // namespace blender + +namespace blender::index_mask_ops::detail { + +IndexMask find_indices_based_on_predicate__merge( + IndexMask indices_to_check, + threading::EnumerableThreadSpecific<Vector<Vector<int64_t>>> &sub_masks, + Vector<int64_t> &r_indices) +{ + /* Gather vectors that have been generated by possibly multiple threads. */ + Vector<Vector<int64_t> *> all_vectors; + int64_t result_mask_size = 0; + for (Vector<Vector<int64_t>> &local_sub_masks : sub_masks) { + for (Vector<int64_t> &sub_mask : local_sub_masks) { + all_vectors.append(&sub_mask); + result_mask_size += sub_mask.size(); + } + } + + if (all_vectors.is_empty()) { + /* Special case when the predicate was false for all elements. */ + return {}; + } + if (result_mask_size == indices_to_check.size()) { + /* Special case when the predicate was true for all elements. */ + return indices_to_check; + } + if (all_vectors.size() == 1) { + /* Special case when all indices for which the predicate is true happen to be in a single + * vector. */ + r_indices = std::move(*all_vectors[0]); + return r_indices.as_span(); + } + + /* Indices in separate vectors don't overlap. So it is ok to sort the vectors just by looking at + * the first element. */ + std::sort(all_vectors.begin(), + all_vectors.end(), + [](const Vector<int64_t> *a, const Vector<int64_t> *b) { return (*a)[0] < (*b)[0]; }); + + /* Precompute the offsets for the individual vectors, so that the indices can be copied into the + * final vector in parallel. */ + Vector<int64_t> offsets; + offsets.reserve(all_vectors.size() + 1); + offsets.append(0); + for (Vector<int64_t> *vector : all_vectors) { + offsets.append(offsets.last() + vector->size()); + } + + r_indices.resize(result_mask_size); + + /* Fill the final index mask in parallel again. */ + threading::parallel_for(all_vectors.index_range(), 100, [&](const IndexRange all_vectors_range) { + for (const int64_t vector_index : all_vectors_range) { + Vector<int64_t> &vector = *all_vectors[vector_index]; + const int64_t offset = offsets[vector_index]; + threading::parallel_for(vector.index_range(), 1024, [&](const IndexRange range) { + initialized_copy_n(vector.data() + range.start(), + range.size(), + r_indices.data() + offset + range.start()); + }); + } + }); + + return r_indices.as_span(); +} + +} // namespace blender::index_mask_ops::detail diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index f96c80185b1..bc3ed099fd5 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -903,6 +903,18 @@ float dist_squared_to_projected_aabb_simple(const float projmat[4][4], /** \} */ +float dist_seg_seg_v2(const float a1[3], const float a2[3], const float b1[3], const float b2[3]) +{ + if (isect_seg_seg_v2_simple(a1, a2, b1, b2)) { + return 0.0f; + } + const float d1 = dist_squared_to_line_segment_v2(a1, b1, b2); + const float d2 = dist_squared_to_line_segment_v2(a2, b1, b2); + const float d3 = dist_squared_to_line_segment_v2(b1, a1, a2); + const float d4 = dist_squared_to_line_segment_v2(b2, a1, a2); + return sqrtf(min_ffff(d1, d2, d3, d4)); +} + void closest_on_tri_to_point_v3( float r[3], const float p[3], const float v1[3], const float v2[3], const float v3[3]) { diff --git a/source/blender/blenlib/intern/mesh_boolean.cc b/source/blender/blenlib/intern/mesh_boolean.cc index 6e2e9787ebe..70030fc2bdf 100644 --- a/source/blender/blenlib/intern/mesh_boolean.cc +++ b/source/blender/blenlib/intern/mesh_boolean.cc @@ -2185,7 +2185,7 @@ static void finish_patch_cell_graph(const IMesh &tm, * There will be a vector of \a nshapes winding numbers in each cell, one per * input shape. * As one crosses a patch into a new cell, the original shape (mesh part) - * that that patch was part of dictates which winding number changes. + * that patch was part of dictates which winding number changes. * The shape_fn(triangle_number) function should return the shape that the * triangle is part of. * Also, as soon as the winding numbers for a cell are set, use bool_optype diff --git a/source/blender/blenlib/intern/string.c b/source/blender/blenlib/intern/string.c index 976c1b0226f..75fa628e701 100644 --- a/source/blender/blenlib/intern/string.c +++ b/source/blender/blenlib/intern/string.c @@ -307,8 +307,9 @@ size_t BLI_str_unescape_ex(char *__restrict dst, { size_t len = 0; bool is_complete = true; + const size_t max_strlen = dst_maxncpy - 1; /* Account for trailing zero byte. */ for (const char *src_end = src + src_maxncpy; (src < src_end) && *src; src++) { - if (UNLIKELY(len == dst_maxncpy)) { + if (UNLIKELY(len == max_strlen)) { is_complete = false; break; } diff --git a/source/blender/blenlib/tests/BLI_array_test.cc b/source/blender/blenlib/tests/BLI_array_test.cc index 6d12b54099a..74eeb5e4e5e 100644 --- a/source/blender/blenlib/tests/BLI_array_test.cc +++ b/source/blender/blenlib/tests/BLI_array_test.cc @@ -231,9 +231,11 @@ TEST(array, Last) { Array<int> array = {5, 7, 8, 9}; EXPECT_EQ(array.last(), 9); + EXPECT_EQ(array.last(1), 8); array.last() = 1; EXPECT_EQ(array[3], 1); EXPECT_EQ(const_cast<const Array<int> &>(array).last(), 1); + EXPECT_EQ(const_cast<const Array<int> &>(array).last(2), 7); } TEST(array, Reinitialize) diff --git a/source/blender/blenlib/tests/BLI_bounds_test.cc b/source/blender/blenlib/tests/BLI_bounds_test.cc new file mode 100644 index 00000000000..9c123d4705c --- /dev/null +++ b/source/blender/blenlib/tests/BLI_bounds_test.cc @@ -0,0 +1,57 @@ +/* SPDX-License-Identifier: Apache-2.0 */ + +#include "testing/testing.h" + +#include "BLI_math_base.hh" + +#include "BLI_array.hh" +#include "BLI_bounds.hh" + +namespace blender::tests { + +TEST(bounds, Empty) +{ + Span<float2> empty_span{}; + EXPECT_TRUE(empty_span.is_empty()); + auto result = bounds::min_max(empty_span); + EXPECT_EQ(result, std::nullopt); +} + +TEST(bounds, MinMax) +{ + Array<float2> data = {float2(0, 1), float2(3, -1), float2(0, -2), float2(-1, 1)}; + auto result = bounds::min_max(data.as_span()); + EXPECT_EQ(result->min, float2(-1, -2)); + EXPECT_EQ(result->max, float2(3, 1)); +} + +TEST(bounds, MinMaxFloat) +{ + Array<float> data = {1.0f, 3.0f, 0.0f, -1.0f}; + auto result = bounds::min_max(data.as_span()); + EXPECT_EQ(result->min, -1.0f); + EXPECT_EQ(result->max, 3.0f); +} + +TEST(bounds, MinMaxRadii) +{ + Array<int2> data = {int2(0, 1), int2(3, -1), int2(0, -2), int2(-1, 1)}; + Array<int> radii = {5, 1, 1, 4}; + auto result = bounds::min_max_with_radii(data.as_span(), radii.as_span()); + EXPECT_EQ(result->min, int2(-5, -4)); + EXPECT_EQ(result->max, int2(5, 6)); +} + +TEST(bounds, Large) +{ + Array<int2> data(10000); + for (const int64_t i : data.index_range()) { + data[i] = int2(i, i); + } + + auto result = bounds::min_max(data.as_span()); + EXPECT_EQ(result->min, int2(0, 0)); + EXPECT_EQ(result->max, int2(9999, 9999)); +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_index_mask_test.cc b/source/blender/blenlib/tests/BLI_index_mask_test.cc index 179c1c58cc4..86ae31cedcc 100644 --- a/source/blender/blenlib/tests/BLI_index_mask_test.cc +++ b/source/blender/blenlib/tests/BLI_index_mask_test.cc @@ -64,4 +64,153 @@ TEST(index_mask, SliceAndOffset) } } +TEST(index_mask, ExtractRanges) +{ + { + Vector<int64_t> indices = {1, 2, 3, 5, 7, 8}; + Vector<IndexRange> ranges = IndexMask(indices).extract_ranges(); + EXPECT_EQ(ranges.size(), 3); + EXPECT_EQ(ranges[0], IndexRange(1, 3)); + EXPECT_EQ(ranges[1], IndexRange(5, 1)); + EXPECT_EQ(ranges[2], IndexRange(7, 2)); + } + { + Vector<int64_t> indices; + Vector<IndexRange> ranges = IndexMask(indices).extract_ranges(); + EXPECT_EQ(ranges.size(), 0); + } + { + Vector<int64_t> indices = {5, 6, 7, 8, 9, 10}; + Vector<IndexRange> ranges = IndexMask(indices).extract_ranges(); + EXPECT_EQ(ranges.size(), 1); + EXPECT_EQ(ranges[0], IndexRange(5, 6)); + } + { + Vector<int64_t> indices = {1, 3, 6, 8}; + Vector<IndexRange> ranges = IndexMask(indices).extract_ranges(); + EXPECT_EQ(ranges.size(), 4); + EXPECT_EQ(ranges[0], IndexRange(1, 1)); + EXPECT_EQ(ranges[1], IndexRange(3, 1)); + EXPECT_EQ(ranges[2], IndexRange(6, 1)); + EXPECT_EQ(ranges[3], IndexRange(8, 1)); + } + { + Vector<int64_t> indices; + IndexRange range1{4, 10}; + IndexRange range2{20, 30}; + IndexRange range3{100, 1}; + IndexRange range4{150, 100}; + for (const IndexRange &range : {range1, range2, range3, range4}) { + for (const int64_t i : range) { + indices.append(i); + } + } + Vector<IndexRange> ranges = IndexMask(indices).extract_ranges(); + EXPECT_EQ(ranges.size(), 4); + EXPECT_EQ(ranges[0], range1); + EXPECT_EQ(ranges[1], range2); + EXPECT_EQ(ranges[2], range3); + EXPECT_EQ(ranges[3], range4); + } + { + const int64_t max_test_range_size = 50; + Vector<int64_t> indices; + int64_t offset = 0; + for (const int64_t range_size : IndexRange(1, max_test_range_size)) { + for (const int i : IndexRange(range_size)) { + indices.append(offset + i); + } + offset += range_size + 1; + } + Vector<IndexRange> ranges = IndexMask(indices).extract_ranges(); + EXPECT_EQ(ranges.size(), max_test_range_size); + for (const int64_t range_size : IndexRange(1, max_test_range_size)) { + const IndexRange range = ranges[range_size - 1]; + EXPECT_EQ(range.size(), range_size); + } + } +} + +TEST(index_mask, Invert) +{ + { + Vector<int64_t> indices; + Vector<int64_t> new_indices; + IndexMask inverted_mask = IndexMask(indices).invert(IndexRange(10), new_indices); + EXPECT_EQ(inverted_mask.size(), 10); + EXPECT_TRUE(new_indices.is_empty()); + } + { + Vector<int64_t> indices = {3, 4, 5, 6}; + Vector<int64_t> new_indices; + IndexMask inverted_mask = IndexMask(indices).invert(IndexRange(3, 4), new_indices); + EXPECT_TRUE(inverted_mask.is_empty()); + } + { + Vector<int64_t> indices = {5}; + Vector<int64_t> new_indices; + IndexMask inverted_mask = IndexMask(indices).invert(IndexRange(10), new_indices); + EXPECT_EQ(inverted_mask.size(), 9); + EXPECT_EQ(inverted_mask.indices(), Span<int64_t>({0, 1, 2, 3, 4, 6, 7, 8, 9})); + } + { + Vector<int64_t> indices = {0, 1, 2, 6, 7, 9}; + Vector<int64_t> new_indices; + IndexMask inverted_mask = IndexMask(indices).invert(IndexRange(10), new_indices); + EXPECT_EQ(inverted_mask.size(), 4); + EXPECT_EQ(inverted_mask.indices(), Span<int64_t>({3, 4, 5, 8})); + } +} + +TEST(index_mask, ExtractRangesInvert) +{ + { + Vector<int64_t> indices; + Vector<IndexRange> ranges = IndexMask(indices).extract_ranges_invert(IndexRange(10), nullptr); + EXPECT_EQ(ranges.size(), 1); + EXPECT_EQ(ranges[0], IndexRange(10)); + } + { + Vector<int64_t> indices = {1, 2, 3, 6, 7}; + Vector<int64_t> skip_amounts; + Vector<IndexRange> ranges = IndexMask(indices).extract_ranges_invert(IndexRange(10), + &skip_amounts); + EXPECT_EQ(ranges.size(), 3); + EXPECT_EQ(ranges[0], IndexRange(0, 1)); + EXPECT_EQ(ranges[1], IndexRange(4, 2)); + EXPECT_EQ(ranges[2], IndexRange(8, 2)); + EXPECT_EQ(skip_amounts[0], 0); + EXPECT_EQ(skip_amounts[1], 3); + EXPECT_EQ(skip_amounts[2], 5); + } + { + Vector<int64_t> indices = {0, 1, 2, 3, 4}; + Vector<int64_t> skip_amounts; + Vector<IndexRange> ranges = IndexMask(indices).extract_ranges_invert(IndexRange(5), + &skip_amounts); + EXPECT_TRUE(ranges.is_empty()); + EXPECT_TRUE(skip_amounts.is_empty()); + } + { + Vector<int64_t> indices = {5, 6, 7, 10, 11}; + Vector<int64_t> skip_amounts; + Vector<IndexRange> ranges = IndexMask(indices).extract_ranges_invert(IndexRange(5, 20), + &skip_amounts); + EXPECT_EQ(ranges.size(), 2); + EXPECT_EQ(ranges[0], IndexRange(8, 2)); + EXPECT_EQ(ranges[1], IndexRange(12, 13)); + EXPECT_EQ(skip_amounts[0], 3); + EXPECT_EQ(skip_amounts[1], 5); + } +} + +TEST(index_mask, ContainedIn) +{ + EXPECT_TRUE(IndexMask({3, 4, 5}).contained_in(IndexRange(10))); + EXPECT_TRUE(IndexMask().contained_in(IndexRange(5, 0))); + EXPECT_FALSE(IndexMask({3}).contained_in(IndexRange(3))); + EXPECT_FALSE(IndexMask({4, 5, 6}).contained_in(IndexRange(5, 10))); + EXPECT_FALSE(IndexMask({5, 6}).contained_in(IndexRange())); +} + } // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_math_base_test.cc b/source/blender/blenlib/tests/BLI_math_base_test.cc index 33acefeeac2..62f2b2775d0 100644 --- a/source/blender/blenlib/tests/BLI_math_base_test.cc +++ b/source/blender/blenlib/tests/BLI_math_base_test.cc @@ -3,6 +3,10 @@ #include "testing/testing.h" #include "BLI_math.h" +#include "BLI_math_base.hh" +#include "BLI_math_vector.hh" + +namespace blender::tests { /* In tests below, when we are using -1.0f as max_diff value, we actually turn the function into a * pure-ULP one. */ @@ -131,3 +135,20 @@ TEST(math_base, FloorPowerOf10) EXPECT_NEAR(floor_power_of_10(100.1f), 100.0f, 1e-4f); EXPECT_NEAR(floor_power_of_10(99.9f), 10.0f, 1e-4f); } + +TEST(math_base, MinVectorAndFloat) +{ + EXPECT_EQ(math::min(1.0f, 2.0f), 1.0f); +} + +TEST(math_base, ClampInt) +{ + EXPECT_EQ(math::clamp(111, -50, 101), 101); +} + +TEST(math_base, Midpoint) +{ + EXPECT_NEAR(math::midpoint(100.0f, 200.0f), 150.0f, 1e-4f); +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_math_vec_types_test.cc b/source/blender/blenlib/tests/BLI_math_vec_types_test.cc index 07eb6b29a20..7590d77525b 100644 --- a/source/blender/blenlib/tests/BLI_math_vec_types_test.cc +++ b/source/blender/blenlib/tests/BLI_math_vec_types_test.cc @@ -146,4 +146,29 @@ TEST(math_vec_types, VectorTypeConversion) EXPECT_EQ(d[1], -1.0); } +TEST(math_vec_types, Divide) +{ + float2 a(1.0f, 2.0f); + float2 b(0.5f, 2.0f); + float2 result = a / b; + EXPECT_FLOAT_EQ(result.x, 2.0f); + EXPECT_FLOAT_EQ(result.y, 1.0f); +} + +TEST(math_vec_types, DivideFloatByVector) +{ + float a = 2.0f; + float2 b(0.5f, 2.0f); + float2 result = a / b; + EXPECT_FLOAT_EQ(result.x, 4.0f); + EXPECT_FLOAT_EQ(result.y, 1.0f); +} + +TEST(math_vec_types, DivideFloatByVectorSmall) +{ + float2 result = 2.0f / float2(2.0f); + EXPECT_FLOAT_EQ(result.x, 1.0f); + EXPECT_FLOAT_EQ(result.y, 1.0f); +} + } // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_memory_utils_test.cc b/source/blender/blenlib/tests/BLI_memory_utils_test.cc index 993434ddeba..ab716e5d011 100644 --- a/source/blender/blenlib/tests/BLI_memory_utils_test.cc +++ b/source/blender/blenlib/tests/BLI_memory_utils_test.cc @@ -176,4 +176,29 @@ static_assert(!is_same_any_v<int, float, bool>); static_assert(!is_same_any_v<int, float>); static_assert(!is_same_any_v<int>); +TEST(memory_utils, ScopedDefer1) +{ + int a = 0; + { + BLI_SCOPED_DEFER([&]() { a -= 5; }); + { + BLI_SCOPED_DEFER([&]() { a *= 10; }); + a = 5; + } + } + EXPECT_EQ(a, 45); +} + +TEST(memory_utils, ScopedDefer2) +{ + std::string s; + { + BLI_SCOPED_DEFER([&]() { s += "A"; }); + BLI_SCOPED_DEFER([&]() { s += "B"; }); + BLI_SCOPED_DEFER([&]() { s += "C"; }); + BLI_SCOPED_DEFER([&]() { s += "D"; }); + } + EXPECT_EQ(s, "DCBA"); +} + } // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_span_test.cc b/source/blender/blenlib/tests/BLI_span_test.cc index 35fb22b3257..0bd34250deb 100644 --- a/source/blender/blenlib/tests/BLI_span_test.cc +++ b/source/blender/blenlib/tests/BLI_span_test.cc @@ -247,6 +247,8 @@ TEST(span, FirstLast) Span<int> a_span(a); EXPECT_EQ(a_span.first(), 6); EXPECT_EQ(a_span.last(), 9); + EXPECT_EQ(a_span.last(1), 8); + EXPECT_EQ(a_span.last(2), 7); } TEST(span, FirstLast_OneElement) @@ -255,6 +257,7 @@ TEST(span, FirstLast_OneElement) Span<int> a_span(&a, 1); EXPECT_EQ(a_span.first(), 3); EXPECT_EQ(a_span.last(), 3); + EXPECT_EQ(a_span.last(0), 3); } TEST(span, Get) diff --git a/source/blender/blenlib/tests/BLI_vector_test.cc b/source/blender/blenlib/tests/BLI_vector_test.cc index 40cda20c395..29b6d2b41fe 100644 --- a/source/blender/blenlib/tests/BLI_vector_test.cc +++ b/source/blender/blenlib/tests/BLI_vector_test.cc @@ -447,6 +447,9 @@ TEST(vector, Last) { Vector<int> a{3, 5, 7}; EXPECT_EQ(a.last(), 7); + EXPECT_EQ(a.last(0), 7); + EXPECT_EQ(a.last(1), 5); + EXPECT_EQ(a.last(2), 3); } TEST(vector, AppendNTimes) |