Differential D16161 Diff 57421 source/blender/blenkernel/BKE_curves_utils.hh

Changeset View

Standalone View

source/blender/blenkernel/BKE_curves_utils.hh

Show First 20 Lines • Show All 61 Lines • ▼ Show 20 Lines	struct CurvePoint : public CurveSegment {
/**		/**
* Compare if 'this' point comes before 'other'. Loop segment for cyclical curves counts		* Compare if 'this' point comes before 'other'. Loop segment for cyclical curves counts
* as the first (least) segment.		* as the first (least) segment.
*/		*/
inline bool operator<(const CurvePoint &other) const;		inline bool operator<(const CurvePoint &other) const;
};		};

/**		/**
* Cyclical index range. Iterates the interval [start, end).		* Cyclical index range. Allows iteration over a plain 'IndexRange' interval on form [start, end)
		* while also supporting treating the underlying array as a cyclic array where the last index is
		* followed by the first nidex in the 'cyclical' range. The cyclical index range can then be
		* considered a combination of the intervals separated by the last index of the underlying array,
		* namely [start, range_size) and [0, end) where start/end is the indices iterated between and
		* range_size is the size of the underlying array. To cycle the underlying array the interval
		* [0, range_size) can be iterated over an arbitrary amount of times inbetween.
*/		*/
class IndexRangeCyclic {		class IndexRangeCyclic {
/* Index to the start and end of the iterated range.		/* Index to the start and end of the iterated range.
*/		*/
int64_t start_ = 0;		int start_ = 0;
int64_t end_ = 0;		int end_ = 0;
/* Index for the start and end of the entire iterable range which contains the iterated range		/* Size of the underlying iterable range.
* (e.g. the point range for an individual spline/curve within the entire Curves point domain).
*/		*/
int64_t range_start_ = 0;		int range_size_ = 0;
int64_t range_end_ = 0;
/* Number of times the range end is passed when the range is iterated.		/* Number of times the range end is passed when the range is iterated.
*/		*/
int64_t cycles_ = 0;		int cycles_ = 0;

constexpr IndexRangeCyclic(int64_t begin,
int64_t end,
int64_t iterable_range_start,
int64_t iterable_range_end,
int64_t cycles)
: start_(begin),
end_(end),
range_start_(iterable_range_start),
range_end_(iterable_range_end),
cycles_(cycles)
{
}

public:		public:
constexpr IndexRangeCyclic() = default;		constexpr IndexRangeCyclic() = default;
~IndexRangeCyclic() = default;		~IndexRangeCyclic() = default;

constexpr IndexRangeCyclic(int64_t start, int64_t end, IndexRange iterable_range, int64_t cycles)		constexpr IndexRangeCyclic(const int start,
: start_(start),		const int end,
end_(end),		const int iterable_range_size,
range_start_(iterable_range.first()),		const int cycles)
range_end_(iterable_range.one_after_last()),		: start_(start), end_(end), range_size_(iterable_range_size), cycles_(cycles)
cycles_(cycles)
{		{
}		}

/**		/**
* Create an iterator over the cyclical interval [start_index, end_index).		* Create an iterator over the cyclical interval [start_index, end_index).
*/		*/
constexpr IndexRangeCyclic(int64_t start, int64_t end, IndexRange iterable_range)		constexpr IndexRangeCyclic(const int start, const int end, const int iterable_range_size)
: start_(start),		: start_(start),
end_(end == iterable_range.one_after_last() ? iterable_range.first() : end),		end_(end == iterable_range_size ? 0 : end),
range_start_(iterable_range.first()),		range_size_(iterable_range_size),
range_end_(iterable_range.one_after_last()),
cycles_(end < start)		cycles_(end < start)
{		{
}		}

/**		/**
* Increment the range by adding the given number of indices to the beginning of the range.		* Create a cyclical iterator of the specified size.
		*
		* \param start_point: Point on the curve that define the starting point of the interval.
		* \param iterator_size: Number of elements to iterate (size of the iterated cyclical range).
		* \param iterable_range_size: Size of the underlying range (superset to the cyclical range).
*/		*/
constexpr IndexRangeCyclic push_forward(int n)		static IndexRangeCyclic get_range_from_size(const int start_index,
		const int iterator_size,
		const int iterable_range_size)
		{
		BLI_assert(start_index >= 0);
		BLI_assert(iterator_size >= 0);
		BLI_assert(iterable_range_size > 0);
		const int num_until_loop = iterable_range_size - start_index;
		if (iterator_size < num_until_loop) {
		return IndexRangeCyclic(start_index, start_index + iterator_size, iterable_range_size, 0);
		}

		const int num_remaining = iterator_size - num_until_loop;
		const int num_full_cycles = num_remaining /
		iterable_range_size; /* Integer division (rounded down). */
		const int end_index = num_remaining - num_full_cycles * iterable_range_size;
		return IndexRangeCyclic(start_index, end_index, iterable_range_size, num_full_cycles + 1);
		}

