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