diff options
Diffstat (limited to 'source/blender/blenlib')
29 files changed, 759 insertions, 245 deletions
diff --git a/source/blender/blenlib/BLI_bitmap.h b/source/blender/blenlib/BLI_bitmap.h index 19d8525311c..973cc5c3d1e 100644 --- a/source/blender/blenlib/BLI_bitmap.h +++ b/source/blender/blenlib/BLI_bitmap.h @@ -27,7 +27,7 @@ typedef unsigned int BLI_bitmap; /** * Number of blocks needed to hold '_num' bits. */ -#define _BITMAP_NUM_BLOCKS(_num) (((_num) >> _BITMAP_POWER) + 1) +#define _BITMAP_NUM_BLOCKS(_num) (((_num) + _BITMAP_MASK) >> _BITMAP_POWER) /** * Size (in bytes) used to hold '_num' bits. @@ -54,6 +54,11 @@ typedef unsigned int BLI_bitmap; ((BLI_bitmap *)BLI_memarena_calloc(_mem, BLI_BITMAP_SIZE(_num)))) /** + * Declares a bitmap as a variable. + */ +#define BLI_BITMAP_DECLARE(_name, _num) BLI_bitmap _name[_BITMAP_NUM_BLOCKS(_num)] = {} + +/** * Get the value of a single bit at '_index'. */ #define BLI_BITMAP_TEST(_bitmap, _index) \ @@ -137,6 +142,12 @@ void BLI_bitmap_and_all(BLI_bitmap *dst, const BLI_bitmap *src, size_t bits); */ void BLI_bitmap_or_all(BLI_bitmap *dst, const BLI_bitmap *src, size_t bits); +/** + * Find index of the lowest unset bit. + * Returns -1 if all the bits are set. + */ +int BLI_bitmap_find_first_unset(const BLI_bitmap *bitmap, size_t bits); + #ifdef __cplusplus } #endif diff --git a/source/blender/blenlib/BLI_float3x3.hh b/source/blender/blenlib/BLI_float3x3.hh index 62478556d9b..6a9e7dd04f0 100644 --- a/source/blender/blenlib/BLI_float3x3.hh +++ b/source/blender/blenlib/BLI_float3x3.hh @@ -152,6 +152,13 @@ struct float3x3 { return result; } + friend float3 operator*(const float3x3 &a, const float3 &b) + { + float3 result; + mul_v3_m3v3(result, a.values, b); + return result; + } + void operator*=(const float3x3 &other) { mul_m3_m3_post(values, other.values); diff --git a/source/blender/blenlib/BLI_generic_span.hh b/source/blender/blenlib/BLI_generic_span.hh index 4c0bfc83ba8..143ab235d2e 100644 --- a/source/blender/blenlib/BLI_generic_span.hh +++ b/source/blender/blenlib/BLI_generic_span.hh @@ -16,20 +16,31 @@ namespace blender { */ class GSpan { protected: - const CPPType *type_; - const void *data_; - int64_t size_; + const CPPType *type_ = nullptr; + const void *data_ = nullptr; + int64_t size_ = 0; public: - GSpan(const CPPType &type, const void *buffer, int64_t size) - : type_(&type), data_(buffer), size_(size) + GSpan() = default; + + GSpan(const CPPType *type, const void *buffer, int64_t size) + : type_(type), data_(buffer), size_(size) { BLI_assert(size >= 0); BLI_assert(buffer != nullptr || size == 0); - BLI_assert(type.pointer_has_valid_alignment(buffer)); + BLI_assert(size == 0 || type != nullptr); + BLI_assert(type == nullptr || type->pointer_has_valid_alignment(buffer)); + } + + GSpan(const CPPType &type, const void *buffer, int64_t size) : GSpan(&type, buffer, size) + { + } + + GSpan(const CPPType &type) : type_(&type) + { } - GSpan(const CPPType &type) : GSpan(type, nullptr, 0) + GSpan(const CPPType *type) : type_(type) { } @@ -41,9 +52,15 @@ class GSpan { const CPPType &type() const { + BLI_assert(type_ != nullptr); return *type_; } + const CPPType *type_ptr() const + { + return type_; + } + bool is_empty() const { return size_ == 0; @@ -76,7 +93,7 @@ class GSpan { BLI_assert(start >= 0); BLI_assert(size >= 0); const int64_t new_size = std::max<int64_t>(0, std::min(size, size_ - start)); - return GSpan(*type_, POINTER_OFFSET(data_, type_->size() * start), new_size); + return GSpan(type_, POINTER_OFFSET(data_, type_->size() * start), new_size); } GSpan slice(const IndexRange range) const @@ -91,20 +108,31 @@ class GSpan { */ class GMutableSpan { protected: - const CPPType *type_; - void *data_; - int64_t size_; + const CPPType *type_ = nullptr; + void *data_ = nullptr; + int64_t size_ = 0; public: - GMutableSpan(const CPPType &type, void *buffer, int64_t size) - : type_(&type), data_(buffer), size_(size) + GMutableSpan() = default; + + GMutableSpan(const CPPType *type, void *buffer, int64_t size) + : type_(type), data_(buffer), size_(size) { BLI_assert(size >= 0); BLI_assert(buffer != nullptr || size == 0); - BLI_assert(type.pointer_has_valid_alignment(buffer)); + BLI_assert(size == 0 || type != nullptr); + BLI_assert(type == nullptr || type->pointer_has_valid_alignment(buffer)); + } + + GMutableSpan(const CPPType &type, void *buffer, int64_t size) : GMutableSpan(&type, buffer, size) + { + } + + GMutableSpan(const CPPType &type) : type_(&type) + { } - GMutableSpan(const CPPType &type) : GMutableSpan(type, nullptr, 0) + GMutableSpan(const CPPType *type) : type_(type) { } @@ -116,14 +144,20 @@ class GMutableSpan { operator GSpan() const { - return GSpan(*type_, data_, size_); + return GSpan(type_, data_, size_); } const CPPType &type() const { + BLI_assert(type_ != nullptr); return *type_; } + const CPPType *type_ptr() const + { + return type_; + } + bool is_empty() const { return size_ == 0; diff --git a/source/blender/blenlib/BLI_generic_virtual_array.hh b/source/blender/blenlib/BLI_generic_virtual_array.hh index 95305a0561d..43ca16a894f 100644 --- a/source/blender/blenlib/BLI_generic_virtual_array.hh +++ b/source/blender/blenlib/BLI_generic_virtual_array.hh @@ -257,22 +257,25 @@ class GVMutableArray : public GVArrayCommon { /** \} */ /* -------------------------------------------------------------------- */ -/** \name #GVArray_GSpan and #GVMutableArray_GSpan. +/** \name #GVArraySpan and #GMutableVArraySpan. * \{ */ -/* A generic version of VArray_Span. */ -class GVArray_GSpan : public GSpan { +/* A generic version of VArraySpan. */ +class GVArraySpan : public GSpan { private: GVArray varray_; void *owned_data_ = nullptr; public: - GVArray_GSpan(GVArray varray); - ~GVArray_GSpan(); + GVArraySpan(); + GVArraySpan(GVArray varray); + GVArraySpan(GVArraySpan &&other); + ~GVArraySpan(); + GVArraySpan &operator=(GVArraySpan &&other); }; -/* A generic version of VMutableArray_Span. */ -class GVMutableArray_GSpan : public GMutableSpan, NonCopyable, NonMovable { +/* A generic version of MutableVArraySpan. */ +class GMutableVArraySpan : public GMutableSpan, NonCopyable, NonMovable { private: GVMutableArray varray_; void *owned_data_ = nullptr; @@ -280,8 +283,13 @@ class GVMutableArray_GSpan : public GMutableSpan, NonCopyable, NonMovable { bool show_not_saved_warning_ = true; public: - GVMutableArray_GSpan(GVMutableArray varray, bool copy_values_to_span = true); - ~GVMutableArray_GSpan(); + GMutableVArraySpan(); + GMutableVArraySpan(GVMutableArray varray, bool copy_values_to_span = true); + GMutableVArraySpan(GMutableVArraySpan &&other); + ~GMutableVArraySpan(); + GMutableVArraySpan &operator=(GMutableVArraySpan &&other); + + const GVMutableArray &varray() const; void save(); void disable_not_applied_warning(); diff --git a/source/blender/blenlib/BLI_index_range.hh b/source/blender/blenlib/BLI_index_range.hh index 7d5c2400bba..6fcc560d856 100644 --- a/source/blender/blenlib/BLI_index_range.hh +++ b/source/blender/blenlib/BLI_index_range.hh @@ -186,13 +186,25 @@ class IndexRange { } /** - * Get the last element in the range. - * Asserts when the range is empty. + * Get the nth last element in the range. + * Asserts when the range is empty or when n is negative. */ - constexpr int64_t last() const + constexpr int64_t last(const int64_t n = 0) const { + BLI_assert(n >= 0); + BLI_assert(n < size_); BLI_assert(this->size() > 0); - return start_ + size_ - 1; + return start_ + size_ - 1 - n; + } + + /** + * Get the element one before the beginning. The returned value is undefined when the range is + * empty, and the range must start after zero already. + */ + constexpr int64_t one_before_start() const + { + BLI_assert(start_ > 0); + return start_ - 1; } /** @@ -280,6 +292,15 @@ class IndexRange { } /** + * Move the range forward or backward within the larger array. The amount may be negative, + * but its absolute value cannot be greater than the existing start of the range. + */ + constexpr IndexRange shift(int64_t n) const + { + return IndexRange(start_ + n, size_); + } + + /** * Get read-only access to a memory buffer that contains the range as actual numbers. */ Span<int64_t> as_span() const; diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h index 8642d728909..17759b6a8ac 100644 --- a/source/blender/blenlib/BLI_kdopbvh.h +++ b/source/blender/blenlib/BLI_kdopbvh.h @@ -332,6 +332,29 @@ extern const float bvhtree_kdop_axes[13][3]; namespace blender { +using BVHTree_RayCastCallback_CPP = + FunctionRef<void(int index, const BVHTreeRay &ray, BVHTreeRayHit &hit)>; + +inline void BLI_bvhtree_ray_cast_all_cpp(BVHTree &tree, + const float3 co, + const float3 dir, + float radius, + float hit_dist, + BVHTree_RayCastCallback_CPP fn) +{ + BLI_bvhtree_ray_cast_all( + &tree, + co, + dir, + radius, + hit_dist, + [](void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) { + BVHTree_RayCastCallback_CPP fn = *static_cast<BVHTree_RayCastCallback_CPP *>(userdata); + fn(index, *ray, *hit); + }, + &fn); +} + using BVHTree_RangeQuery_CPP = FunctionRef<void(int index, const float3 &co, float dist_sq)>; inline void BLI_bvhtree_range_query_cpp(BVHTree &tree, diff --git a/source/blender/blenlib/BLI_length_parameterize.hh b/source/blender/blenlib/BLI_length_parameterize.hh index ec0fabb75b4..d81bcbe1e7a 100644 --- a/source/blender/blenlib/BLI_length_parameterize.hh +++ b/source/blender/blenlib/BLI_length_parameterize.hh @@ -6,10 +6,10 @@ * \ingroup bli */ +#include "BLI_index_mask.hh" #include "BLI_math_base.hh" #include "BLI_math_color.hh" #include "BLI_math_vector.hh" -#include "BLI_vector.hh" namespace blender::length_parameterize { @@ -17,9 +17,9 @@ namespace blender::length_parameterize { * Return the size of the necessary lengths array for a group of points, taking into account the * possible last cyclic segment. * - * \note This is the same as #bke::curves::curve_segment_num. + * \note This is the same as #bke::curves::segments_num. */ -inline int lengths_num(const int points_num, const bool cyclic) +inline int segments_num(const int points_num, const bool cyclic) { return cyclic ? points_num : points_num - 1; } @@ -30,7 +30,7 @@ inline int lengths_num(const int points_num, const bool cyclic) template<typename T> void accumulate_lengths(const Span<T> values, const bool cyclic, MutableSpan<float> lengths) { - BLI_assert(lengths.size() == lengths_num(values.size(), cyclic)); + BLI_assert(lengths.size() == segments_num(values.size(), cyclic)); float length = 0.0f; for (const int i : IndexRange(values.size() - 1)) { length += math::distance(values[i], values[i + 1]); @@ -42,57 +42,135 @@ void accumulate_lengths(const Span<T> values, const bool cyclic, MutableSpan<flo } template<typename T> -void linear_interpolation(const Span<T> src, - const Span<int> indices, - const Span<float> factors, - MutableSpan<T> dst) +inline void interpolate_to_masked(const Span<T> src, + const Span<int> indices, + const Span<float> factors, + const IndexMask dst_mask, + MutableSpan<T> dst) { BLI_assert(indices.size() == factors.size()); - BLI_assert(indices.size() == dst.size()); - const int last_src_index = src.index_range().last(); + BLI_assert(indices.size() == dst_mask.size()); + const int last_src_index = src.size() - 1; - int cyclic_sample_count = 0; - for (int i = indices.index_range().last(); i > 0; i--) { - if (indices[i] != last_src_index) { - break; + dst_mask.to_best_mask_type([&](auto dst_mask) { + for (const int i : IndexRange(dst_mask.size())) { + const int prev_index = indices[i]; + const float factor = factors[i]; + const bool is_cyclic_case = prev_index == last_src_index; + if (is_cyclic_case) { + dst[dst_mask[i]] = math::interpolate(src.last(), src.first(), factor); + } + else { + dst[dst_mask[i]] = math::interpolate(src[prev_index], src[prev_index + 1], factor); + } } - dst[i] = math::interpolate(src.last(), src.first(), factors[i]); - cyclic_sample_count++; + }); +} + +template<typename T> +inline void interpolate(const Span<T> src, + const Span<int> indices, + const Span<float> factors, + MutableSpan<T> dst) +{ + interpolate_to_masked(src, indices, factors, dst.index_range(), dst); +} + +/** + * Passing this to consecutive calls of #sample_at_length can increase performance. + */ +struct SampleSegmentHint { + int segment_index = -1; + float segment_start; + float segment_length_inv; +}; + +/** + * \param accumulated_segment_lengths: Lengths of individual segments added up. + * Each value describes the total length at the end of the segment following a point. + * \param sample_length: The position to sample at. + * \param r_segment_index: Returns the index of the segment that #sample_length is in. + * \param r_factor: Returns the position within the segment. + * + * \note #sample_length must not be outside of any segment. + */ +inline void sample_at_length(const Span<float> accumulated_segment_lengths, + const float sample_length, + int &r_segment_index, + float &r_factor, + SampleSegmentHint *hint = nullptr) +{ + /* Use a shorter variable name. */ + const Span<float> lengths = accumulated_segment_lengths; + + BLI_assert(lengths.size() > 0); + BLI_assert(sample_length >= 0.0f); + BLI_assert(sample_length <= lengths.last()); + + if (hint != nullptr && hint->segment_index >= 0) { + const float length_in_segment = sample_length - hint->segment_start; + const float factor = length_in_segment * hint->segment_length_inv; + if (factor >= 0.0f && factor < 1.0f) { + r_segment_index = hint->segment_index; + r_factor = factor; + return; + } + } + + const float total_length = lengths.last(); + if (sample_length >= total_length) { + /* Return the last position on the last segment. */ + r_segment_index = lengths.size() - 1; + r_factor = 1.0f; + return; } - for (const int i : dst.index_range().drop_back(cyclic_sample_count)) { - dst[i] = math::interpolate(src[indices[i]], src[indices[i] + 1], factors[i]); + const int prev_point_index = std::upper_bound(lengths.begin(), lengths.end(), sample_length) - + lengths.begin(); + const float segment_start = prev_point_index == 0 ? 0.0f : lengths[prev_point_index - 1]; + const float segment_end = lengths[prev_point_index]; + const float segment_length = segment_end - segment_start; + const float segment_length_inv = math::safe_divide(1.0f, segment_length); + const float length_in_segment = sample_length - segment_start; + const float factor = length_in_segment * segment_length_inv; + + r_segment_index = prev_point_index; + r_factor = factor; + + if (hint != nullptr) { + hint->segment_index = r_segment_index; + hint->segment_start = segment_start; + hint->segment_length_inv = segment_length_inv; } } /** - * Find the given number of points, evenly spaced along the provided length. For non-cyclic - * sequences, the first point will always be included, and last point will always be included if - * the #count is greater than zero. For cyclic sequences, the first point will always be included. + * Find evenly spaced samples along the lengths. * - * \warning The #count argument must be greater than zero. + * \param accumulated_segment_lengths: The accumulated lengths of the original elements being + * sampled. Could be calculated by #accumulate_lengths. + * \param include_last_point: Generally false for cyclic sequences and true otherwise. + * \param r_segment_indices: The index of the previous point at each sample. + * \param r_factors: The portion of the length in each segment at each sample. */ -void create_uniform_samples(Span<float> lengths, - bool cyclic, - MutableSpan<int> indices, - MutableSpan<float> factors); +void sample_uniform(Span<float> accumulated_segment_lengths, + bool include_last_point, + MutableSpan<int> r_segment_indices, + MutableSpan<float> r_factors); /** * For each provided sample length, find the segment index and interpolation factor. * - * \param lengths: The accumulated lengths of the original elements being sampled. - * Could be calculated by #accumulate_lengths. + * \param accumulated_segment_lengths: The accumulated lengths of the original elements being + * sampled. Could be calculated by #accumulate_lengths. * \param sample_lengths: Sampled locations in the #lengths array. Must be sorted and is expected * to be within the range of the #lengths values. - * \param cyclic: Whether the points described by the #lengths input is cyclic. This is likely - * redundant information theoretically. - * \param indices: The index of the previous point at each sample. - * \param factors: The portion of the length in each segment at each sample. + * \param r_segment_indices: The index of the previous point at each sample. + * \param r_factors: The portion of the length in each segment at each sample. */ -void create_samples_from_sorted_lengths(Span<float> lengths, - Span<float> sample_lengths, - bool cyclic, - MutableSpan<int> indices, - MutableSpan<float> factors); +void sample_at_lengths(Span<float> accumulated_segment_lengths, + Span<float> sample_lengths, + MutableSpan<int> r_segment_indices, + MutableSpan<float> r_factors); } // namespace blender::length_parameterize diff --git a/source/blender/blenlib/BLI_math_base.h b/source/blender/blenlib/BLI_math_base.h index f072a17f384..c0c4594ddc0 100644 --- a/source/blender/blenlib/BLI_math_base.h +++ b/source/blender/blenlib/BLI_math_base.h @@ -221,6 +221,19 @@ MINLINE unsigned int power_of_2_min_u(unsigned int x); * with integers, to avoid gradual darkening when rounding down. */ MINLINE int divide_round_i(int a, int b); + +/** + * Integer division that returns the ceiling, instead of flooring like normal C division. + */ +MINLINE uint divide_ceil_u(uint a, uint b); +MINLINE uint64_t divide_ceil_ul(uint64_t a, uint64_t b); + +/** + * Returns \a a if it is a multiple of \a b or the next multiple or \a b after \b a . + */ +MINLINE uint ceil_to_multiple_u(uint a, uint b); +MINLINE uint64_t ceil_to_multiple_ul(uint64_t a, uint64_t b); + /** * modulo that handles negative numbers, works the same as Python's. */ diff --git a/source/blender/blenlib/BLI_math_matrix.h b/source/blender/blenlib/BLI_math_matrix.h index 2cd2a299d53..c2dafbe3a1a 100644 --- a/source/blender/blenlib/BLI_math_matrix.h +++ b/source/blender/blenlib/BLI_math_matrix.h @@ -238,6 +238,7 @@ bool invert_m3_ex(float m[3][3], float epsilon); bool invert_m3_m3_ex(float m1[3][3], const float m2[3][3], float epsilon); bool invert_m3(float R[3][3]); +bool invert_m2_m2(float R[2][2], const float A[2][2]); bool invert_m3_m3(float R[3][3], const float A[3][3]); bool invert_m4(float R[4][4]); bool invert_m4_m4(float R[4][4], const float A[4][4]); diff --git a/source/blender/blenlib/BLI_math_rotation.h b/source/blender/blenlib/BLI_math_rotation.h index 192ad482a69..fef51fa780e 100644 --- a/source/blender/blenlib/BLI_math_rotation.h +++ b/source/blender/blenlib/BLI_math_rotation.h @@ -176,6 +176,26 @@ void mat3_to_quat_is_ok(float q[4], const float mat[3][3]); /* Other. */ +/** + * Utility function that performs `sinf` & `cosf` where the quadrants of the circle + * will have exactly matching values when their sign is flipped. + * This works as long as the denominator can be divided by 2 or 4, + * otherwise `sinf` & `cosf` are used without any additional logic. + * + * Besides adjustments to precision, this function is the equivalent of: + * \code {.c} + * float phi = (2 * M_PI) * (float)i / (float)denominator; + * *r_sin = sinf(phi); + * *r_cos = cosf(phi); + * \endcode + * + * \param numerator: An integer factor in [0..denominator] (inclusive). + * \param denominator: The faction denominator (typically the number of segments of the circle). + * \param r_sin: The resulting sine. + * \param r_cos: The resulting cosine. + */ +void sin_cos_from_fraction(const int numerator, const int denominator, float *r_sin, float *r_cos); + void print_qt(const char *str, const float q[4]); #define print_qt_id(q) print_qt(STRINGIFY(q), q) diff --git a/source/blender/blenlib/BLI_math_rotation.hh b/source/blender/blenlib/BLI_math_rotation.hh index e8b746b34df..50a062162ad 100644 --- a/source/blender/blenlib/BLI_math_rotation.hh +++ b/source/blender/blenlib/BLI_math_rotation.hh @@ -15,4 +15,13 @@ namespace blender::math { */ float3 rotate_direction_around_axis(const float3 &direction, const float3 &axis, float angle); +/** + * Rotate any arbitrary \a vector around the \a center position, with a unit-length \a axis + * and the specified \a angle. + */ +float3 rotate_around_axis(const float3 &vector, + const float3 ¢er, + const float3 &axis, + float angle); + } // namespace blender::math diff --git a/source/blender/blenlib/BLI_virtual_array.hh b/source/blender/blenlib/BLI_virtual_array.hh index d0436bdc213..438fcc4b8f7 100644 --- a/source/blender/blenlib/BLI_virtual_array.hh +++ b/source/blender/blenlib/BLI_virtual_array.hh @@ -51,7 +51,10 @@ struct CommonVArrayInfo { /** True when the #data becomes a dangling pointer when the virtual array is destructed. */ bool may_have_ownership = true; - /** Points either to nothing, a single value or array of values, depending on #type. */ + /** + * Points either to nothing, a single value or array of values, depending on #type. + * If this is a span of a mutable virtual array, it is safe to cast away const. + */ const void *data; CommonVArrayInfo() = default; @@ -1117,16 +1120,19 @@ template<typename T> static constexpr bool is_VMutableArray_v<VMutableArray<T>> * from faster access. * - An API is called, that does not accept virtual arrays, but only spans. */ -template<typename T> class VArray_Span final : public Span<T> { +template<typename T> class VArraySpan final : public Span<T> { private: VArray<T> varray_; Array<T> owned_data_; public: - VArray_Span() = default; + VArraySpan() = default; - VArray_Span(VArray<T> varray) : Span<T>(), varray_(std::move(varray)) + VArraySpan(VArray<T> varray) : Span<T>(), varray_(std::move(varray)) { + if (!varray_) { + return; + } this->size_ = varray_.size(); const CommonVArrayInfo info = varray_.common_info(); if (info.type == CommonVArrayInfo::Type::Span) { @@ -1140,9 +1146,12 @@ template<typename T> class VArray_Span final : public Span<T> { } } - VArray_Span(VArray_Span &&other) + VArraySpan(VArraySpan &&other) : varray_(std::move(other.varray_)), owned_data_(std::move(other.owned_data_)) { + if (!varray_) { + return; + } this->size_ = varray_.size(); const CommonVArrayInfo info = varray_.common_info(); if (info.type == CommonVArrayInfo::Type::Span) { @@ -1155,25 +1164,25 @@ template<typename T> class VArray_Span final : public Span<T> { other.size_ = 0; } - VArray_Span &operator=(VArray_Span &&other) + VArraySpan &operator=(VArraySpan &&other) { if (this == &other) { return *this; } std::destroy_at(this); - new (this) VArray_Span(std::move(other)); + new (this) VArraySpan(std::move(other)); return *this; } }; /** - * Same as #VArray_Span, but for a mutable span. + * Same as #VArraySpan, but for a mutable span. * The important thing to note is that when changing this span, the results might not be * immediately reflected in the underlying virtual array (only when the virtual array is a span * internally). The #save method can be used to write all changes to the underlying virtual array, * if necessary. */ -template<typename T> class VMutableArray_Span final : public MutableSpan<T> { +template<typename T> class MutableVArraySpan final : public MutableSpan<T> { private: VMutableArray<T> varray_; Array<T> owned_data_; @@ -1181,11 +1190,17 @@ template<typename T> class VMutableArray_Span final : public MutableSpan<T> { bool show_not_saved_warning_ = true; public: + MutableVArraySpan() = default; + /* Create a span for any virtual array. This is cheap when the virtual array is a span itself. If * not, a new array has to be allocated as a wrapper for the underlying virtual array. */ - VMutableArray_Span(VMutableArray<T> varray, const bool copy_values_to_span = true) + MutableVArraySpan(VMutableArray<T> varray, const bool copy_values_to_span = true) : MutableSpan<T>(), varray_(std::move(varray)) { + if (!varray_) { + return; + } + this->size_ = varray_.size(); const CommonVArrayInfo info = varray_.common_info(); if (info.type == CommonVArrayInfo::Type::Span) { @@ -1204,15 +1219,53 @@ template<typename T> class VMutableArray_Span final : public MutableSpan<T> { } } - ~VMutableArray_Span() + MutableVArraySpan(MutableVArraySpan &&other) + : varray_(std::move(other.varray_)), + owned_data_(std::move(other.owned_data_)), + show_not_saved_warning_(other.show_not_saved_warning_) + { + if (!varray_) { + return; + } + + this->size_ = varray_.size(); + const CommonVArrayInfo info = varray_.common_info(); + if (info.type == CommonVArrayInfo::Type::Span) { + this->data_ = static_cast<T *>(const_cast<void *>(info.data)); + } + else { + this->data_ = owned_data_.data(); + } + other.data_ = nullptr; + other.size_ = 0; + } + + ~MutableVArraySpan() { - if (show_not_saved_warning_) { - if (!save_has_been_called_) { - std::cout << "Warning: Call `save()` to make sure that changes persist in all cases.\n"; + if (varray_) { + if (show_not_saved_warning_) { + if (!save_has_been_called_) { + std::cout << "Warning: Call `save()` to make sure that changes persist in all cases.\n"; + } } } } + MutableVArraySpan &operator=(MutableVArraySpan &&other) + { + if (this == &other) { + return *this; + } + std::destroy_at(this); + new (this) MutableVArraySpan(std::move(other)); + return *this; + } + + const VMutableArray<T> &varray() const + { + return varray_; + } + /* Write back all values from a temporary allocated array to the underlying virtual array. */ void save() { diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 95b4987596e..d39a586206f 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -424,6 +424,7 @@ if(WITH_GTESTS) tests/BLI_array_store_test.cc tests/BLI_array_test.cc tests/BLI_array_utils_test.cc + tests/BLI_bitmap_test.cc tests/BLI_bounds_test.cc tests/BLI_color_test.cc tests/BLI_cpp_type_test.cc diff --git a/source/blender/blenlib/intern/bitmap.c b/source/blender/blenlib/intern/bitmap.c index 7fcbc31c066..2cc2fbc3e2f 100644 --- a/source/blender/blenlib/intern/bitmap.c +++ b/source/blender/blenlib/intern/bitmap.c @@ -11,6 +11,7 @@ #include <string.h> #include "BLI_bitmap.h" +#include "BLI_math_bits.h" #include "BLI_utildefines.h" void BLI_bitmap_set_all(BLI_bitmap *bitmap, bool set, size_t bits) @@ -46,3 +47,22 @@ void BLI_bitmap_or_all(BLI_bitmap *dst, const BLI_bitmap *src, size_t bits) dst[i] |= src[i]; } } + +int BLI_bitmap_find_first_unset(const BLI_bitmap *bitmap, const size_t bits) +{ + const size_t blocks_num = _BITMAP_NUM_BLOCKS(bits); + int result = -1; + /* Skip over completely set blocks. */ + int index = 0; + while (index < blocks_num && bitmap[index] == ~0u) { + index++; + } + if (index < blocks_num) { + /* Found a partially used block: find the lowest unused bit. */ + const uint m = ~bitmap[index]; + BLI_assert(m != 0); + const uint bit_index = bitscan_forward_uint(m); + result = bit_index + (index << _BITMAP_POWER); + } + return result; +} diff --git a/source/blender/blenlib/intern/filereader_zstd.c b/source/blender/blenlib/intern/filereader_zstd.c index 5f114f24fb0..aeb000e9754 100644 --- a/source/blender/blenlib/intern/filereader_zstd.c +++ b/source/blender/blenlib/intern/filereader_zstd.c @@ -281,7 +281,10 @@ static void zstd_close(FileReader *reader) if (zstd->reader.seek) { MEM_freeN(zstd->seek.uncompressed_ofs); MEM_freeN(zstd->seek.compressed_ofs); - MEM_freeN(zstd->seek.cached_content); + /* When an error has occurred this may be NULL, see: T99744. */ + if (zstd->seek.cached_content) { + MEM_freeN(zstd->seek.cached_content); + } } else { MEM_freeN((void *)zstd->in_buf.src); diff --git a/source/blender/blenlib/intern/generic_virtual_array.cc b/source/blender/blenlib/intern/generic_virtual_array.cc index 624af3c6ed1..f66b1e14fc6 100644 --- a/source/blender/blenlib/intern/generic_virtual_array.cc +++ b/source/blender/blenlib/intern/generic_virtual_array.cc @@ -284,11 +284,18 @@ template<int BufferSize> class GVArrayImpl_For_SmallTrivialSingleValue : public /** \} */ /* -------------------------------------------------------------------- */ -/** \name #GVArray_GSpan +/** \name #GVArraySpan * \{ */ -GVArray_GSpan::GVArray_GSpan(GVArray varray) : GSpan(varray.type()), varray_(std::move(varray)) +GVArraySpan::GVArraySpan() = default; + +GVArraySpan::GVArraySpan(GVArray varray) + : GSpan(varray ? &varray.type() : nullptr), varray_(std::move(varray)) { + if (!varray_) { + return; + } + size_ = varray_.size(); const CommonVArrayInfo info = varray_.common_info(); if (info.type == CommonVArrayInfo::Type::Span) { @@ -301,7 +308,27 @@ GVArray_GSpan::GVArray_GSpan(GVArray varray) : GSpan(varray.type()), varray_(std } } -GVArray_GSpan::~GVArray_GSpan() +GVArraySpan::GVArraySpan(GVArraySpan &&other) + : GSpan(other.type_ptr()), varray_(std::move(other.varray_)), owned_data_(other.owned_data_) +{ + if (!varray_) { + return; + } + + size_ = varray_.size(); + const CommonVArrayInfo info = varray_.common_info(); + if (info.type == CommonVArrayInfo::Type::Span) { + data_ = info.data; + } + else { + data_ = owned_data_; + } + other.owned_data_ = nullptr; + other.data_ = nullptr; + other.size_ = 0; +} + +GVArraySpan::~GVArraySpan() { if (owned_data_ != nullptr) { type_->destruct_n(owned_data_, size_); @@ -309,15 +336,30 @@ GVArray_GSpan::~GVArray_GSpan() } } +GVArraySpan &GVArraySpan::operator=(GVArraySpan &&other) +{ + if (this == &other) { + return *this; + } + std::destroy_at(this); + new (this) GVArraySpan(std::move(other)); + return *this; +} + /** \} */ /* -------------------------------------------------------------------- */ -/** \name #GVMutableArray_GSpan +/** \name #GMutableVArraySpan * \{ */ -GVMutableArray_GSpan::GVMutableArray_GSpan(GVMutableArray varray, const bool copy_values_to_span) - : GMutableSpan(varray.type()), varray_(std::move(varray)) +GMutableVArraySpan::GMutableVArraySpan() = default; + +GMutableVArraySpan::GMutableVArraySpan(GVMutableArray varray, const bool copy_values_to_span) + : GMutableSpan(varray ? &varray.type() : nullptr), varray_(std::move(varray)) { + if (!varray_) { + return; + } size_ = varray_.size(); const CommonVArrayInfo info = varray_.common_info(); if (info.type == CommonVArrayInfo::Type::Span) { @@ -335,11 +377,35 @@ GVMutableArray_GSpan::GVMutableArray_GSpan(GVMutableArray varray, const bool cop } } -GVMutableArray_GSpan::~GVMutableArray_GSpan() +GMutableVArraySpan::GMutableVArraySpan(GMutableVArraySpan &&other) + : GMutableSpan(other.type_ptr()), + varray_(std::move(other.varray_)), + owned_data_(other.owned_data_), + show_not_saved_warning_(other.show_not_saved_warning_) { - if (show_not_saved_warning_) { - if (!save_has_been_called_) { - std::cout << "Warning: Call `apply()` to make sure that changes persist in all cases.\n"; + if (!varray_) { + return; + } + size_ = varray_.size(); + const CommonVArrayInfo info = varray_.common_info(); + if (info.type == CommonVArrayInfo::Type::Span) { + data_ = const_cast<void *>(info.data); + } + else { + data_ = owned_data_; + } + other.owned_data_ = nullptr; + other.data_ = nullptr; + other.size_ = 0; +} + +GMutableVArraySpan::~GMutableVArraySpan() +{ + if (varray_) { + if (show_not_saved_warning_) { + if (!save_has_been_called_) { + std::cout << "Warning: Call `save()` to make sure that changes persist in all cases.\n"; + } } } if (owned_data_ != nullptr) { @@ -348,7 +414,17 @@ GVMutableArray_GSpan::~GVMutableArray_GSpan() } } -void GVMutableArray_GSpan::save() +GMutableVArraySpan &GMutableVArraySpan::operator=(GMutableVArraySpan &&other) +{ + if (this == &other) { + return *this; + } + std::destroy_at(this); + new (this) GMutableVArraySpan(std::move(other)); + return *this; +} + +void GMutableVArraySpan::save() { save_has_been_called_ = true; if (data_ != owned_data_) { @@ -357,11 +433,16 @@ void GVMutableArray_GSpan::save() varray_.set_all(owned_data_); } -void GVMutableArray_GSpan::disable_not_applied_warning() +void GMutableVArraySpan::disable_not_applied_warning() { show_not_saved_warning_ = false; } +const GVMutableArray &GMutableVArraySpan::varray() const +{ + return varray_; +} + /** \} */ /* -------------------------------------------------------------------- */ @@ -633,6 +714,15 @@ GVArray GVArray::ForEmpty(const CPPType &type) GVArray GVArray::slice(IndexRange slice) const { + const CommonVArrayInfo info = this->common_info(); + if (info.type == CommonVArrayInfo::Type::Single) { + return GVArray::ForSingle(this->type(), slice.size(), info.data); + } + /* Need to check for ownership, because otherwise the referenced data can be destructed when + * #this is destructed. */ + if (info.type == CommonVArrayInfo::Type::Span && !info.may_have_ownership) { + return GVArray::ForSpan(GSpan(this->type(), info.data, this->size()).slice(slice)); + } return GVArray::For<GVArrayImpl_For_SlicedGVArray>(*this, slice); } diff --git a/source/blender/blenlib/intern/index_mask.cc b/source/blender/blenlib/intern/index_mask.cc index f3590e4a41c..e9af183d60d 100644 --- a/source/blender/blenlib/intern/index_mask.cc +++ b/source/blender/blenlib/intern/index_mask.cc @@ -142,6 +142,7 @@ IndexMask find_indices_based_on_predicate__merge( 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) { + BLI_assert(!sub_mask.is_empty()); all_vectors.append(&sub_mask); result_mask_size += sub_mask.size(); } @@ -232,7 +233,9 @@ IndexMask find_indices_from_virtual_array(const IndexMask indices_to_check, } } }); - sub_masks.local().append(std::move(masked_indices)); + if (!masked_indices.is_empty()) { + sub_masks.local().append(std::move(masked_indices)); + } }); return detail::find_indices_based_on_predicate__merge(indices_to_check, sub_masks, r_indices); diff --git a/source/blender/blenlib/intern/length_parameterize.cc b/source/blender/blenlib/intern/length_parameterize.cc index 7c0fc860b53..06cca281510 100644 --- a/source/blender/blenlib/intern/length_parameterize.cc +++ b/source/blender/blenlib/intern/length_parameterize.cc @@ -1,144 +1,58 @@ /* SPDX-License-Identifier: GPL-2.0-or-later */ #include "BLI_length_parameterize.hh" +#include "BLI_task.hh" namespace blender::length_parameterize { -void create_uniform_samples(const Span<float> lengths, - const bool cyclic, - MutableSpan<int> indices, - MutableSpan<float> factors) +void sample_uniform(const Span<float> lengths, + const bool include_last_point, + MutableSpan<int> r_segment_indices, + MutableSpan<float> r_factors) { - const int count = indices.size(); + const int count = r_segment_indices.size(); BLI_assert(count > 0); BLI_assert(lengths.size() >= 1); BLI_assert(std::is_sorted(lengths.begin(), lengths.end())); - const int segments_num = lengths.size(); - const int points_num = cyclic ? segments_num : segments_num + 1; - indices.first() = 0; - factors.first() = 0.0f; if (count == 1) { + r_segment_indices[0] = 0; + r_factors[0] = 0.0f; return; } - const float total_length = lengths.last(); - if (total_length == 0.0f) { - indices.fill(0); - factors.fill(0.0f); - return; - } - - const float step_length = total_length / (count - (cyclic ? 0 : 1)); - const float step_length_inv = 1.0f / step_length; - - int i_dst = 1; - /* Store the length at the previous point in a variable so it can start out at zero - * (the lengths array doesn't contain 0 for the first point). */ - float prev_length = 0.0f; - for (const int i_src : IndexRange(points_num - 1)) { - const float next_length = lengths[i_src]; - const float segment_length = next_length - prev_length; - if (segment_length == 0.0f) { - continue; - } - /* Add every sample that fits in this segment. */ - const float segment_length_inv = 1.0f / segment_length; - const int segment_samples_num = std::ceil(next_length * step_length_inv - i_dst); - indices.slice(i_dst, segment_samples_num).fill(i_src); - - for (const int i : factors.index_range().slice(i_dst, segment_samples_num)) { - const float length_in_segment = step_length * i - prev_length; - factors[i] = length_in_segment * segment_length_inv; - } - - i_dst += segment_samples_num; - - prev_length = next_length; - } - - /* Add the samples on the last cyclic segment if necessary, and also the samples - * that weren't created in the previous loop due to floating point inaccuracy. */ - if (cyclic && lengths.size() > 1) { - indices.drop_front(i_dst).fill(points_num - 1); - const float segment_length = lengths.last() - lengths.last(1); - if (segment_length == 0.0f) { - return; - } - const float segment_length_inv = 1.0f / segment_length; - for (const int i : indices.index_range().drop_front(i_dst)) { - const float length_in_segment = step_length * i - prev_length; - factors[i] = length_in_segment * segment_length_inv; + const float step_length = total_length / (count - include_last_point); + threading::parallel_for(IndexRange(count), 512, [&](const IndexRange range) { + SampleSegmentHint hint; + for (const int i : range) { + /* Use minimum to avoid issues with floating point accuracy. */ + const float sample_length = std::min(total_length, i * step_length); + sample_at_length(lengths, sample_length, r_segment_indices[i], r_factors[i], &hint); } - } - else { - indices.drop_front(i_dst).fill(points_num - 2); - factors.drop_front(i_dst).fill(1.0f); - } + }); } -void create_samples_from_sorted_lengths(const Span<float> lengths, - const Span<float> sample_lengths, - const bool cyclic, - MutableSpan<int> indices, - MutableSpan<float> factors) +void sample_at_lengths(const Span<float> accumulated_segment_lengths, + const Span<float> sample_lengths, + MutableSpan<int> r_segment_indices, + MutableSpan<float> r_factors) { - BLI_assert(std::is_sorted(lengths.begin(), lengths.end())); + BLI_assert( + std::is_sorted(accumulated_segment_lengths.begin(), accumulated_segment_lengths.end())); BLI_assert(std::is_sorted(sample_lengths.begin(), sample_lengths.end())); - BLI_assert(indices.size() == sample_lengths.size()); - BLI_assert(indices.size() == factors.size()); - const int segments_num = lengths.size(); - const int points_num = cyclic ? segments_num : segments_num + 1; - const float total_length = lengths.last(); - if (total_length == 0.0f) { - indices.fill(0); - factors.fill(0.0f); - return; - } + const int count = sample_lengths.size(); + BLI_assert(count == r_segment_indices.size()); + BLI_assert(count == r_factors.size()); - int i_dst = 0; - /* Store the length at the previous point in a variable so it can start out at zero - * (the lengths array doesn't contain 0 for the first point). */ - float prev_length = 0.0f; - for (const int i_src : IndexRange(points_num - 1)) { - const float next_length = lengths[i_src]; - const float segment_length = next_length - prev_length; - if (segment_length == 0.0f) { - continue; - } - /* Add every sample that fits in this segment. It's also necessary to check if the last sample - * has been reached, since there is no upper bound on the number of samples in each segment. */ - const float segment_length_inv = 1.0f / segment_length; - while (i_dst < sample_lengths.size() && sample_lengths[i_dst] < next_length) { - const float length_in_segment = sample_lengths[i_dst] - prev_length; - const float factor = length_in_segment * segment_length_inv; - indices[i_dst] = i_src; - factors[i_dst] = factor; - i_dst++; + threading::parallel_for(IndexRange(count), 512, [&](const IndexRange range) { + SampleSegmentHint hint; + for (const int i : range) { + const float sample_length = sample_lengths[i]; + sample_at_length( + accumulated_segment_lengths, sample_length, r_segment_indices[i], r_factors[i], &hint); } - - prev_length = next_length; - } - - /* Add the samples on the last cyclic segment if necessary, and also the samples - * that weren't created in the previous loop due to floating point inaccuracy. */ - if (cyclic && lengths.size() > 1) { - const float segment_length = lengths.last() - lengths.last(1); - while (sample_lengths[i_dst] < total_length) { - const float length_in_segment = sample_lengths[i_dst] - prev_length; - const float factor = length_in_segment / segment_length; - indices[i_dst] = points_num - 1; - factors[i_dst] = factor; - i_dst++; - } - indices.drop_front(i_dst).fill(points_num - 1); - factors.drop_front(i_dst).fill(1.0f); - } - else { - indices.drop_front(i_dst).fill(points_num - 2); - factors.drop_front(i_dst).fill(1.0f); - } + }); } } // namespace blender::length_parameterize diff --git a/source/blender/blenlib/intern/math_base_inline.c b/source/blender/blenlib/intern/math_base_inline.c index cb7659a7059..fb71e84c23e 100644 --- a/source/blender/blenlib/intern/math_base_inline.c +++ b/source/blender/blenlib/intern/math_base_inline.c @@ -370,6 +370,11 @@ MINLINE uint divide_ceil_u(uint a, uint b) return (a + b - 1) / b; } +MINLINE uint64_t divide_ceil_ul(uint64_t a, uint64_t b) +{ + return (a + b - 1) / b; +} + /** * Returns \a a if it is a multiple of \a b or the next multiple or \a b after \b a . */ @@ -378,6 +383,11 @@ MINLINE uint ceil_to_multiple_u(uint a, uint b) return divide_ceil_u(a, b) * b; } +MINLINE uint64_t ceil_to_multiple_ul(uint64_t a, uint64_t b) +{ + return divide_ceil_ul(a, b) * b; +} + MINLINE int mod_i(int i, int n) { return (i % n + n) % n; diff --git a/source/blender/blenlib/intern/math_matrix.c b/source/blender/blenlib/intern/math_matrix.c index ce9abc36cad..fcd017b3082 100644 --- a/source/blender/blenlib/intern/math_matrix.c +++ b/source/blender/blenlib/intern/math_matrix.c @@ -1116,6 +1116,22 @@ double determinant_m3_array_db(const double m[3][3]) m[2][0] * (m[0][1] * m[1][2] - m[0][2] * m[1][1])); } +bool invert_m2_m2(float m1[2][2], const float m2[2][2]) +{ + adjoint_m2_m2(m1, m2); + float det = determinant_m2(m2[0][0], m2[1][0], m2[0][1], m2[1][1]); + + bool success = (det != 0.0f); + if (success) { + m1[0][0] /= det; + m1[1][0] /= det; + m1[0][1] /= det; + m1[1][1] /= det; + } + + return success; +} + bool invert_m3_ex(float m[3][3], const float epsilon) { float tmp[3][3]; diff --git a/source/blender/blenlib/intern/math_rotation.c b/source/blender/blenlib/intern/math_rotation.c index 92223bdf1d5..f0bfc7c21e1 100644 --- a/source/blender/blenlib/intern/math_rotation.c +++ b/source/blender/blenlib/intern/math_rotation.c @@ -915,6 +915,55 @@ float tri_to_quat(float q[4], const float a[3], const float b[3], const float c[ return len; } +void sin_cos_from_fraction(const int numerator, const int denominator, float *r_sin, float *r_cos) +{ + BLI_assert((numerator <= denominator) && (denominator > 0)); + if ((denominator & 3) == 0) { + const int denominator_4 = denominator / 4; + if (numerator <= denominator_4) { + /* Fall through. */ + } + else { + if (numerator <= denominator_4 * 2) { + const float phi = (float)(2.0 * M_PI) * + ((float)(numerator - denominator_4) / (float)denominator); + *r_sin = cosf(phi); + *r_cos = -sinf(phi); + } + else if (numerator <= denominator_4 * 3) { + const float phi = (float)(2.0 * M_PI) * + ((float)(numerator - (denominator_4 * 2)) / (float)denominator); + *r_sin = -sinf(phi); + *r_cos = -cosf(phi); + } + else { + const float phi = (float)(2.0 * M_PI) * + ((float)(numerator - (denominator_4 * 3)) / (float)denominator); + *r_cos = sinf(phi); + *r_sin = -cosf(phi); + } + return; + } + } + else if ((denominator & 1) == 0) { + const int denominator_2 = denominator / 2; + if (numerator <= denominator_2) { + /* Fall through. */ + } + else { + const float phi = (float)(2.0 * M_PI) * + ((float)(numerator - denominator_2) / (float)denominator); + *r_sin = -sinf(phi); + *r_cos = -cosf(phi); + return; + } + } + + const float phi = (float)(2.0 * M_PI) * ((float)numerator / (float)denominator); + *r_sin = sinf(phi); + *r_cos = cosf(phi); +} + void print_qt(const char *str, const float q[4]) { printf("%s: %.3f %.3f %.3f %.3f\n", str, q[0], q[1], q[2], q[3]); diff --git a/source/blender/blenlib/intern/math_rotation.cc b/source/blender/blenlib/intern/math_rotation.cc index 74300d55954..091e8af85d9 100644 --- a/source/blender/blenlib/intern/math_rotation.cc +++ b/source/blender/blenlib/intern/math_rotation.cc @@ -23,4 +23,17 @@ float3 rotate_direction_around_axis(const float3 &direction, const float3 &axis, return axis_scaled + diff * std::cos(angle) + cross * std::sin(angle); } +float3 rotate_around_axis(const float3 &vector, + const float3 ¢er, + const float3 &axis, + const float angle) + +{ + float3 result = vector - center; + float mat[3][3]; + axis_angle_normalized_to_mat3(mat, axis, angle); + mul_m3_v3(mat, result); + return result + center; +} + } // namespace blender::math diff --git a/source/blender/blenlib/intern/mesh_boolean.cc b/source/blender/blenlib/intern/mesh_boolean.cc index 700c126ca4c..d4586f95fe0 100644 --- a/source/blender/blenlib/intern/mesh_boolean.cc +++ b/source/blender/blenlib/intern/mesh_boolean.cc @@ -2966,6 +2966,11 @@ static std::ostream &operator<<(std::ostream &os, const FaceMergeState &fms) * \a tris all have the same original face. * Find the 2d edge/triangle topology for these triangles, but only the ones facing in the * norm direction, and whether each edge is dissolvable or not. + * If we did the initial triangulation properly, and any Delaunay triangulations of interections + * properly, then each triangle edge should have at most one neighbor. + * However, there can be anonalies. For example, if an input face is self-intersecting, we fall + * back on the floating poing polyfill triangulation, which, after which all bets are off. + * Hence, try to be tolerant of such unexpected topology. */ static void init_face_merge_state(FaceMergeState *fms, const Vector<int> &tris, @@ -3053,16 +3058,35 @@ static void init_face_merge_state(FaceMergeState *fms, std::cout << "me.v1 == mf.vert[i] so set edge[" << me_index << "].left_face = " << f << "\n"; } - BLI_assert(me.left_face == -1); - fms->edge[me_index].left_face = f; + if (me.left_face != -1) { + /* Unexpected in the normal case: this means more than one triangle shares this + * edge in the same orientation. But be tolerant of this case. By making this + * edge not dissolvable, we'll avoid future problems due to this non-manifold topology. + */ + if (dbg_level > 1) { + std::cout << "me.left_face was already occupied, so triangulation wasn't good\n"; + } + me.dissolvable = false; + } + else { + fms->edge[me_index].left_face = f; + } } else { if (dbg_level > 1) { std::cout << "me.v1 != mf.vert[i] so set edge[" << me_index << "].right_face = " << f << "\n"; } - BLI_assert(me.right_face == -1); - fms->edge[me_index].right_face = f; + if (me.right_face != -1) { + /* Unexpected, analogous to the me.left_face != -1 case above. */ + if (dbg_level > 1) { + std::cout << "me.right_face was already occupied, so triangulation wasn't good\n"; + } + me.dissolvable = false; + } + else { + fms->edge[me_index].right_face = f; + } } fms->face[f].edge.append(me_index); } diff --git a/source/blender/blenlib/intern/rct.c b/source/blender/blenlib/intern/rct.c index 0bb606c288e..7248db5b718 100644 --- a/source/blender/blenlib/intern/rct.c +++ b/source/blender/blenlib/intern/rct.c @@ -265,7 +265,7 @@ bool BLI_rcti_isect_segment(const rcti *rect, const int s1[2], const int s2[2]) /* diagonal: [/] */ tvec1[0] = rect->xmin; tvec1[1] = rect->ymin; - tvec2[0] = rect->xmin; + tvec2[0] = rect->xmax; tvec2[1] = rect->ymax; if (isect_segments_i(s1, s2, tvec1, tvec2)) { return true; @@ -311,7 +311,7 @@ bool BLI_rctf_isect_segment(const rctf *rect, const float s1[2], const float s2[ /* diagonal: [/] */ tvec1[0] = rect->xmin; tvec1[1] = rect->ymin; - tvec2[0] = rect->xmin; + tvec2[0] = rect->xmax; tvec2[1] = rect->ymax; if (isect_segments_fl(s1, s2, tvec1, tvec2)) { return true; diff --git a/source/blender/blenlib/intern/timeit.cc b/source/blender/blenlib/intern/timeit.cc index f11f9c4ad94..7a8cf8da038 100644 --- a/source/blender/blenlib/intern/timeit.cc +++ b/source/blender/blenlib/intern/timeit.cc @@ -3,19 +3,29 @@ #include "BLI_timeit.hh" #include <algorithm> +#include <iomanip> namespace blender::timeit { void print_duration(Nanoseconds duration) { - if (duration < std::chrono::microseconds(100)) { + using namespace std::chrono; + if (duration < microseconds(100)) { std::cout << duration.count() << " ns"; } - else if (duration < std::chrono::seconds(5)) { - std::cout << duration.count() / 1.0e6 << " ms"; + else if (duration < seconds(5)) { + std::cout << std::fixed << std::setprecision(1) << duration.count() / 1.0e6 << " ms"; + } + else if (duration > seconds(90)) { + /* Long durations: print seconds, and also H:m:s */ + const auto dur_hours = duration_cast<hours>(duration); + const auto dur_mins = duration_cast<minutes>(duration - dur_hours); + const auto dur_sec = duration_cast<seconds>(duration - dur_hours - dur_mins); + std::cout << std::fixed << std::setprecision(1) << duration.count() / 1.0e9 << " s (" + << dur_hours.count() << "H:" << dur_mins.count() << "m:" << dur_sec.count() << "s)"; } else { - std::cout << duration.count() / 1.0e9 << " s"; + std::cout << std::fixed << std::setprecision(1) << duration.count() / 1.0e9 << " s"; } } diff --git a/source/blender/blenlib/tests/BLI_bitmap_test.cc b/source/blender/blenlib/tests/BLI_bitmap_test.cc new file mode 100644 index 00000000000..fb9e03e3136 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_bitmap_test.cc @@ -0,0 +1,46 @@ +/* SPDX-License-Identifier: Apache-2.0 */ + +#include "BLI_bitmap.h" +#include "testing/testing.h" + +namespace blender::tests { + +TEST(bitmap, empty_is_all_unset) +{ + BLI_BITMAP_DECLARE(bitmap, 10); + for (int i = 0; i < 10; ++i) { + EXPECT_FALSE(BLI_BITMAP_TEST_BOOL(bitmap, i)); + } +} + +TEST(bitmap, find_first_unset_empty) +{ + BLI_BITMAP_DECLARE(bitmap, 10); + EXPECT_EQ(0, BLI_bitmap_find_first_unset(bitmap, 10)); +} + +TEST(bitmap, find_first_unset_full) +{ + BLI_BITMAP_DECLARE(bitmap, 10); + BLI_bitmap_flip_all(bitmap, 10); + EXPECT_EQ(-1, BLI_bitmap_find_first_unset(bitmap, 10)); +} + +TEST(bitmap, find_first_unset_middle) +{ + BLI_BITMAP_DECLARE(bitmap, 100); + BLI_bitmap_flip_all(bitmap, 100); + /* Turn some bits off */ + BLI_BITMAP_DISABLE(bitmap, 53); + BLI_BITMAP_DISABLE(bitmap, 81); + BLI_BITMAP_DISABLE(bitmap, 85); + BLI_BITMAP_DISABLE(bitmap, 86); + + /* Find lowest unset bit, and set it. */ + EXPECT_EQ(53, BLI_bitmap_find_first_unset(bitmap, 100)); + BLI_BITMAP_ENABLE(bitmap, 53); + /* Now should find the next lowest bit. */ + EXPECT_EQ(81, BLI_bitmap_find_first_unset(bitmap, 100)); +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_index_range_test.cc b/source/blender/blenlib/tests/BLI_index_range_test.cc index 10f6784cd44..f5b994d409a 100644 --- a/source/blender/blenlib/tests/BLI_index_range_test.cc +++ b/source/blender/blenlib/tests/BLI_index_range_test.cc @@ -105,6 +105,12 @@ TEST(index_range, OneAfterEnd) EXPECT_EQ(range.one_after_last(), 8); } +TEST(index_range, OneBeforeStart) +{ + IndexRange range = IndexRange(5, 3); + EXPECT_EQ(range.one_before_start(), 4); +} + TEST(index_range, Start) { IndexRange range = IndexRange(6, 2); diff --git a/source/blender/blenlib/tests/BLI_length_parameterize_test.cc b/source/blender/blenlib/tests/BLI_length_parameterize_test.cc index b63e3a0ec86..3b41a7aed0c 100644 --- a/source/blender/blenlib/tests/BLI_length_parameterize_test.cc +++ b/source/blender/blenlib/tests/BLI_length_parameterize_test.cc @@ -10,7 +10,7 @@ namespace blender::length_parameterize::tests { template<typename T> Array<float> calculate_lengths(const Span<T> values, const bool cyclic) { - Array<float> lengths(lengths_num(values.size(), cyclic)); + Array<float> lengths(segments_num(values.size(), cyclic)); accumulate_lengths<T>(values, cyclic, lengths); return lengths; } @@ -30,9 +30,9 @@ TEST(length_parameterize, FloatSimple) Array<int> indices(4); Array<float> factors(4); - create_uniform_samples(lengths, false, indices, factors); + sample_uniform(lengths, true, indices, factors); Array<float> results(4); - linear_interpolation<float>(values, indices, factors, results); + interpolate<float>(values, indices, factors, results); Array<float> expected({ 0.0f, 1.33333f, @@ -52,9 +52,9 @@ TEST(length_parameterize, Float) Array<int> indices(20); Array<float> factors(20); - create_uniform_samples(lengths, false, indices, factors); + sample_uniform(lengths, true, indices, factors); Array<float> results(20); - linear_interpolation<float>(values, indices, factors, results); + interpolate<float>(values, indices, factors, results); Array<float> expected({ 1.0f, 1.47368f, 1.94737f, 2.42105f, 2.89474f, 3.36842f, 3.84211f, 4.31579f, 4.78947f, 5.26316f, 5.73684f, 6.21053f, 6.68421f, 7.1579f, @@ -73,9 +73,9 @@ TEST(length_parameterize, Float2) Array<int> indices(12); Array<float> factors(12); - create_uniform_samples(lengths, false, indices, factors); + sample_uniform(lengths, true, indices, factors); Array<float2> results(12); - linear_interpolation<float2>(values, indices, factors, results); + interpolate<float2>(values, indices, factors, results); Array<float2> expected({ {0.0f, 0.0f}, {0.272727f, 0.0f}, @@ -103,9 +103,9 @@ TEST(length_parameterize, Float2Cyclic) Array<int> indices(12); Array<float> factors(12); - create_uniform_samples(lengths, true, indices, factors); + sample_uniform(lengths, false, indices, factors); Array<float2> results(12); - linear_interpolation<float2>(values, indices, factors, results); + interpolate<float2>(values, indices, factors, results); Array<float2> expected({ {0.0f, 0.0f}, {0.333333f, 0.0f}, @@ -133,9 +133,9 @@ TEST(length_parameterize, LineMany) Array<int> indices(5007); Array<float> factors(5007); - create_uniform_samples(lengths, false, indices, factors); + sample_uniform(lengths, true, indices, factors); Array<float> results(5007); - linear_interpolation<float>(values, indices, factors, results); + interpolate<float>(values, indices, factors, results); Array<float> expected({ 1.9962f, 1.9964f, 1.9966f, 1.9968f, 1.997f, 1.9972f, 1.9974f, 1.9976f, 1.9978f, 1.998f, 1.9982f, 1.9984f, 1.9986f, 1.9988f, 1.999f, 1.9992f, 1.9994f, 1.9996f, 1.9998f, 2.0f, @@ -152,9 +152,9 @@ TEST(length_parameterize, CyclicMany) Array<int> indices(5007); Array<float> factors(5007); - create_uniform_samples(lengths, true, indices, factors); + sample_uniform(lengths, false, indices, factors); Array<float2> results(5007); - linear_interpolation<float2>(values, indices, factors, results); + interpolate<float2>(values, indices, factors, results); Array<float2> expected({ {0, 0.0159776}, {0, 0.0151787}, {0, 0.0143797}, {0, 0.013581}, {0, 0.0127821}, {0, 0.0119832}, {0, 0.0111842}, {0, 0.0103855}, {0, 0.00958657}, {0, 0.00878763}, @@ -176,9 +176,9 @@ TEST(length_parameterize, InterpolateColor) Array<int> indices(10); Array<float> factors(10); - create_uniform_samples(lengths, true, indices, factors); + sample_uniform(lengths, false, indices, factors); Array<ColorGeometry4f> results(10); - linear_interpolation<ColorGeometry4f>(colors, indices, factors, results); + interpolate<ColorGeometry4f>(colors, indices, factors, results); Array<ColorGeometry4f> expected({ {0, 0, 0, 1}, {0.4, 0, 0, 1}, @@ -207,10 +207,9 @@ TEST(length_parameterize, ArbitraryFloatSimple) Array<float> sample_lengths{{0.5f, 1.5f, 2.0f, 4.0f}}; Array<int> indices(4); Array<float> factors(4); - create_samples_from_sorted_lengths(lengths, sample_lengths, false, indices, factors); + sample_at_lengths(lengths, sample_lengths, indices, factors); Array<float> results(4); - linear_interpolation<float>(values, indices, factors, results); - results.as_span().print_as_lines("results"); + interpolate<float>(values, indices, factors, results); Array<float> expected({ 0.5f, 1.5f, @@ -231,10 +230,9 @@ TEST(length_parameterize, ArbitraryFloat2) {0.5f, 1.5f, 2.0f, 2.0f, 2.1f, 2.5f, 3.5f, 3.6f, 3.8f, 3.85f, 3.90f, 4.0f}}; Array<int> indices(12); Array<float> factors(12); - create_samples_from_sorted_lengths(lengths, sample_lengths, true, indices, factors); + sample_at_lengths(lengths, sample_lengths, indices, factors); Array<float2> results(12); - linear_interpolation<float2>(values, indices, factors, results); - results.as_span().print_as_lines("results"); + interpolate<float2>(values, indices, factors, results); Array<float2> expected({ {0.5f, 0.0f}, {1.0f, 0.5f}, diff --git a/source/blender/blenlib/tests/BLI_virtual_array_test.cc b/source/blender/blenlib/tests/BLI_virtual_array_test.cc index 90c7f1078a5..14f5480f751 100644 --- a/source/blender/blenlib/tests/BLI_virtual_array_test.cc +++ b/source/blender/blenlib/tests/BLI_virtual_array_test.cc @@ -1,6 +1,7 @@ /* SPDX-License-Identifier: Apache-2.0 */ #include "BLI_array.hh" +#include "BLI_generic_virtual_array.hh" #include "BLI_strict_flags.h" #include "BLI_vector.hh" #include "BLI_vector_set.hh" @@ -109,7 +110,7 @@ TEST(virtual_array, AsSpan) { auto func = [](int64_t index) { return (int)(10 * index); }; VArray<int> func_varray = VArray<int>::ForFunc(10, func); - VArray_Span span_varray{func_varray}; + VArraySpan span_varray{func_varray}; EXPECT_EQ(span_varray.size(), 10); Span<int> span = span_varray; EXPECT_EQ(span.size(), 10); @@ -222,4 +223,36 @@ TEST(virtual_array, MaterializeCompressed) } } +TEST(virtual_array, EmptySpanWrapper) +{ + { + VArray<int> varray; + VArraySpan<int> span1 = varray; + EXPECT_TRUE(span1.is_empty()); + VArraySpan<int> span2 = std::move(span1); + EXPECT_TRUE(span2.is_empty()); + } + { + VMutableArray<int> varray; + MutableVArraySpan<int> span1 = varray; + EXPECT_TRUE(span1.is_empty()); + MutableVArraySpan<int> span2 = std::move(span1); + EXPECT_TRUE(span2.is_empty()); + } + { + GVArray varray; + GVArraySpan span1 = varray; + EXPECT_TRUE(span1.is_empty()); + GVArraySpan span2 = std::move(span1); + EXPECT_TRUE(span2.is_empty()); + } + { + GVMutableArray varray; + GMutableVArraySpan span1 = varray; + EXPECT_TRUE(span1.is_empty()); + GMutableVArraySpan span2 = std::move(span1); + EXPECT_TRUE(span2.is_empty()); + } +} + } // namespace blender::tests |