		/**
		* Create a cyclical iterator for all control points within the interval [start_point, end_point]
		* including any control point at the start or end point.
		*
		* \param start_point: Point on the curve that define the starting point of the interval.
		* \param end_point: Point on the curve that define the end point of the interval (included).
		* \param iterable_range_size: Size of the underlying range (superset to the cyclical range).
		*/
		static IndexRangeCyclic get_range_between_endpoints(const CurvePoint start_point,
		const CurvePoint end_point,
		const int iterable_range_size)
		{
		BLI_assert(iterable_range_size > 0);
		const int start_index = start_point.parameter == 0.0 ? start_point.index :
		start_point.next_index;
		int end_index = end_point.parameter == 0.0 ? end_point.index : end_point.next_index;
		int cycles;

		if (end_point.is_controlpoint()) {
		BLI_assert(end_index < iterable_range_size);
		++end_index;
		if (end_index == iterable_range_size) {
		end_index = 0;
		}
		/* end_point < start_point but parameter is irrelevant (end_point is controlpoint), and loop
		* when equal due to increment. */
		cycles = end_index <= start_index;
		}
		else {
		cycles = end_point < start_point \|\| end_index < start_index;
		}
		return IndexRangeCyclic(start_index, end_index, iterable_range_size, cycles);
		}

		/**
		* Next index within the iterable range.
		*/
		template<typename IndexT> constexpr IndexT next_index(const IndexT index, const bool cyclic)
		{
		static_assert((is_same_any_v<IndexT, int, int>), "Expected signed integer type.");
		const IndexT next_index = index + 1;
		if (next_index == this->size_range()) {
		return cyclic ? 0 : index;
		}
		return next_index;
		}

		/**
		* Previous index within the iterable range.
		*/
		template<typename IndexT> constexpr IndexT previous_index(const IndexT index, const bool cyclic)
		{
		static_assert((is_same_any_v<IndexT, int, int64_t>), "Expected signed integer type.");
		const IndexT prev_index = index - 1;
		if (prev_index < 0) {
		return cyclic ? this->size_range() - 1 : 0;
		}
		return prev_index;
		}

		/**
		* Increment the range by adding `n` loops to the range. This invokes undefined behavior when n
		* is negative.
		*/
		constexpr IndexRangeCyclic push_loop(const int n = 1) const
		{
		return {this->start_, this->end_, this->range_size_, this->cycles_ + n};
		}

