svn merge -r41287:41310 ^/trunk/blender note, mirror modifier had slow, per vertex...
[blender.git] / source / blender / blenkernel / intern / mesh.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * Contributor(s): Blender Foundation
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/blenkernel/intern/mesh.c
27  *  \ingroup bke
28  */
29
30
31 #include <stdlib.h>
32 #include <string.h>
33 #include <stdio.h>
34 #include <math.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "DNA_scene_types.h"
39 #include "DNA_material_types.h"
40 #include "DNA_object_types.h"
41 #include "DNA_key_types.h"
42 #include "DNA_meshdata_types.h"
43 #include "DNA_ipo_types.h"
44 #include "DNA_customdata_types.h"
45
46 #include "BLI_utildefines.h"
47 #include "BLI_blenlib.h"
48 #include "BLI_bpath.h"
49 #include "BLI_editVert.h"
50 #include "BLI_math.h"
51 #include "BLI_edgehash.h"
52 #include "BLI_scanfill.h"
53
54 #include "BKE_animsys.h"
55 #include "BKE_main.h"
56 #include "BKE_customdata.h"
57 #include "BKE_DerivedMesh.h"
58 #include "BKE_global.h"
59 #include "BKE_mesh.h"
60 #include "BKE_displist.h"
61 #include "BKE_library.h"
62 #include "BKE_material.h"
63 #include "BKE_modifier.h"
64 #include "BKE_multires.h"
65 #include "BKE_key.h"
66 /* these 2 are only used by conversion functions */
67 #include "BKE_curve.h"
68 /* -- */
69 #include "BKE_object.h"
70 #include "BKE_tessmesh.h"
71 #include "BLI_edgehash.h"
72
73 #include "BLI_blenlib.h"
74 #include "BLI_editVert.h"
75 #include "BLI_math.h"
76 #include "BLI_cellalloc.h"
77 #include "BLI_array.h"
78 #include "BLI_edgehash.h"
79
80 #include "bmesh.h"
81
82 enum {
83         MESHCMP_DVERT_WEIGHTMISMATCH = 1,
84         MESHCMP_DVERT_GROUPMISMATCH,
85         MESHCMP_DVERT_TOTGROUPMISMATCH,
86         MESHCMP_LOOPCOLMISMATCH,
87         MESHCMP_LOOPUVMISMATCH,
88         MESHCMP_LOOPMISMATCH,
89         MESHCMP_POLYVERTMISMATCH,
90         MESHCMP_POLYMISMATCH,
91         MESHCMP_EDGEUNKNOWN,
92         MESHCMP_VERTCOMISMATCH,
93         MESHCMP_CDLAYERS_MISMATCH,
94 };
95
96 static const char *cmpcode_to_str(int code)
97 {
98         switch (code) {
99                 case MESHCMP_DVERT_WEIGHTMISMATCH:
100                         return "Vertex Weight Mismatch";
101                 case MESHCMP_DVERT_GROUPMISMATCH:
102                                         return "Vertex Group Mismatch";
103                 case MESHCMP_DVERT_TOTGROUPMISMATCH:
104                                         return "Vertex Doesn't Belong To Same Number Of Groups";
105                 case MESHCMP_LOOPCOLMISMATCH:
106                                         return "Vertex Color Mismatch";
107                 case MESHCMP_LOOPUVMISMATCH:
108                                         return "UV Mismatch";
109                 case MESHCMP_LOOPMISMATCH:
110                                         return "Loop Mismatch";
111                 case MESHCMP_POLYVERTMISMATCH:
112                                         return "Loop Vert Mismatch In Poly Test";
113                 case MESHCMP_POLYMISMATCH:
114                                         return "Loop Vert Mismatch";
115                 case MESHCMP_EDGEUNKNOWN:
116                                         return "Edge Mismatch";
117                 case MESHCMP_VERTCOMISMATCH:
118                                         return "Vertex Coordinate Mismatch";
119                 case MESHCMP_CDLAYERS_MISMATCH:
120                                         "CustomData Layer Count Mismatch";
121                 default:
122                                 return "Mesh Comparison Code Unknown";
123                 }
124 }
125
126 /*thresh is threshold for comparing vertices, uvs, vertex colors,
127   weights, etc.*/
128 static int customdata_compare(CustomData *c1, CustomData *c2, Mesh *m1, Mesh *m2, float thresh)
129 {
130         CustomDataLayer *l1, *l2;
131         int i, i1=0, i2=0, tot, j;
132         
133         for (i=0; i<c1->totlayer; i++) {
134                 if (ELEM7(c1->layers[i].type, CD_MVERT, CD_MEDGE, CD_MPOLY, 
135                                   CD_MLOOPUV, CD_MLOOPCOL, CD_MTEXPOLY, CD_MDEFORMVERT))                
136                         i1++;
137         }
138         
139         for (i=0; i<c2->totlayer; i++) {
140                 if (ELEM7(c2->layers[i].type, CD_MVERT, CD_MEDGE, CD_MPOLY, 
141                                   CD_MLOOPUV, CD_MLOOPCOL, CD_MTEXPOLY, CD_MDEFORMVERT))                
142                         i2++;
143         }
144         
145         if (i1 != i2)
146                 return MESHCMP_CDLAYERS_MISMATCH;
147         
148         l1 = c1->layers; l2 = c2->layers;
149         tot = i1;
150         i1 = 0; i2 = 0; 
151         for (i=0; i < tot; i++) {
152                 while (i1 < c1->totlayer && !ELEM7(l1->type, CD_MVERT, CD_MEDGE, CD_MPOLY, 
153                                   CD_MLOOPUV, CD_MLOOPCOL, CD_MTEXPOLY, CD_MDEFORMVERT))
154                         i1++, l1++;
155
156                 while (i2 < c2->totlayer && !ELEM7(l2->type, CD_MVERT, CD_MEDGE, CD_MPOLY, 
157                                   CD_MLOOPUV, CD_MLOOPCOL, CD_MTEXPOLY, CD_MDEFORMVERT))
158                         i2++, l2++;
159                 
160                 if (l1->type == CD_MVERT) {
161                         MVert *v1 = l1->data;
162                         MVert *v2 = l2->data;
163                         int vtot = m1->totvert;
164                         
165                         for (j=0; j<vtot; j++, v1++, v2++) {
166                                 if (len_v3v3(v1->co, v2->co) > thresh)
167                                         return MESHCMP_VERTCOMISMATCH;
168                                 /*I don't care about normals, let's just do coodinates*/
169                         }
170                 }
171                 
172                 /*we're order-agnostic for edges here*/
173                 if (l1->type == CD_MEDGE) {
174                         MEdge *e1 = l1->data;
175                         MEdge *e2 = l2->data;
176                         EdgeHash *eh = BLI_edgehash_new();
177                         int etot = m1->totedge;
178                 
179                         for (j=0; j<etot; j++, e1++) {
180                                 BLI_edgehash_insert(eh, e1->v1, e1->v2, e1);
181                         }
182                         
183                         for (j=0; j<etot; j++, e2++) {
184                                 if (!BLI_edgehash_lookup(eh, e2->v1, e2->v2))
185                                         return MESHCMP_EDGEUNKNOWN;
186                         }
187                         BLI_edgehash_free(eh, NULL);
188                 }
189                 
190                 if (l1->type == CD_MPOLY) {
191                         MPoly *p1 = l1->data;
192                         MPoly *p2 = l2->data;
193                         int ptot = m1->totpoly;
194                 
195                         for (j=0; j<ptot; j++, p1++, p2++) {
196                                 MLoop *lp1, *lp2;
197                                 int k;
198                                 
199                                 if (p1->totloop != p2->totloop)
200                                         return MESHCMP_POLYMISMATCH;
201                                 
202                                 lp1 = m1->mloop + p1->loopstart;
203                                 lp2 = m2->mloop + p2->loopstart;
204                                 
205                                 for (k=0; k<p1->totloop; k++, lp1++, lp2++) {
206                                         if (lp1->v != lp2->v)
207                                                 return MESHCMP_POLYVERTMISMATCH;
208                                 }
209                         }
210                 }
211                 if (l1->type == CD_MLOOP) {
212                         MLoop *lp1 = l1->data;
213                         MLoop *lp2 = l2->data;
214                         int ltot = m1->totloop;
215                 
216                         for (j=0; j<ltot; j++, lp1++, lp2++) {
217                                 if (lp1->v != lp2->v)
218                                         return MESHCMP_LOOPMISMATCH;
219                         }
220                 }
221                 if (l1->type == CD_MLOOPUV) {
222                         MLoopUV *lp1 = l1->data;
223                         MLoopUV *lp2 = l2->data;
224                         int ltot = m1->totloop;
225                 
226                         for (j=0; j<ltot; j++, lp1++, lp2++) {
227                                 if (len_v2v2(lp1->uv, lp2->uv) > thresh)
228                                         return MESHCMP_LOOPUVMISMATCH;
229                         }
230                 }
231                 
232                 if (l1->type == CD_MLOOPCOL) {
233                         MLoopCol *lp1 = l1->data;
234                         MLoopCol *lp2 = l2->data;
235                         int ltot = m1->totloop;
236                 
237                         for (j=0; j<ltot; j++, lp1++, lp2++) {
238                                 if (ABS(lp1->r - lp2->r) > thresh || 
239                                     ABS(lp1->g - lp2->g) > thresh || 
240                                     ABS(lp1->b - lp2->b) > thresh || 
241                                     ABS(lp1->a - lp2->a) > thresh)
242                                 {
243                                         return MESHCMP_LOOPCOLMISMATCH;
244                                 }
245                         }
246                 }
247
248                 if (l1->type == CD_MDEFORMVERT) {
249                         MDeformVert *dv1 = l1->data;
250                         MDeformVert *dv2 = l2->data;
251                         int dvtot = m1->totvert;
252                 
253                         for (j=0; j<dvtot; j++, dv1++, dv2++) {
254                                 int k;
255                                 MDeformWeight *dw1 = dv1->dw, *dw2=dv2->dw;
256                                 
257                                 if (dv1->totweight != dv2->totweight)
258                                         return MESHCMP_DVERT_TOTGROUPMISMATCH;
259                                 
260                                 for (k=0; k<dv1->totweight; k++, dw1++, dw2++) {
261                                         if (dw1->def_nr != dw2->def_nr)
262                                                 return MESHCMP_DVERT_GROUPMISMATCH;
263                                         if (ABS(dw1->weight - dw2->weight) > thresh)
264                                                 return MESHCMP_DVERT_WEIGHTMISMATCH;
265                                 }
266                         }
267                 }
268         }
269         
270         return 0;
271 }
272
273 /*used for testing.  returns an error string the two meshes don't match*/
274 const char *mesh_cmp(Mesh *me1, Mesh *me2, float thresh)
275 {
276         int c;
277         
278         if (!me1 || !me2)
279                 return "Requires two input meshes";
280         
281         if (me1->totvert != me2->totvert) 
282                 return "Number of verts don't match";
283         
284         if (me1->totedge != me2->totedge)
285                 return "Number of edges don't match";
286         
287         if (me1->totpoly != me2->totpoly)
288                 return "Number of faces don't match";
289                                 
290         if (me1->totloop !=me2->totloop)
291                 return "Number of loops don't match";
292         
293         if ((c = customdata_compare(&me1->vdata, &me2->vdata, me1, me2, thresh)))
294                 return cmpcode_to_str(c);
295
296         if ((c = customdata_compare(&me1->edata, &me2->edata, me1, me2, thresh)))
297                 return cmpcode_to_str(c);
298
299         if ((c = customdata_compare(&me1->ldata, &me2->ldata, me1, me2, thresh)))
300                 return cmpcode_to_str(c);
301
302         if ((c = customdata_compare(&me1->pdata, &me2->pdata, me1, me2, thresh)))
303                 return cmpcode_to_str(c);
304         
305         return NULL;
306 }
307
308 static void mesh_ensure_tesselation_customdata(Mesh *me)
309 {
310         int tottex, totcol;
311
312         tottex = CustomData_number_of_layers(&me->fdata, CD_MTFACE);
313         totcol = CustomData_number_of_layers(&me->fdata, CD_MCOL);
314         
315         if (tottex != CustomData_number_of_layers(&me->pdata, CD_MTEXPOLY) ||
316             totcol != CustomData_number_of_layers(&me->ldata, CD_MLOOPCOL))
317         {
318                 CustomData_free(&me->fdata, me->totface);
319                 
320                 me->mface = NULL;
321                 me->mtface = NULL;
322                 me->mcol = NULL;
323                 me->totface = 0;
324
325                 memset(&me->fdata, 0, sizeof(&me->fdata));
326
327                 CustomData_from_bmeshpoly(&me->fdata, &me->pdata, &me->ldata, me->totface);
328                 printf("Warning! Tesselation uvs or vcol data got out of sync, had to reset!\n");
329         }
330 }
331
332 /*this ensures grouped customdata (e.g. mtexpoly and mloopuv and mtface, or
333   mloopcol and mcol) have the same relative active/render/clone/mask indices.*/
334 static void mesh_update_linked_customdata(Mesh *me)
335 {
336         int act;
337
338         if (me->edit_btmesh)
339                 BMEdit_UpdateLinkedCustomData(me->edit_btmesh);
340
341         mesh_ensure_tesselation_customdata(me);
342
343         if (CustomData_has_layer(&me->pdata, CD_MTEXPOLY)) {
344                 act = CustomData_get_active_layer(&me->pdata, CD_MTEXPOLY);
345                 CustomData_set_layer_active(&me->ldata, CD_MLOOPUV, act);
346                 CustomData_set_layer_active(&me->fdata, CD_MTFACE, act);
347
348                 act = CustomData_get_render_layer(&me->pdata, CD_MTEXPOLY);
349                 CustomData_set_layer_render(&me->ldata, CD_MLOOPUV, act);
350                 CustomData_set_layer_render(&me->fdata, CD_MTFACE, act);
351
352                 act = CustomData_get_clone_layer(&me->pdata, CD_MTEXPOLY);
353                 CustomData_set_layer_clone(&me->ldata, CD_MLOOPUV, act);
354                 CustomData_set_layer_clone(&me->fdata, CD_MTFACE, act);
355
356                 act = CustomData_get_stencil_layer(&me->pdata, CD_MTEXPOLY);
357                 CustomData_set_layer_stencil(&me->ldata, CD_MLOOPUV, act);
358                 CustomData_set_layer_stencil(&me->fdata, CD_MTFACE, act);
359         }
360
361         if (CustomData_has_layer(&me->ldata, CD_MLOOPCOL)) {
362                 act = CustomData_get_active_layer(&me->ldata, CD_MLOOPCOL);
363                 CustomData_set_layer_active(&me->fdata, CD_MCOL, act);
364
365                 act = CustomData_get_render_layer(&me->ldata, CD_MLOOPCOL);
366                 CustomData_set_layer_render(&me->fdata, CD_MCOL, act);
367
368                 act = CustomData_get_clone_layer(&me->ldata, CD_MLOOPCOL);
369                 CustomData_set_layer_clone(&me->fdata, CD_MCOL, act);
370
371                 act = CustomData_get_stencil_layer(&me->ldata, CD_MLOOPCOL);
372                 CustomData_set_layer_stencil(&me->fdata, CD_MCOL, act);
373         }
374 }
375
376 void mesh_update_customdata_pointers(Mesh *me)
377 {
378         mesh_update_linked_customdata(me);
379
380         me->mvert = CustomData_get_layer(&me->vdata, CD_MVERT);
381         me->dvert = CustomData_get_layer(&me->vdata, CD_MDEFORMVERT);
382         me->msticky = CustomData_get_layer(&me->vdata, CD_MSTICKY);
383
384         me->medge = CustomData_get_layer(&me->edata, CD_MEDGE);
385
386         me->mface = CustomData_get_layer(&me->fdata, CD_MFACE);
387         me->mcol = CustomData_get_layer(&me->fdata, CD_MCOL);
388         me->mtface = CustomData_get_layer(&me->fdata, CD_MTFACE);
389         
390         me->mpoly = CustomData_get_layer(&me->pdata, CD_MPOLY);
391         me->mloop = CustomData_get_layer(&me->ldata, CD_MLOOP);
392
393         me->mtpoly = CustomData_get_layer(&me->pdata, CD_MTEXPOLY);
394         me->mloopcol = CustomData_get_layer(&me->ldata, CD_MLOOPCOL);
395         me->mloopuv = CustomData_get_layer(&me->ldata, CD_MLOOPUV);
396 }
397
398 /* Note: unlinking is called when me->id.us is 0, question remains how
399  * much unlinking of Library data in Mesh should be done... probably
400  * we need a more generic method, like the expand() functions in
401  * readfile.c */
402
403 void unlink_mesh(Mesh *me)
404 {
405         int a;
406         
407         if(me==NULL) return;
408         
409         for(a=0; a<me->totcol; a++) {
410                 if(me->mat[a]) me->mat[a]->id.us--;
411                 me->mat[a]= NULL;
412         }
413
414         if(me->key) {
415                    me->key->id.us--;
416                 if (me->key->id.us == 0 && me->key->ipo )
417                         me->key->ipo->id.us--;
418         }
419         me->key= NULL;
420         
421         if(me->texcomesh) me->texcomesh= NULL;
422 }
423
424
425 /* do not free mesh itself */
426 void free_mesh(Mesh *me, int unlink)
427 {
428         if (unlink)
429                 unlink_mesh(me);
430
431         if(me->pv) {
432                 if(me->pv->vert_map) MEM_freeN(me->pv->vert_map);
433                 if(me->pv->edge_map) MEM_freeN(me->pv->edge_map);
434                 if(me->pv->old_faces) MEM_freeN(me->pv->old_faces);
435                 if(me->pv->old_edges) MEM_freeN(me->pv->old_edges);
436                 me->totvert= me->pv->totvert;
437                 me->totedge= me->pv->totedge;
438                 me->totface= me->pv->totface;
439                 MEM_freeN(me->pv);
440         }
441
442         CustomData_free(&me->vdata, me->totvert);
443         CustomData_free(&me->edata, me->totedge);
444         CustomData_free(&me->fdata, me->totface);
445         CustomData_free(&me->ldata, me->totloop);
446         CustomData_free(&me->pdata, me->totpoly);
447
448         if(me->adt) {
449                 BKE_free_animdata(&me->id);
450                 me->adt= NULL;
451         }
452         
453         if(me->mat) MEM_freeN(me->mat);
454         
455         if(me->bb) MEM_freeN(me->bb);
456         if(me->mselect) MEM_freeN(me->mselect);
457         if(me->edit_btmesh) MEM_freeN(me->edit_btmesh);
458 }
459
460 void copy_dverts(MDeformVert *dst, MDeformVert *src, int copycount)
461 {
462         /* Assumes dst is already set up */
463         int i;
464
465         if (!src || !dst)
466                 return;
467
468         memcpy (dst, src, copycount * sizeof(MDeformVert));
469         
470         for (i=0; i<copycount; i++){
471                 if (src[i].dw){
472                         dst[i].dw = BLI_cellalloc_calloc (sizeof(MDeformWeight)*src[i].totweight, "copy_deformWeight");
473                         memcpy (dst[i].dw, src[i].dw, sizeof (MDeformWeight)*src[i].totweight);
474                 }
475         }
476
477 }
478
479 void free_dverts(MDeformVert *dvert, int totvert)
480 {
481         /* Instead of freeing the verts directly,
482         call this function to delete any special
483         vert data */
484         int     i;
485
486         if (!dvert)
487                 return;
488
489         /* Free any special data from the verts */
490         for (i=0; i<totvert; i++){
491                 if (dvert[i].dw) BLI_cellalloc_free (dvert[i].dw);
492         }
493         MEM_freeN (dvert);
494 }
495
496 Mesh *add_mesh(const char *name)
497 {
498         Mesh *me;
499         
500         me= alloc_libblock(&G.main->mesh, ID_ME, name);
501         
502         me->size[0]= me->size[1]= me->size[2]= 1.0;
503         me->smoothresh= 30;
504         me->texflag= AUTOSPACE;
505         me->flag= ME_TWOSIDED;
506         me->bb= unit_boundbox();
507         me->drawflag= ME_DRAWEDGES|ME_DRAWFACES|ME_DRAWCREASES;
508         
509         return me;
510 }
511
512 Mesh *copy_mesh(Mesh *me)
513 {
514         Mesh *men;
515         MTFace *tface;
516         MTexPoly *txface;
517         int a, i;
518         
519         men= copy_libblock(me);
520         
521         men->mat= MEM_dupallocN(me->mat);
522         for(a=0; a<men->totcol; a++) {
523                 id_us_plus((ID *)men->mat[a]);
524         }
525         id_us_plus((ID *)men->texcomesh);
526
527         CustomData_copy(&me->vdata, &men->vdata, CD_MASK_MESH, CD_DUPLICATE, men->totvert);
528         CustomData_copy(&me->edata, &men->edata, CD_MASK_MESH, CD_DUPLICATE, men->totedge);
529         CustomData_copy(&me->fdata, &men->fdata, CD_MASK_MESH, CD_DUPLICATE, men->totface);
530         CustomData_copy(&me->ldata, &men->ldata, CD_MASK_MESH, CD_DUPLICATE, men->totloop);
531         CustomData_copy(&me->pdata, &men->pdata, CD_MASK_MESH, CD_DUPLICATE, men->totpoly);
532         mesh_update_customdata_pointers(men);
533
534         /* ensure indirect linked data becomes lib-extern */
535         for(i=0; i<me->fdata.totlayer; i++) {
536                 if(me->fdata.layers[i].type == CD_MTFACE) {
537                         tface= (MTFace*)me->fdata.layers[i].data;
538
539                         for(a=0; a<me->totface; a++, tface++)
540                                 if(tface->tpage)
541                                         id_lib_extern((ID*)tface->tpage);
542                 }
543         }
544
545         for(i=0; i<me->pdata.totlayer; i++) {
546                 if(me->pdata.layers[i].type == CD_MTEXPOLY) {
547                         txface= (MTexPoly*)me->pdata.layers[i].data;
548
549                         for(a=0; a<me->totpoly; a++, txface++)
550                                 if(txface->tpage)
551                                         id_lib_extern((ID*)txface->tpage);
552                 }
553         }
554
555         men->mselect= NULL;
556         men->edit_btmesh= NULL;
557         men->pv= NULL; /* looks like this is no-longer supported but NULL just incase */
558
559         men->bb= MEM_dupallocN(men->bb);
560         
561         men->key= copy_key(me->key);
562         if(men->key) men->key->from= (ID *)men;
563
564         return men;
565 }
566
567 BMesh *BKE_mesh_to_bmesh(Mesh *me, Object *ob)
568 {
569         BMesh *bm;
570         int allocsize[4] = {512,512,2048,512};
571
572         bm = BM_Make_Mesh(ob, allocsize);
573
574         BMO_CallOpf(bm, "mesh_to_bmesh mesh=%p object=%p set_shapekey=%i", me, ob, 1);
575
576         return bm;
577 }
578
579 static void expand_local_mesh(Mesh *me)
580 {
581         id_lib_extern((ID *)me->texcomesh);
582
583         if(me->mtface) {
584                 int a, i;
585
586                 for(i=0; i<me->pdata.totlayer; i++) {
587                         if(me->pdata.layers[i].type == CD_MTEXPOLY) {
588                                 MTexPoly *txface= (MTexPoly*)me->fdata.layers[i].data;
589
590                                 for(a=0; a<me->totpoly; a++, txface++) {
591                                         /* special case: ima always local immediately */
592                                         if(txface->tpage) {
593                                                 if(txface->tpage) {
594                                                         id_lib_extern((ID *)txface->tpage);
595                                                 }
596                                         }
597                                 }
598                         }
599                 }
600
601                 for(i=0; i<me->fdata.totlayer; i++) {
602                         if(me->fdata.layers[i].type == CD_MTFACE) {
603                                 MTFace *tface= (MTFace*)me->fdata.layers[i].data;
604
605                                 for(a=0; a<me->totface; a++, tface++) {
606                                         /* special case: ima always local immediately */
607                                         if(tface->tpage) {
608                                                 if(tface->tpage) {
609                                                         id_lib_extern((ID *)tface->tpage);
610                                                 }
611                                         }
612                                 }
613                         }
614                 }
615         }
616
617         if(me->mat) {
618                 extern_local_matarar(me->mat, me->totcol);
619         }
620 }
621
622 void make_local_mesh(Mesh *me)
623 {
624         Main *bmain= G.main;
625         Object *ob;
626         int local=0, lib=0;
627
628         /* - only lib users: do nothing
629          * - only local users: set flag
630          * - mixed: make copy
631          */
632
633         if(me->id.lib==NULL) return;
634         if(me->id.us==1) {
635                 me->id.lib= NULL;
636                 me->id.flag= LIB_LOCAL;
637
638                 new_id(&bmain->mesh, (ID *)me, NULL);
639                 expand_local_mesh(me);
640                 return;
641         }
642
643         for(ob= bmain->object.first; ob && ELEM(0, lib, local); ob= ob->id.next) {
644                 if(me == ob->data) {
645                         if(ob->id.lib) lib= 1;
646                         else local= 1;
647                 }
648         }
649
650         if(local && lib==0) {
651                 me->id.lib= NULL;
652                 me->id.flag= LIB_LOCAL;
653
654                 new_id(&bmain->mesh, (ID *)me, NULL);
655                 expand_local_mesh(me);
656         }
657         else if(local && lib) {
658                 Mesh *men= copy_mesh(me);
659                 men->id.us= 0;
660
661                 for(ob= bmain->object.first; ob; ob= ob->id.next) {
662                         if(me == ob->data) {
663                                 if(ob->id.lib==NULL) {
664                                         set_mesh(ob, men);
665                                 }
666                         }
667                 }
668         }
669 }
670
671 void boundbox_mesh(Mesh *me, float *loc, float *size)
672 {
673         BoundBox *bb;
674         float min[3], max[3];
675         float mloc[3], msize[3];
676         
677         if(me->bb==NULL) me->bb= MEM_callocN(sizeof(BoundBox), "boundbox");
678         bb= me->bb;
679
680         if (!loc) loc= mloc;
681         if (!size) size= msize;
682         
683         INIT_MINMAX(min, max);
684         if(!minmax_mesh(me, min, max)) {
685                 min[0] = min[1] = min[2] = -1.0f;
686                 max[0] = max[1] = max[2] = 1.0f;
687         }
688
689         mid_v3_v3v3(loc, min, max);
690                 
691         size[0]= (max[0]-min[0])/2.0f;
692         size[1]= (max[1]-min[1])/2.0f;
693         size[2]= (max[2]-min[2])/2.0f;
694         
695         boundbox_set_from_min_max(bb, min, max);
696 }
697
698 void tex_space_mesh(Mesh *me)
699 {
700         float loc[3], size[3];
701         int a;
702
703         boundbox_mesh(me, loc, size);
704
705         if(me->texflag & AUTOSPACE) {
706                 for (a=0; a<3; a++) {
707                         if(size[a]==0.0f) size[a]= 1.0f;
708                         else if(size[a]>0.0f && size[a]<0.00001f) size[a]= 0.00001f;
709                         else if(size[a]<0.0f && size[a]> -0.00001f) size[a]= -0.00001f;
710                 }
711
712                 copy_v3_v3(me->loc, loc);
713                 copy_v3_v3(me->size, size);
714                 zero_v3(me->rot);
715         }
716 }
717
718 BoundBox *mesh_get_bb(Object *ob)
719 {
720         Mesh *me= ob->data;
721
722         if(ob->bb)
723                 return ob->bb;
724
725         if (!me->bb)
726                 tex_space_mesh(me);
727
728         return me->bb;
729 }
730
731 void mesh_get_texspace(Mesh *me, float *loc_r, float *rot_r, float *size_r)
732 {
733         if (!me->bb) {
734                 tex_space_mesh(me);
735         }
736
737         if (loc_r) VECCOPY(loc_r, me->loc);
738         if (rot_r) VECCOPY(rot_r, me->rot);
739         if (size_r) VECCOPY(size_r, me->size);
740 }
741
742 float *get_mesh_orco_verts(Object *ob)
743 {
744         Mesh *me = ob->data;
745         MVert *mvert = NULL;
746         Mesh *tme = me->texcomesh?me->texcomesh:me;
747         int a, totvert;
748         float (*vcos)[3] = NULL;
749
750         /* Get appropriate vertex coordinates */
751         vcos = MEM_callocN(sizeof(*vcos)*me->totvert, "orco mesh");
752         mvert = tme->mvert;
753         totvert = MIN2(tme->totvert, me->totvert);
754
755         for(a=0; a<totvert; a++, mvert++) {
756                 copy_v3_v3(vcos[a], mvert->co);
757         }
758
759         return (float*)vcos;
760 }
761
762 void transform_mesh_orco_verts(Mesh *me, float (*orco)[3], int totvert, int invert)
763 {
764         float loc[3], size[3];
765         int a;
766
767         mesh_get_texspace(me->texcomesh?me->texcomesh:me, loc, NULL, size);
768
769         if(invert) {
770                 for(a=0; a<totvert; a++) {
771                         float *co = orco[a];
772                         madd_v3_v3v3v3(co, loc, co, size);
773                 }
774         }
775         else {
776                 for(a=0; a<totvert; a++) {
777                         float *co = orco[a];
778                         co[0] = (co[0]-loc[0])/size[0];
779                         co[1] = (co[1]-loc[1])/size[1];
780                         co[2] = (co[2]-loc[2])/size[2];
781                 }
782         }
783 }
784
785 /* rotates the vertices of a face in case v[2] or v[3] (vertex index) is = 0.
786    this is necessary to make the if(mface->v4) check for quads work */
787 int test_index_face(MFace *mface, CustomData *fdata, int mfindex, int nr)
788 {
789         /* first test if the face is legal */
790         if((mface->v3 || nr==4) && mface->v3==mface->v4) {
791                 mface->v4= 0;
792                 nr--;
793         }
794         if((mface->v2 || mface->v4) && mface->v2==mface->v3) {
795                 mface->v3= mface->v4;
796                 mface->v4= 0;
797                 nr--;
798         }
799         if(mface->v1==mface->v2) {
800                 mface->v2= mface->v3;
801                 mface->v3= mface->v4;
802                 mface->v4= 0;
803                 nr--;
804         }
805
806         /* check corrupt cases, bowtie geometry, cant handle these because edge data wont exist so just return 0 */
807         if(nr==3) {
808                 if(
809                 /* real edges */
810                         mface->v1==mface->v2 ||
811                         mface->v2==mface->v3 ||
812                         mface->v3==mface->v1
813                 ) {
814                         return 0;
815                 }
816         }
817         else if(nr==4) {
818                 if(
819                 /* real edges */
820                         mface->v1==mface->v2 ||
821                         mface->v2==mface->v3 ||
822                         mface->v3==mface->v4 ||
823                         mface->v4==mface->v1 ||
824                 /* across the face */
825                         mface->v1==mface->v3 ||
826                         mface->v2==mface->v4
827                 ) {
828                         return 0;
829                 }
830         }
831
832         /* prevent a zero at wrong index location */
833         if(nr==3) {
834                 if(mface->v3==0) {
835                         static int corner_indices[4] = {1, 2, 0, 3};
836
837                         SWAP(int, mface->v1, mface->v2);
838                         SWAP(int, mface->v2, mface->v3);
839
840                         if(fdata)
841                                 CustomData_swap(fdata, mfindex, corner_indices);
842                 }
843         }
844         else if(nr==4) {
845                 if(mface->v3==0 || mface->v4==0) {
846                         static int corner_indices[4] = {2, 3, 0, 1};
847
848                         SWAP(int, mface->v1, mface->v3);
849                         SWAP(int, mface->v2, mface->v4);
850
851                         if(fdata)
852                                 CustomData_swap(fdata, mfindex, corner_indices);
853                 }
854         }
855
856         return nr;
857 }
858
859 Mesh *get_mesh(Object *ob)
860 {
861         
862         if(ob==NULL) return NULL;
863         if(ob->type==OB_MESH) return ob->data;
864         else return NULL;
865 }
866
867 void set_mesh(Object *ob, Mesh *me)
868 {
869         Mesh *old=NULL;
870
871         multires_force_update(ob);
872         
873         if(ob==NULL) return;
874         
875         if(ob->type==OB_MESH) {
876                 old= ob->data;
877                 if (old)
878                         old->id.us--;
879                 ob->data= me;
880                 id_us_plus((ID *)me);
881         }
882         
883         test_object_materials((ID *)me);
884
885         test_object_modifiers(ob);
886 }
887
888 /* ************** make edges in a Mesh, for outside of editmode */
889
890 struct edgesort {
891         int v1, v2;
892         short is_loose, is_draw;
893 };
894
895 /* edges have to be added with lowest index first for sorting */
896 static void to_edgesort(struct edgesort *ed, int v1, int v2, short is_loose, short is_draw)
897 {
898         if(v1<v2) {
899                 ed->v1= v1; ed->v2= v2;
900         }
901         else {
902                 ed->v1= v2; ed->v2= v1;
903         }
904         ed->is_loose= is_loose;
905         ed->is_draw= is_draw;
906 }
907
908 static int vergedgesort(const void *v1, const void *v2)
909 {
910         const struct edgesort *x1=v1, *x2=v2;
911
912         if( x1->v1 > x2->v1) return 1;
913         else if( x1->v1 < x2->v1) return -1;
914         else if( x1->v2 > x2->v2) return 1;
915         else if( x1->v2 < x2->v2) return -1;
916         
917         return 0;
918 }
919
920 static void mfaces_strip_loose(MFace *mface, int *totface)
921 {
922         int a,b;
923
924         for (a=b=0; a<*totface; a++) {
925                 if (mface[a].v3) {
926                         if (a!=b) {
927                                 memcpy(&mface[b],&mface[a],sizeof(mface[b]));
928                         }
929                         b++;
930                 }
931         }
932
933         *totface= b;
934 }
935
936 /* Create edges based on known verts and faces */
937 static void make_edges_mdata(MVert *UNUSED(allvert), MFace *allface, MLoop *allloop,
938         MPoly *allpoly, int UNUSED(totvert), int totface, int UNUSED(totloop), int totpoly,
939         int old, MEdge **alledge, int *_totedge)
940 {
941         MPoly *mpoly;
942         MLoop *mloop;
943         MFace *mface;
944         MEdge *medge;
945         EdgeHash *hash = BLI_edgehash_new();
946         struct edgesort *edsort, *ed;
947         int a, b, totedge=0, final=0;
948
949         /* we put all edges in array, sort them, and detect doubles that way */
950
951         for(a= totface, mface= allface; a>0; a--, mface++) {
952                 if(mface->v4) totedge+=4;
953                 else if(mface->v3) totedge+=3;
954                 else totedge+=1;
955         }
956
957         if(totedge==0) {
958                 /* flag that mesh has edges */
959                 (*alledge)= MEM_callocN(0, "make mesh edges");
960                 (*_totedge) = 0;
961                 return;
962         }
963
964         ed= edsort= MEM_mallocN(totedge*sizeof(struct edgesort), "edgesort");
965
966         for(a= totface, mface= allface; a>0; a--, mface++) {
967                 to_edgesort(ed++, mface->v1, mface->v2, !mface->v3, mface->edcode & ME_V1V2);
968                 if(mface->v4) {
969                         to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
970                         to_edgesort(ed++, mface->v3, mface->v4, 0, mface->edcode & ME_V3V4);
971                         to_edgesort(ed++, mface->v4, mface->v1, 0, mface->edcode & ME_V4V1);
972                 }
973                 else if(mface->v3) {
974                         to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
975                         to_edgesort(ed++, mface->v3, mface->v1, 0, mface->edcode & ME_V3V1);
976                 }
977         }
978
979         qsort(edsort, totedge, sizeof(struct edgesort), vergedgesort);
980
981         /* count final amount */
982         for(a=totedge, ed=edsort; a>1; a--, ed++) {
983                 /* edge is unique when it differs from next edge, or is last */
984                 if(ed->v1 != (ed+1)->v1 || ed->v2 != (ed+1)->v2) final++;
985         }
986         final++;
987
988         (*alledge)= medge= MEM_callocN(sizeof (MEdge) * final, "make_edges mdge");
989         (*_totedge)= final;
990
991         for(a=totedge, ed=edsort; a>1; a--, ed++) {
992                 /* edge is unique when it differs from next edge, or is last */
993                 if(ed->v1 != (ed+1)->v1 || ed->v2 != (ed+1)->v2) {
994                         medge->v1= ed->v1;
995                         medge->v2= ed->v2;
996                         if(old==0 || ed->is_draw) medge->flag= ME_EDGEDRAW|ME_EDGERENDER;
997                         if(ed->is_loose) medge->flag|= ME_LOOSEEDGE;
998
999                         /* order is swapped so extruding this edge as a surface wont flip face normals
1000                          * with cyclic curves */
1001                         if(ed->v1+1 != ed->v2) {
1002                                 SWAP(int, medge->v1, medge->v2);
1003                         }
1004                         medge++;
1005                 }
1006                 else {
1007                         /* equal edge, we merge the drawflag */
1008                         (ed+1)->is_draw |= ed->is_draw;
1009                 }
1010         }
1011         /* last edge */
1012         medge->v1= ed->v1;
1013         medge->v2= ed->v2;
1014         medge->flag= ME_EDGEDRAW;
1015         if(ed->is_loose) medge->flag|= ME_LOOSEEDGE;
1016         medge->flag |= ME_EDGERENDER;
1017
1018         MEM_freeN(edsort);
1019         
1020         /*set edge members of mloops*/
1021         medge= *alledge;
1022         for (a=0; a<*_totedge; a++, medge++) {
1023                 BLI_edgehash_insert(hash, medge->v1, medge->v2, SET_INT_IN_POINTER(a));
1024         }
1025         
1026         mpoly = allpoly;
1027         for (a=0; a<totpoly; a++, mpoly++) {
1028                 mloop = allloop + mpoly->loopstart;
1029                 for (b=0; b<mpoly->totloop; b++) {
1030                         int v1, v2;
1031                         
1032                         v1 = mloop[b].v;
1033                         v2 = mloop[(b+1)%mpoly->totloop].v;
1034                         mloop[b].e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(hash, v1, v2));
1035                 }
1036         }
1037         
1038         BLI_edgehash_free(hash, NULL);
1039 }
1040
1041 void make_edges(Mesh *me, int old)
1042 {
1043         MEdge *medge;
1044         int totedge=0;
1045
1046         make_edges_mdata(me->mvert, me->mface, me->mloop, me->mpoly, me->totvert, me->totface, me->totloop, me->totpoly, old, &medge, &totedge);
1047         if(totedge==0) {
1048                 /* flag that mesh has edges */
1049                 me->medge = medge;
1050                 me->totedge = 0;
1051                 return;
1052         }
1053
1054         medge= CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, medge, totedge);
1055         me->medge= medge;
1056         me->totedge= totedge;
1057
1058         mesh_strip_loose_faces(me);
1059 }
1060
1061 void mesh_strip_loose_faces(Mesh *me)
1062 {
1063         int a,b;
1064
1065         for (a=b=0; a<me->totface; a++) {
1066                 if (me->mface[a].v3) {
1067                         if (a!=b) {
1068                                 memcpy(&me->mface[b],&me->mface[a],sizeof(me->mface[b]));
1069                                 CustomData_copy_data(&me->fdata, &me->fdata, a, b, 1);
1070                                 CustomData_free_elem(&me->fdata, a, 1);
1071                         }
1072                         b++;
1073                 }
1074         }
1075         me->totface = b;
1076 }
1077
1078 void mesh_strip_loose_edges(Mesh *me)
1079 {
1080         int a,b;
1081
1082         for (a=b=0; a<me->totedge; a++) {
1083                 if (me->medge[a].v1!=me->medge[a].v2) {
1084                         if (a!=b) {
1085                                 memcpy(&me->medge[b],&me->medge[a],sizeof(me->medge[b]));
1086                                 CustomData_copy_data(&me->edata, &me->edata, a, b, 1);
1087                                 CustomData_free_elem(&me->edata, a, 1);
1088                         }
1089                         b++;
1090                 }
1091         }
1092         me->totedge = b;
1093 }
1094
1095 void mball_to_mesh(ListBase *lb, Mesh *me)
1096 {
1097         DispList *dl;
1098         MVert *mvert;
1099         MFace *mface;
1100         float *nors, *verts;
1101         int a, *index;
1102         
1103         dl= lb->first;
1104         if(dl==NULL) return;
1105
1106         if(dl->type==DL_INDEX4) {
1107                 me->totvert= dl->nr;
1108                 me->totface= dl->parts;
1109                 
1110                 mvert= CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, dl->nr);
1111                 mface= CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, dl->parts);
1112                 me->mvert= mvert;
1113                 me->mface= mface;
1114
1115                 a= dl->nr;
1116                 nors= dl->nors;
1117                 verts= dl->verts;
1118                 while(a--) {
1119                         VECCOPY(mvert->co, verts);
1120                         normal_float_to_short_v3(mvert->no, nors);
1121                         mvert++;
1122                         nors+= 3;
1123                         verts+= 3;
1124                 }
1125                 
1126                 a= dl->parts;
1127                 index= dl->index;
1128                 while(a--) {
1129                         mface->v1= index[0];
1130                         mface->v2= index[1];
1131                         mface->v3= index[2];
1132                         mface->v4= index[3];
1133                         mface->flag= ME_SMOOTH;
1134
1135                         test_index_face(mface, NULL, 0, (mface->v3==mface->v4)? 3: 4);
1136
1137                         mface++;
1138                         index+= 4;
1139                 }
1140
1141                 make_edges(me, 0);      // all edges
1142                 convert_mfaces_to_mpolys(me);
1143         }
1144 }
1145
1146 /* Initialize mverts, medges and, faces for converting nurbs to mesh and derived mesh */
1147 /* return non-zero on error */
1148 int nurbs_to_mdata(Object *ob, MVert **allvert, int *totvert,
1149         MEdge **alledge, int *totedge, MFace **allface, MLoop **allloop, MPoly **allpoly, 
1150         int *totface, int *totloop, int *totpoly)
1151 {
1152         return nurbs_to_mdata_customdb(ob, &ob->disp,
1153                 allvert, totvert, alledge, totedge, allface, allloop, allpoly, totface, totloop, totpoly);
1154 }
1155
1156 /* Initialize mverts, medges and, faces for converting nurbs to mesh and derived mesh */
1157 /* use specified dispbase  */
1158 int nurbs_to_mdata_customdb(Object *ob, ListBase *dispbase, MVert **allvert, int *_totvert,
1159         MEdge **alledge, int *_totedge, MFace **allface, MLoop **allloop, MPoly **allpoly, 
1160         int *_totface, int *_totloop, int *_totpoly)
1161 {
1162         DispList *dl;
1163         Curve *cu;
1164         MVert *mvert;
1165         MFace *mface;
1166         MPoly *mpoly;
1167         MLoop *mloop;
1168         float *data;
1169         int a, b, ofs, vertcount, startvert, totvert=0, totvlak=0;
1170         int p1, p2, p3, p4, *index;
1171         int conv_polys= 0;
1172         int i, j;
1173
1174         cu= ob->data;
1175
1176         conv_polys|= cu->flag & CU_3D;          /* 2d polys are filled with DL_INDEX3 displists */
1177         conv_polys|= ob->type == OB_SURF;       /* surf polys are never filled */
1178
1179         /* count */
1180         dl= dispbase->first;
1181         while(dl) {
1182                 if(dl->type==DL_SEGM) {
1183                         totvert+= dl->parts*dl->nr;
1184                         totvlak+= dl->parts*(dl->nr-1);
1185                 }
1186                 else if(dl->type==DL_POLY) {
1187                         if(conv_polys) {
1188                                 totvert+= dl->parts*dl->nr;
1189                                 totvlak+= dl->parts*dl->nr;
1190                         }
1191                 }
1192                 else if(dl->type==DL_SURF) {
1193                         totvert+= dl->parts*dl->nr;
1194                         totvlak+= (dl->parts-1+((dl->flag & DL_CYCL_V)==2))*(dl->nr-1+(dl->flag & DL_CYCL_U));
1195                 }
1196                 else if(dl->type==DL_INDEX3) {
1197                         totvert+= dl->nr;
1198                         totvlak+= dl->parts;
1199                 }
1200                 dl= dl->next;
1201         }
1202
1203         if(totvert==0) {
1204                 /* error("can't convert"); */
1205                 /* Make Sure you check ob->data is a curve */
1206                 return -1;
1207         }
1208
1209         *allvert= mvert= MEM_callocN(sizeof (MVert) * totvert, "nurbs_init mvert");
1210         *allface= mface= MEM_callocN(sizeof (MFace) * totvlak, "nurbs_init mface");
1211         *allloop = mloop = MEM_callocN(sizeof(MLoop) * totvlak * 4, "nurbs_init mloop");
1212         *allpoly = mpoly = MEM_callocN(sizeof(MPoly) * totvlak * 4, "nurbs_init mloop");
1213         
1214         /* verts and faces */
1215         vertcount= 0;
1216
1217         dl= dispbase->first;
1218         while(dl) {
1219                 int smooth= dl->rt & CU_SMOOTH ? 1 : 0;
1220
1221                 if(dl->type==DL_SEGM) {
1222                         startvert= vertcount;
1223                         a= dl->parts*dl->nr;
1224                         data= dl->verts;
1225                         while(a--) {
1226                                 VECCOPY(mvert->co, data);
1227                                 data+=3;
1228                                 vertcount++;
1229                                 mvert++;
1230                         }
1231
1232                         for(a=0; a<dl->parts; a++) {
1233                                 ofs= a*dl->nr;
1234                                 for(b=1; b<dl->nr; b++) {
1235                                         mface->v1= startvert+ofs+b-1;
1236                                         mface->v2= startvert+ofs+b;
1237                                         if(smooth) mface->flag |= ME_SMOOTH;
1238                                         mface++;
1239                                 }
1240                         }
1241
1242                 }
1243                 else if(dl->type==DL_POLY) {
1244                         if(conv_polys) {
1245                                 startvert= vertcount;
1246                                 a= dl->parts*dl->nr;
1247                                 data= dl->verts;
1248                                 while(a--) {
1249                                         VECCOPY(mvert->co, data);
1250                                         data+=3;
1251                                         vertcount++;
1252                                         mvert++;
1253                                 }
1254
1255                                 for(a=0; a<dl->parts; a++) {
1256                                         ofs= a*dl->nr;
1257                                         for(b=0; b<dl->nr; b++) {
1258                                                 mface->v1= startvert+ofs+b;
1259                                                 if(b==dl->nr-1) mface->v2= startvert+ofs;
1260                                                 else mface->v2= startvert+ofs+b+1;
1261                                                 if(smooth) mface->flag |= ME_SMOOTH;
1262                                                 mface++;
1263                                         }
1264                                 }
1265                         }
1266                 }
1267                 else if(dl->type==DL_INDEX3) {
1268                         startvert= vertcount;
1269                         a= dl->nr;
1270                         data= dl->verts;
1271                         while(a--) {
1272                                 VECCOPY(mvert->co, data);
1273                                 data+=3;
1274                                 vertcount++;
1275                                 mvert++;
1276                         }
1277
1278                         a= dl->parts;
1279                         index= dl->index;
1280                         while(a--) {
1281                                 mface->v1= startvert+index[0];
1282                                 mface->v2= startvert+index[2];
1283                                 mface->v3= startvert+index[1];
1284                                 mface->v4= 0;
1285                                 mface->mat_nr= dl->col;
1286                                 test_index_face(mface, NULL, 0, 3);
1287
1288                                 if(smooth) mface->flag |= ME_SMOOTH;
1289                                 mface++;
1290                                 index+= 3;
1291                         }
1292
1293
1294                 }
1295                 else if(dl->type==DL_SURF) {
1296                         startvert= vertcount;
1297                         a= dl->parts*dl->nr;
1298                         data= dl->verts;
1299                         while(a--) {
1300                                 VECCOPY(mvert->co, data);
1301                                 data+=3;
1302                                 vertcount++;
1303                                 mvert++;
1304                         }
1305
1306                         for(a=0; a<dl->parts; a++) {
1307
1308                                 if( (dl->flag & DL_CYCL_V)==0 && a==dl->parts-1) break;
1309
1310                                 if(dl->flag & DL_CYCL_U) {                      /* p2 -> p1 -> */
1311                                         p1= startvert+ dl->nr*a;        /* p4 -> p3 -> */
1312                                         p2= p1+ dl->nr-1;               /* -----> next row */
1313                                         p3= p1+ dl->nr;
1314                                         p4= p2+ dl->nr;
1315                                         b= 0;
1316                                 }
1317                                 else {
1318                                         p2= startvert+ dl->nr*a;
1319                                         p1= p2+1;
1320                                         p4= p2+ dl->nr;
1321                                         p3= p1+ dl->nr;
1322                                         b= 1;
1323                                 }
1324                                 if( (dl->flag & DL_CYCL_V) && a==dl->parts-1) {
1325                                         p3-= dl->parts*dl->nr;
1326                                         p4-= dl->parts*dl->nr;
1327                                 }
1328
1329                                 for(; b<dl->nr; b++) {
1330                                         mface->v1= p1;
1331                                         mface->v2= p3;
1332                                         mface->v3= p4;
1333                                         mface->v4= p2;
1334                                         mface->mat_nr= dl->col;
1335                                         test_index_face(mface, NULL, 0, 4);
1336
1337                                         if(smooth) mface->flag |= ME_SMOOTH;
1338                                         mface++;
1339
1340                                         p4= p3;
1341                                         p3++;
1342                                         p2= p1;
1343                                         p1++;
1344                                 }
1345                         }
1346
1347                 }
1348
1349                 dl= dl->next;
1350         }
1351         
1352         mface= *allface;
1353         j = 0;
1354         for (i=0; i<totvert; i++, mpoly++, mface++) {
1355                 int k;
1356                 
1357                 if (!mface->v3) {
1358                         mpoly--;
1359                         i--;
1360                         continue;
1361                 }
1362                 
1363                 if (mface >= *allface + totvlak)
1364                         break;
1365
1366                 mpoly->flag |= mface->flag & ME_SMOOTH;
1367                 mpoly->loopstart= j;
1368                 mpoly->totloop= mface->v4 ? 4 : 3;
1369                 for (k=0; k<mpoly->totloop; k++, mloop++, j++) {
1370                         mloop->v = (&mface->v1)[k];
1371                 }
1372         }
1373         
1374         *_totpoly= i;
1375         *_totloop= j;
1376         *_totvert= totvert;
1377         *_totface= totvlak;
1378
1379         make_edges_mdata(*allvert, *allface, *allloop, *allpoly, totvert, totvlak, *_totloop, *_totpoly, 0, alledge, _totedge);
1380         mfaces_strip_loose(*allface, _totface);
1381
1382         return 0;
1383 }
1384
1385 /* this may fail replacing ob->data, be sure to check ob->type */
1386 void nurbs_to_mesh(Object *ob)
1387 {
1388         Main *bmain= G.main;
1389         Object *ob1;
1390         DerivedMesh *dm= ob->derivedFinal;
1391         Mesh *me;
1392         Curve *cu;
1393         MVert *allvert= NULL;
1394         MEdge *alledge= NULL;
1395         MFace *allface= NULL;
1396         MLoop *allloop = NULL;
1397         MPoly *allpoly = NULL;
1398         int totvert, totedge, totface, totloop, totpoly;
1399
1400         cu= ob->data;
1401
1402         if (dm == NULL) {
1403                 if (nurbs_to_mdata (ob, &allvert, &totvert, &alledge, &totedge, &allface, &allloop, &allpoly, &totface, &totloop, &totpoly) != 0) {
1404                         /* Error initializing */
1405                         return;
1406                 }
1407
1408                 /* make mesh */
1409                 me= add_mesh("Mesh");
1410                 me->totvert= totvert;
1411                 me->totface= totface;
1412                 me->totedge= totedge;
1413                 me->totloop = totloop;
1414                 me->totpoly = totpoly;
1415
1416                 me->mvert= CustomData_add_layer(&me->vdata, CD_MVERT, CD_ASSIGN, allvert, me->totvert);
1417                 me->medge= CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, alledge, me->totedge);
1418                 me->mface= CustomData_add_layer(&me->fdata, CD_MFACE, CD_ASSIGN, allface, me->totface);
1419                 me->mloop= CustomData_add_layer(&me->ldata, CD_MLOOP, CD_ASSIGN, allloop, me->totloop);
1420                 me->mpoly= CustomData_add_layer(&me->pdata, CD_MPOLY, CD_ASSIGN, allpoly, me->totpoly);
1421
1422                 mesh_calc_normals(me->mvert, me->totvert, me->mloop, me->mpoly, me->totloop, me->totpoly, NULL, NULL, 0, NULL, NULL);
1423         } else {
1424                 me= add_mesh("Mesh");
1425                 DM_to_mesh(dm, me, ob);
1426         }
1427
1428         me->totcol= cu->totcol;
1429         me->mat= cu->mat;
1430
1431         tex_space_mesh(me);
1432
1433         cu->mat= NULL;
1434         cu->totcol= 0;
1435
1436         if(ob->data) {
1437                 free_libblock(&bmain->curve, ob->data);
1438         }
1439         ob->data= me;
1440         ob->type= OB_MESH;
1441
1442         /* other users */
1443         ob1= bmain->object.first;
1444         while(ob1) {
1445                 if(ob1->data==cu) {
1446                         ob1->type= OB_MESH;
1447                 
1448                         ob1->data= ob->data;
1449                         id_us_plus((ID *)ob->data);
1450                 }
1451                 ob1= ob1->id.next;
1452         }
1453 }
1454
1455 typedef struct EdgeLink {
1456         Link *next, *prev;
1457         void *edge;
1458 } EdgeLink;
1459
1460 typedef struct VertLink {
1461         Link *next, *prev;
1462         int index;
1463 } VertLink;
1464
1465 static void prependPolyLineVert(ListBase *lb, int index)
1466 {
1467         VertLink *vl= MEM_callocN(sizeof(VertLink), "VertLink");
1468         vl->index = index;
1469         BLI_addhead(lb, vl);
1470 }
1471
1472 static void appendPolyLineVert(ListBase *lb, int index)
1473 {
1474         VertLink *vl= MEM_callocN(sizeof(VertLink), "VertLink");
1475         vl->index = index;
1476         BLI_addtail(lb, vl);
1477 }
1478
1479 void mesh_to_curve(Scene *scene, Object *ob)
1480 {
1481         /* make new mesh data from the original copy */
1482         DerivedMesh *dm= mesh_get_derived_final(scene, ob, CD_MASK_MESH);
1483
1484         MVert *mverts= dm->getVertArray(dm);
1485         MEdge *med, *medge= dm->getEdgeArray(dm);
1486         MFace *mf,  *mface= dm->getTessFaceArray(dm);
1487
1488         int totedge = dm->getNumEdges(dm);
1489         int totface = dm->getNumTessFaces(dm);
1490         int totedges = 0;
1491         int i, needsFree = 0;
1492
1493         /* only to detect edge polylines */
1494         EdgeHash *eh = BLI_edgehash_new();
1495         EdgeHash *eh_edge = BLI_edgehash_new();
1496
1497
1498         ListBase edges = {NULL, NULL};
1499
1500         /* create edges from all faces (so as to find edges not in any faces) */
1501         mf= mface;
1502         for (i = 0; i < totface; i++, mf++) {
1503                 if (!BLI_edgehash_haskey(eh, mf->v1, mf->v2))
1504                         BLI_edgehash_insert(eh, mf->v1, mf->v2, NULL);
1505                 if (!BLI_edgehash_haskey(eh, mf->v2, mf->v3))
1506                         BLI_edgehash_insert(eh, mf->v2, mf->v3, NULL);
1507
1508                 if (mf->v4) {
1509                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v4))
1510                                 BLI_edgehash_insert(eh, mf->v3, mf->v4, NULL);
1511                         if (!BLI_edgehash_haskey(eh, mf->v4, mf->v1))
1512                                 BLI_edgehash_insert(eh, mf->v4, mf->v1, NULL);
1513                 } else {
1514                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v1))
1515                                 BLI_edgehash_insert(eh, mf->v3, mf->v1, NULL);
1516                 }
1517         }
1518
1519         med= medge;
1520         for(i=0; i<totedge; i++, med++) {
1521                 if (!BLI_edgehash_haskey(eh, med->v1, med->v2)) {
1522                         EdgeLink *edl= MEM_callocN(sizeof(EdgeLink), "EdgeLink");
1523
1524                         BLI_edgehash_insert(eh_edge, med->v1, med->v2, NULL);
1525                         edl->edge= med;
1526
1527                         BLI_addtail(&edges, edl);       totedges++;
1528                 }
1529         }
1530         BLI_edgehash_free(eh_edge, NULL);
1531         BLI_edgehash_free(eh, NULL);
1532
1533         if(edges.first) {
1534                 Curve *cu = add_curve(ob->id.name+2, OB_CURVE);
1535                 cu->flag |= CU_3D;
1536
1537                 while(edges.first) {
1538                         /* each iteration find a polyline and add this as a nurbs poly spline */
1539
1540                         ListBase polyline = {NULL, NULL}; /* store a list of VertLink's */
1541                         int closed = FALSE;
1542                         int totpoly= 0;
1543                         MEdge *med_current= ((EdgeLink *)edges.last)->edge;
1544                         int startVert= med_current->v1;
1545                         int endVert= med_current->v2;
1546                         int ok= TRUE;
1547
1548                         appendPolyLineVert(&polyline, startVert);       totpoly++;
1549                         appendPolyLineVert(&polyline, endVert);         totpoly++;
1550                         BLI_freelinkN(&edges, edges.last);                      totedges--;
1551
1552                         while(ok) { /* while connected edges are found... */
1553                                 ok = FALSE;
1554                                 i= totedges;
1555                                 while(i) {
1556                                         EdgeLink *edl;
1557
1558                                         i-=1;
1559                                         edl= BLI_findlink(&edges, i);
1560                                         med= edl->edge;
1561
1562                                         if(med->v1==endVert) {
1563                                                 endVert = med->v2;
1564                                                 appendPolyLineVert(&polyline, med->v2); totpoly++;
1565                                                 BLI_freelinkN(&edges, edl);                             totedges--;
1566                                                 ok= TRUE;
1567                                         }
1568                                         else if(med->v2==endVert) {
1569                                                 endVert = med->v1;
1570                                                 appendPolyLineVert(&polyline, endVert); totpoly++;
1571                                                 BLI_freelinkN(&edges, edl);                             totedges--;
1572                                                 ok= TRUE;
1573                                         }
1574                                         else if(med->v1==startVert) {
1575                                                 startVert = med->v2;
1576                                                 prependPolyLineVert(&polyline, startVert);      totpoly++;
1577                                                 BLI_freelinkN(&edges, edl);                                     totedges--;
1578                                                 ok= TRUE;
1579                                         }
1580                                         else if(med->v2==startVert) {
1581                                                 startVert = med->v1;
1582                                                 prependPolyLineVert(&polyline, startVert);      totpoly++;
1583                                                 BLI_freelinkN(&edges, edl);                                     totedges--;
1584                                                 ok= TRUE;
1585                                         }
1586                                 }
1587                         }
1588
1589                         /* Now we have a polyline, make into a curve */
1590                         if(startVert==endVert) {
1591                                 BLI_freelinkN(&polyline, polyline.last);
1592                                 totpoly--;
1593                                 closed = TRUE;
1594                         }
1595
1596                         /* --- nurbs --- */
1597                         {
1598                                 Nurb *nu;
1599                                 BPoint *bp;
1600                                 VertLink *vl;
1601
1602                                 /* create new 'nurb' within the curve */
1603                                 nu = (Nurb *)MEM_callocN(sizeof(Nurb), "MeshNurb");
1604
1605                                 nu->pntsu= totpoly;
1606                                 nu->pntsv= 1;
1607                                 nu->orderu= 4;
1608                                 nu->flagu= CU_NURB_ENDPOINT | (closed ? CU_NURB_CYCLIC:0);      /* endpoint */
1609                                 nu->resolu= 12;
1610
1611                                 nu->bp= (BPoint *)MEM_callocN(sizeof(BPoint)*totpoly, "bpoints");
1612
1613                                 /* add points */
1614                                 vl= polyline.first;
1615                                 for (i=0, bp=nu->bp; i < totpoly; i++, bp++, vl=(VertLink *)vl->next) {
1616                                         copy_v3_v3(bp->vec, mverts[vl->index].co);
1617                                         bp->f1= SELECT;
1618                                         bp->radius = bp->weight = 1.0;
1619                                 }
1620                                 BLI_freelistN(&polyline);
1621
1622                                 /* add nurb to curve */
1623                                 BLI_addtail(&cu->nurb, nu);
1624                         }
1625                         /* --- done with nurbs --- */
1626                 }
1627
1628                 ((Mesh *)ob->data)->id.us--;
1629                 ob->data= cu;
1630                 ob->type= OB_CURVE;
1631
1632                 /* curve objects can't contain DM in usual cases, we could free memory */
1633                 needsFree= 1;
1634         }
1635
1636         dm->needsFree = needsFree;
1637         dm->release(dm);
1638
1639         if (needsFree) {
1640                 ob->derivedFinal = NULL;
1641
1642                 /* curve object could have got bounding box only in special cases */
1643                 if(ob->bb) {
1644                         MEM_freeN(ob->bb);
1645                         ob->bb= NULL;
1646                 }
1647         }
1648 }
1649
1650 void mesh_delete_material_index(Mesh *me, short index)
1651 {
1652         int i;
1653
1654         for (i=0; i<me->totpoly; i++) {
1655                 MPoly *mp = &((MPoly*) me->mpoly)[i];
1656                 if (mp->mat_nr && mp->mat_nr>=index) 
1657                         mp->mat_nr--;
1658         }
1659         
1660         for (i=0; i<me->totface; i++) {
1661                 MFace *mf = &((MFace*) me->mface)[i];
1662                 if (mf->mat_nr && mf->mat_nr>=index) 
1663                         mf->mat_nr--;
1664         }
1665 }
1666
1667 void mesh_set_smooth_flag(Object *meshOb, int enableSmooth) 
1668 {
1669         Mesh *me = meshOb->data;
1670         int i;
1671
1672         for (i=0; i<me->totpoly; i++) {
1673                 MPoly *mp = &((MPoly*) me->mpoly)[i];
1674
1675                 if (enableSmooth) {
1676                         mp->flag |= ME_SMOOTH;
1677                 } else {
1678                         mp->flag &= ~ME_SMOOTH;
1679                 }
1680         }
1681         
1682         for (i=0; i<me->totface; i++) {
1683                 MFace *mf = &((MFace*) me->mface)[i];
1684
1685                 if (enableSmooth) {
1686                         mf->flag |= ME_SMOOTH;
1687                 } else {
1688                         mf->flag &= ~ME_SMOOTH;
1689                 }
1690         }
1691
1692         mesh_calc_normals(me->mvert, me->totvert, me->mloop, me->mpoly, me->totloop, 
1693                                           me->totpoly, NULL, NULL, 0, NULL, NULL);
1694 }
1695
1696 void mesh_calc_normals(MVert *mverts, int numVerts, MLoop *mloop, MPoly *mpolys, 
1697         int UNUSED(numLoops), int numPolys, float (*polyNors_r)[3], MFace *mfaces, int numFaces, 
1698         int *origIndexFace, float (*faceNors_r)[3])
1699 {
1700         float (*pnors)[3] = polyNors_r, (*fnors)[3] = faceNors_r;
1701         float (*tnorms)[3], (*edgevecbuf)[3];
1702         float **vertcos = NULL, **vertnos = NULL;
1703         BLI_array_declare(vertcos);
1704         BLI_array_declare(vertnos);
1705         int i, j, maxPolyVerts = 0;
1706         MFace *mf;
1707         MPoly *mp;
1708         MLoop *ml;
1709
1710         if (numPolys == 0) {
1711                 return;
1712         }
1713
1714         mp = mpolys;
1715         for (i=0; i<numPolys; i++, mp++) {
1716                 maxPolyVerts = MAX2(mp->totloop, maxPolyVerts);
1717         }
1718
1719         if (maxPolyVerts == 0) {
1720                 return;
1721         }
1722
1723         /*first go through and calculate normals for all the polys*/
1724         edgevecbuf = MEM_callocN(sizeof(float)*3*maxPolyVerts, "edgevecbuf mesh.c");
1725         tnorms = MEM_callocN(sizeof(float)*3*numVerts, "tnorms mesh.c");
1726         if (!pnors) 
1727                 pnors = MEM_callocN(sizeof(float)*3*numPolys, "poly_nors mesh.c");
1728         if (!fnors)
1729                 fnors = MEM_callocN(sizeof(float)*3*numFaces, "face nors mesh.c");
1730         
1731         mp = mpolys;
1732         for (i=0; i<numPolys; i++, mp++) {
1733                 mesh_calc_poly_normal(mp, mloop+mp->loopstart, mverts, pnors[i]);
1734                 ml = mloop + mp->loopstart;
1735
1736                 BLI_array_empty(vertcos);
1737                 BLI_array_empty(vertnos);
1738                 for (j=0; j<mp->totloop; j++) {
1739                         int vindex = ml[j].v;
1740                         BLI_array_append(vertcos, mverts[vindex].co);
1741                         BLI_array_append(vertnos, tnorms[vindex]);
1742                 }
1743
1744                 accumulate_vertex_normals_poly(vertnos, pnors[i], vertcos, edgevecbuf, mp->totloop);
1745         }
1746         
1747         /* following Mesh convention; we use vertex coordinate itself for normal in this case */
1748         for(i=0; i<numVerts; i++) {
1749                 MVert *mv= &mverts[i];
1750                 float *no= tnorms[i];
1751                 
1752                 if(normalize_v3(no) == 0.0f)
1753                         normalize_v3_v3(no, mv->co);
1754
1755                 normal_float_to_short_v3(mv->no, no);
1756         }
1757         
1758         if (origIndexFace && fnors==faceNors_r && numFaces) {
1759                 mf = mfaces;
1760                 for (i=0; i<numFaces; i++, mf++, origIndexFace++) {
1761                         if (*origIndexFace < numPolys) {
1762                                 VECCOPY(fnors[i], pnors[*origIndexFace]);
1763                         } else {
1764                                 /*eek, we're not corrusponding to polys*/
1765                                 printf("error in mesh_calc_normals; tesselation face indices are incorrect.  normals may look bad.\n");
1766                         }
1767                 }
1768         }
1769
1770         BLI_array_free(vertcos);
1771         BLI_array_free(vertnos);
1772         MEM_freeN(edgevecbuf);
1773         MEM_freeN(tnorms);
1774         if (fnors != faceNors_r)
1775                 MEM_freeN(fnors);
1776         if (pnors != polyNors_r)
1777                 MEM_freeN(pnors);
1778         
1779         fnors = pnors = NULL;
1780         
1781 }
1782
1783 void mesh_calc_tessface_normals(MVert *mverts, int numVerts, MFace *mfaces, int numFaces, float (*faceNors_r)[3]) 
1784 {
1785         float (*tnorms)[3]= MEM_callocN(numVerts*sizeof(*tnorms), "tnorms");
1786         float (*fnors)[3]= (faceNors_r)? faceNors_r: MEM_callocN(sizeof(*fnors)*numFaces, "meshnormals");
1787         int i;
1788
1789         for(i=0; i<numFaces; i++) {
1790                 MFace *mf= &mfaces[i];
1791                 float *f_no= fnors[i];
1792                 float *n4 = (mf->v4)? tnorms[mf->v4]: NULL;
1793                 float *c4 = (mf->v4)? mverts[mf->v4].co: NULL;
1794
1795                 if(mf->v4)
1796                         normal_quad_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, mverts[mf->v4].co);
1797                 else
1798                         normal_tri_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co);
1799
1800                 accumulate_vertex_normals(tnorms[mf->v1], tnorms[mf->v2], tnorms[mf->v3], n4,
1801                         f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, c4);
1802         }
1803
1804         /* following Mesh convention; we use vertex coordinate itself for normal in this case */
1805         for(i=0; i<numVerts; i++) {
1806                 MVert *mv= &mverts[i];
1807                 float *no= tnorms[i];
1808                 
1809                 if(normalize_v3(no) == 0.0f)
1810                         normalize_v3_v3(no, mv->co);
1811
1812                 normal_float_to_short_v3(mv->no, no);
1813         }
1814         
1815         MEM_freeN(tnorms);
1816
1817         if(fnors != faceNors_r)
1818                 MEM_freeN(fnors);
1819 }
1820
1821
1822 static void bmesh_corners_to_loops(Mesh *me, int findex, int loopstart, int numTex, int numCol)
1823 {
1824         MTFace *texface;
1825         MTexPoly *texpoly;
1826         MCol *mcol;
1827         MLoopCol *mloopcol;
1828         MLoopUV *mloopuv;
1829         MFace *mf;
1830         int i;
1831
1832         mf = me->mface + findex;
1833
1834         for(i=0; i < numTex; i++){
1835                 texface = CustomData_get_n(&me->fdata, CD_MTFACE, findex, i);
1836                 texpoly = CustomData_get_n(&me->pdata, CD_MTEXPOLY, findex, i); 
1837                 
1838                 texpoly->tpage = texface->tpage;
1839                 texpoly->flag = texface->flag;
1840                 texpoly->transp = texface->transp;
1841                 texpoly->mode = texface->mode;
1842                 texpoly->tile = texface->tile;
1843                 texpoly->unwrap = texface->unwrap;
1844         
1845                 mloopuv = CustomData_get_n(&me->ldata, CD_MLOOPUV, loopstart, i);
1846                 mloopuv->uv[0] = texface->uv[0][0]; mloopuv->uv[1] = texface->uv[0][1]; mloopuv++;
1847                 mloopuv->uv[0] = texface->uv[1][0]; mloopuv->uv[1] = texface->uv[1][1]; mloopuv++;
1848                 mloopuv->uv[0] = texface->uv[2][0]; mloopuv->uv[1] = texface->uv[2][1]; mloopuv++;
1849
1850                 if (mf->v4) {
1851                         mloopuv->uv[0] = texface->uv[3][0]; mloopuv->uv[1] = texface->uv[3][1]; mloopuv++;
1852                 }
1853         }
1854
1855         for(i=0; i < numCol; i++){
1856                 mloopcol = CustomData_get_n(&me->ldata, CD_MLOOPCOL, loopstart, i);
1857                 mcol = CustomData_get_n(&me->fdata, CD_MCOL, findex, i);
1858
1859                 mloopcol->r = mcol[0].r; mloopcol->g = mcol[0].g; mloopcol->b = mcol[0].b; mloopcol->a = mcol[0].a; mloopcol++;
1860                 mloopcol->r = mcol[1].r; mloopcol->g = mcol[1].g; mloopcol->b = mcol[1].b; mloopcol->a = mcol[1].a; mloopcol++;
1861                 mloopcol->r = mcol[2].r; mloopcol->g = mcol[2].g; mloopcol->b = mcol[2].b; mloopcol->a = mcol[2].a; mloopcol++;
1862                 if (mf->v4) {
1863                         mloopcol->r = mcol[3].r; mloopcol->g = mcol[3].g; mloopcol->b = mcol[3].b; mloopcol->a = mcol[3].a; mloopcol++;
1864                 }
1865         }
1866         
1867         if (CustomData_has_layer(&me->fdata, CD_MDISPS)) {
1868                 MDisps *ld = CustomData_get(&me->ldata, loopstart, CD_MDISPS);
1869                 MDisps *fd = CustomData_get(&me->fdata, findex, CD_MDISPS);
1870                 float (*disps)[3] = fd->disps;
1871                 int i, tot = mf->v4 ? 4 : 3;
1872                 int side, corners;
1873                 
1874                 corners = multires_mdisp_corners(fd);
1875                 
1876                 if (corners == 0) {
1877                         /* Empty MDisp layers appear in at least one of the sintel.blend files.
1878                            Not sure why this happens, but it seems fine to just ignore them here.
1879                            If corners==0 for a non-empty layer though, something went wrong. */
1880                         BLI_assert(fd->totdisp == 0);
1881                 }
1882                 else {
1883                         side = sqrt(fd->totdisp / corners);
1884                 
1885                         for (i=0; i<tot; i++, disps += side*side, ld++) {
1886                                 ld->totdisp = side*side;
1887                         
1888                                 if (ld->disps)
1889                                         BLI_cellalloc_free(ld->disps);
1890                         
1891                                 ld->disps = BLI_cellalloc_calloc(sizeof(float)*3*side*side, "converted loop mdisps");
1892                                 if (fd->disps) {
1893                                         memcpy(ld->disps, disps, sizeof(float)*3*side*side);
1894                                 }
1895                         }
1896                 }
1897         }
1898 }
1899
1900 void convert_mfaces_to_mpolys(Mesh *mesh)
1901 {
1902         MFace *mf;
1903         MLoop *ml;
1904         MPoly *mp;
1905         MEdge *me;
1906         EdgeHash *eh;
1907         int numTex, numCol;
1908         int i, j, totloop;
1909
1910         mesh->totpoly = mesh->totface;
1911         mesh->mpoly = MEM_callocN(sizeof(MPoly)*mesh->totpoly, "mpoly converted");
1912         CustomData_add_layer(&mesh->pdata, CD_MPOLY, CD_ASSIGN, mesh->mpoly, mesh->totpoly);
1913
1914         numTex = CustomData_number_of_layers(&mesh->fdata, CD_MTFACE);
1915         numCol = CustomData_number_of_layers(&mesh->fdata, CD_MCOL);
1916         
1917         totloop = 0;
1918         mf = mesh->mface;
1919         for (i=0; i<mesh->totface; i++, mf++) {
1920                 totloop += mf->v4 ? 4 : 3;
1921         }
1922         
1923         mesh->totloop = totloop;
1924         mesh->mloop = MEM_callocN(sizeof(MLoop)*mesh->totloop, "mloop converted");
1925
1926         CustomData_add_layer(&mesh->ldata, CD_MLOOP, CD_ASSIGN, mesh->mloop, totloop);
1927         CustomData_to_bmeshpoly(&mesh->fdata, &mesh->pdata, &mesh->ldata,
1928                 mesh->totloop, mesh->totpoly);
1929
1930         eh = BLI_edgehash_new();
1931
1932         /*build edge hash*/
1933         me = mesh->medge;
1934         for (i=0; i<mesh->totedge; i++, me++) {
1935                 BLI_edgehash_insert(eh, me->v1, me->v2, SET_INT_IN_POINTER(i));
1936         }
1937
1938         j = 0; /*current loop index*/
1939         ml = mesh->mloop;
1940         mf = mesh->mface;
1941         mp = mesh->mpoly;
1942         for (i=0; i<mesh->totface; i++, mf++, mp++) {
1943                 mp->loopstart = j;
1944                 
1945                 mp->totloop = mf->v4 ? 4 : 3;
1946
1947                 mp->mat_nr = mf->mat_nr;
1948                 mp->flag = mf->flag;
1949                 
1950                 #define ML(v1, v2) {ml->v = mf->v1; ml->e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(eh, mf->v1, mf->v2)); ml++; j++;}
1951                 
1952                 ML(v1, v2);
1953                 ML(v2, v3);
1954                 if (mf->v4) {
1955                         ML(v3, v4);
1956                         ML(v4, v1);
1957                 } else {
1958                         ML(v3, v1);
1959                 }
1960                 
1961                 #undef ML
1962
1963                 bmesh_corners_to_loops(mesh, i, mp->loopstart, numTex, numCol);
1964         }
1965
1966         /* note, we dont convert FGons at all, these are not even real ngons,
1967          * they have their own UV's, colors etc - its more an editing feature. */
1968
1969         BLI_edgehash_free(eh, NULL);
1970 }
1971
1972 float (*mesh_getVertexCos(Mesh *me, int *numVerts_r))[3]
1973 {
1974         int i, numVerts = me->totvert;
1975         float (*cos)[3] = MEM_mallocN(sizeof(*cos)*numVerts, "vertexcos1");
1976         
1977         if (numVerts_r) *numVerts_r = numVerts;
1978         for (i=0; i<numVerts; i++)
1979                 VECCOPY(cos[i], me->mvert[i].co);
1980         
1981         return cos;
1982 }
1983
1984 UvVertMap *make_uv_vert_map(struct MFace *mface, struct MTFace *tface, unsigned int totface, unsigned int totvert, int selected, float *limit)
1985 {
1986         UvVertMap *vmap;
1987         UvMapVert *buf;
1988         MFace *mf;
1989         MTFace *tf;
1990         unsigned int a;
1991         int     i, totuv, nverts;
1992
1993         totuv = 0;
1994
1995         /* generate UvMapVert array */
1996         mf= mface;
1997         tf= tface;
1998         for(a=0; a<totface; a++, mf++, tf++)
1999                 if(!selected || (!(mf->flag & ME_HIDE) && (mf->flag & ME_FACE_SEL)))
2000                         totuv += (mf->v4)? 4: 3;
2001                 
2002         if(totuv==0)
2003                 return NULL;
2004         
2005         vmap= (UvVertMap*)MEM_callocN(sizeof(*vmap), "UvVertMap");
2006         if (!vmap)
2007                 return NULL;
2008
2009         vmap->vert= (UvMapVert**)MEM_callocN(sizeof(*vmap->vert)*totvert, "UvMapVert*");
2010         buf= vmap->buf= (UvMapVert*)MEM_callocN(sizeof(*vmap->buf)*totuv, "UvMapVert");
2011
2012         if (!vmap->vert || !vmap->buf) {
2013                 free_uv_vert_map(vmap);
2014                 return NULL;
2015         }
2016
2017         mf= mface;
2018         tf= tface;
2019         for(a=0; a<totface; a++, mf++, tf++) {
2020                 if(!selected || (!(mf->flag & ME_HIDE) && (mf->flag & ME_FACE_SEL))) {
2021                         nverts= (mf->v4)? 4: 3;
2022
2023                         for(i=0; i<nverts; i++) {
2024                                 buf->tfindex= i;
2025                                 buf->f= a;
2026                                 buf->separate = 0;
2027                                 buf->next= vmap->vert[*(&mf->v1 + i)];
2028                                 vmap->vert[*(&mf->v1 + i)]= buf;
2029                                 buf++;
2030                         }
2031                 }
2032         }
2033         
2034         /* sort individual uvs for each vert */
2035         tf= tface;
2036         for(a=0; a<totvert; a++) {
2037                 UvMapVert *newvlist= NULL, *vlist=vmap->vert[a];
2038                 UvMapVert *iterv, *v, *lastv, *next;
2039                 float *uv, *uv2, uvdiff[2];
2040
2041                 while(vlist) {
2042                         v= vlist;
2043                         vlist= vlist->next;
2044                         v->next= newvlist;
2045                         newvlist= v;
2046
2047                         uv= (tf+v->f)->uv[v->tfindex];
2048                         lastv= NULL;
2049                         iterv= vlist;
2050
2051                         while(iterv) {
2052                                 next= iterv->next;
2053
2054                                 uv2= (tf+iterv->f)->uv[iterv->tfindex];
2055                                 sub_v2_v2v2(uvdiff, uv2, uv);
2056
2057
2058                                 if(fabsf(uv[0]-uv2[0]) < limit[0] && fabsf(uv[1]-uv2[1]) < limit[1]) {
2059                                         if(lastv) lastv->next= next;
2060                                         else vlist= next;
2061                                         iterv->next= newvlist;
2062                                         newvlist= iterv;
2063                                 }
2064                                 else
2065                                         lastv=iterv;
2066
2067                                 iterv= next;
2068                         }
2069
2070                         newvlist->separate = 1;
2071                 }
2072
2073                 vmap->vert[a]= newvlist;
2074         }
2075         
2076         return vmap;
2077 }
2078
2079 UvMapVert *get_uv_map_vert(UvVertMap *vmap, unsigned int v)
2080 {
2081         return vmap->vert[v];
2082 }
2083
2084 void free_uv_vert_map(UvVertMap *vmap)
2085 {
2086         if (vmap) {
2087                 if (vmap->vert) MEM_freeN(vmap->vert);
2088                 if (vmap->buf) MEM_freeN(vmap->buf);
2089                 MEM_freeN(vmap);
2090         }
2091 }
2092
2093 /* Generates a map where the key is the vertex and the value is a list
2094    of faces that use that vertex as a corner. The lists are allocated
2095    from one memory pool. */
2096 void create_vert_face_map(ListBase **map, IndexNode **mem, const MFace *mface, const int totvert, const int totface)
2097 {
2098         int i,j;
2099         IndexNode *node = NULL;
2100         
2101         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
2102         (*mem) = MEM_callocN(sizeof(IndexNode) * totface*4, "vert face map mem");
2103         node = *mem;
2104         
2105         /* Find the users */
2106         for(i = 0; i < totface; ++i){
2107                 for(j = 0; j < (mface[i].v4?4:3); ++j, ++node) {
2108                         node->index = i;
2109                         BLI_addtail(&(*map)[((unsigned int*)(&mface[i]))[j]], node);
2110                 }
2111         }
2112 }
2113
2114 /* Generates a map where the key is the vertex and the value is a list
2115    of edges that use that vertex as an endpoint. The lists are allocated
2116    from one memory pool. */
2117 void create_vert_edge_map(ListBase **map, IndexNode **mem, const MEdge *medge, const int totvert, const int totedge)
2118 {
2119         int i, j;
2120         IndexNode *node = NULL;
2121  
2122         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
2123         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge * 2, "vert edge map mem");
2124         node = *mem;
2125
2126         /* Find the users */
2127         for(i = 0; i < totedge; ++i){
2128                 for(j = 0; j < 2; ++j, ++node) {
2129                         node->index = i;
2130                         BLI_addtail(&(*map)[((unsigned int*)(&medge[i].v1))[j]], node);
2131                 }
2132         }
2133 }
2134
2135 /* Partial Mesh Visibility */
2136 PartialVisibility *mesh_pmv_copy(PartialVisibility *pmv)
2137 {
2138         PartialVisibility *n= MEM_dupallocN(pmv);
2139         n->vert_map= MEM_dupallocN(pmv->vert_map);
2140         n->edge_map= MEM_dupallocN(pmv->edge_map);
2141         n->old_edges= MEM_dupallocN(pmv->old_edges);
2142         n->old_faces= MEM_dupallocN(pmv->old_faces);
2143         return n;
2144 }
2145
2146 void mesh_pmv_free(PartialVisibility *pv)
2147 {
2148         MEM_freeN(pv->vert_map);
2149         MEM_freeN(pv->edge_map);
2150         MEM_freeN(pv->old_faces);
2151         MEM_freeN(pv->old_edges);
2152         MEM_freeN(pv);
2153 }
2154
2155 void mesh_pmv_revert(Mesh *me)
2156 {
2157         if(me->pv) {
2158                 unsigned i;
2159                 MVert *nve, *old_verts;
2160                 
2161                 /* Reorder vertices */
2162                 nve= me->mvert;
2163                 old_verts = MEM_mallocN(sizeof(MVert)*me->pv->totvert,"PMV revert verts");
2164                 for(i=0; i<me->pv->totvert; ++i)
2165                         old_verts[i]= nve[me->pv->vert_map[i]];
2166
2167                 /* Restore verts, edges and faces */
2168                 CustomData_free_layer_active(&me->vdata, CD_MVERT, me->totvert);
2169                 CustomData_free_layer_active(&me->edata, CD_MEDGE, me->totedge);
2170                 CustomData_free_layer_active(&me->fdata, CD_MFACE, me->totface);
2171
2172                 CustomData_add_layer(&me->vdata, CD_MVERT, CD_ASSIGN, old_verts, me->pv->totvert);
2173                 CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, me->pv->old_edges, me->pv->totedge);
2174                 CustomData_add_layer(&me->fdata, CD_MFACE, CD_ASSIGN, me->pv->old_faces, me->pv->totface);
2175                 mesh_update_customdata_pointers(me);
2176
2177                 me->totvert= me->pv->totvert;
2178                 me->totedge= me->pv->totedge;
2179                 me->totface= me->pv->totface;
2180
2181                 me->pv->old_edges= NULL;
2182                 me->pv->old_faces= NULL;
2183
2184                 /* Free maps */
2185                 MEM_freeN(me->pv->edge_map);
2186                 me->pv->edge_map= NULL;
2187                 MEM_freeN(me->pv->vert_map);
2188                 me->pv->vert_map= NULL;
2189         }
2190 }
2191
2192 void mesh_pmv_off(Mesh *me)
2193 {
2194         if(me->pv) {
2195                 mesh_pmv_revert(me);
2196                 MEM_freeN(me->pv);
2197                 me->pv= NULL;
2198         }
2199 }
2200
2201 void mesh_loops_to_tri_corners(CustomData *fdata, CustomData *ldata, 
2202                            CustomData *pdata, int lindex[3], int findex, 
2203                            int polyindex) 
2204 {
2205         MTFace *texface;
2206         MTexPoly *texpoly;
2207         MCol *mcol;
2208         MLoopCol *mloopcol;
2209         MLoopUV *mloopuv;
2210         int i, j, hasWCol = CustomData_has_layer(ldata, CD_WEIGHT_MLOOPCOL);
2211         int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY);
2212         int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
2213         
2214         for(i=0; i < numTex; i++){
2215                 texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
2216                 texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, polyindex, i);
2217                 
2218                 texface->tpage = texpoly->tpage;
2219                 texface->flag = texpoly->flag;
2220                 texface->transp = texpoly->transp;
2221                 texface->mode = texpoly->mode;
2222                 texface->tile = texpoly->tile;
2223                 texface->unwrap = texpoly->unwrap;
2224
2225                 for (j=0; j<3; j++) {
2226                         mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, lindex[j], i);
2227                         texface->uv[j][0] = mloopuv->uv[0];
2228                         texface->uv[j][1] = mloopuv->uv[1];
2229                 }
2230         }
2231
2232         for(i=0; i < numCol; i++){
2233                 mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
2234
2235                 for (j=0; j<3; j++) {
2236                         mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, lindex[j], i);
2237                         mcol[j].r = mloopcol->r;
2238                         mcol[j].g = mloopcol->g;
2239                         mcol[j].b = mloopcol->b;
2240                         mcol[j].a = mloopcol->a;
2241                 }
2242         }
2243
2244         if (hasWCol) {
2245                 mcol = CustomData_get(fdata,  findex, CD_WEIGHT_MCOL);
2246
2247                 for (j=0; j<3; j++) {
2248                         mloopcol = CustomData_get(ldata, lindex[j], CD_WEIGHT_MLOOPCOL);
2249                         mcol[j].r = mloopcol->r;
2250                         mcol[j].g = mloopcol->g;
2251                         mcol[j].b = mloopcol->b;
2252                         mcol[j].a = mloopcol->a;
2253                 }
2254         }
2255 }
2256
2257 /*
2258   this function recreates a tesselation.
2259   returns number of tesselation faces.
2260
2261   use_poly_origindex sets whether or not the tesselation faces' origindex
2262   layer should point to original poly indices or real poly indices.
2263
2264   use_face_origindex sets the tesselation faces' origindex layer
2265   to point to the tesselation faces themselves, not the polys.
2266
2267   if both of the above are 0, it'll use the indices of the mpolys of the MPoly
2268   data in pdata, and ignore the origindex layer altogether.
2269  */
2270 int mesh_recalcTesselation(CustomData *fdata, 
2271                            CustomData *ldata, CustomData *pdata,
2272                            MVert *mvert, int totface, int UNUSED(totloop),
2273                            int totpoly, int use_poly_origindex, 
2274                            int use_face_origindex)
2275 {
2276         MPoly *mp, *mpoly;
2277         MLoop *ml, *mloop;
2278         MFace *mf = NULL, *mface;
2279         BLI_array_declare(mf);
2280         EditVert *v, *lastv, *firstv;
2281         EditFace *f;
2282         BLI_array_declare(origIndex);
2283         int i, j, k, lindex[4], *origIndex = NULL, *polyorigIndex;
2284         int numTex, numCol;
2285
2286         mpoly = CustomData_get_layer(pdata, CD_MPOLY);
2287         mloop = CustomData_get_layer(ldata, CD_MLOOP);
2288
2289         numTex = CustomData_number_of_layers(ldata, CD_MLOOPUV);
2290         numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
2291         
2292         k = 0;
2293         mp = mpoly;
2294         polyorigIndex = use_poly_origindex? CustomData_get_layer(pdata, CD_ORIGINDEX) : NULL;
2295         for (i=0; i<totpoly; i++, mp++) {
2296                 if (mp->totloop > 2) {          
2297                         ml = mloop + mp->loopstart;
2298                         
2299                         BLI_begin_edgefill();
2300                         firstv = NULL;
2301                         lastv = NULL;
2302                         for (j=0; j<mp->totloop; j++, ml++) {
2303                                 v = BLI_addfillvert(mvert[ml->v].co);
2304                                 if (polyorigIndex && use_poly_origindex)
2305                                         v->hash = polyorigIndex[i];
2306                                 else
2307                                         v->hash = i;
2308         
2309                                 v->keyindex = mp->loopstart + j;
2310         
2311                                 if (lastv)
2312                                         BLI_addfilledge(lastv, v);
2313         
2314                                 if (!firstv)
2315                                         firstv = v;
2316                                 lastv = v;
2317                         }
2318                         BLI_addfilledge(lastv, firstv);
2319                         
2320                         BLI_edgefill(2);
2321                         for (f=fillfacebase.first; f; f=f->next) {
2322                                 BLI_array_growone(mf);
2323                                 BLI_array_growone(origIndex);
2324         
2325                                 /*these are loop indices, they'll be transformed
2326                                   into vert indices later.*/
2327                                 mf[k].v1 = f->v1->keyindex;
2328                                 mf[k].v2 = f->v2->keyindex;
2329                                 mf[k].v3 = f->v3->keyindex;
2330                                 
2331                                 /*put poly index in mf->v4*/
2332                                 mf[k].v4 = f->v1->hash;
2333                                 
2334                                 mf[k].mat_nr = mp->mat_nr;
2335                                 mf[k].flag = mp->flag;
2336                                 origIndex[k] = use_face_origindex ? k : f->v1->hash;
2337         
2338                                 k++;
2339                         }
2340         
2341                         BLI_end_edgefill();
2342                 }
2343         }
2344
2345         CustomData_free(fdata, totface);
2346         memset(fdata, 0, sizeof(CustomData));
2347         totface = k;
2348         
2349         CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mf, totface);
2350         CustomData_add_layer(fdata, CD_ORIGINDEX, CD_ASSIGN, origIndex, totface);
2351         CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
2352
2353         mface = mf;
2354         for (i=0; i<totface; i++, mf++) {
2355                 /*sort loop indices to ensure winding is correct*/
2356                 if (mf->v1 > mf->v2) SWAP(int, mf->v1, mf->v2);
2357                 if (mf->v2 > mf->v3) SWAP(int, mf->v2, mf->v3);
2358                 if (mf->v1 > mf->v2) SWAP(int, mf->v1, mf->v2);
2359
2360                 if (mf->v1 > mf->v2) SWAP(int, mf->v1, mf->v2);
2361                 if (mf->v2 > mf->v3) SWAP(int, mf->v2, mf->v3);
2362                 if (mf->v1 > mf->v2) SWAP(int, mf->v1, mf->v2);
2363         
2364                 lindex[0] = mf->v1;
2365                 lindex[1] = mf->v2;
2366                 lindex[2] = mf->v3;
2367
2368                 /*transform loop indices to vert indices*/
2369                 mf->v1 = mloop[mf->v1].v;
2370                 mf->v2 = mloop[mf->v2].v;
2371                 mf->v3 = mloop[mf->v3].v;
2372
2373                 mesh_loops_to_tri_corners(fdata, ldata, pdata,
2374                         lindex, i, mf->v4);
2375                 
2376                 mf->v4 = 0;
2377         }
2378
2379         return totface;
2380 }
2381
2382 /*
2383  * COMPUTE POLY NORMAL
2384  *
2385  * Computes the normal of a planar 
2386  * polygon See Graphics Gems for 
2387  * computing newell normal.
2388  *
2389 */
2390 static void mesh_calc_ngon_normal(MPoly *mpoly, MLoop *loopstart, 
2391                                   MVert *mvert, float *normal)
2392 {
2393
2394         MVert *v1, *v2, *v3;
2395         double u[3],  v[3], w[3];
2396         double n[3] = {0.0, 0.0, 0.0}, l;
2397         int i;
2398
2399         for(i = 0; i < mpoly->totloop; i++){
2400                 v1 = mvert + loopstart[i].v;
2401                 v2 = mvert + loopstart[(i+1)%mpoly->totloop].v;
2402                 v3 = mvert + loopstart[(i+2)%mpoly->totloop].v;
2403                 
2404                 VECCOPY(u, v1->co);
2405                 VECCOPY(v, v2->co);
2406                 VECCOPY(w, v3->co);
2407
2408                 /*this fixes some weird numerical error*/
2409                 if (i==0) {
2410                         u[0] += 0.0001f;
2411                         u[1] += 0.0001f;
2412                         u[2] += 0.0001f;
2413                 }
2414                 
2415                 /* newell's method
2416                 
2417                 so thats?:
2418                 (a[1] - b[1]) * (a[2] + b[2]);
2419                 a[1]*b[2] - b[1]*a[2] - b[1]*b[2] + a[1]*a[2]
2420
2421                 odd.  half of that is the cross product. . .what's the
2422                 other half?
2423
2424                 also could be like a[1]*(b[2] + a[2]) - b[1]*(a[2] - b[2])
2425                 */
2426
2427                 n[0] += (u[1] - v[1]) * (u[2] + v[2]);
2428                 n[1] += (u[2] - v[2]) * (u[0] + v[0]);
2429                 n[2] += (u[0] - v[0]) * (u[1] + v[1]);
2430         }
2431         
2432         l = n[0]*n[0]+n[1]*n[1]+n[2]*n[2];
2433         l = sqrt(l);
2434
2435         if (l == 0.0) {
2436                 normal[0] = 0.0f;
2437                 normal[1] = 0.0f;
2438                 normal[2] = 1.0f;
2439
2440                 return;
2441         } else l = 1.0f / l;
2442
2443         n[0] *= l;
2444         n[1] *= l;
2445         n[2] *= l;
2446         
2447         normal[0] = (float) n[0];
2448         normal[1] = (float) n[1];
2449         normal[2] = (float) n[2];
2450
2451 }
2452
2453 void mesh_calc_poly_normal(MPoly *mpoly, MLoop *loopstart, 
2454                            MVert *mvarray, float *no)
2455 {
2456         if(mpoly->totloop > 4) {
2457                 mesh_calc_ngon_normal(mpoly, loopstart, mvarray, no);
2458         }
2459         else if(mpoly->totloop == 3){
2460                 MVert *v1, *v2, *v3;
2461
2462                 v1 = mvarray + (loopstart++)->v;
2463                 v2 = mvarray + (loopstart++)->v;
2464                 v3 = mvarray + loopstart->v;
2465                 normal_tri_v3( no,v1->co, v2->co, v3->co);
2466         }
2467         else if(mpoly->totloop == 4){
2468                 MVert *v1, *v2, *v3, *v4;
2469
2470                 v1 = mvarray + (loopstart++)->v;
2471                 v2 = mvarray + (loopstart++)->v;
2472                 v3 = mvarray + (loopstart++)->v;
2473                 v4 = mvarray + loopstart->v;
2474                 normal_quad_v3( no,v1->co, v2->co, v3->co, v4->co);
2475         }
2476         else{ /*horrible, two sided face!*/
2477                 no[0] = 0.0;
2478                 no[1] = 0.0;
2479                 no[2] = 1.0;
2480         }
2481 }
2482
2483 /* basic vertex data functions */
2484 int minmax_mesh(Mesh *me, float min[3], float max[3])
2485 {
2486         int i= me->totvert;
2487         MVert *mvert;
2488         for(mvert= me->mvert; i--; mvert++) {
2489                 DO_MINMAX(mvert->co, min, max);
2490         }
2491         
2492         return (me->totvert != 0);
2493 }
2494
2495 int mesh_center_median(Mesh *me, float cent[3])
2496 {
2497         int i= me->totvert;
2498         MVert *mvert;
2499         zero_v3(cent);
2500         for(mvert= me->mvert; i--; mvert++) {
2501                 add_v3_v3(cent, mvert->co);
2502         }
2503         /* otherwise we get NAN for 0 verts */
2504         if(me->totvert) {
2505                 mul_v3_fl(cent, 1.0f/(float)me->totvert);
2506         }
2507
2508         return (me->totvert != 0);
2509 }
2510
2511 int mesh_center_bounds(Mesh *me, float cent[3])
2512 {
2513         float min[3], max[3];
2514         INIT_MINMAX(min, max);
2515         if(minmax_mesh(me, min, max)) {
2516                 mid_v3_v3v3(cent, min, max);
2517                 return 1;
2518         }
2519
2520         return 0;
2521 }
2522
2523 void mesh_translate(Mesh *me, float offset[3], int do_keys)
2524 {
2525         int i= me->totvert;
2526         MVert *mvert;
2527         for(mvert= me->mvert; i--; mvert++) {
2528                 add_v3_v3(mvert->co, offset);
2529         }
2530         
2531         if (do_keys && me->key) {
2532                 KeyBlock *kb;
2533                 for (kb=me->key->block.first; kb; kb=kb->next) {
2534                         float *fp= kb->data;
2535                         for (i= kb->totelem; i--; fp+=3) {
2536                                 add_v3_v3(fp, offset);
2537                         }
2538                 }
2539         }
2540 }
2541
2542
2543 void BKE_mesh_ensure_navmesh(Mesh *me)
2544 {
2545         if (!CustomData_has_layer(&me->fdata, CD_RECAST)) {
2546                 int i;
2547                 int numFaces = me->totface;
2548                 int* recastData;
2549                 CustomData_add_layer_named(&me->fdata, CD_RECAST, CD_CALLOC, NULL, numFaces, "recastData");
2550                 recastData = (int*)CustomData_get_layer(&me->fdata, CD_RECAST);
2551                 for (i=0; i<numFaces; i++) {
2552                         recastData[i] = i+1;
2553                 }
2554                 CustomData_add_layer_named(&me->fdata, CD_RECAST, CD_REFERENCE, recastData, numFaces, "recastData");
2555         }
2556 }