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