43#define USE_CONVEX_CROSS_PRODUCT_ENSURE
56#define USE_ANGLE_ITER_ORDER_ASSERT
110 return (((p1[0] - p0[0]) * (p2[1] - p0[1])) - ((p2[0] - p0[0]) * (p1[1] - p0[1])));
117 const int r_points[],
118 int2 &r_points_range)
120#ifdef USE_CONVEX_CROSS_PRODUCT_ENSURE
121 int bot = r_points_range[0];
122 int top = r_points_range[1];
123 while (top - bot >= 2) {
131 points[r_points[top - 1]],
133 points[r_points[bot]],
135 points[r_points[top]]) >= 0.0f) [[unlikely]]
144 points[r_points[top]],
146 points[r_points[bot + 1]],
148 points[r_points[bot]]) >= 0.0f) [[unlikely]]
156 r_points_range[0] = bot;
157 r_points_range[1] = top;
172#ifdef USE_CONVEX_CROSS_PRODUCT_ENSURE
175 (
is_left(points[r_points[top - 1]], points[
index], points[r_points[top]]) >= 0.0f))
184 r_points[++top] =
index;
201 const int minmin = 0;
202 const int maxmax = points_num - 1;
209 float xmin = points[0][0];
210 for (i = 1; i <= maxmax; i++) {
211 if (points[i][0] != xmin) {
217 if (minmax == maxmax) {
219 if (points[minmax][1] != points[minmin][1]) {
229 xmax = points[maxmax][0];
230 for (i = maxmax - 1; i >= 0; i--) {
231 if (points[i][0] != xmax) {
242 while (++i <= maxmin) {
244 if ((i < maxmin) && (
is_left(points[minmin], points[maxmin], points[i]) >= 0.0f)) {
250 if (
is_left(points[r_points[top - 1]], points[r_points[top]], points[i]) > 0.0f) {
259 if (maxmax != maxmin) {
265 while (--i >= minmax) {
267 if ((i > minmax) && (
is_left(points[maxmax], points[minmax], points[i]) >= 0.0f)) {
273 if (
is_left(points[r_points[top - 1]], points[r_points[top]], points[i]) > 0.0f) {
279 if (points[i][0] == points[r_points[0]][0] && points[i][1] == points[r_points[0]][1]) {
286 if (minmax != minmin && r_points[0] != minmin) {
305 int2 points_range = {0, top};
312 const int points_num = int(points.
size());
314 if (points_num < 2) {
315 if (points_num == 1) {
323 for (
int i = 0; i < points_num; i++) {
327 std::sort(points_map, points_map + points_num, [points](
const int &a_index,
const int &b_index) {
328 const float *a = points[a_index];
329 const float *
b = points[b_index];
346 for (
int i = 0; i < points_num; i++) {
347 copy_v2_v2(points_sort[i], points[points_map[i]]);
353 for (
int i = points_hull_range[0]; i <= points_hull_range[1]; i++) {
354 r_points[i] = points_map[r_points[i]];
357 MEM_delete(points_map);
358 MEM_delete(points_sort);
360 const int points_hull_num = (points_hull_range[1] - points_hull_range[0]) + 1;
362 return points_hull_num;
371#if defined(USE_BRUTE_FORCE_ASSERT) && !defined(NDEBUG)
372static float2 convexhull_aabb_fit_hull_2d_brute_force(
const float (*points_hull)[2],
375 float area_best = std::numeric_limits<float>::max();
376 float2 sincos_best = {0.0f, 1.0f};
378 for (
int i = 0; i < points_hull_num; i++) {
379 const int i_next = (i + 1) % points_hull_num;
381 float dvec_length = 0.0f;
383 float2(points_hull[i_next]) -
float2(points_hull[i]), dvec_length);
384 if (dvec_length == 0.0f) [[unlikely]] {
389 {std::numeric_limits<float>::max(), -std::numeric_limits<float>::max()},
390 {std::numeric_limits<float>::max(), -std::numeric_limits<float>::max()},
394 for (
int j = 0; j < points_hull_num; j++) {
406 if (area_test > area_best) {
411 if (area_test < area_best) {
412 area_best = area_test;
547 prev_p = &iter->
next;
558 const int i_curr = hstep.
index;
561 float dir_length = 0.0f;
563 hstep.
index = i_next;
564 if (dir_length != 0.0f) [[likely]] {
578 const int points_hull_num)
580 const int points_hull_num_minus_1 = points_hull_num - 1;
585 for (
int axis = 0; axis < 2; axis++) {
586 range[axis][0] = points_hull[0][axis];
587 range[axis][1] = points_hull[0][axis];
593 for (
int i = 1; i < points_hull_num; i++) {
594 const float *p = points_hull[i];
595 for (
int axis = 0; axis < 2; axis++) {
596 if (range[axis][0] < p[axis]) {
597 range[axis][0] = p[axis];
600 if (range[axis][1] > p[axis]) {
601 range[axis][1] = p[axis];
612 for (
int axis = 0; axis < 2; axis++) {
613 for (
int i = 0; i < 2; i++) {
614 const int i_orig = hiter.
axis[axis][i].
index;
615 int i_curr = i_orig, i_prev;
619 while ((i_prev = (i_curr + points_hull_num_minus_1) % points_hull_num) != i_orig) {
620 float dir_length = 0.0f;
622 float2(points_hull[i_curr]) -
float2(points_hull[i_prev]), dir_length);
623 if (dir_length != 0.0f) [[likely]] {
625 if (
math::abs(sincos_test[axis]) > 0.5f) {
629 if (sincos_test_canonical[0] != 1.0f) [[likely]] {
648 for (
int axis = 0; axis < 2; axis++) {
649 for (
int i = 0; i < 2; i++) {
660#ifdef USE_ANGLE_ITER_ORDER_ASSERT
664 const int i_a = angle_prev.
index;
670 return dir_a[0] * dir_b[1] - dir_a[1] * dir_b[0];
677#ifdef USE_ANGLE_ITER_ORDER_ASSERT
686#ifdef USE_ANGLE_ITER_ORDER_ASSERT
715template<
int Axis,
int AxisSign>
717 const int points_hull_num,
727 const int index_init = *index_p;
728 int index_best = index_init;
731 float value_best = value_init;
733 for (
int count = 1; count < points_hull_num; count++) {
734 const int index_test = (index_init + count) % points_hull_num;
737 if ((AxisSign == -1) ? (value_test > value_best) : (value_test < value_best)) {
740 value_best = value_test;
741 index_best = index_test;
744 *index_p = index_best;
750 float area_best = std::numeric_limits<float>::max();
751 float2 sincos_best = {0.0f, 1.0f};
752 int index_best = std::numeric_limits<int>::max();
768 points_hull, points_hull_num, hstep->angle.sincos_canonical, &bounds_index[0].
min),
770 points_hull, points_hull_num, hstep->angle.sincos_canonical, &bounds_index[0].
max)},
772 points_hull, points_hull_num, hstep->angle.sincos_canonical, &bounds_index[1].
min),
774 points_hull, points_hull_num, hstep->angle.sincos_canonical, &bounds_index[1].
max)},
777 const float area_test = (bounds_test[0].
max - bounds_test[0].
min) *
778 (bounds_test[1].
max - bounds_test[1].
min);
780 if (area_test < area_best ||
783 ((area_test == area_best) && (hstep->angle.index < index_best)))
785 area_best = area_test;
786 sincos_best = hstep->angle.sincos;
787 index_best = hstep->angle.index;
793#if defined(USE_BRUTE_FORCE_ASSERT) && !defined(NDEBUG)
796 const float2 sincos_test = convexhull_aabb_fit_hull_2d_brute_force(points_hull,
798 if (sincos_best != sincos_test) {
809 const int points_num = int(points.
size());
817 if (points_hull_num > 1) {
820 for (
int j = 0; j < points_hull_num; j++) {
821 copy_v2_v2(points_hull[j], points[index_map[j]]);
825 MEM_delete(points_hull);
828 MEM_delete(index_map);
Read Blender memory allocation and freeing.
__forceinline const float4 insert(const float4 &a, const float b)
#define UNUSED_VARS_NDEBUG(...)
constexpr int64_t size() const
ccl_device_inline void sincos(const float3 x, ccl_private float3 *sine, ccl_private float3 *cosine)
QuaternionBase< T > normalize_and_get_length(const QuaternionBase< T > &q, T &out_length)
T min(const T &a, const T &b)
T max(const T &a, const T &b)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static float convexhull_2d_angle_iter_cross_for_assert(const HullAngleIter &hiter, const AngleCanonical &angle_prev)
static float2 convexhull_aabb_fit_hull_2d(const float(*points_hull)[2], int points_hull_num)
static bool convexhull_2d_angle_iter_step_on_axis(const HullAngleIter &hiter, HullAngleStep &hstep)
static float is_left(const float2 &p0, const float2 &p1, const float2 &p2)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
float2 BLI_convexhull_aabb_fit_points_2d_as_sincos(Span< float2 > points)
MINLINE void copy_v2_v2(float r[2], const float a[2])
static void convexhull_2d_stack_finalize(const float2 *points, const int r_points[], int2 &r_points_range)
static void hull_angle_insert_ordered(HullAngleIter &hiter, HullAngleStep *insert)
static float sincos_rotate_cw_x(const float2 &sincos, const float2 &p)
static float2 sincos_canonical(const float2 &sincos)
int BLI_convexhull_2d(Span< float2 > points, int r_points[])
VecBase< int32_t, 2 > int2
VecBase< float, 2 > float2
static int convexhull_2d_sorted_impl(const float2 *points, const int points_num, int r_points[])
static HullAngleIter convexhull_2d_angle_iter_init(const float(*points_hull)[2], const int points_hull_num)
static int hull_angle_canonical_cmp(const AngleCanonical &a, const AngleCanonical &b)
static float sincos_rotate_cw_y(const float2 &sincos, const float2 &p)
float BLI_convexhull_aabb_fit_points_2d(Span< float2 > points)
static int2 convexhull_2d_sorted(const float2 *points, const int points_num, int r_points[])
static void convexhull_2d_stack_push(const float2 *points, int r_points[], int &top, int index)
static float convexhull_2d_compute_extent_on_axis(const float(*points_hull)[2], const int points_hull_num, const float2 &sincos, int *index_p)
static void convexhull_2d_angle_iter_step(HullAngleIter &hiter)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
HullAngleStep * axis_ordered
const float(* points_hull)[2]