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