Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenkernel / intern / mesh_convert.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  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 /** \file blender/blenkernel/intern/mesh_convert.c
22  *  \ingroup bke
23  */
24
25
26 #include "MEM_guardedalloc.h"
27
28 #include "DNA_scene_types.h"
29 #include "DNA_material_types.h"
30 #include "DNA_meta_types.h"
31 #include "DNA_object_types.h"
32 #include "DNA_mesh_types.h"
33 #include "DNA_curve_types.h"
34
35 #include "BLI_utildefines.h"
36 #include "BLI_math.h"
37 #include "BLI_listbase.h"
38 #include "BLI_edgehash.h"
39
40 #include "BKE_main.h"
41 #include "BKE_DerivedMesh.h"
42 #include "BKE_global.h"
43 #include "BKE_mesh.h"
44 #include "BKE_displist.h"
45 #include "BKE_library.h"
46 #include "BKE_material.h"
47 #include "BKE_mball.h"
48 /* these 2 are only used by conversion functions */
49 #include "BKE_curve.h"
50 /* -- */
51 #include "BKE_object.h"
52
53 #include "DEG_depsgraph.h"
54 #include "DEG_depsgraph_query.h"
55
56 /* Define for cases when you want extra validation of mesh
57  * after certain modifications.
58  */
59 // #undef VALIDATE_MESH
60
61 void BKE_mesh_from_metaball(ListBase *lb, Mesh *me)
62 {
63         DispList *dl;
64         MVert *mvert;
65         MLoop *mloop, *allloop;
66         MPoly *mpoly;
67         const float *nors, *verts;
68         int a, *index;
69
70         dl = lb->first;
71         if (dl == NULL) return;
72
73         if (dl->type == DL_INDEX4) {
74                 mvert = CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, dl->nr);
75                 allloop = mloop = CustomData_add_layer(&me->ldata, CD_MLOOP, CD_CALLOC, NULL, dl->parts * 4);
76                 mpoly = CustomData_add_layer(&me->pdata, CD_MPOLY, CD_CALLOC, NULL, dl->parts);
77                 me->mvert = mvert;
78                 me->mloop = mloop;
79                 me->mpoly = mpoly;
80                 me->totvert = dl->nr;
81                 me->totpoly = dl->parts;
82
83                 a = dl->nr;
84                 nors = dl->nors;
85                 verts = dl->verts;
86                 while (a--) {
87                         copy_v3_v3(mvert->co, verts);
88                         normal_float_to_short_v3(mvert->no, nors);
89                         mvert++;
90                         nors += 3;
91                         verts += 3;
92                 }
93
94                 a = dl->parts;
95                 index = dl->index;
96                 while (a--) {
97                         int count = index[2] != index[3] ? 4 : 3;
98
99                         mloop[0].v = index[0];
100                         mloop[1].v = index[1];
101                         mloop[2].v = index[2];
102                         if (count == 4)
103                                 mloop[3].v = index[3];
104
105                         mpoly->totloop = count;
106                         mpoly->loopstart = (int)(mloop - allloop);
107                         mpoly->flag = ME_SMOOTH;
108
109
110                         mpoly++;
111                         mloop += count;
112                         me->totloop += count;
113                         index += 4;
114                 }
115
116                 BKE_mesh_update_customdata_pointers(me, true);
117
118                 BKE_mesh_calc_normals(me);
119
120                 BKE_mesh_calc_edges(me, true, false);
121         }
122 }
123
124 /**
125  * Specialized function to use when we _know_ existing edges don't overlap with poly edges.
126  */
127 static void make_edges_mdata_extend(MEdge **r_alledge, int *r_totedge,
128                                     const MPoly *mpoly, MLoop *mloop,
129                                     const int totpoly)
130 {
131         int totedge = *r_totedge;
132         int totedge_new;
133         EdgeHash *eh;
134         unsigned int eh_reserve;
135         const MPoly *mp;
136         int i;
137
138         eh_reserve = max_ii(totedge, BLI_EDGEHASH_SIZE_GUESS_FROM_POLYS(totpoly));
139         eh = BLI_edgehash_new_ex(__func__, eh_reserve);
140
141         for (i = 0, mp = mpoly; i < totpoly; i++, mp++) {
142                 BKE_mesh_poly_edgehash_insert(eh, mp, mloop + mp->loopstart);
143         }
144
145         totedge_new = BLI_edgehash_len(eh);
146
147 #ifdef DEBUG
148         /* ensure that theres no overlap! */
149         if (totedge_new) {
150                 MEdge *medge = *r_alledge;
151                 for (i = 0; i < totedge; i++, medge++) {
152                         BLI_assert(BLI_edgehash_haskey(eh, medge->v1, medge->v2) == false);
153                 }
154         }
155 #endif
156
157         if (totedge_new) {
158                 EdgeHashIterator *ehi;
159                 MEdge *medge;
160                 unsigned int e_index = totedge;
161
162                 *r_alledge = medge = (*r_alledge ? MEM_reallocN(*r_alledge, sizeof(MEdge) * (totedge + totedge_new)) :
163                                                    MEM_calloc_arrayN(totedge_new, sizeof(MEdge), __func__));
164                 medge += totedge;
165
166                 totedge += totedge_new;
167
168                 /* --- */
169                 for (ehi = BLI_edgehashIterator_new(eh);
170                      BLI_edgehashIterator_isDone(ehi) == false;
171                      BLI_edgehashIterator_step(ehi), ++medge, e_index++)
172                 {
173                         BLI_edgehashIterator_getKey(ehi, &medge->v1, &medge->v2);
174                         BLI_edgehashIterator_setValue(ehi, SET_UINT_IN_POINTER(e_index));
175
176                         medge->crease = medge->bweight = 0;
177                         medge->flag = ME_EDGEDRAW | ME_EDGERENDER;
178                 }
179                 BLI_edgehashIterator_free(ehi);
180
181                 *r_totedge = totedge;
182
183
184                 for (i = 0, mp = mpoly; i < totpoly; i++, mp++) {
185                         MLoop *l = &mloop[mp->loopstart];
186                         MLoop *l_prev = (l + (mp->totloop - 1));
187                         int j;
188                         for (j = 0; j < mp->totloop; j++, l++) {
189                                 /* lookup hashed edge index */
190                                 l_prev->e = GET_UINT_FROM_POINTER(BLI_edgehash_lookup(eh, l_prev->v, l->v));
191                                 l_prev = l;
192                         }
193                 }
194         }
195
196         BLI_edgehash_free(eh, NULL);
197 }
198
199
200 /* Initialize mverts, medges and, faces for converting nurbs to mesh and derived mesh */
201 /* return non-zero on error */
202 int BKE_mesh_nurbs_to_mdata(
203         Object *ob, MVert **r_allvert, int *r_totvert,
204         MEdge **r_alledge, int *r_totedge, MLoop **r_allloop, MPoly **r_allpoly,
205         int *r_totloop, int *r_totpoly)
206 {
207         ListBase disp = {NULL, NULL};
208
209         if (ob->curve_cache) {
210                 disp = ob->curve_cache->disp;
211         }
212
213         return BKE_mesh_nurbs_displist_to_mdata(
214                 ob, &disp,
215                 r_allvert, r_totvert,
216                 r_alledge, r_totedge,
217                 r_allloop, r_allpoly, NULL,
218                 r_totloop, r_totpoly);
219 }
220
221 /* BMESH: this doesn't calculate all edges from polygons,
222  * only free standing edges are calculated */
223
224 /* Initialize mverts, medges and, faces for converting nurbs to mesh and derived mesh */
225 /* use specified dispbase */
226 int BKE_mesh_nurbs_displist_to_mdata(
227         Object *ob, const ListBase *dispbase,
228         MVert **r_allvert, int *r_totvert,
229         MEdge **r_alledge, int *r_totedge,
230         MLoop **r_allloop, MPoly **r_allpoly,
231         MLoopUV **r_alluv,
232         int *r_totloop, int *r_totpoly)
233 {
234         Curve *cu = ob->data;
235         DispList *dl;
236         MVert *mvert;
237         MPoly *mpoly;
238         MLoop *mloop;
239         MLoopUV *mloopuv = NULL;
240         MEdge *medge;
241         const float *data;
242         int a, b, ofs, vertcount, startvert, totvert = 0, totedge = 0, totloop = 0, totpoly = 0;
243         int p1, p2, p3, p4, *index;
244         const bool conv_polys = ((CU_DO_2DFILL(cu) == false) ||  /* 2d polys are filled with DL_INDEX3 displists */
245                                  (ob->type == OB_SURF));  /* surf polys are never filled */
246
247         /* count */
248         dl = dispbase->first;
249         while (dl) {
250                 if (dl->type == DL_SEGM) {
251                         totvert += dl->parts * dl->nr;
252                         totedge += dl->parts * (dl->nr - 1);
253                 }
254                 else if (dl->type == DL_POLY) {
255                         if (conv_polys) {
256                                 totvert += dl->parts * dl->nr;
257                                 totedge += dl->parts * dl->nr;
258                         }
259                 }
260                 else if (dl->type == DL_SURF) {
261                         int tot;
262                         totvert += dl->parts * dl->nr;
263                         tot = (dl->parts - 1 + ((dl->flag & DL_CYCL_V) == 2)) * (dl->nr - 1 + (dl->flag & DL_CYCL_U));
264                         totpoly += tot;
265                         totloop += tot * 4;
266                 }
267                 else if (dl->type == DL_INDEX3) {
268                         int tot;
269                         totvert += dl->nr;
270                         tot = dl->parts;
271                         totpoly += tot;
272                         totloop += tot * 3;
273                 }
274                 dl = dl->next;
275         }
276
277         if (totvert == 0) {
278                 /* error("can't convert"); */
279                 /* Make Sure you check ob->data is a curve */
280                 return -1;
281         }
282
283         *r_allvert = mvert = MEM_calloc_arrayN(totvert, sizeof(MVert), "nurbs_init mvert");
284         *r_alledge = medge = MEM_calloc_arrayN(totedge, sizeof(MEdge), "nurbs_init medge");
285         *r_allloop = mloop = MEM_calloc_arrayN(totpoly, 4 * sizeof(MLoop), "nurbs_init mloop"); // totloop
286         *r_allpoly = mpoly = MEM_calloc_arrayN(totpoly, sizeof(MPoly), "nurbs_init mloop");
287
288         if (r_alluv)
289                 *r_alluv = mloopuv = MEM_calloc_arrayN(totpoly, 4 * sizeof(MLoopUV), "nurbs_init mloopuv");
290
291         /* verts and faces */
292         vertcount = 0;
293
294         dl = dispbase->first;
295         while (dl) {
296                 const bool is_smooth = (dl->rt & CU_SMOOTH) != 0;
297
298                 if (dl->type == DL_SEGM) {
299                         startvert = vertcount;
300                         a = dl->parts * dl->nr;
301                         data = dl->verts;
302                         while (a--) {
303                                 copy_v3_v3(mvert->co, data);
304                                 data += 3;
305                                 vertcount++;
306                                 mvert++;
307                         }
308
309                         for (a = 0; a < dl->parts; a++) {
310                                 ofs = a * dl->nr;
311                                 for (b = 1; b < dl->nr; b++) {
312                                         medge->v1 = startvert + ofs + b - 1;
313                                         medge->v2 = startvert + ofs + b;
314                                         medge->flag = ME_LOOSEEDGE | ME_EDGERENDER | ME_EDGEDRAW;
315
316                                         medge++;
317                                 }
318                         }
319
320                 }
321                 else if (dl->type == DL_POLY) {
322                         if (conv_polys) {
323                                 startvert = vertcount;
324                                 a = dl->parts * dl->nr;
325                                 data = dl->verts;
326                                 while (a--) {
327                                         copy_v3_v3(mvert->co, data);
328                                         data += 3;
329                                         vertcount++;
330                                         mvert++;
331                                 }
332
333                                 for (a = 0; a < dl->parts; a++) {
334                                         ofs = a * dl->nr;
335                                         for (b = 0; b < dl->nr; b++) {
336                                                 medge->v1 = startvert + ofs + b;
337                                                 if (b == dl->nr - 1) medge->v2 = startvert + ofs;
338                                                 else medge->v2 = startvert + ofs + b + 1;
339                                                 medge->flag = ME_LOOSEEDGE | ME_EDGERENDER | ME_EDGEDRAW;
340                                                 medge++;
341                                         }
342                                 }
343                         }
344                 }
345                 else if (dl->type == DL_INDEX3) {
346                         startvert = vertcount;
347                         a = dl->nr;
348                         data = dl->verts;
349                         while (a--) {
350                                 copy_v3_v3(mvert->co, data);
351                                 data += 3;
352                                 vertcount++;
353                                 mvert++;
354                         }
355
356                         a = dl->parts;
357                         index = dl->index;
358                         while (a--) {
359                                 mloop[0].v = startvert + index[0];
360                                 mloop[1].v = startvert + index[2];
361                                 mloop[2].v = startvert + index[1];
362                                 mpoly->loopstart = (int)(mloop - (*r_allloop));
363                                 mpoly->totloop = 3;
364                                 mpoly->mat_nr = dl->col;
365
366                                 if (mloopuv) {
367                                         int i;
368
369                                         for (i = 0; i < 3; i++, mloopuv++) {
370                                                 mloopuv->uv[0] = (mloop[i].v - startvert) / (float)(dl->nr - 1);
371                                                 mloopuv->uv[1] = 0.0f;
372                                         }
373                                 }
374
375                                 if (is_smooth) mpoly->flag |= ME_SMOOTH;
376                                 mpoly++;
377                                 mloop += 3;
378                                 index += 3;
379                         }
380                 }
381                 else if (dl->type == DL_SURF) {
382                         startvert = vertcount;
383                         a = dl->parts * dl->nr;
384                         data = dl->verts;
385                         while (a--) {
386                                 copy_v3_v3(mvert->co, data);
387                                 data += 3;
388                                 vertcount++;
389                                 mvert++;
390                         }
391
392                         for (a = 0; a < dl->parts; a++) {
393
394                                 if ( (dl->flag & DL_CYCL_V) == 0 && a == dl->parts - 1) break;
395
396                                 if (dl->flag & DL_CYCL_U) {         /* p2 -> p1 -> */
397                                         p1 = startvert + dl->nr * a;    /* p4 -> p3 -> */
398                                         p2 = p1 + dl->nr - 1;       /* -----> next row */
399                                         p3 = p1 + dl->nr;
400                                         p4 = p2 + dl->nr;
401                                         b = 0;
402                                 }
403                                 else {
404                                         p2 = startvert + dl->nr * a;
405                                         p1 = p2 + 1;
406                                         p4 = p2 + dl->nr;
407                                         p3 = p1 + dl->nr;
408                                         b = 1;
409                                 }
410                                 if ( (dl->flag & DL_CYCL_V) && a == dl->parts - 1) {
411                                         p3 -= dl->parts * dl->nr;
412                                         p4 -= dl->parts * dl->nr;
413                                 }
414
415                                 for (; b < dl->nr; b++) {
416                                         mloop[0].v = p1;
417                                         mloop[1].v = p3;
418                                         mloop[2].v = p4;
419                                         mloop[3].v = p2;
420                                         mpoly->loopstart = (int)(mloop - (*r_allloop));
421                                         mpoly->totloop = 4;
422                                         mpoly->mat_nr = dl->col;
423
424                                         if (mloopuv) {
425                                                 int orco_sizeu = dl->nr - 1;
426                                                 int orco_sizev = dl->parts - 1;
427                                                 int i;
428
429                                                 /* exception as handled in convertblender.c too */
430                                                 if (dl->flag & DL_CYCL_U) {
431                                                         orco_sizeu++;
432                                                         if (dl->flag & DL_CYCL_V)
433                                                                 orco_sizev++;
434                                                 }
435                                                 else if (dl->flag & DL_CYCL_V) {
436                                                         orco_sizev++;
437                                                 }
438
439                                                 for (i = 0; i < 4; i++, mloopuv++) {
440                                                         /* find uv based on vertex index into grid array */
441                                                         int v = mloop[i].v - startvert;
442
443                                                         mloopuv->uv[0] = (v / dl->nr) / (float)orco_sizev;
444                                                         mloopuv->uv[1] = (v % dl->nr) / (float)orco_sizeu;
445
446                                                         /* cyclic correction */
447                                                         if ((i == 1 || i == 2) && mloopuv->uv[0] == 0.0f)
448                                                                 mloopuv->uv[0] = 1.0f;
449                                                         if ((i == 0 || i == 1) && mloopuv->uv[1] == 0.0f)
450                                                                 mloopuv->uv[1] = 1.0f;
451                                                 }
452                                         }
453
454                                         if (is_smooth) mpoly->flag |= ME_SMOOTH;
455                                         mpoly++;
456                                         mloop += 4;
457
458                                         p4 = p3;
459                                         p3++;
460                                         p2 = p1;
461                                         p1++;
462                                 }
463                         }
464                 }
465
466                 dl = dl->next;
467         }
468
469         if (totpoly) {
470                 make_edges_mdata_extend(
471                         r_alledge, &totedge,
472                         *r_allpoly, *r_allloop, totpoly);
473         }
474
475         *r_totpoly = totpoly;
476         *r_totloop = totloop;
477         *r_totedge = totedge;
478         *r_totvert = totvert;
479
480         return 0;
481 }
482
483 Mesh *BKE_mesh_new_nomain_from_curve_displist(Object *ob, ListBase *dispbase)
484 {
485         Curve *cu = ob->data;
486         Mesh *mesh;
487         MVert *allvert;
488         MEdge *alledge;
489         MLoop *allloop;
490         MPoly *allpoly;
491         MLoopUV *alluv = NULL;
492         int totvert, totedge, totloop, totpoly;
493         bool use_orco_uv = (cu->flag & CU_UV_ORCO) != 0;
494
495         if (BKE_mesh_nurbs_displist_to_mdata(
496                 ob, dispbase, &allvert, &totvert, &alledge,
497                 &totedge, &allloop, &allpoly, (use_orco_uv) ? &alluv : NULL,
498                 &totloop, &totpoly) != 0)
499         {
500                 /* Error initializing mdata. This often happens when curve is empty */
501                 return BKE_mesh_new_nomain(0, 0, 0, 0, 0);
502         }
503
504         mesh = BKE_mesh_new_nomain(totvert, totedge, 0, totloop, totpoly);
505         mesh->runtime.cd_dirty_vert |= CD_MASK_NORMAL;
506
507         memcpy(mesh->mvert, allvert, totvert * sizeof(MVert));
508         memcpy(mesh->medge, alledge, totedge * sizeof(MEdge));
509         memcpy(mesh->mloop, allloop, totloop * sizeof(MLoop));
510         memcpy(mesh->mpoly, allpoly, totpoly * sizeof(MPoly));
511
512         if (alluv) {
513                 const char *uvname = "Orco";
514                 CustomData_add_layer_named(&mesh->ldata, CD_MLOOPUV, CD_ASSIGN, alluv, totloop, uvname);
515         }
516
517         MEM_freeN(allvert);
518         MEM_freeN(alledge);
519         MEM_freeN(allloop);
520         MEM_freeN(allpoly);
521
522         return mesh;
523 }
524
525 Mesh *BKE_mesh_new_nomain_from_curve(Object *ob)
526 {
527         ListBase disp = {NULL, NULL};
528
529         if (ob->curve_cache) {
530                 disp = ob->curve_cache->disp;
531         }
532
533         return BKE_mesh_new_nomain_from_curve_displist(ob, &disp);
534 }
535
536 /* this may fail replacing ob->data, be sure to check ob->type */
537 void BKE_mesh_from_nurbs_displist(Object *ob, ListBase *dispbase, const bool use_orco_uv, const char *obdata_name)
538 {
539         Main *bmain = G.main;
540         Object *ob1;
541         DerivedMesh *dm = ob->derivedFinal;
542         Mesh *me;
543         Curve *cu;
544         MVert *allvert = NULL;
545         MEdge *alledge = NULL;
546         MLoop *allloop = NULL;
547         MLoopUV *alluv = NULL;
548         MPoly *allpoly = NULL;
549         int totvert, totedge, totloop, totpoly;
550
551         cu = ob->data;
552
553         if (dm == NULL) {
554                 if (BKE_mesh_nurbs_displist_to_mdata(ob, dispbase, &allvert, &totvert,
555                                                      &alledge, &totedge, &allloop,
556                                                      &allpoly, (use_orco_uv) ? &alluv : NULL,
557                                                      &totloop, &totpoly) != 0)
558                 {
559                         /* Error initializing */
560                         return;
561                 }
562
563                 /* make mesh */
564                 me = BKE_mesh_add(bmain, obdata_name);
565                 me->totvert = totvert;
566                 me->totedge = totedge;
567                 me->totloop = totloop;
568                 me->totpoly = totpoly;
569
570                 me->mvert = CustomData_add_layer(&me->vdata, CD_MVERT, CD_ASSIGN, allvert, me->totvert);
571                 me->medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, alledge, me->totedge);
572                 me->mloop = CustomData_add_layer(&me->ldata, CD_MLOOP, CD_ASSIGN, allloop, me->totloop);
573                 me->mpoly = CustomData_add_layer(&me->pdata, CD_MPOLY, CD_ASSIGN, allpoly, me->totpoly);
574
575                 if (alluv) {
576                         const char *uvname = "Orco";
577                         me->mloopuv = CustomData_add_layer_named(&me->ldata, CD_MLOOPUV, CD_ASSIGN, alluv, me->totloop, uvname);
578                 }
579
580                 BKE_mesh_calc_normals(me);
581         }
582         else {
583                 me = BKE_mesh_add(bmain, obdata_name);
584                 DM_to_mesh(dm, me, ob, CD_MASK_MESH, false);
585         }
586
587         me->totcol = cu->totcol;
588         me->mat = cu->mat;
589
590         /* Copy evaluated texture space from curve to mesh.
591          *
592          * Note that we disable auto texture space feature since that will cause
593          * texture space to evaluate differently for curve and mesh, since curve
594          * uses CV to calculate bounding box, and mesh uses what is coming from
595          * tessellated curve.
596          */
597         me->texflag = cu->texflag & ~CU_AUTOSPACE;
598         copy_v3_v3(me->loc, cu->loc);
599         copy_v3_v3(me->size, cu->size);
600         copy_v3_v3(me->rot, cu->rot);
601         BKE_mesh_texspace_calc(me);
602
603         cu->mat = NULL;
604         cu->totcol = 0;
605
606         /* Do not decrement ob->data usercount here, it's done at end of func with BKE_libblock_free_us() call. */
607         ob->data = me;
608         ob->type = OB_MESH;
609
610         /* other users */
611         ob1 = bmain->object.first;
612         while (ob1) {
613                 if (ob1->data == cu) {
614                         ob1->type = OB_MESH;
615
616                         id_us_min((ID *)ob1->data);
617                         ob1->data = ob->data;
618                         id_us_plus((ID *)ob1->data);
619                 }
620                 ob1 = ob1->id.next;
621         }
622
623         BKE_libblock_free_us(bmain, cu);
624 }
625
626 void BKE_mesh_from_nurbs(Object *ob)
627 {
628         Curve *cu = (Curve *) ob->data;
629         bool use_orco_uv = (cu->flag & CU_UV_ORCO) != 0;
630         ListBase disp = {NULL, NULL};
631
632         if (ob->curve_cache) {
633                 disp = ob->curve_cache->disp;
634         }
635
636         BKE_mesh_from_nurbs_displist(ob, &disp, use_orco_uv, cu->id.name);
637 }
638
639 typedef struct EdgeLink {
640         struct EdgeLink *next, *prev;
641         void *edge;
642 } EdgeLink;
643
644 typedef struct VertLink {
645         Link *next, *prev;
646         unsigned int index;
647 } VertLink;
648
649 static void prependPolyLineVert(ListBase *lb, unsigned int index)
650 {
651         VertLink *vl = MEM_callocN(sizeof(VertLink), "VertLink");
652         vl->index = index;
653         BLI_addhead(lb, vl);
654 }
655
656 static void appendPolyLineVert(ListBase *lb, unsigned int index)
657 {
658         VertLink *vl = MEM_callocN(sizeof(VertLink), "VertLink");
659         vl->index = index;
660         BLI_addtail(lb, vl);
661 }
662
663 void BKE_mesh_to_curve_nurblist(DerivedMesh *dm, ListBase *nurblist, const int edge_users_test)
664 {
665         MVert       *mvert = dm->getVertArray(dm);
666         MEdge *med, *medge = dm->getEdgeArray(dm);
667         MPoly *mp,  *mpoly = dm->getPolyArray(dm);
668         MLoop       *mloop = dm->getLoopArray(dm);
669
670         int dm_totedge = dm->getNumEdges(dm);
671         int dm_totpoly = dm->getNumPolys(dm);
672         int totedges = 0;
673         int i;
674
675         /* only to detect edge polylines */
676         int *edge_users;
677
678         ListBase edges = {NULL, NULL};
679
680         /* get boundary edges */
681         edge_users = MEM_calloc_arrayN(dm_totedge, sizeof(int), __func__);
682         for (i = 0, mp = mpoly; i < dm_totpoly; i++, mp++) {
683                 MLoop *ml = &mloop[mp->loopstart];
684                 int j;
685                 for (j = 0; j < mp->totloop; j++, ml++) {
686                         edge_users[ml->e]++;
687                 }
688         }
689
690         /* create edges from all faces (so as to find edges not in any faces) */
691         med = medge;
692         for (i = 0; i < dm_totedge; i++, med++) {
693                 if (edge_users[i] == edge_users_test) {
694                         EdgeLink *edl = MEM_callocN(sizeof(EdgeLink), "EdgeLink");
695                         edl->edge = med;
696
697                         BLI_addtail(&edges, edl);   totedges++;
698                 }
699         }
700         MEM_freeN(edge_users);
701
702         if (edges.first) {
703                 while (edges.first) {
704                         /* each iteration find a polyline and add this as a nurbs poly spline */
705
706                         ListBase polyline = {NULL, NULL}; /* store a list of VertLink's */
707                         bool closed = false;
708                         int totpoly = 0;
709                         MEdge *med_current = ((EdgeLink *)edges.last)->edge;
710                         unsigned int startVert = med_current->v1;
711                         unsigned int endVert = med_current->v2;
712                         bool ok = true;
713
714                         appendPolyLineVert(&polyline, startVert);   totpoly++;
715                         appendPolyLineVert(&polyline, endVert);     totpoly++;
716                         BLI_freelinkN(&edges, edges.last);          totedges--;
717
718                         while (ok) { /* while connected edges are found... */
719                                 EdgeLink *edl = edges.last;
720                                 ok = false;
721                                 while (edl) {
722                                         EdgeLink *edl_prev = edl->prev;
723
724                                         med = edl->edge;
725
726                                         if (med->v1 == endVert) {
727                                                 endVert = med->v2;
728                                                 appendPolyLineVert(&polyline, med->v2); totpoly++;
729                                                 BLI_freelinkN(&edges, edl);             totedges--;
730                                                 ok = true;
731                                         }
732                                         else if (med->v2 == endVert) {
733                                                 endVert = med->v1;
734                                                 appendPolyLineVert(&polyline, endVert); totpoly++;
735                                                 BLI_freelinkN(&edges, edl);             totedges--;
736                                                 ok = true;
737                                         }
738                                         else if (med->v1 == startVert) {
739                                                 startVert = med->v2;
740                                                 prependPolyLineVert(&polyline, startVert);  totpoly++;
741                                                 BLI_freelinkN(&edges, edl);                 totedges--;
742                                                 ok = true;
743                                         }
744                                         else if (med->v2 == startVert) {
745                                                 startVert = med->v1;
746                                                 prependPolyLineVert(&polyline, startVert);  totpoly++;
747                                                 BLI_freelinkN(&edges, edl);                 totedges--;
748                                                 ok = true;
749                                         }
750
751                                         edl = edl_prev;
752                                 }
753                         }
754
755                         /* Now we have a polyline, make into a curve */
756                         if (startVert == endVert) {
757                                 BLI_freelinkN(&polyline, polyline.last);
758                                 totpoly--;
759                                 closed = true;
760                         }
761
762                         /* --- nurbs --- */
763                         {
764                                 Nurb *nu;
765                                 BPoint *bp;
766                                 VertLink *vl;
767
768                                 /* create new 'nurb' within the curve */
769                                 nu = (Nurb *)MEM_callocN(sizeof(Nurb), "MeshNurb");
770
771                                 nu->pntsu = totpoly;
772                                 nu->pntsv = 1;
773                                 nu->orderu = 4;
774                                 nu->flagu = CU_NURB_ENDPOINT | (closed ? CU_NURB_CYCLIC : 0);  /* endpoint */
775                                 nu->resolu = 12;
776
777                                 nu->bp = (BPoint *)MEM_calloc_arrayN(totpoly, sizeof(BPoint), "bpoints");
778
779                                 /* add points */
780                                 vl = polyline.first;
781                                 for (i = 0, bp = nu->bp; i < totpoly; i++, bp++, vl = (VertLink *)vl->next) {
782                                         copy_v3_v3(bp->vec, mvert[vl->index].co);
783                                         bp->f1 = SELECT;
784                                         bp->radius = bp->weight = 1.0;
785                                 }
786                                 BLI_freelistN(&polyline);
787
788                                 /* add nurb to curve */
789                                 BLI_addtail(nurblist, nu);
790                         }
791                         /* --- done with nurbs --- */
792                 }
793         }
794 }
795
796 void BKE_mesh_to_curve(Depsgraph *depsgraph, Scene *scene, Object *ob)
797 {
798         /* make new mesh data from the original copy */
799         DerivedMesh *dm = mesh_get_derived_final(depsgraph, scene, ob, CD_MASK_MESH);
800         ListBase nurblist = {NULL, NULL};
801         bool needsFree = false;
802
803         BKE_mesh_to_curve_nurblist(dm, &nurblist, 0);
804         BKE_mesh_to_curve_nurblist(dm, &nurblist, 1);
805
806         if (nurblist.first) {
807                 Curve *cu = BKE_curve_add(G.main, ob->id.name + 2, OB_CURVE);
808                 cu->flag |= CU_3D;
809
810                 cu->nurb = nurblist;
811
812                 id_us_min(&((Mesh *)ob->data)->id);
813                 ob->data = cu;
814                 ob->type = OB_CURVE;
815
816                 /* curve objects can't contain DM in usual cases, we could free memory */
817                 needsFree = true;
818         }
819
820         dm->needsFree = needsFree;
821         dm->release(dm);
822
823         if (needsFree) {
824                 ob->derivedFinal = NULL;
825
826                 /* curve object could have got bounding box only in special cases */
827                 if (ob->bb) {
828                         MEM_freeN(ob->bb);
829                         ob->bb = NULL;
830                 }
831         }
832 }
833
834 /* settings: 1 - preview, 2 - render */
835 Mesh *BKE_mesh_new_from_object(
836         Depsgraph *depsgraph, Main *bmain, Scene *sce, Object *ob,
837         const bool apply_modifiers, const bool calc_tessface, const bool calc_undeformed)
838 {
839         Mesh *tmpmesh;
840         Curve *tmpcu = NULL, *copycu;
841         int i;
842         const bool render = (DEG_get_mode(depsgraph) == DAG_EVAL_RENDER);
843         const bool cage = !apply_modifiers;
844         bool do_mat_id_data_us = true;
845
846         /* perform the mesh extraction based on type */
847         switch (ob->type) {
848                 case OB_FONT:
849                 case OB_CURVE:
850                 case OB_SURF:
851                 {
852                         ListBase dispbase = {NULL, NULL};
853                         DerivedMesh *derivedFinal = NULL;
854                         int uv_from_orco;
855
856                         /* copies object and modifiers (but not the data) */
857                         Object *tmpobj;
858                         /* TODO: make it temp copy outside bmain! */
859                         BKE_id_copy_ex(bmain, &ob->id, (ID **)&tmpobj, LIB_ID_COPY_CACHES, false);
860                         tmpcu = (Curve *)tmpobj->data;
861                         id_us_min(&tmpcu->id);
862
863                         /* Copy cached display list, it might be needed by the stack evaluation.
864                          * Ideally stack should be able to use render-time display list, but doing
865                          * so is quite tricky and not safe so close to the release.
866                          *
867                          * TODO(sergey): Look into more proper solution.
868                          */
869                         if (ob->curve_cache != NULL) {
870                                 if (tmpobj->curve_cache == NULL) {
871                                         tmpobj->curve_cache = MEM_callocN(sizeof(CurveCache), "CurveCache for curve types");
872                                 }
873                                 BKE_displist_copy(&tmpobj->curve_cache->disp, &ob->curve_cache->disp);
874                         }
875
876                         /* if getting the original caged mesh, delete object modifiers */
877                         if (cage)
878                                 BKE_object_free_modifiers(tmpobj, 0);
879
880                         /* copies the data */
881                         copycu = tmpobj->data = BKE_curve_copy(bmain, (Curve *) ob->data);
882
883                         /* make sure texture space is calculated for a copy of curve,
884                          * it will be used for the final result.
885                          */
886                         BKE_curve_texspace_calc(copycu);
887
888                         /* temporarily set edit so we get updates from edit mode, but
889                          * also because for text datablocks copying it while in edit
890                          * mode gives invalid data structures */
891                         copycu->editfont = tmpcu->editfont;
892                         copycu->editnurb = tmpcu->editnurb;
893
894                         /* get updated display list, and convert to a mesh */
895                         BKE_displist_make_curveTypes_forRender(depsgraph, sce, tmpobj, &dispbase, &derivedFinal, false, render);
896
897                         copycu->editfont = NULL;
898                         copycu->editnurb = NULL;
899
900                         tmpobj->derivedFinal = derivedFinal;
901
902                         /* convert object type to mesh */
903                         uv_from_orco = (tmpcu->flag & CU_UV_ORCO) != 0;
904                         BKE_mesh_from_nurbs_displist(tmpobj, &dispbase, uv_from_orco, tmpcu->id.name + 2);
905
906                         tmpmesh = tmpobj->data;
907
908                         BKE_displist_free(&dispbase);
909
910                         /* BKE_mesh_from_nurbs changes the type to a mesh, check it worked.
911                          * if it didn't the curve did not have any segments or otherwise
912                          * would have generated an empty mesh */
913                         if (tmpobj->type != OB_MESH) {
914                                 BKE_libblock_free_us(bmain, tmpobj);
915                                 return NULL;
916                         }
917
918                         BKE_libblock_free_us(bmain, tmpobj);
919
920                         /* XXX The curve to mesh conversion is convoluted... But essentially, BKE_mesh_from_nurbs_displist()
921                          *     already transfers the ownership of materials from the temp copy of the Curve ID to the new
922                          *     Mesh ID, so we do not want to increase materials' usercount later. */
923                         do_mat_id_data_us = false;
924
925                         break;
926                 }
927
928                 case OB_MBALL:
929                 {
930                         /* metaballs don't have modifiers, so just convert to mesh */
931                         Object *basis_ob = BKE_mball_basis_find(sce, ob);
932                         /* todo, re-generatre for render-res */
933                         /* metaball_polygonize(scene, ob) */
934
935                         if (ob != basis_ob)
936                                 return NULL;  /* only do basis metaball */
937
938                         tmpmesh = BKE_mesh_add(bmain, ((ID *)ob->data)->name + 2);
939                         /* BKE_mesh_add gives us a user count we don't need */
940                         id_us_min(&tmpmesh->id);
941
942                         if (render) {
943                                 ListBase disp = {NULL, NULL};
944                                 BKE_displist_make_mball_forRender(depsgraph, sce, ob, &disp);
945                                 BKE_mesh_from_metaball(&disp, tmpmesh);
946                                 BKE_displist_free(&disp);
947                         }
948                         else {
949                                 ListBase disp = {NULL, NULL};
950                                 if (ob->curve_cache) {
951                                         disp = ob->curve_cache->disp;
952                                 }
953                                 BKE_mesh_from_metaball(&disp, tmpmesh);
954                         }
955
956                         BKE_mesh_texspace_copy_from_object(tmpmesh, ob);
957
958                         break;
959
960                 }
961                 case OB_MESH:
962                         /* copies object and modifiers (but not the data) */
963                         if (cage) {
964                                 /* copies the data */
965                                 tmpmesh = BKE_mesh_copy(bmain, ob->data);
966
967                                 /* XXX BKE_mesh_copy() already handles materials usercount. */
968                                 do_mat_id_data_us = false;
969                         }
970                         /* if not getting the original caged mesh, get final derived mesh */
971                         else {
972                                 /* Make a dummy mesh, saves copying */
973                                 DerivedMesh *dm;
974                                 /* CustomDataMask mask = CD_MASK_BAREMESH|CD_MASK_MTFACE|CD_MASK_MCOL; */
975                                 CustomDataMask mask = CD_MASK_MESH; /* this seems more suitable, exporter,
976                                                                      * for example, needs CD_MASK_MDEFORMVERT */
977
978                                 if (calc_undeformed)
979                                         mask |= CD_MASK_ORCO;
980
981                                 /* Write the display mesh into the dummy mesh */
982                                 if (render)
983                                         dm = mesh_create_derived_render(depsgraph, sce, ob, mask);
984                                 else
985                                         dm = mesh_create_derived_view(depsgraph, sce, ob, mask);
986
987                                 tmpmesh = BKE_mesh_add(bmain, ((ID *)ob->data)->name + 2);
988                                 DM_to_mesh(dm, tmpmesh, ob, mask, true);
989
990                                 /* Copy autosmooth settings from original mesh. */
991                                 Mesh *me = (Mesh *)ob->data;
992                                 tmpmesh->flag |= (me->flag & ME_AUTOSMOOTH);
993                                 tmpmesh->smoothresh = me->smoothresh;
994                         }
995
996                         /* BKE_mesh_add/copy gives us a user count we don't need */
997                         id_us_min(&tmpmesh->id);
998
999                         break;
1000                 default:
1001                         /* "Object does not have geometry data") */
1002                         return NULL;
1003         }
1004
1005         /* Copy materials to new mesh */
1006         switch (ob->type) {
1007                 case OB_SURF:
1008                 case OB_FONT:
1009                 case OB_CURVE:
1010                         tmpmesh->totcol = tmpcu->totcol;
1011
1012                         /* free old material list (if it exists) and adjust user counts */
1013                         if (tmpcu->mat) {
1014                                 for (i = tmpcu->totcol; i-- > 0; ) {
1015                                         /* are we an object material or data based? */
1016                                         tmpmesh->mat[i] = give_current_material(ob, i + 1);
1017
1018                                         if (((ob->matbits && ob->matbits[i]) || do_mat_id_data_us)  && tmpmesh->mat[i]) {
1019                                                 id_us_plus(&tmpmesh->mat[i]->id);
1020                                         }
1021                                 }
1022                         }
1023                         break;
1024
1025                 case OB_MBALL:
1026                 {
1027                         MetaBall *tmpmb = (MetaBall *)ob->data;
1028                         tmpmesh->mat = MEM_dupallocN(tmpmb->mat);
1029                         tmpmesh->totcol = tmpmb->totcol;
1030
1031                         /* free old material list (if it exists) and adjust user counts */
1032                         if (tmpmb->mat) {
1033                                 for (i = tmpmb->totcol; i-- > 0; ) {
1034                                         /* are we an object material or data based? */
1035                                         tmpmesh->mat[i] = give_current_material(ob, i + 1);
1036
1037                                         if (((ob->matbits && ob->matbits[i]) || do_mat_id_data_us) && tmpmesh->mat[i]) {
1038                                                 id_us_plus(&tmpmesh->mat[i]->id);
1039                                         }
1040                                 }
1041                         }
1042                         break;
1043                 }
1044
1045                 case OB_MESH:
1046                         if (!cage) {
1047                                 Mesh *origmesh = ob->data;
1048                                 tmpmesh->flag = origmesh->flag;
1049                                 tmpmesh->mat = MEM_dupallocN(origmesh->mat);
1050                                 tmpmesh->totcol = origmesh->totcol;
1051                                 tmpmesh->smoothresh = origmesh->smoothresh;
1052                                 if (origmesh->mat) {
1053                                         for (i = origmesh->totcol; i-- > 0; ) {
1054                                                 /* are we an object material or data based? */
1055                                                 tmpmesh->mat[i] = give_current_material(ob, i + 1);
1056
1057                                                 if (((ob->matbits && ob->matbits[i]) || do_mat_id_data_us)  && tmpmesh->mat[i]) {
1058                                                         id_us_plus(&tmpmesh->mat[i]->id);
1059                                                 }
1060                                         }
1061                                 }
1062                         }
1063                         break;
1064         } /* end copy materials */
1065
1066         if (calc_tessface) {
1067                 /* cycles and exporters rely on this still */
1068                 BKE_mesh_tessface_ensure(tmpmesh);
1069         }
1070
1071         return tmpmesh;
1072 }