16#include "testing/testing.h"
37#define DEFAULT_TEST_ITER 8
40#define DEFAULT_TEST_POLY_NUM 12
42#define DEFAULT_TEST_RANDOM_SEED 123
45#define ROTATION_EPS 1e-6
55 for (
int p_index : points_map) {
56 points_hull[
index++] = points[p_index];
66 Span<int> points_hull_map_span(points_hull_map.
data(), points_hull_map_num);
90TEST(convexhull_2d, IsConvex)
99 if (points_hull.
size() < 3) [[unlikely]] {
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++) {
116 for (
float2 &p : points) {
139 Array<float2> points = {{0.0f, 0.0f}, {0.0f, 0.0f}, {0.0f, 0.0f}};
144TEST(convexhull_2d, Lines_AxisAligned)
147 for (
int sign_x = -1; sign_x <= 2; sign_x += 2) {
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}};
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}};
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}};
185 for (
float2 &p : points) {
199 for (
float2 &p : points) {
210TEST(convexhull_2d, Lines_Diagonal)
213 const float expected[4] = {45, -45, -45, 45};
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}};
227 const float expected[4] = {45, -45, -45, 45};
229 for (
int sign_x = -1; sign_x <= 2; sign_x += 2) {
230 for (
int sign_y = -1; sign_y <= 2; sign_y += 2) {
233 {1.0f * sign_x, 1.0f * sign_y},
234 {2.0f * sign_x, 2.0f * sign_y},
276 points_square_diagonal,
277 points_square_aligned,
280 for (
int x = -1;
x <= 1;
x += 2) {
281 for (
int y = -1;
y <= 1;
y += 2) {
284 for (
int i = 0; i < points.
size(); i++) {
285 points[i] *= xy_flip;
290 points_indices.
data());
294 for (
int i = 0; i < points_indices_num; i++) {
295 points_hull[i] = points[points_indices[i]];
300 cross_poly_v2(
reinterpret_cast<float (*)[2]
>(points_hull.
data()), points_indices_num),
304 for (
int i = 1; i < points_indices_num; i++) {
305 EXPECT_TRUE((points_hull[0][1] == points_hull[i][1]) ?
307 (points_hull[0][0] < points_hull[i][0]) :
309 (points_hull[0][1] < points_hull[i][1]));
321 for (
int i = 0; i < points_num; i++) {
337TEST(convexhull_2d, OctagonAxisAligned)
342 for (
int i = 0; i < points_num; i++) {
358TEST(convexhull_2d, OctagonNearDuplicates)
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},
373 {-169.99509, -259.28387},
374 {-172.33832, -279.7067},
375 {-148.70407, -309.46725},
376 {-128.28127, -311.81046},
379 for (
int scale_step = -15; scale_step <= 15; scale_step += 1) {
382 if (scale_step == 0) {
385 else if (scale_step < 0) {
393 for (
float2 &p : points_copy) {
413 auto shape_generate_fn =
417 const int points_num_reserved = 4;
426 for (
int i = points_num_reserved; i < points_num; i++) {
432 for (
int i = 0; i < points_num_reserved; i++) {
433 std::swap(points[i], points[rng.
get_int32(points_num)]);
437 const float2 translation = {
444 for (
float2 &p : points) {
448 p = (((p -
float2(0.5f, 0.5f)) * size) * rot_mat) + translation;
456 constexpr float size_margin = 0.1;
469 for (
const float2 &p : points) {
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);
480TEST(convexhull_2d, NearCoLinear)
487 {+0.117849081754684448, 0.989015936851501464},
488 {-0.035001631826162338, 0.988978028297424316},
489 {-0.046869464218616485, 0.988972485065460205},
490 {-0.048847433179616928, 0.988971292972564697},
498TEST(convexhull_2d, CoincidentTopmostX)
503 {0.404492587f, 0.514067411f},
504 {0.222857147f, 0.608571410f},
505 {0.222857147f, 0.631428599f},
506 {0.214285702f, 0.608571410f},
507 {0.214285702f, 0.579999983f},
508 {0.217142850f, 0.557142854f},
509 {0.222857147f, 0.545714259f},
512 ASSERT_GE(points_hull.
size(), 3);
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++) {
530 auto shape_circle_fn = [](RandomNumberGenerator &rng,
const int points_num) -> Array<float2> {
532 Array<float2> points(points_num);
535 for (
int i = 0; i < points_num; i++) {
538 rng.shuffle<
float2>(points);
550TEST(convexhull_2d, Random)
558 for (
int i = 0; i < points_num; i++) {
559 points[i] = rng.get_unit_float2();
#define DEFAULT_TEST_RANDOM_SEED
#define DEFAULT_TEST_POLY_NUM
#define DEFAULT_TEST_ITER
#define INIT_MINMAX2(min, max)
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
RandomNumberGenerator(uint32_t seed=0)
void shuffle(MutableSpan< T > values)
constexpr int64_t size() const
float3x3 scale(float3x3 mat, float2 scale)
#define EXPECT_GE(result, expect)
#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)
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)
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)
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)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
static AngleRadianBase from_degree(const float °rees)