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