Blender V5.3
scanfill_utils.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <cstdlib>
10
11#include "DNA_listBase.h"
12
13#include "MEM_guardedalloc.h"
14
15#include "BLI_listbase.hh"
16#include "BLI_map.hh"
17#include "BLI_math_geom_c.hh"
18#include "BLI_math_vector_c.hh"
19#include "BLI_utildefines.hh"
20
21#include "BLI_scanfill.hh" /* own include */
22
23#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
24
25namespace blender {
26
31
34 float co[3];
35
36 /* newly created vertex */
38};
39
40#define V_ISISECT 1
41#define E_ISISECT 1
42#define E_ISDELETE 2
43
44#define EFLAG_SET(eed, val) \
45 { \
46 CHECK_TYPE(eed, ScanFillEdge *); \
47 (eed)->user_flag = (eed)->user_flag | uint(val); \
48 } \
49 (void)0
50#if 0
51# define EFLAG_CLEAR(eed, val) \
52 { \
53 CHECK_TYPE(eed, ScanFillEdge *); \
54 (eed)->user_flag = (eed)->user_flag & ~uint(val); \
55 } \
56 (void)0
57#endif
58
59#define VFLAG_SET(eve, val) \
60 { \
61 CHECK_TYPE(eve, ScanFillVert *); \
62 (eve)->user_flag = (eve)->user_flag | uint(val); \
63 } \
64 (void)0
65#if 0
66# define VFLAG_CLEAR(eve, val) \
67 { \
68 CHECK_TYPE(eve, ScanFillVert *); \
69 (eve)->user_flags = (eve)->user_flag & ~uint(val); \
70 } \
71 (void)0
72#endif
73
74#if 0
75void BLI_scanfill_obj_dump(ScanFillContext *sf_ctx)
76{
77 FILE *f = fopen("test.obj", "w");
78 uint i = 1;
79
80 ScanFillVert *eve;
81 ScanFillEdge *eed;
82
83 for (eve = sf_ctx->fillvertbase.first_; eve; eve = eve->next, i++) {
84 fprintf(f, "v %f %f %f\n", UNPACK3(eve->co));
85 eve->keyindex = i;
86 }
87 for (eed = sf_ctx->filledgebase.first_; eed; eed = eed->next) {
88 fprintf(f, "f %d %d\n", eed->v1->keyindex, eed->v2->keyindex);
89 }
90 fclose(f);
91}
92#endif
93
95
96static ListBaseT<LinkData> *edge_isect_ls_ensure(IsectMap *isect_hash, ScanFillEdge *eed)
97{
98 return isect_hash->lookup_or_add_cb(
99 eed, []() { return MEM_new_zeroed<ListBaseT<LinkData>>("edge_isect_ls_ensure"); });
100}
101
102static ListBaseT<LinkData> *edge_isect_ls_add(IsectMap *isect_hash,
103 ScanFillEdge *eed,
104 ScanFillIsect *isect)
105{
106 ListBaseT<LinkData> *e_ls;
107 LinkData *isect_link;
108 e_ls = edge_isect_ls_ensure(isect_hash, eed);
109 isect_link = MEM_new_zeroed<LinkData>(__func__);
110 isect_link->data = isect;
111 EFLAG_SET(eed, E_ISISECT);
112 BLI_addtail(e_ls, isect_link);
113 return e_ls;
114}
115
116static int edge_isect_ls_sort_cb(void *thunk, const void *def_a_ptr, const void *def_b_ptr)
117{
118 const float *co = static_cast<const float *>(thunk);
119
120 const ScanFillIsect *i_a = static_cast<const ScanFillIsect *>(
121 (static_cast<const LinkData *>(def_a_ptr))->data);
122 const ScanFillIsect *i_b = static_cast<const ScanFillIsect *>(
123 (static_cast<const LinkData *>(def_b_ptr))->data);
124 const float a = len_squared_v2v2(co, i_a->co);
125 const float b = len_squared_v2v2(co, i_b->co);
126
127 if (a > b) {
128 return -1;
129 }
130
131 return (a < b);
132}
133
134static ScanFillEdge *edge_step(PolyInfo *poly_info,
135 const ushort poly_nr,
136 ScanFillVert *v_prev,
137 ScanFillVert *v_curr,
138 ScanFillEdge *e_curr)
139{
140 ScanFillEdge *eed;
141
142 BLI_assert(ELEM(v_prev, e_curr->v1, e_curr->v2));
143 BLI_assert(ELEM(v_curr, e_curr->v1, e_curr->v2));
144
145 eed = (e_curr->next && e_curr != poly_info[poly_nr].edge_last) ? e_curr->next :
146 poly_info[poly_nr].edge_first;
147 if (ELEM(v_curr, eed->v1, eed->v2) == true && ELEM(v_prev, eed->v1, eed->v2) == false) {
148 return eed;
149 }
150
151 eed = (e_curr->prev && e_curr != poly_info[poly_nr].edge_first) ? e_curr->prev :
152 poly_info[poly_nr].edge_last;
153 if (ELEM(v_curr, eed->v1, eed->v2) == true && ELEM(v_prev, eed->v1, eed->v2) == false) {
154 return eed;
155 }
156
157 BLI_assert(0);
158 return nullptr;
159}
160
162 PolyInfo *poly_info,
163 const ushort poly_nr,
164 ListBaseT<ScanFillEdge> *filledgebase)
165{
166 PolyInfo *pi = &poly_info[poly_nr];
167 IsectMap *isect_hash = nullptr;
168 ListBaseT<ScanFillIsect> isect_lb = {nullptr};
169
170 /* warning, O(n2) check here, should use spatial lookup */
171 {
172 ScanFillEdge *eed;
173
174 for (eed = pi->edge_first; eed; eed = (eed == pi->edge_last) ? nullptr : eed->next) {
175 ScanFillEdge *eed_other;
176
177 for (eed_other = eed->next; eed_other;
178 eed_other = (eed_other == pi->edge_last) ? nullptr : eed_other->next)
179 {
180 if (!ELEM(eed->v1, eed_other->v1, eed_other->v2) &&
181 !ELEM(eed->v2, eed_other->v1, eed_other->v2) && (eed != eed_other))
182 {
183 /* check isect */
184 float pt[2];
185 BLI_assert(eed != eed_other);
186
188 eed->v1->co, eed->v2->co, eed_other->v1->co, eed_other->v2->co, pt) == 1)
189 {
190 ScanFillIsect *isect;
191
192 if (isect_hash == nullptr) [[unlikely]] {
193 isect_hash = MEM_new<IsectMap>(__func__);
194 }
195
196 isect = MEM_new_uninitialized<ScanFillIsect>(__func__);
197
198 BLI_addtail(&isect_lb, isect);
199
200 copy_v2_v2(isect->co, pt);
201 isect->co[2] = eed->v1->co[2];
202 isect->v = BLI_scanfill_vert_add(sf_ctx, isect->co);
203
204 /* NOTE: vert may belong to 2 polys now */
205 isect->v->poly_nr = eed->v1->poly_nr;
206
207 VFLAG_SET(isect->v, V_ISISECT);
208 edge_isect_ls_add(isect_hash, eed, isect);
209 edge_isect_ls_add(isect_hash, eed_other, isect);
210 }
211 }
212 }
213 }
214 }
215
216 if (isect_hash == nullptr) {
217 return false;
218 }
219
220 /* now subdiv the edges */
221 {
222 ScanFillEdge *eed;
223
224 for (eed = pi->edge_first; eed; eed = (eed == pi->edge_last) ? nullptr : eed->next) {
225 if (eed->user_flag & E_ISISECT) {
226 ListBaseT<LinkData> *e_ls = isect_hash->lookup_default(eed, nullptr);
227
228 if (e_ls == nullptr) [[unlikely]] {
229 /* only happens in very rare cases (entirely overlapping splines).
230 * in this case we can't do much useful. but at least don't crash */
231 continue;
232 }
233
234 /* Maintain correct terminating edge. */
235 if (pi->edge_last == eed) {
236 pi->edge_last = nullptr;
237 }
238
239 if (e_ls->is_single() == false) {
241 }
242
243 /* move original edge to filledgebase and add replacement
244 * (which gets subdivided next) */
245 {
246 ScanFillEdge *eed_tmp;
247 eed_tmp = BLI_scanfill_edge_add(sf_ctx, eed->v1, eed->v2);
248 BLI_remlink(&sf_ctx->filledgebase, eed_tmp);
249 BLI_insertlinkafter(&sf_ctx->filledgebase, eed, eed_tmp);
250 BLI_remlink(&sf_ctx->filledgebase, eed);
251 BLI_addtail(filledgebase, eed);
252 if (pi->edge_first == eed) {
253 pi->edge_first = eed_tmp;
254 }
255 eed = eed_tmp;
256 }
257
258 for (LinkData &isect_link : *e_ls) {
259 ScanFillIsect *isect = static_cast<ScanFillIsect *>(isect_link.data);
260 ScanFillEdge *eed_subd;
261
262 eed_subd = BLI_scanfill_edge_add(sf_ctx, isect->v, eed->v2);
263 eed_subd->poly_nr = poly_nr;
264 eed->v2 = isect->v;
265
266 BLI_remlink(&sf_ctx->filledgebase, eed_subd);
267 BLI_insertlinkafter(&sf_ctx->filledgebase, eed, eed_subd);
268
269 /* step to the next edge and continue dividing */
270 eed = eed_subd;
271 }
272
273 e_ls->free_no_destruct();
274 MEM_delete(e_ls);
275
276 if (pi->edge_last == nullptr) {
277 pi->edge_last = eed;
278 }
279 }
280 }
281 }
282
283 isect_lb.free_no_destruct();
284 MEM_delete(isect_hash);
285
286 {
287 ScanFillEdge *e_init;
288 ScanFillEdge *e_curr;
289 ScanFillEdge *e_next;
290
291 ScanFillVert *v_prev;
292 ScanFillVert *v_curr;
293
294 bool inside = false;
295
296 /* first vert */
297#if 0
298 e_init = pi->edge_last;
299 e_curr = e_init;
300 e_next = pi->edge_first;
301
302 v_prev = e_curr->v1;
303 v_curr = e_curr->v2;
304#else
305
306 /* find outside vertex */
307 {
308 ScanFillEdge *eed;
309 ScanFillEdge *eed_prev;
310 float min_x = FLT_MAX;
311
312 e_curr = pi->edge_last;
313 e_next = pi->edge_first;
314
315 eed_prev = pi->edge_last;
316 for (eed = pi->edge_first; eed; eed = (eed == pi->edge_last) ? nullptr : eed->next) {
317 if (eed->v2->co[0] < min_x) {
318 min_x = eed->v2->co[0];
319 e_curr = eed_prev;
320 e_next = eed;
321 }
322 eed_prev = eed;
323 }
324
325 e_init = e_curr;
326 v_prev = e_curr->v1;
327 v_curr = e_curr->v2;
328 }
329#endif
330
331 BLI_assert(e_curr->poly_nr == poly_nr);
332 BLI_assert(pi->edge_last->poly_nr == poly_nr);
333
334 do {
335 ScanFillVert *v_next;
336
337 v_next = (e_next->v1 == v_curr) ? e_next->v2 : e_next->v1;
338 BLI_assert(ELEM(v_curr, e_next->v1, e_next->v2));
339
340 /* track intersections */
341 if (inside) {
342 EFLAG_SET(e_next, E_ISDELETE);
343 }
344 if (v_next->user_flag & V_ISISECT) {
345 inside = !inside;
346 }
347 /* now step... */
348
349 v_prev = v_curr;
350 v_curr = v_next;
351 e_curr = e_next;
352
353 e_next = edge_step(poly_info, poly_nr, v_prev, v_curr, e_curr);
354
355 } while (e_curr != e_init);
356 }
357
358 return true;
359}
360
362 ListBaseT<ScanFillVert> *remvertbase,
363 ListBaseT<ScanFillEdge> *remedgebase)
364{
365 const uint poly_num = uint(sf_ctx->poly_nr) + 1;
366 bool changed = false;
367
368 if (sf_ctx->poly_nr == SF_POLY_UNSET) [[unlikely]] {
369 return false;
370 }
371
372 PolyInfo *poly_info = MEM_new_array_zeroed<PolyInfo>(poly_num, __func__);
373
374 /* get the polygon span */
375 if (sf_ctx->poly_nr == 0) {
376 poly_info->edge_first = sf_ctx->filledgebase.first();
377 poly_info->edge_last = sf_ctx->filledgebase.last();
378 }
379 else {
380 ushort poly_nr = 0;
381
382 for (auto [eed_index, eed] : sf_ctx->filledgebase.enumerate()) {
383 BLI_assert(eed.poly_nr == eed.v1->poly_nr);
384 BLI_assert(eed.poly_nr == eed.v2->poly_nr);
385
386 if ((poly_info[poly_nr].edge_last != nullptr) &&
387 (poly_info[poly_nr].edge_last->poly_nr != eed.poly_nr))
388 {
389 poly_nr++;
390 }
391
392 if (poly_info[poly_nr].edge_first == nullptr) {
393 poly_info[poly_nr].edge_first = &eed;
394 poly_info[poly_nr].edge_last = &eed;
395 }
396 else if (poly_info[poly_nr].edge_last->poly_nr == eed.poly_nr) {
397 poly_info[poly_nr].edge_last = &eed;
398 }
399
400 BLI_assert(poly_info[poly_nr].edge_first->poly_nr == poly_info[poly_nr].edge_last->poly_nr);
401 }
402 }
403
404 /* self-intersect each polygon */
405 {
406 ushort poly_nr;
407 for (poly_nr = 0; poly_nr < poly_num; poly_nr++) {
408 changed |= scanfill_preprocess_self_isect(sf_ctx, poly_info, poly_nr, remedgebase);
409 }
410 }
411
412 MEM_delete(poly_info);
413
414 if (changed == false) {
415 return false;
416 }
417
418 /* move free edges into their own list */
419 {
420 for (ScanFillEdge &eed : sf_ctx->filledgebase.items_mutable()) {
421 if (eed.user_flag & E_ISDELETE) {
422 BLI_remlink(&sf_ctx->filledgebase, &eed);
423 BLI_addtail(remedgebase, &eed);
424 }
425 }
426 }
427
428 /* move free vertices into their own list */
429 {
430 for (ScanFillVert &eve : sf_ctx->fillvertbase) {
431 eve.user_flag = 0;
433 }
434 for (ScanFillEdge &eed : sf_ctx->filledgebase) {
435 eed.v1->user_flag = 1;
436 eed.v2->user_flag = 1;
438 }
439
440 for (ScanFillVert &eve : sf_ctx->fillvertbase.items_mutable()) {
441 if (eve.user_flag != 1) {
442 BLI_remlink(&sf_ctx->fillvertbase, &eve);
443 BLI_addtail(remvertbase, &eve);
444 }
445 else {
446 eve.user_flag = 0;
447 }
448 }
449 }
450
451 /* polygon id's are no longer meaningful,
452 * when removing self intersections we may have created new isolated polys */
453 sf_ctx->poly_nr = SF_POLY_UNSET;
454
455#if 0
456 BLI_scanfill_view3d_dump(sf_ctx);
457 BLI_scanfill_obj_dump(sf_ctx);
458#endif
459
460 return changed;
461}
462
463} // namespace blender
#define SF_POLY_UNSET
These structs are the foundation for all linked lists in the library system.
Read Blender memory allocation and freeing.
#define UNPACK3(a)
#define ELEM(...)
Value lookup_default(const Key &key, const Value &default_value) const
Definition BLI_map.hh:570
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
Definition BLI_map.hh:620
#define FLT_MAX
BMesh Iterators.
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
unsigned int uint
Definition BKE_text.h:55
static int edge_isect_ls_sort_cb(void *thunk, const void *def_a_ptr, const void *def_b_ptr)
bool BLI_scanfill_calc_self_isect(ScanFillContext *sf_ctx, ListBaseT< ScanFillVert > *remvertbase, ListBaseT< ScanFillEdge > *remedgebase)
MINLINE void copy_v2_v2(float r[2], const float a[2])
unsigned short ushort
Definition BKE_text.h:56
static bool scanfill_preprocess_self_isect(ScanFillContext *sf_ctx, PolyInfo *poly_info, const ushort poly_nr, ListBaseT< ScanFillEdge > *filledgebase)
int isect_seg_seg_v2_point(const float v0[2], const float v1[2], const float v2[2], const float v3[2], float r_vi[2])
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
void void void BLI_listbase_sort_r(ListBase *listbase, int(*cmp)(void *, const void *, const void *), void *thunk) ATTR_NONNULL(1
Definition listbase.cc:328
void BLI_remlink(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:138
void BLI_insertlinkafter(ListBase *listbase, void *vprevlink, void *vnewlink) ATTR_NONNULL(1)
Definition listbase.cc:339
struct ScanFillVert * BLI_scanfill_vert_add(ScanFillContext *sf_ctx, const float vec[3])
Definition scanfill.cc:105
struct ScanFillEdge * BLI_scanfill_edge_add(ScanFillContext *sf_ctx, struct ScanFillVert *v1, struct ScanFillVert *v2)
Definition scanfill.cc:127
Map< ScanFillEdge *, ListBaseT< LinkData > * > IsectMap
void BLI_addtail(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:118
static BMEdge * edge_step(BMVert *v, BMEdge *edge, BMVert **r_next_vertex)
static ListBaseT< LinkData > * edge_isect_ls_ensure(IsectMap *isect_hash, ScanFillEdge *eed)
MINLINE float len_squared_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static ListBaseT< LinkData > * edge_isect_ls_add(IsectMap *isect_hash, ScanFillEdge *eed, ScanFillIsect *isect)
#define E_ISISECT
#define EFLAG_SET(eed, val)
#define VFLAG_SET(eve, val)
#define E_ISDELETE
#define V_ISISECT
ScanFillEdge * edge_first
ScanFillEdge * edge_last
ScanFillVert * vert_outer
ListBaseT< ScanFillEdge > filledgebase
ListBaseT< ScanFillVert > fillvertbase
struct ScanFillEdge * prev
unsigned short poly_nr
struct ScanFillVert * v2
struct ScanFillEdge * next
struct ScanFillVert * v1
unsigned short poly_nr