remove mesh PartialVisibility, it wasnt being version patches or used anywhere, other...
[blender-staging.git] / source / blender / blenkernel / intern / mesh.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * Contributor(s): Blender Foundation
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/blenkernel/intern/mesh.c
27  *  \ingroup bke
28  */
29
30
31 #include <stdlib.h>
32 #include <string.h>
33 #include <stdio.h>
34 #include <math.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "DNA_scene_types.h"
39 #include "DNA_material_types.h"
40 #include "DNA_object_types.h"
41 #include "DNA_key_types.h"
42 #include "DNA_meshdata_types.h"
43 #include "DNA_ipo_types.h"
44
45 #include "BLI_blenlib.h"
46 #include "BLI_bpath.h"
47 #include "BLI_editVert.h"
48 #include "BLI_math.h"
49 #include "BLI_edgehash.h"
50 #include "BLI_utildefines.h"
51
52 #include "BKE_animsys.h"
53 #include "BKE_main.h"
54 #include "BKE_DerivedMesh.h"
55 #include "BKE_global.h"
56 #include "BKE_mesh.h"
57 #include "BKE_displist.h"
58 #include "BKE_library.h"
59 #include "BKE_material.h"
60 #include "BKE_modifier.h"
61 #include "BKE_multires.h"
62 #include "BKE_key.h"
63 /* these 2 are only used by conversion functions */
64 #include "BKE_curve.h"
65 /* -- */
66 #include "BKE_object.h"
67
68
69 EditMesh *BKE_mesh_get_editmesh(Mesh *me)
70 {
71         return me->edit_mesh;
72 }
73
74 void BKE_mesh_end_editmesh(Mesh *UNUSED(me), EditMesh *UNUSED(em))
75 {
76 }
77
78
79 void mesh_update_customdata_pointers(Mesh *me)
80 {
81         me->mvert = CustomData_get_layer(&me->vdata, CD_MVERT);
82         me->dvert = CustomData_get_layer(&me->vdata, CD_MDEFORMVERT);
83         me->msticky = CustomData_get_layer(&me->vdata, CD_MSTICKY);
84
85         me->medge = CustomData_get_layer(&me->edata, CD_MEDGE);
86
87         me->mface = CustomData_get_layer(&me->fdata, CD_MFACE);
88         me->mcol = CustomData_get_layer(&me->fdata, CD_MCOL);
89         me->mtface = CustomData_get_layer(&me->fdata, CD_MTFACE);
90 }
91
92 /* Note: unlinking is called when me->id.us is 0, question remains how
93  * much unlinking of Library data in Mesh should be done... probably
94  * we need a more generic method, like the expand() functions in
95  * readfile.c */
96
97 void unlink_mesh(Mesh *me)
98 {
99         int a;
100         
101         if(me==NULL) return;
102         
103         for(a=0; a<me->totcol; a++) {
104                 if(me->mat[a]) me->mat[a]->id.us--;
105                 me->mat[a]= NULL;
106         }
107
108         if(me->key) {
109                 me->key->id.us--;
110         }
111         me->key= NULL;
112         
113         if(me->texcomesh) me->texcomesh= NULL;
114 }
115
116 /* do not free mesh itself */
117 void free_mesh(Mesh *me)
118 {
119         unlink_mesh(me);
120
121         CustomData_free(&me->vdata, me->totvert);
122         CustomData_free(&me->edata, me->totedge);
123         CustomData_free(&me->fdata, me->totface);
124         
125         if(me->adt) {
126                 BKE_free_animdata(&me->id);
127                 me->adt= NULL;
128         }
129         
130         if(me->mat) MEM_freeN(me->mat);
131         
132         if(me->bb) MEM_freeN(me->bb);
133         if(me->mselect) MEM_freeN(me->mselect);
134         if(me->edit_mesh) MEM_freeN(me->edit_mesh);
135 }
136
137 void copy_dverts(MDeformVert *dst, MDeformVert *src, int copycount)
138 {
139         /* Assumes dst is already set up */
140         int i;
141
142         if (!src || !dst)
143                 return;
144
145         memcpy (dst, src, copycount * sizeof(MDeformVert));
146         
147         for (i=0; i<copycount; i++){
148                 if (src[i].dw){
149                         dst[i].dw = MEM_callocN (sizeof(MDeformWeight)*src[i].totweight, "copy_deformWeight");
150                         memcpy (dst[i].dw, src[i].dw, sizeof (MDeformWeight)*src[i].totweight);
151                 }
152         }
153
154 }
155
156 void free_dverts(MDeformVert *dvert, int totvert)
157 {
158         /* Instead of freeing the verts directly,
159         call this function to delete any special
160         vert data */
161         int     i;
162
163         if (!dvert)
164                 return;
165
166         /* Free any special data from the verts */
167         for (i=0; i<totvert; i++){
168                 if (dvert[i].dw) MEM_freeN (dvert[i].dw);
169         }
170         MEM_freeN (dvert);
171 }
172
173 Mesh *add_mesh(const char *name)
174 {
175         Mesh *me;
176         
177         me= alloc_libblock(&G.main->mesh, ID_ME, name);
178         
179         me->size[0]= me->size[1]= me->size[2]= 1.0;
180         me->smoothresh= 30;
181         me->texflag= AUTOSPACE;
182         me->flag= ME_TWOSIDED;
183         me->bb= unit_boundbox();
184         me->drawflag= ME_DRAWEDGES|ME_DRAWFACES|ME_DRAWCREASES;
185         
186         return me;
187 }
188
189 Mesh *copy_mesh(Mesh *me)
190 {
191         Mesh *men;
192         MTFace *tface;
193         int a, i;
194         
195         men= copy_libblock(&me->id);
196         
197         men->mat= MEM_dupallocN(me->mat);
198         for(a=0; a<men->totcol; a++) {
199                 id_us_plus((ID *)men->mat[a]);
200         }
201         id_us_plus((ID *)men->texcomesh);
202
203         CustomData_copy(&me->vdata, &men->vdata, CD_MASK_MESH, CD_DUPLICATE, men->totvert);
204         CustomData_copy(&me->edata, &men->edata, CD_MASK_MESH, CD_DUPLICATE, men->totedge);
205         CustomData_copy(&me->fdata, &men->fdata, CD_MASK_MESH, CD_DUPLICATE, men->totface);
206         mesh_update_customdata_pointers(men);
207
208         /* ensure indirect linked data becomes lib-extern */
209         for(i=0; i<me->fdata.totlayer; i++) {
210                 if(me->fdata.layers[i].type == CD_MTFACE) {
211                         tface= (MTFace*)me->fdata.layers[i].data;
212
213                         for(a=0; a<me->totface; a++, tface++)
214                                 if(tface->tpage)
215                                         id_lib_extern((ID*)tface->tpage);
216                 }
217         }
218         
219         men->mselect= NULL;
220         men->edit_mesh= NULL;
221
222         men->bb= MEM_dupallocN(men->bb);
223         
224         men->key= copy_key(me->key);
225         if(men->key) men->key->from= (ID *)men;
226
227         return men;
228 }
229
230 static void expand_local_mesh(Mesh *me)
231 {
232         id_lib_extern((ID *)me->texcomesh);
233
234         if(me->mtface) {
235                 MTFace *tface;
236                 int a, i;
237
238                 for(i=0; i<me->fdata.totlayer; i++) {
239                         if(me->fdata.layers[i].type == CD_MTFACE) {
240                                 tface= (MTFace*)me->fdata.layers[i].data;
241
242                                 for(a=0; a<me->totface; a++, tface++) {
243                                         if(tface->tpage) {
244                                                 id_lib_extern((ID *)tface->tpage);
245                                         }
246                                 }
247                         }
248                 }
249         }
250
251         if(me->mat) {
252                 extern_local_matarar(me->mat, me->totcol);
253         }
254 }
255
256 void make_local_mesh(Mesh *me)
257 {
258         Main *bmain= G.main;
259         Object *ob;
260         int is_local= FALSE, is_lib= FALSE;
261
262         /* - only lib users: do nothing
263          * - only local users: set flag
264          * - mixed: make copy
265          */
266
267         if(me->id.lib==NULL) return;
268         if(me->id.us==1) {
269                 id_clear_lib_data(bmain, &me->id);
270                 expand_local_mesh(me);
271                 return;
272         }
273
274         for(ob= bmain->object.first; ob && ELEM(0, is_lib, is_local); ob= ob->id.next) {
275                 if(me == ob->data) {
276                         if(ob->id.lib) is_lib= TRUE;
277                         else is_local= TRUE;
278                 }
279         }
280
281         if(is_local && is_lib == FALSE) {
282                 id_clear_lib_data(bmain, &me->id);
283                 expand_local_mesh(me);
284         }
285         else if(is_local && is_lib) {
286                 Mesh *me_new= copy_mesh(me);
287                 me_new->id.us= 0;
288
289
290                 /* Remap paths of new ID using old library as base. */
291                 BKE_id_lib_local_paths(bmain, me->id.lib, &me_new->id);
292
293                 for(ob= bmain->object.first; ob; ob= ob->id.next) {
294                         if(me == ob->data) {
295                                 if(ob->id.lib==NULL) {
296                                         set_mesh(ob, me_new);
297                                 }
298                         }
299                 }
300         }
301 }
302
303 void boundbox_mesh(Mesh *me, float *loc, float *size)
304 {
305         BoundBox *bb;
306         float min[3], max[3];
307         float mloc[3], msize[3];
308         
309         if(me->bb==NULL) me->bb= MEM_callocN(sizeof(BoundBox), "boundbox");
310         bb= me->bb;
311
312         if (!loc) loc= mloc;
313         if (!size) size= msize;
314         
315         INIT_MINMAX(min, max);
316         if(!minmax_mesh(me, min, max)) {
317                 min[0] = min[1] = min[2] = -1.0f;
318                 max[0] = max[1] = max[2] = 1.0f;
319         }
320
321         mid_v3_v3v3(loc, min, max);
322                 
323         size[0]= (max[0]-min[0])/2.0f;
324         size[1]= (max[1]-min[1])/2.0f;
325         size[2]= (max[2]-min[2])/2.0f;
326         
327         boundbox_set_from_min_max(bb, min, max);
328 }
329
330 void tex_space_mesh(Mesh *me)
331 {
332         float loc[3], size[3];
333         int a;
334
335         boundbox_mesh(me, loc, size);
336
337         if(me->texflag & AUTOSPACE) {
338                 for (a=0; a<3; a++) {
339                         if(size[a]==0.0f) size[a]= 1.0f;
340                         else if(size[a]>0.0f && size[a]<0.00001f) size[a]= 0.00001f;
341                         else if(size[a]<0.0f && size[a]> -0.00001f) size[a]= -0.00001f;
342                 }
343
344                 copy_v3_v3(me->loc, loc);
345                 copy_v3_v3(me->size, size);
346                 zero_v3(me->rot);
347         }
348 }
349
350 BoundBox *mesh_get_bb(Object *ob)
351 {
352         Mesh *me= ob->data;
353
354         if(ob->bb)
355                 return ob->bb;
356
357         if (!me->bb)
358                 tex_space_mesh(me);
359
360         return me->bb;
361 }
362
363 void mesh_get_texspace(Mesh *me, float *loc_r, float *rot_r, float *size_r)
364 {
365         if (!me->bb) {
366                 tex_space_mesh(me);
367         }
368
369         if (loc_r) VECCOPY(loc_r, me->loc);
370         if (rot_r) VECCOPY(rot_r, me->rot);
371         if (size_r) VECCOPY(size_r, me->size);
372 }
373
374 float *get_mesh_orco_verts(Object *ob)
375 {
376         Mesh *me = ob->data;
377         MVert *mvert = NULL;
378         Mesh *tme = me->texcomesh?me->texcomesh:me;
379         int a, totvert;
380         float (*vcos)[3] = NULL;
381
382         /* Get appropriate vertex coordinates */
383         vcos = MEM_callocN(sizeof(*vcos)*me->totvert, "orco mesh");
384         mvert = tme->mvert;
385         totvert = MIN2(tme->totvert, me->totvert);
386
387         for(a=0; a<totvert; a++, mvert++) {
388                 copy_v3_v3(vcos[a], mvert->co);
389         }
390
391         return (float*)vcos;
392 }
393
394 void transform_mesh_orco_verts(Mesh *me, float (*orco)[3], int totvert, int invert)
395 {
396         float loc[3], size[3];
397         int a;
398
399         mesh_get_texspace(me->texcomesh?me->texcomesh:me, loc, NULL, size);
400
401         if(invert) {
402                 for(a=0; a<totvert; a++) {
403                         float *co = orco[a];
404                         madd_v3_v3v3v3(co, loc, co, size);
405                 }
406         }
407         else {
408                 for(a=0; a<totvert; a++) {
409                         float *co = orco[a];
410                         co[0] = (co[0]-loc[0])/size[0];
411                         co[1] = (co[1]-loc[1])/size[1];
412                         co[2] = (co[2]-loc[2])/size[2];
413                 }
414         }
415 }
416
417 /* rotates the vertices of a face in case v[2] or v[3] (vertex index) is = 0.
418    this is necessary to make the if(mface->v4) check for quads work */
419 int test_index_face(MFace *mface, CustomData *fdata, int mfindex, int nr)
420 {
421         /* first test if the face is legal */
422         if((mface->v3 || nr==4) && mface->v3==mface->v4) {
423                 mface->v4= 0;
424                 nr--;
425         }
426         if((mface->v2 || mface->v4) && mface->v2==mface->v3) {
427                 mface->v3= mface->v4;
428                 mface->v4= 0;
429                 nr--;
430         }
431         if(mface->v1==mface->v2) {
432                 mface->v2= mface->v3;
433                 mface->v3= mface->v4;
434                 mface->v4= 0;
435                 nr--;
436         }
437
438         /* check corrupt cases, bowtie geometry, cant handle these because edge data wont exist so just return 0 */
439         if(nr==3) {
440                 if(
441                 /* real edges */
442                         mface->v1==mface->v2 ||
443                         mface->v2==mface->v3 ||
444                         mface->v3==mface->v1
445                 ) {
446                         return 0;
447                 }
448         }
449         else if(nr==4) {
450                 if(
451                 /* real edges */
452                         mface->v1==mface->v2 ||
453                         mface->v2==mface->v3 ||
454                         mface->v3==mface->v4 ||
455                         mface->v4==mface->v1 ||
456                 /* across the face */
457                         mface->v1==mface->v3 ||
458                         mface->v2==mface->v4
459                 ) {
460                         return 0;
461                 }
462         }
463
464         /* prevent a zero at wrong index location */
465         if(nr==3) {
466                 if(mface->v3==0) {
467                         static int corner_indices[4] = {1, 2, 0, 3};
468
469                         SWAP(int, mface->v1, mface->v2);
470                         SWAP(int, mface->v2, mface->v3);
471
472                         if(fdata)
473                                 CustomData_swap(fdata, mfindex, corner_indices);
474                 }
475         }
476         else if(nr==4) {
477                 if(mface->v3==0 || mface->v4==0) {
478                         static int corner_indices[4] = {2, 3, 0, 1};
479
480                         SWAP(int, mface->v1, mface->v3);
481                         SWAP(int, mface->v2, mface->v4);
482
483                         if(fdata)
484                                 CustomData_swap(fdata, mfindex, corner_indices);
485                 }
486         }
487
488         return nr;
489 }
490
491 Mesh *get_mesh(Object *ob)
492 {
493         
494         if(ob==NULL) return NULL;
495         if(ob->type==OB_MESH) return ob->data;
496         else return NULL;
497 }
498
499 void set_mesh(Object *ob, Mesh *me)
500 {
501         Mesh *old=NULL;
502
503         multires_force_update(ob);
504         
505         if(ob==NULL) return;
506         
507         if(ob->type==OB_MESH) {
508                 old= ob->data;
509                 if (old)
510                         old->id.us--;
511                 ob->data= me;
512                 id_us_plus((ID *)me);
513         }
514         
515         test_object_materials((ID *)me);
516
517         test_object_modifiers(ob);
518 }
519
520 /* ************** make edges in a Mesh, for outside of editmode */
521
522 struct edgesort {
523         int v1, v2;
524         short is_loose, is_draw;
525 };
526
527 /* edges have to be added with lowest index first for sorting */
528 static void to_edgesort(struct edgesort *ed, int v1, int v2, short is_loose, short is_draw)
529 {
530         if(v1<v2) {
531                 ed->v1= v1; ed->v2= v2;
532         }
533         else {
534                 ed->v1= v2; ed->v2= v1;
535         }
536         ed->is_loose= is_loose;
537         ed->is_draw= is_draw;
538 }
539
540 static int vergedgesort(const void *v1, const void *v2)
541 {
542         const struct edgesort *x1=v1, *x2=v2;
543
544         if( x1->v1 > x2->v1) return 1;
545         else if( x1->v1 < x2->v1) return -1;
546         else if( x1->v2 > x2->v2) return 1;
547         else if( x1->v2 < x2->v2) return -1;
548         
549         return 0;
550 }
551
552 static void mfaces_strip_loose(MFace *mface, int *totface)
553 {
554         int a,b;
555
556         for (a=b=0; a<*totface; a++) {
557                 if (mface[a].v3) {
558                         if (a!=b) {
559                                 memcpy(&mface[b],&mface[a],sizeof(mface[b]));
560                         }
561                         b++;
562                 }
563         }
564
565         *totface= b;
566 }
567
568 /* Create edges based on known verts and faces */
569 static void make_edges_mdata(MVert *UNUSED(allvert), MFace *allface, int UNUSED(totvert), int totface,
570         int old, MEdge **alledge, int *_totedge)
571 {
572         MFace *mface;
573         MEdge *medge;
574         struct edgesort *edsort, *ed;
575         int a, totedge=0, final=0;
576
577         /* we put all edges in array, sort them, and detect doubles that way */
578
579         for(a= totface, mface= allface; a>0; a--, mface++) {
580                 if(mface->v4) totedge+=4;
581                 else if(mface->v3) totedge+=3;
582                 else totedge+=1;
583         }
584
585         if(totedge==0) {
586                 /* flag that mesh has edges */
587                 (*alledge)= MEM_callocN(0, "make mesh edges");
588                 (*_totedge) = 0;
589                 return;
590         }
591
592         ed= edsort= MEM_mallocN(totedge*sizeof(struct edgesort), "edgesort");
593
594         for(a= totface, mface= allface; a>0; a--, mface++) {
595                 to_edgesort(ed++, mface->v1, mface->v2, !mface->v3, mface->edcode & ME_V1V2);
596                 if(mface->v4) {
597                         to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
598                         to_edgesort(ed++, mface->v3, mface->v4, 0, mface->edcode & ME_V3V4);
599                         to_edgesort(ed++, mface->v4, mface->v1, 0, mface->edcode & ME_V4V1);
600                 }
601                 else if(mface->v3) {
602                         to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
603                         to_edgesort(ed++, mface->v3, mface->v1, 0, mface->edcode & ME_V3V1);
604                 }
605         }
606
607         qsort(edsort, totedge, sizeof(struct edgesort), vergedgesort);
608
609         /* count final amount */
610         for(a=totedge, ed=edsort; a>1; a--, ed++) {
611                 /* edge is unique when it differs from next edge, or is last */
612                 if(ed->v1 != (ed+1)->v1 || ed->v2 != (ed+1)->v2) final++;
613         }
614         final++;
615
616         (*alledge)= medge= MEM_callocN(sizeof (MEdge) * final, "make_edges mdge");
617         (*_totedge)= final;
618
619         for(a=totedge, ed=edsort; a>1; a--, ed++) {
620                 /* edge is unique when it differs from next edge, or is last */
621                 if(ed->v1 != (ed+1)->v1 || ed->v2 != (ed+1)->v2) {
622                         medge->v1= ed->v1;
623                         medge->v2= ed->v2;
624                         if(old==0 || ed->is_draw) medge->flag= ME_EDGEDRAW|ME_EDGERENDER;
625                         if(ed->is_loose) medge->flag|= ME_LOOSEEDGE;
626
627                         /* order is swapped so extruding this edge as a surface wont flip face normals
628                          * with cyclic curves */
629                         if(ed->v1+1 != ed->v2) {
630                                 SWAP(int, medge->v1, medge->v2);
631                         }
632                         medge++;
633                 }
634                 else {
635                         /* equal edge, we merge the drawflag */
636                         (ed+1)->is_draw |= ed->is_draw;
637                 }
638         }
639         /* last edge */
640         medge->v1= ed->v1;
641         medge->v2= ed->v2;
642         medge->flag= ME_EDGEDRAW;
643         if(ed->is_loose) medge->flag|= ME_LOOSEEDGE;
644         medge->flag |= ME_EDGERENDER;
645
646         MEM_freeN(edsort);
647 }
648
649 void make_edges(Mesh *me, int old)
650 {
651         MEdge *medge;
652         int totedge=0;
653
654         make_edges_mdata(me->mvert, me->mface, me->totvert, me->totface, old, &medge, &totedge);
655         if(totedge==0) {
656                 /* flag that mesh has edges */
657                 me->medge = medge;
658                 me->totedge = 0;
659                 return;
660         }
661
662         medge= CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, medge, totedge);
663         me->medge= medge;
664         me->totedge= totedge;
665
666         mesh_strip_loose_faces(me);
667 }
668
669 void mesh_strip_loose_faces(Mesh *me)
670 {
671         int a,b;
672
673         for (a=b=0; a<me->totface; a++) {
674                 if (me->mface[a].v3) {
675                         if (a!=b) {
676                                 memcpy(&me->mface[b],&me->mface[a],sizeof(me->mface[b]));
677                                 CustomData_copy_data(&me->fdata, &me->fdata, a, b, 1);
678                                 CustomData_free_elem(&me->fdata, a, 1);
679                         }
680                         b++;
681                 }
682         }
683         me->totface = b;
684 }
685
686 void mesh_strip_loose_edges(Mesh *me)
687 {
688         int a,b;
689
690         for (a=b=0; a<me->totedge; a++) {
691                 if (me->medge[a].v1!=me->medge[a].v2) {
692                         if (a!=b) {
693                                 memcpy(&me->medge[b],&me->medge[a],sizeof(me->medge[b]));
694                                 CustomData_copy_data(&me->edata, &me->edata, a, b, 1);
695                                 CustomData_free_elem(&me->edata, a, 1);
696                         }
697                         b++;
698                 }
699         }
700         me->totedge = b;
701 }
702
703 void mball_to_mesh(ListBase *lb, Mesh *me)
704 {
705         DispList *dl;
706         MVert *mvert;
707         MFace *mface;
708         float *nors, *verts;
709         int a, *index;
710         
711         dl= lb->first;
712         if(dl==NULL) return;
713
714         if(dl->type==DL_INDEX4) {
715                 me->totvert= dl->nr;
716                 me->totface= dl->parts;
717                 
718                 mvert= CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, dl->nr);
719                 mface= CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, dl->parts);
720                 me->mvert= mvert;
721                 me->mface= mface;
722
723                 a= dl->nr;
724                 nors= dl->nors;
725                 verts= dl->verts;
726                 while(a--) {
727                         VECCOPY(mvert->co, verts);
728                         normal_float_to_short_v3(mvert->no, nors);
729                         mvert++;
730                         nors+= 3;
731                         verts+= 3;
732                 }
733                 
734                 a= dl->parts;
735                 index= dl->index;
736                 while(a--) {
737                         mface->v1= index[0];
738                         mface->v2= index[1];
739                         mface->v3= index[2];
740                         mface->v4= index[3];
741                         mface->flag= ME_SMOOTH;
742
743                         test_index_face(mface, NULL, 0, (mface->v3==mface->v4)? 3: 4);
744
745                         mface++;
746                         index+= 4;
747                 }
748
749                 make_edges(me, 0);      // all edges
750         }       
751 }
752
753 /* Initialize mverts, medges and, faces for converting nurbs to mesh and derived mesh */
754 /* return non-zero on error */
755 int nurbs_to_mdata(Object *ob, MVert **allvert, int *totvert,
756         MEdge **alledge, int *totedge, MFace **allface, int *totface)
757 {
758         return nurbs_to_mdata_customdb(ob, &ob->disp,
759                 allvert, totvert, alledge, totedge, allface, totface);
760 }
761
762 /* Initialize mverts, medges and, faces for converting nurbs to mesh and derived mesh */
763 /* use specified dispbase  */
764 int nurbs_to_mdata_customdb(Object *ob, ListBase *dispbase, MVert **allvert, int *_totvert,
765         MEdge **alledge, int *_totedge, MFace **allface, int *_totface)
766 {
767         DispList *dl;
768         Curve *cu;
769         MVert *mvert;
770         MFace *mface;
771         float *data;
772         int a, b, ofs, vertcount, startvert, totvert=0, totvlak=0;
773         int p1, p2, p3, p4, *index;
774         int conv_polys= 0;
775
776         cu= ob->data;
777
778         conv_polys|= cu->flag & CU_3D;          /* 2d polys are filled with DL_INDEX3 displists */
779         conv_polys|= ob->type == OB_SURF;       /* surf polys are never filled */
780
781         /* count */
782         dl= dispbase->first;
783         while(dl) {
784                 if(dl->type==DL_SEGM) {
785                         totvert+= dl->parts*dl->nr;
786                         totvlak+= dl->parts*(dl->nr-1);
787                 }
788                 else if(dl->type==DL_POLY) {
789                         if(conv_polys) {
790                                 totvert+= dl->parts*dl->nr;
791                                 totvlak+= dl->parts*dl->nr;
792                         }
793                 }
794                 else if(dl->type==DL_SURF) {
795                         totvert+= dl->parts*dl->nr;
796                         totvlak+= (dl->parts-1+((dl->flag & DL_CYCL_V)==2))*(dl->nr-1+(dl->flag & DL_CYCL_U));
797                 }
798                 else if(dl->type==DL_INDEX3) {
799                         totvert+= dl->nr;
800                         totvlak+= dl->parts;
801                 }
802                 dl= dl->next;
803         }
804
805         if(totvert==0) {
806                 /* error("can't convert"); */
807                 /* Make Sure you check ob->data is a curve */
808                 return -1;
809         }
810
811         *allvert= mvert= MEM_callocN(sizeof (MVert) * totvert, "nurbs_init mvert");
812         *allface= mface= MEM_callocN(sizeof (MFace) * totvlak, "nurbs_init mface");
813
814         /* verts and faces */
815         vertcount= 0;
816
817         dl= dispbase->first;
818         while(dl) {
819                 int smooth= dl->rt & CU_SMOOTH ? 1 : 0;
820
821                 if(dl->type==DL_SEGM) {
822                         startvert= vertcount;
823                         a= dl->parts*dl->nr;
824                         data= dl->verts;
825                         while(a--) {
826                                 VECCOPY(mvert->co, data);
827                                 data+=3;
828                                 vertcount++;
829                                 mvert++;
830                         }
831
832                         for(a=0; a<dl->parts; a++) {
833                                 ofs= a*dl->nr;
834                                 for(b=1; b<dl->nr; b++) {
835                                         mface->v1= startvert+ofs+b-1;
836                                         mface->v2= startvert+ofs+b;
837                                         if(smooth) mface->flag |= ME_SMOOTH;
838                                         mface++;
839                                 }
840                         }
841
842                 }
843                 else if(dl->type==DL_POLY) {
844                         if(conv_polys) {
845                                 startvert= vertcount;
846                                 a= dl->parts*dl->nr;
847                                 data= dl->verts;
848                                 while(a--) {
849                                         VECCOPY(mvert->co, data);
850                                         data+=3;
851                                         vertcount++;
852                                         mvert++;
853                                 }
854
855                                 for(a=0; a<dl->parts; a++) {
856                                         ofs= a*dl->nr;
857                                         for(b=0; b<dl->nr; b++) {
858                                                 mface->v1= startvert+ofs+b;
859                                                 if(b==dl->nr-1) mface->v2= startvert+ofs;
860                                                 else mface->v2= startvert+ofs+b+1;
861                                                 if(smooth) mface->flag |= ME_SMOOTH;
862                                                 mface++;
863                                         }
864                                 }
865                         }
866                 }
867                 else if(dl->type==DL_INDEX3) {
868                         startvert= vertcount;
869                         a= dl->nr;
870                         data= dl->verts;
871                         while(a--) {
872                                 VECCOPY(mvert->co, data);
873                                 data+=3;
874                                 vertcount++;
875                                 mvert++;
876                         }
877
878                         a= dl->parts;
879                         index= dl->index;
880                         while(a--) {
881                                 mface->v1= startvert+index[0];
882                                 mface->v2= startvert+index[2];
883                                 mface->v3= startvert+index[1];
884                                 mface->v4= 0;
885                                 mface->mat_nr= dl->col;
886                                 test_index_face(mface, NULL, 0, 3);
887
888                                 if(smooth) mface->flag |= ME_SMOOTH;
889                                 mface++;
890                                 index+= 3;
891                         }
892
893
894                 }
895                 else if(dl->type==DL_SURF) {
896                         startvert= vertcount;
897                         a= dl->parts*dl->nr;
898                         data= dl->verts;
899                         while(a--) {
900                                 VECCOPY(mvert->co, data);
901                                 data+=3;
902                                 vertcount++;
903                                 mvert++;
904                         }
905
906                         for(a=0; a<dl->parts; a++) {
907
908                                 if( (dl->flag & DL_CYCL_V)==0 && a==dl->parts-1) break;
909
910                                 if(dl->flag & DL_CYCL_U) {                      /* p2 -> p1 -> */
911                                         p1= startvert+ dl->nr*a;        /* p4 -> p3 -> */
912                                         p2= p1+ dl->nr-1;               /* -----> next row */
913                                         p3= p1+ dl->nr;
914                                         p4= p2+ dl->nr;
915                                         b= 0;
916                                 }
917                                 else {
918                                         p2= startvert+ dl->nr*a;
919                                         p1= p2+1;
920                                         p4= p2+ dl->nr;
921                                         p3= p1+ dl->nr;
922                                         b= 1;
923                                 }
924                                 if( (dl->flag & DL_CYCL_V) && a==dl->parts-1) {
925                                         p3-= dl->parts*dl->nr;
926                                         p4-= dl->parts*dl->nr;
927                                 }
928
929                                 for(; b<dl->nr; b++) {
930                                         mface->v1= p1;
931                                         mface->v2= p3;
932                                         mface->v3= p4;
933                                         mface->v4= p2;
934                                         mface->mat_nr= dl->col;
935                                         test_index_face(mface, NULL, 0, 4);
936
937                                         if(smooth) mface->flag |= ME_SMOOTH;
938                                         mface++;
939
940                                         p4= p3;
941                                         p3++;
942                                         p2= p1;
943                                         p1++;
944                                 }
945                         }
946
947                 }
948
949                 dl= dl->next;
950         }
951
952         *_totvert= totvert;
953         *_totface= totvlak;
954
955         make_edges_mdata(*allvert, *allface, totvert, totvlak, 0, alledge, _totedge);
956         mfaces_strip_loose(*allface, _totface);
957
958         return 0;
959 }
960
961 /* this may fail replacing ob->data, be sure to check ob->type */
962 void nurbs_to_mesh(Object *ob)
963 {
964         Main *bmain= G.main;
965         Object *ob1;
966         DerivedMesh *dm= ob->derivedFinal;
967         Mesh *me;
968         Curve *cu;
969         MVert *allvert= NULL;
970         MEdge *alledge= NULL;
971         MFace *allface= NULL;
972         int totvert, totedge, totface;
973
974         cu= ob->data;
975
976         if (dm == NULL) {
977                 if (nurbs_to_mdata (ob, &allvert, &totvert, &alledge, &totedge, &allface, &totface) != 0) {
978                         /* Error initializing */
979                         return;
980                 }
981
982                 /* make mesh */
983                 me= add_mesh("Mesh");
984                 me->totvert= totvert;
985                 me->totface= totface;
986                 me->totedge= totedge;
987
988                 me->mvert= CustomData_add_layer(&me->vdata, CD_MVERT, CD_ASSIGN, allvert, me->totvert);
989                 me->mface= CustomData_add_layer(&me->fdata, CD_MFACE, CD_ASSIGN, allface, me->totface);
990                 me->medge= CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, alledge, me->totedge);
991
992                 mesh_calc_normals(me->mvert, me->totvert, me->mface, me->totface, NULL);
993         } else {
994                 me= add_mesh("Mesh");
995                 DM_to_mesh(dm, me);
996         }
997
998         me->totcol= cu->totcol;
999         me->mat= cu->mat;
1000
1001         tex_space_mesh(me);
1002
1003         cu->mat= NULL;
1004         cu->totcol= 0;
1005
1006         if(ob->data) {
1007                 free_libblock(&bmain->curve, ob->data);
1008         }
1009         ob->data= me;
1010         ob->type= OB_MESH;
1011
1012         /* other users */
1013         ob1= bmain->object.first;
1014         while(ob1) {
1015                 if(ob1->data==cu) {
1016                         ob1->type= OB_MESH;
1017                 
1018                         ob1->data= ob->data;
1019                         id_us_plus((ID *)ob->data);
1020                 }
1021                 ob1= ob1->id.next;
1022         }
1023 }
1024
1025 typedef struct EdgeLink {
1026         Link *next, *prev;
1027         void *edge;
1028 } EdgeLink;
1029
1030 typedef struct VertLink {
1031         Link *next, *prev;
1032         int index;
1033 } VertLink;
1034
1035 static void prependPolyLineVert(ListBase *lb, int index)
1036 {
1037         VertLink *vl= MEM_callocN(sizeof(VertLink), "VertLink");
1038         vl->index = index;
1039         BLI_addhead(lb, vl);
1040 }
1041
1042 static void appendPolyLineVert(ListBase *lb, int index)
1043 {
1044         VertLink *vl= MEM_callocN(sizeof(VertLink), "VertLink");
1045         vl->index = index;
1046         BLI_addtail(lb, vl);
1047 }
1048
1049 void mesh_to_curve(Scene *scene, Object *ob)
1050 {
1051         /* make new mesh data from the original copy */
1052         DerivedMesh *dm= mesh_get_derived_final(scene, ob, CD_MASK_MESH);
1053
1054         MVert *mverts= dm->getVertArray(dm);
1055         MEdge *med, *medge= dm->getEdgeArray(dm);
1056         MFace *mf,  *mface= dm->getFaceArray(dm);
1057
1058         int totedge = dm->getNumEdges(dm);
1059         int totface = dm->getNumFaces(dm);
1060         int totedges = 0;
1061         int i, needsFree = 0;
1062
1063         /* only to detect edge polylines */
1064         EdgeHash *eh = BLI_edgehash_new();
1065         EdgeHash *eh_edge = BLI_edgehash_new();
1066
1067
1068         ListBase edges = {NULL, NULL};
1069
1070         /* create edges from all faces (so as to find edges not in any faces) */
1071         mf= mface;
1072         for (i = 0; i < totface; i++, mf++) {
1073                 if (!BLI_edgehash_haskey(eh, mf->v1, mf->v2))
1074                         BLI_edgehash_insert(eh, mf->v1, mf->v2, NULL);
1075                 if (!BLI_edgehash_haskey(eh, mf->v2, mf->v3))
1076                         BLI_edgehash_insert(eh, mf->v2, mf->v3, NULL);
1077
1078                 if (mf->v4) {
1079                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v4))
1080                                 BLI_edgehash_insert(eh, mf->v3, mf->v4, NULL);
1081                         if (!BLI_edgehash_haskey(eh, mf->v4, mf->v1))
1082                                 BLI_edgehash_insert(eh, mf->v4, mf->v1, NULL);
1083                 } else {
1084                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v1))
1085                                 BLI_edgehash_insert(eh, mf->v3, mf->v1, NULL);
1086                 }
1087         }
1088
1089         med= medge;
1090         for(i=0; i<totedge; i++, med++) {
1091                 if (!BLI_edgehash_haskey(eh, med->v1, med->v2)) {
1092                         EdgeLink *edl= MEM_callocN(sizeof(EdgeLink), "EdgeLink");
1093
1094                         BLI_edgehash_insert(eh_edge, med->v1, med->v2, NULL);
1095                         edl->edge= med;
1096
1097                         BLI_addtail(&edges, edl);       totedges++;
1098                 }
1099         }
1100         BLI_edgehash_free(eh_edge, NULL);
1101         BLI_edgehash_free(eh, NULL);
1102
1103         if(edges.first) {
1104                 Curve *cu = add_curve(ob->id.name+2, OB_CURVE);
1105                 cu->flag |= CU_3D;
1106
1107                 while(edges.first) {
1108                         /* each iteration find a polyline and add this as a nurbs poly spline */
1109
1110                         ListBase polyline = {NULL, NULL}; /* store a list of VertLink's */
1111                         int closed = FALSE;
1112                         int totpoly= 0;
1113                         MEdge *med_current= ((EdgeLink *)edges.last)->edge;
1114                         int startVert= med_current->v1;
1115                         int endVert= med_current->v2;
1116                         int ok= TRUE;
1117
1118                         appendPolyLineVert(&polyline, startVert);       totpoly++;
1119                         appendPolyLineVert(&polyline, endVert);         totpoly++;
1120                         BLI_freelinkN(&edges, edges.last);                      totedges--;
1121
1122                         while(ok) { /* while connected edges are found... */
1123                                 ok = FALSE;
1124                                 i= totedges;
1125                                 while(i) {
1126                                         EdgeLink *edl;
1127
1128                                         i-=1;
1129                                         edl= BLI_findlink(&edges, i);
1130                                         med= edl->edge;
1131
1132                                         if(med->v1==endVert) {
1133                                                 endVert = med->v2;
1134                                                 appendPolyLineVert(&polyline, med->v2); totpoly++;
1135                                                 BLI_freelinkN(&edges, edl);                             totedges--;
1136                                                 ok= TRUE;
1137                                         }
1138                                         else if(med->v2==endVert) {
1139                                                 endVert = med->v1;
1140                                                 appendPolyLineVert(&polyline, endVert); totpoly++;
1141                                                 BLI_freelinkN(&edges, edl);                             totedges--;
1142                                                 ok= TRUE;
1143                                         }
1144                                         else if(med->v1==startVert) {
1145                                                 startVert = med->v2;
1146                                                 prependPolyLineVert(&polyline, startVert);      totpoly++;
1147                                                 BLI_freelinkN(&edges, edl);                                     totedges--;
1148                                                 ok= TRUE;
1149                                         }
1150                                         else if(med->v2==startVert) {
1151                                                 startVert = med->v1;
1152                                                 prependPolyLineVert(&polyline, startVert);      totpoly++;
1153                                                 BLI_freelinkN(&edges, edl);                                     totedges--;
1154                                                 ok= TRUE;
1155                                         }
1156                                 }
1157                         }
1158
1159                         /* Now we have a polyline, make into a curve */
1160                         if(startVert==endVert) {
1161                                 BLI_freelinkN(&polyline, polyline.last);
1162                                 totpoly--;
1163                                 closed = TRUE;
1164                         }
1165
1166                         /* --- nurbs --- */
1167                         {
1168                                 Nurb *nu;
1169                                 BPoint *bp;
1170                                 VertLink *vl;
1171
1172                                 /* create new 'nurb' within the curve */
1173                                 nu = (Nurb *)MEM_callocN(sizeof(Nurb), "MeshNurb");
1174
1175                                 nu->pntsu= totpoly;
1176                                 nu->pntsv= 1;
1177                                 nu->orderu= 4;
1178                                 nu->flagu= CU_NURB_ENDPOINT | (closed ? CU_NURB_CYCLIC:0);      /* endpoint */
1179                                 nu->resolu= 12;
1180
1181                                 nu->bp= (BPoint *)MEM_callocN(sizeof(BPoint)*totpoly, "bpoints");
1182
1183                                 /* add points */
1184                                 vl= polyline.first;
1185                                 for (i=0, bp=nu->bp; i < totpoly; i++, bp++, vl=(VertLink *)vl->next) {
1186                                         copy_v3_v3(bp->vec, mverts[vl->index].co);
1187                                         bp->f1= SELECT;
1188                                         bp->radius = bp->weight = 1.0;
1189                                 }
1190                                 BLI_freelistN(&polyline);
1191
1192                                 /* add nurb to curve */
1193                                 BLI_addtail(&cu->nurb, nu);
1194                         }
1195                         /* --- done with nurbs --- */
1196                 }
1197
1198                 ((Mesh *)ob->data)->id.us--;
1199                 ob->data= cu;
1200                 ob->type= OB_CURVE;
1201
1202                 /* curve objects can't contain DM in usual cases, we could free memory */
1203                 needsFree= 1;
1204         }
1205
1206         dm->needsFree = needsFree;
1207         dm->release(dm);
1208
1209         if (needsFree) {
1210                 ob->derivedFinal = NULL;
1211
1212                 /* curve object could have got bounding box only in special cases */
1213                 if(ob->bb) {
1214                         MEM_freeN(ob->bb);
1215                         ob->bb= NULL;
1216                 }
1217         }
1218 }
1219
1220 void mesh_delete_material_index(Mesh *me, short index)
1221 {
1222         MFace *mf;
1223         int i;
1224
1225         for (i=0, mf=me->mface; i<me->totface; i++, mf++) {
1226                 if (mf->mat_nr && mf->mat_nr>=index) 
1227                         mf->mat_nr--;
1228         }
1229 }
1230
1231 void mesh_set_smooth_flag(Object *meshOb, int enableSmooth) 
1232 {
1233         Mesh *me = meshOb->data;
1234         int i;
1235
1236         for (i=0; i<me->totface; i++) {
1237                 MFace *mf = &((MFace*) me->mface)[i];
1238
1239                 if (enableSmooth) {
1240                         mf->flag |= ME_SMOOTH;
1241                 } else {
1242                         mf->flag &= ~ME_SMOOTH;
1243                 }
1244         }
1245
1246         mesh_calc_normals(me->mvert, me->totvert, me->mface, me->totface, NULL);
1247 }
1248
1249 void mesh_calc_normals(MVert *mverts, int numVerts, MFace *mfaces, int numFaces, float (*faceNors_r)[3]) 
1250 {
1251         float (*tnorms)[3]= MEM_callocN(numVerts*sizeof(*tnorms), "tnorms");
1252         float (*fnors)[3]= (faceNors_r)? faceNors_r: MEM_callocN(sizeof(*fnors)*numFaces, "meshnormals");
1253         int i;
1254
1255         for(i=0; i<numFaces; i++) {
1256                 MFace *mf= &mfaces[i];
1257                 float *f_no= fnors[i];
1258                 float *n4 = (mf->v4)? tnorms[mf->v4]: NULL;
1259                 float *c4 = (mf->v4)? mverts[mf->v4].co: NULL;
1260
1261                 if(mf->v4)
1262                         normal_quad_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, mverts[mf->v4].co);
1263                 else
1264                         normal_tri_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co);
1265
1266                 accumulate_vertex_normals(tnorms[mf->v1], tnorms[mf->v2], tnorms[mf->v3], n4,
1267                         f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, c4);
1268         }
1269
1270         /* following Mesh convention; we use vertex coordinate itself for normal in this case */
1271         for(i=0; i<numVerts; i++) {
1272                 MVert *mv= &mverts[i];
1273                 float *no= tnorms[i];
1274                 
1275                 if(normalize_v3(no) == 0.0f)
1276                         normalize_v3_v3(no, mv->co);
1277
1278                 normal_float_to_short_v3(mv->no, no);
1279         }
1280         
1281         MEM_freeN(tnorms);
1282
1283         if(fnors != faceNors_r)
1284                 MEM_freeN(fnors);
1285 }
1286
1287 float (*mesh_getVertexCos(Mesh *me, int *numVerts_r))[3]
1288 {
1289         int i, numVerts = me->totvert;
1290         float (*cos)[3] = MEM_mallocN(sizeof(*cos)*numVerts, "vertexcos1");
1291         
1292         if (numVerts_r) *numVerts_r = numVerts;
1293         for (i=0; i<numVerts; i++)
1294                 VECCOPY(cos[i], me->mvert[i].co);
1295         
1296         return cos;
1297 }
1298
1299 UvVertMap *make_uv_vert_map(struct MFace *mface, struct MTFace *tface, unsigned int totface, unsigned int totvert, int selected, float *limit)
1300 {
1301         UvVertMap *vmap;
1302         UvMapVert *buf;
1303         MFace *mf;
1304         unsigned int a;
1305         int     i, totuv, nverts;
1306
1307         totuv = 0;
1308
1309         /* generate UvMapVert array */
1310         mf= mface;
1311         for(a=0; a<totface; a++, mf++)
1312                 if(!selected || (!(mf->flag & ME_HIDE) && (mf->flag & ME_FACE_SEL)))
1313                         totuv += (mf->v4)? 4: 3;
1314                 
1315         if(totuv==0)
1316                 return NULL;
1317         
1318         vmap= (UvVertMap*)MEM_callocN(sizeof(*vmap), "UvVertMap");
1319         if (!vmap)
1320                 return NULL;
1321
1322         vmap->vert= (UvMapVert**)MEM_callocN(sizeof(*vmap->vert)*totvert, "UvMapVert*");
1323         buf= vmap->buf= (UvMapVert*)MEM_callocN(sizeof(*vmap->buf)*totuv, "UvMapVert");
1324
1325         if (!vmap->vert || !vmap->buf) {
1326                 free_uv_vert_map(vmap);
1327                 return NULL;
1328         }
1329
1330         mf= mface;
1331         for(a=0; a<totface; a++, mf++) {
1332                 if(!selected || (!(mf->flag & ME_HIDE) && (mf->flag & ME_FACE_SEL))) {
1333                         nverts= (mf->v4)? 4: 3;
1334
1335                         for(i=0; i<nverts; i++) {
1336                                 buf->tfindex= i;
1337                                 buf->f= a;
1338                                 buf->separate = 0;
1339                                 buf->next= vmap->vert[*(&mf->v1 + i)];
1340                                 vmap->vert[*(&mf->v1 + i)]= buf;
1341                                 buf++;
1342                         }
1343                 }
1344         }
1345         
1346         /* sort individual uvs for each vert */
1347         for(a=0; a<totvert; a++) {
1348                 UvMapVert *newvlist= NULL, *vlist=vmap->vert[a];
1349                 UvMapVert *iterv, *v, *lastv, *next;
1350                 float *uv, *uv2, uvdiff[2];
1351
1352                 while(vlist) {
1353                         v= vlist;
1354                         vlist= vlist->next;
1355                         v->next= newvlist;
1356                         newvlist= v;
1357
1358                         uv= tface[v->f].uv[v->tfindex];
1359                         lastv= NULL;
1360                         iterv= vlist;
1361
1362                         while(iterv) {
1363                                 next= iterv->next;
1364
1365                                 uv2= tface[iterv->f].uv[iterv->tfindex];
1366                                 sub_v2_v2v2(uvdiff, uv2, uv);
1367
1368
1369                                 if(fabsf(uv[0]-uv2[0]) < limit[0] && fabsf(uv[1]-uv2[1]) < limit[1]) {
1370                                         if(lastv) lastv->next= next;
1371                                         else vlist= next;
1372                                         iterv->next= newvlist;
1373                                         newvlist= iterv;
1374                                 }
1375                                 else
1376                                         lastv=iterv;
1377
1378                                 iterv= next;
1379                         }
1380
1381                         newvlist->separate = 1;
1382                 }
1383
1384                 vmap->vert[a]= newvlist;
1385         }
1386         
1387         return vmap;
1388 }
1389
1390 UvMapVert *get_uv_map_vert(UvVertMap *vmap, unsigned int v)
1391 {
1392         return vmap->vert[v];
1393 }
1394
1395 void free_uv_vert_map(UvVertMap *vmap)
1396 {
1397         if (vmap) {
1398                 if (vmap->vert) MEM_freeN(vmap->vert);
1399                 if (vmap->buf) MEM_freeN(vmap->buf);
1400                 MEM_freeN(vmap);
1401         }
1402 }
1403
1404 /* Generates a map where the key is the vertex and the value is a list
1405    of faces that use that vertex as a corner. The lists are allocated
1406    from one memory pool. */
1407 void create_vert_face_map(ListBase **map, IndexNode **mem, const MFace *mface, const int totvert, const int totface)
1408 {
1409         int i,j;
1410         IndexNode *node = NULL;
1411         
1412         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
1413         (*mem) = MEM_callocN(sizeof(IndexNode) * totface*4, "vert face map mem");
1414         node = *mem;
1415         
1416         /* Find the users */
1417         for(i = 0; i < totface; ++i){
1418                 for(j = 0; j < (mface[i].v4?4:3); ++j, ++node) {
1419                         node->index = i;
1420                         BLI_addtail(&(*map)[((unsigned int*)(&mface[i]))[j]], node);
1421                 }
1422         }
1423 }
1424
1425 /* Generates a map where the key is the vertex and the value is a list
1426    of edges that use that vertex as an endpoint. The lists are allocated
1427    from one memory pool. */
1428 void create_vert_edge_map(ListBase **map, IndexNode **mem, const MEdge *medge, const int totvert, const int totedge)
1429 {
1430         int i, j;
1431         IndexNode *node = NULL;
1432  
1433         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
1434         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge * 2, "vert edge map mem");
1435         node = *mem;
1436
1437         /* Find the users */
1438         for(i = 0; i < totedge; ++i){
1439                 for(j = 0; j < 2; ++j, ++node) {
1440                         node->index = i;
1441                         BLI_addtail(&(*map)[((unsigned int*)(&medge[i].v1))[j]], node);
1442                 }
1443         }
1444 }
1445
1446 /* basic vertex data functions */
1447 int minmax_mesh(Mesh *me, float min[3], float max[3])
1448 {
1449         int i= me->totvert;
1450         MVert *mvert;
1451         for(mvert= me->mvert; i--; mvert++) {
1452                 DO_MINMAX(mvert->co, min, max);
1453         }
1454         
1455         return (me->totvert != 0);
1456 }
1457
1458 int mesh_center_median(Mesh *me, float cent[3])
1459 {
1460         int i= me->totvert;
1461         MVert *mvert;
1462         zero_v3(cent);
1463         for(mvert= me->mvert; i--; mvert++) {
1464                 add_v3_v3(cent, mvert->co);
1465         }
1466         /* otherwise we get NAN for 0 verts */
1467         if(me->totvert) {
1468                 mul_v3_fl(cent, 1.0f/(float)me->totvert);
1469         }
1470
1471         return (me->totvert != 0);
1472 }
1473
1474 int mesh_center_bounds(Mesh *me, float cent[3])
1475 {
1476         float min[3], max[3];
1477         INIT_MINMAX(min, max);
1478         if(minmax_mesh(me, min, max)) {
1479                 mid_v3_v3v3(cent, min, max);
1480                 return 1;
1481         }
1482
1483         return 0;
1484 }
1485
1486 void mesh_translate(Mesh *me, float offset[3], int do_keys)
1487 {
1488         int i= me->totvert;
1489         MVert *mvert;
1490         for(mvert= me->mvert; i--; mvert++) {
1491                 add_v3_v3(mvert->co, offset);
1492         }
1493         
1494         if (do_keys && me->key) {
1495                 KeyBlock *kb;
1496                 for (kb=me->key->block.first; kb; kb=kb->next) {
1497                         float *fp= kb->data;
1498                         for (i= kb->totelem; i--; fp+=3) {
1499                                 add_v3_v3(fp, offset);
1500                         }
1501                 }
1502         }
1503 }
1504
1505
1506 void BKE_mesh_ensure_navmesh(Mesh *me)
1507 {
1508         if (!CustomData_has_layer(&me->fdata, CD_RECAST)) {
1509                 int i;
1510                 int numFaces = me->totface;
1511                 int* recastData;
1512                 CustomData_add_layer_named(&me->fdata, CD_RECAST, CD_CALLOC, NULL, numFaces, "recastData");
1513                 recastData = (int*)CustomData_get_layer(&me->fdata, CD_RECAST);
1514                 for (i=0; i<numFaces; i++) {
1515                         recastData[i] = i+1;
1516                 }
1517                 CustomData_add_layer_named(&me->fdata, CD_RECAST, CD_REFERENCE, recastData, numFaces, "recastData");
1518         }
1519 }