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