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