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