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