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