47 float min_xy[2], max_xy[2];
52struct ScanFillVertLink {
54 ScanFillEdge *edge_first, *edge_last;
61#define SF_EPSILON 0.00003f
62#define SF_EPSILON_SQ (SF_EPSILON * SF_EPSILON)
66#define SF_VERT_AVAILABLE 1
67#define SF_VERT_ZERO_LEN 2
74#define SF_EDGE_INTERNAL 2
78#define SF_POLY_VALID 1
84 const ScanFillVertLink *x1 =
static_cast<const ScanFillVertLink *
>(a1);
85 const ScanFillVertLink *x2 =
static_cast<const ScanFillVertLink *
>(a2);
87 if (x1->vert->xy[1] < x2->vert->xy[1]) {
90 if (x1->vert->xy[1] > x2->vert->xy[1]) {
93 if (x1->vert->xy[0] > x2->vert->xy[0]) {
96 if (x1->vert->xy[0] < x2->vert->xy[0]) {
113 sf_v->
tmp.p =
nullptr;
167 if (pf1->edges == 0 ||
pf2->edges == 0) {
171 if (
pf2->max_xy[0] < pf1->min_xy[0]) {
174 if (
pf2->max_xy[1] < pf1->min_xy[1]) {
178 if (
pf2->min_xy[0] > pf1->max_xy[0]) {
181 if (
pf2->min_xy[1] > pf1->max_xy[1]) {
190 const uint pf_target,
192 uint *__restrict target_map)
194 const PolyFill *pf_a = pf_list + pf_test;
195 for (
uint pf_b_index = pf_target + 1; pf_b_index < pf_len; pf_b_index++) {
196 if (target_map[pf_b_index] != pf_b_index) {
201 const PolyFill *pf_b = pf_list + pf_b_index;
203 target_map[pf_b_index] = pf_target;
226 pf1->verts +=
pf2->verts;
227 pf1->edges +=
pf2->edges;
229 pf1->max_xy[0] = std::max(pf1->max_xy[0],
pf2->max_xy[0]);
230 pf1->max_xy[1] = std::max(pf1->max_xy[1],
pf2->max_xy[1]);
232 pf1->min_xy[0] = std::min(pf1->min_xy[0],
pf2->min_xy[0]);
233 pf1->min_xy[1] = std::min(pf1->min_xy[1],
pf2->min_xy[1]);
235 pf1->f = (pf1->f |
pf2->f);
238 pf2->verts =
pf2->edges = 0;
246 inp = (
v2[0] - v1[0]) * (v1[1] - v3[1]) + (v1[1] -
v2[1]) * (v1[0] - v3[0]);
252 if (v1[0] == v3[0] && v1[1] == v3[1]) {
255 if (
v2[0] == v3[0] &&
v2[1] == v3[1]) {
266 float fac, fac1,
x,
y;
268 if (sc->edge_first ==
nullptr) {
269 sc->edge_first = sc->edge_last = eed;
277 fac1 = eed->
v2->
xy[1] -
y;
279 fac1 = 1.0e10f * (eed->
v2->
xy[0] -
x);
282 fac1 = (
x - eed->
v2->
xy[0]) / fac1;
285 for (
ed = sc->edge_first;
ed;
ed =
ed->next) {
287 if (
ed->v2 == eed->
v2) {
291 fac =
ed->v2->xy[1] -
y;
293 fac = 1.0e10f * (
ed->v2->xy[0] -
x);
296 fac = (
x -
ed->v2->xy[0]) / fac;
317 ScanFillVertLink *sc, scsearch;
321 if (eed->
v1->
xy[1] == eed->
v2->
xy[1]) {
322 if (eed->
v1->
xy[0] > eed->
v2->
xy[0]) {
328 else if (eed->
v1->
xy[1] < eed->
v2->
xy[1]) {
334 scsearch.vert = eed->
v1;
335 sc =
static_cast<ScanFillVertLink *
>(
336 bsearch(&scsearch, scdata,
len,
sizeof(ScanFillVertLink),
vergscdata));
338 if (sc ==
nullptr) [[unlikely]] {
339 printf(
"Error in search edge: %p\n",
static_cast<void *
>(eed));
353 float minx, maxx, miny, maxy;
355 if (eed->
v1->
xy[0] < eed->
v2->
xy[0]) {
356 minx = eed->
v1->
xy[0];
357 maxx = eed->
v2->
xy[0];
360 minx = eed->
v2->
xy[0];
361 maxx = eed->
v1->
xy[0];
363 if (eve->
xy[0] >= minx && eve->
xy[0] <= maxx) {
364 if (eed->
v1->
xy[1] < eed->
v2->
xy[1]) {
365 miny = eed->
v1->
xy[1];
366 maxy = eed->
v2->
xy[1];
369 miny = eed->
v2->
xy[1];
370 maxy = eed->
v1->
xy[1];
372 if (eve->
xy[1] >= miny && eve->
xy[1] <= maxy) {
390 for (; !(ed1->
v1 == &eve || ed1->
v2 == &eve); ed1 = ed1->
next) {
394 if (ed1->
v1 == &eve) {
434 ListBaseT<ScanFillVert> *tempve,
435 ListBaseT<ScanFillEdge> *temped,
443 if (eve.poly_nr == nr) {
450 if (eed.poly_nr == nr) {
459 ScanFillVertLink *scdata;
460 ScanFillVertLink *sc =
nullptr, *sc1;
462 uint a,
b, verts, maxface, totface;
464 bool twoconnected =
false;
470 printf(
"vert: %x co: %f %f\n", &eve, eve.
xy[0], eve.
xy[1]);
474 printf(
"edge: %x verts: %x %x\n", &eed, eed.
v1, eed.
v2);
512 sc->edge_first = sc->edge_last =
nullptr;
515 if (even->tmp.v ==
nullptr) {
524 qsort(scdata, verts,
sizeof(ScanFillVertLink),
vergscdata);
554 if (eed.
v1 != eed.
v2) {
562 if (eed.
v1 != eed.
v2) {
568 sc = sf_ctx->_scdata;
569 for (a = 0; a < verts; a++) {
570 printf(
"\nscvert: %x\n", sc->vert);
571 for (eed = sc->edge_first; eed; eed = eed->
next) {
572 printf(
" ed %x %x %x\n", eed, eed->
v1, eed->
v2);
595 for (a = 0; a < verts; a++) {
599 for (ed1 = sc->edge_first; ed1; ed1 = eed_next) {
600 eed_next = ed1->
next;
615 while (sc->edge_first) {
616 ed1 = sc->edge_first;
622 if (callLocalInterruptCallBack()){
626 if (totface >= maxface) {
631 if (ed2 ==
nullptr) {
632 sc->edge_first = sc->edge_last =
nullptr;
641 ScanFillVertLink *best_sc =
nullptr;
642 float angle_best_cos = -1.0f;
644 bool firsttime =
false;
651 if (v1 ==
v2 ||
v2 == v3) {
659 for (
b = a + 1;
b < verts;
b++, sc1++) {
661 if (sc1->vert->xy[1] <= miny) {
672 if (best_sc ==
nullptr) {
679 if (firsttime ==
false) {
684 const float angle_test_cos =
cos_v2v2v2(
v2->xy, v1->
xy, sc1->vert->xy);
685 if (angle_test_cos > angle_best_cos) {
687 angle_best_cos = angle_test_cos;
742 for (ed3 = sc1->edge_first; ed3; ed3 = ed3->
next) {
743 if ((ed3->
v1 == v1 && ed3->
v2 == v3) || (ed3->
v1 == v3 && ed3->
v2 == v1)) {
758 for (ed1 = sc->edge_first; ed1; ed1 = eed_next) {
759 eed_next = ed1->
next;
786 memset(sf_ctx, 0,
sizeof(*sf_ctx));
793 memset(sf_ctx, 0,
sizeof(*sf_ctx));
795 sf_ctx->
arena = arena;
801 sf_ctx->
arena =
nullptr;
828 ListBaseT<ScanFillVert> tempve;
829 ListBaseT<ScanFillEdge> temped;
830 PolyFill *pflist, *
pf;
831 float *min_xy_p, *max_xy_p;
857 bool vert_available =
false;
860 vert_available =
true;
865 if (!vert_available) [[unlikely]] {
925 for (; eed; eed = (toggle & 1) ? eed->
next : eed->
prev) {
976 printf(
"No vertices with 250 edges allowed!\n");
994 for (; eed; eed = eed_next) {
995 eed_next = (toggle & 1) ? eed->
next : eed->
prev;
1043 for (a = 0; a < poly; a++) {
1044 pf->edges =
pf->verts = 0;
1045 pf->min_xy[0] =
pf->min_xy[1] = 1.0e20f;
1046 pf->max_xy[0] =
pf->max_xy[1] = -1.0e20f;
1057 min_xy_p = pflist[eve.
poly_nr].min_xy;
1058 max_xy_p = pflist[eve.
poly_nr].max_xy;
1060 min_xy_p[0] = (min_xy_p[0]) < (eve.
xy[0]) ? (min_xy_p[0]) : (eve.
xy[0]);
1061 min_xy_p[1] = (min_xy_p[1]) < (eve.
xy[1]) ? (min_xy_p[1]) : (eve.
xy[1]);
1062 max_xy_p[0] = (max_xy_p[0]) > (eve.
xy[0]) ? (max_xy_p[0]) : (eve.
xy[0]);
1063 max_xy_p[1] = (max_xy_p[1]) > (eve.
xy[1]) ? (max_xy_p[1]) : (eve.
xy[1]);
1076 for (a = 0; a < poly; a++) {
1077 printf(
"poly:%d edges:%d verts:%d flag: %d\n", a,
pf->edges,
pf->verts,
pf->f);
1078 PRINT2(f, f,
pf->min[0],
pf->min[1]);
1083 uint *target_map = MEM_new_array<uint>(poly,
"polycache");
1086 for (a = 0; a < poly; a++) {
1087 if (target_map[a] != a) {
1094 for (a = 0; a < poly; a++) {
1095 if (target_map[a] != a) {
1096 PolyFill *pf_src = pflist + a;
1097 PolyFill *pf_dst = pflist + target_map[a];
1102 MEM_delete(target_map);
1108 for (a = 0; a < poly; a++) {
1109 printf(
"poly:%d edges:%d verts:%d flag: %d\n", a,
pf->edges,
pf->verts,
pf->f);
1124 for (a = 0; a < poly; a++) {
1125 if (
pf->edges > 1) {
#define BLI_SCANFILL_ARENA_SIZE
These structs are the foundation for all linked lists in the library system.
Read Blender memory allocation and freeing.
#define pf2(_x, _i)
Prefetch 128.
#define pf(_x, _i)
Prefetch 64.
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
void fill_index_range(MutableSpan< T > span, const T start=0)
MINLINE float min_ff(float a, float b)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
MINLINE void copy_v3_v3(float r[3], const float a[3])
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void BLI_scanfill_end(ScanFillContext *sf_ctx)
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
@ BLI_SCANFILL_CALC_LOOSE
@ BLI_SCANFILL_CALC_POLYS
@ BLI_SCANFILL_CALC_HOLES
@ BLI_SCANFILL_CALC_REMOVE_DOUBLES
void void void BLI_movelisttolist(ListBase *dst, ListBase *src) ATTR_NONNULL(1
static uint scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
void BLI_remlink(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
void BLI_scanfill_begin_arena(ScanFillContext *sf_ctx, struct MemArena *arena)
void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
struct ScanFillVert * BLI_scanfill_vert_add(ScanFillContext *sf_ctx, const float vec[3])
static void mergepolysSimp(ScanFillContext *sf_ctx, PolyFill *pf1, PolyFill *pf2)
void BLI_scanfill_begin(ScanFillContext *sf_ctx)
float cos_v2v2v2(const float p1[2], const float p2[2], const float p3[2]) ATTR_WARN_UNUSED_RESULT
MINLINE void zero_v3(float r[3])
void BLI_insertlinkbefore(ListBase *listbase, void *vnextlink, void *vnewlink) ATTR_NONNULL(1)
MINLINE bool equals_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
unsigned int BLI_scanfill_calc(ScanFillContext *sf_ctx, int flag)
struct ScanFillEdge * BLI_scanfill_edge_add(ScanFillContext *sf_ctx, struct ScanFillVert *v1, struct ScanFillVert *v2)
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
MINLINE float normalize_v3(float n[3])
MINLINE bool compare_v3v3(const float v1[3], const float v2[3], float limit) ATTR_WARN_UNUSED_RESULT
void BLI_scanfill_end_arena(ScanFillContext *sf_ctx, struct MemArena *arena)
void BLI_addtail(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
static bool boundisect(const PolyFill *pf2, const PolyFill *pf1)
static ScanFillVertLink * addedgetoscanlist(ScanFillVertLink *scdata, ScanFillEdge *eed, uint len)
unsigned int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, int flag, const float nor_proj[3])
static int vergscdata(const void *a1, const void *a2)
float dist_squared_to_line_v2(const float p[2], const float l1[2], const float l2[2])
static bool testedgeside(const float v1[2], const float v2[2], const float v3[2])
static bool boundinsideEV(const ScanFillEdge *eed, const ScanFillVert *eve)
static bool addedgetoscanvert(ScanFillVertLink *sc, ScanFillEdge *eed)
static void addfillface(ScanFillContext *sf_ctx, ScanFillVert *v1, ScanFillVert *v2, ScanFillVert *v3)
MINLINE void zero_v2(float r[2])
static void fill_target_map_recursive(const PolyFill *__restrict pf_list, const uint pf_len, const uint pf_target, const uint pf_test, uint *__restrict target_map)
static void splitlist(ScanFillContext *sf_ctx, ListBaseT< ScanFillVert > *tempve, ListBaseT< ScanFillEdge > *temped, ushort nr)
static void testvertexnearedge(ScanFillContext *sf_ctx)
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
MINLINE bool compare_v2v2(const float v1[2], const float v2[2], float limit) ATTR_WARN_UNUSED_RESULT
#define SF_VERT_AVAILABLE
ListBaseT< ScanFillFace > fillfacebase
ListBaseT< ScanFillEdge > filledgebase
ListBaseT< ScanFillVert > fillvertbase
struct ScanFillEdge * prev
union blender::ScanFillEdge::@262251053107234334274134243151221246013035300046 tmp
struct ScanFillEdge * next
union blender::ScanFillVert::@124355022001164321030006076112165043115032300246 tmp