Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / blenlib / intern / scanfill_utils.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file \ingroup bli
18  */
19
20 #include <stdio.h>
21 #include <math.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <limits.h>
25
26 #include "MEM_guardedalloc.h"
27
28 #include "BLI_listbase.h"
29 #include "BLI_math.h"
30 #include "BLI_utildefines.h"
31 #include "BLI_ghash.h"
32
33 #include "BLI_scanfill.h"  /* own include */
34
35 #include "BLI_strict_flags.h"
36
37 typedef struct PolyInfo {
38         ScanFillEdge *edge_first, *edge_last;
39         ScanFillVert *vert_outer;
40 } PolyInfo;
41
42 typedef struct ScanFillIsect {
43         struct ScanFillIsect *next, *prev;
44         float co[3];
45
46         /* newly created vertex */
47         ScanFillVert *v;
48 } ScanFillIsect;
49
50
51 #define V_ISISECT 1
52 #define E_ISISECT 1
53 #define E_ISDELETE 2
54
55
56 #define EFLAG_SET(eed, val)  { CHECK_TYPE(eed, ScanFillEdge *); \
57         (eed)->user_flag = (eed)->user_flag | (unsigned int)val; } (void)0
58 #if 0
59 #define EFLAG_CLEAR(eed, val)  { CHECK_TYPE(eed, ScanFillEdge *); \
60         (eed)->user_flag = (eed)->user_flag & ~(unsigned int)val; } (void)0
61 #endif
62
63 #define VFLAG_SET(eve, val)  { CHECK_TYPE(eve, ScanFillVert *); \
64         (eve)->user_flag = (eve)->user_flag | (unsigned int)val; } (void)0
65 #if 0
66 #define VFLAG_CLEAR(eve, val)  { CHECK_TYPE(eve, ScanFillVert *); \
67         (eve)->user_flags = (eve)->user_flag & ~(unsigned int)val; } (void)0
68 #endif
69
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         else {
129                 return (a < b);
130         }
131 }
132
133 static ScanFillEdge *edge_step(PolyInfo *poly_info,
134                                const unsigned short poly_nr,
135                                ScanFillVert *v_prev, 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 : poly_info[poly_nr].edge_first;
144         if ((v_curr == eed->v1 || v_curr == eed->v2) == true &&
145             (v_prev == eed->v1 || v_prev == eed->v2) == false)
146         {
147                 return eed;
148         }
149
150         eed = (e_curr->prev && e_curr != poly_info[poly_nr].edge_first) ? e_curr->prev : poly_info[poly_nr].edge_last;
151         if ((v_curr == eed->v1 || v_curr == eed->v2) == true &&
152             (v_prev == eed->v1 || v_prev == eed->v2) == false)
153         {
154                 return eed;
155         }
156
157         BLI_assert(0);
158         return NULL;
159 }
160
161 static bool scanfill_preprocess_self_isect(
162         ScanFillContext *sf_ctx,
163         PolyInfo *poly_info,
164         const unsigned short poly_nr,
165         ListBase *filledgebase)
166 {
167         PolyInfo *pi = &poly_info[poly_nr];
168         GHash *isect_hash = NULL;
169         ListBase isect_lb = {NULL};
170
171         /* warning, O(n2) check here, should use spatial lookup */
172         {
173                 ScanFillEdge *eed;
174
175                 for (eed = pi->edge_first;
176                      eed;
177                      eed = (eed == pi->edge_last) ? NULL : eed->next)
178                 {
179                         ScanFillEdge *eed_other;
180
181                         for (eed_other = eed->next;
182                              eed_other;
183                              eed_other = (eed_other == pi->edge_last) ? NULL : eed_other->next)
184                         {
185                                 if (!ELEM(eed->v1, eed_other->v1, eed_other->v2) &&
186                                     !ELEM(eed->v2, eed_other->v1, eed_other->v2) &&
187                                     (eed != eed_other))
188                                 {
189                                         /* check isect */
190                                         float pt[2];
191                                         BLI_assert(eed != eed_other);
192
193                                         if (isect_seg_seg_v2_point(eed->v1->co, eed->v2->co,
194                                                                    eed_other->v1->co, eed_other->v2->co,
195                                                                    pt) == 1)
196                                         {
197                                                 ScanFillIsect *isect;
198
199                                                 if (UNLIKELY(isect_hash == NULL)) {
200                                                         isect_hash = BLI_ghash_ptr_new(__func__);
201                                                 }
202
203                                                 isect = MEM_mallocN(sizeof(ScanFillIsect), __func__);
204
205                                                 BLI_addtail(&isect_lb, isect);
206
207                                                 copy_v2_v2(isect->co, pt);
208                                                 isect->co[2] = eed->v1->co[2];
209                                                 isect->v = BLI_scanfill_vert_add(sf_ctx, isect->co);
210
211                                                 /* NOTE: vert may belong to 2 polys now */
212                                                 isect->v->poly_nr = eed->v1->poly_nr;
213
214                                                 VFLAG_SET(isect->v, V_ISISECT);
215                                                 edge_isect_ls_add(isect_hash, eed, isect);
216                                                 edge_isect_ls_add(isect_hash, eed_other, isect);
217                                         }
218                                 }
219                         }
220                 }
221         }
222
223         if (isect_hash == NULL) {
224                 return false;
225         }
226
227         /* now subdiv the edges */
228         {
229                 ScanFillEdge *eed;
230
231                 for (eed = pi->edge_first;
232                      eed;
233                      eed = (eed == pi->edge_last) ? NULL : eed->next)
234                 {
235                         if (eed->user_flag & E_ISISECT) {
236                                 ListBase *e_ls = BLI_ghash_lookup(isect_hash, eed);
237
238                                 LinkData *isect_link;
239
240                                 if (UNLIKELY(e_ls == NULL)) {
241                                         /* only happens in very rare cases (entirely overlapping splines).
242                                          * in this case we can't do much useful. but at least don't crash */
243                                         continue;
244                                 }
245
246                                 /* maintain coorect terminating edge */
247                                 if (pi->edge_last == eed) {
248                                         pi->edge_last = NULL;
249                                 }
250
251                                 if (BLI_listbase_is_single(e_ls) == false) {
252                                         BLI_listbase_sort_r(e_ls, edge_isect_ls_sort_cb, eed->v2->co);
253                                 }
254
255                                 /* move original edge to filledgebase and add replacement
256                                  * (which gets subdivided next) */
257                                 {
258                                         ScanFillEdge *eed_tmp;
259                                         eed_tmp = BLI_scanfill_edge_add(sf_ctx, eed->v1, eed->v2);
260                                         BLI_remlink(&sf_ctx->filledgebase, eed_tmp);
261                                         BLI_insertlinkafter(&sf_ctx->filledgebase, eed, eed_tmp);
262                                         BLI_remlink(&sf_ctx->filledgebase, eed);
263                                         BLI_addtail(filledgebase, eed);
264                                         if (pi->edge_first == eed) {
265                                                 pi->edge_first = eed_tmp;
266                                         }
267                                         eed = eed_tmp;
268                                 }
269
270                                 for (isect_link = e_ls->first; isect_link; isect_link = isect_link->next) {
271                                         ScanFillIsect *isect = isect_link->data;
272                                         ScanFillEdge *eed_subd;
273
274                                         eed_subd = BLI_scanfill_edge_add(sf_ctx, isect->v, eed->v2);
275                                         eed_subd->poly_nr = poly_nr;
276                                         eed->v2 = isect->v;
277
278                                         BLI_remlink(&sf_ctx->filledgebase, eed_subd);
279                                         BLI_insertlinkafter(&sf_ctx->filledgebase, eed, eed_subd);
280
281                                         /* step to the next edge and continue dividing */
282                                         eed = eed_subd;
283                                 }
284
285                                 BLI_freelistN(e_ls);
286                                 MEM_freeN(e_ls);
287
288                                 if (pi->edge_last == NULL) {
289                                         pi->edge_last = eed;
290                                 }
291                         }
292                 }
293         }
294
295         BLI_freelistN(&isect_lb);
296         BLI_ghash_free(isect_hash, NULL, NULL);
297
298         {
299                 ScanFillEdge *e_init;
300                 ScanFillEdge *e_curr;
301                 ScanFillEdge *e_next;
302
303                 ScanFillVert *v_prev;
304                 ScanFillVert *v_curr;
305
306                 bool inside = false;
307
308                 /* first vert */
309 #if 0
310                 e_init = pi->edge_last;
311                 e_curr = e_init;
312                 e_next = pi->edge_first;
313
314                 v_prev = e_curr->v1;
315                 v_curr = e_curr->v2;
316 #else
317
318                 /* find outside vertex */
319                 {
320                         ScanFillEdge *eed;
321                         ScanFillEdge *eed_prev;
322                         float min_x = FLT_MAX;
323
324                         e_curr = pi->edge_last;
325                         e_next = pi->edge_first;
326
327                         eed_prev = pi->edge_last;
328                         for (eed = pi->edge_first;
329                              eed;
330                              eed = (eed == pi->edge_last) ? NULL : eed->next)
331                         {
332                                 if (eed->v2->co[0] < min_x) {
333                                         min_x = eed->v2->co[0];
334                                         e_curr = eed_prev;
335                                         e_next = eed;
336
337                                 }
338                                 eed_prev = eed;
339                         }
340
341                         e_init = e_curr;
342                         v_prev = e_curr->v1;
343                         v_curr = e_curr->v2;
344                 }
345 #endif
346
347                 BLI_assert(e_curr->poly_nr == poly_nr);
348                 BLI_assert(pi->edge_last->poly_nr == poly_nr);
349
350                 do {
351                         ScanFillVert *v_next;
352
353                         v_next = (e_next->v1 == v_curr) ? e_next->v2 : e_next->v1;
354                         BLI_assert(ELEM(v_curr, e_next->v1, e_next->v2));
355
356                         /* track intersections */
357                         if (inside) {
358                                 EFLAG_SET(e_next, E_ISDELETE);
359                         }
360                         if (v_next->user_flag & V_ISISECT) {
361                                 inside = !inside;
362                         }
363                         /* now step... */
364
365                         v_prev = v_curr;
366                         v_curr = v_next;
367                         e_curr = e_next;
368
369                         e_next = edge_step(poly_info, poly_nr, v_prev, v_curr, e_curr);
370
371                 } while (e_curr != e_init);
372         }
373
374         return true;
375 }
376
377 /**
378  * Call before scanfill to remove self intersections.
379  *
380  * \return false if no changes were made.
381  */
382 bool BLI_scanfill_calc_self_isect(
383         ScanFillContext *sf_ctx,
384         ListBase *remvertbase,
385         ListBase *remedgebase)
386 {
387         const unsigned int poly_tot = (unsigned int)sf_ctx->poly_nr + 1;
388         unsigned int eed_index = 0;
389         int totvert_new = 0;
390         bool changed = false;
391
392         PolyInfo *poly_info;
393
394         if (UNLIKELY(sf_ctx->poly_nr == SF_POLY_UNSET)) {
395                 return false;
396         }
397
398         poly_info = MEM_callocN(sizeof(*poly_info) * poly_tot, __func__);
399
400         /* get the polygon span */
401         if (sf_ctx->poly_nr == 0) {
402                 poly_info->edge_first = sf_ctx->filledgebase.first;
403                 poly_info->edge_last = sf_ctx->filledgebase.last;
404         }
405         else {
406                 unsigned short poly_nr;
407                 ScanFillEdge *eed;
408
409                 poly_nr = 0;
410
411                 for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next, eed_index++) {
412
413                         BLI_assert(eed->poly_nr == eed->v1->poly_nr);
414                         BLI_assert(eed->poly_nr == eed->v2->poly_nr);
415
416                         if ((poly_info[poly_nr].edge_last != NULL) &&
417                             (poly_info[poly_nr].edge_last->poly_nr != eed->poly_nr))
418                         {
419                                 poly_nr++;
420                         }
421
422                         if (poly_info[poly_nr].edge_first == NULL) {
423                                 poly_info[poly_nr].edge_first = eed;
424                                 poly_info[poly_nr].edge_last  = eed;
425                         }
426                         else if (poly_info[poly_nr].edge_last->poly_nr == eed->poly_nr) {
427                                 poly_info[poly_nr].edge_last  = eed;
428                         }
429
430                         BLI_assert(poly_info[poly_nr].edge_first->poly_nr == poly_info[poly_nr].edge_last->poly_nr);
431                 }
432         }
433
434         /* self-intersect each polygon */
435         {
436                 unsigned short poly_nr;
437                 for (poly_nr = 0; poly_nr < poly_tot; poly_nr++) {
438                         changed |= scanfill_preprocess_self_isect(sf_ctx, poly_info, poly_nr, remedgebase);
439                 }
440         }
441
442         MEM_freeN(poly_info);
443
444         if (changed == false) {
445                 return false;
446         }
447
448         /* move free edges into own list */
449         {
450                 ScanFillEdge *eed;
451                 ScanFillEdge *eed_next;
452                 for (eed = sf_ctx->filledgebase.first; eed; eed = eed_next) {
453                         eed_next = eed->next;
454                         if (eed->user_flag & E_ISDELETE) {
455                                 BLI_remlink(&sf_ctx->filledgebase, eed);
456                                 BLI_addtail(remedgebase, eed);
457                         }
458                 }
459         }
460
461         /* move free vertices into own list */
462         {
463                 ScanFillEdge *eed;
464                 ScanFillVert *eve;
465                 ScanFillVert *eve_next;
466
467                 for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
468                         eve->user_flag = 0;
469                         eve->poly_nr = SF_POLY_UNSET;
470                 }
471                 for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
472                         eed->v1->user_flag = 1;
473                         eed->v2->user_flag = 1;
474                         eed->poly_nr = SF_POLY_UNSET;
475                 }
476
477                 for (eve = sf_ctx->fillvertbase.first; eve; eve = eve_next) {
478                         eve_next = eve->next;
479                         if (eve->user_flag != 1) {
480                                 BLI_remlink(&sf_ctx->fillvertbase, eve);
481                                 BLI_addtail(remvertbase, eve);
482                                 totvert_new--;
483                         }
484                         else {
485                                 eve->user_flag = 0;
486                         }
487                 }
488         }
489
490         /* polygon id's are no longer meaningful,
491          * when removing self intersections we may have created new isolated polys */
492         sf_ctx->poly_nr = SF_POLY_UNSET;
493
494 #if 0
495         BLI_scanfill_view3d_dump(sf_ctx);
496         BLI_scanfill_obj_dump(sf_ctx);
497 #endif
498
499         return changed;
500 }