Cleanup: style, use braces for blenkernel
[blender.git] / source / blender / blenkernel / intern / mesh_mapping.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
18  * \ingroup bke
19  *
20  * Functions for accessing mesh connectivity data.
21  * eg: polys connected to verts, UV's connected to verts.
22  */
23
24 #include "MEM_guardedalloc.h"
25
26 #include "DNA_meshdata_types.h"
27 #include "DNA_vec_types.h"
28
29 #include "BLI_buffer.h"
30 #include "BLI_utildefines.h"
31 #include "BLI_bitmap.h"
32 #include "BLI_math.h"
33
34 #include "BKE_mesh_mapping.h"
35 #include "BKE_customdata.h"
36 #include "BLI_memarena.h"
37
38 #include "BLI_strict_flags.h"
39
40 /* -------------------------------------------------------------------- */
41 /** \name Mesh Connectivity Mapping
42  * \{ */
43
44 /* ngon version wip, based on BM_uv_vert_map_create */
45 /* this replaces the non bmesh function (in trunk) which takes MTFace's, if we ever need it back we could
46  * but for now this replaces it because its unused. */
47
48 UvVertMap *BKE_mesh_uv_vert_map_create(const MPoly *mpoly,
49                                        const MLoop *mloop,
50                                        const MLoopUV *mloopuv,
51                                        unsigned int totpoly,
52                                        unsigned int totvert,
53                                        const float limit[2],
54                                        const bool selected,
55                                        const bool use_winding)
56 {
57   UvVertMap *vmap;
58   UvMapVert *buf;
59   const MPoly *mp;
60   unsigned int a;
61   int i, totuv, nverts;
62
63   bool *winding = NULL;
64   BLI_buffer_declare_static(vec2f, tf_uv_buf, BLI_BUFFER_NOP, 32);
65
66   totuv = 0;
67
68   /* generate UvMapVert array */
69   mp = mpoly;
70   for (a = 0; a < totpoly; a++, mp++) {
71     if (!selected || (!(mp->flag & ME_HIDE) && (mp->flag & ME_FACE_SEL))) {
72       totuv += mp->totloop;
73     }
74   }
75
76   if (totuv == 0) {
77     return NULL;
78   }
79
80   vmap = (UvVertMap *)MEM_callocN(sizeof(*vmap), "UvVertMap");
81   buf = vmap->buf = (UvMapVert *)MEM_callocN(sizeof(*vmap->buf) * (size_t)totuv, "UvMapVert");
82   vmap->vert = (UvMapVert **)MEM_callocN(sizeof(*vmap->vert) * totvert, "UvMapVert*");
83   if (use_winding) {
84     winding = MEM_callocN(sizeof(*winding) * totpoly, "winding");
85   }
86
87   if (!vmap->vert || !vmap->buf) {
88     BKE_mesh_uv_vert_map_free(vmap);
89     return NULL;
90   }
91
92   mp = mpoly;
93   for (a = 0; a < totpoly; a++, mp++) {
94     if (!selected || (!(mp->flag & ME_HIDE) && (mp->flag & ME_FACE_SEL))) {
95       float(*tf_uv)[2] = NULL;
96
97       if (use_winding) {
98         tf_uv = (float(*)[2])BLI_buffer_reinit_data(&tf_uv_buf, vec2f, (size_t)mp->totloop);
99       }
100
101       nverts = mp->totloop;
102
103       for (i = 0; i < nverts; i++) {
104         buf->loop_of_poly_index = (unsigned short)i;
105         buf->poly_index = a;
106         buf->separate = 0;
107         buf->next = vmap->vert[mloop[mp->loopstart + i].v];
108         vmap->vert[mloop[mp->loopstart + i].v] = buf;
109
110         if (use_winding) {
111           copy_v2_v2(tf_uv[i], mloopuv[mpoly[a].loopstart + i].uv);
112         }
113
114         buf++;
115       }
116
117       if (use_winding) {
118         winding[a] = cross_poly_v2(tf_uv, (unsigned int)nverts) > 0;
119       }
120     }
121   }
122
123   /* sort individual uvs for each vert */
124   for (a = 0; a < totvert; a++) {
125     UvMapVert *newvlist = NULL, *vlist = vmap->vert[a];
126     UvMapVert *iterv, *v, *lastv, *next;
127     const float *uv, *uv2;
128     float uvdiff[2];
129
130     while (vlist) {
131       v = vlist;
132       vlist = vlist->next;
133       v->next = newvlist;
134       newvlist = v;
135
136       uv = mloopuv[mpoly[v->poly_index].loopstart + v->loop_of_poly_index].uv;
137       lastv = NULL;
138       iterv = vlist;
139
140       while (iterv) {
141         next = iterv->next;
142
143         uv2 = mloopuv[mpoly[iterv->poly_index].loopstart + iterv->loop_of_poly_index].uv;
144         sub_v2_v2v2(uvdiff, uv2, uv);
145
146         if (fabsf(uv[0] - uv2[0]) < limit[0] && fabsf(uv[1] - uv2[1]) < limit[1] &&
147             (!use_winding || winding[iterv->poly_index] == winding[v->poly_index])) {
148           if (lastv) {
149             lastv->next = next;
150           }
151           else {
152             vlist = next;
153           }
154           iterv->next = newvlist;
155           newvlist = iterv;
156         }
157         else {
158           lastv = iterv;
159         }
160
161         iterv = next;
162       }
163
164       newvlist->separate = 1;
165     }
166
167     vmap->vert[a] = newvlist;
168   }
169
170   if (use_winding) {
171     MEM_freeN(winding);
172   }
173
174   BLI_buffer_free(&tf_uv_buf);
175
176   return vmap;
177 }
178
179 UvMapVert *BKE_mesh_uv_vert_map_get_vert(UvVertMap *vmap, unsigned int v)
180 {
181   return vmap->vert[v];
182 }
183
184 void BKE_mesh_uv_vert_map_free(UvVertMap *vmap)
185 {
186   if (vmap) {
187     if (vmap->vert) {
188       MEM_freeN(vmap->vert);
189     }
190     if (vmap->buf) {
191       MEM_freeN(vmap->buf);
192     }
193     MEM_freeN(vmap);
194   }
195 }
196
197 /**
198  * Generates a map where the key is the vertex and the value is a list
199  * of polys or loops that use that vertex as a corner. The lists are allocated
200  * from one memory pool.
201  *
202  * Wrapped by #BKE_mesh_vert_poly_map_create & BKE_mesh_vert_loop_map_create
203  */
204 static void mesh_vert_poly_or_loop_map_create(MeshElemMap **r_map,
205                                               int **r_mem,
206                                               const MPoly *mpoly,
207                                               const MLoop *mloop,
208                                               int totvert,
209                                               int totpoly,
210                                               int totloop,
211                                               const bool do_loops)
212 {
213   MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * (size_t)totvert, __func__);
214   int *indices, *index_iter;
215   int i, j;
216
217   indices = index_iter = MEM_mallocN(sizeof(int) * (size_t)totloop, __func__);
218
219   /* Count number of polys for each vertex */
220   for (i = 0; i < totpoly; i++) {
221     const MPoly *p = &mpoly[i];
222
223     for (j = 0; j < p->totloop; j++) {
224       map[mloop[p->loopstart + j].v].count++;
225     }
226   }
227
228   /* Assign indices mem */
229   for (i = 0; i < totvert; i++) {
230     map[i].indices = index_iter;
231     index_iter += map[i].count;
232
233     /* Reset 'count' for use as index in last loop */
234     map[i].count = 0;
235   }
236
237   /* Find the users */
238   for (i = 0; i < totpoly; i++) {
239     const MPoly *p = &mpoly[i];
240
241     for (j = 0; j < p->totloop; j++) {
242       unsigned int v = mloop[p->loopstart + j].v;
243
244       map[v].indices[map[v].count] = do_loops ? p->loopstart + j : i;
245       map[v].count++;
246     }
247   }
248
249   *r_map = map;
250   *r_mem = indices;
251 }
252
253 /**
254  * Generates a map where the key is the vertex and the value is a list of polys that use that vertex as a corner.
255  * The lists are allocated from one memory pool.
256  */
257 void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map,
258                                    int **r_mem,
259                                    const MPoly *mpoly,
260                                    const MLoop *mloop,
261                                    int totvert,
262                                    int totpoly,
263                                    int totloop)
264 {
265   mesh_vert_poly_or_loop_map_create(r_map, r_mem, mpoly, mloop, totvert, totpoly, totloop, false);
266 }
267
268 /**
269  * Generates a map where the key is the vertex and the value is a list of loops that use that vertex as a corner.
270  * The lists are allocated from one memory pool.
271  */
272 void BKE_mesh_vert_loop_map_create(MeshElemMap **r_map,
273                                    int **r_mem,
274                                    const MPoly *mpoly,
275                                    const MLoop *mloop,
276                                    int totvert,
277                                    int totpoly,
278                                    int totloop)
279 {
280   mesh_vert_poly_or_loop_map_create(r_map, r_mem, mpoly, mloop, totvert, totpoly, totloop, true);
281 }
282
283 /**
284  * Generates a map where the key is the edge and the value is a list of looptris that use that edge.
285  * The lists are allocated from one memory pool.
286  */
287 void BKE_mesh_vert_looptri_map_create(MeshElemMap **r_map,
288                                       int **r_mem,
289                                       const MVert *UNUSED(mvert),
290                                       const int totvert,
291                                       const MLoopTri *mlooptri,
292                                       const int totlooptri,
293                                       const MLoop *mloop,
294                                       const int UNUSED(totloop))
295 {
296   MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * (size_t)totvert, __func__);
297   int *indices = MEM_mallocN(sizeof(int) * (size_t)totlooptri * 3, __func__);
298   int *index_step;
299   const MLoopTri *mlt;
300   int i;
301
302   /* count face users */
303   for (i = 0, mlt = mlooptri; i < totlooptri; mlt++, i++) {
304     for (int j = 3; j--;) {
305       map[mloop[mlt->tri[j]].v].count++;
306     }
307   }
308
309   /* create offsets */
310   index_step = indices;
311   for (i = 0; i < totvert; i++) {
312     map[i].indices = index_step;
313     index_step += map[i].count;
314
315     /* re-count, using this as an index below */
316     map[i].count = 0;
317   }
318
319   /* assign looptri-edge users */
320   for (i = 0, mlt = mlooptri; i < totlooptri; mlt++, i++) {
321     for (int j = 3; j--;) {
322       MeshElemMap *map_ele = &map[mloop[mlt->tri[j]].v];
323       map_ele->indices[map_ele->count++] = i;
324     }
325   }
326
327   *r_map = map;
328   *r_mem = indices;
329 }
330
331 /**
332  * Generates a map where the key is the vertex and the value is a list of edges that use that vertex as an endpoint.
333  * The lists are allocated from one memory pool.
334  */
335 void BKE_mesh_vert_edge_map_create(
336     MeshElemMap **r_map, int **r_mem, const MEdge *medge, int totvert, int totedge)
337 {
338   MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * (size_t)totvert, "vert-edge map");
339   int *indices = MEM_mallocN(sizeof(int[2]) * (size_t)totedge, "vert-edge map mem");
340   int *i_pt = indices;
341
342   int i;
343
344   /* Count number of edges for each vertex */
345   for (i = 0; i < totedge; i++) {
346     map[medge[i].v1].count++;
347     map[medge[i].v2].count++;
348   }
349
350   /* Assign indices mem */
351   for (i = 0; i < totvert; i++) {
352     map[i].indices = i_pt;
353     i_pt += map[i].count;
354
355     /* Reset 'count' for use as index in last loop */
356     map[i].count = 0;
357   }
358
359   /* Find the users */
360   for (i = 0; i < totedge; i++) {
361     const unsigned int v[2] = {medge[i].v1, medge[i].v2};
362
363     map[v[0]].indices[map[v[0]].count] = i;
364     map[v[1]].indices[map[v[1]].count] = i;
365
366     map[v[0]].count++;
367     map[v[1]].count++;
368   }
369
370   *r_map = map;
371   *r_mem = indices;
372 }
373
374 /**
375  * A version of #BKE_mesh_vert_edge_map_create that references connected vertices directly (not their edges).
376  */
377 void BKE_mesh_vert_edge_vert_map_create(
378     MeshElemMap **r_map, int **r_mem, const MEdge *medge, int totvert, int totedge)
379 {
380   MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * (size_t)totvert, "vert-edge map");
381   int *indices = MEM_mallocN(sizeof(int[2]) * (size_t)totedge, "vert-edge map mem");
382   int *i_pt = indices;
383
384   int i;
385
386   /* Count number of edges for each vertex */
387   for (i = 0; i < totedge; i++) {
388     map[medge[i].v1].count++;
389     map[medge[i].v2].count++;
390   }
391
392   /* Assign indices mem */
393   for (i = 0; i < totvert; i++) {
394     map[i].indices = i_pt;
395     i_pt += map[i].count;
396
397     /* Reset 'count' for use as index in last loop */
398     map[i].count = 0;
399   }
400
401   /* Find the users */
402   for (i = 0; i < totedge; i++) {
403     const unsigned int v[2] = {medge[i].v1, medge[i].v2};
404
405     map[v[0]].indices[map[v[0]].count] = (int)v[1];
406     map[v[1]].indices[map[v[1]].count] = (int)v[0];
407
408     map[v[0]].count++;
409     map[v[1]].count++;
410   }
411
412   *r_map = map;
413   *r_mem = indices;
414 }
415
416 /**
417  * Generates a map where the key is the edge and the value is a list of loops that use that edge.
418  * Loops indices of a same poly are contiguous and in winding order.
419  * The lists are allocated from one memory pool.
420  */
421 void BKE_mesh_edge_loop_map_create(MeshElemMap **r_map,
422                                    int **r_mem,
423                                    const MEdge *UNUSED(medge),
424                                    const int totedge,
425                                    const MPoly *mpoly,
426                                    const int totpoly,
427                                    const MLoop *mloop,
428                                    const int totloop)
429 {
430   MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * (size_t)totedge, "edge-poly map");
431   int *indices = MEM_mallocN(sizeof(int) * (size_t)totloop * 2, "edge-poly map mem");
432   int *index_step;
433   const MPoly *mp;
434   int i;
435
436   /* count face users */
437   for (i = 0, mp = mpoly; i < totpoly; mp++, i++) {
438     const MLoop *ml;
439     int j = mp->totloop;
440     for (ml = &mloop[mp->loopstart]; j--; ml++) {
441       map[ml->e].count += 2;
442     }
443   }
444
445   /* create offsets */
446   index_step = indices;
447   for (i = 0; i < totedge; i++) {
448     map[i].indices = index_step;
449     index_step += map[i].count;
450
451     /* re-count, using this as an index below */
452     map[i].count = 0;
453   }
454
455   /* assign loop-edge users */
456   for (i = 0, mp = mpoly; i < totpoly; mp++, i++) {
457     const MLoop *ml;
458     MeshElemMap *map_ele;
459     const int max_loop = mp->loopstart + mp->totloop;
460     int j = mp->loopstart;
461     for (ml = &mloop[j]; j < max_loop; j++, ml++) {
462       map_ele = &map[ml->e];
463       map_ele->indices[map_ele->count++] = j;
464       map_ele->indices[map_ele->count++] = j + 1;
465     }
466     /* last edge/loop of poly, must point back to first loop! */
467     map_ele->indices[map_ele->count - 1] = mp->loopstart;
468   }
469
470   *r_map = map;
471   *r_mem = indices;
472 }
473
474 /**
475  * Generates a map where the key is the edge and the value is a list of polygons that use that edge.
476  * The lists are allocated from one memory pool.
477  */
478 void BKE_mesh_edge_poly_map_create(MeshElemMap **r_map,
479                                    int **r_mem,
480                                    const MEdge *UNUSED(medge),
481                                    const int totedge,
482                                    const MPoly *mpoly,
483                                    const int totpoly,
484                                    const MLoop *mloop,
485                                    const int totloop)
486 {
487   MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * (size_t)totedge, "edge-poly map");
488   int *indices = MEM_mallocN(sizeof(int) * (size_t)totloop, "edge-poly map mem");
489   int *index_step;
490   const MPoly *mp;
491   int i;
492
493   /* count face users */
494   for (i = 0, mp = mpoly; i < totpoly; mp++, i++) {
495     const MLoop *ml;
496     int j = mp->totloop;
497     for (ml = &mloop[mp->loopstart]; j--; ml++) {
498       map[ml->e].count++;
499     }
500   }
501
502   /* create offsets */
503   index_step = indices;
504   for (i = 0; i < totedge; i++) {
505     map[i].indices = index_step;
506     index_step += map[i].count;
507
508     /* re-count, using this as an index below */
509     map[i].count = 0;
510   }
511
512   /* assign poly-edge users */
513   for (i = 0, mp = mpoly; i < totpoly; mp++, i++) {
514     const MLoop *ml;
515     int j = mp->totloop;
516     for (ml = &mloop[mp->loopstart]; j--; ml++) {
517       MeshElemMap *map_ele = &map[ml->e];
518       map_ele->indices[map_ele->count++] = i;
519     }
520   }
521
522   *r_map = map;
523   *r_mem = indices;
524 }
525
526 /**
527  * This function creates a map so the source-data (vert/edge/loop/poly)
528  * can loop over the destination data (using the destination arrays origindex).
529  *
530  * This has the advantage that it can operate on any data-types.
531  *
532  * \param totsource: The total number of elements the that \a final_origindex points to.
533  * \param totfinal: The size of \a final_origindex
534  * \param final_origindex: The size of the final array.
535  *
536  * \note ``totsource`` could be ``totpoly``,
537  *       ``totfinal`` could be ``tottessface`` and ``final_origindex`` its ORIGINDEX customdata.
538  *       This would allow an MPoly to loop over its tessfaces.
539  */
540 void BKE_mesh_origindex_map_create(MeshElemMap **r_map,
541                                    int **r_mem,
542                                    const int totsource,
543                                    const int *final_origindex,
544                                    const int totfinal)
545 {
546   MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * (size_t)totsource, "poly-tessface map");
547   int *indices = MEM_mallocN(sizeof(int) * (size_t)totfinal, "poly-tessface map mem");
548   int *index_step;
549   int i;
550
551   /* count face users */
552   for (i = 0; i < totfinal; i++) {
553     if (final_origindex[i] != ORIGINDEX_NONE) {
554       BLI_assert(final_origindex[i] < totsource);
555       map[final_origindex[i]].count++;
556     }
557   }
558
559   /* create offsets */
560   index_step = indices;
561   for (i = 0; i < totsource; i++) {
562     map[i].indices = index_step;
563     index_step += map[i].count;
564
565     /* re-count, using this as an index below */
566     map[i].count = 0;
567   }
568
569   /* assign poly-tessface users */
570   for (i = 0; i < totfinal; i++) {
571     if (final_origindex[i] != ORIGINDEX_NONE) {
572       MeshElemMap *map_ele = &map[final_origindex[i]];
573       map_ele->indices[map_ele->count++] = i;
574     }
575   }
576
577   *r_map = map;
578   *r_mem = indices;
579 }
580
581 /**
582  * A version of #BKE_mesh_origindex_map_create that takes a looptri array.
583  * Making a poly -> looptri map.
584  */
585 void BKE_mesh_origindex_map_create_looptri(MeshElemMap **r_map,
586                                            int **r_mem,
587                                            const MPoly *mpoly,
588                                            const int mpoly_num,
589                                            const MLoopTri *looptri,
590                                            const int looptri_num)
591 {
592   MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * (size_t)mpoly_num, "poly-tessface map");
593   int *indices = MEM_mallocN(sizeof(int) * (size_t)looptri_num, "poly-tessface map mem");
594   int *index_step;
595   int i;
596
597   /* create offsets */
598   index_step = indices;
599   for (i = 0; i < mpoly_num; i++) {
600     map[i].indices = index_step;
601     index_step += ME_POLY_TRI_TOT(&mpoly[i]);
602   }
603
604   /* assign poly-tessface users */
605   for (i = 0; i < looptri_num; i++) {
606     MeshElemMap *map_ele = &map[looptri[i].poly];
607     map_ele->indices[map_ele->count++] = i;
608   }
609
610   *r_map = map;
611   *r_mem = indices;
612 }
613
614 /** \} */
615
616 /* -------------------------------------------------------------------- */
617 /** \name Mesh loops/poly islands.
618  * Used currently for UVs and 'smooth groups'.
619  * \{ */
620
621 /**
622  * Callback deciding whether the given poly/loop/edge define an island boundary or not.
623  */
624 typedef bool (*MeshRemap_CheckIslandBoundary)(const struct MPoly *mpoly,
625                                               const struct MLoop *mloop,
626                                               const struct MEdge *medge,
627                                               const int nbr_egde_users,
628                                               void *user_data);
629
630 static void poly_edge_loop_islands_calc(const MEdge *medge,
631                                         const int totedge,
632                                         const MPoly *mpoly,
633                                         const int totpoly,
634                                         const MLoop *mloop,
635                                         const int totloop,
636                                         MeshElemMap *edge_poly_map,
637                                         const bool use_bitflags,
638                                         MeshRemap_CheckIslandBoundary edge_boundary_check,
639                                         void *edge_boundary_check_data,
640                                         int **r_poly_groups,
641                                         int *r_totgroup,
642                                         BLI_bitmap **r_edge_borders,
643                                         int *r_totedgeborder)
644 {
645   int *poly_groups;
646   int *poly_stack;
647
648   BLI_bitmap *edge_borders = NULL;
649   int num_edgeborders = 0;
650
651   int poly_prev = 0;
652   const int temp_poly_group_id = 3; /* Placeholder value. */
653   const int poly_group_id_overflowed =
654       5; /* Group we could not find any available bit, will be reset to 0 at end */
655   int tot_group = 0;
656   bool group_id_overflow = false;
657
658   /* map vars */
659   int *edge_poly_mem = NULL;
660
661   if (totpoly == 0) {
662     *r_totgroup = 0;
663     *r_poly_groups = NULL;
664     if (r_edge_borders) {
665       *r_edge_borders = NULL;
666       *r_totedgeborder = 0;
667     }
668     return;
669   }
670
671   if (r_edge_borders) {
672     edge_borders = BLI_BITMAP_NEW(totedge, __func__);
673     *r_totedgeborder = 0;
674   }
675
676   if (!edge_poly_map) {
677     BKE_mesh_edge_poly_map_create(
678         &edge_poly_map, &edge_poly_mem, medge, totedge, mpoly, totpoly, mloop, totloop);
679   }
680
681   poly_groups = MEM_callocN(sizeof(int) * (size_t)totpoly, __func__);
682   poly_stack = MEM_mallocN(sizeof(int) * (size_t)totpoly, __func__);
683
684   while (true) {
685     int poly;
686     int bit_poly_group_mask = 0;
687     int poly_group_id;
688     int ps_curr_idx = 0, ps_end_idx = 0; /* stack indices */
689
690     for (poly = poly_prev; poly < totpoly; poly++) {
691       if (poly_groups[poly] == 0) {
692         break;
693       }
694     }
695
696     if (poly == totpoly) {
697       /* all done */
698       break;
699     }
700
701     poly_group_id = use_bitflags ? temp_poly_group_id : ++tot_group;
702
703     /* start searching from here next time */
704     poly_prev = poly + 1;
705
706     poly_groups[poly] = poly_group_id;
707     poly_stack[ps_end_idx++] = poly;
708
709     while (ps_curr_idx != ps_end_idx) {
710       const MPoly *mp;
711       const MLoop *ml;
712       int j;
713
714       poly = poly_stack[ps_curr_idx++];
715       BLI_assert(poly_groups[poly] == poly_group_id);
716
717       mp = &mpoly[poly];
718       for (ml = &mloop[mp->loopstart], j = mp->totloop; j--; ml++) {
719         /* loop over poly users */
720         const int me_idx = (int)ml->e;
721         const MEdge *me = &medge[me_idx];
722         const MeshElemMap *map_ele = &edge_poly_map[me_idx];
723         const int *p = map_ele->indices;
724         int i = map_ele->count;
725         if (!edge_boundary_check(mp, ml, me, i, edge_boundary_check_data)) {
726           for (; i--; p++) {
727             /* if we meet other non initialized its a bug */
728             BLI_assert(ELEM(poly_groups[*p], 0, poly_group_id));
729
730             if (poly_groups[*p] == 0) {
731               poly_groups[*p] = poly_group_id;
732               poly_stack[ps_end_idx++] = *p;
733             }
734           }
735         }
736         else {
737           if (edge_borders && !BLI_BITMAP_TEST(edge_borders, me_idx)) {
738             BLI_BITMAP_ENABLE(edge_borders, me_idx);
739             num_edgeborders++;
740           }
741           if (use_bitflags) {
742             /* Find contiguous smooth groups already assigned, these are the values we can't reuse! */
743             for (; i--; p++) {
744               int bit = poly_groups[*p];
745               if (!ELEM(bit, 0, poly_group_id, poly_group_id_overflowed) &&
746                   !(bit_poly_group_mask & bit)) {
747                 bit_poly_group_mask |= bit;
748               }
749             }
750           }
751         }
752       }
753     }
754     /* And now, we have all our poly from current group in poly_stack (from 0 to (ps_end_idx - 1)), as well as
755      * all smoothgroups bits we can't use in bit_poly_group_mask.
756      */
757     if (use_bitflags) {
758       int i, *p, gid_bit = 0;
759       poly_group_id = 1;
760
761       /* Find first bit available! */
762       for (; (poly_group_id & bit_poly_group_mask) && (gid_bit < 32); gid_bit++) {
763         poly_group_id <<= 1; /* will 'overflow' on last possible iteration. */
764       }
765       if (UNLIKELY(gid_bit > 31)) {
766         /* All bits used in contiguous smooth groups, we can't do much!
767          * Note: this is *very* unlikely - theoretically, four groups are enough, I don't think we can reach
768          *       this goal with such a simple algo, but I don't think either we'll never need all 32 groups!
769          */
770         printf(
771             "Warning, could not find an available id for current smooth group, faces will me "
772             "marked "
773             "as out of any smooth group...\n");
774         poly_group_id =
775             poly_group_id_overflowed; /* Can't use 0, will have to set them to this value later. */
776         group_id_overflow = true;
777       }
778       if (gid_bit > tot_group) {
779         tot_group = gid_bit;
780       }
781       /* And assign the final smooth group id to that poly group! */
782       for (i = ps_end_idx, p = poly_stack; i--; p++) {
783         poly_groups[*p] = poly_group_id;
784       }
785     }
786   }
787
788   if (use_bitflags) {
789     /* used bits are zero-based. */
790     tot_group++;
791   }
792
793   if (UNLIKELY(group_id_overflow)) {
794     int i = totpoly, *gid = poly_groups;
795     for (; i--; gid++) {
796       if (*gid == poly_group_id_overflowed) {
797         *gid = 0;
798       }
799     }
800     /* Using 0 as group id adds one more group! */
801     tot_group++;
802   }
803
804   if (edge_poly_mem) {
805     MEM_freeN(edge_poly_map);
806     MEM_freeN(edge_poly_mem);
807   }
808   MEM_freeN(poly_stack);
809
810   *r_totgroup = tot_group;
811   *r_poly_groups = poly_groups;
812   if (r_edge_borders) {
813     *r_edge_borders = edge_borders;
814     *r_totedgeborder = num_edgeborders;
815   }
816 }
817
818 static bool poly_is_island_boundary_smooth_cb(const MPoly *mp,
819                                               const MLoop *UNUSED(ml),
820                                               const MEdge *me,
821                                               const int nbr_egde_users,
822                                               void *UNUSED(user_data))
823 {
824   /* Edge is sharp if its poly is sharp, or edge itself is sharp, or edge is not used by exactly two polygons. */
825   return (!(mp->flag & ME_SMOOTH) || (me->flag & ME_SHARP) || (nbr_egde_users != 2));
826 }
827
828 /**
829  * Calculate smooth groups from sharp edges.
830  *
831  * \param r_totgroup: The total number of groups, 1 or more.
832  * \return Polygon aligned array of group index values (bitflags if use_bitflags is true), starting at 1
833  *         (0 being used as 'invalid' flag).
834  *         Note it's callers's responsibility to MEM_freeN returned array.
835  */
836 int *BKE_mesh_calc_smoothgroups(const MEdge *medge,
837                                 const int totedge,
838                                 const MPoly *mpoly,
839                                 const int totpoly,
840                                 const MLoop *mloop,
841                                 const int totloop,
842                                 int *r_totgroup,
843                                 const bool use_bitflags)
844 {
845   int *poly_groups = NULL;
846
847   poly_edge_loop_islands_calc(medge,
848                               totedge,
849                               mpoly,
850                               totpoly,
851                               mloop,
852                               totloop,
853                               NULL,
854                               use_bitflags,
855                               poly_is_island_boundary_smooth_cb,
856                               NULL,
857                               &poly_groups,
858                               r_totgroup,
859                               NULL,
860                               NULL);
861
862   return poly_groups;
863 }
864
865 #define MISLAND_DEFAULT_BUFSIZE 64
866
867 void BKE_mesh_loop_islands_init(MeshIslandStore *island_store,
868                                 const short item_type,
869                                 const int items_num,
870                                 const short island_type,
871                                 const short innercut_type)
872 {
873   MemArena *mem = island_store->mem;
874
875   if (mem == NULL) {
876     mem = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
877     island_store->mem = mem;
878   }
879   /* else memarena should be cleared */
880
881   BLI_assert(
882       ELEM(item_type, MISLAND_TYPE_VERT, MISLAND_TYPE_EDGE, MISLAND_TYPE_POLY, MISLAND_TYPE_LOOP));
883   BLI_assert(ELEM(
884       island_type, MISLAND_TYPE_VERT, MISLAND_TYPE_EDGE, MISLAND_TYPE_POLY, MISLAND_TYPE_LOOP));
885
886   island_store->item_type = item_type;
887   island_store->items_to_islands_num = items_num;
888   island_store->items_to_islands = BLI_memarena_alloc(
889       mem, sizeof(*island_store->items_to_islands) * (size_t)items_num);
890
891   island_store->island_type = island_type;
892   island_store->islands_num_alloc = MISLAND_DEFAULT_BUFSIZE;
893   island_store->islands = BLI_memarena_alloc(
894       mem, sizeof(*island_store->islands) * island_store->islands_num_alloc);
895
896   island_store->innercut_type = innercut_type;
897   island_store->innercuts = BLI_memarena_alloc(
898       mem, sizeof(*island_store->innercuts) * island_store->islands_num_alloc);
899 }
900
901 void BKE_mesh_loop_islands_clear(MeshIslandStore *island_store)
902 {
903   island_store->item_type = MISLAND_TYPE_NONE;
904   island_store->items_to_islands_num = 0;
905   island_store->items_to_islands = NULL;
906
907   island_store->island_type = MISLAND_TYPE_NONE;
908   island_store->islands_num = 0;
909   island_store->islands = NULL;
910
911   island_store->innercut_type = MISLAND_TYPE_NONE;
912   island_store->innercuts = NULL;
913
914   if (island_store->mem) {
915     BLI_memarena_clear(island_store->mem);
916   }
917
918   island_store->islands_num_alloc = 0;
919 }
920
921 void BKE_mesh_loop_islands_free(MeshIslandStore *island_store)
922 {
923   if (island_store->mem) {
924     BLI_memarena_free(island_store->mem);
925     island_store->mem = NULL;
926   }
927 }
928
929 void BKE_mesh_loop_islands_add(MeshIslandStore *island_store,
930                                const int item_num,
931                                int *items_indices,
932                                const int num_island_items,
933                                int *island_item_indices,
934                                const int num_innercut_items,
935                                int *innercut_item_indices)
936 {
937   MemArena *mem = island_store->mem;
938
939   MeshElemMap *isld, *innrcut;
940   const int curr_island_idx = island_store->islands_num++;
941   const size_t curr_num_islands = (size_t)island_store->islands_num;
942   int i = item_num;
943
944   while (i--) {
945     island_store->items_to_islands[items_indices[i]] = curr_island_idx;
946   }
947
948   if (UNLIKELY(curr_num_islands > island_store->islands_num_alloc)) {
949     MeshElemMap **islds, **innrcuts;
950
951     island_store->islands_num_alloc *= 2;
952     islds = BLI_memarena_alloc(mem, sizeof(*islds) * island_store->islands_num_alloc);
953     memcpy(islds, island_store->islands, sizeof(*islds) * (curr_num_islands - 1));
954     island_store->islands = islds;
955
956     innrcuts = BLI_memarena_alloc(mem, sizeof(*innrcuts) * island_store->islands_num_alloc);
957     memcpy(innrcuts, island_store->innercuts, sizeof(*innrcuts) * (curr_num_islands - 1));
958     island_store->innercuts = innrcuts;
959   }
960
961   island_store->islands[curr_island_idx] = isld = BLI_memarena_alloc(mem, sizeof(*isld));
962   isld->count = num_island_items;
963   isld->indices = BLI_memarena_alloc(mem, sizeof(*isld->indices) * (size_t)num_island_items);
964   memcpy(isld->indices, island_item_indices, sizeof(*isld->indices) * (size_t)num_island_items);
965
966   island_store->innercuts[curr_island_idx] = innrcut = BLI_memarena_alloc(mem, sizeof(*innrcut));
967   innrcut->count = num_innercut_items;
968   innrcut->indices = BLI_memarena_alloc(mem,
969                                         sizeof(*innrcut->indices) * (size_t)num_innercut_items);
970   memcpy(innrcut->indices,
971          innercut_item_indices,
972          sizeof(*innrcut->indices) * (size_t)num_innercut_items);
973 }
974
975 /* TODO: I'm not sure edge seam flag is enough to define UV islands? Maybe we should also consider UVmaps values
976  *       themselves (i.e. different UV-edges for a same mesh-edge => boundary edge too?).
977  *       Would make things much more complex though, and each UVMap would then need its own mesh mapping,
978  *       not sure we want that at all!
979  */
980 typedef struct MeshCheckIslandBoundaryUv {
981   const MLoop *loops;
982   const MLoopUV *luvs;
983   const MeshElemMap *edge_loop_map;
984 } MeshCheckIslandBoundaryUv;
985
986 static bool mesh_check_island_boundary_uv(const MPoly *UNUSED(mp),
987                                           const MLoop *ml,
988                                           const MEdge *me,
989                                           const int UNUSED(nbr_egde_users),
990                                           void *user_data)
991 {
992   if (user_data) {
993     const MeshCheckIslandBoundaryUv *data = user_data;
994     const MLoop *loops = data->loops;
995     const MLoopUV *luvs = data->luvs;
996     const MeshElemMap *edge_to_loops = &data->edge_loop_map[ml->e];
997
998     BLI_assert(edge_to_loops->count >= 2 && (edge_to_loops->count % 2) == 0);
999
1000     const unsigned int v1 = loops[edge_to_loops->indices[0]].v;
1001     const unsigned int v2 = loops[edge_to_loops->indices[1]].v;
1002     const float *uvco_v1 = luvs[edge_to_loops->indices[0]].uv;
1003     const float *uvco_v2 = luvs[edge_to_loops->indices[1]].uv;
1004     for (int i = 2; i < edge_to_loops->count; i += 2) {
1005       if (loops[edge_to_loops->indices[i]].v == v1) {
1006         if (!equals_v2v2(uvco_v1, luvs[edge_to_loops->indices[i]].uv) ||
1007             !equals_v2v2(uvco_v2, luvs[edge_to_loops->indices[i + 1]].uv)) {
1008           return true;
1009         }
1010       }
1011       else {
1012         BLI_assert(loops[edge_to_loops->indices[i]].v == v2);
1013         UNUSED_VARS_NDEBUG(v2);
1014         if (!equals_v2v2(uvco_v2, luvs[edge_to_loops->indices[i]].uv) ||
1015             !equals_v2v2(uvco_v1, luvs[edge_to_loops->indices[i + 1]].uv)) {
1016           return true;
1017         }
1018       }
1019     }
1020     return false;
1021   }
1022   else {
1023     /* Edge is UV boundary if tagged as seam. */
1024     return (me->flag & ME_SEAM) != 0;
1025   }
1026 }
1027
1028 static bool mesh_calc_islands_loop_poly_uv(MVert *UNUSED(verts),
1029                                            const int UNUSED(totvert),
1030                                            MEdge *edges,
1031                                            const int totedge,
1032                                            MPoly *polys,
1033                                            const int totpoly,
1034                                            MLoop *loops,
1035                                            const int totloop,
1036                                            const MLoopUV *luvs,
1037                                            MeshIslandStore *r_island_store)
1038 {
1039   int *poly_groups = NULL;
1040   int num_poly_groups;
1041
1042   /* map vars */
1043   MeshElemMap *edge_poly_map;
1044   int *edge_poly_mem;
1045
1046   MeshElemMap *edge_loop_map;
1047   int *edge_loop_mem;
1048
1049   MeshCheckIslandBoundaryUv edge_boundary_check_data;
1050
1051   int *poly_indices;
1052   int *loop_indices;
1053   int num_pidx, num_lidx;
1054
1055   /* Those are used to detect 'inner cuts', i.e. edges that are borders, and yet have two or more polys of
1056    * a same group using them (typical case: seam used to unwrap properly a cylinder). */
1057   BLI_bitmap *edge_borders = NULL;
1058   int num_edge_borders = 0;
1059   char *edge_border_count = NULL;
1060   int *edge_innercut_indices = NULL;
1061   int num_einnercuts = 0;
1062
1063   int grp_idx, p_idx, pl_idx, l_idx;
1064
1065   BKE_mesh_loop_islands_clear(r_island_store);
1066   BKE_mesh_loop_islands_init(
1067       r_island_store, MISLAND_TYPE_LOOP, totloop, MISLAND_TYPE_POLY, MISLAND_TYPE_EDGE);
1068
1069   BKE_mesh_edge_poly_map_create(
1070       &edge_poly_map, &edge_poly_mem, edges, totedge, polys, totpoly, loops, totloop);
1071
1072   if (luvs) {
1073     BKE_mesh_edge_loop_map_create(
1074         &edge_loop_map, &edge_loop_mem, edges, totedge, polys, totpoly, loops, totloop);
1075     edge_boundary_check_data.loops = loops;
1076     edge_boundary_check_data.luvs = luvs;
1077     edge_boundary_check_data.edge_loop_map = edge_loop_map;
1078   }
1079
1080   poly_edge_loop_islands_calc(edges,
1081                               totedge,
1082                               polys,
1083                               totpoly,
1084                               loops,
1085                               totloop,
1086                               edge_poly_map,
1087                               false,
1088                               mesh_check_island_boundary_uv,
1089                               luvs ? &edge_boundary_check_data : NULL,
1090                               &poly_groups,
1091                               &num_poly_groups,
1092                               &edge_borders,
1093                               &num_edge_borders);
1094
1095   if (!num_poly_groups) {
1096     /* Should never happen... */
1097     MEM_freeN(edge_poly_map);
1098     MEM_freeN(edge_poly_mem);
1099
1100     if (edge_borders) {
1101       MEM_freeN(edge_borders);
1102     }
1103     return false;
1104   }
1105
1106   if (num_edge_borders) {
1107     edge_border_count = MEM_mallocN(sizeof(*edge_border_count) * (size_t)totedge, __func__);
1108     edge_innercut_indices = MEM_mallocN(sizeof(*edge_innercut_indices) * (size_t)num_edge_borders,
1109                                         __func__);
1110   }
1111
1112   poly_indices = MEM_mallocN(sizeof(*poly_indices) * (size_t)totpoly, __func__);
1113   loop_indices = MEM_mallocN(sizeof(*loop_indices) * (size_t)totloop, __func__);
1114
1115   /* Note: here we ignore '0' invalid group - this should *never* happen in this case anyway? */
1116   for (grp_idx = 1; grp_idx <= num_poly_groups; grp_idx++) {
1117     num_pidx = num_lidx = 0;
1118     if (num_edge_borders) {
1119       num_einnercuts = 0;
1120       memset(edge_border_count, 0, sizeof(*edge_border_count) * (size_t)totedge);
1121     }
1122
1123     for (p_idx = 0; p_idx < totpoly; p_idx++) {
1124       MPoly *mp;
1125
1126       if (poly_groups[p_idx] != grp_idx) {
1127         continue;
1128       }
1129
1130       mp = &polys[p_idx];
1131       poly_indices[num_pidx++] = p_idx;
1132       for (l_idx = mp->loopstart, pl_idx = 0; pl_idx < mp->totloop; l_idx++, pl_idx++) {
1133         MLoop *ml = &loops[l_idx];
1134         loop_indices[num_lidx++] = l_idx;
1135         if (num_edge_borders && BLI_BITMAP_TEST(edge_borders, ml->e) &&
1136             (edge_border_count[ml->e] < 2)) {
1137           edge_border_count[ml->e]++;
1138           if (edge_border_count[ml->e] == 2) {
1139             edge_innercut_indices[num_einnercuts++] = (int)ml->e;
1140           }
1141         }
1142       }
1143     }
1144
1145     BKE_mesh_loop_islands_add(r_island_store,
1146                               num_lidx,
1147                               loop_indices,
1148                               num_pidx,
1149                               poly_indices,
1150                               num_einnercuts,
1151                               edge_innercut_indices);
1152   }
1153
1154   MEM_freeN(edge_poly_map);
1155   MEM_freeN(edge_poly_mem);
1156
1157   if (luvs) {
1158     MEM_freeN(edge_loop_map);
1159     MEM_freeN(edge_loop_mem);
1160   }
1161
1162   MEM_freeN(poly_indices);
1163   MEM_freeN(loop_indices);
1164   MEM_freeN(poly_groups);
1165
1166   if (edge_borders) {
1167     MEM_freeN(edge_borders);
1168   }
1169
1170   if (num_edge_borders) {
1171     MEM_freeN(edge_border_count);
1172     MEM_freeN(edge_innercut_indices);
1173   }
1174   return true;
1175 }
1176
1177 /**
1178  * Calculate 'generic' UV islands, i.e. based only on actual geometry data (edge seams), not some UV layers coordinates.
1179  */
1180 bool BKE_mesh_calc_islands_loop_poly_edgeseam(MVert *verts,
1181                                               const int totvert,
1182                                               MEdge *edges,
1183                                               const int totedge,
1184                                               MPoly *polys,
1185                                               const int totpoly,
1186                                               MLoop *loops,
1187                                               const int totloop,
1188                                               MeshIslandStore *r_island_store)
1189 {
1190   return mesh_calc_islands_loop_poly_uv(
1191       verts, totvert, edges, totedge, polys, totpoly, loops, totloop, NULL, r_island_store);
1192 }
1193
1194 /**
1195  * Calculate UV islands.
1196  *
1197  * \note If no MLoopUV layer is passed, we only consider edges tagged as seams as UV boundaries.
1198  *     This has the advantages of simplicity, and being valid/common to all UV maps.
1199  *     However, it means actual UV islands without matching UV seams will not be handled correctly...
1200  *     If a valid UV layer is passed as \a luvs parameter, UV coordinates are also used to detect islands boundaries.
1201  *
1202  * \note All this could be optimized...
1203  *     Not sure it would be worth the more complex code, though, those loops are supposed to be really quick to do...
1204  */
1205 bool BKE_mesh_calc_islands_loop_poly_uvmap(MVert *verts,
1206                                            const int totvert,
1207                                            MEdge *edges,
1208                                            const int totedge,
1209                                            MPoly *polys,
1210                                            const int totpoly,
1211                                            MLoop *loops,
1212                                            const int totloop,
1213                                            const MLoopUV *luvs,
1214                                            MeshIslandStore *r_island_store)
1215 {
1216   BLI_assert(luvs != NULL);
1217   return mesh_calc_islands_loop_poly_uv(
1218       verts, totvert, edges, totedge, polys, totpoly, loops, totloop, luvs, r_island_store);
1219 }
1220
1221 /** \} */