		/**
		* Increment the range by adding the given number of indices to the beginning of the iterated
		* range. This invokes undefined behavior when n is negative.
		*/
		constexpr IndexRangeCyclic push_front(const int n = 1) const
{		{
BLI_assert(n >= 0);		BLI_assert(n >= 0);
int64_t nstart = start_ - n;		int new_start = this->start_ - n;
int64_t cycles = cycles_;		int num_cycles = this->cycles_;
if (nstart < range_start_) {		if (new_start < 0) {
		const int new_cycles = n / this->size_range(); /* Integer division (floor) */
		const int remainder = new_start + this->size_range() * new_cycles;
		const bool underflow = remainder < 0;
		new_start = remainder + (underflow ? this->size_range() : 0);
		num_cycles += new_cycles + int(underflow);
		}
		BLI_assert(num_cycles >= 0);
		BLI_assert(num_cycles > 0 \|\|
		(new_start <= this->end_ \|\| (this->end_ == 0 && new_start < this->size_range())));
		return {new_start, this->end_, this->range_size_, num_cycles};
		}

cycles += (int64_t)(n / (range_end_ - range_start_)) + (end_ < nstart) - (end_ < start_);		/**
		* Increment the range by adding the given number of indices to the end of the iterated range.
		* This invokes undefined behavior when n is negative.
		*/
		constexpr IndexRangeCyclic push_back(const int n = 1) const
		{
		BLI_assert(n >= 0);
		int new_end = this->end_ + n;
		int num_cycles = this->cycles_;
		if (this->size_range() <= new_end) {
		const int new_cycles = n / this->size_range(); /* Integer division (floor) */
		const int remainder = new_end - this->size_range() * new_cycles;
		const bool overflow = remainder >= this->size_range();
		new_end = remainder - (overflow ? this->size_range() : 0);
		num_cycles += new_cycles + int(overflow);
}		}
return {nstart, end_, range_start_, range_end_, cycles};		BLI_assert(num_cycles >= 0);
		BLI_assert(num_cycles > 0 \|\| (this->start_ <= new_end \|\| new_end == 0));
		return {this->start_, new_end, this->range_size_, num_cycles};
}		}

/**		/**
* Increment the range by adding the given number of indices to the end of the range.		* Returns a new range with n indices removed from the beginning of the range.
		* This invokes undefined behavior.
*/		*/
constexpr IndexRangeCyclic push_backward(int n)		constexpr IndexRangeCyclic drop_front(const int n = 1) const
{		{
BLI_assert(n >= 0);		BLI_assert(n >= 0);
int64_t new_end = end_ + n;		int new_start = this->start_ + n;
int64_t cycles = cycles_;		int num_cycles = this->cycles_;
if (range_end_ <= new_end) {		if (this->size_range() <= new_start) {
cycles += (int64_t)(n / (range_end_ - range_start_)) + (new_end < start_) - (end_ < start_);		const int dropped_cycles = n / this->size_range(); /* Integer division (floor) */
		const int remainder = new_start - this->size_range() * dropped_cycles;
		const bool overflow = remainder >= this->size_range();
		new_start = remainder - (overflow ? this->size_range() : 0);
		num_cycles -= dropped_cycles + int(overflow);
		}
		BLI_assert(num_cycles >= 0);
		BLI_assert(num_cycles > 0 \|\|
		(new_start <= this->end_ \|\| (this->end_ == 0 && new_start < this->size_range())));
		return {new_start, this->end_, this->range_size_, num_cycles};
}		}
return {start_, new_end, range_start_, range_end_, cycles};
		/**
		* Returns a new range with n indices removed from the end of the range.
		* This invokes undefined behavior when n is negative or n is larger then the underlying range.
		*/
		constexpr IndexRangeCyclic drop_back(const int n = 1) const
		{
		BLI_assert(n >= 0);
		int new_end = this->end_ - n;
		int num_cycles = this->cycles_;
		if (0 >= new_end) {
		const int dropped_cycles = n / this->size_range(); /* Integer division (floor) */
		const int remainder = new_end + this->size_range() * dropped_cycles;
		const bool underflow = remainder < 0;
		new_end = remainder + (underflow ? this->size_range() : 0);
		num_cycles -= dropped_cycles + int(underflow);
		}
		BLI_assert(num_cycles >= 0);
		BLI_assert(num_cycles > 0 \|\| (this->start_ <= new_end \|\| new_end == 0));
		return {this->start_, new_end, this->range_size_, num_cycles};
}		}

/**		/**
* Get the index range for the curve buffer.		* Get the index range for the curve buffer.
*/		*/
constexpr IndexRange curve_range() const		constexpr IndexRange curve_range() const
{		{
return IndexRange(range_start_, total_size());		return IndexRange(0, this->size_range());
}		}

/**		/**
* Range between the first element up to the end of the range.		* Range between the first element up to the end of the range.
*/		*/
constexpr IndexRange range_before_loop() const		constexpr IndexRange range_before_loop() const
{		{
return IndexRange(start_, size_before_loop());		return IndexRange(this->start_, this->size_before_loop());
}		}

/**		/**
* Range between the first element in the iterable range up to the last element in the range.		* Range between the first element in the iterable range up to the last element in the range.
*/		*/
constexpr IndexRange range_after_loop() const		constexpr IndexRange range_after_loop() const
{		{
return IndexRange(range_start_, size_after_loop());		return IndexRange(0, this->size_after_loop());
}		}

/**		/**
* Size of the entire iterable range.		* Number of elements in the underlying iterable range.
*/		*/
constexpr int64_t total_size() const		constexpr int size_range() const
{		{
return range_end_ - range_start_;		return this->range_size_;
}		}

/**		/**
* Number of elements between the first element in the range up to the last element in the curve.		* Number of elements between the first element in the range up to the last element in the curve.
*/		*/
constexpr int64_t size_before_loop() const		constexpr int size_before_loop() const
{		{
return range_end_ - start_;		return this->range_size_ - this->start_;
}		}

/**		/**
* Number of elements between the first element in the iterable range up to the last element in		* Number of elements between the first element in the iterable range up to the last element in
* the range.		* the range.
*/		*/
constexpr int64_t size_after_loop() const		constexpr int size_after_loop() const
{		{
return end_ - range_start_;		return this->end_;
}		}

/**		/**
* Get number of elements iterated by the cyclical index range.		* Number of elements iterated by the cyclical index range.
*/		*/
constexpr int64_t size() const		constexpr int size() const
{		{
if (cycles_ > 0) {		if (this->cycles_ > 0) {
return size_before_loop() + end_ + (cycles_ - 1) * (range_end_ - range_start_);		return this->size_before_loop() + this->end_ + (this->cycles_ - 1) * this->range_size_;
}		}
else {		else {
return end_ - start_;		return int(this->end_ - this->start_);
}		}
}		}

/**		/**
* Return the number of times the iterator will cycle before ending.		* Return the number of times the iterator will cycle before ending.
*/		*/
constexpr int64_t cycles() const		constexpr int cycles() const
		{
		return this->cycles_;
		}

