3 #include "testing/testing.h"
9 #define USE_COMBINATIONS_ALL
20 #ifdef USE_OBJ_PREVIEW
31 const float poly[][2],
32 const unsigned int poly_num,
33 const unsigned int tris[][3],
34 const unsigned int tris_num);
39 #define TRI_ERROR_VALUE (unsigned int)-1
44 for (i = 0; i < tris_num; i++) {
46 for (j = 0; j < 3; j++) {
60 const unsigned int poly_num,
61 const unsigned int tris[][3],
62 const unsigned int tris_num)
65 int *used_num = (
int *)
MEM_callocN(poly_num *
sizeof(
int), __func__);
66 for (i = 0; i < tris_num; i++) {
68 for (j = 0; j < 3; j++) {
70 used_num[tris[i][j]] += 1;
72 EXPECT_NE(tris[i][0], tris[i][1]);
73 EXPECT_NE(tris[i][1], tris[i][2]);
74 EXPECT_NE(tris[i][2], tris[i][0]);
76 for (i = 0; i < poly_num; i++) {
77 EXPECT_NE(0, used_num[i]);
83 const unsigned int poly_num,
84 const unsigned int tris[][3],
85 const unsigned int tris_num)
90 for (i = 0; i < tris_num; i++) {
92 for (j = 0; j < 3; j++) {
93 const unsigned int v1 = tris[i][j];
94 const unsigned int v2 = tris[i][(j + 1) % 3];
106 for (i = 0; i < poly_num; i++) {
107 const unsigned int v1 = i;
108 const unsigned int v2 = (i + 1) % poly_num;
110 EXPECT_NE((
void *)p,
nullptr);
129 const unsigned int tris[][3],
130 const unsigned int tris_num)
133 unsigned int count[2] = {0, 0};
134 for (i = 0; i < tris_num; i++) {
135 float winding_test =
cross_tri_v2(poly[tris[i][0]], poly[tris[i][1]], poly[tris[i][2]]);
136 if (
fabsf(winding_test) > FLT_EPSILON) {
137 count[winding_test < 0.0f] += 1;
147 const unsigned int poly_num,
148 const unsigned int tris[][3],
149 const unsigned int tris_num)
153 float area_total_tris = 0.0f;
154 const float eps_abs = 0.00001f;
155 const float eps = area_total > 1.0f ? (area_total * eps_abs) : eps_abs;
156 for (i = 0; i < tris_num; i++) {
157 area_total_tris +=
area_tri_v2(poly[tris[i][0]], poly[tris[i][1]], poly[tris[i][2]]);
159 EXPECT_NEAR(area_total, area_total_tris,
eps);
169 const float poly[][2],
170 const unsigned int poly_num,
171 const unsigned int tris[][3],
172 const unsigned int tris_num)
176 if (!is_degenerate) {
186 const float poly[][2],
187 const unsigned int poly_num,
188 unsigned int tris[][3],
189 const unsigned int tris_num)
215 const float poly[][2],
216 const unsigned int poly_num,
217 unsigned int tris[][3],
218 const unsigned int tris_num)
221 for (
int flip_x = 0; flip_x < 2; flip_x++) {
222 for (
int flip_y = 0; flip_y < 2; flip_y++) {
223 float sign_x = flip_x ? -1.0f : 1.0f;
224 float sign_y = flip_y ? -1.0f : 1.0f;
225 for (
int i = 0; i < poly_num; i++) {
226 poly_copy[i][0] = poly[i][0] * sign_x;
227 poly_copy[i][1] = poly[i][1] * sign_y;
235 #ifdef USE_COMBINATIONS_ALL
238 const float poly[][2],
239 const unsigned int poly_num,
240 unsigned int tris[][3],
241 const unsigned int tris_num)
244 unsigned int poly_reverse;
248 memcpy(poly_copy, poly,
sizeof(
float[2]) * poly_num);
250 for (poly_reverse = 0; poly_reverse < 2; poly_reverse++) {
251 unsigned int poly_cycle;
257 for (poly_cycle = 0; poly_cycle < poly_num; poly_cycle++) {
263 memmove(&poly_copy[0], &poly_copy[1], (poly_num - 1) *
sizeof(
float[2]));
273 const float poly[][2],
274 const unsigned int poly_num,
275 unsigned int tris[][3],
276 const unsigned int tris_num)
282 #define TEST_POLYFILL_TEMPLATE_STATIC(poly, is_degenerate) \
284 unsigned int tris[POLY_TRI_COUNT(ARRAY_SIZE(poly))][3]; \
285 const unsigned int poly_num = ARRAY_SIZE(poly); \
286 const unsigned int tris_num = ARRAY_SIZE(tris); \
287 const char *id = typeid(*this).name(); \
289 test_polyfill_template_main(id, is_degenerate, poly, poly_num, tris, tris_num); \
296 #ifdef USE_OBJ_PREVIEW
298 const float poly[][2],
299 const unsigned int poly_num,
300 const unsigned int tris[][3],
301 const unsigned int tris_num)
309 f = fopen(path,
"w");
314 for (i = 0; i < poly_num; i++) {
315 fprintf(f,
"v %f %f 0.0\n",
UNPACK2(poly[i]));
318 for (i = 0; i < tris_num; i++) {
319 fprintf(f,
"f %u %u %u\n",
UNPACK3_EX(1 +, tris[i], ));
326 const float poly[][2],
327 const unsigned int poly_num,
328 const unsigned int tris[][3],
329 const unsigned int tris_num)
332 (
void)poly, (
void)poly_num;
333 (
void)tris, (
void)tris_num;
377 #define POLY_TRI_COUNT(len) ((len)-2)
382 const float poly[][2] = {{0, 0}, {0, 1}, {1, 0}};
389 const float poly[][2] = {{0, 0}, {0, 1}, {1, 1}, {1, 0}};
396 const float poly[][2] = {{0, 0}, {1, 0}, {1, 1}, {0, 1}};
403 const float poly[][2] = {{0, 0}, {0.6f, 0.4f}, {1, 0}, {0.5f, 1}};
408 TEST(polyfill2d, StarfleetDegenerate)
410 const float poly[][2] = {{0, 0}, {0.6f, 0.4f}, {0.6f, 0.4f}, {1, 0}, {0.5f, 1}};
417 const float poly[][2] = {{0, 0}, {1, 0}, {2, 0}};
424 const float poly[][2] = {{0, 0}, {1, 0}, {2, 0}, {3, 0}};
429 TEST(polyfill2d, UnorderedColinear)
431 const float poly[][2] = {{0, 0}, {1, 1}, {2, 0}, {3, 1}, {4, 0}};
438 const float poly[][2] = {
458 const float poly[][2] = {{4, 0}, {5, 3}, {8, 4}, {5, 5}, {4, 8}, {3, 5}, {0, 4}, {3, 3}};
465 const float poly[][2] = {
466 {1, 0}, {2, 0}, {3, 1}, {3, 3}, {2, 3}, {2, 1}, {1, 1}, {1, 3}, {0, 3}, {0, 1}};
473 const float poly[][2] = {
497 const float poly[][2] = {
518 TEST(polyfill2d, SelfIntersect)
520 const float poly[][2] = {{0, 0}, {1, 1}, {2, -1}, {3, 1}, {4, 0}};
527 const float poly[][2] = {
547 const float poly[][2] = {
567 const float poly[][2] = {
568 {190, 480}, {140, 180}, {310, 100}, {330, 390}, {290, 390}, {280, 260}, {220, 260},
569 {220, 430}, {370, 430}, {350, 30}, {50, 30}, {160, 560}, {730, 510}, {710, 20},
570 {410, 30}, {470, 440}, {640, 410}, {630, 140}, {590, 140}, {580, 360}, {510, 370},
571 {510, 60}, {650, 70}, {660, 450}, {190, 480},
579 const float poly[][2] = {
595 const float poly[][2] = {
596 {72.42465f, 197.07095f},
597 {78.485535f, 189.92776f},
598 {86.12059f, 180.92929f},
599 {99.68253f, 164.94557f},
600 {105.24325f, 165.79604f},
601 {107.21862f, 166.09814f},
602 {112.41958f, 162.78253f},
603 {113.73238f, 161.94562f},
604 {123.29477f, 167.93805f},
605 {126.70667f, 170.07617f},
606 {73.22717f, 199.51062f},
615 const float poly[][2] = {
616 {2400.0f, 480.0f}, {2400.0f, 176.0f}, {1920.0f, 480.0f},
617 {1920.0459f, 484.22314f}, {1920.1797f, 487.91016f}, {1920.3955f, 491.0874f},
618 {1920.6875f, 493.78125f}, {1921.0498f, 496.01807f}, {1921.4766f, 497.82422f},
619 {1921.9619f, 499.22607f}, {1922.5f, 500.25f}, {1923.085f, 500.92236f},
620 {1923.7109f, 501.26953f}, {1924.3721f, 501.31787f}, {1925.0625f, 501.09375f},
621 {1925.7764f, 500.62354f}, {1926.5078f, 499.9336f}, {1927.251f, 499.0503f},
622 {1928.0f, 498.0f}, {1928.749f, 496.80908f}, {1929.4922f, 495.5039f},
623 {1930.2236f, 494.11084f}, {1930.9375f, 492.65625f}, {1931.6279f, 491.1665f},
624 {1932.2891f, 489.66797f}, {1932.915f, 488.187f}, {1933.5f, 486.75f},
625 {1934.0381f, 485.3833f}, {1934.5234f, 484.11328f}, {1934.9502f, 482.9663f},
626 {1935.3125f, 481.96875f}, {1935.6045f, 481.14697f}, {1935.8203f, 480.52734f},
627 {1935.9541f, 480.13623f}, {1936.0f, 480.0f}};
634 const float poly[][2] = {
635 {3.914329f, 1.9008259f},
636 {4.414321f, 1.903619f},
637 {4.8973203f, 1.9063174f},
638 {5.4979978f, 1.9096732f},
647 const float poly[][2] = {
648 {3.914329f, 1.9008259f},
649 {4.414321f, 1.903619f},
650 {4.8973203f, 1.9063174f},
651 {5.4979978f, 1.9096732f},
658 TEST(polyfill2d, IssueT40777_colinear)
660 const float poly[][2] = {
661 {0.7, 0.37}, {0.7, 0}, {0.76, 0}, {0.76, 0.4}, {0.83, 0.4}, {0.83, 0}, {0.88, 0},
662 {0.88, 0.4}, {0.94, 0.4}, {0.94, 0}, {1, 0}, {1, 0.4}, {0.03, 0.62}, {0.03, 0.89},
663 {0.59, 0.89}, {0.03, 1}, {0, 1}, {0, 0}, {0.03, 0}, {0.03, 0.37},
669 TEST(polyfill2d, IssueT41986_axis_align)
671 const float poly[][2] = {
672 {-0.25, -0.07}, {-0.25, 0.27}, {-1.19, 0.14}, {-0.06, 0.73}, {0.17, 1.25},
673 {-0.25, 1.07}, {-0.38, 1.02}, {-0.25, 0.94}, {-0.40, 0.90}, {-0.41, 0.86},
674 {-0.34, 0.83}, {-0.25, 0.82}, {-0.66, 0.73}, {-0.56, 1.09}, {-0.25, 1.10},
675 {0.00, 1.31}, {-0.03, 1.47}, {-0.25, 1.53}, {0.12, 1.62}, {0.36, 1.07},
676 {0.12, 0.67}, {0.29, 0.57}, {0.44, 0.45}, {0.57, 0.29}, {0.66, 0.12},
677 {0.68, 0.06}, {0.57, -0.36}, {-0.25, -0.37}, {0.49, -0.74}, {-0.59, -1.21},
678 {-0.25, -0.15}, {-0.46, -0.52}, {-1.08, -0.83}, {-1.45, -0.33}, {-1.25, -0.04}};
684 TEST(polyfill2d, IssueT52834_axis_align_co_linear)
686 const float poly[][2] = {
687 {40, 0}, {36, 0}, {36, 5}, {35, 5}, {35, 0}, {30, 0}, {30, 5}, {29, 5},
688 {29, 0}, {24, 0}, {24, 3}, {23, 4}, {23, 0}, {18, 0}, {18, 5}, {17, 5},
689 {17, 0}, {12, 0}, {12, 5}, {11, 5}, {11, 0}, {6, 0}, {6, 5}, {5, 5},
690 {5, 0}, {0, 0}, {0, 5}, {-1, 5}, {-1, 0}, {-6, 0}, {-9, -3}, {-6, -3},
691 {-6, -2}, {-1, -2}, {0, -2}, {5, -2}, {6, -2}, {11, -2}, {12, -2}, {17, -2},
692 {18, -2}, {23, -2}, {24, -2}, {29, -2}, {30, -2}, {35, -2}, {36, -2}, {40, -2},
700 TEST(polyfill2d, IssueT67109_axis_align_co_linear_a)
702 const float poly[][2] = {
703 {3.2060661, -11.438997},
704 {2.8720665, -5.796999},
705 {-2.8659325, -5.796999},
706 {-2.8659325, -8.307999},
707 {-3.2549324, -11.438997},
708 {-2.8659325, -5.4869995},
709 {2.8720665, -5.4869995},
710 {2.8720665, -2.9759989},
711 {2.8720665, -2.6659985},
712 {2.8720665, -0.15499878},
718 TEST(polyfill2d, IssueT67109_axis_align_co_linear_b)
720 const float poly[][2] = {
721 {32.41416, -12.122593},
722 {28.094929, -8.477332},
723 {24.141455, -12.636018},
724 {25.96133, -14.366093},
725 {27.96254, -16.805279},
726 {23.916779, -12.422427},
727 {27.870255, -8.263744},
728 {26.050375, -6.533667},
729 {25.825695, -6.320076},
730 {24.00582, -4.5899982},
736 TEST(polyfill2d, IssueT67109_axis_align_co_linear_c)
738 const float poly[][2] = {
739 {-67.10034, 43.677097},
740 {-63.253956, 61.399143},
741 {-80.98382, 66.36057},
742 {-83.15499, 58.601795},
743 {-87.06422, 49.263668},
744 {-80.71576, 67.31843},
745 {-62.985912, 62.35701},
746 {-60.81475, 70.11576},
747 {-60.546703, 71.07365},
748 {-58.37554, 78.83239},
typedef float(TangentPoint)[2]
Generic array manipulation API.
#define BLI_array_reverse(arr, arr_len)
void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP free_value)
void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val)
EdgeHashIterator * BLI_edgehashIterator_new(EdgeHash *eh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
EdgeHash * BLI_edgehash_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
int BLI_edgehash_len(const EdgeHash *eh) ATTR_WARN_UNUSED_RESULT
void ** BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT
BLI_INLINE void BLI_edgehashIterator_step(EdgeHashIterator *ehi)
void BLI_edgehashIterator_free(EdgeHashIterator *ehi)
BLI_INLINE bool BLI_edgehashIterator_isDone(const EdgeHashIterator *ehi)
BLI_INLINE void ** BLI_edgehashIterator_getValue_p(EdgeHashIterator *ehi)
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
A min-heap / priority queue ADT.
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
MINLINE float area_tri_v2(const float v1[2], const float v2[2], const float v3[2])
MINLINE float cross_tri_v2(const float v1[2], const float v2[2], const float v3[2])
float area_poly_v2(const float verts[][2], unsigned int nr)
MINLINE void copy_v2_v2(float r[2], const float a[2])
void BLI_memarena_free(struct MemArena *ma) ATTR_NONNULL(1)
struct MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
#define BLI_POLYFILL_ARENA_SIZE
void BLI_polyfill_calc(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3])
#define BLI_POLYFILL_ALLOC_NGON_RESERVE
void BLI_polyfill_beautify(const float(*coords)[2], unsigned int coords_num, unsigned int(*tris)[3], struct MemArena *arena, struct Heap *eheap)
TEST(polyfill2d, TriangleCCW)
static void test_polyfill_topology(const float[][2], const unsigned int poly_num, const unsigned int tris[][3], const unsigned int tris_num)
static void test_polyfill_simple(const float[][2], const unsigned int poly_num, const unsigned int tris[][3], const unsigned int tris_num)
static void test_polyfill_winding(const float poly[][2], const unsigned int, const unsigned int tris[][3], const unsigned int tris_num)
static void test_polyfill_area(const float poly[][2], const unsigned int poly_num, const unsigned int tris[][3], const unsigned int tris_num)
static void test_polyfill_template_flip_sign(const char *id, bool is_degenerate, const float poly[][2], const unsigned int poly_num, unsigned int tris[][3], const unsigned int tris_num)
static void test_polyfill_template_main(const char *id, bool is_degenerate, const float poly[][2], const unsigned int poly_num, unsigned int tris[][3], const unsigned int tris_num)
static void test_polyfill_template(const char *id, bool is_degenerate, const float poly[][2], const unsigned int poly_num, unsigned int tris[][3], const unsigned int tris_num)
static void polyfill_to_obj(const char *id, const float poly[][2], const unsigned int poly_num, const unsigned int tris[][3], const unsigned int tris_num)
#define TEST_POLYFILL_TEMPLATE_STATIC(poly, is_degenerate)
static void test_polyfill_template_check(const char *id, bool is_degenerate, const float poly[][2], const unsigned int poly_num, const unsigned int tris[][3], const unsigned int tris_num)
static void test_valid_polyfill_prepare(unsigned int tris[][3], unsigned int tris_num)
size_t BLI_snprintf(char *__restrict dst, size_t maxncpy, const char *__restrict format,...) ATTR_NONNULL(1
#define UNPACK3_EX(pre, a, post)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
ATTR_WARN_UNUSED_RESULT const BMVert * v2
SyclQueue void void size_t num_bytes void
void(* MEM_freeN)(void *vmemh)
void *(* MEM_callocN)(size_t len, const char *str)
void *(* MEM_mallocN)(size_t len, const char *str)