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