Pass EvaluationContext argument everywhere
[blender.git] / source / blender / blenkernel / intern / mesh.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * Contributor(s): Blender Foundation
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/blenkernel/intern/mesh.c
27  *  \ingroup bke
28  */
29
30 #include "MEM_guardedalloc.h"
31
32 #include "DNA_scene_types.h"
33 #include "DNA_material_types.h"
34 #include "DNA_meta_types.h"
35 #include "DNA_object_types.h"
36 #include "DNA_key_types.h"
37 #include "DNA_mesh_types.h"
38 #include "DNA_curve_types.h"
39
40 #include "BLI_utildefines.h"
41 #include "BLI_math.h"
42 #include "BLI_linklist.h"
43 #include "BLI_listbase.h"
44 #include "BLI_memarena.h"
45 #include "BLI_edgehash.h"
46 #include "BLI_string.h"
47
48 #include "BKE_animsys.h"
49 #include "BKE_main.h"
50 #include "BKE_DerivedMesh.h"
51 #include "BKE_global.h"
52 #include "BKE_mesh.h"
53 #include "BKE_displist.h"
54 #include "BKE_library.h"
55 #include "BKE_library_query.h"
56 #include "BKE_library_remap.h"
57 #include "BKE_material.h"
58 #include "BKE_modifier.h"
59 #include "BKE_multires.h"
60 #include "BKE_key.h"
61 #include "BKE_mball.h"
62 /* these 2 are only used by conversion functions */
63 #include "BKE_curve.h"
64 /* -- */
65 #include "BKE_object.h"
66 #include "BKE_editmesh.h"
67
68 #include "DEG_depsgraph.h"
69
70 /* Define for cases when you want extra validation of mesh
71  * after certain modifications.
72  */
73 // #undef VALIDATE_MESH
74
75 enum {
76         MESHCMP_DVERT_WEIGHTMISMATCH = 1,
77         MESHCMP_DVERT_GROUPMISMATCH,
78         MESHCMP_DVERT_TOTGROUPMISMATCH,
79         MESHCMP_LOOPCOLMISMATCH,
80         MESHCMP_LOOPUVMISMATCH,
81         MESHCMP_LOOPMISMATCH,
82         MESHCMP_POLYVERTMISMATCH,
83         MESHCMP_POLYMISMATCH,
84         MESHCMP_EDGEUNKNOWN,
85         MESHCMP_VERTCOMISMATCH,
86         MESHCMP_CDLAYERS_MISMATCH
87 };
88
89 static const char *cmpcode_to_str(int code)
90 {
91         switch (code) {
92                 case MESHCMP_DVERT_WEIGHTMISMATCH:
93                         return "Vertex Weight Mismatch";
94                 case MESHCMP_DVERT_GROUPMISMATCH:
95                         return "Vertex Group Mismatch";
96                 case MESHCMP_DVERT_TOTGROUPMISMATCH:
97                         return "Vertex Doesn't Belong To Same Number Of Groups";
98                 case MESHCMP_LOOPCOLMISMATCH:
99                         return "Vertex Color Mismatch";
100                 case MESHCMP_LOOPUVMISMATCH:
101                         return "UV Mismatch";
102                 case MESHCMP_LOOPMISMATCH:
103                         return "Loop Mismatch";
104                 case MESHCMP_POLYVERTMISMATCH:
105                         return "Loop Vert Mismatch In Poly Test";
106                 case MESHCMP_POLYMISMATCH:
107                         return "Loop Vert Mismatch";
108                 case MESHCMP_EDGEUNKNOWN:
109                         return "Edge Mismatch";
110                 case MESHCMP_VERTCOMISMATCH:
111                         return "Vertex Coordinate Mismatch";
112                 case MESHCMP_CDLAYERS_MISMATCH:
113                         return "CustomData Layer Count Mismatch";
114                 default:
115                         return "Mesh Comparison Code Unknown";
116         }
117 }
118
119 /* thresh is threshold for comparing vertices, uvs, vertex colors,
120  * weights, etc.*/
121 static int customdata_compare(CustomData *c1, CustomData *c2, Mesh *m1, Mesh *m2, const float thresh)
122 {
123         const float thresh_sq = thresh * thresh;
124         CustomDataLayer *l1, *l2;
125         int i, i1 = 0, i2 = 0, tot, j;
126         
127         for (i = 0; i < c1->totlayer; i++) {
128                 if (ELEM(c1->layers[i].type, CD_MVERT, CD_MEDGE, CD_MPOLY,
129                          CD_MLOOPUV, CD_MLOOPCOL, CD_MDEFORMVERT))
130                 {
131                         i1++;
132                 }
133         }
134
135         for (i = 0; i < c2->totlayer; i++) {
136                 if (ELEM(c2->layers[i].type, CD_MVERT, CD_MEDGE, CD_MPOLY,
137                          CD_MLOOPUV, CD_MLOOPCOL, CD_MDEFORMVERT))
138                 {
139                         i2++;
140                 }
141         }
142
143         if (i1 != i2)
144                 return MESHCMP_CDLAYERS_MISMATCH;
145         
146         l1 = c1->layers; l2 = c2->layers;
147         tot = i1;
148         i1 = 0; i2 = 0;
149         for (i = 0; i < tot; i++) {
150                 while (i1 < c1->totlayer && !ELEM(l1->type, CD_MVERT, CD_MEDGE, CD_MPOLY,
151                                                   CD_MLOOPUV, CD_MLOOPCOL, CD_MDEFORMVERT))
152                 {
153                         i1++;
154                         l1++;
155                 }
156
157                 while (i2 < c2->totlayer && !ELEM(l2->type, CD_MVERT, CD_MEDGE, CD_MPOLY,
158                                                   CD_MLOOPUV, CD_MLOOPCOL, CD_MDEFORMVERT))
159                 {
160                         i2++;
161                         l2++;
162                 }
163                 
164                 if (l1->type == CD_MVERT) {
165                         MVert *v1 = l1->data;
166                         MVert *v2 = l2->data;
167                         int vtot = m1->totvert;
168                         
169                         for (j = 0; j < vtot; j++, v1++, v2++) {
170                                 if (len_squared_v3v3(v1->co, v2->co) > thresh_sq)
171                                         return MESHCMP_VERTCOMISMATCH;
172                                 /* I don't care about normals, let's just do coodinates */
173                         }
174                 }
175                 
176                 /*we're order-agnostic for edges here*/
177                 if (l1->type == CD_MEDGE) {
178                         MEdge *e1 = l1->data;
179                         MEdge *e2 = l2->data;
180                         int etot = m1->totedge;
181                         EdgeHash *eh = BLI_edgehash_new_ex(__func__, etot);
182                 
183                         for (j = 0; j < etot; j++, e1++) {
184                                 BLI_edgehash_insert(eh, e1->v1, e1->v2, e1);
185                         }
186                         
187                         for (j = 0; j < etot; j++, e2++) {
188                                 if (!BLI_edgehash_lookup(eh, e2->v1, e2->v2))
189                                         return MESHCMP_EDGEUNKNOWN;
190                         }
191                         BLI_edgehash_free(eh, NULL);
192                 }
193                 
194                 if (l1->type == CD_MPOLY) {
195                         MPoly *p1 = l1->data;
196                         MPoly *p2 = l2->data;
197                         int ptot = m1->totpoly;
198                 
199                         for (j = 0; j < ptot; j++, p1++, p2++) {
200                                 MLoop *lp1, *lp2;
201                                 int k;
202                                 
203                                 if (p1->totloop != p2->totloop)
204                                         return MESHCMP_POLYMISMATCH;
205                                 
206                                 lp1 = m1->mloop + p1->loopstart;
207                                 lp2 = m2->mloop + p2->loopstart;
208                                 
209                                 for (k = 0; k < p1->totloop; k++, lp1++, lp2++) {
210                                         if (lp1->v != lp2->v)
211                                                 return MESHCMP_POLYVERTMISMATCH;
212                                 }
213                         }
214                 }
215                 if (l1->type == CD_MLOOP) {
216                         MLoop *lp1 = l1->data;
217                         MLoop *lp2 = l2->data;
218                         int ltot = m1->totloop;
219                 
220                         for (j = 0; j < ltot; j++, lp1++, lp2++) {
221                                 if (lp1->v != lp2->v)
222                                         return MESHCMP_LOOPMISMATCH;
223                         }
224                 }
225                 if (l1->type == CD_MLOOPUV) {
226                         MLoopUV *lp1 = l1->data;
227                         MLoopUV *lp2 = l2->data;
228                         int ltot = m1->totloop;
229                 
230                         for (j = 0; j < ltot; j++, lp1++, lp2++) {
231                                 if (len_squared_v2v2(lp1->uv, lp2->uv) > thresh_sq)
232                                         return MESHCMP_LOOPUVMISMATCH;
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 || 
243                                     ABS(lp1->g - lp2->g) > thresh || 
244                                     ABS(lp1->b - lp2->b) > thresh || 
245                                     ABS(lp1->a - lp2->a) > thresh)
246                                 {
247                                         return MESHCMP_LOOPCOLMISMATCH;
248                                 }
249                         }
250                 }
251
252                 if (l1->type == CD_MDEFORMVERT) {
253                         MDeformVert *dv1 = l1->data;
254                         MDeformVert *dv2 = l2->data;
255                         int dvtot = m1->totvert;
256                 
257                         for (j = 0; j < dvtot; j++, dv1++, dv2++) {
258                                 int k;
259                                 MDeformWeight *dw1 = dv1->dw, *dw2 = dv2->dw;
260                                 
261                                 if (dv1->totweight != dv2->totweight)
262                                         return MESHCMP_DVERT_TOTGROUPMISMATCH;
263                                 
264                                 for (k = 0; k < dv1->totweight; k++, dw1++, dw2++) {
265                                         if (dw1->def_nr != dw2->def_nr)
266                                                 return MESHCMP_DVERT_GROUPMISMATCH;
267                                         if (fabsf(dw1->weight - dw2->weight) > thresh)
268                                                 return MESHCMP_DVERT_WEIGHTMISMATCH;
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         if (me1->totvert != me2->totvert) 
291                 return "Number of verts don't match";
292         
293         if (me1->totedge != me2->totedge)
294                 return "Number of edges don't match";
295         
296         if (me1->totpoly != me2->totpoly)
297                 return "Number of faces don't match";
298                                 
299         if (me1->totloop != me2->totloop)
300                 return "Number of loops don't match";
301         
302         if ((c = customdata_compare(&me1->vdata, &me2->vdata, me1, me2, thresh)))
303                 return cmpcode_to_str(c);
304
305         if ((c = customdata_compare(&me1->edata, &me2->edata, me1, me2, thresh)))
306                 return cmpcode_to_str(c);
307
308         if ((c = customdata_compare(&me1->ldata, &me2->ldata, me1, me2, thresh)))
309                 return cmpcode_to_str(c);
310
311         if ((c = customdata_compare(&me1->pdata, &me2->pdata, me1, me2, thresh)))
312                 return cmpcode_to_str(c);
313         
314         return NULL;
315 }
316
317 static void mesh_ensure_tessellation_customdata(Mesh *me)
318 {
319         if (UNLIKELY((me->totface != 0) && (me->totpoly == 0))) {
320                 /* Pass, otherwise this function  clears 'mface' before
321                  * versioning 'mface -> mpoly' code kicks in [#30583]
322                  *
323                  * Callers could also check but safer to do here - campbell */
324         }
325         else {
326                 const int tottex_original = CustomData_number_of_layers(&me->ldata, CD_MLOOPUV);
327                 const int totcol_original = CustomData_number_of_layers(&me->ldata, CD_MLOOPCOL);
328
329                 const int tottex_tessface = CustomData_number_of_layers(&me->fdata, CD_MTFACE);
330                 const int totcol_tessface = CustomData_number_of_layers(&me->fdata, CD_MCOL);
331
332                 if (tottex_tessface != tottex_original ||
333                     totcol_tessface != totcol_original)
334                 {
335                         BKE_mesh_tessface_clear(me);
336
337                         CustomData_from_bmeshpoly(&me->fdata, &me->ldata, me->totface);
338
339                         /* TODO - add some --debug-mesh option */
340                         if (G.debug & G_DEBUG) {
341                                 /* note: this warning may be un-called for if we are initializing the mesh for the
342                                  * first time from bmesh, rather then giving a warning about this we could be smarter
343                                  * and check if there was any data to begin with, for now just print the warning with
344                                  * some info to help troubleshoot whats going on - campbell */
345                                 printf("%s: warning! Tessellation uvs or vcol data got out of sync, "
346                                        "had to reset!\n    CD_MTFACE: %d != CD_MLOOPUV: %d || CD_MCOL: %d != CD_MLOOPCOL: %d\n",
347                                        __func__, tottex_tessface, tottex_original, totcol_tessface, totcol_original);
348                         }
349                 }
350         }
351 }
352
353 void BKE_mesh_ensure_skin_customdata(Mesh *me)
354 {
355         BMesh *bm = me->edit_btmesh ? me->edit_btmesh->bm : NULL;
356         MVertSkin *vs;
357
358         if (bm) {
359                 if (!CustomData_has_layer(&bm->vdata, CD_MVERT_SKIN)) {
360                         BMVert *v;
361                         BMIter iter;
362
363                         BM_data_layer_add(bm, &bm->vdata, CD_MVERT_SKIN);
364
365                         /* Mark an arbitrary vertex as root */
366                         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
367                                 vs = CustomData_bmesh_get(&bm->vdata, v->head.data,
368                                                           CD_MVERT_SKIN);
369                                 vs->flag |= MVERT_SKIN_ROOT;
370                                 break;
371                         }
372                 }
373         }
374         else {
375                 if (!CustomData_has_layer(&me->vdata, CD_MVERT_SKIN)) {
376                         vs = CustomData_add_layer(&me->vdata,
377                                                   CD_MVERT_SKIN,
378                                                   CD_DEFAULT,
379                                                   NULL,
380                                                   me->totvert);
381
382                         /* Mark an arbitrary vertex as root */
383                         if (vs) {
384                                 vs->flag |= MVERT_SKIN_ROOT;
385                         }
386                 }
387         }
388 }
389
390 bool BKE_mesh_ensure_facemap_customdata(struct Mesh *me)
391 {
392         BMesh *bm = me->edit_btmesh ? me->edit_btmesh->bm : NULL;
393         bool changed = false;
394         if (bm) {
395                 if (!CustomData_has_layer(&bm->pdata, CD_FACEMAP)) {
396                         BM_data_layer_add(bm, &bm->pdata, CD_FACEMAP);
397                         changed = true;
398                 }
399         }
400         else {
401                 if (!CustomData_has_layer(&me->pdata, CD_FACEMAP)) {
402                         CustomData_add_layer(&me->pdata,
403                                                   CD_FACEMAP,
404                                                   CD_DEFAULT,
405                                                   NULL,
406                                                   me->totpoly);
407                         changed = true;
408                 }
409         }
410         return changed;
411 }
412
413 bool BKE_mesh_clear_facemap_customdata(struct Mesh *me)
414 {
415         BMesh *bm = me->edit_btmesh ? me->edit_btmesh->bm : NULL;
416         bool changed = false;
417         if (bm) {
418                 if (CustomData_has_layer(&bm->pdata, CD_FACEMAP)) {
419                         BM_data_layer_free(bm, &bm->pdata, CD_FACEMAP);
420                         changed = true;
421                 }
422         }
423         else {
424                 if (CustomData_has_layer(&me->pdata, CD_FACEMAP)) {
425                         CustomData_free_layers(&me->pdata, CD_FACEMAP, me->totpoly);
426                         changed = true;
427                 }
428         }
429         return changed;
430 }
431
432 /* this ensures grouped customdata (e.g. mtexpoly and mloopuv and mtface, or
433  * mloopcol and mcol) have the same relative active/render/clone/mask indices.
434  *
435  * note that for undo mesh data we want to skip 'ensure_tess_cd' call since
436  * we don't want to store memory for tessface when its only used for older
437  * versions of the mesh. - campbell*/
438 static void mesh_update_linked_customdata(Mesh *me, const bool do_ensure_tess_cd)
439 {
440         if (do_ensure_tess_cd) {
441                 mesh_ensure_tessellation_customdata(me);
442         }
443
444         CustomData_bmesh_update_active_layers(&me->fdata, &me->ldata);
445 }
446
447 void BKE_mesh_update_customdata_pointers(Mesh *me, const bool do_ensure_tess_cd)
448 {
449         mesh_update_linked_customdata(me, do_ensure_tess_cd);
450
451         me->mvert = CustomData_get_layer(&me->vdata, CD_MVERT);
452         me->dvert = CustomData_get_layer(&me->vdata, CD_MDEFORMVERT);
453
454         me->medge = CustomData_get_layer(&me->edata, CD_MEDGE);
455
456         me->mface = CustomData_get_layer(&me->fdata, CD_MFACE);
457         me->mcol = CustomData_get_layer(&me->fdata, CD_MCOL);
458         me->mtface = CustomData_get_layer(&me->fdata, CD_MTFACE);
459         
460         me->mpoly = CustomData_get_layer(&me->pdata, CD_MPOLY);
461         me->mloop = CustomData_get_layer(&me->ldata, CD_MLOOP);
462
463         me->mloopcol = CustomData_get_layer(&me->ldata, CD_MLOOPCOL);
464         me->mloopuv = CustomData_get_layer(&me->ldata, CD_MLOOPUV);
465 }
466
467 bool BKE_mesh_has_custom_loop_normals(Mesh *me)
468 {
469         if (me->edit_btmesh) {
470                 return CustomData_has_layer(&me->edit_btmesh->bm->ldata, CD_CUSTOMLOOPNORMAL);
471         }
472         else {
473                 return CustomData_has_layer(&me->ldata, CD_CUSTOMLOOPNORMAL);
474         }
475 }
476
477 /** Free (or release) any data used by this mesh (does not free the mesh itself). */
478 void BKE_mesh_free(Mesh *me)
479 {
480         BKE_animdata_free(&me->id, false);
481
482         BKE_mesh_batch_cache_free(me);
483
484         CustomData_free(&me->vdata, me->totvert);
485         CustomData_free(&me->edata, me->totedge);
486         CustomData_free(&me->fdata, me->totface);
487         CustomData_free(&me->ldata, me->totloop);
488         CustomData_free(&me->pdata, me->totpoly);
489
490         MEM_SAFE_FREE(me->mat);
491         MEM_SAFE_FREE(me->bb);
492         MEM_SAFE_FREE(me->mselect);
493         MEM_SAFE_FREE(me->edit_btmesh);
494 }
495
496 static void mesh_tessface_clear_intern(Mesh *mesh, int free_customdata)
497 {
498         if (free_customdata) {
499                 CustomData_free(&mesh->fdata, mesh->totface);
500         }
501         else {
502                 CustomData_reset(&mesh->fdata);
503         }
504
505         mesh->mface = NULL;
506         mesh->mtface = NULL;
507         mesh->mcol = NULL;
508         mesh->totface = 0;
509 }
510
511 void BKE_mesh_init(Mesh *me)
512 {
513         BLI_assert(MEMCMP_STRUCT_OFS_IS_ZERO(me, id));
514
515         me->size[0] = me->size[1] = me->size[2] = 1.0;
516         me->smoothresh = DEG2RADF(30);
517         me->texflag = ME_AUTOSPACE;
518
519         /* disable because its slow on many GPU's, see [#37518] */
520 #if 0
521         me->flag = ME_TWOSIDED;
522 #endif
523         me->drawflag = ME_DRAWEDGES | ME_DRAWFACES | ME_DRAWCREASES;
524
525         CustomData_reset(&me->vdata);
526         CustomData_reset(&me->edata);
527         CustomData_reset(&me->fdata);
528         CustomData_reset(&me->pdata);
529         CustomData_reset(&me->ldata);
530 }
531
532 Mesh *BKE_mesh_add(Main *bmain, const char *name)
533 {
534         Mesh *me;
535
536         me = BKE_libblock_alloc(bmain, ID_ME, name);
537
538         BKE_mesh_init(me);
539
540         return me;
541 }
542
543 Mesh *BKE_mesh_copy(Main *bmain, const Mesh *me)
544 {
545         Mesh *men;
546         int a;
547         const int do_tessface = ((me->totface != 0) && (me->totpoly == 0)); /* only do tessface if we have no polys */
548         
549         men = BKE_libblock_copy(bmain, &me->id);
550         
551         men->mat = MEM_dupallocN(me->mat);
552         for (a = 0; a < men->totcol; a++) {
553                 id_us_plus((ID *)men->mat[a]);
554         }
555         id_us_plus((ID *)men->texcomesh);
556
557         CustomData_copy(&me->vdata, &men->vdata, CD_MASK_MESH, CD_DUPLICATE, men->totvert);
558         CustomData_copy(&me->edata, &men->edata, CD_MASK_MESH, CD_DUPLICATE, men->totedge);
559         CustomData_copy(&me->ldata, &men->ldata, CD_MASK_MESH, CD_DUPLICATE, men->totloop);
560         CustomData_copy(&me->pdata, &men->pdata, CD_MASK_MESH, CD_DUPLICATE, men->totpoly);
561         if (do_tessface) {
562                 CustomData_copy(&me->fdata, &men->fdata, CD_MASK_MESH, CD_DUPLICATE, men->totface);
563         }
564         else {
565                 mesh_tessface_clear_intern(men, false);
566         }
567
568         BKE_mesh_update_customdata_pointers(men, do_tessface);
569
570         men->edit_btmesh = NULL;
571         men->batch_cache = NULL;
572
573         men->mselect = MEM_dupallocN(men->mselect);
574         men->bb = MEM_dupallocN(men->bb);
575
576         if (me->key) {
577                 men->key = BKE_key_copy(bmain, me->key);
578                 men->key->from = (ID *)men;
579         }
580
581         BKE_id_copy_ensure_local(bmain, &me->id, &men->id);
582
583         return men;
584 }
585
586 BMesh *BKE_mesh_to_bmesh(
587         Mesh *me, Object *ob,
588         const bool add_key_index, const struct BMeshCreateParams *params)
589 {
590         BMesh *bm;
591         const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_ME(me);
592
593         bm = BM_mesh_create(&allocsize, params);
594
595         BM_mesh_bm_from_me(
596                 bm, me, (&(struct BMeshFromMeshParams){
597                     .add_key_index = add_key_index, .use_shapekey = true, .active_shapekey = ob->shapenr,
598                 }));
599
600         return bm;
601 }
602
603 void BKE_mesh_make_local(Main *bmain, Mesh *me, const bool lib_local)
604 {
605         BKE_id_make_local_generic(bmain, &me->id, true, lib_local);
606 }
607
608 bool BKE_mesh_uv_cdlayer_rename_index(Mesh *me, const int poly_index, const int loop_index, const int face_index,
609                                       const char *new_name, const bool do_tessface)
610 {
611         CustomData *pdata, *ldata, *fdata;
612         CustomDataLayer *cdlp, *cdlu, *cdlf;
613         const int step = do_tessface ? 3 : 2;
614         int i;
615
616         if (me->edit_btmesh) {
617                 pdata = &me->edit_btmesh->bm->pdata;
618                 ldata = &me->edit_btmesh->bm->ldata;
619                 fdata = NULL;  /* No tessellated data in BMesh! */
620         }
621         else {
622                 pdata = &me->pdata;
623                 ldata = &me->ldata;
624                 fdata = &me->fdata;
625         }
626
627         cdlu = &ldata->layers[loop_index];
628         cdlp = (poly_index != -1) ? &pdata->layers[poly_index] : NULL;
629         cdlf = (face_index != -1) && fdata && do_tessface ? &fdata->layers[face_index] : NULL;
630
631         if (cdlu->name != new_name) {
632                 /* Mesh validate passes a name from the CD layer as the new name,
633                  * Avoid memcpy from self to self in this case.
634                  */
635                 BLI_strncpy(cdlu->name, new_name, sizeof(cdlu->name));
636                 CustomData_set_layer_unique_name(ldata, loop_index);
637         }
638
639         if (cdlp == NULL && cdlf == NULL) {
640                 return false;
641         }
642
643         /* Loop until we do have exactly the same name for all layers! */
644         for (i = 1;
645              (cdlp && !STREQ(cdlu->name, cdlp->name)) ||
646              (cdlf && !STREQ(cdlu->name, cdlf->name));
647              i++)
648         {
649                 switch (i % step) {
650                         case 0:
651                                 if (cdlp) {
652                                         BLI_strncpy(cdlp->name, cdlu->name, sizeof(cdlp->name));
653                                         CustomData_set_layer_unique_name(pdata, poly_index);
654                                 }
655                                 break;
656                         case 1:
657                                 BLI_strncpy(cdlu->name, cdlp->name, sizeof(cdlu->name));
658                                 CustomData_set_layer_unique_name(ldata, loop_index);
659                                 break;
660                         case 2:
661                                 if (cdlf) {
662                                         BLI_strncpy(cdlf->name, cdlu->name, sizeof(cdlf->name));
663                                         CustomData_set_layer_unique_name(fdata, face_index);
664                                 }
665                                 break;
666                 }
667         }
668
669         return true;
670 }
671
672 bool BKE_mesh_uv_cdlayer_rename(Mesh *me, const char *old_name, const char *new_name, bool do_tessface)
673 {
674         CustomData *ldata, *fdata;
675         if (me->edit_btmesh) {
676                 ldata = &me->edit_btmesh->bm->ldata;
677                 /* No tessellated data in BMesh! */
678                 fdata = NULL;
679                 do_tessface = false;
680         }
681         else {
682                 ldata = &me->ldata;
683                 fdata = &me->fdata;
684                 do_tessface = (do_tessface && fdata->totlayer);
685         }
686
687         {
688                 const int lidx_start = CustomData_get_layer_index(ldata, CD_MLOOPUV);
689                 const int fidx_start = do_tessface ? CustomData_get_layer_index(fdata, CD_MTFACE) : -1;
690                 int lidx = CustomData_get_named_layer(ldata, CD_MLOOPUV, old_name);
691                 int fidx = do_tessface ? CustomData_get_named_layer(fdata, CD_MTFACE, old_name) : -1;
692
693                 /* None of those cases should happen, in theory!
694                  * Note this assume we have the same number of mtexpoly, mloopuv and mtface layers!
695                  */
696                 if (lidx == -1) {
697                         if (fidx == -1) {
698                                 /* No layer found with this name! */
699                                 return false;
700                         }
701                         else {
702                                 lidx = fidx;
703                         }
704                 }
705
706                 /* Go back to absolute indices! */
707                 lidx += lidx_start;
708                 if (fidx != -1)
709                         fidx += fidx_start;
710
711                 return BKE_mesh_uv_cdlayer_rename_index(me, -1, lidx, fidx, new_name, do_tessface);
712         }
713 }
714
715 void BKE_mesh_boundbox_calc(Mesh *me, float r_loc[3], float r_size[3])
716 {
717         BoundBox *bb;
718         float min[3], max[3];
719         float mloc[3], msize[3];
720         
721         if (me->bb == NULL) me->bb = MEM_callocN(sizeof(BoundBox), "boundbox");
722         bb = me->bb;
723
724         if (!r_loc) r_loc = mloc;
725         if (!r_size) r_size = msize;
726         
727         INIT_MINMAX(min, max);
728         if (!BKE_mesh_minmax(me, min, max)) {
729                 min[0] = min[1] = min[2] = -1.0f;
730                 max[0] = max[1] = max[2] = 1.0f;
731         }
732
733         mid_v3_v3v3(r_loc, min, max);
734                 
735         r_size[0] = (max[0] - min[0]) / 2.0f;
736         r_size[1] = (max[1] - min[1]) / 2.0f;
737         r_size[2] = (max[2] - min[2]) / 2.0f;
738         
739         BKE_boundbox_init_from_minmax(bb, min, max);
740
741         bb->flag &= ~BOUNDBOX_DIRTY;
742 }
743
744 void BKE_mesh_texspace_calc(Mesh *me)
745 {
746         float loc[3], size[3];
747         int a;
748
749         BKE_mesh_boundbox_calc(me, loc, size);
750
751         if (me->texflag & ME_AUTOSPACE) {
752                 for (a = 0; a < 3; a++) {
753                         if (size[a] == 0.0f) size[a] = 1.0f;
754                         else if (size[a] > 0.0f && size[a] < 0.00001f) size[a] = 0.00001f;
755                         else if (size[a] < 0.0f && size[a] > -0.00001f) size[a] = -0.00001f;
756                 }
757
758                 copy_v3_v3(me->loc, loc);
759                 copy_v3_v3(me->size, size);
760                 zero_v3(me->rot);
761         }
762 }
763
764 BoundBox *BKE_mesh_boundbox_get(Object *ob)
765 {
766         Mesh *me = ob->data;
767
768         if (ob->bb)
769                 return ob->bb;
770
771         if (me->bb == NULL || (me->bb->flag & BOUNDBOX_DIRTY)) {
772                 BKE_mesh_texspace_calc(me);
773         }
774
775         return me->bb;
776 }
777
778 void BKE_mesh_texspace_get(Mesh *me, float r_loc[3], float r_rot[3], float r_size[3])
779 {
780         if (me->bb == NULL || (me->bb->flag & BOUNDBOX_DIRTY)) {
781                 BKE_mesh_texspace_calc(me);
782         }
783
784         if (r_loc) copy_v3_v3(r_loc,  me->loc);
785         if (r_rot) copy_v3_v3(r_rot,  me->rot);
786         if (r_size) copy_v3_v3(r_size, me->size);
787 }
788
789 void BKE_mesh_texspace_get_reference(Mesh *me, short **r_texflag,  float **r_loc, float **r_rot, float **r_size)
790 {
791         if (me->bb == NULL || (me->bb->flag & BOUNDBOX_DIRTY)) {
792                 BKE_mesh_texspace_calc(me);
793         }
794
795         if (r_texflag != NULL) *r_texflag = &me->texflag;
796         if (r_loc != NULL) *r_loc = me->loc;
797         if (r_rot != NULL) *r_rot = me->rot;
798         if (r_size != NULL) *r_size = me->size;
799 }
800
801 void BKE_mesh_texspace_copy_from_object(Mesh *me, Object *ob)
802 {
803         float *texloc, *texrot, *texsize;
804         short *texflag;
805
806         if (BKE_object_obdata_texspace_get(ob, &texflag, &texloc, &texsize, &texrot)) {
807                 me->texflag = *texflag;
808                 copy_v3_v3(me->loc, texloc);
809                 copy_v3_v3(me->size, texsize);
810                 copy_v3_v3(me->rot, texrot);
811         }
812 }
813
814 float (*BKE_mesh_orco_verts_get(Object *ob))[3]
815 {
816         Mesh *me = ob->data;
817         MVert *mvert = NULL;
818         Mesh *tme = me->texcomesh ? me->texcomesh : me;
819         int a, totvert;
820         float (*vcos)[3] = NULL;
821
822         /* Get appropriate vertex coordinates */
823         vcos = MEM_callocN(sizeof(*vcos) * me->totvert, "orco mesh");
824         mvert = tme->mvert;
825         totvert = min_ii(tme->totvert, me->totvert);
826
827         for (a = 0; a < totvert; a++, mvert++) {
828                 copy_v3_v3(vcos[a], mvert->co);
829         }
830
831         return vcos;
832 }
833
834 void BKE_mesh_orco_verts_transform(Mesh *me, float (*orco)[3], int totvert, int invert)
835 {
836         float loc[3], size[3];
837         int a;
838
839         BKE_mesh_texspace_get(me->texcomesh ? me->texcomesh : me, loc, NULL, size);
840
841         if (invert) {
842                 for (a = 0; a < totvert; a++) {
843                         float *co = orco[a];
844                         madd_v3_v3v3v3(co, loc, co, size);
845                 }
846         }
847         else {
848                 for (a = 0; a < totvert; a++) {
849                         float *co = orco[a];
850                         co[0] = (co[0] - loc[0]) / size[0];
851                         co[1] = (co[1] - loc[1]) / size[1];
852                         co[2] = (co[2] - loc[2]) / size[2];
853                 }
854         }
855 }
856
857 /* rotates the vertices of a face in case v[2] or v[3] (vertex index) is = 0.
858  * this is necessary to make the if (mface->v4) check for quads work */
859 int test_index_face(MFace *mface, CustomData *fdata, int mfindex, int nr)
860 {
861         /* first test if the face is legal */
862         if ((mface->v3 || nr == 4) && mface->v3 == mface->v4) {
863                 mface->v4 = 0;
864                 nr--;
865         }
866         if ((mface->v2 || mface->v4) && mface->v2 == mface->v3) {
867                 mface->v3 = mface->v4;
868                 mface->v4 = 0;
869                 nr--;
870         }
871         if (mface->v1 == mface->v2) {
872                 mface->v2 = mface->v3;
873                 mface->v3 = mface->v4;
874                 mface->v4 = 0;
875                 nr--;
876         }
877
878         /* check corrupt cases, bow-tie geometry, cant handle these because edge data wont exist so just return 0 */
879         if (nr == 3) {
880                 if (
881                     /* real edges */
882                     mface->v1 == mface->v2 ||
883                     mface->v2 == mface->v3 ||
884                     mface->v3 == mface->v1)
885                 {
886                         return 0;
887                 }
888         }
889         else if (nr == 4) {
890                 if (
891                     /* real edges */
892                     mface->v1 == mface->v2 ||
893                     mface->v2 == mface->v3 ||
894                     mface->v3 == mface->v4 ||
895                     mface->v4 == mface->v1 ||
896                     /* across the face */
897                     mface->v1 == mface->v3 ||
898                     mface->v2 == mface->v4)
899                 {
900                         return 0;
901                 }
902         }
903
904         /* prevent a zero at wrong index location */
905         if (nr == 3) {
906                 if (mface->v3 == 0) {
907                         static int corner_indices[4] = {1, 2, 0, 3};
908
909                         SWAP(unsigned int, mface->v1, mface->v2);
910                         SWAP(unsigned int, mface->v2, mface->v3);
911
912                         if (fdata)
913                                 CustomData_swap_corners(fdata, mfindex, corner_indices);
914                 }
915         }
916         else if (nr == 4) {
917                 if (mface->v3 == 0 || mface->v4 == 0) {
918                         static int corner_indices[4] = {2, 3, 0, 1};
919
920                         SWAP(unsigned int, mface->v1, mface->v3);
921                         SWAP(unsigned int, mface->v2, mface->v4);
922
923                         if (fdata)
924                                 CustomData_swap_corners(fdata, mfindex, corner_indices);
925                 }
926         }
927
928         return nr;
929 }
930
931 Mesh *BKE_mesh_from_object(Object *ob)
932 {
933         
934         if (ob == NULL) return NULL;
935         if (ob->type == OB_MESH) return ob->data;
936         else return NULL;
937 }
938
939 void BKE_mesh_assign_object(Object *ob, Mesh *me)
940 {
941         Mesh *old = NULL;
942
943         multires_force_update(ob);
944         
945         if (ob == NULL) return;
946         
947         if (ob->type == OB_MESH) {
948                 old = ob->data;
949                 if (old)
950                         id_us_min(&old->id);
951                 ob->data = me;
952                 id_us_plus((ID *)me);
953         }
954         
955         test_object_materials(ob, (ID *)me);
956
957         test_object_modifiers(ob);
958 }
959
960 void BKE_mesh_from_metaball(ListBase *lb, Mesh *me)
961 {
962         DispList *dl;
963         MVert *mvert;
964         MLoop *mloop, *allloop;
965         MPoly *mpoly;
966         const float *nors, *verts;
967         int a, *index;
968         
969         dl = lb->first;
970         if (dl == NULL) return;
971
972         if (dl->type == DL_INDEX4) {
973                 mvert = CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, dl->nr);
974                 allloop = mloop = CustomData_add_layer(&me->ldata, CD_MLOOP, CD_CALLOC, NULL, dl->parts * 4);
975                 mpoly = CustomData_add_layer(&me->pdata, CD_MPOLY, CD_CALLOC, NULL, dl->parts);
976                 me->mvert = mvert;
977                 me->mloop = mloop;
978                 me->mpoly = mpoly;
979                 me->totvert = dl->nr;
980                 me->totpoly = dl->parts;
981
982                 a = dl->nr;
983                 nors = dl->nors;
984                 verts = dl->verts;
985                 while (a--) {
986                         copy_v3_v3(mvert->co, verts);
987                         normal_float_to_short_v3(mvert->no, nors);
988                         mvert++;
989                         nors += 3;
990                         verts += 3;
991                 }
992                 
993                 a = dl->parts;
994                 index = dl->index;
995                 while (a--) {
996                         int count = index[2] != index[3] ? 4 : 3;
997
998                         mloop[0].v = index[0];
999                         mloop[1].v = index[1];
1000                         mloop[2].v = index[2];
1001                         if (count == 4)
1002                                 mloop[3].v = index[3];
1003
1004                         mpoly->totloop = count;
1005                         mpoly->loopstart = (int)(mloop - allloop);
1006                         mpoly->flag = ME_SMOOTH;
1007
1008
1009                         mpoly++;
1010                         mloop += count;
1011                         me->totloop += count;
1012                         index += 4;
1013                 }
1014
1015                 BKE_mesh_update_customdata_pointers(me, true);
1016
1017                 BKE_mesh_calc_normals(me);
1018
1019                 BKE_mesh_calc_edges(me, true, false);
1020         }
1021 }
1022
1023 /**
1024  * Specialized function to use when we _know_ existing edges don't overlap with poly edges.
1025  */
1026 static void make_edges_mdata_extend(MEdge **r_alledge, int *r_totedge,
1027                                     const MPoly *mpoly, MLoop *mloop,
1028                                     const int totpoly)
1029 {
1030         int totedge = *r_totedge;
1031         int totedge_new;
1032         EdgeHash *eh;
1033         unsigned int eh_reserve;
1034         const MPoly *mp;
1035         int i;
1036
1037         eh_reserve = max_ii(totedge, BLI_EDGEHASH_SIZE_GUESS_FROM_POLYS(totpoly));
1038         eh = BLI_edgehash_new_ex(__func__, eh_reserve);
1039
1040         for (i = 0, mp = mpoly; i < totpoly; i++, mp++) {
1041                 BKE_mesh_poly_edgehash_insert(eh, mp, mloop + mp->loopstart);
1042         }
1043
1044         totedge_new = BLI_edgehash_size(eh);
1045
1046 #ifdef DEBUG
1047         /* ensure that theres no overlap! */
1048         if (totedge_new) {
1049                 MEdge *medge = *r_alledge;
1050                 for (i = 0; i < totedge; i++, medge++) {
1051                         BLI_assert(BLI_edgehash_haskey(eh, medge->v1, medge->v2) == false);
1052                 }
1053         }
1054 #endif
1055
1056         if (totedge_new) {
1057                 EdgeHashIterator *ehi;
1058                 MEdge *medge;
1059                 unsigned int e_index = totedge;
1060
1061                 *r_alledge = medge = (*r_alledge ? MEM_reallocN(*r_alledge, sizeof(MEdge) * (totedge + totedge_new)) :
1062                                                    MEM_callocN(sizeof(MEdge) * totedge_new, __func__));
1063                 medge += totedge;
1064
1065                 totedge += totedge_new;
1066
1067                 /* --- */
1068                 for (ehi = BLI_edgehashIterator_new(eh);
1069                      BLI_edgehashIterator_isDone(ehi) == false;
1070                      BLI_edgehashIterator_step(ehi), ++medge, e_index++)
1071                 {
1072                         BLI_edgehashIterator_getKey(ehi, &medge->v1, &medge->v2);
1073                         BLI_edgehashIterator_setValue(ehi, SET_UINT_IN_POINTER(e_index));
1074
1075                         medge->crease = medge->bweight = 0;
1076                         medge->flag = ME_EDGEDRAW | ME_EDGERENDER;
1077                 }
1078                 BLI_edgehashIterator_free(ehi);
1079
1080                 *r_totedge = totedge;
1081
1082
1083                 for (i = 0, mp = mpoly; i < totpoly; i++, mp++) {
1084                         MLoop *l = &mloop[mp->loopstart];
1085                         MLoop *l_prev = (l + (mp->totloop - 1));
1086                         int j;
1087                         for (j = 0; j < mp->totloop; j++, l++) {
1088                                 /* lookup hashed edge index */
1089                                 l_prev->e = GET_UINT_FROM_POINTER(BLI_edgehash_lookup(eh, l_prev->v, l->v));
1090                                 l_prev = l;
1091                         }
1092                 }
1093         }
1094
1095         BLI_edgehash_free(eh, NULL);
1096 }
1097
1098
1099 /* Initialize mverts, medges and, faces for converting nurbs to mesh and derived mesh */
1100 /* return non-zero on error */
1101 int BKE_mesh_nurbs_to_mdata(
1102         Object *ob, MVert **r_allvert, int *r_totvert,
1103         MEdge **r_alledge, int *r_totedge, MLoop **r_allloop, MPoly **r_allpoly,
1104         int *r_totloop, int *r_totpoly)
1105 {
1106         ListBase disp = {NULL, NULL};
1107
1108         if (ob->curve_cache) {
1109                 disp = ob->curve_cache->disp;
1110         }
1111
1112         return BKE_mesh_nurbs_displist_to_mdata(
1113                 ob, &disp,
1114                 r_allvert, r_totvert,
1115                 r_alledge, r_totedge,
1116                 r_allloop, r_allpoly, NULL,
1117                 r_totloop, r_totpoly);
1118 }
1119
1120 /* BMESH: this doesn't calculate all edges from polygons,
1121  * only free standing edges are calculated */
1122
1123 /* Initialize mverts, medges and, faces for converting nurbs to mesh and derived mesh */
1124 /* use specified dispbase */
1125 int BKE_mesh_nurbs_displist_to_mdata(
1126         Object *ob, const ListBase *dispbase,
1127         MVert **r_allvert, int *r_totvert,
1128         MEdge **r_alledge, int *r_totedge,
1129         MLoop **r_allloop, MPoly **r_allpoly,
1130         MLoopUV **r_alluv,
1131         int *r_totloop, int *r_totpoly)
1132 {
1133         Curve *cu = ob->data;
1134         DispList *dl;
1135         MVert *mvert;
1136         MPoly *mpoly;
1137         MLoop *mloop;
1138         MLoopUV *mloopuv = NULL;
1139         MEdge *medge;
1140         const float *data;
1141         int a, b, ofs, vertcount, startvert, totvert = 0, totedge = 0, totloop = 0, totvlak = 0;
1142         int p1, p2, p3, p4, *index;
1143         const bool conv_polys = ((CU_DO_2DFILL(cu) == false) ||  /* 2d polys are filled with DL_INDEX3 displists */
1144                                  (ob->type == OB_SURF));  /* surf polys are never filled */
1145
1146         /* count */
1147         dl = dispbase->first;
1148         while (dl) {
1149                 if (dl->type == DL_SEGM) {
1150                         totvert += dl->parts * dl->nr;
1151                         totedge += dl->parts * (dl->nr - 1);
1152                 }
1153                 else if (dl->type == DL_POLY) {
1154                         if (conv_polys) {
1155                                 totvert += dl->parts * dl->nr;
1156                                 totedge += dl->parts * dl->nr;
1157                         }
1158                 }
1159                 else if (dl->type == DL_SURF) {
1160                         int tot;
1161                         totvert += dl->parts * dl->nr;
1162                         tot = (dl->parts - 1 + ((dl->flag & DL_CYCL_V) == 2)) * (dl->nr - 1 + (dl->flag & DL_CYCL_U));
1163                         totvlak += tot;
1164                         totloop += tot * 4;
1165                 }
1166                 else if (dl->type == DL_INDEX3) {
1167                         int tot;
1168                         totvert += dl->nr;
1169                         tot = dl->parts;
1170                         totvlak += tot;
1171                         totloop += tot * 3;
1172                 }
1173                 dl = dl->next;
1174         }
1175
1176         if (totvert == 0) {
1177                 /* error("can't convert"); */
1178                 /* Make Sure you check ob->data is a curve */
1179                 return -1;
1180         }
1181
1182         *r_allvert = mvert = MEM_callocN(sizeof(MVert) * totvert, "nurbs_init mvert");
1183         *r_alledge = medge = MEM_callocN(sizeof(MEdge) * totedge, "nurbs_init medge");
1184         *r_allloop = mloop = MEM_callocN(sizeof(MLoop) * totvlak * 4, "nurbs_init mloop"); // totloop
1185         *r_allpoly = mpoly = MEM_callocN(sizeof(MPoly) * totvlak, "nurbs_init mloop");
1186
1187         if (r_alluv)
1188                 *r_alluv = mloopuv = MEM_callocN(sizeof(MLoopUV) * totvlak * 4, "nurbs_init mloopuv");
1189         
1190         /* verts and faces */
1191         vertcount = 0;
1192
1193         dl = dispbase->first;
1194         while (dl) {
1195                 const bool is_smooth = (dl->rt & CU_SMOOTH) != 0;
1196
1197                 if (dl->type == DL_SEGM) {
1198                         startvert = vertcount;
1199                         a = dl->parts * dl->nr;
1200                         data = dl->verts;
1201                         while (a--) {
1202                                 copy_v3_v3(mvert->co, data);
1203                                 data += 3;
1204                                 vertcount++;
1205                                 mvert++;
1206                         }
1207
1208                         for (a = 0; a < dl->parts; a++) {
1209                                 ofs = a * dl->nr;
1210                                 for (b = 1; b < dl->nr; b++) {
1211                                         medge->v1 = startvert + ofs + b - 1;
1212                                         medge->v2 = startvert + ofs + b;
1213                                         medge->flag = ME_LOOSEEDGE | ME_EDGERENDER | ME_EDGEDRAW;
1214
1215                                         medge++;
1216                                 }
1217                         }
1218
1219                 }
1220                 else if (dl->type == DL_POLY) {
1221                         if (conv_polys) {
1222                                 startvert = vertcount;
1223                                 a = dl->parts * dl->nr;
1224                                 data = dl->verts;
1225                                 while (a--) {
1226                                         copy_v3_v3(mvert->co, data);
1227                                         data += 3;
1228                                         vertcount++;
1229                                         mvert++;
1230                                 }
1231
1232                                 for (a = 0; a < dl->parts; a++) {
1233                                         ofs = a * dl->nr;
1234                                         for (b = 0; b < dl->nr; b++) {
1235                                                 medge->v1 = startvert + ofs + b;
1236                                                 if (b == dl->nr - 1) medge->v2 = startvert + ofs;
1237                                                 else medge->v2 = startvert + ofs + b + 1;
1238                                                 medge->flag = ME_LOOSEEDGE | ME_EDGERENDER | ME_EDGEDRAW;
1239                                                 medge++;
1240                                         }
1241                                 }
1242                         }
1243                 }
1244                 else if (dl->type == DL_INDEX3) {
1245                         startvert = vertcount;
1246                         a = dl->nr;
1247                         data = dl->verts;
1248                         while (a--) {
1249                                 copy_v3_v3(mvert->co, data);
1250                                 data += 3;
1251                                 vertcount++;
1252                                 mvert++;
1253                         }
1254
1255                         a = dl->parts;
1256                         index = dl->index;
1257                         while (a--) {
1258                                 mloop[0].v = startvert + index[0];
1259                                 mloop[1].v = startvert + index[2];
1260                                 mloop[2].v = startvert + index[1];
1261                                 mpoly->loopstart = (int)(mloop - (*r_allloop));
1262                                 mpoly->totloop = 3;
1263                                 mpoly->mat_nr = dl->col;
1264
1265                                 if (mloopuv) {
1266                                         int i;
1267
1268                                         for (i = 0; i < 3; i++, mloopuv++) {
1269                                                 mloopuv->uv[0] = (mloop[i].v - startvert) / (float)(dl->nr - 1);
1270                                                 mloopuv->uv[1] = 0.0f;
1271                                         }
1272                                 }
1273
1274                                 if (is_smooth) mpoly->flag |= ME_SMOOTH;
1275                                 mpoly++;
1276                                 mloop += 3;
1277                                 index += 3;
1278                         }
1279                 }
1280                 else if (dl->type == DL_SURF) {
1281                         startvert = vertcount;
1282                         a = dl->parts * dl->nr;
1283                         data = dl->verts;
1284                         while (a--) {
1285                                 copy_v3_v3(mvert->co, data);
1286                                 data += 3;
1287                                 vertcount++;
1288                                 mvert++;
1289                         }
1290
1291                         for (a = 0; a < dl->parts; a++) {
1292
1293                                 if ( (dl->flag & DL_CYCL_V) == 0 && a == dl->parts - 1) break;
1294
1295                                 if (dl->flag & DL_CYCL_U) {         /* p2 -> p1 -> */
1296                                         p1 = startvert + dl->nr * a;    /* p4 -> p3 -> */
1297                                         p2 = p1 + dl->nr - 1;       /* -----> next row */
1298                                         p3 = p1 + dl->nr;
1299                                         p4 = p2 + dl->nr;
1300                                         b = 0;
1301                                 }
1302                                 else {
1303                                         p2 = startvert + dl->nr * a;
1304                                         p1 = p2 + 1;
1305                                         p4 = p2 + dl->nr;
1306                                         p3 = p1 + dl->nr;
1307                                         b = 1;
1308                                 }
1309                                 if ( (dl->flag & DL_CYCL_V) && a == dl->parts - 1) {
1310                                         p3 -= dl->parts * dl->nr;
1311                                         p4 -= dl->parts * dl->nr;
1312                                 }
1313
1314                                 for (; b < dl->nr; b++) {
1315                                         mloop[0].v = p1;
1316                                         mloop[1].v = p3;
1317                                         mloop[2].v = p4;
1318                                         mloop[3].v = p2;
1319                                         mpoly->loopstart = (int)(mloop - (*r_allloop));
1320                                         mpoly->totloop = 4;
1321                                         mpoly->mat_nr = dl->col;
1322
1323                                         if (mloopuv) {
1324                                                 int orco_sizeu = dl->nr - 1;
1325                                                 int orco_sizev = dl->parts - 1;
1326                                                 int i;
1327
1328                                                 /* exception as handled in convertblender.c too */
1329                                                 if (dl->flag & DL_CYCL_U) {
1330                                                         orco_sizeu++;
1331                                                         if (dl->flag & DL_CYCL_V)
1332                                                                 orco_sizev++;
1333                                                 }
1334                                                 else if (dl->flag & DL_CYCL_V) {
1335                                                         orco_sizev++;
1336                                                 }
1337
1338                                                 for (i = 0; i < 4; i++, mloopuv++) {
1339                                                         /* find uv based on vertex index into grid array */
1340                                                         int v = mloop[i].v - startvert;
1341
1342                                                         mloopuv->uv[0] = (v / dl->nr) / (float)orco_sizev;
1343                                                         mloopuv->uv[1] = (v % dl->nr) / (float)orco_sizeu;
1344
1345                                                         /* cyclic correction */
1346                                                         if ((i == 1 || i == 2) && mloopuv->uv[0] == 0.0f)
1347                                                                 mloopuv->uv[0] = 1.0f;
1348                                                         if ((i == 0 || i == 1) && mloopuv->uv[1] == 0.0f)
1349                                                                 mloopuv->uv[1] = 1.0f;
1350                                                 }
1351                                         }
1352
1353                                         if (is_smooth) mpoly->flag |= ME_SMOOTH;
1354                                         mpoly++;
1355                                         mloop += 4;
1356
1357                                         p4 = p3;
1358                                         p3++;
1359                                         p2 = p1;
1360                                         p1++;
1361                                 }
1362                         }
1363                 }
1364
1365                 dl = dl->next;
1366         }
1367         
1368         if (totvlak) {
1369                 make_edges_mdata_extend(r_alledge, &totedge,
1370                                         *r_allpoly, *r_allloop, totvlak);
1371         }
1372
1373         *r_totpoly = totvlak;
1374         *r_totloop = totloop;
1375         *r_totedge = totedge;
1376         *r_totvert = totvert;
1377
1378         return 0;
1379 }
1380
1381
1382 /* this may fail replacing ob->data, be sure to check ob->type */
1383 void BKE_mesh_from_nurbs_displist(Object *ob, ListBase *dispbase, const bool use_orco_uv, const char *obdata_name)
1384 {
1385         Main *bmain = G.main;
1386         Object *ob1;
1387         DerivedMesh *dm = ob->derivedFinal;
1388         Mesh *me;
1389         Curve *cu;
1390         MVert *allvert = NULL;
1391         MEdge *alledge = NULL;
1392         MLoop *allloop = NULL;
1393         MLoopUV *alluv = NULL;
1394         MPoly *allpoly = NULL;
1395         int totvert, totedge, totloop, totpoly;
1396
1397         cu = ob->data;
1398
1399         if (dm == NULL) {
1400                 if (BKE_mesh_nurbs_displist_to_mdata(ob, dispbase, &allvert, &totvert,
1401                                                      &alledge, &totedge, &allloop,
1402                                                      &allpoly, (use_orco_uv) ? &alluv : NULL,
1403                                                      &totloop, &totpoly) != 0)
1404                 {
1405                         /* Error initializing */
1406                         return;
1407                 }
1408
1409                 /* make mesh */
1410                 me = BKE_mesh_add(bmain, obdata_name);
1411                 me->totvert = totvert;
1412                 me->totedge = totedge;
1413                 me->totloop = totloop;
1414                 me->totpoly = totpoly;
1415
1416                 me->mvert = CustomData_add_layer(&me->vdata, CD_MVERT, CD_ASSIGN, allvert, me->totvert);
1417                 me->medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, alledge, me->totedge);
1418                 me->mloop = CustomData_add_layer(&me->ldata, CD_MLOOP, CD_ASSIGN, allloop, me->totloop);
1419                 me->mpoly = CustomData_add_layer(&me->pdata, CD_MPOLY, CD_ASSIGN, allpoly, me->totpoly);
1420
1421                 if (alluv) {
1422                         const char *uvname = "Orco";
1423                         me->mloopuv = CustomData_add_layer_named(&me->ldata, CD_MLOOPUV, CD_ASSIGN, alluv, me->totloop, uvname);
1424                 }
1425
1426                 BKE_mesh_calc_normals(me);
1427         }
1428         else {
1429                 me = BKE_mesh_add(bmain, obdata_name);
1430                 DM_to_mesh(dm, me, ob, CD_MASK_MESH, false);
1431         }
1432
1433         me->totcol = cu->totcol;
1434         me->mat = cu->mat;
1435
1436         BKE_mesh_texspace_calc(me);
1437
1438         cu->mat = NULL;
1439         cu->totcol = 0;
1440
1441         /* Do not decrement ob->data usercount here, it's done at end of func with BKE_libblock_free_us() call. */
1442         ob->data = me;
1443         ob->type = OB_MESH;
1444
1445         /* other users */
1446         ob1 = bmain->object.first;
1447         while (ob1) {
1448                 if (ob1->data == cu) {
1449                         ob1->type = OB_MESH;
1450                 
1451                         id_us_min((ID *)ob1->data);
1452                         ob1->data = ob->data;
1453                         id_us_plus((ID *)ob1->data);
1454                 }
1455                 ob1 = ob1->id.next;
1456         }
1457
1458         BKE_libblock_free_us(bmain, cu);
1459 }
1460
1461 void BKE_mesh_from_nurbs(Object *ob)
1462 {
1463         Curve *cu = (Curve *) ob->data;
1464         bool use_orco_uv = (cu->flag & CU_UV_ORCO) != 0;
1465         ListBase disp = {NULL, NULL};
1466
1467         if (ob->curve_cache) {
1468                 disp = ob->curve_cache->disp;
1469         }
1470
1471         BKE_mesh_from_nurbs_displist(ob, &disp, use_orco_uv, cu->id.name);
1472 }
1473
1474 typedef struct EdgeLink {
1475         struct EdgeLink *next, *prev;
1476         void *edge;
1477 } EdgeLink;
1478
1479 typedef struct VertLink {
1480         Link *next, *prev;
1481         unsigned int index;
1482 } VertLink;
1483
1484 static void prependPolyLineVert(ListBase *lb, unsigned int index)
1485 {
1486         VertLink *vl = MEM_callocN(sizeof(VertLink), "VertLink");
1487         vl->index = index;
1488         BLI_addhead(lb, vl);
1489 }
1490
1491 static void appendPolyLineVert(ListBase *lb, unsigned int index)
1492 {
1493         VertLink *vl = MEM_callocN(sizeof(VertLink), "VertLink");
1494         vl->index = index;
1495         BLI_addtail(lb, vl);
1496 }
1497
1498 void BKE_mesh_to_curve_nurblist(DerivedMesh *dm, ListBase *nurblist, const int edge_users_test)
1499 {
1500         MVert       *mvert = dm->getVertArray(dm);
1501         MEdge *med, *medge = dm->getEdgeArray(dm);
1502         MPoly *mp,  *mpoly = dm->getPolyArray(dm);
1503         MLoop       *mloop = dm->getLoopArray(dm);
1504
1505         int dm_totedge = dm->getNumEdges(dm);
1506         int dm_totpoly = dm->getNumPolys(dm);
1507         int totedges = 0;
1508         int i;
1509
1510         /* only to detect edge polylines */
1511         int *edge_users;
1512
1513         ListBase edges = {NULL, NULL};
1514
1515         /* get boundary edges */
1516         edge_users = MEM_callocN(sizeof(int) * dm_totedge, __func__);
1517         for (i = 0, mp = mpoly; i < dm_totpoly; i++, mp++) {
1518                 MLoop *ml = &mloop[mp->loopstart];
1519                 int j;
1520                 for (j = 0; j < mp->totloop; j++, ml++) {
1521                         edge_users[ml->e]++;
1522                 }
1523         }
1524
1525         /* create edges from all faces (so as to find edges not in any faces) */
1526         med = medge;
1527         for (i = 0; i < dm_totedge; i++, med++) {
1528                 if (edge_users[i] == edge_users_test) {
1529                         EdgeLink *edl = MEM_callocN(sizeof(EdgeLink), "EdgeLink");
1530                         edl->edge = med;
1531
1532                         BLI_addtail(&edges, edl);   totedges++;
1533                 }
1534         }
1535         MEM_freeN(edge_users);
1536
1537         if (edges.first) {
1538                 while (edges.first) {
1539                         /* each iteration find a polyline and add this as a nurbs poly spline */
1540
1541                         ListBase polyline = {NULL, NULL}; /* store a list of VertLink's */
1542                         bool closed = false;
1543                         int totpoly = 0;
1544                         MEdge *med_current = ((EdgeLink *)edges.last)->edge;
1545                         unsigned int startVert = med_current->v1;
1546                         unsigned int endVert = med_current->v2;
1547                         bool ok = true;
1548
1549                         appendPolyLineVert(&polyline, startVert);   totpoly++;
1550                         appendPolyLineVert(&polyline, endVert);     totpoly++;
1551                         BLI_freelinkN(&edges, edges.last);          totedges--;
1552
1553                         while (ok) { /* while connected edges are found... */
1554                                 EdgeLink *edl = edges.last;
1555                                 ok = false;
1556                                 while (edl) {
1557                                         EdgeLink *edl_prev = edl->prev;
1558
1559                                         med = edl->edge;
1560
1561                                         if (med->v1 == endVert) {
1562                                                 endVert = med->v2;
1563                                                 appendPolyLineVert(&polyline, med->v2); totpoly++;
1564                                                 BLI_freelinkN(&edges, edl);             totedges--;
1565                                                 ok = true;
1566                                         }
1567                                         else if (med->v2 == endVert) {
1568                                                 endVert = med->v1;
1569                                                 appendPolyLineVert(&polyline, endVert); totpoly++;
1570                                                 BLI_freelinkN(&edges, edl);             totedges--;
1571                                                 ok = true;
1572                                         }
1573                                         else if (med->v1 == startVert) {
1574                                                 startVert = med->v2;
1575                                                 prependPolyLineVert(&polyline, startVert);  totpoly++;
1576                                                 BLI_freelinkN(&edges, edl);                 totedges--;
1577                                                 ok = true;
1578                                         }
1579                                         else if (med->v2 == startVert) {
1580                                                 startVert = med->v1;
1581                                                 prependPolyLineVert(&polyline, startVert);  totpoly++;
1582                                                 BLI_freelinkN(&edges, edl);                 totedges--;
1583                                                 ok = true;
1584                                         }
1585
1586                                         edl = edl_prev;
1587                                 }
1588                         }
1589
1590                         /* Now we have a polyline, make into a curve */
1591                         if (startVert == endVert) {
1592                                 BLI_freelinkN(&polyline, polyline.last);
1593                                 totpoly--;
1594                                 closed = true;
1595                         }
1596
1597                         /* --- nurbs --- */
1598                         {
1599                                 Nurb *nu;
1600                                 BPoint *bp;
1601                                 VertLink *vl;
1602
1603                                 /* create new 'nurb' within the curve */
1604                                 nu = (Nurb *)MEM_callocN(sizeof(Nurb), "MeshNurb");
1605
1606                                 nu->pntsu = totpoly;
1607                                 nu->pntsv = 1;
1608                                 nu->orderu = 4;
1609                                 nu->flagu = CU_NURB_ENDPOINT | (closed ? CU_NURB_CYCLIC : 0);  /* endpoint */
1610                                 nu->resolu = 12;
1611
1612                                 nu->bp = (BPoint *)MEM_callocN(sizeof(BPoint) * totpoly, "bpoints");
1613
1614                                 /* add points */
1615                                 vl = polyline.first;
1616                                 for (i = 0, bp = nu->bp; i < totpoly; i++, bp++, vl = (VertLink *)vl->next) {
1617                                         copy_v3_v3(bp->vec, mvert[vl->index].co);
1618                                         bp->f1 = SELECT;
1619                                         bp->radius = bp->weight = 1.0;
1620                                 }
1621                                 BLI_freelistN(&polyline);
1622
1623                                 /* add nurb to curve */
1624                                 BLI_addtail(nurblist, nu);
1625                         }
1626                         /* --- done with nurbs --- */
1627                 }
1628         }
1629 }
1630
1631 void BKE_mesh_to_curve(EvaluationContext *eval_ctx, Scene *scene, Object *ob)
1632 {
1633         /* make new mesh data from the original copy */
1634         DerivedMesh *dm = mesh_get_derived_final(eval_ctx, scene, ob, CD_MASK_MESH);
1635         ListBase nurblist = {NULL, NULL};
1636         bool needsFree = false;
1637
1638         BKE_mesh_to_curve_nurblist(dm, &nurblist, 0);
1639         BKE_mesh_to_curve_nurblist(dm, &nurblist, 1);
1640
1641         if (nurblist.first) {
1642                 Curve *cu = BKE_curve_add(G.main, ob->id.name + 2, OB_CURVE);
1643                 cu->flag |= CU_3D;
1644
1645                 cu->nurb = nurblist;
1646
1647                 id_us_min(&((Mesh *)ob->data)->id);
1648                 ob->data = cu;
1649                 ob->type = OB_CURVE;
1650
1651                 /* curve objects can't contain DM in usual cases, we could free memory */
1652                 needsFree = true;
1653         }
1654
1655         dm->needsFree = needsFree;
1656         dm->release(dm);
1657
1658         if (needsFree) {
1659                 ob->derivedFinal = NULL;
1660
1661                 /* curve object could have got bounding box only in special cases */
1662                 if (ob->bb) {
1663                         MEM_freeN(ob->bb);
1664                         ob->bb = NULL;
1665                 }
1666         }
1667 }
1668
1669 void BKE_mesh_material_index_remove(Mesh *me, short index)
1670 {
1671         MPoly *mp;
1672         MFace *mf;
1673         int i;
1674
1675         for (mp = me->mpoly, i = 0; i < me->totpoly; i++, mp++) {
1676                 if (mp->mat_nr && mp->mat_nr >= index) {
1677                         mp->mat_nr--;
1678                 }
1679         }
1680
1681         for (mf = me->mface, i = 0; i < me->totface; i++, mf++) {
1682                 if (mf->mat_nr && mf->mat_nr >= index) {
1683                         mf->mat_nr--;
1684                 }
1685         }
1686 }
1687
1688 void BKE_mesh_material_index_clear(Mesh *me)
1689 {
1690         MPoly *mp;
1691         MFace *mf;
1692         int i;
1693
1694         for (mp = me->mpoly, i = 0; i < me->totpoly; i++, mp++) {
1695                 mp->mat_nr = 0;
1696         }
1697
1698         for (mf = me->mface, i = 0; i < me->totface; i++, mf++) {
1699                 mf->mat_nr = 0;
1700         }
1701 }
1702
1703 void BKE_mesh_material_remap(Mesh *me, const unsigned int *remap, unsigned int remap_len)
1704 {
1705         const short remap_len_short = (short)remap_len;
1706
1707 #define MAT_NR_REMAP(n) \
1708         if (n < remap_len_short) { \
1709                 BLI_assert(n >= 0 && remap[n] < remap_len_short); \
1710                 n = remap[n]; \
1711         } ((void)0)
1712
1713         if (me->edit_btmesh) {
1714                 BMEditMesh *em = me->edit_btmesh;
1715                 BMIter iter;
1716                 BMFace *efa;
1717
1718                 BM_ITER_MESH(efa, &iter, em->bm, BM_FACES_OF_MESH) {
1719                         MAT_NR_REMAP(efa->mat_nr);
1720                 }
1721         }
1722         else {
1723                 int i;
1724                 for (i = 0; i < me->totpoly; i++) {
1725                         MAT_NR_REMAP(me->mpoly[i].mat_nr);
1726                 }
1727         }
1728
1729 #undef MAT_NR_REMAP
1730
1731 }
1732
1733 void BKE_mesh_smooth_flag_set(Object *meshOb, int enableSmooth) 
1734 {
1735         Mesh *me = meshOb->data;
1736         int i;
1737
1738         for (i = 0; i < me->totpoly; i++) {
1739                 MPoly *mp = &me->mpoly[i];
1740
1741                 if (enableSmooth) {
1742                         mp->flag |= ME_SMOOTH;
1743                 }
1744                 else {
1745                         mp->flag &= ~ME_SMOOTH;
1746                 }
1747         }
1748         
1749         for (i = 0; i < me->totface; i++) {
1750                 MFace *mf = &me->mface[i];
1751
1752                 if (enableSmooth) {
1753                         mf->flag |= ME_SMOOTH;
1754                 }
1755                 else {
1756                         mf->flag &= ~ME_SMOOTH;
1757                 }
1758         }
1759 }
1760
1761 /**
1762  * Return a newly MEM_malloc'd array of all the mesh vertex locations
1763  * \note \a r_numVerts may be NULL
1764  */
1765 float (*BKE_mesh_vertexCos_get(const Mesh *me, int *r_numVerts))[3]
1766 {
1767         int i, numVerts = me->totvert;
1768         float (*cos)[3] = MEM_mallocN(sizeof(*cos) * numVerts, "vertexcos1");
1769
1770         if (r_numVerts) *r_numVerts = numVerts;
1771         for (i = 0; i < numVerts; i++)
1772                 copy_v3_v3(cos[i], me->mvert[i].co);
1773
1774         return cos;
1775 }
1776
1777 /**
1778  * Find the index of the loop in 'poly' which references vertex,
1779  * returns -1 if not found
1780  */
1781 int poly_find_loop_from_vert(
1782         const MPoly *poly, const MLoop *loopstart,
1783         unsigned vert)
1784 {
1785         int j;
1786         for (j = 0; j < poly->totloop; j++, loopstart++) {
1787                 if (loopstart->v == vert)
1788                         return j;
1789         }
1790         
1791         return -1;
1792 }
1793
1794 /**
1795  * Fill \a r_adj with the loop indices in \a poly adjacent to the
1796  * vertex. Returns the index of the loop matching vertex, or -1 if the
1797  * vertex is not in \a poly
1798  */
1799 int poly_get_adj_loops_from_vert(
1800         const MPoly *poly,
1801         const MLoop *mloop, unsigned int vert,
1802         unsigned int r_adj[2])
1803 {
1804         int corner = poly_find_loop_from_vert(poly,
1805                                               &mloop[poly->loopstart],
1806                                               vert);
1807                 
1808         if (corner != -1) {
1809 #if 0   /* unused - this loop */
1810                 const MLoop *ml = &mloop[poly->loopstart + corner];
1811 #endif
1812
1813                 /* vertex was found */
1814                 r_adj[0] = ME_POLY_LOOP_PREV(mloop, poly, corner)->v;
1815                 r_adj[1] = ME_POLY_LOOP_NEXT(mloop, poly, corner)->v;
1816         }
1817
1818         return corner;
1819 }
1820
1821 /**
1822  * Return the index of the edge vert that is not equal to \a v. If
1823  * neither edge vertex is equal to \a v, returns -1.
1824  */
1825 int BKE_mesh_edge_other_vert(const MEdge *e, int v)
1826 {
1827         if (e->v1 == v)
1828                 return e->v2;
1829         else if (e->v2 == v)
1830                 return e->v1;
1831         else
1832                 return -1;
1833 }
1834
1835 /* basic vertex data functions */
1836 bool BKE_mesh_minmax(const Mesh *me, float r_min[3], float r_max[3])
1837 {
1838         int i = me->totvert;
1839         MVert *mvert;
1840         for (mvert = me->mvert; i--; mvert++) {
1841                 minmax_v3v3_v3(r_min, r_max, mvert->co);
1842         }
1843         
1844         return (me->totvert != 0);
1845 }
1846
1847 void BKE_mesh_transform(Mesh *me, float mat[4][4], bool do_keys)
1848 {
1849         int i;
1850         MVert *mvert = me->mvert;
1851         float (*lnors)[3] = CustomData_get_layer(&me->ldata, CD_NORMAL);
1852
1853         for (i = 0; i < me->totvert; i++, mvert++)
1854                 mul_m4_v3(mat, mvert->co);
1855
1856         if (do_keys && me->key) {
1857                 KeyBlock *kb;
1858                 for (kb = me->key->block.first; kb; kb = kb->next) {
1859                         float *fp = kb->data;
1860                         for (i = kb->totelem; i--; fp += 3) {
1861                                 mul_m4_v3(mat, fp);
1862                         }
1863                 }
1864         }
1865
1866         /* don't update normals, caller can do this explicitly.
1867          * We do update loop normals though, those may not be auto-generated (see e.g. STL import script)! */
1868         if (lnors) {
1869                 float m3[3][3];
1870
1871                 copy_m3_m4(m3, mat);
1872                 normalize_m3(m3);
1873                 for (i = 0; i < me->totloop; i++, lnors++) {
1874                         mul_m3_v3(m3, *lnors);
1875                 }
1876         }
1877 }
1878
1879 void BKE_mesh_translate(Mesh *me, const float offset[3], const bool do_keys)
1880 {
1881         int i = me->totvert;
1882         MVert *mvert;
1883         for (mvert = me->mvert; i--; mvert++) {
1884                 add_v3_v3(mvert->co, offset);
1885         }
1886         
1887         if (do_keys && me->key) {
1888                 KeyBlock *kb;
1889                 for (kb = me->key->block.first; kb; kb = kb->next) {
1890                         float *fp = kb->data;
1891                         for (i = kb->totelem; i--; fp += 3) {
1892                                 add_v3_v3(fp, offset);
1893                         }
1894                 }
1895         }
1896 }
1897
1898 void BKE_mesh_ensure_navmesh(Mesh *me)
1899 {
1900         if (!CustomData_has_layer(&me->pdata, CD_RECAST)) {
1901                 int i;
1902                 int numFaces = me->totpoly;
1903                 int *recastData;
1904                 recastData = (int *)MEM_mallocN(numFaces * sizeof(int), __func__);
1905                 for (i = 0; i < numFaces; i++) {
1906                         recastData[i] = i + 1;
1907                 }
1908                 CustomData_add_layer_named(&me->pdata, CD_RECAST, CD_ASSIGN, recastData, numFaces, "recastData");
1909         }
1910 }
1911
1912 void BKE_mesh_tessface_calc(Mesh *mesh)
1913 {
1914         mesh->totface = BKE_mesh_recalc_tessellation(&mesh->fdata, &mesh->ldata, &mesh->pdata,
1915                                                      mesh->mvert,
1916                                                      mesh->totface, mesh->totloop, mesh->totpoly,
1917                                                      /* calc normals right after, don't copy from polys here */
1918                                                      false);
1919
1920         BKE_mesh_update_customdata_pointers(mesh, true);
1921 }
1922
1923 void BKE_mesh_tessface_ensure(Mesh *mesh)
1924 {
1925         if (mesh->totpoly && mesh->totface == 0) {
1926                 BKE_mesh_tessface_calc(mesh);
1927         }
1928 }
1929
1930 void BKE_mesh_tessface_clear(Mesh *mesh)
1931 {
1932         mesh_tessface_clear_intern(mesh, true);
1933 }
1934
1935 void BKE_mesh_do_versions_cd_flag_init(Mesh *mesh)
1936 {
1937         if (UNLIKELY(mesh->cd_flag)) {
1938                 return;
1939         }
1940         else {
1941                 MVert *mv;
1942                 MEdge *med;
1943                 int i;
1944
1945                 for (mv = mesh->mvert, i = 0; i < mesh->totvert; mv++, i++) {
1946                         if (mv->bweight != 0) {
1947                                 mesh->cd_flag |= ME_CDFLAG_VERT_BWEIGHT;
1948                                 break;
1949                         }
1950                 }
1951
1952                 for (med = mesh->medge, i = 0; i < mesh->totedge; med++, i++) {
1953                         if (med->bweight != 0) {
1954                                 mesh->cd_flag |= ME_CDFLAG_EDGE_BWEIGHT;
1955                                 if (mesh->cd_flag & ME_CDFLAG_EDGE_CREASE) {
1956                                         break;
1957                                 }
1958                         }
1959                         if (med->crease != 0) {
1960                                 mesh->cd_flag |= ME_CDFLAG_EDGE_CREASE;
1961                                 if (mesh->cd_flag & ME_CDFLAG_EDGE_BWEIGHT) {
1962                                         break;
1963                                 }
1964                         }
1965                 }
1966
1967         }
1968 }
1969
1970
1971 /* -------------------------------------------------------------------- */
1972 /* MSelect functions (currently used in weight paint mode) */
1973
1974 void BKE_mesh_mselect_clear(Mesh *me)
1975 {
1976         if (me->mselect) {
1977                 MEM_freeN(me->mselect);
1978                 me->mselect = NULL;
1979         }
1980         me->totselect = 0;
1981 }
1982
1983 void BKE_mesh_mselect_validate(Mesh *me)
1984 {
1985         MSelect *mselect_src, *mselect_dst;
1986         int i_src, i_dst;
1987
1988         if (me->totselect == 0)
1989                 return;
1990
1991         mselect_src = me->mselect;
1992         mselect_dst = MEM_mallocN(sizeof(MSelect) * (me->totselect), "Mesh selection history");
1993
1994         for (i_src = 0, i_dst = 0; i_src < me->totselect; i_src++) {
1995                 int index = mselect_src[i_src].index;
1996                 switch (mselect_src[i_src].type) {
1997                         case ME_VSEL:
1998                         {
1999                                 if (me->mvert[index].flag & SELECT) {
2000                                         mselect_dst[i_dst] = mselect_src[i_src];
2001                                         i_dst++;
2002                                 }
2003                                 break;
2004                         }
2005                         case ME_ESEL:
2006                         {
2007                                 if (me->medge[index].flag & SELECT) {
2008                                         mselect_dst[i_dst] = mselect_src[i_src];
2009                                         i_dst++;
2010                                 }
2011                                 break;
2012                         }
2013                         case ME_FSEL:
2014                         {
2015                                 if (me->mpoly[index].flag & SELECT) {
2016                                         mselect_dst[i_dst] = mselect_src[i_src];
2017                                         i_dst++;
2018                                 }
2019                                 break;
2020                         }
2021                         default:
2022                         {
2023                                 BLI_assert(0);
2024                                 break;
2025                         }
2026                 }
2027         }
2028
2029         MEM_freeN(mselect_src);
2030
2031         if (i_dst == 0) {
2032                 MEM_freeN(mselect_dst);
2033                 mselect_dst = NULL;
2034         }
2035         else if (i_dst != me->totselect) {
2036                 mselect_dst = MEM_reallocN(mselect_dst, sizeof(MSelect) * i_dst);
2037         }
2038
2039         me->totselect = i_dst;
2040         me->mselect = mselect_dst;
2041
2042 }
2043
2044 /**
2045  * Return the index within me->mselect, or -1
2046  */
2047 int BKE_mesh_mselect_find(Mesh *me, int index, int type)
2048 {
2049         int i;
2050
2051         BLI_assert(ELEM(type, ME_VSEL, ME_ESEL, ME_FSEL));
2052
2053         for (i = 0; i < me->totselect; i++) {
2054                 if ((me->mselect[i].index == index) &&
2055                     (me->mselect[i].type == type))
2056                 {
2057                         return i;
2058                 }
2059         }
2060
2061         return -1;
2062 }
2063
2064 /**
2065  * Return The index of the active element.
2066  */
2067 int BKE_mesh_mselect_active_get(Mesh *me, int type)
2068 {
2069         BLI_assert(ELEM(type, ME_VSEL, ME_ESEL, ME_FSEL));
2070
2071         if (me->totselect) {
2072                 if (me->mselect[me->totselect - 1].type == type) {
2073                         return me->mselect[me->totselect - 1].index;
2074                 }
2075         }
2076         return -1;
2077 }
2078
2079 void BKE_mesh_mselect_active_set(Mesh *me, int index, int type)
2080 {
2081         const int msel_index = BKE_mesh_mselect_find(me, index, type);
2082
2083         if (msel_index == -1) {
2084                 /* add to the end */
2085                 me->mselect = MEM_reallocN(me->mselect, sizeof(MSelect) * (me->totselect + 1));
2086                 me->mselect[me->totselect].index = index;
2087                 me->mselect[me->totselect].type  = type;
2088                 me->totselect++;
2089         }
2090         else if (msel_index != me->totselect - 1) {
2091                 /* move to the end */
2092                 SWAP(MSelect, me->mselect[msel_index], me->mselect[me->totselect - 1]);
2093         }
2094
2095         BLI_assert((me->mselect[me->totselect - 1].index == index) &&
2096                    (me->mselect[me->totselect - 1].type  == type));
2097 }
2098
2099 void BKE_mesh_calc_normals_split_ex(Mesh *mesh, MLoopNorSpaceArray *r_lnors_spacearr)
2100 {
2101         float (*r_loopnors)[3];
2102         float (*polynors)[3];
2103         short (*clnors)[2] = NULL;
2104         bool free_polynors = false;
2105
2106         if (CustomData_has_layer(&mesh->ldata, CD_NORMAL)) {
2107                 r_loopnors = CustomData_get_layer(&mesh->ldata, CD_NORMAL);
2108                 memset(r_loopnors, 0, sizeof(float[3]) * mesh->totloop);
2109         }
2110         else {
2111                 r_loopnors = CustomData_add_layer(&mesh->ldata, CD_NORMAL, CD_CALLOC, NULL, mesh->totloop);
2112                 CustomData_set_layer_flag(&mesh->ldata, CD_NORMAL, CD_FLAG_TEMPORARY);
2113         }
2114
2115         /* may be NULL */
2116         clnors = CustomData_get_layer(&mesh->ldata, CD_CUSTOMLOOPNORMAL);
2117
2118         if (CustomData_has_layer(&mesh->pdata, CD_NORMAL)) {
2119                 /* This assume that layer is always up to date, not sure this is the case (esp. in Edit mode?)... */
2120                 polynors = CustomData_get_layer(&mesh->pdata, CD_NORMAL);
2121                 free_polynors = false;
2122         }
2123         else {
2124                 polynors = MEM_mallocN(sizeof(float[3]) * mesh->totpoly, __func__);
2125                 BKE_mesh_calc_normals_poly(
2126                             mesh->mvert, NULL, mesh->totvert,
2127                             mesh->mloop, mesh->mpoly, mesh->totloop, mesh->totpoly, polynors, false);
2128                 free_polynors = true;
2129         }
2130
2131         BKE_mesh_normals_loop_split(
2132                 mesh->mvert, mesh->totvert, mesh->medge, mesh->totedge,
2133                 mesh->mloop, r_loopnors, mesh->totloop, mesh->mpoly, (const float (*)[3])polynors, mesh->totpoly,
2134                 (mesh->flag & ME_AUTOSMOOTH) != 0, mesh->smoothresh, r_lnors_spacearr, clnors, NULL);
2135
2136         if (free_polynors) {
2137                 MEM_freeN(polynors);
2138         }
2139 }
2140
2141 void BKE_mesh_calc_normals_split(Mesh *mesh)
2142 {
2143         BKE_mesh_calc_normals_split_ex(mesh, NULL);
2144 }
2145
2146 /* Split faces helper functions. */
2147
2148 typedef struct SplitFaceNewVert {
2149         struct SplitFaceNewVert *next;
2150         int new_index;
2151         int orig_index;
2152         float *vnor;
2153 } SplitFaceNewVert;
2154
2155 typedef struct SplitFaceNewEdge {
2156         struct SplitFaceNewEdge *next;
2157         int new_index;
2158         int orig_index;
2159         int v1;
2160         int v2;
2161 } SplitFaceNewEdge;
2162
2163 /* Detect needed new vertices, and update accordingly loops' vertex indices.
2164  * WARNING! Leaves mesh in invalid state. */
2165 static int split_faces_prepare_new_verts(
2166         const Mesh *mesh, MLoopNorSpaceArray *lnors_spacearr, SplitFaceNewVert **new_verts, MemArena *memarena,
2167         bool *r_need_vnors_recalc)
2168 {
2169         /* Note: if lnors_spacearr is NULL, ther is no autosmooth handling, and we only split out flat polys. */
2170         const int num_loops = mesh->totloop;
2171         int num_verts = mesh->totvert;
2172         MVert *mvert = mesh->mvert;
2173         MLoop *mloop = mesh->mloop;
2174
2175         BLI_bitmap *verts_used = BLI_BITMAP_NEW(num_verts, __func__);
2176
2177         if (lnors_spacearr) {
2178                 BLI_bitmap *done_loops = BLI_BITMAP_NEW(num_loops, __func__);
2179
2180                 MLoop *ml = mloop;
2181                 MLoopNorSpace **lnor_space = lnors_spacearr->lspacearr;
2182                 for (int loop_idx = 0; loop_idx < num_loops; loop_idx++, ml++, lnor_space++) {
2183                         if (!BLI_BITMAP_TEST(done_loops, loop_idx)) {
2184                                 const int vert_idx = ml->v;
2185                                 const bool vert_used = BLI_BITMAP_TEST_BOOL(verts_used, vert_idx);
2186                                 /* If vert is already used by another smooth fan, we need a new vert for this one. */
2187                                 const int new_vert_idx = vert_used ? num_verts++ : vert_idx;
2188
2189                                 BLI_assert(*lnor_space);
2190
2191                                 if ((*lnor_space)->loops) {
2192                                         for (LinkNode *lnode = (*lnor_space)->loops; lnode; lnode = lnode->next) {
2193                                                 const int ml_fan_idx = GET_INT_FROM_POINTER(lnode->link);
2194                                                 BLI_BITMAP_ENABLE(done_loops, ml_fan_idx);
2195                                                 if (vert_used) {
2196                                                         mloop[ml_fan_idx].v = new_vert_idx;
2197                                                 }
2198                                         }
2199                                 }
2200                                 else {
2201                                         /* Single loop in this fan... */
2202                                         BLI_BITMAP_ENABLE(done_loops, loop_idx);
2203                                         if (vert_used) {
2204                                                 ml->v = new_vert_idx;
2205                                         }
2206                                 }
2207
2208                                 if (!vert_used) {
2209                                         BLI_BITMAP_ENABLE(verts_used, vert_idx);
2210                                         /* We need to update that vertex's normal here, we won't go over it again. */
2211                                         /* This is important! *DO NOT* set vnor to final computed lnor, vnor should always be defined to
2212                                          * 'automatic normal' value computed from its polys, not some custom normal.
2213                                          * Fortunately, that's the loop normal space's 'lnor' reference vector. ;) */
2214                                         normal_float_to_short_v3(mvert[vert_idx].no, (*lnor_space)->vec_lnor);
2215                                 }
2216                                 else {
2217                                         /* Add new vert to list. */
2218                                         SplitFaceNewVert *new_vert = BLI_memarena_alloc(memarena, sizeof(*new_vert));
2219                                         new_vert->orig_index = vert_idx;
2220                                         new_vert->new_index = new_vert_idx;
2221                                         new_vert->vnor = (*lnor_space)->vec_lnor;  /* See note above. */
2222                                         new_vert->next = *new_verts;
2223                                         *new_verts = new_vert;
2224                                 }
2225                         }
2226                 }
2227
2228                 MEM_freeN(done_loops);
2229         }
2230         else {
2231                 /* No loop normal spaces available, we only split out flat polys. */
2232                 const int num_polys = mesh->totpoly;
2233                 const MPoly *mpoly = mesh->mpoly;
2234
2235                 /* We do that in two loops, to keep original edges/verts to smooth polys preferencially. */
2236                 const MPoly *mp = mpoly;
2237                 for (int i = 0; i < num_polys; i++, mp++) {
2238                         if (mp->flag & ME_SMOOTH) {
2239                                 const MLoop *ml = &mloop[mp->loopstart];
2240                                 for (int j = 0; j < mp->totloop; j++, ml++) {
2241                                         /* Just mark the vertex as used/reserved, that way neighbor flat polys, if any,
2242                                          * will have to create their own. */
2243                                         BLI_BITMAP_ENABLE(verts_used, ml->v);
2244                                 }
2245                         }
2246                 }
2247
2248                 mp = mpoly;
2249                 for (int i = 0; i < num_polys; i++, mp++) {
2250                         if (!(mp->flag & ME_SMOOTH)) {
2251                                 MLoop *ml = &mloop[mp->loopstart];
2252                                 for (int j = 0; j < mp->totloop; j++, ml++) {
2253                                         const int vert_idx = ml->v;
2254
2255                                         if (BLI_BITMAP_TEST(verts_used, vert_idx)) {
2256                                                 /* Add new vert to list. */
2257                                                 const int new_vert_idx = num_verts++;
2258                                                 ml->v = new_vert_idx;
2259
2260                                                 SplitFaceNewVert *new_vert = BLI_memarena_alloc(memarena, sizeof(*new_vert));
2261                                                 new_vert->orig_index = vert_idx;
2262                                                 new_vert->new_index = new_vert_idx;
2263                                                 new_vert->vnor = NULL;  /* See note below about normals. */
2264                                                 new_vert->next = *new_verts;
2265                                                 *new_verts = new_vert;
2266                                         }
2267                                         else {
2268                                                 BLI_BITMAP_ENABLE(verts_used, vert_idx);
2269                                         }
2270                                 }
2271                                 /* Note: there is no way to get new normals for smooth vertices here (and we don't have direct access
2272                                  * to poly normals either for flat ones), so we'll have to recompute all vnors at the end... */
2273                                 *r_need_vnors_recalc = true;
2274                         }
2275                 }
2276         }
2277
2278         MEM_freeN(verts_used);
2279
2280         return num_verts - mesh->totvert;
2281 }
2282
2283 /* Detect needed new edges, and update accordingly loops' edge indices.
2284  * WARNING! Leaves mesh in invalid state. */
2285 static int split_faces_prepare_new_edges(
2286         const Mesh *mesh, SplitFaceNewEdge **new_edges, MemArena *memarena)
2287 {
2288         const int num_polys = mesh->totpoly;
2289         int num_edges = mesh->totedge;
2290         MEdge *medge = mesh->medge;
2291         MLoop *mloop = mesh->mloop;
2292         const MPoly *mpoly = mesh->mpoly;
2293
2294         BLI_bitmap *edges_used = BLI_BITMAP_NEW(num_edges, __func__);
2295         EdgeHash *edges_hash = BLI_edgehash_new_ex(__func__, num_edges);
2296
2297         const MPoly *mp = mpoly;
2298         for (int poly_idx = 0; poly_idx < num_polys; poly_idx++, mp++) {
2299                 MLoop *ml_prev = &mloop[mp->loopstart + mp->totloop - 1];
2300                 MLoop *ml = &mloop[mp->loopstart];
2301                 for (int loop_idx = 0; loop_idx < mp->totloop; loop_idx++, ml++) {
2302                         void **eval;
2303                         if (!BLI_edgehash_ensure_p(edges_hash, ml_prev->v, ml->v, &eval)) {
2304                                 const int edge_idx = ml_prev->e;
2305
2306                                 /* That edge has not been encountered yet, define it. */
2307                                 if (BLI_BITMAP_TEST(edges_used, edge_idx)) {
2308                                         /* Original edge has already been used, we need to define a new one. */
2309                                         const int new_edge_idx = num_edges++;
2310                                         *eval = SET_INT_IN_POINTER(new_edge_idx);
2311                                         ml_prev->e = new_edge_idx;
2312
2313                                         SplitFaceNewEdge *new_edge = BLI_memarena_alloc(memarena, sizeof(*new_edge));
2314                                         new_edge->orig_index = edge_idx;
2315                                         new_edge->new_index = new_edge_idx;
2316                                         new_edge->v1 = ml_prev->v;
2317                                         new_edge->v2 = ml->v;
2318                                         new_edge->next = *new_edges;
2319                                         *new_edges = new_edge;
2320                                 }
2321                                 else {
2322                                         /* We can re-use original edge. */
2323                                         medge[edge_idx].v1 = ml_prev->v;
2324                                         medge[edge_idx].v2 = ml->v;
2325                                         *eval = SET_INT_IN_POINTER(edge_idx);
2326                                         BLI_BITMAP_ENABLE(edges_used, edge_idx);
2327                                 }
2328                         }
2329                         else {
2330                                 /* Edge already known, just update loop's edge index. */
2331                                 ml_prev->e = GET_INT_FROM_POINTER(*eval);
2332                         }
2333
2334                         ml_prev = ml;
2335                 }
2336         }
2337
2338         MEM_freeN(edges_used);
2339         BLI_edgehash_free(edges_hash, NULL);
2340
2341         return num_edges - mesh->totedge;
2342 }
2343
2344 /* Perform actual split of vertices. */
2345 static void split_faces_split_new_verts(
2346         Mesh *mesh, SplitFaceNewVert *new_verts, const int num_new_verts)
2347 {
2348         const int num_verts = mesh->totvert - num_new_verts;
2349         MVert *mvert = mesh->mvert;
2350
2351         /* Remember new_verts is a single linklist, so its items are in reversed order... */
2352         MVert *new_mv = &mvert[mesh->totvert - 1];
2353         for (int i = mesh->totvert - 1; i >= num_verts ; i--, new_mv--, new_verts = new_verts->next) {
2354                 BLI_assert(new_verts->new_index == i);
2355                 BLI_assert(new_verts->new_index != new_verts->orig_index);
2356                 CustomData_copy_data(&mesh->vdata, &mesh->vdata, new_verts->orig_index, i, 1);
2357                 if (new_verts->vnor) {
2358                         normal_float_to_short_v3(new_mv->no, new_verts->vnor);
2359                 }
2360         }
2361 }
2362
2363 /* Perform actual split of edges. */
2364 static void split_faces_split_new_edges(
2365         Mesh *mesh, SplitFaceNewEdge *new_edges, const int num_new_edges)
2366 {
2367         const int num_edges = mesh->totedge - num_new_edges;
2368         MEdge *medge = mesh->medge;
2369
2370         /* Remember new_edges is a single linklist, so its items are in reversed order... */
2371         MEdge *new_med = &medge[mesh->totedge - 1];
2372         for (int i = mesh->totedge - 1; i >= num_edges ; i--, new_med--, new_edges = new_edges->next) {
2373                 BLI_assert(new_edges->new_index == i);
2374                 BLI_assert(new_edges->new_index != new_edges->orig_index);
2375                 CustomData_copy_data(&mesh->edata, &mesh->edata, new_edges->orig_index, i, 1);
2376                 new_med->v1 = new_edges->v1;
2377                 new_med->v2 = new_edges->v2;
2378         }
2379 }
2380
2381 /* Split faces based on the edge angle and loop normals.
2382  * Matches behavior of face splitting in render engines.
2383  *
2384  * NOTE: Will leave CD_NORMAL loop data layer which is
2385  * used by render engines to set shading up.
2386  */
2387 void BKE_mesh_split_faces(Mesh *mesh, bool free_loop_normals)
2388 {
2389         const int num_polys = mesh->totpoly;
2390
2391         if (num_polys == 0) {
2392                 return;
2393         }
2394         BKE_mesh_tessface_clear(mesh);
2395
2396         MLoopNorSpaceArray *lnors_spacearr = NULL;
2397         MemArena *memarena;
2398         bool need_vnors_recalc = false;
2399
2400         if (mesh->flag & ME_AUTOSMOOTH) {
2401                 lnors_spacearr = MEM_callocN(sizeof(*lnors_spacearr), __func__);
2402                 /* Compute loop normals and loop normal spaces (a.k.a. smooth fans of faces around vertices). */
2403                 BKE_mesh_calc_normals_split_ex(mesh, lnors_spacearr);
2404                 /* Stealing memarena from loop normals space array. */
2405                 memarena = lnors_spacearr->mem;
2406         }
2407         else {
2408                 /* We still have to split out flat faces... */
2409                 memarena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
2410         }
2411
2412         SplitFaceNewVert *new_verts = NULL;
2413         SplitFaceNewEdge *new_edges = NULL;
2414
2415         /* Detect loop normal spaces (a.k.a. smooth fans) that will need a new vert. */
2416         const int num_new_verts = split_faces_prepare_new_verts(mesh, lnors_spacearr, &new_verts, memarena, &need_vnors_recalc);
2417
2418         if (num_new_verts > 0) {
2419                 /* Reminder: beyond this point, there is no way out, mesh is in invalid state (due to early-reassignment of
2420                  * loops' vertex and edge indices to new, to-be-created split ones). */
2421
2422                 const int num_new_edges = split_faces_prepare_new_edges(mesh, &new_edges, memarena);
2423                 /* We can have to split a vertex without having to add a single new edge... */
2424                 const bool do_edges = (num_new_edges > 0);
2425
2426                 /* Reallocate all vert and edge related data. */
2427                 mesh->totvert += num_new_verts;
2428                 mesh->totedge += num_new_edges;
2429                 CustomData_realloc(&mesh->vdata, mesh->totvert);
2430                 if (do_edges) {
2431                         CustomData_realloc(&mesh->edata, mesh->totedge);
2432                 }
2433                 /* Update pointers to a newly allocated memory. */
2434                 BKE_mesh_update_customdata_pointers(mesh, false);
2435
2436                 /* Perform actual split of vertices and edges. */
2437                 split_faces_split_new_verts(mesh, new_verts, num_new_verts);
2438                 if (do_edges) {
2439                         split_faces_split_new_edges(mesh, new_edges, num_new_edges);
2440                 }
2441         }
2442
2443         /* Note: after this point mesh is expected to be valid again. */
2444
2445         /* CD_NORMAL is expected to be temporary only. */
2446         if (free_loop_normals) {
2447                 CustomData_free_layers(&mesh->ldata, CD_NORMAL, mesh->totloop);
2448         }
2449
2450         if (lnors_spacearr) {
2451                 /* Also frees new_verts/edges temp data, since we used its memarena to allocate them. */
2452                 BKE_lnor_spacearr_free(lnors_spacearr);
2453                 MEM_freeN(lnors_spacearr);
2454         }
2455         else {
2456                 BLI_memarena_free(memarena);
2457         }
2458
2459         if (need_vnors_recalc) {
2460                 BKE_mesh_calc_normals(mesh);
2461         }
2462 #ifdef VALIDATE_MESH
2463         BKE_mesh_validate(mesh, true, true);
2464 #endif
2465 }
2466
2467 /* settings: 1 - preview, 2 - render */
2468 Mesh *BKE_mesh_new_from_object(
2469         EvaluationContext *eval_ctx, Main *bmain, Scene *sce, Object *ob,
2470         int apply_modifiers, int settings, int calc_tessface, int calc_undeformed)
2471 {
2472         Mesh *tmpmesh;
2473         Curve *tmpcu = NULL, *copycu;
2474         int i;
2475         const bool render = (settings == eModifierMode_Render);
2476         const bool cage = !apply_modifiers;
2477         bool do_mat_id_data_us = true;
2478
2479         /* perform the mesh extraction based on type */
2480         switch (ob->type) {
2481                 case OB_FONT:
2482                 case OB_CURVE:
2483                 case OB_SURF:
2484                 {
2485                         ListBase dispbase = {NULL, NULL};
2486                         DerivedMesh *derivedFinal = NULL;
2487                         int uv_from_orco;
2488
2489                         /* copies object and modifiers (but not the data) */
2490                         Object *tmpobj = BKE_object_copy_ex(bmain, ob, true);
2491                         tmpcu = (Curve *)tmpobj->data;
2492                         id_us_min(&tmpcu->id);
2493
2494                         /* Copy cached display list, it might be needed by the stack evaluation.
2495                          * Ideally stack should be able to use render-time display list, but doing
2496                          * so is quite tricky and not safe so close to the release.
2497                          *
2498                          * TODO(sergey): Look into more proper solution.
2499                          */
2500                         if (ob->curve_cache != NULL) {
2501                                 if (tmpobj->curve_cache == NULL) {
2502                                         tmpobj->curve_cache = MEM_callocN(sizeof(CurveCache), "CurveCache for curve types");
2503                                 }
2504                                 BKE_displist_copy(&tmpobj->curve_cache->disp, &ob->curve_cache->disp);
2505                         }
2506
2507                         /* if getting the original caged mesh, delete object modifiers */
2508                         if (cage)
2509                                 BKE_object_free_modifiers(tmpobj);
2510
2511                         /* copies the data */
2512                         copycu = tmpobj->data = BKE_curve_copy(bmain, (Curve *) ob->data);
2513
2514                         /* temporarily set edit so we get updates from edit mode, but
2515                          * also because for text datablocks copying it while in edit
2516                          * mode gives invalid data structures */
2517                         copycu->editfont = tmpcu->editfont;
2518                         copycu->editnurb = tmpcu->editnurb;
2519
2520                         /* get updated display list, and convert to a mesh */
2521                         BKE_displist_make_curveTypes_forRender(eval_ctx, sce, tmpobj, &dispbase, &derivedFinal, false, render);
2522
2523                         copycu->editfont = NULL;
2524                         copycu->editnurb = NULL;
2525
2526                         tmpobj->derivedFinal = derivedFinal;
2527
2528                         /* convert object type to mesh */
2529                         uv_from_orco = (tmpcu->flag & CU_UV_ORCO) != 0;
2530                         BKE_mesh_from_nurbs_displist(tmpobj, &dispbase, uv_from_orco, tmpcu->id.name + 2);
2531
2532                         tmpmesh = tmpobj->data;
2533
2534                         BKE_displist_free(&dispbase);
2535
2536                         /* BKE_mesh_from_nurbs changes the type to a mesh, check it worked.
2537                          * if it didn't the curve did not have any segments or otherwise 
2538                          * would have generated an empty mesh */
2539                         if (tmpobj->type != OB_MESH) {
2540                                 BKE_libblock_free_us(bmain, tmpobj);
2541                                 return NULL;
2542                         }
2543
2544                         BKE_mesh_texspace_copy_from_object(tmpmesh, ob);
2545
2546                         BKE_libblock_free_us(bmain, tmpobj);
2547
2548                         /* XXX The curve to mesh conversion is convoluted... But essentially, BKE_mesh_from_nurbs_displist()
2549                          *     already transfers the ownership of materials from the temp copy of the Curve ID to the new
2550                          *     Mesh ID, so we do not want to increase materials' usercount later. */
2551                         do_mat_id_data_us = false;
2552
2553                         break;
2554                 }
2555
2556                 case OB_MBALL:
2557                 {
2558                         /* metaballs don't have modifiers, so just convert to mesh */
2559                         Object *basis_ob = BKE_mball_basis_find(sce, ob);
2560                         /* todo, re-generatre for render-res */
2561                         /* metaball_polygonize(scene, ob) */
2562
2563                         if (ob != basis_ob)
2564                                 return NULL;  /* only do basis metaball */
2565
2566                         tmpmesh = BKE_mesh_add(bmain, ((ID *)ob->data)->name + 2);
2567                         /* BKE_mesh_add gives us a user count we don't need */
2568                         id_us_min(&tmpmesh->id);
2569
2570                         if (render) {
2571                                 ListBase disp = {NULL, NULL};
2572                                 BKE_displist_make_mball_forRender(eval_ctx, sce, ob, &disp);
2573                                 BKE_mesh_from_metaball(&disp, tmpmesh);
2574                                 BKE_displist_free(&disp);
2575                         }
2576                         else {
2577                                 ListBase disp = {NULL, NULL};
2578                                 if (ob->curve_cache) {
2579                                         disp = ob->curve_cache->disp;
2580                                 }
2581                                 BKE_mesh_from_metaball(&disp, tmpmesh);
2582                         }
2583
2584                         BKE_mesh_texspace_copy_from_object(tmpmesh, ob);
2585
2586                         break;
2587
2588                 }
2589                 case OB_MESH:
2590                         /* copies object and modifiers (but not the data) */
2591                         if (cage) {
2592                                 /* copies the data */
2593                                 tmpmesh = BKE_mesh_copy(bmain, ob->data);
2594
2595                                 /* XXX BKE_mesh_copy() already handles materials usercount. */
2596                                 do_mat_id_data_us = false;
2597                         }
2598                         /* if not getting the original caged mesh, get final derived mesh */
2599                         else {
2600                                 /* Make a dummy mesh, saves copying */
2601                                 DerivedMesh *dm;
2602                                 /* CustomDataMask mask = CD_MASK_BAREMESH|CD_MASK_MTFACE|CD_MASK_MCOL; */
2603                                 CustomDataMask mask = CD_MASK_MESH; /* this seems more suitable, exporter,
2604                                                                      * for example, needs CD_MASK_MDEFORMVERT */
2605
2606                                 if (calc_undeformed)
2607                                         mask |= CD_MASK_ORCO;
2608
2609                                 /* Write the display mesh into the dummy mesh */
2610                                 if (render)
2611                                         dm = mesh_create_derived_render(eval_ctx, sce, ob, mask);
2612                                 else
2613                                         dm = mesh_create_derived_view(eval_ctx, sce, ob, mask);
2614
2615                                 tmpmesh = BKE_mesh_add(bmain, ((ID *)ob->data)->name + 2);
2616                                 DM_to_mesh(dm, tmpmesh, ob, mask, true);
2617
2618                                 /* Copy autosmooth settings from original mesh. */
2619                                 Mesh *me = (Mesh *)ob->data;
2620                                 tmpmesh->flag |= (me->flag & ME_AUTOSMOOTH);
2621                                 tmpmesh->smoothresh = me->smoothresh;
2622                         }
2623
2624                         /* BKE_mesh_add/copy gives us a user count we don't need */
2625                         id_us_min(&tmpmesh->id);
2626
2627                         break;
2628                 default:
2629                         /* "Object does not have geometry data") */
2630                         return NULL;
2631         }
2632
2633         /* Copy materials to new mesh */
2634         switch (ob->type) {
2635                 case OB_SURF:
2636                 case OB_FONT:
2637                 case OB_CURVE:
2638                         tmpmesh->totcol = tmpcu->totcol;
2639
2640                         /* free old material list (if it exists) and adjust user counts */
2641                         if (tmpcu->mat) {
2642                                 for (i = tmpcu->totcol; i-- > 0; ) {
2643                                         /* are we an object material or data based? */
2644                                         tmpmesh->mat[i] = give_current_material(ob, i + 1);
2645
2646                                         if (((ob->matbits && ob->matbits[i]) || do_mat_id_data_us)  && tmpmesh->mat[i]) {
2647                                                 id_us_plus(&tmpmesh->mat[i]->id);
2648                                         }
2649                                 }
2650                         }
2651                         break;
2652
2653                 case OB_MBALL:
2654                 {
2655                         MetaBall *tmpmb = (MetaBall *)ob->data;
2656                         tmpmesh->mat = MEM_dupallocN(tmpmb->mat);
2657                         tmpmesh->totcol = tmpmb->totcol;
2658
2659                         /* free old material list (if it exists) and adjust user counts */
2660                         if (tmpmb->mat) {
2661                                 for (i = tmpmb->totcol; i-- > 0; ) {
2662                                         /* are we an object material or data based? */
2663                                         tmpmesh->mat[i] = give_current_material(ob, i + 1);
2664
2665                                         if (((ob->matbits && ob->matbits[i]) || do_mat_id_data_us) && tmpmesh->mat[i]) {
2666                                                 id_us_plus(&tmpmesh->mat[i]->id);
2667                                         }
2668                                 }
2669                         }
2670                         break;
2671                 }
2672
2673                 case OB_MESH:
2674                         if (!cage) {
2675                                 Mesh *origmesh = ob->data;
2676                                 tmpmesh->flag = origmesh->flag;
2677                                 tmpmesh->mat = MEM_dupallocN(origmesh->mat);
2678                                 tmpmesh->totcol = origmesh->totcol;
2679                                 tmpmesh->smoothresh = origmesh->smoothresh;
2680                                 if (origmesh->mat) {
2681                                         for (i = origmesh->totcol; i-- > 0; ) {
2682                                                 /* are we an object material or data based? */
2683                                                 tmpmesh->mat[i] = give_current_material(ob, i + 1);
2684
2685                                                 if (((ob->matbits && ob->matbits[i]) || do_mat_id_data_us)  && tmpmesh->mat[i]) {
2686                                                         id_us_plus(&tmpmesh->mat[i]->id);
2687                                                 }
2688                                         }
2689                                 }
2690                         }
2691                         break;
2692         } /* end copy materials */
2693
2694         if (calc_tessface) {
2695                 /* cycles and exporters rely on this still */
2696                 BKE_mesh_tessface_ensure(tmpmesh);
2697         }
2698
2699         return tmpmesh;
2700 }
2701
2702 /* **** Depsgraph evaluation **** */
2703
2704 void BKE_mesh_eval_geometry(EvaluationContext *UNUSED(eval_ctx),
2705                             Mesh *mesh)
2706 {
2707         if (G.debug & G_DEBUG_DEPSGRAPH) {
2708                 printf("%s on %s\n", __func__, mesh->id.name);
2709         }
2710         if (mesh->bb == NULL || (mesh->bb->flag & BOUNDBOX_DIRTY)) {
2711                 BKE_mesh_texspace_calc(mesh);
2712         }
2713 }
2714
2715 /* Draw Engine */
2716 void (*BKE_mesh_batch_cache_dirty_cb)(Mesh *me, int mode) = NULL;
2717 void (*BKE_mesh_batch_cache_free_cb)(Mesh *me) = NULL;
2718
2719 void BKE_mesh_batch_cache_dirty(Mesh *me, int mode)
2720 {
2721         if (me->batch_cache) {
2722                 BKE_mesh_batch_cache_dirty_cb(me, mode);
2723         }
2724 }
2725 void BKE_mesh_batch_cache_free(Mesh *me)
2726 {
2727         if (me->batch_cache) {
2728                 BKE_mesh_batch_cache_free_cb(me);
2729         }
2730 }