		constexpr int first() const
		{
		return this->start_;
		}

		constexpr int last() const
{		{
return cycles_;		BLI_assert(this->size() > 0);
		return int(this->end_ - 1);
}		}

constexpr int64_t first() const		constexpr int one_after_last() const
{		{
return start_;		return this->end_;
}		}

constexpr int64_t one_after_last() const		constexpr bool operator==(const IndexRangeCyclic &other) const
{		{
return end_;		return this->start_ == other.start_ && this->end_ == other.end_ &&
		this->cycles_ == other.cycles_ && this->range_size_ == other.range_size_;
		}
		constexpr bool operator!=(const IndexRangeCyclic &other) const
		{
		return !this->operator==(other);
}		}

struct CyclicIterator; /* Forward declaration */		struct CyclicIterator; /* Forward declaration */

constexpr CyclicIterator begin() const		constexpr CyclicIterator begin() const
{		{
return CyclicIterator(range_start_, range_end_, start_, 0);		return CyclicIterator(this->range_size_, this->start_, 0);
}		}

constexpr CyclicIterator end() const		constexpr CyclicIterator end() const
{		{
return CyclicIterator(range_start_, range_end_, end_, cycles_);		return CyclicIterator(this->range_size_, this->end_, this->cycles_);
}		}

struct CyclicIterator {		struct CyclicIterator {
int64_t index_, begin_, end_, cycles_;		int index_, range_end_, cycles_;

constexpr CyclicIterator(int64_t range_begin, int64_t range_end, int64_t index, int64_t cycles)		constexpr CyclicIterator(const int range_end, const int index, const int cycles)
: index_(index), begin_(range_begin), end_(range_end), cycles_(cycles)		: index_(index), range_end_(range_end), cycles_(cycles)
{		{
BLI_assert(range_begin <= index && index <= range_end);		BLI_assert(0 <= index && index <= range_end);
}		}

constexpr CyclicIterator(const CyclicIterator &copy)		constexpr CyclicIterator(const CyclicIterator &copy)
: index_(copy.index_), begin_(copy.begin_), end_(copy.end_), cycles_(copy.cycles_)		: index_(copy.index_), range_end_(copy.range_end_), cycles_(copy.cycles_)
{		{
}		}
~CyclicIterator() = default;		~CyclicIterator() = default;

constexpr CyclicIterator &operator=(const CyclicIterator &copy)		constexpr CyclicIterator &operator=(const CyclicIterator &copy)
{		{
if (this == &copy) {		if (this == &copy) {
return *this;		return *this;
}		}
index_ = copy.index_;		this->index_ = copy.index_;
begin_ = copy.begin_;		this->range_end_ = copy.range_end_;
end_ = copy.end_;		this->cycles_ = copy.cycles_;
cycles_ = copy.cycles_;
return *this;		return *this;
}		}
constexpr CyclicIterator &operator++()		constexpr CyclicIterator &operator++()
{		{
index_++;		this->index_++;
if (index_ == end_) {		if (this->index_ == this->range_end_) {
index_ = begin_;		this->index_ = 0;
cycles_++;		this->cycles_++;
}		}
return *this;		return *this;
}		}

void increment(int64_t n)		void increment(const int n)
{		{
for (int i = 0; i < n; i++) {		for (int i = 0; i < n; i++) {
++*this;		++*this;
}		}
}		}

constexpr const int64_t &operator*() const		constexpr const int &operator*() const
{		{
return index_;		return this->index_;
}		}

constexpr bool operator==(const CyclicIterator &other) const		constexpr bool operator==(const CyclicIterator &other) const
{		{
return index_ == other.index_ && cycles_ == other.cycles_;		return this->index_ == other.index_ && this->cycles_ == other.cycles_;
}		}
constexpr bool operator!=(const CyclicIterator &other) const		constexpr bool operator!=(const CyclicIterator &other) const
{		{
return !this->operator==(other);		return !this->operator==(other);
}		}
};		};
};		};

