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