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