Blender  V3.3
scanfill.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2001-2002 NaN Holding BV. All rights reserved. */
3 
17 #include <limits.h>
18 #include <math.h>
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include <string.h>
22 
23 #include "MEM_guardedalloc.h"
24 
25 #include "BLI_listbase.h"
26 #include "BLI_math.h"
27 #include "BLI_memarena.h"
28 #include "BLI_utildefines.h"
29 
30 #include "BLI_scanfill.h" /* own include */
31 
32 #include "BLI_strict_flags.h"
33 
34 /* local types */
35 typedef struct PolyFill {
36  unsigned int edges, verts;
37  float min_xy[2], max_xy[2];
38  unsigned short nr;
39  bool f;
41 
42 typedef struct ScanFillVertLink {
46 
47 /* local funcs */
48 
49 #define SF_EPSILON 0.00003f
50 #define SF_EPSILON_SQ (SF_EPSILON * SF_EPSILON)
51 
53 #define SF_VERT_NEW 0 /* all new verts have this flag set */
54 #define SF_VERT_AVAILABLE 1 /* available - in an edge */
55 #define SF_VERT_ZERO_LEN 2
56 
58 /* Optionally set ScanFillEdge f to this to mark original boundary edges.
59  * Only needed if there are internal diagonal edges passed to BLI_scanfill_calc. */
60 #define SF_EDGE_NEW 0 /* all new edges have this flag set */
61 // #define SF_EDGE_BOUNDARY 1 /* UNUSED */
62 #define SF_EDGE_INTERNAL 2 /* edge is created while scan-filling */
63 
65 #define SF_POLY_NEW 0 /* all polys initialized to this */
66 #define SF_POLY_VALID 1 /* has at least 3 verts */
67 
68 /* **** FUNCTIONS FOR QSORT *************************** */
69 
70 static int vergscdata(const void *a1, const void *a2)
71 {
72  const ScanFillVertLink *x1 = a1, *x2 = a2;
73 
74  if (x1->vert->xy[1] < x2->vert->xy[1]) {
75  return 1;
76  }
77  if (x1->vert->xy[1] > x2->vert->xy[1]) {
78  return -1;
79  }
80  if (x1->vert->xy[0] > x2->vert->xy[0]) {
81  return 1;
82  }
83  if (x1->vert->xy[0] < x2->vert->xy[0]) {
84  return -1;
85  }
86 
87  return 0;
88 }
89 
90 static int vergpoly(const void *a1, const void *a2)
91 {
92  const PolyFill *x1 = a1, *x2 = a2;
93 
94  if (x1->min_xy[0] > x2->min_xy[0]) {
95  return 1;
96  }
97  if (x1->min_xy[0] < x2->min_xy[0]) {
98  return -1;
99  }
100  if (x1->min_xy[1] > x2->min_xy[1]) {
101  return 1;
102  }
103  if (x1->min_xy[1] < x2->min_xy[1]) {
104  return -1;
105  }
106 
107  return 0;
108 }
109 
110 /* **** FILL ROUTINES *************************** */
111 
113 {
114  ScanFillVert *sf_v;
115 
116  sf_v = BLI_memarena_alloc(sf_ctx->arena, sizeof(ScanFillVert));
117 
118  BLI_addtail(&sf_ctx->fillvertbase, sf_v);
119 
120  sf_v->tmp.p = NULL;
121  copy_v3_v3(sf_v->co, vec);
122 
123  /* just zero out the rest */
124  zero_v2(sf_v->xy);
125  sf_v->keyindex = 0;
126  sf_v->poly_nr = sf_ctx->poly_nr;
127  sf_v->edge_count = 0;
128  sf_v->f = SF_VERT_NEW;
129  sf_v->user_flag = 0;
130 
131  return sf_v;
132 }
133 
135 {
136  ScanFillEdge *sf_ed;
137 
138  sf_ed = BLI_memarena_alloc(sf_ctx->arena, sizeof(ScanFillEdge));
139  BLI_addtail(&sf_ctx->filledgebase, sf_ed);
140 
141  sf_ed->v1 = v1;
142  sf_ed->v2 = v2;
143 
144  /* just zero out the rest */
145  sf_ed->poly_nr = sf_ctx->poly_nr;
146  sf_ed->f = SF_EDGE_NEW;
147  sf_ed->user_flag = 0;
148  sf_ed->tmp.c = 0;
149 
150  return sf_ed;
151 }
152 
153 static void addfillface(ScanFillContext *sf_ctx,
154  ScanFillVert *v1,
155  ScanFillVert *v2,
156  ScanFillVert *v3)
157 {
158  /* does not make edges */
159  ScanFillFace *sf_tri;
160 
161  sf_tri = BLI_memarena_alloc(sf_ctx->arena, sizeof(ScanFillFace));
162  BLI_addtail(&sf_ctx->fillfacebase, sf_tri);
163 
164  sf_tri->v1 = v1;
165  sf_tri->v2 = v2;
166  sf_tri->v3 = v3;
167 }
168 
169 static bool boundisect(PolyFill *pf2, PolyFill *pf1)
170 {
171  /* has pf2 been touched (intersected) by pf1 ? with bounding box */
172  /* test first if polys exist */
173 
174  if (pf1->edges == 0 || pf2->edges == 0) {
175  return false;
176  }
177 
178  if (pf2->max_xy[0] < pf1->min_xy[0]) {
179  return false;
180  }
181  if (pf2->max_xy[1] < pf1->min_xy[1]) {
182  return false;
183  }
184 
185  if (pf2->min_xy[0] > pf1->max_xy[0]) {
186  return false;
187  }
188  if (pf2->min_xy[1] > pf1->max_xy[1]) {
189  return false;
190  }
191 
192  /* join */
193  if (pf2->max_xy[0] < pf1->max_xy[0]) {
194  pf2->max_xy[0] = pf1->max_xy[0];
195  }
196  if (pf2->max_xy[1] < pf1->max_xy[1]) {
197  pf2->max_xy[1] = pf1->max_xy[1];
198  }
199 
200  if (pf2->min_xy[0] > pf1->min_xy[0]) {
201  pf2->min_xy[0] = pf1->min_xy[0];
202  }
203  if (pf2->min_xy[1] > pf1->min_xy[1]) {
204  pf2->min_xy[1] = pf1->min_xy[1];
205  }
206 
207  return true;
208 }
209 
210 /* add pf2 to pf1 */
211 static void mergepolysSimp(ScanFillContext *sf_ctx, PolyFill *pf1, PolyFill *pf2)
212 {
213  ScanFillVert *eve;
214  ScanFillEdge *eed;
215 
216  /* replace old poly numbers */
217  for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
218  if (eve->poly_nr == pf2->nr) {
219  eve->poly_nr = pf1->nr;
220  }
221  }
222 
223  for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
224  if (eed->poly_nr == pf2->nr) {
225  eed->poly_nr = pf1->nr;
226  }
227  }
228 
229  pf1->verts += pf2->verts;
230  pf1->edges += pf2->edges;
231  pf2->verts = pf2->edges = 0;
232  pf1->f = (pf1->f | pf2->f);
233 }
234 
235 static bool testedgeside(const float v1[2], const float v2[2], const float v3[2])
236 /* is v3 to the right of v1-v2 ? With exception: v3 == v1 || v3 == v2 */
237 {
238  float inp;
239 
240  inp = (v2[0] - v1[0]) * (v1[1] - v3[1]) + (v1[1] - v2[1]) * (v1[0] - v3[0]);
241 
242  if (inp < 0.0f) {
243  return false;
244  }
245  if (inp == 0.0f) {
246  if (v1[0] == v3[0] && v1[1] == v3[1]) {
247  return false;
248  }
249  if (v2[0] == v3[0] && v2[1] == v3[1]) {
250  return false;
251  }
252  }
253  return true;
254 }
255 
257 {
258  /* find first edge to the right of eed, and insert eed before that */
259  ScanFillEdge *ed;
260  float fac, fac1, x, y;
261 
262  if (sc->edge_first == NULL) {
263  sc->edge_first = sc->edge_last = eed;
264  eed->prev = eed->next = NULL;
265  return 1;
266  }
267 
268  x = eed->v1->xy[0];
269  y = eed->v1->xy[1];
270 
271  fac1 = eed->v2->xy[1] - y;
272  if (fac1 == 0.0f) {
273  fac1 = 1.0e10f * (eed->v2->xy[0] - x);
274  }
275  else {
276  fac1 = (x - eed->v2->xy[0]) / fac1;
277  }
278 
279  for (ed = sc->edge_first; ed; ed = ed->next) {
280 
281  if (ed->v2 == eed->v2) {
282  return false;
283  }
284 
285  fac = ed->v2->xy[1] - y;
286  if (fac == 0.0f) {
287  fac = 1.0e10f * (ed->v2->xy[0] - x);
288  }
289  else {
290  fac = (x - ed->v2->xy[0]) / fac;
291  }
292 
293  if (fac > fac1) {
294  break;
295  }
296  }
297  if (ed) {
298  BLI_insertlinkbefore((ListBase *)&(sc->edge_first), ed, eed);
299  }
300  else {
301  BLI_addtail((ListBase *)&(sc->edge_first), eed);
302  }
303 
304  return true;
305 }
306 
308  ScanFillEdge *eed,
309  unsigned int len)
310 {
311  /* inserts edge at correct location in ScanFillVertLink list */
312  /* returns sc when edge already exists */
313  ScanFillVertLink *sc, scsearch;
314  ScanFillVert *eve;
315 
316  /* which vert is left-top? */
317  if (eed->v1->xy[1] == eed->v2->xy[1]) {
318  if (eed->v1->xy[0] > eed->v2->xy[0]) {
319  eve = eed->v1;
320  eed->v1 = eed->v2;
321  eed->v2 = eve;
322  }
323  }
324  else if (eed->v1->xy[1] < eed->v2->xy[1]) {
325  eve = eed->v1;
326  eed->v1 = eed->v2;
327  eed->v2 = eve;
328  }
329  /* find location in list */
330  scsearch.vert = eed->v1;
331  sc = (ScanFillVertLink *)bsearch(&scsearch, scdata, len, sizeof(ScanFillVertLink), vergscdata);
332 
333  if (UNLIKELY(sc == NULL)) {
334  printf("Error in search edge: %p\n", (void *)eed);
335  }
336  else if (addedgetoscanvert(sc, eed) == false) {
337  return sc;
338  }
339 
340  return NULL;
341 }
342 
346 static bool boundinsideEV(ScanFillEdge *eed, ScanFillVert *eve)
347 {
348  float minx, maxx, miny, maxy;
349 
350  if (eed->v1->xy[0] < eed->v2->xy[0]) {
351  minx = eed->v1->xy[0];
352  maxx = eed->v2->xy[0];
353  }
354  else {
355  minx = eed->v2->xy[0];
356  maxx = eed->v1->xy[0];
357  }
358  if (eve->xy[0] >= minx && eve->xy[0] <= maxx) {
359  if (eed->v1->xy[1] < eed->v2->xy[1]) {
360  miny = eed->v1->xy[1];
361  maxy = eed->v2->xy[1];
362  }
363  else {
364  miny = eed->v2->xy[1];
365  maxy = eed->v1->xy[1];
366  }
367  if (eve->xy[1] >= miny && eve->xy[1] <= maxy) {
368  return true;
369  }
370  }
371  return false;
372 }
373 
375 {
376  /* only vertices with (->edge_count == 1) are being tested for
377  * being close to an edge, if true insert */
378 
379  ScanFillVert *eve;
380  ScanFillEdge *eed, *ed1;
381 
382  for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
383  if (eve->edge_count == 1) {
384  /* find the edge which has vertex eve,
385  * NOTE: we _know_ this will crash if 'ed1' becomes NULL
386  * but this will never happen. */
387  for (ed1 = sf_ctx->filledgebase.first; !(ed1->v1 == eve || ed1->v2 == eve);
388  ed1 = ed1->next) {
389  /* do nothing */
390  }
391 
392  if (ed1->v1 == eve) {
393  ed1->v1 = ed1->v2;
394  ed1->v2 = eve;
395  }
396 
397  for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
398  if (eve != eed->v1 && eve != eed->v2 && eve->poly_nr == eed->poly_nr) {
399  if (compare_v2v2(eve->xy, eed->v1->xy, SF_EPSILON)) {
400  ed1->v2 = eed->v1;
401  eed->v1->edge_count++;
402  eve->edge_count = 0;
403  break;
404  }
405  if (compare_v2v2(eve->xy, eed->v2->xy, SF_EPSILON)) {
406  ed1->v2 = eed->v2;
407  eed->v2->edge_count++;
408  eve->edge_count = 0;
409  break;
410  }
411 
412  if (boundinsideEV(eed, eve)) {
413  const float dist = dist_squared_to_line_v2(eed->v1->xy, eed->v2->xy, eve->xy);
414  if (dist < SF_EPSILON_SQ) {
415  /* new edge */
416  ed1 = BLI_scanfill_edge_add(sf_ctx, eed->v1, eve);
417 
418  // printf("fill: vertex near edge %x\n", eve);
419  ed1->poly_nr = eed->poly_nr;
420  eed->v1 = eve;
421  eve->edge_count = 3;
422  break;
423  }
424  }
425  }
426  }
427  }
428  }
429 }
430 
431 static void splitlist(ScanFillContext *sf_ctx,
432  ListBase *tempve,
433  ListBase *temped,
434  unsigned short nr)
435 {
436  /* Everything is in temp-list, write only poly nr to fill-list. */
437  ScanFillVert *eve, *eve_next;
438  ScanFillEdge *eed, *eed_next;
439 
440  BLI_movelisttolist(tempve, &sf_ctx->fillvertbase);
441  BLI_movelisttolist(temped, &sf_ctx->filledgebase);
442 
443  for (eve = tempve->first; eve; eve = eve_next) {
444  eve_next = eve->next;
445  if (eve->poly_nr == nr) {
446  BLI_remlink(tempve, eve);
447  BLI_addtail(&sf_ctx->fillvertbase, eve);
448  }
449  }
450 
451  for (eed = temped->first; eed; eed = eed_next) {
452  eed_next = eed->next;
453  if (eed->poly_nr == nr) {
454  BLI_remlink(temped, eed);
455  BLI_addtail(&sf_ctx->filledgebase, eed);
456  }
457  }
458 }
459 
460 static unsigned int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
461 {
462  ScanFillVertLink *scdata;
463  ScanFillVertLink *sc = NULL, *sc1;
464  ScanFillVert *eve, *v1, *v2, *v3;
465  ScanFillEdge *eed, *eed_next, *ed1, *ed2, *ed3;
466  unsigned int a, b, verts, maxface, totface;
467  const unsigned short nr = pf->nr;
468  bool twoconnected = false;
469 
470  /* PRINTS */
471 #if 0
472  verts = pf->verts;
473  for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
474  printf("vert: %x co: %f %f\n", eve, eve->xy[0], eve->xy[1]);
475  }
476 
477  for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
478  printf("edge: %x verts: %x %x\n", eed, eed->v1, eed->v2);
479  }
480 #endif
481 
482  /* STEP 0: remove zero sized edges */
484  for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
485  if (equals_v2v2(eed->v1->xy, eed->v2->xy)) {
486  if (eed->v1->f == SF_VERT_ZERO_LEN && eed->v2->f != SF_VERT_ZERO_LEN) {
487  eed->v2->f = SF_VERT_ZERO_LEN;
488  eed->v2->tmp.v = eed->v1->tmp.v;
489  }
490  else if (eed->v2->f == SF_VERT_ZERO_LEN && eed->v1->f != SF_VERT_ZERO_LEN) {
491  eed->v1->f = SF_VERT_ZERO_LEN;
492  eed->v1->tmp.v = eed->v2->tmp.v;
493  }
494  else if (eed->v2->f == SF_VERT_ZERO_LEN && eed->v1->f == SF_VERT_ZERO_LEN) {
495  eed->v1->tmp.v = eed->v2->tmp.v;
496  }
497  else {
498  eed->v2->f = SF_VERT_ZERO_LEN;
499  eed->v2->tmp.v = eed->v1;
500  }
501  }
502  }
503  }
504 
505  /* STEP 1: make using FillVert and FillEdge lists a sorted
506  * ScanFillVertLink list
507  */
508  sc = scdata = MEM_mallocN(sizeof(*scdata) * pf->verts, "Scanfill1");
509  verts = 0;
510  for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
511  if (eve->poly_nr == nr) {
512  if (eve->f != SF_VERT_ZERO_LEN) {
513  verts++;
514  eve->f = SF_VERT_NEW; /* Flag for connect edges later on. */
515  sc->vert = eve;
516  sc->edge_first = sc->edge_last = NULL;
517  /* NOTE: debug print only will work for curve poly-fill, union is in use for mesh. */
518  /* if (even->tmp.v == NULL) eve->tmp.u = verts; */
519  sc++;
520  }
521  }
522  }
523 
524  qsort(scdata, verts, sizeof(ScanFillVertLink), vergscdata);
525 
527  for (eed = sf_ctx->filledgebase.first; eed; eed = eed_next) {
528  eed_next = eed->next;
529  BLI_remlink(&sf_ctx->filledgebase, eed);
530  /* This code is for handling zero-length edges that get
531  * collapsed in step 0. It was removed for some time to
532  * fix trunk bug T4544, so if that comes back, this code
533  * may need some work, or there will have to be a better
534  * fix to T4544.
535  *
536  * warning, this can hang on un-ordered edges, see: T33281.
537  * for now disable 'BLI_SCANFILL_CALC_REMOVE_DOUBLES' for ngons.
538  */
539  if (eed->v1->f == SF_VERT_ZERO_LEN) {
540  v1 = eed->v1;
541  while ((eed->v1->f == SF_VERT_ZERO_LEN) && (eed->v1->tmp.v != v1) &&
542  (eed->v1 != eed->v1->tmp.v)) {
543  eed->v1 = eed->v1->tmp.v;
544  }
545  }
546  if (eed->v2->f == SF_VERT_ZERO_LEN) {
547  v2 = eed->v2;
548  while ((eed->v2->f == SF_VERT_ZERO_LEN) && (eed->v2->tmp.v != v2) &&
549  (eed->v2 != eed->v2->tmp.v)) {
550  eed->v2 = eed->v2->tmp.v;
551  }
552  }
553  if (eed->v1 != eed->v2) {
554  addedgetoscanlist(scdata, eed, verts);
555  }
556  }
557  }
558  else {
559  for (eed = sf_ctx->filledgebase.first; eed; eed = eed_next) {
560  eed_next = eed->next;
561  BLI_remlink(&sf_ctx->filledgebase, eed);
562  if (eed->v1 != eed->v2) {
563  addedgetoscanlist(scdata, eed, verts);
564  }
565  }
566  }
567 #if 0
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);
573  }
574  sc++;
575  }
576 #endif
577 
578  /* STEP 2: FILL LOOP */
579 
580  if (pf->f == SF_POLY_NEW) {
581  twoconnected = true;
582  }
583 
584  /* (temporal) security: never much more faces than vertices */
585  totface = 0;
586  if (flag & BLI_SCANFILL_CALC_HOLES) {
587  maxface = 2 * verts; /* 2*verts: based at a filled circle within a triangle */
588  }
589  else {
590  /* when we don't calc any holes, we assume face is a non overlapping loop */
591  maxface = verts - 2;
592  }
593 
594  sc = scdata;
595  for (a = 0; a < verts; a++) {
596  // printf("VERTEX %d index %d\n", a, sc->vert->tmp.u);
597  /* Set connect-flags. */
598  for (ed1 = sc->edge_first; ed1; ed1 = eed_next) {
599  eed_next = ed1->next;
600  if (ed1->v1->edge_count == 1 || ed1->v2->edge_count == 1) {
601  BLI_remlink((ListBase *)&(sc->edge_first), ed1);
602  BLI_addtail(&sf_ctx->filledgebase, ed1);
603  if (ed1->v1->edge_count > 1) {
604  ed1->v1->edge_count--;
605  }
606  if (ed1->v2->edge_count > 1) {
607  ed1->v2->edge_count--;
608  }
609  }
610  else {
611  ed1->v2->f = SF_VERT_AVAILABLE;
612  }
613  }
614  while (sc->edge_first) { /* for as long there are edges */
615  ed1 = sc->edge_first;
616  ed2 = ed1->next;
617 
618  /* commented out... the ESC here delivers corrupted memory
619  * (and doesn't work during grab). */
620  /* if (callLocalInterruptCallBack()) break; */
621  if (totface >= maxface) {
622  // printf("Fill error: endless loop. Escaped at vert %d, tot: %d.\n", a, verts);
623  a = verts;
624  break;
625  }
626  if (ed2 == NULL) {
627  sc->edge_first = sc->edge_last = NULL;
628  // printf("just 1 edge to vert\n");
629  BLI_addtail(&sf_ctx->filledgebase, ed1);
630  ed1->v2->f = SF_VERT_NEW;
631  ed1->v1->edge_count--;
632  ed1->v2->edge_count--;
633  }
634  else {
635  /* test rest of vertices */
636  ScanFillVertLink *best_sc = NULL;
637  float angle_best_cos = -1.0f;
638  float miny;
639  bool firsttime = false;
640 
641  v1 = ed1->v2;
642  v2 = ed1->v1;
643  v3 = ed2->v2;
644 
645  /* this happens with a serial of overlapping edges */
646  if (v1 == v2 || v2 == v3) {
647  break;
648  }
649 
650  // printf("test verts %d %d %d\n", v1->tmp.u, v2->tmp.u, v3->tmp.u);
651  miny = min_ff(v1->xy[1], v3->xy[1]);
652  sc1 = sc + 1;
653 
654  for (b = a + 1; b < verts; b++, sc1++) {
655  if (sc1->vert->f == SF_VERT_NEW) {
656  if (sc1->vert->xy[1] <= miny) {
657  break;
658  }
659  if (testedgeside(v1->xy, v2->xy, sc1->vert->xy)) {
660  if (testedgeside(v2->xy, v3->xy, sc1->vert->xy)) {
661  if (testedgeside(v3->xy, v1->xy, sc1->vert->xy)) {
662  /* point is in triangle */
663 
664  /* Because multiple points can be inside triangle
665  * (concave holes) we continue searching and pick the
666  * one with sharpest corner. */
667  if (best_sc == NULL) {
668  /* even without holes we need to keep checking T35861. */
669  best_sc = sc1;
670  }
671  else {
672  /* Prevent angle calc for the simple cases
673  * only 1 vertex is found. */
674  if (firsttime == false) {
675  angle_best_cos = cos_v2v2v2(v2->xy, v1->xy, best_sc->vert->xy);
676  firsttime = true;
677  }
678 
679  const float angle_test_cos = cos_v2v2v2(v2->xy, v1->xy, sc1->vert->xy);
680  if (angle_test_cos > angle_best_cos) {
681  best_sc = sc1;
682  angle_best_cos = angle_test_cos;
683  }
684  }
685  }
686  }
687  }
688  }
689  }
690 
691  if (best_sc) {
692  /* make new edge, and start over */
693  // printf("add new edge %d %d and start again\n", v2->tmp.u, best_sc->vert->tmp.u);
694 
695  ed3 = BLI_scanfill_edge_add(sf_ctx, v2, best_sc->vert);
696  BLI_remlink(&sf_ctx->filledgebase, ed3);
697  BLI_insertlinkbefore((ListBase *)&(sc->edge_first), ed2, ed3);
698  ed3->v2->f = SF_VERT_AVAILABLE;
699  ed3->f = SF_EDGE_INTERNAL;
700  ed3->v1->edge_count++;
701  ed3->v2->edge_count++;
702  }
703  else {
704  /* new triangle */
705  // printf("add face %d %d %d\n", v1->tmp.u, v2->tmp.u, v3->tmp.u);
706  addfillface(sf_ctx, v1, v2, v3);
707  totface++;
708  BLI_remlink((ListBase *)&(sc->edge_first), ed1);
709  BLI_addtail(&sf_ctx->filledgebase, ed1);
710  ed1->v2->f = SF_VERT_NEW;
711  ed1->v1->edge_count--;
712  ed1->v2->edge_count--;
713  /* ed2 can be removed when it's a boundary edge */
714  if (((ed2->f == SF_EDGE_NEW) && twoconnected) /* || (ed2->f == SF_EDGE_BOUNDARY) */) {
715  BLI_remlink((ListBase *)&(sc->edge_first), ed2);
716  BLI_addtail(&sf_ctx->filledgebase, ed2);
717  ed2->v2->f = SF_VERT_NEW;
718  ed2->v1->edge_count--;
719  ed2->v2->edge_count--;
720  }
721 
722  /* new edge */
723  ed3 = BLI_scanfill_edge_add(sf_ctx, v1, v3);
724  BLI_remlink(&sf_ctx->filledgebase, ed3);
725  ed3->f = SF_EDGE_INTERNAL;
726  ed3->v1->edge_count++;
727  ed3->v2->edge_count++;
728 
729  // printf("add new edge %x %x\n", v1, v3);
730  sc1 = addedgetoscanlist(scdata, ed3, verts);
731 
732  if (sc1) { /* ed3 already exists: remove if a boundary */
733  // printf("Edge exists\n");
734  ed3->v1->edge_count--;
735  ed3->v2->edge_count--;
736 
737  for (ed3 = sc1->edge_first; ed3; ed3 = ed3->next) {
738  if ((ed3->v1 == v1 && ed3->v2 == v3) || (ed3->v1 == v3 && ed3->v2 == v1)) {
739  if (twoconnected /* || (ed3->f == SF_EDGE_BOUNDARY) */) {
740  BLI_remlink((ListBase *)&(sc1->edge_first), ed3);
741  BLI_addtail(&sf_ctx->filledgebase, ed3);
742  ed3->v1->edge_count--;
743  ed3->v2->edge_count--;
744  }
745  break;
746  }
747  }
748  }
749  }
750  }
751 
752  /* test for loose edges */
753  for (ed1 = sc->edge_first; ed1; ed1 = eed_next) {
754  eed_next = ed1->next;
755  if (ed1->v1->edge_count < 2 || ed1->v2->edge_count < 2) {
756  BLI_remlink((ListBase *)&(sc->edge_first), ed1);
757  BLI_addtail(&sf_ctx->filledgebase, ed1);
758  if (ed1->v1->edge_count > 1) {
759  ed1->v1->edge_count--;
760  }
761  if (ed1->v2->edge_count > 1) {
762  ed1->v2->edge_count--;
763  }
764  }
765  }
766  /* done with loose edges */
767  }
768 
769  sc++;
770  }
771 
772  MEM_freeN(scdata);
773 
774  BLI_assert(totface <= maxface);
775 
776  return totface;
777 }
778 
780 {
781  memset(sf_ctx, 0, sizeof(*sf_ctx));
782  sf_ctx->poly_nr = SF_POLY_UNSET;
783  sf_ctx->arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__);
784 }
785 
787 {
788  memset(sf_ctx, 0, sizeof(*sf_ctx));
789  sf_ctx->poly_nr = SF_POLY_UNSET;
790  sf_ctx->arena = arena;
791 }
792 
794 {
795  BLI_memarena_free(sf_ctx->arena);
796  sf_ctx->arena = NULL;
797 
801 }
802 
804 {
805  BLI_memarena_clear(arena);
806  BLI_assert(sf_ctx->arena == arena);
807 
811 }
812 
813 unsigned int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, const int flag, const float nor_proj[3])
814 {
815  /*
816  * - fill works with its own lists, so create that first (no faces!)
817  * - for vertices, put in ->tmp.v the old pointer
818  * - struct elements xs en ys are not used here: don't hide stuff in it
819  * - edge flag ->f becomes 2 when it's a new edge
820  * - mode: & 1 is check for crossings, then create edges (TO DO )
821  * - returns number of triangle faces added.
822  */
823  ListBase tempve, temped;
824  ScanFillVert *eve;
825  ScanFillEdge *eed, *eed_next;
826  PolyFill *pflist, *pf;
827  float *min_xy_p, *max_xy_p;
828  unsigned int totfaces = 0; /* total faces added */
829  unsigned short a, c, poly = 0;
830  bool ok;
831  float mat_2d[3][3];
832 
833  BLI_assert(!nor_proj || len_squared_v3(nor_proj) > FLT_EPSILON);
834 
835 #ifdef DEBUG
836  for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
837  /* these values used to be set,
838  * however they should always be zero'd so check instead */
839  BLI_assert(eve->f == 0);
840  BLI_assert(sf_ctx->poly_nr || eve->poly_nr == 0);
841  BLI_assert(eve->edge_count == 0);
842  }
843 #endif
844 
845  /* first test vertices if they are in edges */
846  /* including resetting of flags */
847  for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
848  BLI_assert(sf_ctx->poly_nr != SF_POLY_UNSET || eed->poly_nr == SF_POLY_UNSET);
849  eed->v1->f = SF_VERT_AVAILABLE;
850  eed->v2->f = SF_VERT_AVAILABLE;
851  }
852 
853  for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
854  if (eve->f == SF_VERT_AVAILABLE) {
855  break;
856  }
857  }
858 
859  if (UNLIKELY(eve == NULL)) {
860  return 0;
861  }
862 
863  float n[3];
864 
865  if (nor_proj) {
866  copy_v3_v3(n, nor_proj);
867  }
868  else {
869  /* define projection: with 'best' normal */
870  /* Newell's Method */
871  /* Similar code used elsewhere, but this checks for double ups
872  * which historically this function supports so better not change */
873 
874  /* WARNING: this only gives stable direction with single polygons,
875  * ideally we'd calculate connectivity and each polys normal, see T41047 */
876  const float *v_prev;
877 
878  zero_v3(n);
879  eve = sf_ctx->fillvertbase.last;
880  v_prev = eve->co;
881 
882  for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
883  if (LIKELY(!compare_v3v3(v_prev, eve->co, SF_EPSILON))) {
884  add_newell_cross_v3_v3v3(n, v_prev, eve->co);
885  v_prev = eve->co;
886  }
887  }
888  }
889 
890  if (UNLIKELY(normalize_v3(n) == 0.0f)) {
891  return 0;
892  }
893 
895 
896  /* STEP 1: COUNT POLYS */
897  if (sf_ctx->poly_nr != SF_POLY_UNSET) {
898  poly = (unsigned short)(sf_ctx->poly_nr + 1);
899  sf_ctx->poly_nr = SF_POLY_UNSET;
900  }
901 
902  if (flag & BLI_SCANFILL_CALC_POLYS && (poly == 0)) {
903  for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
904  mul_v2_m3v3(eve->xy, mat_2d, eve->co);
905 
906  /* get first vertex with no poly number */
907  if (eve->poly_nr == SF_POLY_UNSET) {
908  unsigned int toggle = 0;
909  /* now a sort of select connected */
910  ok = true;
911  eve->poly_nr = poly;
912 
913  while (ok) {
914 
915  ok = false;
916 
917  toggle++;
918  for (eed = (toggle & 1) ? sf_ctx->filledgebase.first : sf_ctx->filledgebase.last; eed;
919  eed = (toggle & 1) ? eed->next : eed->prev) {
920  if (eed->v1->poly_nr == SF_POLY_UNSET && eed->v2->poly_nr == poly) {
921  eed->v1->poly_nr = poly;
922  eed->poly_nr = poly;
923  ok = true;
924  }
925  else if (eed->v2->poly_nr == SF_POLY_UNSET && eed->v1->poly_nr == poly) {
926  eed->v2->poly_nr = poly;
927  eed->poly_nr = poly;
928  ok = true;
929  }
930  else if (eed->poly_nr == SF_POLY_UNSET) {
931  if (eed->v1->poly_nr == poly && eed->v2->poly_nr == poly) {
932  eed->poly_nr = poly;
933  ok = true;
934  }
935  }
936  }
937  }
938 
939  poly++;
940  }
941  }
942  // printf("amount of poly's: %d\n", poly);
943  }
944  else if (poly) {
945  /* we pre-calculated poly_nr */
946  for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
947  mul_v2_m3v3(eve->xy, mat_2d, eve->co);
948  }
949  }
950  else {
951  poly = 1;
952 
953  for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
954  mul_v2_m3v3(eve->xy, mat_2d, eve->co);
955  eve->poly_nr = 0;
956  }
957 
958  for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
959  eed->poly_nr = 0;
960  }
961  }
962 
963  /* STEP 2: remove loose edges and strings of edges */
964  if (flag & BLI_SCANFILL_CALC_LOOSE) {
965  unsigned int toggle = 0;
966  for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
967  if (eed->v1->edge_count++ > 250) {
968  break;
969  }
970  if (eed->v2->edge_count++ > 250) {
971  break;
972  }
973  }
974  if (eed) {
975  /* otherwise it's impossible to be sure you can clear vertices */
976 #ifdef DEBUG
977  printf("No vertices with 250 edges allowed!\n");
978 #endif
979  return 0;
980  }
981 
982  /* does it only for vertices with (->edge_count == 1) */
983  testvertexnearedge(sf_ctx);
984 
985  ok = true;
986  while (ok) {
987  ok = false;
988 
989  toggle++;
990  for (eed = (toggle & 1) ? sf_ctx->filledgebase.first : sf_ctx->filledgebase.last; eed;
991  eed = eed_next) {
992  eed_next = (toggle & 1) ? eed->next : eed->prev;
993  if (eed->v1->edge_count == 1) {
994  eed->v2->edge_count--;
995  BLI_remlink(&sf_ctx->fillvertbase, eed->v1);
996  BLI_remlink(&sf_ctx->filledgebase, eed);
997  ok = true;
998  }
999  else if (eed->v2->edge_count == 1) {
1000  eed->v1->edge_count--;
1001  BLI_remlink(&sf_ctx->fillvertbase, eed->v2);
1002  BLI_remlink(&sf_ctx->filledgebase, eed);
1003  ok = true;
1004  }
1005  }
1006  }
1007  if (BLI_listbase_is_empty(&sf_ctx->filledgebase)) {
1008  // printf("All edges removed\n");
1009  return 0;
1010  }
1011  }
1012  else {
1013  /* skip checks for loose edges */
1014  for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
1015  eed->v1->edge_count++;
1016  eed->v2->edge_count++;
1017  }
1018 #ifdef DEBUG
1019  /* ensure we're right! */
1020  for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
1021  BLI_assert(eed->v1->edge_count != 1);
1022  BLI_assert(eed->v2->edge_count != 1);
1023  }
1024 #endif
1025  }
1026 
1027  /* CURRENT STATUS:
1028  * - `eve->f`: 1 = available in edges.
1029  * - `eve->poly_nr`: poly-number.
1030  * - `eve->edge_count`: amount of edges connected to vertex.
1031  * - `eve->tmp.v`: store! original vertex number.
1032  *
1033  * - `eed->f`: 1 = boundary edge (optionally set by caller).
1034  * - `eed->poly_nr`: poly number.
1035  */
1036 
1037  /* STEP 3: MAKE POLYFILL STRUCT */
1038  pflist = MEM_mallocN(sizeof(*pflist) * (size_t)poly, "edgefill");
1039  pf = pflist;
1040  for (a = 0; a < poly; a++) {
1041  pf->edges = pf->verts = 0;
1042  pf->min_xy[0] = pf->min_xy[1] = 1.0e20f;
1043  pf->max_xy[0] = pf->max_xy[1] = -1.0e20f;
1044  pf->f = SF_POLY_NEW;
1045  pf->nr = a;
1046  pf++;
1047  }
1048  for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
1049  pflist[eed->poly_nr].edges++;
1050  }
1051 
1052  for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
1053  pflist[eve->poly_nr].verts++;
1054  min_xy_p = pflist[eve->poly_nr].min_xy;
1055  max_xy_p = pflist[eve->poly_nr].max_xy;
1056 
1057  min_xy_p[0] = (min_xy_p[0]) < (eve->xy[0]) ? (min_xy_p[0]) : (eve->xy[0]);
1058  min_xy_p[1] = (min_xy_p[1]) < (eve->xy[1]) ? (min_xy_p[1]) : (eve->xy[1]);
1059  max_xy_p[0] = (max_xy_p[0]) > (eve->xy[0]) ? (max_xy_p[0]) : (eve->xy[0]);
1060  max_xy_p[1] = (max_xy_p[1]) > (eve->xy[1]) ? (max_xy_p[1]) : (eve->xy[1]);
1061  if (eve->edge_count > 2) {
1062  pflist[eve->poly_nr].f = SF_POLY_VALID;
1063  }
1064  }
1065 
1066  /* STEP 4: FIND HOLES OR BOUNDS, JOIN THEM
1067  * ( bounds just to divide it in pieces for optimization,
1068  * the edgefill itself has good auto-hole detection)
1069  * WATCH IT: ONLY WORKS WITH SORTED POLYS!!! */
1070 
1071  if ((flag & BLI_SCANFILL_CALC_HOLES) && (poly > 1)) {
1072  unsigned short *polycache, *pc;
1073 
1074  /* so, sort first */
1075  qsort(pflist, (size_t)poly, sizeof(PolyFill), vergpoly);
1076 
1077 #if 0
1078  pf = pflist;
1079  for (a = 0; a < poly; a++) {
1080  printf("poly:%d edges:%d verts:%d flag: %d\n", a, pf->edges, pf->verts, pf->f);
1081  PRINT2(f, f, pf->min[0], pf->min[1]);
1082  pf++;
1083  }
1084 #endif
1085 
1086  polycache = pc = MEM_callocN(sizeof(*polycache) * (size_t)poly, "polycache");
1087  pf = pflist;
1088  for (a = 0; a < poly; a++, pf++) {
1089  for (c = (unsigned short)(a + 1); c < poly; c++) {
1090 
1091  /* if 'a' inside 'c': join (bbox too)
1092  * Careful: 'a' can also be inside another poly.
1093  */
1094  if (boundisect(pf, pflist + c)) {
1095  *pc = c;
1096  pc++;
1097  }
1098  /* only for optimize! */
1099  /* else if (pf->max_xy[0] < (pflist+c)->min[cox]) break; */
1100  }
1101  while (pc != polycache) {
1102  pc--;
1103  mergepolysSimp(sf_ctx, pf, pflist + *pc);
1104  }
1105  }
1106  MEM_freeN(polycache);
1107  }
1108 
1109 #if 0
1110  printf("after merge\n");
1111  pf = pflist;
1112  for (a = 0; a < poly; a++) {
1113  printf("poly:%d edges:%d verts:%d flag: %d\n", a, pf->edges, pf->verts, pf->f);
1114  pf++;
1115  }
1116 #endif
1117 
1118  /* STEP 5: MAKE TRIANGLES */
1119 
1120  tempve.first = sf_ctx->fillvertbase.first;
1121  tempve.last = sf_ctx->fillvertbase.last;
1122  temped.first = sf_ctx->filledgebase.first;
1123  temped.last = sf_ctx->filledgebase.last;
1124  BLI_listbase_clear(&sf_ctx->fillvertbase);
1125  BLI_listbase_clear(&sf_ctx->filledgebase);
1126 
1127  pf = pflist;
1128  for (a = 0; a < poly; a++) {
1129  if (pf->edges > 1) {
1130  splitlist(sf_ctx, &tempve, &temped, pf->nr);
1131  totfaces += scanfill(sf_ctx, pf, flag);
1132  }
1133  pf++;
1134  }
1135  BLI_movelisttolist(&sf_ctx->fillvertbase, &tempve);
1136  BLI_movelisttolist(&sf_ctx->filledgebase, &temped);
1137 
1138  /* FREE */
1139 
1140  MEM_freeN(pflist);
1141 
1142  return totfaces;
1143 }
1144 
1145 unsigned int BLI_scanfill_calc(ScanFillContext *sf_ctx, const int flag)
1146 {
1147  return BLI_scanfill_calc_ex(sf_ctx, flag, NULL);
1148 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
BLI_INLINE bool BLI_listbase_is_empty(const struct ListBase *lb)
Definition: BLI_listbase.h:269
BLI_INLINE void BLI_listbase_clear(struct ListBase *lb)
Definition: BLI_listbase.h:273
void void void BLI_movelisttolist(struct ListBase *dst, struct ListBase *src) ATTR_NONNULL(1
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 BLI_insertlinkbefore(struct ListBase *listbase, void *vnextlink, void *vnewlink) ATTR_NONNULL(1)
Definition: listbase.c:340
MINLINE float min_ff(float a, float b)
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
Definition: math_geom.c:3544
float dist_squared_to_line_v2(const float p[2], const float l1[2], const float l2[2])
Definition: math_geom.c:270
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
Definition: math_matrix.c:917
MINLINE bool compare_v3v3(const float a[3], const float b[3], float limit) ATTR_WARN_UNUSED_RESULT
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float normalize_v3(float r[3])
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
float cos_v2v2v2(const float p1[2], const float p2[2], const float p3[2]) ATTR_WARN_UNUSED_RESULT
Definition: math_vector.c:411
MINLINE bool compare_v2v2(const float a[2], const float b[2], float limit) ATTR_WARN_UNUSED_RESULT
MINLINE bool equals_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
MINLINE void zero_v2(float r[2])
MINLINE void zero_v3(float r[3])
void BLI_memarena_free(struct MemArena *ma) ATTR_NONNULL(1)
Definition: BLI_memarena.c:94
struct MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
Definition: BLI_memarena.c:64
void * BLI_memarena_alloc(struct MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
Definition: BLI_memarena.c:116
void void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
Definition: BLI_memarena.c:208
#define SF_POLY_UNSET
Definition: BLI_scanfill.h:36
#define BLI_SCANFILL_ARENA_SIZE
Definition: BLI_scanfill.h:29
@ BLI_SCANFILL_CALC_LOOSE
Definition: BLI_scanfill.h:98
@ BLI_SCANFILL_CALC_POLYS
Definition: BLI_scanfill.h:91
@ BLI_SCANFILL_CALC_HOLES
Definition: BLI_scanfill.h:95
@ BLI_SCANFILL_CALC_REMOVE_DOUBLES
Definition: BLI_scanfill.h:88
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
#define UNLIKELY(x)
#define LIKELY(x)
_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 y
_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 GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble x2
_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
int len
Definition: draw_manager.c:108
static float verts[][3]
#define pf2(_x, _i)
Prefetch 128.
Definition: gim_memory.h:50
#define pf(_x, _i)
Prefetch 64.
Definition: gim_memory.h:48
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 c
Definition: RandGen.cpp:83
static unsigned a[3]
Definition: RandGen.cpp:78
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
static void addfillface(ScanFillContext *sf_ctx, ScanFillVert *v1, ScanFillVert *v2, ScanFillVert *v3)
Definition: scanfill.c:153
#define SF_POLY_VALID
Definition: scanfill.c:66
static bool testedgeside(const float v1[2], const float v2[2], const float v3[2])
Definition: scanfill.c:235
void BLI_scanfill_begin(ScanFillContext *sf_ctx)
Definition: scanfill.c:779
#define SF_VERT_NEW
Definition: scanfill.c:53
struct ScanFillVertLink ScanFillVertLink
void BLI_scanfill_end_arena(ScanFillContext *sf_ctx, MemArena *arena)
Definition: scanfill.c:803
#define SF_EPSILON
Definition: scanfill.c:49
ScanFillVert * BLI_scanfill_vert_add(ScanFillContext *sf_ctx, const float vec[3])
Definition: scanfill.c:112
static int vergpoly(const void *a1, const void *a2)
Definition: scanfill.c:90
static unsigned int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
Definition: scanfill.c:460
void BLI_scanfill_end(ScanFillContext *sf_ctx)
Definition: scanfill.c:793
#define SF_EDGE_NEW
Definition: scanfill.c:60
struct PolyFill PolyFill
static bool boundinsideEV(ScanFillEdge *eed, ScanFillVert *eve)
Definition: scanfill.c:346
static void mergepolysSimp(ScanFillContext *sf_ctx, PolyFill *pf1, PolyFill *pf2)
Definition: scanfill.c:211
unsigned int BLI_scanfill_calc(ScanFillContext *sf_ctx, const int flag)
Definition: scanfill.c:1145
static bool boundisect(PolyFill *pf2, PolyFill *pf1)
Definition: scanfill.c:169
#define SF_VERT_ZERO_LEN
Definition: scanfill.c:55
static int vergscdata(const void *a1, const void *a2)
Definition: scanfill.c:70
ScanFillEdge * BLI_scanfill_edge_add(ScanFillContext *sf_ctx, ScanFillVert *v1, ScanFillVert *v2)
Definition: scanfill.c:134
#define SF_EDGE_INTERNAL
Definition: scanfill.c:62
void BLI_scanfill_begin_arena(ScanFillContext *sf_ctx, MemArena *arena)
Definition: scanfill.c:786
#define SF_EPSILON_SQ
Definition: scanfill.c:50
#define SF_POLY_NEW
Definition: scanfill.c:65
unsigned int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, const int flag, const float nor_proj[3])
Definition: scanfill.c:813
static bool addedgetoscanvert(ScanFillVertLink *sc, ScanFillEdge *eed)
Definition: scanfill.c:256
static ScanFillVertLink * addedgetoscanlist(ScanFillVertLink *scdata, ScanFillEdge *eed, unsigned int len)
Definition: scanfill.c:307
static void splitlist(ScanFillContext *sf_ctx, ListBase *tempve, ListBase *temped, unsigned short nr)
Definition: scanfill.c:431
#define SF_VERT_AVAILABLE
Definition: scanfill.c:54
static void testvertexnearedge(ScanFillContext *sf_ctx)
Definition: scanfill.c:374
void * last
Definition: DNA_listBase.h:31
void * first
Definition: DNA_listBase.h:31
unsigned int verts
Definition: scanfill.c:36
bool f
Definition: scanfill.c:39
float max_xy[2]
Definition: scanfill.c:37
unsigned int edges
Definition: scanfill.c:36
float min_xy[2]
Definition: scanfill.c:37
unsigned short nr
Definition: scanfill.c:38
struct MemArena * arena
Definition: BLI_scanfill.h:26
ListBase fillvertbase
Definition: BLI_scanfill.h:17
ListBase filledgebase
Definition: BLI_scanfill.h:18
unsigned short poly_nr
Definition: BLI_scanfill.h:23
ListBase fillfacebase
Definition: BLI_scanfill.h:19
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
unsigned char c
Definition: BLI_scanfill.h:68
unsigned int f
Definition: BLI_scanfill.h:65
struct ScanFillEdge * next
Definition: BLI_scanfill.h:62
union ScanFillEdge::@122 tmp
unsigned int user_flag
Definition: BLI_scanfill.h:66
struct ScanFillVert * v2
Definition: BLI_scanfill.h:74
struct ScanFillVert * v3
Definition: BLI_scanfill.h:74
struct ScanFillVert * v1
Definition: BLI_scanfill.h:74
float xy[2]
Definition: BLI_scanfill.h:49
unsigned short poly_nr
Definition: BLI_scanfill.h:52
unsigned int f
Definition: BLI_scanfill.h:56
unsigned char edge_count
Definition: BLI_scanfill.h:54
struct ScanFillVert * next
Definition: BLI_scanfill.h:39
float co[3]
Definition: BLI_scanfill.h:47
struct ScanFillVert * v
Definition: BLI_scanfill.h:41
union ScanFillVert::@121 tmp
unsigned int user_flag
Definition: BLI_scanfill.h:58
unsigned int keyindex
Definition: BLI_scanfill.h:51