Blender V5.3
convexhull_2d.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 * SPDX-FileCopyrightText: 2001 softSurfer (http://www.softsurfer.com)
3 *
4 * SPDX-License-Identifier: GPL-2.0-or-later */
5
9
10#include <algorithm>
11#include <cstdlib>
12#include <cstring>
13
14#include "MEM_guardedalloc.h"
15
16#include "BLI_bounds_types.hh"
17#include "BLI_convexhull_2d.hh"
18#include "BLI_math_vector.hh"
19#include "BLI_math_vector_c.hh"
21#include "BLI_utildefines.hh"
22
23#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
24
25namespace blender {
26
43#define USE_CONVEX_CROSS_PRODUCT_ENSURE
44
49// #define USE_BRUTE_FORCE_ASSERT
50
56#define USE_ANGLE_ITER_ORDER_ASSERT
57
58/* -------------------------------------------------------------------- */
61
62static float sincos_rotate_cw_x(const float2 &sincos, const float2 &p)
63{
64 return (sincos[0] * p[0]) + (sincos[1] * p[1]);
65}
66
67static float sincos_rotate_cw_y(const float2 &sincos, const float2 &p)
68{
69 return (sincos[1] * p[0]) - (sincos[0] * p[1]);
70}
71
73
74/* -------------------------------------------------------------------- */
79
80/* Copyright 2001, softSurfer (http://www.softsurfer.com)
81 * This code may be freely used and modified for any purpose
82 * providing that this copyright notice is included with it.
83 * SoftSurfer makes no warranty for this code, and cannot be held
84 * liable for any real or imagined damage resulting from its use.
85 * Users of this code must verify correctness for their application.
86 * http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm
87 *
88 * NOTE(@ideasman42): additional checks added to ensure the resulting hull is convex,
89 * see the: #USE_CONVEX_CROSS_PRODUCT_ENSURE define.
90 */
91
108static float is_left(const float2 &p0, const float2 &p1, const float2 &p2)
109{
110 return (((p1[0] - p0[0]) * (p2[1] - p0[1])) - ((p2[0] - p0[0]) * (p1[1] - p0[1])));
111}
112
116static void convexhull_2d_stack_finalize(const float2 *points,
117 const int r_points[],
118 int2 &r_points_range)
119{
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) {
124 /* While the order of checking the beginning/end doesn't matter,
125 * prefer dropping values off the end of `r_points`
126 * since it doesn't require re-ordering. */
127
128 /* See #is_left note on argument order. */
129 if (is_left(
130 /* Second last point. */
131 points[r_points[top - 1]],
132 /* First point. */
133 points[r_points[bot]],
134 /* Last point (candidate "ear" to remove). */
135 points[r_points[top]]) >= 0.0f) [[unlikely]]
136 {
137 /* Concave: drop from the end: `r_points[top]`. */
138 top--;
139 continue;
140 }
141 /* See #is_left note on argument order. */
142 if (is_left(
143 /* Last point. */
144 points[r_points[top]],
145 /* Second point. */
146 points[r_points[bot + 1]],
147 /* First point (candidate "ear" to remove). */
148 points[r_points[bot]]) >= 0.0f) [[unlikely]]
149 {
150 /* Concave: drop from the front: `r_points[bot]`. */
151 bot++;
152 continue;
153 }
154 break;
155 }
156 r_points_range[0] = bot;
157 r_points_range[1] = top;
158#else
159 UNUSED_VARS(points, r_points, r_points_range);
160#endif /* !USE_CONVEX_CROSS_PRODUCT_ENSURE */
161}
162
167static inline void convexhull_2d_stack_push(const float2 *points,
168 int r_points[],
169 int &top,
170 int index)
171{
172#ifdef USE_CONVEX_CROSS_PRODUCT_ENSURE
173 while ((top > 0) &&
174 /* See #is_left note on argument order. */
175 (is_left(points[r_points[top - 1]], points[index], points[r_points[top]]) >= 0.0f))
176 [[unlikely]]
177 {
178 top--;
179 }
180#else
181 UNUSED_VARS(points);
182#endif /* !USE_CONVEX_CROSS_PRODUCT_ENSURE */
183
184 r_points[++top] = index;
185}
186
191static int convexhull_2d_sorted_impl(const float2 *points, const int points_num, int r_points[])
192{
193 BLI_assert(points_num >= 2); /* Doesn't handle trivial cases. */
194 /* The output array `r_points[]` will be used as the stack. */
195 int bot = 0;
196 /* Indices for bottom and top of the stack. */
197 int top = -1;
198 /* Array scan index. */
199 int i;
200
201 const int minmin = 0;
202 const int maxmax = points_num - 1;
203 int minmax;
204 int maxmin;
205
206 float xmax;
207
208 /* Get the indices of points with min X-coord and min|max Y-coord. */
209 float xmin = points[0][0];
210 for (i = 1; i <= maxmax; i++) {
211 if (points[i][0] != xmin) {
212 break;
213 }
214 }
215
216 minmax = i - 1;
217 if (minmax == maxmax) { /* Degenerate case: all x-coords == X-min. */
218 convexhull_2d_stack_push(points, r_points, top, minmin);
219 if (points[minmax][1] != points[minmin][1]) {
220 /* A nontrivial segment. */
221 convexhull_2d_stack_push(points, r_points, top, minmax);
222 }
223 BLI_assert(top + 1 <= points_num);
224 return top;
225 }
226
227 /* Get the indices of points with max X-coord and min|max Y-coord. */
228
229 xmax = points[maxmax][0];
230 for (i = maxmax - 1; i >= 0; i--) {
231 if (points[i][0] != xmax) {
232 break;
233 }
234 }
235 maxmin = i + 1;
236
237 /* Compute the lower hull on the stack `r_points`. */
238 BLI_assert(top < 2);
239 convexhull_2d_stack_push(points, r_points, top, minmin);
240
241 i = minmax;
242 while (++i <= maxmin) {
243 /* The lower line joins `points[minmin]` with `points[maxmin]`. */
244 if ((i < maxmin) && (is_left(points[minmin], points[maxmin], points[i]) >= 0.0f)) {
245 continue; /* Ignore `points[i]` above or on the lower line. */
246 }
247
248 while (top > 0) { /* There are at least 2 points on the stack. */
249 /* Test if `points[i]` is left of the line at the stack top. */
250 if (is_left(points[r_points[top - 1]], points[r_points[top]], points[i]) > 0.0f) {
251 break; /* `points[i]` is a new hull vertex. */
252 }
253 top--; /* Pop top point off stack. */
254 }
255 convexhull_2d_stack_push(points, r_points, top, i);
256 }
257
258 /* Next, compute the upper hull on the stack `r_points` above the bottom hull. */
259 if (maxmax != maxmin) { /* If distinct `xmax` points. */
260 convexhull_2d_stack_push(points, r_points, top, maxmax);
261 }
262
263 bot = top; /* The bottom point of the upper hull stack. */
264 i = maxmin;
265 while (--i >= minmax) {
266 /* The upper line joins `points[maxmax]` with `points[minmax]`. */
267 if ((i > minmax) && (is_left(points[maxmax], points[minmax], points[i]) >= 0.0f)) {
268 continue; /* Ignore points[i] below or on the upper line. */
269 }
270
271 while (top > bot) { /* At least 2 points on the upper stack. */
272 /* Test if `points[i]` is left of the line at the stack top. */
273 if (is_left(points[r_points[top - 1]], points[r_points[top]], points[i]) > 0.0f) {
274 break; /* `points[i]` is a new hull vertex. */
275 }
276 top--; /* Pop top point off stack. */
277 }
278
279 if (points[i][0] == points[r_points[0]][0] && points[i][1] == points[r_points[0]][1]) {
280 BLI_assert(top + 1 <= points_num);
281 return top; /* Special case (mgomes). */
282 }
283 convexhull_2d_stack_push(points, r_points, top, i);
284 }
285
286 if (minmax != minmin && r_points[0] != minmin) {
287 /* Push joining endpoint onto stack. */
288 convexhull_2d_stack_push(points, r_points, top, minmin);
289 }
290
291 BLI_assert(top + 1 <= points_num);
292 return top;
293}
294
302static int2 convexhull_2d_sorted(const float2 *points, const int points_num, int r_points[])
303{
304 const int top = convexhull_2d_sorted_impl(points, points_num, r_points);
305 int2 points_range = {0, top};
306 convexhull_2d_stack_finalize(points, r_points, points_range);
307 return points_range;
308}
309
310int BLI_convexhull_2d(Span<float2> points, int r_points[])
311{
312 const int points_num = int(points.size());
313 BLI_assert(points_num >= 0);
314 if (points_num < 2) {
315 if (points_num == 1) {
316 r_points[0] = 0;
317 }
318 return points_num;
319 }
320 int *points_map = MEM_new_array_uninitialized<int>(size_t(points_num), __func__);
321 float2 *points_sort = MEM_new_array_uninitialized<float2>(size_t(points_num), __func__);
322
323 for (int i = 0; i < points_num; i++) {
324 points_map[i] = i;
325 }
326
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];
330 if (a[1] > b[1]) {
331 return false;
332 }
333 if (a[1] < b[1]) {
334 return true;
335 }
336
337 if (a[0] > b[0]) {
338 return false;
339 }
340 if (a[0] < b[0]) {
341 return true;
342 }
343 return false;
344 });
345
346 for (int i = 0; i < points_num; i++) {
347 copy_v2_v2(points_sort[i], points[points_map[i]]);
348 }
349
350 const int2 points_hull_range = convexhull_2d_sorted(points_sort, points_num, r_points);
351
352 /* Map back to the unsorted index values. */
353 for (int i = points_hull_range[0]; i <= points_hull_range[1]; i++) {
354 r_points[i] = points_map[r_points[i]];
355 }
356
357 MEM_delete(points_map);
358 MEM_delete(points_sort);
359
360 const int points_hull_num = (points_hull_range[1] - points_hull_range[0]) + 1;
361 BLI_assert(points_hull_num <= points_num);
362 return points_hull_num;
363}
364
366
367/* -------------------------------------------------------------------- */
370
371#if defined(USE_BRUTE_FORCE_ASSERT) && !defined(NDEBUG)
372static float2 convexhull_aabb_fit_hull_2d_brute_force(const float (*points_hull)[2],
373 int points_hull_num)
374{
375 float area_best = std::numeric_limits<float>::max();
376 float2 sincos_best = {0.0f, 1.0f}; /* Track the best angle as a unit vector, delaying `atan2`. */
377
378 for (int i = 0; i < points_hull_num; i++) {
379 const int i_next = (i + 1) % points_hull_num;
380 /* 2D rotation matrix. */
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]] {
385 continue;
386 }
387
388 Bounds<float> bounds[2] = {
389 {std::numeric_limits<float>::max(), -std::numeric_limits<float>::max()},
390 {std::numeric_limits<float>::max(), -std::numeric_limits<float>::max()},
391 };
392 float area_test;
393
394 for (int j = 0; j < points_hull_num; j++) {
395 const float2 tvec = {
396 sincos_rotate_cw_x(sincos, points_hull[j]),
397 sincos_rotate_cw_y(sincos, points_hull[j]),
398 };
399
400 bounds[0].min = math::min(bounds[0].min, tvec[0]);
401 bounds[0].max = math::max(bounds[0].max, tvec[0]);
402 bounds[1].min = math::min(bounds[1].min, tvec[1]);
403 bounds[1].max = math::max(bounds[1].max, tvec[1]);
404
405 area_test = (bounds[0].max - bounds[0].min) * (bounds[1].max - bounds[1].min);
406 if (area_test > area_best) {
407 break;
408 }
409 }
410
411 if (area_test < area_best) {
412 area_best = area_test;
413 sincos_best = sincos;
414 }
415 }
416
417 return sincos_best;
418}
419#endif
420
422
423/* -------------------------------------------------------------------- */
429
435{
436
437 /* Normalize doesn't ensure a `sin` / `cos` of 1.0/-1.0 ensures the other value is zero.
438 * Without the check for both 0.0 and 1.0, iteration may not be ordered. */
440 if (sincos[0] < 0.0f) {
441 if (sincos[1] < 0.0f) {
442 result[0] = -sincos[0];
443 result[1] = -sincos[1];
444 }
445 else if ((sincos[0] == -1.0f) && (sincos[1] == 0.0f)) {
446 result[0] = -sincos[0];
447 result[1] = sincos[1];
448 }
449 else {
450 result[0] = sincos[1];
451 result[1] = -sincos[0];
452 }
453 }
454 else {
455 if (sincos[1] < 0.0f) {
456 result[0] = -sincos[1];
457 result[1] = sincos[0];
458 }
459 else if ((sincos[0] == 0.0f) && (sincos[1] == 1.0f)) {
460 result[0] = sincos[1];
461 result[1] = sincos[0];
462 }
463 else {
464 result = sincos;
465 }
466 }
467
468 /* The range is [1.0, 0.0], it will approach but never return [0.0, 1.0],
469 * as the canonical version of this value gets flipped to [1.0, 0.0]. */
470 BLI_assert(result[0] > 0.0f);
471 BLI_assert(result[1] >= 0.0f);
472 return result;
473}
474
486
488{
489 if (a.sincos_canonical[0] < b.sincos_canonical[0]) {
490 return -1;
491 }
492 if (a.sincos_canonical[0] > b.sincos_canonical[0]) {
493 return 1;
494 }
495 /* Flipped intentionally. */
496 if (a.sincos_canonical[1] > b.sincos_canonical[1]) {
497 return -1;
498 }
499 if (a.sincos_canonical[1] < b.sincos_canonical[1]) {
500 return 1;
501 }
502
503 /* Flipped intentionally. */
504 if (a.index > b.index) {
505 return -1;
506 }
507 if (a.index < b.index) {
508 return 1;
509 }
510 return 0;
511}
512
528
541
543{
544 HullAngleStep **prev_p = &hiter.axis_ordered;
545 HullAngleStep *iter = hiter.axis_ordered;
546 while (iter && hull_angle_canonical_cmp(iter->angle, insert->angle) > 0) {
547 prev_p = &iter->next;
548 iter = iter->next;
549 }
550 *prev_p = insert;
551 insert->next = iter;
552}
553
555{
556 BLI_assert(hstep.index != -1);
557 while (hstep.index != hstep.index_max) {
558 const int i_curr = hstep.index;
559 const int i_next = (hstep.index + 1) % hiter.points_hull_num;
560 const float2 dir = float2(hiter.points_hull[i_next]) - float2(hiter.points_hull[i_curr]);
561 float dir_length = 0.0f;
562 const float2 sincos_test = math::normalize_and_get_length(dir, dir_length);
563 hstep.index = i_next;
564 if (dir_length != 0.0f) [[likely]] {
565 hstep.angle.sincos = sincos_test;
566 hstep.angle.sincos_canonical = sincos_canonical(sincos_test);
567 hstep.angle.index = i_curr;
568 return true;
569 }
570 }
571
572 /* Reached the end, signal this axis shouldn't be stepped over. */
573 hstep.index = -1;
574 return false;
575}
576
577static HullAngleIter convexhull_2d_angle_iter_init(const float (*points_hull)[2],
578 const int points_hull_num)
579{
580 const int points_hull_num_minus_1 = points_hull_num - 1;
581 HullAngleIter hiter = {};
582 /* Aligned with `hiter.axis`. */
583 float range[2][2];
584 /* Initialize min-max range from the first point. */
585 for (int axis = 0; axis < 2; axis++) {
586 range[axis][0] = points_hull[0][axis];
587 range[axis][1] = points_hull[0][axis];
588 }
589 /* Expand from all other points.
590 *
591 * NOTE: Don't attempt to pick either side when there are multiple equal points.
592 * Walking backwards while checking `sincos_canonical` handles that. */
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];
598 hiter.axis[axis][0].index = i;
599 }
600 if (range[axis][1] > p[axis]) {
601 range[axis][1] = p[axis];
602 hiter.axis[axis][1].index = i;
603 }
604 }
605 }
606
607 /* Step backwards, compute the actual `sincos_canonical` because it's possible
608 * an edge which is not *exactly* axis aligned normalizes to a value which is.
609 * Instead of attempting to guess when this might happen,
610 * simply calculate the value and walk backwards for a long as the canonical angle
611 * has a `sin` of 1.0 (which must always come first). */
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;
616 /* Prevent an eternal loop (incredibly unlikely).
617 * In virtually all cases this will step back once
618 * (in the case of an axis-aligned edge) or not at all. */
619 while ((i_prev = (i_curr + points_hull_num_minus_1) % points_hull_num) != i_orig) {
620 float dir_length = 0.0f;
621 const float2 sincos_test = math::normalize_and_get_length(
622 float2(points_hull[i_curr]) - float2(points_hull[i_prev]), dir_length);
623 if (dir_length != 0.0f) [[likely]] {
624 /* Account for 90 degree corners that may also have an axis-aligned canonical angle. */
625 if (math::abs(sincos_test[axis]) > 0.5f) {
626 break;
627 }
628 const float2 sincos_test_canonical = sincos_canonical(sincos_test);
629 if (sincos_test_canonical[0] != 1.0f) [[likely]] {
630 break;
631 }
632 }
633 i_curr = i_prev;
634 hiter.axis[axis][i].index = i_curr;
635 }
636 }
637 }
638
639 /* Setup counter-clockwise limits. */
640 hiter.axis[0][0].index_max = hiter.axis[1][0].index; /* West to south. */
641 hiter.axis[1][0].index_max = hiter.axis[0][1].index; /* South to east. */
642 hiter.axis[0][1].index_max = hiter.axis[1][1].index; /* East to north. */
643 hiter.axis[1][1].index_max = hiter.axis[0][0].index; /* North to west. */
644
645 hiter.points_hull = points_hull;
646 hiter.points_hull_num = points_hull_num;
647
648 for (int axis = 0; axis < 2; axis++) {
649 for (int i = 0; i < 2; i++) {
650 hiter.axis[axis][i].angle.index = hiter.axis[axis][i].index;
651 if (convexhull_2d_angle_iter_step_on_axis(hiter, hiter.axis[axis][i])) {
652 hull_angle_insert_ordered(hiter, &hiter.axis[axis][i]);
653 }
654 }
655 }
656
657 return hiter;
658}
659
660#ifdef USE_ANGLE_ITER_ORDER_ASSERT
661[[maybe_unused]] static float convexhull_2d_angle_iter_cross_for_assert(
662 const HullAngleIter &hiter, const AngleCanonical &angle_prev)
663{
664 const int i_a = angle_prev.index;
665 const int i_b = hiter.axis_ordered->angle.index;
666 const float2 dir_a = float2(hiter.points_hull[(i_a + 1) % hiter.points_hull_num]) -
667 float2(hiter.points_hull[i_a]);
668 const float2 dir_b = float2(hiter.points_hull[(i_b + 1) % hiter.points_hull_num]) -
669 float2(hiter.points_hull[i_b]);
670 return dir_a[0] * dir_b[1] - dir_a[1] * dir_b[0];
671}
672#endif
673
675{
676 HullAngleStep *hstep = hiter.axis_ordered;
677#ifdef USE_ANGLE_ITER_ORDER_ASSERT
678 const AngleCanonical angle_prev = hstep->angle;
679#endif
680
681 hiter.axis_ordered = hiter.axis_ordered->next;
682 if (convexhull_2d_angle_iter_step_on_axis(hiter, *hstep)) {
683 hull_angle_insert_ordered(hiter, hstep);
684 }
685
686#ifdef USE_ANGLE_ITER_ORDER_ASSERT
687 if (hiter.axis_ordered) {
688 hstep = hiter.axis_ordered;
689 BLI_assert((hull_angle_canonical_cmp(angle_prev, hiter.axis_ordered->angle) > 0) ||
690 /* Skip for near co-linear edges can fail.
691 * The `convexhull_2d.NearCoLinear` test needs this so as not to assert.
692 *
693 * NOTE: An alternative would be to "filter" the hull by walking around the hull,
694 * angle stepping and filtering out points that don't fit consistent turning rule.
695 * This is debatable - with near co-linear edges it's unlikely to make a noticeable
696 * improvement to the result, at the expense of having to calculate unit length
697 * vectors for all edges twice (or store them for reuse). */
698 (std::abs(convexhull_2d_angle_iter_cross_for_assert(hiter, angle_prev)) < 1e-6f));
699 UNUSED_VARS_NDEBUG(angle_prev);
700 }
701#endif
702}
703
705
706/* -------------------------------------------------------------------- */
709
715template<int Axis, int AxisSign>
716static float convexhull_2d_compute_extent_on_axis(const float (*points_hull)[2],
717 const int points_hull_num,
718 const float2 &sincos,
719 int *index_p)
720{
721 /* NOTE(@ideasman42): Use a forward search instead of attempting a search strategy
722 * computing upper & lower bounds (similar to a binary search). The rotating calipers
723 * are ensured to test ordered rotations between 0-90 degrees, meaning any cases where
724 * this function needs to step over many points will be limited to a small number of cases.
725 * Since scanning forward isn't expensive it shouldn't pose a problem. */
726 BLI_assert(*index_p >= 0);
727 const int index_init = *index_p;
728 int index_best = index_init;
729 float value_init = (Axis == 0) ? sincos_rotate_cw_x(sincos, points_hull[index_best]) :
730 sincos_rotate_cw_y(sincos, points_hull[index_best]);
731 float value_best = value_init;
732 /* Simply scan up the array. */
733 for (int count = 1; count < points_hull_num; count++) {
734 const int index_test = (index_init + count) % points_hull_num;
735 const float value_test = (Axis == 0) ? sincos_rotate_cw_x(sincos, points_hull[index_test]) :
736 sincos_rotate_cw_y(sincos, points_hull[index_test]);
737 if ((AxisSign == -1) ? (value_test > value_best) : (value_test < value_best)) {
738 break;
739 }
740 value_best = value_test;
741 index_best = index_test;
742 }
743
744 *index_p = index_best;
745 return value_best;
746}
747
748static float2 convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], int points_hull_num)
749{
750 float area_best = std::numeric_limits<float>::max();
751 float2 sincos_best = {0.0f, 1.0f}; /* Track the best angle as a unit vector, delaying `atan2`. */
752 int index_best = std::numeric_limits<int>::max();
753
754 /* Initialize to zero because the first pass uses the first index to set the bounds. */
755 Bounds<int> bounds_index[2] = {{0, 0}, {0, 0}};
756
757 HullAngleIter hull_iter = convexhull_2d_angle_iter_init(points_hull, points_hull_num);
758
759 /* Use the axis aligned bounds as starting points. */
760 bounds_index[0].min = hull_iter.axis[0][1].angle.index;
761 bounds_index[0].max = hull_iter.axis[0][0].angle.index;
762 bounds_index[1].min = hull_iter.axis[1][0].angle.index;
763 bounds_index[1].max = hull_iter.axis[1][1].angle.index;
764 while (const HullAngleStep *hstep = hull_iter.axis_ordered) {
765 /* Step the calipers to the new rotation `sincos`, returning the bounds at the same time. */
766 Bounds<float> bounds_test[2] = {
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)},
775 };
776
777 const float area_test = (bounds_test[0].max - bounds_test[0].min) *
778 (bounds_test[1].max - bounds_test[1].min);
779
780 if (area_test < area_best ||
781 /* Use the index as a tie breaker, this simply matches the behavior of checking
782 * all edges in-order and only overwriting past results when they're an improvement. */
783 ((area_test == area_best) && (hstep->angle.index < index_best)))
784 {
785 area_best = area_test;
786 sincos_best = hstep->angle.sincos;
787 index_best = hstep->angle.index;
788 }
789
791 }
792
793#if defined(USE_BRUTE_FORCE_ASSERT) && !defined(NDEBUG)
794 {
795 /* Ensure the optimized result matches the brute-force version. */
796 const float2 sincos_test = convexhull_aabb_fit_hull_2d_brute_force(points_hull,
797 points_hull_num);
798 if (sincos_best != sincos_test) {
799 BLI_assert(sincos_best == sincos_test);
800 }
801 }
802#endif
803
804 return sincos_best;
805}
806
808{
809 const int points_num = int(points.size());
810 BLI_assert(points_num >= 0);
811 float2 sincos = {0.0f, 1.0f};
812
813 int *index_map = MEM_new_array_uninitialized<int>(size_t(points_num), __func__);
814
815 int points_hull_num = BLI_convexhull_2d(points, index_map);
816
817 if (points_hull_num > 1) {
818 float (*points_hull)[2] = MEM_new_array_uninitialized<float[2]>(size_t(points_hull_num),
819 __func__);
820 for (int j = 0; j < points_hull_num; j++) {
821 copy_v2_v2(points_hull[j], points[index_map[j]]);
822 }
823
824 sincos = convexhull_aabb_fit_hull_2d(points_hull, points_hull_num);
825 MEM_delete(points_hull);
826 }
827
828 MEM_delete(index_map);
829
830 return sincos;
831}
832
838
840
841} // namespace blender
Read Blender memory allocation and freeing.
__forceinline const float4 insert(const float4 &a, const float b)
Definition binning.cpp:31
#define UNUSED_VARS(...)
#define UNUSED_VARS_NDEBUG(...)
btScalar max
constexpr int64_t size() const
Definition BLI_span.hh:256
#define atan2
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)
T abs(const T &a)
BMesh Iterators.
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
#define min(a, b)
Definition sort.cc:38
HullAngleStep * axis_ordered
HullAngleStep axis[2][2]
const float(* points_hull)[2]