Blender V5.3
BLI_convexhull_2d_test.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2024 Blender Authors
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
15
16#include "testing/testing.h"
17
18#include "BLI_array.hh"
19#include "BLI_convexhull_2d.hh"
21#include "BLI_math_geom_c.hh"
22#include "BLI_math_matrix_c.hh"
24#include "BLI_math_rotation.hh"
26#include "BLI_math_vector.hh"
27#include "BLI_math_vector_c.hh"
29#include "BLI_rand.hh"
30
31namespace blender {
32
37#define DEFAULT_TEST_ITER 8
38
40#define DEFAULT_TEST_POLY_NUM 12
41
42#define DEFAULT_TEST_RANDOM_SEED 123
43
45#define ROTATION_EPS 1e-6
46
47/* -------------------------------------------------------------------- */
50
52{
53 Array<float2> points_hull(points_map.size());
54 int index = 0;
55 for (int p_index : points_map) {
56 points_hull[index++] = points[p_index];
57 }
58 return points_hull;
59}
60
62{
63 Array<int> points_hull_map(points.size());
64 int points_hull_map_num = BLI_convexhull_2d(points, points_hull_map.data());
65
66 Span<int> points_hull_map_span(points_hull_map.data(), points_hull_map_num);
67 return convexhull_points_from_map(points, points_hull_map_span);
68}
69
70static float mod_inline(float a, float b)
71{
72 return a - (b * floorf(a / b));
73}
74
80{
81 return mod_inline(angle, float(M_PI / 2.0f));
82}
83
85
86/* -------------------------------------------------------------------- */
89
90TEST(convexhull_2d, IsConvex)
91{
94 for (int iter = 0; iter < DEFAULT_TEST_ITER; iter++) {
95 for (float2 &p : points) {
96 p = float2(rng.get_float(), rng.get_float());
97 }
98 Array<float2> points_hull = convexhull_2d_as_array(points);
99 if (points_hull.size() < 3) [[unlikely]] {
100 continue;
101 }
102
103 int i_prev = points_hull.size() - 2;
104 int i_curr = points_hull.size() - 1;
105 for (int i_next = 0; i_next < points_hull.size(); i_prev = i_curr, i_curr = i_next++) {
106 EXPECT_GE(cross_tri_v2(points_hull[i_prev], points_hull[i_curr], points_hull[i_next]), 0.0f);
107 }
108 }
109}
110
111TEST(convexhull_2d, IsCCW)
112{
115 for (int iter = 0; iter < DEFAULT_TEST_ITER; iter++) {
116 for (float2 &p : points) {
117 p = float2(rng.get_float(), rng.get_float());
118 }
119 Array<float2> points_hull = convexhull_2d_as_array(points);
120
121 EXPECT_GE(cross_poly_v2(reinterpret_cast<const float (*)[2]>(points_hull.data()),
122 points_hull.size()),
123 0.0f);
124 }
125}
126
127TEST(convexhull_2d, NOP)
128{
129 { /* Single point. */
130 Array<float2> points = {{0.0f, 0.0f}};
132 }
133
134 { /* Single point, 2x duplicates. */
135 Array<float2> points = {{0.0f, 0.0f}, {0.0f, 0.0f}};
137 }
138 { /* Single point, 3x duplicates. */
139 Array<float2> points = {{0.0f, 0.0f}, {0.0f, 0.0f}, {0.0f, 0.0f}};
141 }
142}
143
144TEST(convexhull_2d, Lines_AxisAligned)
145{
146 { /* Horizontal line (2 points). */
147 for (int sign_x = -1; sign_x <= 2; sign_x += 2) {
148 Array<float2> points = {{0.0f, 0.0f}, {1.0f * sign_x, 0.0}};
150 float(math::AngleRadian::from_degree(90.0f)),
152 }
153 }
154 { /* Horizontal line (3 points). */
155 for (int sign_x = -1; sign_x <= 2; sign_x += 2) {
156 Array<float2> points = {{0.0f, 0.0f}, {1.0f * sign_x, 0.0}, {2.0f * sign_x, 0.0}};
158 float(math::AngleRadian::from_degree(90.0f)),
160 }
161 }
162
163 { /* Vertical line (2 points). */
164 for (int sign_y = -1; sign_y <= 2; sign_y += 2) {
165 Array<float2> points = {{0.0f, 0.0f}, {0.0f, 1.0f * sign_y}};
169 }
170 }
171 { /* Vertical line (3 points). */
172 for (int sign_y = -1; sign_y <= 2; sign_y += 2) {
173 Array<float2> points = {{0.0f, 0.0f}, {0.0f, 1.0f * sign_y}, {0.0f, 2.0f * sign_y}};
177 }
178 }
179
180 { /* Horizontal line (many points). */
181 Array<float2> points(8);
183 for (int iter = 0; iter < DEFAULT_TEST_ITER; iter++) {
184 /* Add points, Y is always positive. */
185 for (float2 &p : points) {
186 p = rng.get_unit_float2();
187 p[0] = 0.0;
188 }
189
191 }
192 }
193
194 { /* Vertical line (many points). */
195 Array<float2> points(8);
197 for (int iter = 0; iter < DEFAULT_TEST_ITER; iter++) {
198 /* Add points, Y is always positive. */
199 for (float2 &p : points) {
200 p = rng.get_unit_float2();
201 p[0] = 0.0;
202 }
203
204 Array<float2> points_hull = convexhull_2d_as_array(points);
206 }
207 }
208}
209
210TEST(convexhull_2d, Lines_Diagonal)
211{
212 { /* Diagonal line (2 points). */
213 const float expected[4] = {45, -45, -45, 45};
214 int index = 0;
215 for (int sign_x = -1; sign_x <= 2; sign_x += 2) {
216 for (int sign_y = -1; sign_y <= 2; sign_y += 2) {
217 Array<float2> points = {{0.0f, 0.0f}, {1.0f * sign_x, 1.0f * sign_y}};
219 float(math::AngleRadian::from_degree(expected[index])),
221 index++;
222 }
223 }
224 }
225
226 { /* Diagonal line (3 points). */
227 const float expected[4] = {45, -45, -45, 45};
228 int index = 0;
229 for (int sign_x = -1; sign_x <= 2; sign_x += 2) {
230 for (int sign_y = -1; sign_y <= 2; sign_y += 2) {
231 Array<float2> points = {
232 {0.0f, 0.0f},
233 {1.0f * sign_x, 1.0f * sign_y},
234 {2.0f * sign_x, 2.0f * sign_y},
235 };
237 float(math::AngleRadian::from_degree(expected[index])),
239 index++;
240 }
241 }
242 }
243}
244
245TEST(convexhull_2d, Simple)
246{
247
248 /* 45degree rotated square. */
249 const Array<float2> points_square_diagonal = {
250 {0.0f, -1.0f},
251 {-1.0f, 0.0f},
252 {0.0f, 1.0f},
253 {1.0f, 0.0f},
254 };
255
256 /* Axis aligned square. */
257 const Array<float2> points_square_aligned = {
258 {-1.0f, -1.0f},
259 {-1.0f, 1.0f},
260 {1.0f, 1.0f},
261 {1.0f, -1.0f},
262 };
263
264 /* 45degree rotated square. */
265 EXPECT_NEAR(BLI_convexhull_aabb_fit_points_2d(points_square_diagonal),
266 float(math::AngleRadian::from_degree(45.0f)),
268
269 /* Axis aligned square. */
270 EXPECT_NEAR(BLI_convexhull_aabb_fit_points_2d(points_square_aligned),
271 float(math::AngleRadian::from_degree(90.0f)),
273
274 for (const Array<float2> &points_orig :
275 {
276 points_square_diagonal,
277 points_square_aligned,
278 })
279 {
280 for (int x = -1; x <= 1; x += 2) {
281 for (int y = -1; y <= 1; y += 2) {
282 Array<float2> points = points_orig;
283 const float2 xy_flip = {float(x), float(y)};
284 for (int i = 0; i < points.size(); i++) {
285 points[i] *= xy_flip;
286 }
287
288 Array<int> points_indices(points.size());
289 int points_indices_num = BLI_convexhull_2d(Span(points.data(), points.size()),
290 points_indices.data());
291
292 Array<float2> points_hull(points_indices_num);
293
294 for (int i = 0; i < points_indices_num; i++) {
295 points_hull[i] = points[points_indices[i]];
296 }
297
298 /* The cross product must be positive or zero. */
299 EXPECT_GE(
300 cross_poly_v2(reinterpret_cast<float (*)[2]>(points_hull.data()), points_indices_num),
301 0.0f);
302
303 /* The first point is documented to be the lowest, check this is so. */
304 for (int i = 1; i < points_indices_num; i++) {
305 EXPECT_TRUE((points_hull[0][1] == points_hull[i][1]) ?
306 /* Equal Y therefor X must be less. */
307 (points_hull[0][0] < points_hull[i][0]) :
308 /* When Y isn't equal, Y must be less. */
309 (points_hull[0][1] < points_hull[i][1]));
310 }
311 }
312 }
313 }
314}
315
316TEST(convexhull_2d, Octagon)
317{
318 auto shape_octagon_fn = [](RandomNumberGenerator &rng, const int points_num) -> Array<float2> {
319 /* Avoid zero area boxes. */
320 Array<float2> points(points_num);
321 for (int i = 0; i < points_num; i++) {
322 sin_cos_from_fraction(i, points_num, &points[i][0], &points[i][1]);
323 }
324 rng.shuffle<float2>(points);
325 return points;
326 };
327
329 for (int iter = 0; iter < DEFAULT_TEST_ITER; iter++) {
330 Array<float2> points = shape_octagon_fn(rng, 8);
332 float(math::AngleRadian::from_degree(67.5f)),
334 }
335}
336
337TEST(convexhull_2d, OctagonAxisAligned)
338{
339 auto shape_octagon_fn = [](RandomNumberGenerator &rng, const int points_num) -> Array<float2> {
340 /* Avoid zero area boxes. */
341 Array<float2> points(points_num);
342 for (int i = 0; i < points_num; i++) {
343 sin_cos_from_fraction((i * 2) + 1, points_num * 2, &points[i][0], &points[i][1]);
344 }
345 rng.shuffle<float2>(points);
346 return points;
347 };
348
350 for (int iter = 0; iter < DEFAULT_TEST_ITER; iter++) {
351 Array<float2> points = shape_octagon_fn(rng, 8);
353 float(math::AngleRadian::from_degree(90.0f)),
355 }
356}
357
358TEST(convexhull_2d, OctagonNearDuplicates)
359{
360 /* A large rotated octagon that contains two points which are *almost* duplicates.
361 * Calculating the best fit AABB returns different angles depending on the scale.
362 * This isn't something that needs *fixing* since the exact edge used may
363 * reasonably differ when scaling orders of magnate up or down.
364 * In this test don't check for the exact angle instead check the wrapped (canonical)
365 * angle matches at every scale, see: #143390. */
366 Array<float2> points = {
367 {-128.28127, -311.8105},
368 {-98.5207, -288.1762},
369 {-96.177475, -267.75345},
370 {-119.81172, -237.99284},
371 {-140.23453, -235.64966},
372 {-140.23453, -235.64963}, /* Close to the previous. */
373 {-169.99509, -259.28387},
374 {-172.33832, -279.7067},
375 {-148.70407, -309.46725},
376 {-128.28127, -311.81046}, /* Close to the first. */
377 };
378
379 for (int scale_step = -15; scale_step <= 15; scale_step += 1) {
380 /* Test orders of magnitude from `1 / (10 ** 15)` to `10 ** 15` */
381 float scale;
382 if (scale_step == 0) {
383 scale = 1.0f;
384 }
385 else if (scale_step < 0) {
386 scale = float(1.0 / pow(10.0, double(-scale_step)));
387 }
388 else {
389 scale = float(pow(10.0, double(scale_step)));
390 }
391
392 Array<float2> points_copy = points;
393 for (float2 &p : points_copy) {
394 p *= scale;
395 }
396
397 /* NOTE: #ROTATION_EPS epsilon fails on MacOS,
398 * use a slightly larger epsilon so tests pass on all systems. */
399 const float abs_error = scale < 10.0f ? ROTATION_EPS : 1e-5f;
401 float(math::AngleRadian::from_degree(51.5453016381f)),
402 abs_error);
403 }
404}
405
411TEST(convexhull_2d, Complex)
412{
413 auto shape_generate_fn =
414 [](RandomNumberGenerator &rng, const float2 &size, const int points_num) -> Array<float2> {
415 /* Avoid zero area boxes. */
416 Array<float2> points(points_num);
417 const int points_num_reserved = 4;
418 BLI_assert(points_num_reserved >= 4);
419
420 /* Ensure there are always points at the bounds. */
421 points[0] = {0.0f, rng.get_float()}; /* Left. */
422 points[1] = {1.0f, rng.get_float()}; /* Right. */
423 points[2] = {rng.get_float(), 0.0f}; /* Bottom. */
424 points[3] = {rng.get_float(), 1.0f}; /* Top. */
425
426 for (int i = points_num_reserved; i < points_num; i++) {
427 points[i] = {rng.get_float(), rng.get_float()};
428 }
429
430 /* Shuffle to ensure the solution is valid no matter the order of the input,
431 * Only the first `points_num_reserved` matter as remaining points are random. */
432 for (int i = 0; i < points_num_reserved; i++) {
433 std::swap(points[i], points[rng.get_int32(points_num)]);
434 }
435
436 /* Map from 0-1 to a random transformation. */
437 const float2 translation = {
438 (rng.get_float() * 2.0f) - 1.0f,
439 (rng.get_float() * 2.0f) - 1.0f,
440 };
441
444 for (float2 &p : points) {
445 BLI_assert(p[0] >= 0.0 && p[0] <= 1.0f);
446 BLI_assert(p[1] >= 0.0 && p[1] <= 1.0f);
447 /* Center from [-0.5..0.5], apply size, rotate & translate. */
448 p = (((p - float2(0.5f, 0.5f)) * size) * rot_mat) + translation;
449 }
450
451 return points;
452 };
453
455 for (int i = 0; i < DEFAULT_TEST_ITER; i++) {
456 constexpr float size_margin = 0.1;
457 /* Random size from `[size_margin..2]`. */
458 float2 size = {
459 math::min((rng.get_float() * 2.0f) + size_margin, 2.0f),
460 math::min((rng.get_float() * 2.0f) + size_margin, 2.0f),
461 };
462
463 Array<float2> points = shape_generate_fn(rng, size, DEFAULT_TEST_POLY_NUM);
464 const float angle = BLI_convexhull_aabb_fit_points_2d(points);
465
467 float2 tempmin, tempmax;
468 INIT_MINMAX2(tempmin, tempmax);
469 for (const float2 &p : points) {
470 math::min_max(p * rot_mat, tempmin, tempmax);
471 }
472
473 const float2 size_result = tempmax - tempmin;
474 float area_input = size[0] * size[1];
475 float area_result = size_result[0] * size_result[1];
476 EXPECT_LE(area_result, area_input + 1e-6f);
477 }
478}
479
480TEST(convexhull_2d, NearCoLinear)
481{
482 /* This test uses a polygon that is very close to having a co-linear edge.
483 * The rotating calipers detect this as walking backwards (i.e. the hull is *not* convex),
484 * however, it being convex or not will give different answers depending on the method used.
485 * Add near co-linear test, extracted from: #152810 which was asserting. */
486 const float2 coords[] = {
487 {+0.117849081754684448, 0.989015936851501464},
488 {-0.035001631826162338, 0.988978028297424316},
489 {-0.046869464218616485, 0.988972485065460205},
490 {-0.048847433179616928, 0.988971292972564697},
491 };
494 float(math::AngleRadian::from_degree(89.984655)),
496}
497
498TEST(convexhull_2d, CoincidentTopmostX)
499{
500 /* The top-most point shares its X with the point below, which gave an incorrect
501 * (concave) result in v5.1. */
502 const Array<float2> points = {
503 {0.404492587f, 0.514067411f},
504 {0.222857147f, 0.608571410f},
505 {0.222857147f, 0.631428599f}, /* Top-most, shares X with the previous point. */
506 {0.214285702f, 0.608571410f},
507 {0.214285702f, 0.579999983f},
508 {0.217142850f, 0.557142854f},
509 {0.222857147f, 0.545714259f},
510 };
511 Array<float2> points_hull = convexhull_2d_as_array(points);
512 ASSERT_GE(points_hull.size(), 3);
513
514 int i_prev = points_hull.size() - 2;
515 int i_curr = points_hull.size() - 1;
516 for (int i_next = 0; i_next < points_hull.size(); i_prev = i_curr, i_curr = i_next++) {
517 EXPECT_GE(cross_tri_v2(points_hull[i_prev], points_hull[i_curr], points_hull[i_next]), 0.0f);
518 }
519}
520
521/* Keep these as they're handy for generating a lot of random data.
522 * To brute force check results are as expected:
523 * - Increase #DEFAULT_TEST_ITER to a large number (100k or so).
524 * - Uncomment #USE_BRUTE_FORCE_ASSERT define in `convexhull_2d.cc` to ensure results
525 * match a reference implementation.
526 */
527#if 0
528TEST(convexhull_2d, Circle)
529{
530 auto shape_circle_fn = [](RandomNumberGenerator &rng, const int points_num) -> Array<float2> {
531 /* Avoid zero area boxes. */
532 Array<float2> points(points_num);
533
534 /* Going this way ends up with normal(s) upward */
535 for (int i = 0; i < points_num; i++) {
536 sin_cos_from_fraction(i, points_num, &points[i][0], &points[i][1]);
537 }
538 rng.shuffle<float2>(points);
539 return points;
540 };
541
543 for (int iter = 0; iter < DEFAULT_TEST_ITER; iter++) {
544 Array<float2> points = shape_circle_fn(rng, DEFAULT_TEST_POLY_NUM);
545 const float angle = BLI_convexhull_aabb_fit_points_2d(points);
546 (void)angle;
547 }
548}
549
550TEST(convexhull_2d, Random)
551{
552 auto shape_random_unit_fn = [](RandomNumberGenerator &rng,
553 const int points_num) -> Array<float2> {
554 /* Avoid zero area boxes. */
555 Array<float2> points(points_num);
556
557 /* Going this way ends up with normal(s) upward */
558 for (int i = 0; i < points_num; i++) {
559 points[i] = rng.get_unit_float2();
560 }
561 return points;
562 };
563
565
566 for (int iter = 0; iter < DEFAULT_TEST_ITER; iter++) {
567 Array<float2> points = shape_random_unit_fn(rng, DEFAULT_TEST_POLY_NUM);
568 const float angle = BLI_convexhull_aabb_fit_points_2d(points);
569 (void)angle;
570 }
571}
572#endif
573
575
576} // namespace blender
#define DEFAULT_TEST_RANDOM_SEED
#define DEFAULT_TEST_POLY_NUM
#define DEFAULT_TEST_ITER
#define ROTATION_EPS
#define M_PI
#define INIT_MINMAX2(min, max)
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
int64_t size() const
Definition BLI_array.hh:267
const T * data() const
Definition BLI_array.hh:323
RandomNumberGenerator(uint32_t seed=0)
Definition BLI_rand.hh:21
void shuffle(MutableSpan< T > values)
Definition BLI_rand.hh:88
constexpr Span()=default
constexpr int64_t size() const
Definition BLI_span.hh:256
#define pow
float3x3 scale(float3x3 mat, float2 scale)
#define EXPECT_GE(result, expect)
#define TEST(a, b)
#define EXPECT_TRUE(result)
#define EXPECT_NEAR(result, expect, threshold)
#define EXPECT_LE(result, expect)
AngleRadianBase< float > AngleRadian
T min(const T &a, const T &b)
void min_max(const T &value, T &min, T &max)
MatT from_rotation(const RotationT &rotation)
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static float mod_inline(float a, float b)
static Array< float2 > convexhull_points_from_map(Span< float2 > points, Span< int > points_map)
float cross_poly_v2(const float verts[][2], unsigned int nr)
Definition math_geom.cc:153
MatBase< float, 2, 2 > float2x2
MINLINE float cross_tri_v2(const float v1[2], const float v2[2], const float v3[2])
void sin_cos_from_fraction(int numerator, int denominator, float *r_sin, float *r_cos)
TEST(array_store, Nop)
int BLI_convexhull_2d(Span< float2 > points, int r_points[])
VecBase< float, 2 > float2
static Array< float2 > convexhull_2d_as_array(Span< float2 > points)
static float convexhull_aabb_canonical_angle(float angle)
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
float BLI_convexhull_aabb_fit_points_2d(Span< float2 > points)
#define floorf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
static AngleRadianBase from_degree(const float &degrees)