Cleanup: replace BKE_id_copy_ex by BKE_id_copy where possible.
[blender.git] / source / blender / blenkernel / intern / mesh.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  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17  * All rights reserved.
18  */
19
20 /** \file blender/blenkernel/intern/mesh.c
21  *  \ingroup bke
22  */
23
24 #include "MEM_guardedalloc.h"
25
26 #include "DNA_object_types.h"
27 #include "DNA_key_types.h"
28 #include "DNA_mesh_types.h"
29 #include "DNA_meshdata_types.h"
30
31 #include "BLI_utildefines.h"
32 #include "BLI_bitmap.h"
33 #include "BLI_math.h"
34 #include "BLI_linklist.h"
35 #include "BLI_memarena.h"
36 #include "BLI_edgehash.h"
37 #include "BLI_string.h"
38
39 #include "BKE_animsys.h"
40 #include "BKE_idcode.h"
41 #include "BKE_main.h"
42 #include "BKE_global.h"
43 #include "BKE_mesh.h"
44 #include "BKE_mesh_runtime.h"
45 #include "BKE_library.h"
46 #include "BKE_material.h"
47 #include "BKE_modifier.h"
48 #include "BKE_multires.h"
49 #include "BKE_object.h"
50 #include "BKE_editmesh.h"
51
52 #include "DEG_depsgraph.h"
53
54 enum {
55         MESHCMP_DVERT_WEIGHTMISMATCH = 1,
56         MESHCMP_DVERT_GROUPMISMATCH,
57         MESHCMP_DVERT_TOTGROUPMISMATCH,
58         MESHCMP_LOOPCOLMISMATCH,
59         MESHCMP_LOOPUVMISMATCH,
60         MESHCMP_LOOPMISMATCH,
61         MESHCMP_POLYVERTMISMATCH,
62         MESHCMP_POLYMISMATCH,
63         MESHCMP_EDGEUNKNOWN,
64         MESHCMP_VERTCOMISMATCH,
65         MESHCMP_CDLAYERS_MISMATCH,
66 };
67
68 static const char *cmpcode_to_str(int code)
69 {
70         switch (code) {
71                 case MESHCMP_DVERT_WEIGHTMISMATCH:
72                         return "Vertex Weight Mismatch";
73                 case MESHCMP_DVERT_GROUPMISMATCH:
74                         return "Vertex Group Mismatch";
75                 case MESHCMP_DVERT_TOTGROUPMISMATCH:
76                         return "Vertex Doesn't Belong To Same Number Of Groups";
77                 case MESHCMP_LOOPCOLMISMATCH:
78                         return "Vertex Color Mismatch";
79                 case MESHCMP_LOOPUVMISMATCH:
80                         return "UV Mismatch";
81                 case MESHCMP_LOOPMISMATCH:
82                         return "Loop Mismatch";
83                 case MESHCMP_POLYVERTMISMATCH:
84                         return "Loop Vert Mismatch In Poly Test";
85                 case MESHCMP_POLYMISMATCH:
86                         return "Loop Vert Mismatch";
87                 case MESHCMP_EDGEUNKNOWN:
88                         return "Edge Mismatch";
89                 case MESHCMP_VERTCOMISMATCH:
90                         return "Vertex Coordinate Mismatch";
91                 case MESHCMP_CDLAYERS_MISMATCH:
92                         return "CustomData Layer Count Mismatch";
93                 default:
94                         return "Mesh Comparison Code Unknown";
95         }
96 }
97
98 /* thresh is threshold for comparing vertices, uvs, vertex colors,
99  * weights, etc.*/
100 static int customdata_compare(CustomData *c1, CustomData *c2, Mesh *m1, Mesh *m2, const float thresh)
101 {
102         const float thresh_sq = thresh * thresh;
103         CustomDataLayer *l1, *l2;
104         int i, i1 = 0, i2 = 0, tot, j;
105
106         for (i = 0; i < c1->totlayer; i++) {
107                 if (ELEM(c1->layers[i].type, CD_MVERT, CD_MEDGE, CD_MPOLY,
108                          CD_MLOOPUV, CD_MLOOPCOL, CD_MDEFORMVERT))
109                 {
110                         i1++;
111                 }
112         }
113
114         for (i = 0; i < c2->totlayer; i++) {
115                 if (ELEM(c2->layers[i].type, CD_MVERT, CD_MEDGE, CD_MPOLY,
116                          CD_MLOOPUV, CD_MLOOPCOL, CD_MDEFORMVERT))
117                 {
118                         i2++;
119                 }
120         }
121
122         if (i1 != i2)
123                 return MESHCMP_CDLAYERS_MISMATCH;
124
125         l1 = c1->layers; l2 = c2->layers;
126         tot = i1;
127         i1 = 0; i2 = 0;
128         for (i = 0; i < tot; i++) {
129                 while (i1 < c1->totlayer && !ELEM(l1->type, CD_MVERT, CD_MEDGE, CD_MPOLY,
130                                                   CD_MLOOPUV, CD_MLOOPCOL, CD_MDEFORMVERT))
131                 {
132                         i1++;
133                         l1++;
134                 }
135
136                 while (i2 < c2->totlayer && !ELEM(l2->type, CD_MVERT, CD_MEDGE, CD_MPOLY,
137                                                   CD_MLOOPUV, CD_MLOOPCOL, CD_MDEFORMVERT))
138                 {
139                         i2++;
140                         l2++;
141                 }
142
143                 if (l1->type == CD_MVERT) {
144                         MVert *v1 = l1->data;
145                         MVert *v2 = l2->data;
146                         int vtot = m1->totvert;
147
148                         for (j = 0; j < vtot; j++, v1++, v2++) {
149                                 if (len_squared_v3v3(v1->co, v2->co) > thresh_sq)
150                                         return MESHCMP_VERTCOMISMATCH;
151                                 /* I don't care about normals, let's just do coordinates */
152                         }
153                 }
154
155                 /*we're order-agnostic for edges here*/
156                 if (l1->type == CD_MEDGE) {
157                         MEdge *e1 = l1->data;
158                         MEdge *e2 = l2->data;
159                         int etot = m1->totedge;
160                         EdgeHash *eh = BLI_edgehash_new_ex(__func__, etot);
161
162                         for (j = 0; j < etot; j++, e1++) {
163                                 BLI_edgehash_insert(eh, e1->v1, e1->v2, e1);
164                         }
165
166                         for (j = 0; j < etot; j++, e2++) {
167                                 if (!BLI_edgehash_lookup(eh, e2->v1, e2->v2))
168                                         return MESHCMP_EDGEUNKNOWN;
169                         }
170                         BLI_edgehash_free(eh, NULL);
171                 }
172
173                 if (l1->type == CD_MPOLY) {
174                         MPoly *p1 = l1->data;
175                         MPoly *p2 = l2->data;
176                         int ptot = m1->totpoly;
177
178                         for (j = 0; j < ptot; j++, p1++, p2++) {
179                                 MLoop *lp1, *lp2;
180                                 int k;
181
182                                 if (p1->totloop != p2->totloop)
183                                         return MESHCMP_POLYMISMATCH;
184
185                                 lp1 = m1->mloop + p1->loopstart;
186                                 lp2 = m2->mloop + p2->loopstart;
187
188                                 for (k = 0; k < p1->totloop; k++, lp1++, lp2++) {
189                                         if (lp1->v != lp2->v)
190                                                 return MESHCMP_POLYVERTMISMATCH;
191                                 }
192                         }
193                 }
194                 if (l1->type == CD_MLOOP) {
195                         MLoop *lp1 = l1->data;
196                         MLoop *lp2 = l2->data;
197                         int ltot = m1->totloop;
198
199                         for (j = 0; j < ltot; j++, lp1++, lp2++) {
200                                 if (lp1->v != lp2->v)
201                                         return MESHCMP_LOOPMISMATCH;
202                         }
203                 }
204                 if (l1->type == CD_MLOOPUV) {
205                         MLoopUV *lp1 = l1->data;
206                         MLoopUV *lp2 = l2->data;
207                         int ltot = m1->totloop;
208
209                         for (j = 0; j < ltot; j++, lp1++, lp2++) {
210                                 if (len_squared_v2v2(lp1->uv, lp2->uv) > thresh_sq)
211                                         return MESHCMP_LOOPUVMISMATCH;
212                         }
213                 }
214
215                 if (l1->type == CD_MLOOPCOL) {
216                         MLoopCol *lp1 = l1->data;
217                         MLoopCol *lp2 = l2->data;
218                         int ltot = m1->totloop;
219
220                         for (j = 0; j < ltot; j++, lp1++, lp2++) {
221                                 if (ABS(lp1->r - lp2->r) > thresh ||
222                                     ABS(lp1->g - lp2->g) > thresh ||
223                                     ABS(lp1->b - lp2->b) > thresh ||
224                                     ABS(lp1->a - lp2->a) > thresh)
225                                 {
226                                         return MESHCMP_LOOPCOLMISMATCH;
227                                 }
228                         }
229                 }
230
231                 if (l1->type == CD_MDEFORMVERT) {
232                         MDeformVert *dv1 = l1->data;
233                         MDeformVert *dv2 = l2->data;
234                         int dvtot = m1->totvert;
235
236                         for (j = 0; j < dvtot; j++, dv1++, dv2++) {
237                                 int k;
238                                 MDeformWeight *dw1 = dv1->dw, *dw2 = dv2->dw;
239
240                                 if (dv1->totweight != dv2->totweight)
241                                         return MESHCMP_DVERT_TOTGROUPMISMATCH;
242
243                                 for (k = 0; k < dv1->totweight; k++, dw1++, dw2++) {
244                                         if (dw1->def_nr != dw2->def_nr)
245                                                 return MESHCMP_DVERT_GROUPMISMATCH;
246                                         if (fabsf(dw1->weight - dw2->weight) > thresh)
247                                                 return MESHCMP_DVERT_WEIGHTMISMATCH;
248                                 }
249                         }
250                 }
251         }
252
253         return 0;
254 }
255
256 /**
257  * Used for unit testing; compares two meshes, checking only
258  * differences we care about.  should be usable with leaf's
259  * testing framework I get RNA work done, will use hackish
260  * testing code for now.
261  */
262 const char *BKE_mesh_cmp(Mesh *me1, Mesh *me2, float thresh)
263 {
264         int c;
265
266         if (!me1 || !me2)
267                 return "Requires two input meshes";
268
269         if (me1->totvert != me2->totvert)
270                 return "Number of verts don't match";
271
272         if (me1->totedge != me2->totedge)
273                 return "Number of edges don't match";
274
275         if (me1->totpoly != me2->totpoly)
276                 return "Number of faces don't match";
277
278         if (me1->totloop != me2->totloop)
279                 return "Number of loops don't match";
280
281         if ((c = customdata_compare(&me1->vdata, &me2->vdata, me1, me2, thresh)))
282                 return cmpcode_to_str(c);
283
284         if ((c = customdata_compare(&me1->edata, &me2->edata, me1, me2, thresh)))
285                 return cmpcode_to_str(c);
286
287         if ((c = customdata_compare(&me1->ldata, &me2->ldata, me1, me2, thresh)))
288                 return cmpcode_to_str(c);
289
290         if ((c = customdata_compare(&me1->pdata, &me2->pdata, me1, me2, thresh)))
291                 return cmpcode_to_str(c);
292
293         return NULL;
294 }
295
296 static void mesh_ensure_tessellation_customdata(Mesh *me)
297 {
298         if (UNLIKELY((me->totface != 0) && (me->totpoly == 0))) {
299                 /* Pass, otherwise this function  clears 'mface' before
300                  * versioning 'mface -> mpoly' code kicks in [#30583]
301                  *
302                  * Callers could also check but safer to do here - campbell */
303         }
304         else {
305                 const int tottex_original = CustomData_number_of_layers(&me->ldata, CD_MLOOPUV);
306                 const int totcol_original = CustomData_number_of_layers(&me->ldata, CD_MLOOPCOL);
307
308                 const int tottex_tessface = CustomData_number_of_layers(&me->fdata, CD_MTFACE);
309                 const int totcol_tessface = CustomData_number_of_layers(&me->fdata, CD_MCOL);
310
311                 if (tottex_tessface != tottex_original ||
312                     totcol_tessface != totcol_original)
313                 {
314                         BKE_mesh_tessface_clear(me);
315
316                         CustomData_from_bmeshpoly(&me->fdata, &me->ldata, me->totface);
317
318                         /* TODO - add some --debug-mesh option */
319                         if (G.debug & G_DEBUG) {
320                                 /* note: this warning may be un-called for if we are initializing the mesh for the
321                                  * first time from bmesh, rather then giving a warning about this we could be smarter
322                                  * and check if there was any data to begin with, for now just print the warning with
323                                  * some info to help troubleshoot what's going on - campbell */
324                                 printf("%s: warning! Tessellation uvs or vcol data got out of sync, "
325                                        "had to reset!\n    CD_MTFACE: %d != CD_MLOOPUV: %d || CD_MCOL: %d != CD_MLOOPCOL: %d\n",
326                                        __func__, tottex_tessface, tottex_original, totcol_tessface, totcol_original);
327                         }
328                 }
329         }
330 }
331
332 void BKE_mesh_ensure_skin_customdata(Mesh *me)
333 {
334         BMesh *bm = me->edit_btmesh ? me->edit_btmesh->bm : NULL;
335         MVertSkin *vs;
336
337         if (bm) {
338                 if (!CustomData_has_layer(&bm->vdata, CD_MVERT_SKIN)) {
339                         BMVert *v;
340                         BMIter iter;
341
342                         BM_data_layer_add(bm, &bm->vdata, CD_MVERT_SKIN);
343
344                         /* Mark an arbitrary vertex as root */
345                         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
346                                 vs = CustomData_bmesh_get(
347                                         &bm->vdata, v->head.data,
348                                         CD_MVERT_SKIN);
349                                 vs->flag |= MVERT_SKIN_ROOT;
350                                 break;
351                         }
352                 }
353         }
354         else {
355                 if (!CustomData_has_layer(&me->vdata, CD_MVERT_SKIN)) {
356                         vs = CustomData_add_layer(
357                                 &me->vdata,
358                                 CD_MVERT_SKIN,
359                                 CD_DEFAULT,
360                                 NULL,
361                                 me->totvert);
362
363                         /* Mark an arbitrary vertex as root */
364                         if (vs) {
365                                 vs->flag |= MVERT_SKIN_ROOT;
366                         }
367                 }
368         }
369 }
370
371 bool BKE_mesh_ensure_facemap_customdata(struct Mesh *me)
372 {
373         BMesh *bm = me->edit_btmesh ? me->edit_btmesh->bm : NULL;
374         bool changed = false;
375         if (bm) {
376                 if (!CustomData_has_layer(&bm->pdata, CD_FACEMAP)) {
377                         BM_data_layer_add(bm, &bm->pdata, CD_FACEMAP);
378                         changed = true;
379                 }
380         }
381         else {
382                 if (!CustomData_has_layer(&me->pdata, CD_FACEMAP)) {
383                         CustomData_add_layer(
384                                 &me->pdata,
385                                 CD_FACEMAP,
386                                 CD_DEFAULT,
387                                 NULL,
388                                 me->totpoly);
389                         changed = true;
390                 }
391         }
392         return changed;
393 }
394
395 bool BKE_mesh_clear_facemap_customdata(struct Mesh *me)
396 {
397         BMesh *bm = me->edit_btmesh ? me->edit_btmesh->bm : NULL;
398         bool changed = false;
399         if (bm) {
400                 if (CustomData_has_layer(&bm->pdata, CD_FACEMAP)) {
401                         BM_data_layer_free(bm, &bm->pdata, CD_FACEMAP);
402                         changed = true;
403                 }
404         }
405         else {
406                 if (CustomData_has_layer(&me->pdata, CD_FACEMAP)) {
407                         CustomData_free_layers(&me->pdata, CD_FACEMAP, me->totpoly);
408                         changed = true;
409                 }
410         }
411         return changed;
412 }
413
414 /* this ensures grouped customdata (e.g. mtexpoly and mloopuv and mtface, or
415  * mloopcol and mcol) have the same relative active/render/clone/mask indices.
416  *
417  * note that for undo mesh data we want to skip 'ensure_tess_cd' call since
418  * we don't want to store memory for tessface when its only used for older
419  * versions of the mesh. - campbell*/
420 static void mesh_update_linked_customdata(Mesh *me, const bool do_ensure_tess_cd)
421 {
422         if (do_ensure_tess_cd) {
423                 mesh_ensure_tessellation_customdata(me);
424         }
425
426         CustomData_bmesh_update_active_layers(&me->fdata, &me->ldata);
427 }
428
429 void BKE_mesh_update_customdata_pointers(Mesh *me, const bool do_ensure_tess_cd)
430 {
431         mesh_update_linked_customdata(me, do_ensure_tess_cd);
432
433         me->mvert = CustomData_get_layer(&me->vdata, CD_MVERT);
434         me->dvert = CustomData_get_layer(&me->vdata, CD_MDEFORMVERT);
435
436         me->medge = CustomData_get_layer(&me->edata, CD_MEDGE);
437
438         me->mface = CustomData_get_layer(&me->fdata, CD_MFACE);
439         me->mcol = CustomData_get_layer(&me->fdata, CD_MCOL);
440         me->mtface = CustomData_get_layer(&me->fdata, CD_MTFACE);
441
442         me->mpoly = CustomData_get_layer(&me->pdata, CD_MPOLY);
443         me->mloop = CustomData_get_layer(&me->ldata, CD_MLOOP);
444
445         me->mloopcol = CustomData_get_layer(&me->ldata, CD_MLOOPCOL);
446         me->mloopuv = CustomData_get_layer(&me->ldata, CD_MLOOPUV);
447 }
448
449 bool BKE_mesh_has_custom_loop_normals(Mesh *me)
450 {
451         if (me->edit_btmesh) {
452                 return CustomData_has_layer(&me->edit_btmesh->bm->ldata, CD_CUSTOMLOOPNORMAL);
453         }
454         else {
455                 return CustomData_has_layer(&me->ldata, CD_CUSTOMLOOPNORMAL);
456         }
457 }
458
459 /** Free (or release) any data used by this mesh (does not free the mesh itself). */
460 void BKE_mesh_free(Mesh *me)
461 {
462         BKE_animdata_free(&me->id, false);
463
464         BKE_mesh_runtime_clear_cache(me);
465
466         CustomData_free(&me->vdata, me->totvert);
467         CustomData_free(&me->edata, me->totedge);
468         CustomData_free(&me->fdata, me->totface);
469         CustomData_free(&me->ldata, me->totloop);
470         CustomData_free(&me->pdata, me->totpoly);
471
472         MEM_SAFE_FREE(me->mat);
473         MEM_SAFE_FREE(me->bb);
474         MEM_SAFE_FREE(me->mselect);
475         MEM_SAFE_FREE(me->edit_btmesh);
476 }
477
478 static void mesh_tessface_clear_intern(Mesh *mesh, int free_customdata)
479 {
480         if (free_customdata) {
481                 CustomData_free(&mesh->fdata, mesh->totface);
482         }
483         else {
484                 CustomData_reset(&mesh->fdata);
485         }
486
487         mesh->mface = NULL;
488         mesh->mtface = NULL;
489         mesh->mcol = NULL;
490         mesh->totface = 0;
491 }
492
493 void BKE_mesh_init(Mesh *me)
494 {
495         BLI_assert(MEMCMP_STRUCT_OFS_IS_ZERO(me, id));
496
497         me->size[0] = me->size[1] = me->size[2] = 1.0;
498         me->smoothresh = DEG2RADF(30);
499         me->texflag = ME_AUTOSPACE;
500
501         CustomData_reset(&me->vdata);
502         CustomData_reset(&me->edata);
503         CustomData_reset(&me->fdata);
504         CustomData_reset(&me->pdata);
505         CustomData_reset(&me->ldata);
506 }
507
508 Mesh *BKE_mesh_add(Main *bmain, const char *name)
509 {
510         Mesh *me;
511
512         me = BKE_libblock_alloc(bmain, ID_ME, name, 0);
513
514         BKE_mesh_init(me);
515
516         return me;
517 }
518
519 /**
520  * Only copy internal data of Mesh ID from source to already allocated/initialized destination.
521  * You probably nerver want to use that directly, use BKE_id_copy or BKE_id_copy_ex for typical needs.
522  *
523  * WARNING! This function will not handle ID user count!
524  *
525  * \param flag: Copying options (see BKE_library.h's LIB_ID_COPY_... flags for more).
526  */
527 void BKE_mesh_copy_data(Main *bmain, Mesh *me_dst, const Mesh *me_src, const int flag)
528 {
529         const bool do_tessface = ((me_src->totface != 0) && (me_src->totpoly == 0)); /* only do tessface if we have no polys */
530         CustomDataMask mask = CD_MASK_MESH;
531
532         if (me_src->id.tag & LIB_TAG_NO_MAIN) {
533                 /* For copies in depsgraph, keep data like origindex and orco. */
534                 mask |= CD_MASK_DERIVEDMESH;
535         }
536
537         me_dst->mat = MEM_dupallocN(me_src->mat);
538
539         const eCDAllocType alloc_type = (flag & LIB_ID_COPY_CD_REFERENCE) ? CD_REFERENCE : CD_DUPLICATE;
540         CustomData_copy(&me_src->vdata, &me_dst->vdata, mask, alloc_type, me_dst->totvert);
541         CustomData_copy(&me_src->edata, &me_dst->edata, mask, alloc_type, me_dst->totedge);
542         CustomData_copy(&me_src->ldata, &me_dst->ldata, mask, alloc_type, me_dst->totloop);
543         CustomData_copy(&me_src->pdata, &me_dst->pdata, mask, alloc_type, me_dst->totpoly);
544         if (do_tessface) {
545                 CustomData_copy(&me_src->fdata, &me_dst->fdata, mask, alloc_type, me_dst->totface);
546         }
547         else {
548                 mesh_tessface_clear_intern(me_dst, false);
549         }
550
551         BKE_mesh_update_customdata_pointers(me_dst, do_tessface);
552
553         me_dst->edit_btmesh = NULL;
554
555         /* Call BKE_mesh_runtime_reset? */
556         me_dst->runtime.batch_cache = NULL;
557         me_dst->runtime.looptris.array = NULL;
558         me_dst->runtime.bvh_cache = NULL;
559         me_dst->runtime.shrinkwrap_data = NULL;
560
561         if (me_src->id.tag & LIB_TAG_NO_MAIN) {
562                 me_dst->runtime.deformed_only = me_src->runtime.deformed_only;
563         }
564         else {
565                 /* This is a direct copy of a main mesh, so for now it has the same topology. */
566                 me_dst->runtime.deformed_only = 1;
567         }
568         me_dst->runtime.is_original = false;
569
570         me_dst->mselect = MEM_dupallocN(me_dst->mselect);
571         me_dst->bb = MEM_dupallocN(me_dst->bb);
572
573         /* TODO Do we want to add flag to prevent this? */
574         if (me_src->key && (flag & LIB_ID_COPY_SHAPEKEY)) {
575                 BKE_id_copy_ex(bmain, &me_src->key->id, (ID **)&me_dst->key, flag);
576         }
577 }
578
579 /* Custom data layer functions; those assume that totXXX are set correctly. */
580 static void mesh_ensure_cdlayers_primary(Mesh *mesh, bool do_tessface)
581 {
582         if (!CustomData_get_layer(&mesh->vdata, CD_MVERT))
583                 CustomData_add_layer(&mesh->vdata, CD_MVERT, CD_CALLOC, NULL, mesh->totvert);
584         if (!CustomData_get_layer(&mesh->edata, CD_MEDGE))
585                 CustomData_add_layer(&mesh->edata, CD_MEDGE, CD_CALLOC, NULL, mesh->totedge);
586         if (!CustomData_get_layer(&mesh->ldata, CD_MLOOP))
587                 CustomData_add_layer(&mesh->ldata, CD_MLOOP, CD_CALLOC, NULL, mesh->totloop);
588         if (!CustomData_get_layer(&mesh->pdata, CD_MPOLY))
589                 CustomData_add_layer(&mesh->pdata, CD_MPOLY, CD_CALLOC, NULL, mesh->totpoly);
590
591         if (do_tessface && !CustomData_get_layer(&mesh->fdata, CD_MFACE))
592                 CustomData_add_layer(&mesh->fdata, CD_MFACE, CD_CALLOC, NULL, mesh->totface);
593 }
594 static void mesh_ensure_cdlayers_origindex(Mesh *mesh, bool do_tessface)
595 {
596         if (!CustomData_get_layer(&mesh->vdata, CD_ORIGINDEX))
597                 CustomData_add_layer(&mesh->vdata, CD_ORIGINDEX, CD_CALLOC, NULL, mesh->totvert);
598         if (!CustomData_get_layer(&mesh->edata, CD_ORIGINDEX))
599                 CustomData_add_layer(&mesh->edata, CD_ORIGINDEX, CD_CALLOC, NULL, mesh->totedge);
600         if (!CustomData_get_layer(&mesh->pdata, CD_ORIGINDEX))
601                 CustomData_add_layer(&mesh->pdata, CD_ORIGINDEX, CD_CALLOC, NULL,  mesh->totpoly);
602
603         if (do_tessface && !CustomData_get_layer(&mesh->fdata, CD_ORIGINDEX))
604                 CustomData_add_layer(&mesh->fdata, CD_ORIGINDEX, CD_CALLOC, NULL, mesh->totface);
605 }
606
607 Mesh *BKE_mesh_new_nomain(int verts_len, int edges_len, int tessface_len, int loops_len, int polys_len)
608 {
609         Mesh *mesh = BKE_libblock_alloc(
610                 NULL, ID_ME,
611                 BKE_idcode_to_name(ID_ME),
612                 LIB_ID_COPY_LOCALIZE);
613         BKE_libblock_init_empty(&mesh->id);
614
615         /* don't use CustomData_reset(...); because we dont want to touch customdata */
616         copy_vn_i(mesh->vdata.typemap, CD_NUMTYPES, -1);
617         copy_vn_i(mesh->edata.typemap, CD_NUMTYPES, -1);
618         copy_vn_i(mesh->fdata.typemap, CD_NUMTYPES, -1);
619         copy_vn_i(mesh->ldata.typemap, CD_NUMTYPES, -1);
620         copy_vn_i(mesh->pdata.typemap, CD_NUMTYPES, -1);
621
622         mesh->totvert = verts_len;
623         mesh->totedge = edges_len;
624         mesh->totface = tessface_len;
625         mesh->totloop = loops_len;
626         mesh->totpoly = polys_len;
627
628         mesh_ensure_cdlayers_primary(mesh, true);
629         mesh_ensure_cdlayers_origindex(mesh, true);
630         BKE_mesh_update_customdata_pointers(mesh, false);
631
632         return mesh;
633 }
634
635 static Mesh *mesh_new_nomain_from_template_ex(
636         const Mesh *me_src,
637         int verts_len, int edges_len, int tessface_len,
638         int loops_len, int polys_len,
639         CustomDataMask mask)
640 {
641         /* Only do tessface if we are creating tessfaces or copying from mesh with only tessfaces. */
642         const bool do_tessface = (tessface_len ||
643                                   ((me_src->totface != 0) && (me_src->totpoly == 0)));
644
645         Mesh *me_dst = BKE_id_new_nomain(ID_ME, NULL);
646
647         me_dst->mat = MEM_dupallocN(me_src->mat);
648         me_dst->mselect = MEM_dupallocN(me_dst->mselect);
649
650         me_dst->totvert = verts_len;
651         me_dst->totedge = edges_len;
652         me_dst->totface = tessface_len;
653         me_dst->totloop = loops_len;
654         me_dst->totpoly = polys_len;
655
656         me_dst->cd_flag = me_src->cd_flag;
657
658         CustomData_copy(&me_src->vdata, &me_dst->vdata, mask, CD_CALLOC, verts_len);
659         CustomData_copy(&me_src->edata, &me_dst->edata, mask, CD_CALLOC, edges_len);
660         CustomData_copy(&me_src->ldata, &me_dst->ldata, mask, CD_CALLOC, loops_len);
661         CustomData_copy(&me_src->pdata, &me_dst->pdata, mask, CD_CALLOC, polys_len);
662         if (do_tessface) {
663                 CustomData_copy(&me_src->fdata, &me_dst->fdata, mask, CD_CALLOC, tessface_len);
664         }
665         else {
666                 mesh_tessface_clear_intern(me_dst, false);
667         }
668
669         /* The destination mesh should at least have valid primary CD layers,
670          * even in cases where the source mesh does not. */
671         mesh_ensure_cdlayers_primary(me_dst, do_tessface);
672         mesh_ensure_cdlayers_origindex(me_dst, false);
673         BKE_mesh_update_customdata_pointers(me_dst, false);
674
675         return me_dst;
676 }
677
678 Mesh *BKE_mesh_new_nomain_from_template(
679         const Mesh *me_src,
680         int verts_len, int edges_len, int tessface_len,
681         int loops_len, int polys_len)
682 {
683         return mesh_new_nomain_from_template_ex(
684                 me_src,
685                 verts_len, edges_len, tessface_len,
686                 loops_len, polys_len,
687                 CD_MASK_EVERYTHING);
688 }
689
690 Mesh *BKE_mesh_copy_for_eval(struct Mesh *source, bool reference)
691 {
692         int flags = LIB_ID_COPY_LOCALIZE;
693
694         if (reference) {
695                 flags |= LIB_ID_COPY_CD_REFERENCE;
696         }
697
698         Mesh *result;
699         BKE_id_copy_ex(NULL, &source->id, (ID **)&result, flags);
700         return result;
701 }
702
703 Mesh *BKE_mesh_copy(Main *bmain, const Mesh *me)
704 {
705         Mesh *me_copy;
706         BKE_id_copy(bmain, &me->id, (ID **)&me_copy);
707         return me_copy;
708 }
709
710 BMesh *BKE_mesh_to_bmesh_ex(
711         const Mesh *me,
712         const struct BMeshCreateParams *create_params,
713         const struct BMeshFromMeshParams *convert_params)
714 {
715         BMesh *bm;
716         const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_ME(me);
717
718         bm = BM_mesh_create(&allocsize, create_params);
719         BM_mesh_bm_from_me(bm, me, convert_params);
720
721         return bm;
722 }
723
724 BMesh *BKE_mesh_to_bmesh(
725         Mesh *me, Object *ob,
726         const bool add_key_index, const struct BMeshCreateParams *params)
727 {
728         return BKE_mesh_to_bmesh_ex(
729                 me, params,
730                 &(struct BMeshFromMeshParams){
731                     .calc_face_normal = false,
732                     .add_key_index = add_key_index,
733                     .use_shapekey = true,
734                     .active_shapekey = ob->shapenr,
735                 });
736 }
737
738 Mesh *BKE_mesh_from_bmesh_nomain(BMesh *bm, const struct BMeshToMeshParams *params)
739 {
740         BLI_assert(params->calc_object_remap == false);
741         Mesh *mesh = BKE_id_new_nomain(ID_ME, NULL);
742         BM_mesh_bm_to_me(NULL, bm, mesh, params);
743         return mesh;
744 }
745
746 Mesh *BKE_mesh_from_bmesh_for_eval_nomain(BMesh *bm, const int64_t cd_mask_extra)
747 {
748         Mesh *mesh = BKE_id_new_nomain(ID_ME, NULL);
749         BM_mesh_bm_to_me_for_eval(bm, mesh, cd_mask_extra);
750         return mesh;
751 }
752
753 /**
754  * TODO(campbell): support mesh with only an edit-mesh which is lazy initialized.
755  */
756 Mesh *BKE_mesh_from_editmesh_with_coords_thin_wrap(
757         BMEditMesh *em, CustomDataMask data_mask, float (*vertexCos)[3])
758 {
759         Mesh *me = BKE_mesh_from_bmesh_for_eval_nomain(em->bm, data_mask);
760         /* Use editmesh directly where possible. */
761         me->runtime.is_original = true;
762         if (vertexCos) {
763                 /* We will own this array in the future. */
764                 BKE_mesh_apply_vert_coords(me, vertexCos);
765                 MEM_freeN(vertexCos);
766                 me->runtime.is_original = false;
767         }
768         return me;
769 }
770
771 void BKE_mesh_make_local(Main *bmain, Mesh *me, const bool lib_local)
772 {
773         BKE_id_make_local_generic(bmain, &me->id, true, lib_local);
774 }
775
776 bool BKE_mesh_uv_cdlayer_rename_index(
777         Mesh *me, const int loop_index, const int face_index,
778         const char *new_name, const bool do_tessface)
779 {
780         CustomData *ldata, *fdata;
781         CustomDataLayer *cdlu, *cdlf;
782
783         if (me->edit_btmesh) {
784                 ldata = &me->edit_btmesh->bm->ldata;
785                 fdata = NULL;  /* No tessellated data in BMesh! */
786         }
787         else {
788                 ldata = &me->ldata;
789                 fdata = &me->fdata;
790         }
791
792         cdlu = &ldata->layers[loop_index];
793         cdlf = (face_index != -1) && fdata && do_tessface ? &fdata->layers[face_index] : NULL;
794
795         if (cdlu->name != new_name) {
796                 /* Mesh validate passes a name from the CD layer as the new name,
797                  * Avoid memcpy from self to self in this case.
798                  */
799                 BLI_strncpy(cdlu->name, new_name, sizeof(cdlu->name));
800                 CustomData_set_layer_unique_name(ldata, loop_index);
801         }
802
803         if (cdlf == NULL) {
804                 return false;
805         }
806
807         BLI_strncpy(cdlf->name, cdlu->name, sizeof(cdlf->name));
808         CustomData_set_layer_unique_name(fdata, face_index);
809
810         return true;
811 }
812
813 bool BKE_mesh_uv_cdlayer_rename(Mesh *me, const char *old_name, const char *new_name, bool do_tessface)
814 {
815         CustomData *ldata, *fdata;
816         if (me->edit_btmesh) {
817                 ldata = &me->edit_btmesh->bm->ldata;
818                 /* No tessellated data in BMesh! */
819                 fdata = NULL;
820                 do_tessface = false;
821         }
822         else {
823                 ldata = &me->ldata;
824                 fdata = &me->fdata;
825                 do_tessface = (do_tessface && fdata->totlayer);
826         }
827
828         {
829                 const int lidx_start = CustomData_get_layer_index(ldata, CD_MLOOPUV);
830                 const int fidx_start = do_tessface ? CustomData_get_layer_index(fdata, CD_MTFACE) : -1;
831                 int lidx = CustomData_get_named_layer(ldata, CD_MLOOPUV, old_name);
832                 int fidx = do_tessface ? CustomData_get_named_layer(fdata, CD_MTFACE, old_name) : -1;
833
834                 /* None of those cases should happen, in theory!
835                  * Note this assume we have the same number of mtexpoly, mloopuv and mtface layers!
836                  */
837                 if (lidx == -1) {
838                         if (fidx == -1) {
839                                 /* No layer found with this name! */
840                                 return false;
841                         }
842                         else {
843                                 lidx = fidx;
844                         }
845                 }
846
847                 /* Go back to absolute indices! */
848                 lidx += lidx_start;
849                 if (fidx != -1)
850                         fidx += fidx_start;
851
852                 return BKE_mesh_uv_cdlayer_rename_index(me, lidx, fidx, new_name, do_tessface);
853         }
854 }
855
856 void BKE_mesh_boundbox_calc(Mesh *me, float r_loc[3], float r_size[3])
857 {
858         BoundBox *bb;
859         float min[3], max[3];
860         float mloc[3], msize[3];
861
862         if (me->bb == NULL) me->bb = MEM_callocN(sizeof(BoundBox), "boundbox");
863         bb = me->bb;
864
865         if (!r_loc) r_loc = mloc;
866         if (!r_size) r_size = msize;
867
868         INIT_MINMAX(min, max);
869         if (!BKE_mesh_minmax(me, min, max)) {
870                 min[0] = min[1] = min[2] = -1.0f;
871                 max[0] = max[1] = max[2] = 1.0f;
872         }
873
874         mid_v3_v3v3(r_loc, min, max);
875
876         r_size[0] = (max[0] - min[0]) / 2.0f;
877         r_size[1] = (max[1] - min[1]) / 2.0f;
878         r_size[2] = (max[2] - min[2]) / 2.0f;
879
880         BKE_boundbox_init_from_minmax(bb, min, max);
881
882         bb->flag &= ~BOUNDBOX_DIRTY;
883 }
884
885 void BKE_mesh_texspace_calc(Mesh *me)
886 {
887         float loc[3], size[3];
888         int a;
889
890         BKE_mesh_boundbox_calc(me, loc, size);
891
892         if (me->texflag & ME_AUTOSPACE) {
893                 for (a = 0; a < 3; a++) {
894                         if (size[a] == 0.0f) size[a] = 1.0f;
895                         else if (size[a] > 0.0f && size[a] < 0.00001f) size[a] = 0.00001f;
896                         else if (size[a] < 0.0f && size[a] > -0.00001f) size[a] = -0.00001f;
897                 }
898
899                 copy_v3_v3(me->loc, loc);
900                 copy_v3_v3(me->size, size);
901                 zero_v3(me->rot);
902         }
903 }
904
905 BoundBox *BKE_mesh_boundbox_get(Object *ob)
906 {
907         /* This is Object-level data access, DO NOT touch to Mesh's bb, would be totally thread-unsafe. */
908         if (ob->bb == NULL || ob->bb->flag & BOUNDBOX_DIRTY) {
909                 Mesh *me = ob->data;
910                 float min[3], max[3];
911
912                 INIT_MINMAX(min, max);
913                 if (!BKE_mesh_minmax(me, min, max)) {
914                         min[0] = min[1] = min[2] = -1.0f;
915                         max[0] = max[1] = max[2] = 1.0f;
916                 }
917
918                 if (ob->bb == NULL) {
919                         ob->bb = MEM_mallocN(sizeof(*ob->bb), __func__);
920                 }
921                 BKE_boundbox_init_from_minmax(ob->bb, min, max);
922                 ob->bb->flag &= ~BOUNDBOX_DIRTY;
923         }
924
925         return ob->bb;
926 }
927
928 BoundBox *BKE_mesh_texspace_get(Mesh *me, float r_loc[3], float r_rot[3], float r_size[3])
929 {
930         if (me->bb == NULL || (me->bb->flag & BOUNDBOX_DIRTY)) {
931                 BKE_mesh_texspace_calc(me);
932         }
933
934         if (r_loc) copy_v3_v3(r_loc,  me->loc);
935         if (r_rot) copy_v3_v3(r_rot,  me->rot);
936         if (r_size) copy_v3_v3(r_size, me->size);
937
938         return me->bb;
939 }
940
941 void BKE_mesh_texspace_get_reference(Mesh *me, short **r_texflag,  float **r_loc, float **r_rot, float **r_size)
942 {
943         if (me->bb == NULL || (me->bb->flag & BOUNDBOX_DIRTY)) {
944                 BKE_mesh_texspace_calc(me);
945         }
946
947         if (r_texflag != NULL) *r_texflag = &me->texflag;
948         if (r_loc != NULL) *r_loc = me->loc;
949         if (r_rot != NULL) *r_rot = me->rot;
950         if (r_size != NULL) *r_size = me->size;
951 }
952
953 void BKE_mesh_texspace_copy_from_object(Mesh *me, Object *ob)
954 {
955         float *texloc, *texrot, *texsize;
956         short *texflag;
957
958         if (BKE_object_obdata_texspace_get(ob, &texflag, &texloc, &texsize, &texrot)) {
959                 me->texflag = *texflag;
960                 copy_v3_v3(me->loc, texloc);
961                 copy_v3_v3(me->size, texsize);
962                 copy_v3_v3(me->rot, texrot);
963         }
964 }
965
966 float (*BKE_mesh_orco_verts_get(Object *ob))[3]
967 {
968         Mesh *me = ob->data;
969         MVert *mvert = NULL;
970         Mesh *tme = me->texcomesh ? me->texcomesh : me;
971         int a, totvert;
972         float (*vcos)[3] = NULL;
973
974         /* Get appropriate vertex coordinates */
975         vcos = MEM_calloc_arrayN(me->totvert, sizeof(*vcos), "orco mesh");
976         mvert = tme->mvert;
977         totvert = min_ii(tme->totvert, me->totvert);
978
979         for (a = 0; a < totvert; a++, mvert++) {
980                 copy_v3_v3(vcos[a], mvert->co);
981         }
982
983         return vcos;
984 }
985
986 void BKE_mesh_orco_verts_transform(Mesh *me, float (*orco)[3], int totvert, int invert)
987 {
988         float loc[3], size[3];
989         int a;
990
991         BKE_mesh_texspace_get(me->texcomesh ? me->texcomesh : me, loc, NULL, size);
992
993         if (invert) {
994                 for (a = 0; a < totvert; a++) {
995                         float *co = orco[a];
996                         madd_v3_v3v3v3(co, loc, co, size);
997                 }
998         }
999         else {
1000                 for (a = 0; a < totvert; a++) {
1001                         float *co = orco[a];
1002                         co[0] = (co[0] - loc[0]) / size[0];
1003                         co[1] = (co[1] - loc[1]) / size[1];
1004                         co[2] = (co[2] - loc[2]) / size[2];
1005                 }
1006         }
1007 }
1008
1009 /* rotates the vertices of a face in case v[2] or v[3] (vertex index) is = 0.
1010  * this is necessary to make the if (mface->v4) check for quads work */
1011 int test_index_face(MFace *mface, CustomData *fdata, int mfindex, int nr)
1012 {
1013         /* first test if the face is legal */
1014         if ((mface->v3 || nr == 4) && mface->v3 == mface->v4) {
1015                 mface->v4 = 0;
1016                 nr--;
1017         }
1018         if ((mface->v2 || mface->v4) && mface->v2 == mface->v3) {
1019                 mface->v3 = mface->v4;
1020                 mface->v4 = 0;
1021                 nr--;
1022         }
1023         if (mface->v1 == mface->v2) {
1024                 mface->v2 = mface->v3;
1025                 mface->v3 = mface->v4;
1026                 mface->v4 = 0;
1027                 nr--;
1028         }
1029
1030         /* check corrupt cases, bow-tie geometry, cant handle these because edge data wont exist so just return 0 */
1031         if (nr == 3) {
1032                 if (
1033                     /* real edges */
1034                     mface->v1 == mface->v2 ||
1035                     mface->v2 == mface->v3 ||
1036                     mface->v3 == mface->v1)
1037                 {
1038                         return 0;
1039                 }
1040         }
1041         else if (nr == 4) {
1042                 if (
1043                     /* real edges */
1044                     mface->v1 == mface->v2 ||
1045                     mface->v2 == mface->v3 ||
1046                     mface->v3 == mface->v4 ||
1047                     mface->v4 == mface->v1 ||
1048                     /* across the face */
1049                     mface->v1 == mface->v3 ||
1050                     mface->v2 == mface->v4)
1051                 {
1052                         return 0;
1053                 }
1054         }
1055
1056         /* prevent a zero at wrong index location */
1057         if (nr == 3) {
1058                 if (mface->v3 == 0) {
1059                         static int corner_indices[4] = {1, 2, 0, 3};
1060
1061                         SWAP(unsigned int, mface->v1, mface->v2);
1062                         SWAP(unsigned int, mface->v2, mface->v3);
1063
1064                         if (fdata)
1065                                 CustomData_swap_corners(fdata, mfindex, corner_indices);
1066                 }
1067         }
1068         else if (nr == 4) {
1069                 if (mface->v3 == 0 || mface->v4 == 0) {
1070                         static int corner_indices[4] = {2, 3, 0, 1};
1071
1072                         SWAP(unsigned int, mface->v1, mface->v3);
1073                         SWAP(unsigned int, mface->v2, mface->v4);
1074
1075                         if (fdata)
1076                                 CustomData_swap_corners(fdata, mfindex, corner_indices);
1077                 }
1078         }
1079
1080         return nr;
1081 }
1082
1083 Mesh *BKE_mesh_from_object(Object *ob)
1084 {
1085
1086         if (ob == NULL) return NULL;
1087         if (ob->type == OB_MESH) return ob->data;
1088         else return NULL;
1089 }
1090
1091 void BKE_mesh_assign_object(Main *bmain, Object *ob, Mesh *me)
1092 {
1093         Mesh *old = NULL;
1094
1095         multires_force_update(ob);
1096
1097         if (ob == NULL) return;
1098
1099         if (ob->type == OB_MESH) {
1100                 old = ob->data;
1101                 if (old)
1102                         id_us_min(&old->id);
1103                 ob->data = me;
1104                 id_us_plus((ID *)me);
1105         }
1106
1107         test_object_materials(bmain, ob, (ID *)me);
1108
1109         test_object_modifiers(ob);
1110 }
1111
1112 void BKE_mesh_material_index_remove(Mesh *me, short index)
1113 {
1114         MPoly *mp;
1115         MFace *mf;
1116         int i;
1117
1118         for (mp = me->mpoly, i = 0; i < me->totpoly; i++, mp++) {
1119                 if (mp->mat_nr && mp->mat_nr >= index) {
1120                         mp->mat_nr--;
1121                 }
1122         }
1123
1124         for (mf = me->mface, i = 0; i < me->totface; i++, mf++) {
1125                 if (mf->mat_nr && mf->mat_nr >= index) {
1126                         mf->mat_nr--;
1127                 }
1128         }
1129 }
1130
1131 void BKE_mesh_material_index_clear(Mesh *me)
1132 {
1133         MPoly *mp;
1134         MFace *mf;
1135         int i;
1136
1137         for (mp = me->mpoly, i = 0; i < me->totpoly; i++, mp++) {
1138                 mp->mat_nr = 0;
1139         }
1140
1141         for (mf = me->mface, i = 0; i < me->totface; i++, mf++) {
1142                 mf->mat_nr = 0;
1143         }
1144 }
1145
1146 void BKE_mesh_material_remap(Mesh *me, const unsigned int *remap, unsigned int remap_len)
1147 {
1148         const short remap_len_short = (short)remap_len;
1149
1150 #define MAT_NR_REMAP(n) \
1151         if (n < remap_len_short) { \
1152                 BLI_assert(n >= 0 && remap[n] < remap_len_short); \
1153                 n = remap[n]; \
1154         } ((void)0)
1155
1156         if (me->edit_btmesh) {
1157                 BMEditMesh *em = me->edit_btmesh;
1158                 BMIter iter;
1159                 BMFace *efa;
1160
1161                 BM_ITER_MESH(efa, &iter, em->bm, BM_FACES_OF_MESH) {
1162                         MAT_NR_REMAP(efa->mat_nr);
1163                 }
1164         }
1165         else {
1166                 int i;
1167                 for (i = 0; i < me->totpoly; i++) {
1168                         MAT_NR_REMAP(me->mpoly[i].mat_nr);
1169                 }
1170         }
1171
1172 #undef MAT_NR_REMAP
1173
1174 }
1175
1176 void BKE_mesh_smooth_flag_set(Object *meshOb, int enableSmooth)
1177 {
1178         Mesh *me = meshOb->data;
1179         int i;
1180
1181         for (i = 0; i < me->totpoly; i++) {
1182                 MPoly *mp = &me->mpoly[i];
1183
1184                 if (enableSmooth) {
1185                         mp->flag |= ME_SMOOTH;
1186                 }
1187                 else {
1188                         mp->flag &= ~ME_SMOOTH;
1189                 }
1190         }
1191
1192         for (i = 0; i < me->totface; i++) {
1193                 MFace *mf = &me->mface[i];
1194
1195                 if (enableSmooth) {
1196                         mf->flag |= ME_SMOOTH;
1197                 }
1198                 else {
1199                         mf->flag &= ~ME_SMOOTH;
1200                 }
1201         }
1202 }
1203
1204 /**
1205  * Return a newly MEM_malloc'd array of all the mesh vertex locations
1206  * \note \a r_verts_len may be NULL
1207  */
1208 float (*BKE_mesh_vertexCos_get(const Mesh *me, int *r_verts_len))[3]
1209 {
1210         int i, verts_len = me->totvert;
1211         float (*cos)[3] = MEM_malloc_arrayN(verts_len, sizeof(*cos), "vertexcos1");
1212
1213         if (r_verts_len) *r_verts_len = verts_len;
1214         for (i = 0; i < verts_len; i++)
1215                 copy_v3_v3(cos[i], me->mvert[i].co);
1216
1217         return cos;
1218 }
1219
1220 /**
1221  * Find the index of the loop in 'poly' which references vertex,
1222  * returns -1 if not found
1223  */
1224 int poly_find_loop_from_vert(
1225         const MPoly *poly, const MLoop *loopstart,
1226         unsigned vert)
1227 {
1228         int j;
1229         for (j = 0; j < poly->totloop; j++, loopstart++) {
1230                 if (loopstart->v == vert)
1231                         return j;
1232         }
1233
1234         return -1;
1235 }
1236
1237 /**
1238  * Fill \a r_adj with the loop indices in \a poly adjacent to the
1239  * vertex. Returns the index of the loop matching vertex, or -1 if the
1240  * vertex is not in \a poly
1241  */
1242 int poly_get_adj_loops_from_vert(
1243         const MPoly *poly,
1244         const MLoop *mloop, unsigned int vert,
1245         unsigned int r_adj[2])
1246 {
1247         int corner = poly_find_loop_from_vert(
1248                 poly,
1249                 &mloop[poly->loopstart],
1250                 vert);
1251
1252         if (corner != -1) {
1253                 /* vertex was found */
1254                 r_adj[0] = ME_POLY_LOOP_PREV(mloop, poly, corner)->v;
1255                 r_adj[1] = ME_POLY_LOOP_NEXT(mloop, poly, corner)->v;
1256         }
1257
1258         return corner;
1259 }
1260
1261 /**
1262  * Return the index of the edge vert that is not equal to \a v. If
1263  * neither edge vertex is equal to \a v, returns -1.
1264  */
1265 int BKE_mesh_edge_other_vert(const MEdge *e, int v)
1266 {
1267         if (e->v1 == v)
1268                 return e->v2;
1269         else if (e->v2 == v)
1270                 return e->v1;
1271         else
1272                 return -1;
1273 }
1274
1275 /**
1276  * Sets each output array element to the edge index if it is a real edge, or -1.
1277  */
1278 void BKE_mesh_looptri_get_real_edges(const Mesh *mesh, const MLoopTri *looptri, int r_edges[3])
1279 {
1280         for (int i = 2, i_next = 0; i_next < 3; i = i_next++) {
1281                 const MLoop *l1 = &mesh->mloop[looptri->tri[i]], *l2 = &mesh->mloop[looptri->tri[i_next]];
1282                 const MEdge *e = &mesh->medge[l1->e];
1283
1284                 bool is_real = (l1->v == e->v1 && l2->v == e->v2) || (l1->v == e->v2 && l2->v == e->v1);
1285
1286                 r_edges[i] = is_real ? l1->e : -1;
1287         }
1288 }
1289
1290 /* basic vertex data functions */
1291 bool BKE_mesh_minmax(const Mesh *me, float r_min[3], float r_max[3])
1292 {
1293         int i = me->totvert;
1294         MVert *mvert;
1295         for (mvert = me->mvert; i--; mvert++) {
1296                 minmax_v3v3_v3(r_min, r_max, mvert->co);
1297         }
1298
1299         return (me->totvert != 0);
1300 }
1301
1302 void BKE_mesh_transform(Mesh *me, float mat[4][4], bool do_keys)
1303 {
1304         int i;
1305         MVert *mvert = me->mvert;
1306         float (*lnors)[3] = CustomData_get_layer(&me->ldata, CD_NORMAL);
1307
1308         for (i = 0; i < me->totvert; i++, mvert++)
1309                 mul_m4_v3(mat, mvert->co);
1310
1311         if (do_keys && me->key) {
1312                 KeyBlock *kb;
1313                 for (kb = me->key->block.first; kb; kb = kb->next) {
1314                         float *fp = kb->data;
1315                         for (i = kb->totelem; i--; fp += 3) {
1316                                 mul_m4_v3(mat, fp);
1317                         }
1318                 }
1319         }
1320
1321         /* don't update normals, caller can do this explicitly.
1322          * We do update loop normals though, those may not be auto-generated (see e.g. STL import script)! */
1323         if (lnors) {
1324                 float m3[3][3];
1325
1326                 copy_m3_m4(m3, mat);
1327                 normalize_m3(m3);
1328                 for (i = 0; i < me->totloop; i++, lnors++) {
1329                         mul_m3_v3(m3, *lnors);
1330                 }
1331         }
1332 }
1333
1334 void BKE_mesh_translate(Mesh *me, const float offset[3], const bool do_keys)
1335 {
1336         int i = me->totvert;
1337         MVert *mvert;
1338         for (mvert = me->mvert; i--; mvert++) {
1339                 add_v3_v3(mvert->co, offset);
1340         }
1341
1342         if (do_keys && me->key) {
1343                 KeyBlock *kb;
1344                 for (kb = me->key->block.first; kb; kb = kb->next) {
1345                         float *fp = kb->data;
1346                         for (i = kb->totelem; i--; fp += 3) {
1347                                 add_v3_v3(fp, offset);
1348                         }
1349                 }
1350         }
1351 }
1352
1353 void BKE_mesh_ensure_navmesh(Mesh *me)
1354 {
1355         if (!CustomData_has_layer(&me->pdata, CD_RECAST)) {
1356                 int i;
1357                 int polys_len = me->totpoly;
1358                 int *recastData;
1359                 recastData = (int *)MEM_malloc_arrayN(polys_len, sizeof(int), __func__);
1360                 for (i = 0; i < polys_len; i++) {
1361                         recastData[i] = i + 1;
1362                 }
1363                 CustomData_add_layer_named(&me->pdata, CD_RECAST, CD_ASSIGN, recastData, polys_len, "recastData");
1364         }
1365 }
1366
1367 void BKE_mesh_tessface_calc(Mesh *mesh)
1368 {
1369         mesh->totface = BKE_mesh_recalc_tessellation(
1370                 &mesh->fdata, &mesh->ldata, &mesh->pdata,
1371                 mesh->mvert,
1372                 mesh->totface, mesh->totloop, mesh->totpoly,
1373                 /* calc normals right after, don't copy from polys here */
1374                 false);
1375
1376         BKE_mesh_update_customdata_pointers(mesh, true);
1377 }
1378
1379 void BKE_mesh_tessface_ensure(Mesh *mesh)
1380 {
1381         if (mesh->totpoly && mesh->totface == 0) {
1382                 BKE_mesh_tessface_calc(mesh);
1383         }
1384 }
1385
1386 void BKE_mesh_tessface_clear(Mesh *mesh)
1387 {
1388         mesh_tessface_clear_intern(mesh, true);
1389 }
1390
1391 void BKE_mesh_do_versions_cd_flag_init(Mesh *mesh)
1392 {
1393         if (UNLIKELY(mesh->cd_flag)) {
1394                 return;
1395         }
1396         else {
1397                 MVert *mv;
1398                 MEdge *med;
1399                 int i;
1400
1401                 for (mv = mesh->mvert, i = 0; i < mesh->totvert; mv++, i++) {
1402                         if (mv->bweight != 0) {
1403                                 mesh->cd_flag |= ME_CDFLAG_VERT_BWEIGHT;
1404                                 break;
1405                         }
1406                 }
1407
1408                 for (med = mesh->medge, i = 0; i < mesh->totedge; med++, i++) {
1409                         if (med->bweight != 0) {
1410                                 mesh->cd_flag |= ME_CDFLAG_EDGE_BWEIGHT;
1411                                 if (mesh->cd_flag & ME_CDFLAG_EDGE_CREASE) {
1412                                         break;
1413                                 }
1414                         }
1415                         if (med->crease != 0) {
1416                                 mesh->cd_flag |= ME_CDFLAG_EDGE_CREASE;
1417                                 if (mesh->cd_flag & ME_CDFLAG_EDGE_BWEIGHT) {
1418                                         break;
1419                                 }
1420                         }
1421                 }
1422
1423         }
1424 }
1425
1426
1427 /* -------------------------------------------------------------------- */
1428 /* MSelect functions (currently used in weight paint mode) */
1429
1430 void BKE_mesh_mselect_clear(Mesh *me)
1431 {
1432         if (me->mselect) {
1433                 MEM_freeN(me->mselect);
1434                 me->mselect = NULL;
1435         }
1436         me->totselect = 0;
1437 }
1438
1439 void BKE_mesh_mselect_validate(Mesh *me)
1440 {
1441         MSelect *mselect_src, *mselect_dst;
1442         int i_src, i_dst;
1443
1444         if (me->totselect == 0)
1445                 return;
1446
1447         mselect_src = me->mselect;
1448         mselect_dst = MEM_malloc_arrayN((me->totselect), sizeof(MSelect), "Mesh selection history");
1449
1450         for (i_src = 0, i_dst = 0; i_src < me->totselect; i_src++) {
1451                 int index = mselect_src[i_src].index;
1452                 switch (mselect_src[i_src].type) {
1453                         case ME_VSEL:
1454                         {
1455                                 if (me->mvert[index].flag & SELECT) {
1456                                         mselect_dst[i_dst] = mselect_src[i_src];
1457                                         i_dst++;
1458                                 }
1459                                 break;
1460                         }
1461                         case ME_ESEL:
1462                         {
1463                                 if (me->medge[index].flag & SELECT) {
1464                                         mselect_dst[i_dst] = mselect_src[i_src];
1465                                         i_dst++;
1466                                 }
1467                                 break;
1468                         }
1469                         case ME_FSEL:
1470                         {
1471                                 if (me->mpoly[index].flag & SELECT) {
1472                                         mselect_dst[i_dst] = mselect_src[i_src];
1473                                         i_dst++;
1474                                 }
1475                                 break;
1476                         }
1477                         default:
1478                         {
1479                                 BLI_assert(0);
1480                                 break;
1481                         }
1482                 }
1483         }
1484
1485         MEM_freeN(mselect_src);
1486
1487         if (i_dst == 0) {
1488                 MEM_freeN(mselect_dst);
1489                 mselect_dst = NULL;
1490         }
1491         else if (i_dst != me->totselect) {
1492                 mselect_dst = MEM_reallocN(mselect_dst, sizeof(MSelect) * i_dst);
1493         }
1494
1495         me->totselect = i_dst;
1496         me->mselect = mselect_dst;
1497
1498 }
1499
1500 /**
1501  * Return the index within me->mselect, or -1
1502  */
1503 int BKE_mesh_mselect_find(Mesh *me, int index, int type)
1504 {
1505         int i;
1506
1507         BLI_assert(ELEM(type, ME_VSEL, ME_ESEL, ME_FSEL));
1508
1509         for (i = 0; i < me->totselect; i++) {
1510                 if ((me->mselect[i].index == index) &&
1511                     (me->mselect[i].type == type))
1512                 {
1513                         return i;
1514                 }
1515         }
1516
1517         return -1;
1518 }
1519
1520 /**
1521  * Return The index of the active element.
1522  */
1523 int BKE_mesh_mselect_active_get(Mesh *me, int type)
1524 {
1525         BLI_assert(ELEM(type, ME_VSEL, ME_ESEL, ME_FSEL));
1526
1527         if (me->totselect) {
1528                 if (me->mselect[me->totselect - 1].type == type) {
1529                         return me->mselect[me->totselect - 1].index;
1530                 }
1531         }
1532         return -1;
1533 }
1534
1535 void BKE_mesh_mselect_active_set(Mesh *me, int index, int type)
1536 {
1537         const int msel_index = BKE_mesh_mselect_find(me, index, type);
1538
1539         if (msel_index == -1) {
1540                 /* add to the end */
1541                 me->mselect = MEM_reallocN(me->mselect, sizeof(MSelect) * (me->totselect + 1));
1542                 me->mselect[me->totselect].index = index;
1543                 me->mselect[me->totselect].type  = type;
1544                 me->totselect++;
1545         }
1546         else if (msel_index != me->totselect - 1) {
1547                 /* move to the end */
1548                 SWAP(MSelect, me->mselect[msel_index], me->mselect[me->totselect - 1]);
1549         }
1550
1551         BLI_assert((me->mselect[me->totselect - 1].index == index) &&
1552                    (me->mselect[me->totselect - 1].type  == type));
1553 }
1554
1555 void BKE_mesh_count_selected_items(const Mesh *mesh, int r_count[3])
1556 {
1557         r_count[0] = r_count[1] = r_count[2] = 0;
1558         if (mesh->edit_btmesh) {
1559                 BMesh *bm = mesh->edit_btmesh->bm;
1560                 r_count[0] = bm->totvertsel;
1561                 r_count[1] = bm->totedgesel;
1562                 r_count[2] = bm->totfacesel;
1563         }
1564         /* We could support faces in paint modes. */
1565
1566 }
1567
1568 void BKE_mesh_apply_vert_coords(Mesh *mesh, float (*vertCoords)[3])
1569 {
1570         MVert *vert;
1571         int i;
1572
1573         /* this will just return the pointer if it wasn't a referenced layer */
1574         vert = CustomData_duplicate_referenced_layer(&mesh->vdata, CD_MVERT, mesh->totvert);
1575         mesh->mvert = vert;
1576
1577         for (i = 0; i < mesh->totvert; ++i, ++vert)
1578                 copy_v3_v3(vert->co, vertCoords[i]);
1579
1580         mesh->runtime.cd_dirty_vert |= CD_MASK_NORMAL;
1581 }
1582
1583 void BKE_mesh_apply_vert_normals(Mesh *mesh, short (*vertNormals)[3])
1584 {
1585         MVert *vert;
1586         int i;
1587
1588         /* this will just return the pointer if it wasn't a referenced layer */
1589         vert = CustomData_duplicate_referenced_layer(&mesh->vdata, CD_MVERT, mesh->totvert);
1590         mesh->mvert = vert;
1591
1592         for (i = 0; i < mesh->totvert; ++i, ++vert)
1593                 copy_v3_v3_short(vert->no, vertNormals[i]);
1594
1595         mesh->runtime.cd_dirty_vert &= ~CD_MASK_NORMAL;
1596 }
1597
1598 /**
1599  * Compute 'split' (aka loop, or per face corner's) normals.
1600  *
1601  * \param r_lnors_spacearr: Allows to get computed loop normal space array. That data, among other things,
1602  *                         contains 'smooth fan' info, useful e.g. to split geometry along sharp edges...
1603  */
1604 void BKE_mesh_calc_normals_split_ex(Mesh *mesh, MLoopNorSpaceArray *r_lnors_spacearr)
1605 {
1606         float (*r_loopnors)[3];
1607         float (*polynors)[3];
1608         short (*clnors)[2] = NULL;
1609         bool free_polynors = false;
1610
1611         /* Note that we enforce computing clnors when the clnor space array is requested by caller here.
1612          * However, we obviously only use the autosmooth angle threshold only in case autosmooth is enabled. */
1613         const bool use_split_normals = (r_lnors_spacearr != NULL) || ((mesh->flag & ME_AUTOSMOOTH) != 0);
1614         const float split_angle = (mesh->flag & ME_AUTOSMOOTH) != 0 ? mesh->smoothresh : (float)M_PI;
1615
1616         if (CustomData_has_layer(&mesh->ldata, CD_NORMAL)) {
1617                 r_loopnors = CustomData_get_layer(&mesh->ldata, CD_NORMAL);
1618                 memset(r_loopnors, 0, sizeof(float[3]) * mesh->totloop);
1619         }
1620         else {
1621                 r_loopnors = CustomData_add_layer(&mesh->ldata, CD_NORMAL, CD_CALLOC, NULL, mesh->totloop);
1622                 CustomData_set_layer_flag(&mesh->ldata, CD_NORMAL, CD_FLAG_TEMPORARY);
1623         }
1624
1625         /* may be NULL */
1626         clnors = CustomData_get_layer(&mesh->ldata, CD_CUSTOMLOOPNORMAL);
1627
1628         if (CustomData_has_layer(&mesh->pdata, CD_NORMAL)) {
1629                 /* This assume that layer is always up to date, not sure this is the case (esp. in Edit mode?)... */
1630                 polynors = CustomData_get_layer(&mesh->pdata, CD_NORMAL);
1631                 free_polynors = false;
1632         }
1633         else {
1634                 polynors = MEM_malloc_arrayN(mesh->totpoly, sizeof(float[3]), __func__);
1635                 BKE_mesh_calc_normals_poly(
1636                         mesh->mvert, NULL, mesh->totvert,
1637                         mesh->mloop, mesh->mpoly, mesh->totloop, mesh->totpoly, polynors, false);
1638                 free_polynors = true;
1639         }
1640
1641         BKE_mesh_normals_loop_split(
1642                 mesh->mvert, mesh->totvert, mesh->medge, mesh->totedge,
1643                 mesh->mloop, r_loopnors, mesh->totloop, mesh->mpoly, (const float (*)[3])polynors, mesh->totpoly,
1644                 use_split_normals, split_angle, r_lnors_spacearr, clnors, NULL);
1645
1646         if (free_polynors) {
1647                 MEM_freeN(polynors);
1648         }
1649
1650         mesh->runtime.cd_dirty_vert &= ~CD_MASK_NORMAL;
1651 }
1652
1653 void BKE_mesh_calc_normals_split(Mesh *mesh)
1654 {
1655         BKE_mesh_calc_normals_split_ex(mesh, NULL);
1656 }
1657
1658 /* Split faces helper functions. */
1659
1660 typedef struct SplitFaceNewVert {
1661         struct SplitFaceNewVert *next;
1662         int new_index;
1663         int orig_index;
1664         float *vnor;
1665 } SplitFaceNewVert;
1666
1667 typedef struct SplitFaceNewEdge {
1668         struct SplitFaceNewEdge *next;
1669         int new_index;
1670         int orig_index;
1671         int v1;
1672         int v2;
1673 } SplitFaceNewEdge;
1674
1675 /* Detect needed new vertices, and update accordingly loops' vertex indices.
1676  * WARNING! Leaves mesh in invalid state. */
1677 static int split_faces_prepare_new_verts(
1678         const Mesh *mesh, MLoopNorSpaceArray *lnors_spacearr, SplitFaceNewVert **new_verts, MemArena *memarena)
1679 {
1680         /* This is now mandatory, trying to do the job in simple way without that data is doomed to fail, even when only
1681          * dealing with smooth/flat faces one can find cases that no simple algorithm can handle properly. */
1682         BLI_assert(lnors_spacearr != NULL);
1683
1684         const int loops_len = mesh->totloop;
1685         int verts_len = mesh->totvert;
1686         MVert *mvert = mesh->mvert;
1687         MLoop *mloop = mesh->mloop;
1688
1689         BLI_bitmap *verts_used = BLI_BITMAP_NEW(verts_len, __func__);
1690         BLI_bitmap *done_loops = BLI_BITMAP_NEW(loops_len, __func__);
1691
1692         MLoop *ml = mloop;
1693         MLoopNorSpace **lnor_space = lnors_spacearr->lspacearr;
1694
1695         BLI_assert(lnors_spacearr->data_type == MLNOR_SPACEARR_LOOP_INDEX);
1696
1697         for (int loop_idx = 0; loop_idx < loops_len; loop_idx++, ml++, lnor_space++) {
1698                 if (!BLI_BITMAP_TEST(done_loops, loop_idx)) {
1699                         const int vert_idx = ml->v;
1700                         const bool vert_used = BLI_BITMAP_TEST_BOOL(verts_used, vert_idx);
1701                         /* If vert is already used by another smooth fan, we need a new vert for this one. */
1702                         const int new_vert_idx = vert_used ? verts_len++ : vert_idx;
1703
1704                         BLI_assert(*lnor_space);
1705
1706                         if ((*lnor_space)->flags & MLNOR_SPACE_IS_SINGLE) {
1707                                 /* Single loop in this fan... */
1708                                 BLI_assert(POINTER_AS_INT((*lnor_space)->loops) == loop_idx);
1709                                 BLI_BITMAP_ENABLE(done_loops, loop_idx);
1710                                 if (vert_used) {
1711                                         ml->v = new_vert_idx;
1712                                 }
1713                         }
1714                         else {
1715                                 for (LinkNode *lnode = (*lnor_space)->loops; lnode; lnode = lnode->next) {
1716                                         const int ml_fan_idx = POINTER_AS_INT(lnode->link);
1717                                         BLI_BITMAP_ENABLE(done_loops, ml_fan_idx);
1718                                         if (vert_used) {
1719                                                 mloop[ml_fan_idx].v = new_vert_idx;
1720                                         }
1721                                 }
1722                         }
1723
1724                         if (!vert_used) {
1725                                 BLI_BITMAP_ENABLE(verts_used, vert_idx);
1726                                 /* We need to update that vertex's normal here, we won't go over it again. */
1727                                 /* This is important! *DO NOT* set vnor to final computed lnor, vnor should always be defined to
1728                                  * 'automatic normal' value computed from its polys, not some custom normal.
1729                                  * Fortunately, that's the loop normal space's 'lnor' reference vector. ;) */
1730                                 normal_float_to_short_v3(mvert[vert_idx].no, (*lnor_space)->vec_lnor);
1731                         }
1732                         else {
1733                                 /* Add new vert to list. */
1734                                 SplitFaceNewVert *new_vert = BLI_memarena_alloc(memarena, sizeof(*new_vert));
1735                                 new_vert->orig_index = vert_idx;
1736                                 new_vert->new_index = new_vert_idx;
1737                                 new_vert->vnor = (*lnor_space)->vec_lnor;  /* See note above. */
1738                                 new_vert->next = *new_verts;
1739                                 *new_verts = new_vert;
1740                         }
1741                 }
1742         }
1743
1744         MEM_freeN(done_loops);
1745         MEM_freeN(verts_used);
1746
1747         return verts_len - mesh->totvert;
1748 }
1749
1750 /* Detect needed new edges, and update accordingly loops' edge indices.
1751  * WARNING! Leaves mesh in invalid state. */
1752 static int split_faces_prepare_new_edges(
1753         const Mesh *mesh, SplitFaceNewEdge **new_edges, MemArena *memarena)
1754 {
1755         const int num_polys = mesh->totpoly;
1756         int num_edges = mesh->totedge;
1757         MEdge *medge = mesh->medge;
1758         MLoop *mloop = mesh->mloop;
1759         const MPoly *mpoly = mesh->mpoly;
1760
1761         BLI_bitmap *edges_used = BLI_BITMAP_NEW(num_edges, __func__);
1762         EdgeHash *edges_hash = BLI_edgehash_new_ex(__func__, num_edges);
1763
1764         const MPoly *mp = mpoly;
1765         for (int poly_idx = 0; poly_idx < num_polys; poly_idx++, mp++) {
1766                 MLoop *ml_prev = &mloop[mp->loopstart + mp->totloop - 1];
1767                 MLoop *ml = &mloop[mp->loopstart];
1768                 for (int loop_idx = 0; loop_idx < mp->totloop; loop_idx++, ml++) {
1769                         void **eval;
1770                         if (!BLI_edgehash_ensure_p(edges_hash, ml_prev->v, ml->v, &eval)) {
1771                                 const int edge_idx = ml_prev->e;
1772
1773                                 /* That edge has not been encountered yet, define it. */
1774                                 if (BLI_BITMAP_TEST(edges_used, edge_idx)) {
1775                                         /* Original edge has already been used, we need to define a new one. */
1776                                         const int new_edge_idx = num_edges++;
1777                                         *eval = POINTER_FROM_INT(new_edge_idx);
1778                                         ml_prev->e = new_edge_idx;
1779
1780                                         SplitFaceNewEdge *new_edge = BLI_memarena_alloc(memarena, sizeof(*new_edge));
1781                                         new_edge->orig_index = edge_idx;
1782                                         new_edge->new_index = new_edge_idx;
1783                                         new_edge->v1 = ml_prev->v;
1784                                         new_edge->v2 = ml->v;
1785                                         new_edge->next = *new_edges;
1786                                         *new_edges = new_edge;
1787                                 }
1788                                 else {
1789                                         /* We can re-use original edge. */
1790                                         medge[edge_idx].v1 = ml_prev->v;
1791                                         medge[edge_idx].v2 = ml->v;
1792                                         *eval = POINTER_FROM_INT(edge_idx);
1793                                         BLI_BITMAP_ENABLE(edges_used, edge_idx);
1794                                 }
1795                         }
1796                         else {
1797                                 /* Edge already known, just update loop's edge index. */
1798                                 ml_prev->e = POINTER_AS_INT(*eval);
1799                         }
1800
1801                         ml_prev = ml;
1802                 }
1803         }
1804
1805         MEM_freeN(edges_used);
1806         BLI_edgehash_free(edges_hash, NULL);
1807
1808         return num_edges - mesh->totedge;
1809 }
1810
1811 /* Perform actual split of vertices. */
1812 static void split_faces_split_new_verts(
1813         Mesh *mesh, SplitFaceNewVert *new_verts, const int num_new_verts)
1814 {
1815         const int verts_len = mesh->totvert - num_new_verts;
1816         MVert *mvert = mesh->mvert;
1817
1818         /* Remember new_verts is a single linklist, so its items are in reversed order... */
1819         MVert *new_mv = &mvert[mesh->totvert - 1];
1820         for (int i = mesh->totvert - 1; i >= verts_len ; i--, new_mv--, new_verts = new_verts->next) {
1821                 BLI_assert(new_verts->new_index == i);
1822                 BLI_assert(new_verts->new_index != new_verts->orig_index);
1823                 CustomData_copy_data(&mesh->vdata, &mesh->vdata, new_verts->orig_index, i, 1);
1824                 if (new_verts->vnor) {
1825                         normal_float_to_short_v3(new_mv->no, new_verts->vnor);
1826                 }
1827         }
1828 }
1829
1830 /* Perform actual split of edges. */
1831 static void split_faces_split_new_edges(
1832         Mesh *mesh, SplitFaceNewEdge *new_edges, const int num_new_edges)
1833 {
1834         const int num_edges = mesh->totedge - num_new_edges;
1835         MEdge *medge = mesh->medge;
1836
1837         /* Remember new_edges is a single linklist, so its items are in reversed order... */
1838         MEdge *new_med = &medge[mesh->totedge - 1];
1839         for (int i = mesh->totedge - 1; i >= num_edges ; i--, new_med--, new_edges = new_edges->next) {
1840                 BLI_assert(new_edges->new_index == i);
1841                 BLI_assert(new_edges->new_index != new_edges->orig_index);
1842                 CustomData_copy_data(&mesh->edata, &mesh->edata, new_edges->orig_index, i, 1);
1843                 new_med->v1 = new_edges->v1;
1844                 new_med->v2 = new_edges->v2;
1845         }
1846 }
1847
1848 /* Split faces based on the edge angle and loop normals.
1849  * Matches behavior of face splitting in render engines.
1850  *
1851  * NOTE: Will leave CD_NORMAL loop data layer which is
1852  * used by render engines to set shading up.
1853  */
1854 void BKE_mesh_split_faces(Mesh *mesh, bool free_loop_normals)
1855 {
1856         const int num_polys = mesh->totpoly;
1857
1858         if (num_polys == 0) {
1859                 return;
1860         }
1861         BKE_mesh_tessface_clear(mesh);
1862
1863         MLoopNorSpaceArray lnors_spacearr = {NULL};
1864         /* Compute loop normals and loop normal spaces (a.k.a. smooth fans of faces around vertices). */
1865         BKE_mesh_calc_normals_split_ex(mesh, &lnors_spacearr);
1866         /* Stealing memarena from loop normals space array. */
1867         MemArena *memarena = lnors_spacearr.mem;
1868
1869         SplitFaceNewVert *new_verts = NULL;
1870         SplitFaceNewEdge *new_edges = NULL;
1871
1872         /* Detect loop normal spaces (a.k.a. smooth fans) that will need a new vert. */
1873         const int num_new_verts = split_faces_prepare_new_verts(mesh, &lnors_spacearr, &new_verts, memarena);
1874
1875         if (num_new_verts > 0) {
1876                 /* Reminder: beyond this point, there is no way out, mesh is in invalid state (due to early-reassignment of
1877                  * loops' vertex and edge indices to new, to-be-created split ones). */
1878
1879                 const int num_new_edges = split_faces_prepare_new_edges(mesh, &new_edges, memarena);
1880                 /* We can have to split a vertex without having to add a single new edge... */
1881                 const bool do_edges = (num_new_edges > 0);
1882
1883                 /* Reallocate all vert and edge related data. */
1884                 mesh->totvert += num_new_verts;
1885                 CustomData_realloc(&mesh->vdata, mesh->totvert);
1886                 if (do_edges) {
1887                         mesh->totedge += num_new_edges;
1888                         CustomData_realloc(&mesh->edata, mesh->totedge);
1889                 }
1890                 /* Update pointers to a newly allocated memory. */
1891                 BKE_mesh_update_customdata_pointers(mesh, false);
1892
1893                 /* Perform actual split of vertices and edges. */
1894                 split_faces_split_new_verts(mesh, new_verts, num_new_verts);
1895                 if (do_edges) {
1896                         split_faces_split_new_edges(mesh, new_edges, num_new_edges);
1897                 }
1898         }
1899
1900         /* Note: after this point mesh is expected to be valid again. */
1901
1902         /* CD_NORMAL is expected to be temporary only. */
1903         if (free_loop_normals) {
1904                 CustomData_free_layers(&mesh->ldata, CD_NORMAL, mesh->totloop);
1905         }
1906
1907         /* Also frees new_verts/edges temp data, since we used its memarena to allocate them. */
1908         BKE_lnor_spacearr_free(&lnors_spacearr);
1909
1910 #ifdef VALIDATE_MESH
1911         BKE_mesh_validate(mesh, true, true);
1912 #endif
1913 }
1914
1915 /* **** Depsgraph evaluation **** */
1916
1917 void BKE_mesh_eval_geometry(
1918         Depsgraph *depsgraph,
1919         Mesh *mesh)
1920 {
1921         DEG_debug_print_eval(depsgraph, __func__, mesh->id.name, mesh);
1922         if (mesh->bb == NULL || (mesh->bb->flag & BOUNDBOX_DIRTY)) {
1923                 BKE_mesh_texspace_calc(mesh);
1924         }
1925         /* Clear autospace flag in evaluated mesh, so that texspace does not get recomputed when bbox is
1926          * (e.g. after modifiers, etc.) */
1927         mesh->texflag &= ~ME_AUTOSPACE;
1928 }