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