▲ Show 20 Lines • Show All 78 Lines • ▼ Show 20 Lines
void accumulate_counts_to_offsets(MutableSpan<int> counts_to_offsets, int start_offset = 0);		void accumulate_counts_to_offsets(MutableSpan<int> counts_to_offsets, int start_offset = 0);

IndexMask indices_for_type(const VArray<int8_t> &types,		IndexMask indices_for_type(const VArray<int8_t> &types,
const std::array<int, CURVE_TYPES_NUM> &type_counts,		const std::array<int, CURVE_TYPES_NUM> &type_counts,
const CurveType type,		const CurveType type,
const IndexMask selection,		const IndexMask selection,
Vector<int64_t> &r_indices);		Vector<int64_t> &r_indices);

		void indices_for_each_type(const VArray<int8_t> &types,
		const std::array<int, CURVE_TYPES_NUM> &counts,
		const IndexMask selection,
		std::array<IndexMask, CURVE_TYPES_NUM> &r_type_masks,
		std::array<Vector<int64_t>, CURVE_TYPES_NUM> &r_type_indices);

void foreach_curve_by_type(const VArray<int8_t> &types,		void foreach_curve_by_type(const VArray<int8_t> &types,
const std::array<int, CURVE_TYPES_NUM> &type_counts,		const std::array<int, CURVE_TYPES_NUM> &type_counts,
IndexMask selection,		IndexMask selection,
FunctionRef<void(IndexMask)> catmull_rom_fn,		FunctionRef<void(IndexMask)> catmull_rom_fn,
FunctionRef<void(IndexMask)> poly_fn,		FunctionRef<void(IndexMask)> poly_fn,
FunctionRef<void(IndexMask)> bezier_fn,		FunctionRef<void(IndexMask)> bezier_fn,
FunctionRef<void(IndexMask)> nurbs_fn);		FunctionRef<void(IndexMask)> nurbs_fn);

		/**
		* Same as 'by_type' but index mask for each curve type is pre-computed.
		*/
		void foreach_curve_by_type_mask(const std::array<IndexMask, CURVE_TYPES_NUM> &curve_type_mask,
		HooglyBooglyUnsubmitted Done Inline Actions I think `std::array` like is used for the type counts would be a slight improvement in this area, so it doesn't decay to raw pointers. HooglyBoogly: I think `std::array` like is used for the type counts would be a slight improvement in this…
		FunctionRef<void(IndexMask)> catmull_rom_fn,
		FunctionRef<void(IndexMask)> poly_fn,
		FunctionRef<void(IndexMask)> bezier_fn,
		FunctionRef<void(IndexMask)> nurbs_fn);

/** \} */		/** \} */

/* -------------------------------------------------------------------- */		/* -------------------------------------------------------------------- */
/** \name #CurvePoint Inline Methods		/** \name #CurvePoint Inline Methods
* \{ */		* \{ */

inline bool CurvePoint::is_controlpoint() const		inline bool CurvePoint::is_controlpoint() const
{		{
Show All 29 Lines