Blender V5.3
BLI_bounds.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#pragma once
6
10
11#include <optional>
12
13#include "BLI_bounds_types.hh"
14#include "BLI_index_mask.hh"
15#include "BLI_math_matrix.hh"
16#include "BLI_math_vector.hh"
17#include "BLI_span.hh"
18#include "BLI_task.hh"
19#include "BLI_virtual_array.hh"
20
21#include "PRF_profile.hh"
22
23namespace blender {
25namespace bounds {
26
27template<typename T> [[nodiscard]] inline Bounds<T> merge(const Bounds<T> &a, const Bounds<T> &b)
28{
29 return {math::min(a.min, b.min), math::max(a.max, b.max)};
30}
31
32template<typename T>
33[[nodiscard]] inline std::optional<Bounds<T>> merge(const std::optional<Bounds<T>> &a,
34 const std::optional<Bounds<T>> &b)
36 if (a.has_value() && b.has_value()) {
37 return merge(*a, *b);
38 }
39 if (a.has_value()) {
40 return a;
41 }
42 if (b.has_value()) {
43 return b;
44 }
45 return std::nullopt;
47
48template<typename T>
49[[nodiscard]] inline std::optional<Bounds<T>> merge(const std::optional<Bounds<T>> &a,
50 const Bounds<T> &b)
51{
52 return merge(a, std::optional<Bounds<T>>(b));
54
55template<typename T>
56[[nodiscard]] inline std::optional<Bounds<T>> min_max(const std::optional<Bounds<T>> &a,
57 const T &b)
59 if (a.has_value()) {
60 return merge(*a, {b, b});
61 }
62 return Bounds<T>{b, b};
63}
65namespace detail {
66
70 * the point before it.
71 */
72template<typename T> [[nodiscard]] inline Bounds<T> min_max_lanes(const Span<T> values)
73{
74 constexpr int64_t lanes = 4;
75 const int64_t size = values.size();
76 const int64_t full = size & ~(lanes - 1);
77
78 T lo[lanes];
79 T hi[lanes];
80 for (int64_t lane = 0; lane < lanes; lane++) {
81 lo[lane] = hi[lane] = values[0];
82 }
83 for (int64_t i = 0; i < full; i += lanes) {
84 for (int64_t lane = 0; lane < lanes; lane++) {
85 const T &value = values[i + lane];
86 lo[lane] = math::min(lo[lane], value);
87 hi[lane] = math::max(hi[lane], value);
88 }
89 }
90
91 Bounds<T> result{lo[0], hi[0]};
92 for (int64_t lane = 1; lane < lanes; lane++) {
93 result.min = math::min(result.min, lo[lane]);
94 result.max = math::max(result.max, hi[lane]);
95 }
96 for (int64_t i = full; i < size; i++) {
97 result.min = math::min(result.min, values[i]);
98 result.max = math::max(result.max, values[i]);
99 }
100 return result;
101}
102
104template<typename T, typename RadiusT>
105[[nodiscard]] inline Bounds<T> min_max_lanes_with_radii(const Span<T> values,
106 const Span<RadiusT> radii)
107{
108 constexpr int64_t lanes = 4;
109 const int64_t size = values.size();
110 const int64_t full = size & ~(lanes - 1);
111
112 T lo[lanes];
113 T hi[lanes];
114 for (int64_t lane = 0; lane < lanes; lane++) {
115 lo[lane] = values[0] - radii[0];
116 hi[lane] = values[0] + radii[0];
117 }
118 for (int64_t i = 0; i < full; i += lanes) {
119 for (int64_t lane = 0; lane < lanes; lane++) {
120 lo[lane] = math::min(lo[lane], values[i + lane] - radii[i + lane]);
121 hi[lane] = math::max(hi[lane], values[i + lane] + radii[i + lane]);
122 }
123 }
124
125 Bounds<T> result{lo[0], hi[0]};
126 for (int64_t lane = 1; lane < lanes; lane++) {
127 result.min = math::min(result.min, lo[lane]);
128 result.max = math::max(result.max, hi[lane]);
129 }
130 for (int64_t i = full; i < size; i++) {
131 result.min = math::min(result.min, values[i] - radii[i]);
132 result.max = math::max(result.max, values[i] + radii[i]);
133 }
134 return result;
135}
136
137} // namespace detail
138
142template<typename T> [[nodiscard]] inline std::optional<Bounds<T>> min_max(const Span<T> values)
143{
144 if (values.is_empty()) {
145 return std::nullopt;
146 }
148 const Bounds<T> init{values.first(), values.first()};
150 values.index_range(),
151 1024,
152 init,
153 [&](const IndexRange range, const Bounds<T> &init) {
154 return merge(init, detail::min_max_lanes(values.slice(range)));
155 },
156 [](const Bounds<T> &a, const Bounds<T> &b) { return merge(a, b); });
157}
158
159template<typename T>
160[[nodiscard]] inline std::optional<Bounds<T>> min_max(const IndexMask &mask, const Span<T> values)
161{
162 if (values.is_empty() || mask.is_empty()) {
163 return std::nullopt;
164 }
165 if (mask.size() == values.size()) {
166 /* To avoid mask slice/lookup. */
167 return min_max(values);
168 }
170 const Bounds<T> init{values[mask.first()], values[mask.first()]};
172 mask.index_range().drop_front(1),
173 1024,
174 init,
175 [&](const IndexRange range, const Bounds<T> &init) {
176 Bounds<T> result = init;
177 mask.slice(range).foreach_index_optimized<int64_t>(
178 [&](const int i) { math::min_max(values[i], result.min, result.max); });
179 return result;
180 },
181 [](const Bounds<T> &a, const Bounds<T> &b) { return merge(a, b); });
182}
183
188template<typename T, typename RadiusT>
189[[nodiscard]] inline std::optional<Bounds<T>> min_max_with_radii(const Span<T> values,
190 const Span<RadiusT> radii)
191{
192 BLI_assert(values.size() == radii.size());
193 if (values.is_empty()) {
194 return std::nullopt;
195 }
196 PRF_scope_with_name("bounds::min_max_with_radii", ProfileCategory::Default);
197 const Bounds<T> init{values.first(), values.first()};
199 values.index_range(),
200 1024,
201 init,
202 [&](const IndexRange range, const Bounds<T> &init) {
203 return merge(init,
204 detail::min_max_lanes_with_radii(values.slice(range), radii.slice(range)));
205 },
206 [](const Bounds<T> &a, const Bounds<T> &b) { return merge(a, b); });
207}
208
212template<typename T> [[nodiscard]] inline std::optional<Bounds<T>> min_max(const VArray<T> &varray)
213{
214 if (varray.is_empty()) {
215 return std::nullopt;
216 }
217 PRF_scope_with_name("bounds::min_max_with_radii", ProfileCategory::Default);
218 const CommonVArrayInfo info = varray.common_info();
220 Bounds<T> result = Bounds<T>(varray.first());
221 return result;
222 }
224 const Span<T> span(static_cast<const T *>(info.data), varray.size());
225 return min_max<T>(span);
226 }
227 const Bounds<T> init{varray.first(), varray.first()};
229 varray.index_range(),
230 1024,
231 init,
232 [&](const IndexRange range, const Bounds<T> &init) {
233 Bounds<T> result = init;
234 for (const int i : range) {
235 math::min_max(varray[i], result.min, result.max);
236 }
237 return result;
238 },
239 [](const Bounds<T> &a, const Bounds<T> &b) { return merge(a, b); });
240}
241
246template<typename T>
247[[nodiscard]] inline std::optional<Bounds<T>> intersect(const Bounds<T> &a, const Bounds<T> &b)
248{
249 const Bounds<T> result{math::max(a.min, b.min), math::min(a.max, b.max)};
250 if (result.is_empty()) {
251 return std::nullopt;
252 }
253 return result;
254}
255template<typename T>
256[[nodiscard]] inline std::optional<Bounds<T>> intersect(const std::optional<Bounds<T>> &a,
257 const std::optional<Bounds<T>> &b)
258{
259 if (!a.has_value() || !b.has_value()) {
260 return std::nullopt;
261 }
262 return intersect(*a, *b);
263}
264
268template<typename T> inline std::optional<T> max(const VArray<T> &values)
269{
270 if (values.is_empty()) {
271 return std::nullopt;
272 }
274 if (const std::optional<T> value = values.get_if_single()) {
275 return value;
276 }
277 const VArraySpan<int> values_span = values;
279 values_span.index_range(),
280 2048,
281 std::numeric_limits<T>::min(),
282 [&](const IndexRange range, int current_max) {
283 for (const int value : values_span.slice(range)) {
284 current_max = std::max(current_max, value);
285 }
286 return current_max;
287 },
288 [](const int a, const int b) { return std::max(a, b); });
289}
290
310template<typename T>
311inline std::array<VecBase<T, 3>, 8> corners(const Bounds<VecBase<T, 3>> &bounds)
312{
313 return {
314 VecBase<T, 3>{bounds.min[0], bounds.min[1], bounds.min[2]},
315 VecBase<T, 3>{bounds.min[0], bounds.min[1], bounds.max[2]},
316 VecBase<T, 3>{bounds.min[0], bounds.max[1], bounds.max[2]},
317 VecBase<T, 3>{bounds.min[0], bounds.max[1], bounds.min[2]},
318 VecBase<T, 3>{bounds.max[0], bounds.min[1], bounds.min[2]},
319 VecBase<T, 3>{bounds.max[0], bounds.min[1], bounds.max[2]},
320 VecBase<T, 3>{bounds.max[0], bounds.max[1], bounds.max[2]},
321 VecBase<T, 3>{bounds.max[0], bounds.max[1], bounds.min[2]},
322 };
323}
324
342template<typename T>
343inline std::array<VecBase<T, 2>, 4> corners(const Bounds<VecBase<T, 2>> &bounds)
344{
345 return {
346 bounds.min,
347 VecBase<T, 2>{bounds.max.x, bounds.min.y},
348 bounds.max,
349 VecBase<T, 2>{bounds.min.x, bounds.max.y},
350 };
351}
352
363template<typename T, int D>
366{
367 std::array<VecBase<T, 3>, 8> points = corners(bounds);
368 for (VecBase<T, 3> &p : points) {
369 p = math::transform_point(matrix, p);
370 }
371 return {math::min(Span(points)), math::max(Span(points))};
372}
373
379template<typename T, int D>
382{
383 std::array<VecBase<T, 2>, 4> points = corners(bounds);
384 for (VecBase<T, 2> &p : points) {
385 p = math::transform_point(matrix, p);
386 }
387 return {math::min(Span(points)), math::max(Span(points))};
388}
389
390namespace detail {
391
392template<typename T, int Size>
393[[nodiscard]] inline bool any_less_than_v(const VecBase<T, Size> &a, const VecBase<T, Size> &b)
394{
395 for (int i = 0; i < Size; i++) {
396 if (a[i] < b[i]) {
397 return true;
398 }
399 }
400 return false;
401}
402
403template<typename T, int Size>
404[[nodiscard]] inline bool any_greater_than_v(const VecBase<T, Size> &a, const VecBase<T, Size> &b)
405{
406 for (int i = 0; i < Size; i++) {
407 if (a[i] > b[i]) {
408 return true;
409 }
410 }
411 return false;
412}
413
414template<typename T, int Size>
415[[nodiscard]] inline bool any_less_or_equal_than_v(const VecBase<T, Size> &a,
416 const VecBase<T, Size> &b)
417{
418 for (int i = 0; i < Size; i++) {
419 if (a[i] <= b[i]) {
420 return true;
421 }
422 }
423 return false;
424}
425
426template<typename T> [[nodiscard]] inline bool any_less_than(const T &a, const T &b)
427{
428 if constexpr (std::is_integral_v<T> || std::is_floating_point_v<T>) {
429 return a < b;
430 }
431 else {
432 return any_less_than_v(a, b);
433 }
434}
435
436template<typename T> [[nodiscard]] inline bool any_greater_than(const T &a, const T &b)
437{
438 if constexpr (std::is_integral_v<T> || std::is_floating_point_v<T>) {
439 return a > b;
440 }
441 else {
442 return any_greater_than_v(a, b);
443 }
444}
445
446template<typename T> [[nodiscard]] inline bool any_less_or_equal_than(const T &a, const T &b)
447{
448 if constexpr (std::is_integral_v<T> || std::is_floating_point_v<T>) {
449 return a <= b;
450 }
451 else {
452 return any_less_or_equal_than_v(a, b);
453 }
454}
455
456template<typename T> [[nodiscard]] inline Bounds<T> segment_bounds(const T &start, const T &end)
457{
458 Bounds<T> bounds{start, start};
459 math::min_max(end, bounds.min, bounds.max);
460 return bounds;
461}
462
464template<typename T>
465[[nodiscard]] inline bool rational_greater_than(const T &p1, const T &q1, const T &p2, const T &q2)
466{
467 BLI_assert(q1 > T(0) && q2 > T(0));
468 return p1 * q2 > p2 * q1;
469}
470
471template<typename T>
472[[nodiscard]] inline bool rational_less_than(const T &p1, const T &q1, const T &p2, const T &q2)
473{
474 BLI_assert(q1 > T(0) && q2 > T(0));
475 return p1 * q2 < p2 * q1;
476}
477
479template<typename T, int Size>
480[[nodiscard]] inline bool segment_enter_exit_bounds(const Bounds<VecBase<T, Size>> &bounds,
481 const VecBase<T, Size> &start,
482 const VecBase<T, Size> &end)
483{
484 T p_enter = T(0);
485 T q_enter = T(1);
486 T p_exit = T(1);
487 T q_exit = T(1);
488
489 /* t_enter = p_enter / q_enter */
490 /* t_exit = p_exit / q_exit */
491 for (int i = 0; i < Size; i++) {
492 const T di = end[i] - start[i];
493 if (di == T(0)) {
494 /* Segment is parallel to i-th axis. */
495 if (start[i] < bounds.min[i] || start[i] > bounds.max[i]) {
496 return false;
497 }
498 continue;
499 }
500
501 /* Note: We flip the sign here to ensure the denominator is positive. This doesn't change the
502 * value of the rational number. */
503 const T p_low = (di > T(0)) ? bounds.min[i] - start[i] : -(bounds.max[i] - start[i]);
504 const T p_high = (di > T(0)) ? bounds.max[i] - start[i] : -(bounds.min[i] - start[i]);
505 const T di_abs = (di > T(0)) ? di : -di;
506
507 /* t_low = p_low / di_abs */
508 /* t_high = p_high / di_abs */
509 if (rational_greater_than(p_low, di_abs, p_enter, q_enter)) {
510 /* t_low > t_enter */
511 p_enter = p_low;
512 q_enter = di_abs;
513 }
514 if (rational_less_than(p_high, di_abs, p_exit, q_exit)) {
515 /* t_high < t_exit */
516 p_exit = p_high;
517 q_exit = di_abs;
518 }
519
520 if (rational_greater_than(p_enter, q_enter, p_exit, q_exit)) {
521 /* t_enter > t_exit */
522 return false;
523 }
524 }
525
526 /* t_exit >= 0 and t_enter <= 1 */
527 return p_exit >= T(0) && p_enter <= q_enter;
528}
529
530} // namespace detail
531} // namespace bounds
532
533template<typename T> inline bool Bounds<T>::is_empty() const
534{
536}
537
538template<typename T> inline T Bounds<T>::center() const
539{
540 return math::midpoint(this->min, this->max);
541}
542
543template<typename T> inline T Bounds<T>::size() const
544{
545 return math::abs(max - min);
546}
547
548template<typename T> inline void Bounds<T>::translate(const T &offset)
549{
550 this->min += offset;
551 this->max += offset;
552}
553
554template<typename T> inline void Bounds<T>::scale_from_center(const T &scale)
555{
556 const T center = this->center();
557 const T new_half_size = this->size() / T(2) * scale;
558 this->min = center - new_half_size;
559 this->max = center + new_half_size;
560}
561
562template<typename T> inline void Bounds<T>::resize(const T &new_size)
563{
564 this->min = this->center() - (new_size / T(2));
565 this->max = this->min + new_size;
566}
567
568template<typename T> inline void Bounds<T>::recenter(const T &new_center)
569{
570 const T offset = new_center - this->center();
571 this->translate(offset);
572}
573
574template<typename T>
575template<typename PaddingT>
576inline void Bounds<T>::pad(const PaddingT &padding)
577{
578 this->min = this->min - padding;
579 this->max = this->max + padding;
580}
581
582template<typename T> inline bool Bounds<T>::contains(const T &point) const
583{
584 if (bounds::detail::any_less_than(point, this->min)) {
585 return false;
586 }
587 if (bounds::detail::any_greater_than(point, this->max)) {
588 return false;
589 }
590 return true;
591}
592
593template<typename T> inline bool Bounds<T>::intersects(const Bounds<T> &other) const
594{
595 if (bounds::intersect(*this, other)) {
596 return true;
597 }
598 return false;
599}
600
601template<typename T> inline bool Bounds<T>::intersects_segment(const T &start, const T &end) const
602{
603 /* Check end points first to properly handle degenerate case where the segment is a point. */
604 if (this->contains(start) || this->contains(end)) {
605 return true;
606 }
607 if constexpr (std::is_integral_v<T> || std::is_floating_point_v<T>) {
608 return this->intersects(bounds::detail::segment_bounds(start, end));
609 }
610 else {
611 /* Check if the segment is entering and exiting the bounds. */
612 return bounds::detail::segment_enter_exit_bounds(*this, start, end);
613 }
614}
615
616} // namespace blender
#define PRF_scope_with_name(ui_name, category)
constexpr Span()=default
constexpr const T & first() const
Definition BLI_span.hh:319
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr bool is_empty() const
Definition BLI_span.hh:264
std::optional< T > get_if_single() const
IndexRange index_range() const
CommonVArrayInfo common_info() const
constexpr IndexRange index_range() const
float3x3 scale(float3x3 mat, float2 scale)
OrientationBounds merge(const OrientationBounds &cone_a, const OrientationBounds &cone_b)
#define T
Bounds< T > segment_bounds(const T &start, const T &end)
bool any_greater_than_v(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
bool any_less_or_equal_than_v(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
bool segment_enter_exit_bounds(const Bounds< VecBase< T, Size > > &bounds, const VecBase< T, Size > &start, const VecBase< T, Size > &end)
bool any_less_than_v(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
bool any_less_than(const T &a, const T &b)
Bounds< T > min_max_lanes(const Span< T > values)
Definition BLI_bounds.hh:72
bool rational_greater_than(const T &p1, const T &q1, const T &p2, const T &q2)
Bounds< T > min_max_lanes_with_radii(const Span< T > values, const Span< RadiusT > radii)
bool any_less_or_equal_than(const T &a, const T &b)
bool rational_less_than(const T &p1, const T &q1, const T &p2, const T &q2)
bool any_greater_than(const T &a, const T &b)
Bounds< VecBase< T, 3 > > transform_bounds(const MatBase< T, D, D > &matrix, const Bounds< VecBase< T, 3 > > &bounds)
Bounds< T > merge(const Bounds< T > &a, const Bounds< T > &b)
Definition BLI_bounds.hh:27
std::array< VecBase< T, 3 >, 8 > corners(const Bounds< VecBase< T, 3 > > &bounds)
std::optional< Bounds< T > > min_max_with_radii(const Span< T > values, const Span< RadiusT > radii)
std::optional< Bounds< T > > min_max(const std::optional< Bounds< T > > &a, const T &b)
Definition BLI_bounds.hh:56
std::optional< T > max(const VArray< T > &values)
std::optional< Bounds< T > > intersect(const Bounds< T > &a, const Bounds< T > &b)
int size(const AssetLibraryReference *library_reference)
T min(const T &a, const T &b)
T midpoint(const T &a, const T &b)
void min_max(const T &value, T &min, T &max)
T max(const T &a, const T &b)
T abs(const T &a)
VecBase< T, 3 > transform_point(const CartesianBasis &basis, const VecBase< T, 3 > &v)
Value parallel_reduce(IndexRange range, int64_t grain_size, const Value &identity, const Function &function, const Reduction &reduction)
Definition BLI_task.hh:127
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
uint padding(uint offset, uint alignment)
void scale_from_center(const T &scale)
bool contains(const T &point) const
void recenter(const T &new_center)
void resize(const T &new_size)
void pad(const PaddingT &padding)
void translate(const T &offset)
blender::VecBase< float, 3 > size() const
bool intersects_segment(const T &start, const T &end) const
T center() const
bool is_empty() const
bool intersects(const Bounds< T > &other) const