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