remove mesh and object arguments from bmesh operators, these are stored within the...
[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(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 set_shapekey=%i", 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         /*BMESH_TODO now to deal with fgons*/
1965
1966         BLI_edgehash_free(eh, NULL);
1967 }
1968
1969 float (*mesh_getVertexCos(Mesh *me, int *numVerts_r))[3]
1970 {
1971         int i, numVerts = me->totvert;
1972         float (*cos)[3] = MEM_mallocN(sizeof(*cos)*numVerts, "vertexcos1");
1973         
1974         if (numVerts_r) *numVerts_r = numVerts;
1975         for (i=0; i<numVerts; i++)
1976                 VECCOPY(cos[i], me->mvert[i].co);
1977         
1978         return cos;
1979 }
1980
1981 UvVertMap *make_uv_vert_map(struct MFace *mface, struct MTFace *tface, unsigned int totface, unsigned int totvert, int selected, float *limit)
1982 {
1983         UvVertMap *vmap;
1984         UvMapVert *buf;
1985         MFace *mf;
1986         MTFace *tf;
1987         unsigned int a;
1988         int     i, totuv, nverts;
1989
1990         totuv = 0;
1991
1992         /* generate UvMapVert array */
1993         mf= mface;
1994         tf= tface;
1995         for(a=0; a<totface; a++, mf++, tf++)
1996                 if(!selected || (!(mf->flag & ME_HIDE) && (mf->flag & ME_FACE_SEL)))
1997                         totuv += (mf->v4)? 4: 3;
1998                 
1999         if(totuv==0)
2000                 return NULL;
2001         
2002         vmap= (UvVertMap*)MEM_callocN(sizeof(*vmap), "UvVertMap");
2003         if (!vmap)
2004                 return NULL;
2005
2006         vmap->vert= (UvMapVert**)MEM_callocN(sizeof(*vmap->vert)*totvert, "UvMapVert*");
2007         buf= vmap->buf= (UvMapVert*)MEM_callocN(sizeof(*vmap->buf)*totuv, "UvMapVert");
2008
2009         if (!vmap->vert || !vmap->buf) {
2010                 free_uv_vert_map(vmap);
2011                 return NULL;
2012         }
2013
2014         mf= mface;
2015         tf= tface;
2016         for(a=0; a<totface; a++, mf++, tf++) {
2017                 if(!selected || (!(mf->flag & ME_HIDE) && (mf->flag & ME_FACE_SEL))) {
2018                         nverts= (mf->v4)? 4: 3;
2019
2020                         for(i=0; i<nverts; i++) {
2021                                 buf->tfindex= i;
2022                                 buf->f= a;
2023                                 buf->separate = 0;
2024                                 buf->next= vmap->vert[*(&mf->v1 + i)];
2025                                 vmap->vert[*(&mf->v1 + i)]= buf;
2026                                 buf++;
2027                         }
2028                 }
2029         }
2030         
2031         /* sort individual uvs for each vert */
2032         tf= tface;
2033         for(a=0; a<totvert; a++) {
2034                 UvMapVert *newvlist= NULL, *vlist=vmap->vert[a];
2035                 UvMapVert *iterv, *v, *lastv, *next;
2036                 float *uv, *uv2, uvdiff[2];
2037
2038                 while(vlist) {
2039                         v= vlist;
2040                         vlist= vlist->next;
2041                         v->next= newvlist;
2042                         newvlist= v;
2043
2044                         uv= (tf+v->f)->uv[v->tfindex];
2045                         lastv= NULL;
2046                         iterv= vlist;
2047
2048                         while(iterv) {
2049                                 next= iterv->next;
2050
2051                                 uv2= (tf+iterv->f)->uv[iterv->tfindex];
2052                                 sub_v2_v2v2(uvdiff, uv2, uv);
2053
2054
2055                                 if(fabsf(uv[0]-uv2[0]) < limit[0] && fabsf(uv[1]-uv2[1]) < limit[1]) {
2056                                         if(lastv) lastv->next= next;
2057                                         else vlist= next;
2058                                         iterv->next= newvlist;
2059                                         newvlist= iterv;
2060                                 }
2061                                 else
2062                                         lastv=iterv;
2063
2064                                 iterv= next;
2065                         }
2066
2067                         newvlist->separate = 1;
2068                 }
2069
2070                 vmap->vert[a]= newvlist;
2071         }
2072         
2073         return vmap;
2074 }
2075
2076 UvMapVert *get_uv_map_vert(UvVertMap *vmap, unsigned int v)
2077 {
2078         return vmap->vert[v];
2079 }
2080
2081 void free_uv_vert_map(UvVertMap *vmap)
2082 {
2083         if (vmap) {
2084                 if (vmap->vert) MEM_freeN(vmap->vert);
2085                 if (vmap->buf) MEM_freeN(vmap->buf);
2086                 MEM_freeN(vmap);
2087         }
2088 }
2089
2090 /* Generates a map where the key is the vertex and the value is a list
2091    of faces that use that vertex as a corner. The lists are allocated
2092    from one memory pool. */
2093 void create_vert_face_map(ListBase **map, IndexNode **mem, const MFace *mface, const int totvert, const int totface)
2094 {
2095         int i,j;
2096         IndexNode *node = NULL;
2097         
2098         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
2099         (*mem) = MEM_callocN(sizeof(IndexNode) * totface*4, "vert face map mem");
2100         node = *mem;
2101         
2102         /* Find the users */
2103         for(i = 0; i < totface; ++i){
2104                 for(j = 0; j < (mface[i].v4?4:3); ++j, ++node) {
2105                         node->index = i;
2106                         BLI_addtail(&(*map)[((unsigned int*)(&mface[i]))[j]], node);
2107                 }
2108         }
2109 }
2110
2111 /* Generates a map where the key is the vertex and the value is a list
2112    of edges that use that vertex as an endpoint. The lists are allocated
2113    from one memory pool. */
2114 void create_vert_edge_map(ListBase **map, IndexNode **mem, const MEdge *medge, const int totvert, const int totedge)
2115 {
2116         int i, j;
2117         IndexNode *node = NULL;
2118  
2119         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
2120         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge * 2, "vert edge map mem");
2121         node = *mem;
2122
2123         /* Find the users */
2124         for(i = 0; i < totedge; ++i){
2125                 for(j = 0; j < 2; ++j, ++node) {
2126                         node->index = i;
2127                         BLI_addtail(&(*map)[((unsigned int*)(&medge[i].v1))[j]], node);
2128                 }
2129         }
2130 }
2131
2132 /* Partial Mesh Visibility */
2133 PartialVisibility *mesh_pmv_copy(PartialVisibility *pmv)
2134 {
2135         PartialVisibility *n= MEM_dupallocN(pmv);
2136         n->vert_map= MEM_dupallocN(pmv->vert_map);
2137         n->edge_map= MEM_dupallocN(pmv->edge_map);
2138         n->old_edges= MEM_dupallocN(pmv->old_edges);
2139         n->old_faces= MEM_dupallocN(pmv->old_faces);
2140         return n;
2141 }
2142
2143 void mesh_pmv_free(PartialVisibility *pv)
2144 {
2145         MEM_freeN(pv->vert_map);
2146         MEM_freeN(pv->edge_map);
2147         MEM_freeN(pv->old_faces);
2148         MEM_freeN(pv->old_edges);
2149         MEM_freeN(pv);
2150 }
2151
2152 void mesh_pmv_revert(Mesh *me)
2153 {
2154         if(me->pv) {
2155                 unsigned i;
2156                 MVert *nve, *old_verts;
2157                 
2158                 /* Reorder vertices */
2159                 nve= me->mvert;
2160                 old_verts = MEM_mallocN(sizeof(MVert)*me->pv->totvert,"PMV revert verts");
2161                 for(i=0; i<me->pv->totvert; ++i)
2162                         old_verts[i]= nve[me->pv->vert_map[i]];
2163
2164                 /* Restore verts, edges and faces */
2165                 CustomData_free_layer_active(&me->vdata, CD_MVERT, me->totvert);
2166                 CustomData_free_layer_active(&me->edata, CD_MEDGE, me->totedge);
2167                 CustomData_free_layer_active(&me->fdata, CD_MFACE, me->totface);
2168
2169                 CustomData_add_layer(&me->vdata, CD_MVERT, CD_ASSIGN, old_verts, me->pv->totvert);
2170                 CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, me->pv->old_edges, me->pv->totedge);
2171                 CustomData_add_layer(&me->fdata, CD_MFACE, CD_ASSIGN, me->pv->old_faces, me->pv->totface);
2172                 mesh_update_customdata_pointers(me);
2173
2174                 me->totvert= me->pv->totvert;
2175                 me->totedge= me->pv->totedge;
2176                 me->totface= me->pv->totface;
2177
2178                 me->pv->old_edges= NULL;
2179                 me->pv->old_faces= NULL;
2180
2181                 /* Free maps */
2182                 MEM_freeN(me->pv->edge_map);
2183                 me->pv->edge_map= NULL;
2184                 MEM_freeN(me->pv->vert_map);
2185                 me->pv->vert_map= NULL;
2186         }
2187 }
2188
2189 void mesh_pmv_off(Mesh *me)
2190 {
2191         if(me->pv) {
2192                 mesh_pmv_revert(me);
2193                 MEM_freeN(me->pv);
2194                 me->pv= NULL;
2195         }
2196 }
2197
2198 void mesh_loops_to_tri_corners(CustomData *fdata, CustomData *ldata, 
2199                            CustomData *pdata, int lindex[3], int findex, 
2200                            int polyindex) 
2201 {
2202         MTFace *texface;
2203         MTexPoly *texpoly;
2204         MCol *mcol;
2205         MLoopCol *mloopcol;
2206         MLoopUV *mloopuv;
2207         int i, j, hasWCol = CustomData_has_layer(ldata, CD_WEIGHT_MLOOPCOL);
2208         int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY);
2209         int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
2210         
2211         for(i=0; i < numTex; i++){
2212                 texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
2213                 texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, polyindex, i);
2214                 
2215                 texface->tpage = texpoly->tpage;
2216                 texface->flag = texpoly->flag;
2217                 texface->transp = texpoly->transp;
2218                 texface->mode = texpoly->mode;
2219                 texface->tile = texpoly->tile;
2220                 texface->unwrap = texpoly->unwrap;
2221
2222                 for (j=0; j<3; j++) {
2223                         mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, lindex[j], i);
2224                         texface->uv[j][0] = mloopuv->uv[0];
2225                         texface->uv[j][1] = mloopuv->uv[1];
2226                 }
2227         }
2228
2229         for(i=0; i < numCol; i++){
2230                 mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
2231
2232                 for (j=0; j<3; j++) {
2233                         mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, lindex[j], i);
2234                         mcol[j].r = mloopcol->r;
2235                         mcol[j].g = mloopcol->g;
2236                         mcol[j].b = mloopcol->b;
2237                         mcol[j].a = mloopcol->a;
2238                 }
2239         }
2240
2241         if (hasWCol) {
2242                 mcol = CustomData_get(fdata,  findex, CD_WEIGHT_MCOL);
2243
2244                 for (j=0; j<3; j++) {
2245                         mloopcol = CustomData_get(ldata, lindex[j], CD_WEIGHT_MLOOPCOL);
2246                         mcol[j].r = mloopcol->r;
2247                         mcol[j].g = mloopcol->g;
2248                         mcol[j].b = mloopcol->b;
2249                         mcol[j].a = mloopcol->a;
2250                 }
2251         }
2252 }
2253
2254 /*
2255   this function recreates a tesselation.
2256   returns number of tesselation faces.
2257
2258   use_poly_origindex sets whether or not the tesselation faces' origindex
2259   layer should point to original poly indices or real poly indices.
2260
2261   use_face_origindex sets the tesselation faces' origindex layer
2262   to point to the tesselation faces themselves, not the polys.
2263
2264   if both of the above are 0, it'll use the indices of the mpolys of the MPoly
2265   data in pdata, and ignore the origindex layer altogether.
2266  */
2267 int mesh_recalcTesselation(CustomData *fdata, 
2268                            CustomData *ldata, CustomData *pdata,
2269                            MVert *mvert, int totface, int UNUSED(totloop),
2270                            int totpoly, int use_poly_origindex, 
2271                            int use_face_origindex)
2272 {
2273         MPoly *mp, *mpoly;
2274         MLoop *ml, *mloop;
2275         MFace *mf = NULL, *mface;
2276         BLI_array_declare(mf);
2277         EditVert *v, *lastv, *firstv;
2278         EditFace *f;
2279         BLI_array_declare(origIndex);
2280         int i, j, k, lindex[4], *origIndex = NULL, *polyorigIndex;
2281         int numTex, numCol;
2282
2283         mpoly = CustomData_get_layer(pdata, CD_MPOLY);
2284         mloop = CustomData_get_layer(ldata, CD_MLOOP);
2285
2286         numTex = CustomData_number_of_layers(ldata, CD_MLOOPUV);
2287         numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
2288         
2289         k = 0;
2290         mp = mpoly;
2291         polyorigIndex = use_poly_origindex? CustomData_get_layer(pdata, CD_ORIGINDEX) : NULL;
2292         for (i=0; i<totpoly; i++, mp++) {
2293                 if (mp->totloop > 2) {          
2294                         ml = mloop + mp->loopstart;
2295                         
2296                         BLI_begin_edgefill();
2297                         firstv = NULL;
2298                         lastv = NULL;
2299                         for (j=0; j<mp->totloop; j++, ml++) {
2300                                 v = BLI_addfillvert(mvert[ml->v].co);
2301                                 if (polyorigIndex && use_poly_origindex)
2302                                         v->hash = polyorigIndex[i];
2303                                 else
2304                                         v->hash = i;
2305         
2306                                 v->keyindex = mp->loopstart + j;
2307         
2308                                 if (lastv)
2309                                         BLI_addfilledge(lastv, v);
2310         
2311                                 if (!firstv)
2312                                         firstv = v;
2313                                 lastv = v;
2314                         }
2315                         BLI_addfilledge(lastv, firstv);
2316                         
2317                         BLI_edgefill(2);
2318                         for (f=fillfacebase.first; f; f=f->next) {
2319                                 BLI_array_growone(mf);
2320                                 BLI_array_growone(origIndex);
2321         
2322                                 /*these are loop indices, they'll be transformed
2323                                   into vert indices later.*/
2324                                 mf[k].v1 = f->v1->keyindex;
2325                                 mf[k].v2 = f->v2->keyindex;
2326                                 mf[k].v3 = f->v3->keyindex;
2327                                 
2328                                 /*put poly index in mf->v4*/
2329                                 mf[k].v4 = f->v1->hash;
2330                                 
2331                                 mf[k].mat_nr = mp->mat_nr;
2332                                 mf[k].flag = mp->flag;
2333                                 origIndex[k] = use_face_origindex ? k : f->v1->hash;
2334         
2335                                 k++;
2336                         }
2337         
2338                         BLI_end_edgefill();
2339                 }
2340         }
2341
2342         CustomData_free(fdata, totface);
2343         memset(fdata, 0, sizeof(CustomData));
2344         totface = k;
2345         
2346         CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mf, totface);
2347         CustomData_add_layer(fdata, CD_ORIGINDEX, CD_ASSIGN, origIndex, totface);
2348         CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
2349
2350         mface = mf;
2351         for (i=0; i<totface; i++, mf++) {
2352                 /*sort loop indices to ensure winding is correct*/
2353                 if (mf->v1 > mf->v2) SWAP(int, mf->v1, mf->v2);
2354                 if (mf->v2 > mf->v3) SWAP(int, mf->v2, mf->v3);
2355                 if (mf->v1 > mf->v2) SWAP(int, mf->v1, mf->v2);
2356
2357                 if (mf->v1 > mf->v2) SWAP(int, mf->v1, mf->v2);
2358                 if (mf->v2 > mf->v3) SWAP(int, mf->v2, mf->v3);
2359                 if (mf->v1 > mf->v2) SWAP(int, mf->v1, mf->v2);
2360         
2361                 lindex[0] = mf->v1;
2362                 lindex[1] = mf->v2;
2363                 lindex[2] = mf->v3;
2364
2365                 /*transform loop indices to vert indices*/
2366                 mf->v1 = mloop[mf->v1].v;
2367                 mf->v2 = mloop[mf->v2].v;
2368                 mf->v3 = mloop[mf->v3].v;
2369
2370                 mesh_loops_to_tri_corners(fdata, ldata, pdata,
2371                         lindex, i, mf->v4);
2372                 
2373                 mf->v4 = 0;
2374         }
2375
2376         return totface;
2377 }
2378
2379 /*
2380  * COMPUTE POLY NORMAL
2381  *
2382  * Computes the normal of a planar 
2383  * polygon See Graphics Gems for 
2384  * computing newell normal.
2385  *
2386 */
2387 static void mesh_calc_ngon_normal(MPoly *mpoly, MLoop *loopstart, 
2388                                   MVert *mvert, float *normal)
2389 {
2390
2391         MVert *v1, *v2, *v3;
2392         double u[3],  v[3], w[3];
2393         double n[3] = {0.0, 0.0, 0.0}, l;
2394         int i;
2395
2396         for(i = 0; i < mpoly->totloop; i++){
2397                 v1 = mvert + loopstart[i].v;
2398                 v2 = mvert + loopstart[(i+1)%mpoly->totloop].v;
2399                 v3 = mvert + loopstart[(i+2)%mpoly->totloop].v;
2400                 
2401                 VECCOPY(u, v1->co);
2402                 VECCOPY(v, v2->co);
2403                 VECCOPY(w, v3->co);
2404
2405                 /*this fixes some weird numerical error*/
2406                 if (i==0) {
2407                         u[0] += 0.0001f;
2408                         u[1] += 0.0001f;
2409                         u[2] += 0.0001f;
2410                 }
2411                 
2412                 /* newell's method
2413                 
2414                 so thats?:
2415                 (a[1] - b[1]) * (a[2] + b[2]);
2416                 a[1]*b[2] - b[1]*a[2] - b[1]*b[2] + a[1]*a[2]
2417
2418                 odd.  half of that is the cross product. . .what's the
2419                 other half?
2420
2421                 also could be like a[1]*(b[2] + a[2]) - b[1]*(a[2] - b[2])
2422                 */
2423
2424                 n[0] += (u[1] - v[1]) * (u[2] + v[2]);
2425                 n[1] += (u[2] - v[2]) * (u[0] + v[0]);
2426                 n[2] += (u[0] - v[0]) * (u[1] + v[1]);
2427         }
2428         
2429         l = n[0]*n[0]+n[1]*n[1]+n[2]*n[2];
2430         l = sqrt(l);
2431
2432         if (l == 0.0) {
2433                 normal[0] = 0.0f;
2434                 normal[1] = 0.0f;
2435                 normal[2] = 1.0f;
2436
2437                 return;
2438         } else l = 1.0f / l;
2439
2440         n[0] *= l;
2441         n[1] *= l;
2442         n[2] *= l;
2443         
2444         normal[0] = (float) n[0];
2445         normal[1] = (float) n[1];
2446         normal[2] = (float) n[2];
2447
2448 }
2449
2450 void mesh_calc_poly_normal(MPoly *mpoly, MLoop *loopstart, 
2451                            MVert *mvarray, float *no)
2452 {
2453         if(mpoly->totloop > 4) {
2454                 mesh_calc_ngon_normal(mpoly, loopstart, mvarray, no);
2455         }
2456         else if(mpoly->totloop == 3){
2457                 MVert *v1, *v2, *v3;
2458
2459                 v1 = mvarray + (loopstart++)->v;
2460                 v2 = mvarray + (loopstart++)->v;
2461                 v3 = mvarray + loopstart->v;
2462                 normal_tri_v3( no,v1->co, v2->co, v3->co);
2463         }
2464         else if(mpoly->totloop == 4){
2465                 MVert *v1, *v2, *v3, *v4;
2466
2467                 v1 = mvarray + (loopstart++)->v;
2468                 v2 = mvarray + (loopstart++)->v;
2469                 v3 = mvarray + (loopstart++)->v;
2470                 v4 = mvarray + loopstart->v;
2471                 normal_quad_v3( no,v1->co, v2->co, v3->co, v4->co);
2472         }
2473         else{ /*horrible, two sided face!*/
2474                 no[0] = 0.0;
2475                 no[1] = 0.0;
2476                 no[2] = 1.0;
2477         }
2478 }
2479
2480 /* basic vertex data functions */
2481 int minmax_mesh(Mesh *me, float min[3], float max[3])
2482 {
2483         int i= me->totvert;
2484         MVert *mvert;
2485         for(mvert= me->mvert; i--; mvert++) {
2486                 DO_MINMAX(mvert->co, min, max);
2487         }
2488         
2489         return (me->totvert != 0);
2490 }
2491
2492 int mesh_center_median(Mesh *me, float cent[3])
2493 {
2494         int i= me->totvert;
2495         MVert *mvert;
2496         zero_v3(cent);
2497         for(mvert= me->mvert; i--; mvert++) {
2498                 add_v3_v3(cent, mvert->co);
2499         }
2500         /* otherwise we get NAN for 0 verts */
2501         if(me->totvert) {
2502                 mul_v3_fl(cent, 1.0f/(float)me->totvert);
2503         }
2504
2505         return (me->totvert != 0);
2506 }
2507
2508 int mesh_center_bounds(Mesh *me, float cent[3])
2509 {
2510         float min[3], max[3];
2511         INIT_MINMAX(min, max);
2512         if(minmax_mesh(me, min, max)) {
2513                 mid_v3_v3v3(cent, min, max);
2514                 return 1;
2515         }
2516
2517         return 0;
2518 }
2519
2520 void mesh_translate(Mesh *me, float offset[3], int do_keys)
2521 {
2522         int i= me->totvert;
2523         MVert *mvert;
2524         for(mvert= me->mvert; i--; mvert++) {
2525                 add_v3_v3(mvert->co, offset);
2526         }
2527         
2528         if (do_keys && me->key) {
2529                 KeyBlock *kb;
2530                 for (kb=me->key->block.first; kb; kb=kb->next) {
2531                         float *fp= kb->data;
2532                         for (i= kb->totelem; i--; fp+=3) {
2533                                 add_v3_v3(fp, offset);
2534                         }
2535                 }
2536         }
2537 }