this someone didn't get committed
[blender-staging.git] / source / blender / blenkernel / intern / mesh.c
1
2 /*  mesh.c
3  *
4  *  
5  * 
6  * $Id$
7  *
8  * ***** BEGIN GPL LICENSE BLOCK *****
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, write to the Free Software Foundation,
22  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
23  *
24  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
25  * All rights reserved.
26  *
27  * Contributor(s): Blender Foundation
28  *
29  * ***** END GPL LICENSE BLOCK *****
30  */
31
32 #ifdef HAVE_CONFIG_H
33 #include <config.h>
34 #endif
35
36 #include <stdlib.h>
37 #include <string.h>
38 #include <stdio.h>
39 #include <math.h>
40
41 #include "MEM_guardedalloc.h"
42
43 #include "DNA_ID.h"
44 #include "DNA_curve_types.h"
45 #include "DNA_scene_types.h"
46 #include "DNA_material_types.h"
47 #include "DNA_object_types.h"
48 #include "DNA_image_types.h"
49 #include "DNA_key_types.h"
50 #include "DNA_mesh_types.h"
51 #include "DNA_meshdata_types.h"
52 #include "DNA_ipo_types.h"
53
54 #include "BKE_customdata.h"
55 #include "BKE_depsgraph.h"
56 #include "BKE_main.h"
57 #include "BKE_DerivedMesh.h"
58 #include "BKE_global.h"
59 #include "BKE_mesh.h"
60 #include "BKE_subsurf.h"
61 #include "BKE_displist.h"
62 #include "BKE_library.h"
63 #include "BKE_material.h"
64 #include "BKE_key.h"
65 /* these 2 are only used by conversion functions */
66 #include "BKE_curve.h"
67 /* -- */
68 #include "BKE_object.h"
69 #include "BKE_utildefines.h"
70 #include "BKE_tessmesh.h"
71
72 #include "BLI_blenlib.h"
73 #include "BLI_editVert.h"
74 #include "BLI_math.h"
75 #include "BLI_cellalloc.h"
76 #include "BLI_array.h"
77 #include "BLI_edgehash.h"
78
79 #include "bmesh.h"
80
81 EditMesh *BKE_mesh_get_editmesh(Mesh *me)
82 {
83         return bmesh_to_editmesh(me->edit_btmesh->bm);
84 }
85
86 void free_editMesh(EditMesh *em);
87 void BKE_mesh_end_editmesh(Mesh *me, EditMesh *em)
88 {
89         BM_Free_Mesh(me->edit_btmesh->bm);
90         me->edit_btmesh->bm = editmesh_to_bmesh(em);
91         BMEdit_RecalcTesselation(me->edit_btmesh);
92         free_editMesh(em);
93         MEM_freeN(em);
94 }
95
96 static void mesh_ensure_tesselation_customdata(Mesh *me)
97 {
98         int tottex, totcol;
99
100         tottex = CustomData_number_of_layers(&me->fdata, CD_MTFACE);
101         totcol = CustomData_number_of_layers(&me->fdata, CD_MCOL);
102         
103         if (tottex != CustomData_number_of_layers(&me->pdata, CD_MTEXPOLY) ||
104             totcol != CustomData_number_of_layers(&me->ldata, CD_MLOOPCOL))
105         {
106                 CustomData_free(&me->fdata, me->totface);
107                 
108                 me->mface = NULL;
109                 me->mtface = NULL;
110                 me->mcol = NULL;
111                 me->totface = 0;
112
113                 memset(&me->fdata, 0, sizeof(&me->fdata));
114
115                 CustomData_from_bmeshpoly(&me->fdata, &me->pdata, &me->ldata, me->totface);
116                 printf("Warning! Tesselation uvs or vcol data got out of sync, had to reset!\n");
117         }
118 }
119
120 /*this ensures grouped customdata (e.g. mtexpoly and mloopuv and mtface, or
121   mloopcol and mcol) have the same relative active/render/clone/mask indices.*/
122 void mesh_update_linked_customdata(Mesh *me)
123 {
124         int act;
125
126         if (me->edit_btmesh)
127                 BMEdit_UpdateLinkedCustomData(me->edit_btmesh);
128
129         mesh_ensure_tesselation_customdata(me);
130
131         if (CustomData_has_layer(&me->pdata, CD_MTEXPOLY)) {
132                 act = CustomData_get_active_layer(&me->pdata, CD_MTEXPOLY);
133                 CustomData_set_layer_active(&me->ldata, CD_MLOOPUV, act);
134                 CustomData_set_layer_active(&me->fdata, CD_MTFACE, act);
135
136                 act = CustomData_get_render_layer(&me->pdata, CD_MTEXPOLY);
137                 CustomData_set_layer_render(&me->ldata, CD_MLOOPUV, act);
138                 CustomData_set_layer_render(&me->fdata, CD_MTFACE, act);
139
140                 act = CustomData_get_clone_layer(&me->pdata, CD_MTEXPOLY);
141                 CustomData_set_layer_clone(&me->ldata, CD_MLOOPUV, act);
142                 CustomData_set_layer_clone(&me->fdata, CD_MTFACE, act);
143
144                 act = CustomData_get_mask_layer(&me->pdata, CD_MTEXPOLY);
145                 CustomData_set_layer_mask(&me->ldata, CD_MLOOPUV, act);
146                 CustomData_set_layer_mask(&me->fdata, CD_MTFACE, act);
147         }
148
149         if (CustomData_has_layer(&me->ldata, CD_MLOOPCOL)) {
150                 act = CustomData_get_active_layer(&me->ldata, CD_MLOOPCOL);
151                 CustomData_set_layer_active(&me->fdata, CD_MCOL, act);
152
153                 act = CustomData_get_render_layer(&me->ldata, CD_MLOOPCOL);
154                 CustomData_set_layer_render(&me->fdata, CD_MCOL, act);
155
156                 act = CustomData_get_clone_layer(&me->ldata, CD_MLOOPCOL);
157                 CustomData_set_layer_clone(&me->fdata, CD_MCOL, act);
158
159                 act = CustomData_get_mask_layer(&me->ldata, CD_MLOOPCOL);
160                 CustomData_set_layer_mask(&me->fdata, CD_MCOL, act);
161         }
162 }
163
164 void mesh_update_customdata_pointers(Mesh *me)
165 {
166         mesh_update_linked_customdata(me);
167
168         me->mvert = CustomData_get_layer(&me->vdata, CD_MVERT);
169         me->dvert = CustomData_get_layer(&me->vdata, CD_MDEFORMVERT);
170         me->msticky = CustomData_get_layer(&me->vdata, CD_MSTICKY);
171
172         me->medge = CustomData_get_layer(&me->edata, CD_MEDGE);
173
174         me->mface = CustomData_get_layer(&me->fdata, CD_MFACE);
175         me->mcol = CustomData_get_layer(&me->fdata, CD_MCOL);
176         me->mtface = CustomData_get_layer(&me->fdata, CD_MTFACE);
177         
178         me->mpoly = CustomData_get_layer(&me->pdata, CD_MPOLY);
179         me->mloop = CustomData_get_layer(&me->ldata, CD_MLOOP);
180
181         me->mtpoly = CustomData_get_layer(&me->pdata, CD_MTEXPOLY);
182         me->mloopcol = CustomData_get_layer(&me->ldata, CD_MLOOPCOL);
183         me->mloopuv = CustomData_get_layer(&me->ldata, CD_MLOOPUV);
184 }
185
186 /* Note: unlinking is called when me->id.us is 0, question remains how
187  * much unlinking of Library data in Mesh should be done... probably
188  * we need a more generic method, like the expand() functions in
189  * readfile.c */
190
191 void unlink_mesh(Mesh *me)
192 {
193         int a;
194         
195         if(me==0) return;
196         
197         for(a=0; a<me->totcol; a++) {
198                 if(me->mat[a]) me->mat[a]->id.us--;
199                 me->mat[a]= 0;
200         }
201
202         if(me->key) {
203                 me->key->id.us--;
204                 if (me->key->id.us == 0 && me->key->ipo )
205                         me->key->ipo->id.us--;
206         }
207         me->key= 0;
208         
209         if(me->texcomesh) me->texcomesh= 0;
210 }
211
212
213 /* do not free mesh itself */
214 void free_mesh(Mesh *me, int unlink)
215 {
216         if (unlink)
217                 unlink_mesh(me);
218
219         if(me->pv) {
220                 if(me->pv->vert_map) MEM_freeN(me->pv->vert_map);
221                 if(me->pv->edge_map) MEM_freeN(me->pv->edge_map);
222                 if(me->pv->old_faces) MEM_freeN(me->pv->old_faces);
223                 if(me->pv->old_edges) MEM_freeN(me->pv->old_edges);
224                 me->totvert= me->pv->totvert;
225                 me->totedge= me->pv->totedge;
226                 me->totface= me->pv->totface;
227                 MEM_freeN(me->pv);
228         }
229
230         CustomData_free(&me->vdata, me->totvert);
231         CustomData_free(&me->edata, me->totedge);
232         CustomData_free(&me->fdata, me->totface);
233         CustomData_free(&me->ldata, me->totloop);
234         CustomData_free(&me->pdata, me->totpoly);
235
236         if(me->mat) MEM_freeN(me->mat);
237         
238         if(me->bb) MEM_freeN(me->bb);
239         if(me->mselect) MEM_freeN(me->mselect);
240         if(me->edit_btmesh) MEM_freeN(me->edit_btmesh);
241 }
242
243 void copy_dverts(MDeformVert *dst, MDeformVert *src, int copycount)
244 {
245         /* Assumes dst is already set up */
246         int i;
247
248         if (!src || !dst)
249                 return;
250
251         memcpy (dst, src, copycount * sizeof(MDeformVert));
252         
253         for (i=0; i<copycount; i++){
254                 if (src[i].dw){
255                         dst[i].dw = BLI_cellalloc_calloc (sizeof(MDeformWeight)*src[i].totweight, "copy_deformWeight");
256                         memcpy (dst[i].dw, src[i].dw, sizeof (MDeformWeight)*src[i].totweight);
257                 }
258         }
259
260 }
261
262 void free_dverts(MDeformVert *dvert, int totvert)
263 {
264         /* Instead of freeing the verts directly,
265         call this function to delete any special
266         vert data */
267         int     i;
268
269         if (!dvert)
270                 return;
271
272         /* Free any special data from the verts */
273         for (i=0; i<totvert; i++){
274                 if (dvert[i].dw) BLI_cellalloc_free (dvert[i].dw);
275         }
276         MEM_freeN (dvert);
277 }
278
279 Mesh *add_mesh(char *name)
280 {
281         Mesh *me;
282         
283         me= alloc_libblock(&G.main->mesh, ID_ME, name);
284         
285         me->size[0]= me->size[1]= me->size[2]= 1.0;
286         me->smoothresh= 30;
287         me->texflag= AUTOSPACE;
288         me->flag= ME_TWOSIDED;
289         me->bb= unit_boundbox();
290         me->drawflag= ME_DRAWEDGES|ME_DRAWFACES|ME_DRAWCREASES;
291         
292         return me;
293 }
294
295 Mesh *copy_mesh(Mesh *me)
296 {
297         Mesh *men;
298         MTFace *tface;
299         MTexPoly *txface;
300         int a, i;
301         
302         men= copy_libblock(me);
303         
304         men->mat= MEM_dupallocN(me->mat);
305         for(a=0; a<men->totcol; a++) {
306                 id_us_plus((ID *)men->mat[a]);
307         }
308         id_us_plus((ID *)men->texcomesh);
309
310         CustomData_copy(&me->vdata, &men->vdata, CD_MASK_MESH, CD_DUPLICATE, men->totvert);
311         CustomData_copy(&me->edata, &men->edata, CD_MASK_MESH, CD_DUPLICATE, men->totedge);
312         CustomData_copy(&me->fdata, &men->fdata, CD_MASK_MESH, CD_DUPLICATE, men->totface);
313         CustomData_copy(&me->ldata, &men->ldata, CD_MASK_MESH, CD_DUPLICATE, men->totloop);
314         CustomData_copy(&me->pdata, &men->pdata, CD_MASK_MESH, CD_DUPLICATE, men->totpoly);
315         mesh_update_customdata_pointers(men);
316
317         /* ensure indirect linked data becomes lib-extern */
318         for(i=0; i<me->fdata.totlayer; i++) {
319                 if(me->fdata.layers[i].type == CD_MTFACE) {
320                         tface= (MTFace*)me->fdata.layers[i].data;
321
322                         for(a=0; a<me->totface; a++, tface++)
323                                 if(tface->tpage)
324                                         id_lib_extern((ID*)tface->tpage);
325                 }
326         }
327
328         for(i=0; i<me->pdata.totlayer; i++) {
329                 if(me->pdata.layers[i].type == CD_MTEXPOLY) {
330                         txface= (MTexPoly*)me->pdata.layers[i].data;
331
332                         for(a=0; a<me->totpoly; a++, txface++)
333                                 if(txface->tpage)
334                                         id_lib_extern((ID*)txface->tpage);
335                 }
336         }
337
338         men->mselect= NULL;
339
340         men->bb= MEM_dupallocN(men->bb);
341         
342         men->key= copy_key(me->key);
343         if(men->key) men->key->from= (ID *)men;
344
345         return men;
346 }
347
348 BMesh *BKE_mesh_to_bmesh(Mesh *me, Object *ob)
349 {
350         BMesh *bm;
351         int allocsize[4] = {512,512,2048,512};
352
353         bm = BM_Make_Mesh(allocsize);
354
355         BMO_CallOpf(bm, "mesh_to_bmesh mesh=%p object=%p", me, ob);
356
357         return bm;
358 }
359
360 void make_local_tface(Mesh *me)
361 {
362         MTFace *tface;
363         MTexPoly *txface;
364         Image *ima;
365         int a, i;
366         
367         for(i=0; i<me->pdata.totlayer; i++) {
368                 if(me->pdata.layers[i].type == CD_MTEXPOLY) {
369                         txface= (MTexPoly*)me->fdata.layers[i].data;
370                         
371                         for(a=0; a<me->totpoly; a++, txface++) {
372                                 /* special case: ima always local immediately */
373                                 if(txface->tpage) {
374                                         ima= txface->tpage;
375                                         if(ima->id.lib) {
376                                                 ima->id.lib= 0;
377                                                 ima->id.flag= LIB_LOCAL;
378                                                 new_id(0, (ID *)ima, 0);
379                                         }
380                                 }
381                         }
382                 }
383         }
384
385         for(i=0; i<me->fdata.totlayer; i++) {
386                 if(me->fdata.layers[i].type == CD_MTFACE) {
387                         tface= (MTFace*)me->fdata.layers[i].data;
388                         
389                         for(a=0; a<me->totface; a++, tface++) {
390                                 /* special case: ima always local immediately */
391                                 if(tface->tpage) {
392                                         ima= tface->tpage;
393                                         if(ima->id.lib) {
394                                                 ima->id.lib= 0;
395                                                 ima->id.flag= LIB_LOCAL;
396                                                 new_id(0, (ID *)ima, 0);
397                                         }
398                                 }
399                         }
400                 }
401         }
402
403 }
404
405 void make_local_mesh(Mesh *me)
406 {
407         Object *ob;
408         Mesh *men;
409         int local=0, lib=0;
410
411         /* - only lib users: do nothing
412             * - only local users: set flag
413             * - mixed: make copy
414             */
415         
416         if(me->id.lib==0) return;
417         if(me->id.us==1) {
418                 me->id.lib= 0;
419                 me->id.flag= LIB_LOCAL;
420                 new_id(0, (ID *)me, 0);
421                 
422                 if(me->mtface) make_local_tface(me);
423                 
424                 return;
425         }
426         
427         ob= G.main->object.first;
428         while(ob) {
429                 if( me==get_mesh(ob) ) {
430                         if(ob->id.lib) lib= 1;
431                         else local= 1;
432                 }
433                 ob= ob->id.next;
434         }
435         
436         if(local && lib==0) {
437                 me->id.lib= 0;
438                 me->id.flag= LIB_LOCAL;
439                 new_id(0, (ID *)me, 0);
440                 
441                 if(me->mtface) make_local_tface(me);
442                 
443         }
444         else if(local && lib) {
445                 men= copy_mesh(me);
446                 men->id.us= 0;
447                 
448                 ob= G.main->object.first;
449                 while(ob) {
450                         if( me==get_mesh(ob) ) {                                
451                                 if(ob->id.lib==0) {
452                                         set_mesh(ob, men);
453                                 }
454                         }
455                         ob= ob->id.next;
456                 }
457         }
458 }
459
460 void boundbox_mesh(Mesh *me, float *loc, float *size)
461 {
462         MVert *mvert;
463         BoundBox *bb;
464         float min[3], max[3];
465         float mloc[3], msize[3];
466         int a;
467         
468         if(me->bb==0) me->bb= MEM_callocN(sizeof(BoundBox), "boundbox");
469         bb= me->bb;
470         
471         INIT_MINMAX(min, max);
472
473         if (!loc) loc= mloc;
474         if (!size) size= msize;
475         
476         mvert= me->mvert;
477         for(a=0; a<me->totvert; a++, mvert++) {
478                 DO_MINMAX(mvert->co, min, max);
479         }
480
481         if(!me->totvert) {
482                 min[0] = min[1] = min[2] = -1.0f;
483                 max[0] = max[1] = max[2] = 1.0f;
484         }
485
486         loc[0]= (min[0]+max[0])/2.0f;
487         loc[1]= (min[1]+max[1])/2.0f;
488         loc[2]= (min[2]+max[2])/2.0f;
489                 
490         size[0]= (max[0]-min[0])/2.0f;
491         size[1]= (max[1]-min[1])/2.0f;
492         size[2]= (max[2]-min[2])/2.0f;
493         
494         boundbox_set_from_min_max(bb, min, max);
495 }
496
497 void tex_space_mesh(Mesh *me)
498 {
499         float loc[3], size[3];
500         int a;
501
502         boundbox_mesh(me, loc, size);
503
504         if(me->texflag & AUTOSPACE) {
505                 for (a=0; a<3; a++) {
506                         if(size[a]==0.0) size[a]= 1.0;
507                         else if(size[a]>0.0 && size[a]<0.00001) size[a]= 0.00001;
508                         else if(size[a]<0.0 && size[a]> -0.00001) size[a]= -0.00001;
509                 }
510
511                 VECCOPY(me->loc, loc);
512                 VECCOPY(me->size, size);
513                 me->rot[0]= me->rot[1]= me->rot[2]= 0.0;
514         }
515 }
516
517 BoundBox *mesh_get_bb(Object *ob)
518 {
519         Mesh *me= ob->data;
520
521         if(ob->bb)
522                 return ob->bb;
523
524         if (!me->bb)
525                 tex_space_mesh(me);
526
527         return me->bb;
528 }
529
530 void mesh_get_texspace(Mesh *me, float *loc_r, float *rot_r, float *size_r)
531 {
532         if (!me->bb) {
533                 tex_space_mesh(me);
534         }
535
536         if (loc_r) VECCOPY(loc_r, me->loc);
537         if (rot_r) VECCOPY(rot_r, me->rot);
538         if (size_r) VECCOPY(size_r, me->size);
539 }
540
541 float *get_mesh_orco_verts(Object *ob)
542 {
543         Mesh *me = ob->data;
544         MVert *mvert = NULL;
545         Mesh *tme = me->texcomesh?me->texcomesh:me;
546         int a, totvert;
547         float (*vcos)[3] = NULL;
548
549         /* Get appropriate vertex coordinates */
550         vcos = MEM_callocN(sizeof(*vcos)*me->totvert, "orco mesh");
551         mvert = tme->mvert;
552         totvert = MIN2(tme->totvert, me->totvert);
553
554         for(a=0; a<totvert; a++, mvert++) {
555                 vcos[a][0]= mvert->co[0];
556                 vcos[a][1]= mvert->co[1];
557                 vcos[a][2]= mvert->co[2];
558         }
559
560         return (float*)vcos;
561 }
562
563 void transform_mesh_orco_verts(Mesh *me, float (*orco)[3], int totvert, int invert)
564 {
565         float loc[3], size[3];
566         int a;
567
568         mesh_get_texspace(me->texcomesh?me->texcomesh:me, loc, NULL, size);
569
570         if(invert) {
571                 for(a=0; a<totvert; a++) {
572                         float *co = orco[a];
573                         co[0] = co[0]*size[0] + loc[0];
574                         co[1] = co[1]*size[1] + loc[1];
575                         co[2] = co[2]*size[2] + loc[2];
576                 }
577         }
578         else {
579                 for(a=0; a<totvert; a++) {
580                         float *co = orco[a];
581                         co[0] = (co[0]-loc[0])/size[0];
582                         co[1] = (co[1]-loc[1])/size[1];
583                         co[2] = (co[2]-loc[2])/size[2];
584                 }
585         }
586 }
587
588 /* rotates the vertices of a face in case v[2] or v[3] (vertex index) is = 0.
589    this is necessary to make the if(mface->v4) check for quads work */
590 int test_index_face(MFace *mface, CustomData *fdata, int mfindex, int nr)
591 {
592         /* first test if the face is legal */
593         if(mface->v3 && mface->v3==mface->v4) {
594                 mface->v4= 0;
595                 nr--;
596         }
597         if(mface->v2 && mface->v2==mface->v3) {
598                 mface->v3= mface->v4;
599                 mface->v4= 0;
600                 nr--;
601         }
602         if(mface->v1==mface->v2) {
603                 mface->v2= mface->v3;
604                 mface->v3= mface->v4;
605                 mface->v4= 0;
606                 nr--;
607         }
608
609         /* prevent a zero at wrong index location */
610         if(nr==3) {
611                 if(mface->v3==0) {
612                         static int corner_indices[4] = {1, 2, 0, 3};
613
614                         SWAP(int, mface->v1, mface->v2);
615                         SWAP(int, mface->v2, mface->v3);
616
617                         if(fdata)
618                                 CustomData_swap(fdata, mfindex, corner_indices);
619                 }
620         }
621         else if(nr==4) {
622                 if(mface->v3==0 || mface->v4==0) {
623                         static int corner_indices[4] = {2, 3, 0, 1};
624
625                         SWAP(int, mface->v1, mface->v3);
626                         SWAP(int, mface->v2, mface->v4);
627
628                         if(fdata)
629                                 CustomData_swap(fdata, mfindex, corner_indices);
630                 }
631         }
632
633         return nr;
634 }
635
636 Mesh *get_mesh(Object *ob)
637 {
638         
639         if(ob==0) return 0;
640         if(ob->type==OB_MESH) return ob->data;
641         else return 0;
642 }
643
644 void set_mesh(Object *ob, Mesh *me)
645 {
646         Mesh *old=0;
647         
648         if(ob==0) return;
649         
650         if(ob->type==OB_MESH) {
651                 old= ob->data;
652                 if (old)
653                         old->id.us--;
654                 ob->data= me;
655                 id_us_plus((ID *)me);
656         }
657         
658         test_object_materials((ID *)me);
659 }
660
661 /* ************** make edges in a Mesh, for outside of editmode */
662
663 struct edgesort {
664         int v1, v2;
665         short is_loose, is_draw;
666 };
667
668 /* edges have to be added with lowest index first for sorting */
669 static void to_edgesort(struct edgesort *ed, int v1, int v2, short is_loose, short is_draw)
670 {
671         if(v1<v2) {
672                 ed->v1= v1; ed->v2= v2;
673         }
674         else {
675                 ed->v1= v2; ed->v2= v1;
676         }
677         ed->is_loose= is_loose;
678         ed->is_draw= is_draw;
679 }
680
681 static int vergedgesort(const void *v1, const void *v2)
682 {
683         const struct edgesort *x1=v1, *x2=v2;
684
685         if( x1->v1 > x2->v1) return 1;
686         else if( x1->v1 < x2->v1) return -1;
687         else if( x1->v2 > x2->v2) return 1;
688         else if( x1->v2 < x2->v2) return -1;
689         
690         return 0;
691 }
692
693 void make_edges(Mesh *me, int old)
694 {
695         MFace *mface;
696         MEdge *medge;
697         struct edgesort *edsort, *ed;
698         int a, totedge=0, final=0;
699         
700         /* we put all edges in array, sort them, and detect doubles that way */
701         
702         for(a= me->totface, mface= me->mface; a>0; a--, mface++) {
703                 if(mface->v4) totedge+=4;
704                 else if(mface->v3) totedge+=3;
705                 else totedge+=1;
706         }
707         
708         if(totedge==0) {
709                 /* flag that mesh has edges */
710                 me->medge = MEM_callocN(0, "make mesh edges");
711                 me->totedge = 0;
712                 return;
713         }
714         
715         ed= edsort= MEM_mallocN(totedge*sizeof(struct edgesort), "edgesort");
716         
717         for(a= me->totface, mface= me->mface; a>0; a--, mface++) {
718                 to_edgesort(ed++, mface->v1, mface->v2, !mface->v3, mface->edcode & ME_V1V2);
719                 if(mface->v4) {
720                         to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
721                         to_edgesort(ed++, mface->v3, mface->v4, 0, mface->edcode & ME_V3V4);
722                         to_edgesort(ed++, mface->v4, mface->v1, 0, mface->edcode & ME_V4V1);
723                 }
724                 else if(mface->v3) {
725                         to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
726                         to_edgesort(ed++, mface->v3, mface->v1, 0, mface->edcode & ME_V3V1);
727                 }
728         }
729         
730         qsort(edsort, totedge, sizeof(struct edgesort), vergedgesort);
731         
732         /* count final amount */
733         for(a=totedge, ed=edsort; a>1; a--, ed++) {
734                 /* edge is unique when it differs from next edge, or is last */
735                 if(ed->v1 != (ed+1)->v1 || ed->v2 != (ed+1)->v2) final++;
736         }
737         final++;
738         
739
740         medge= CustomData_add_layer(&me->edata, CD_MEDGE, CD_CALLOC, NULL, final);
741         me->medge= medge;
742         me->totedge= final;
743         
744         for(a=totedge, ed=edsort; a>1; a--, ed++) {
745                 /* edge is unique when it differs from next edge, or is last */
746                 if(ed->v1 != (ed+1)->v1 || ed->v2 != (ed+1)->v2) {
747                         medge->v1= ed->v1;
748                         medge->v2= ed->v2;
749                         if(old==0 || ed->is_draw) medge->flag= ME_EDGEDRAW|ME_EDGERENDER;
750                         if(ed->is_loose) medge->flag|= ME_LOOSEEDGE;
751                         medge++;
752                 }
753                 else {
754                         /* equal edge, we merge the drawflag */
755                         (ed+1)->is_draw |= ed->is_draw;
756                 }
757         }
758         /* last edge */
759         medge->v1= ed->v1;
760         medge->v2= ed->v2;
761         medge->flag= ME_EDGEDRAW;
762         if(ed->is_loose) medge->flag|= ME_LOOSEEDGE;
763         medge->flag |= ME_EDGERENDER;
764
765         MEM_freeN(edsort);
766
767         mesh_strip_loose_faces(me);
768 }
769
770 void mesh_strip_loose_faces(Mesh *me)
771 {
772         int a,b;
773
774         for (a=b=0; a<me->totface; a++) {
775                 if (me->mface[a].v3) {
776                         if (a!=b) {
777                                 memcpy(&me->mface[b],&me->mface[a],sizeof(me->mface[b]));
778                                 CustomData_copy_data(&me->fdata, &me->fdata, a, b, 1);
779                                 CustomData_free_elem(&me->fdata, a, 1);
780                         }
781                         b++;
782                 }
783         }
784         me->totface = b;
785 }
786
787
788 void mball_to_mesh(ListBase *lb, Mesh *me)
789 {
790         DispList *dl;
791         MVert *mvert;
792         MFace *mface;
793         float *nors, *verts;
794         int a, *index;
795         
796         dl= lb->first;
797         if(dl==0) return;
798
799         if(dl->type==DL_INDEX4) {
800                 me->flag= ME_NOPUNOFLIP;
801                 me->totvert= dl->nr;
802                 me->totface= dl->parts;
803                 
804                 mvert= CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, dl->nr);
805                 mface= CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, dl->parts);
806                 me->mvert= mvert;
807                 me->mface= mface;
808
809                 a= dl->nr;
810                 nors= dl->nors;
811                 verts= dl->verts;
812                 while(a--) {
813                         VECCOPY(mvert->co, verts);
814                         mvert->no[0]= (short int)(nors[0]*32767.0);
815                         mvert->no[1]= (short int)(nors[1]*32767.0);
816                         mvert->no[2]= (short int)(nors[2]*32767.0);
817                         mvert++;
818                         nors+= 3;
819                         verts+= 3;
820                 }
821                 
822                 a= dl->parts;
823                 index= dl->index;
824                 while(a--) {
825                         mface->v1= index[0];
826                         mface->v2= index[1];
827                         mface->v3= index[2];
828                         mface->v4= index[3];
829                         mface->flag= ME_SMOOTH;
830
831                         test_index_face(mface, NULL, 0, (mface->v3==mface->v4)? 3: 4);
832
833                         mface++;
834                         index+= 4;
835                 }
836
837                 make_edges(me, 0);      // all edges
838         }       
839 }
840
841 /* this may fail replacing ob->data, be sure to check ob->type */
842 void nurbs_to_mesh(Object *ob)
843 {
844         Object *ob1;
845         DispList *dl;
846         Mesh *me;
847         Curve *cu;
848         MVert *mvert;
849         MFace *mface;
850         float *data;
851         int a, b, ofs, vertcount, startvert, totvert=0, totvlak=0;
852         int p1, p2, p3, p4, *index;
853
854         cu= ob->data;
855
856         /* count */
857         dl= cu->disp.first;
858         while(dl) {
859                 if(dl->type==DL_SEGM) {
860                         totvert+= dl->parts*dl->nr;
861                         totvlak+= dl->parts*(dl->nr-1);
862                 }
863                 else if(dl->type==DL_POLY) {
864                         /* cyclic polys are filled. except when 3D */
865                         if(cu->flag & CU_3D) {
866                                 totvert+= dl->parts*dl->nr;
867                                 totvlak+= dl->parts*dl->nr;
868                         }
869                 }
870                 else if(dl->type==DL_SURF) {
871                         totvert+= dl->parts*dl->nr;
872                         totvlak+= (dl->parts-1+((dl->flag & DL_CYCL_V)==2))*(dl->nr-1+(dl->flag & DL_CYCL_U));
873                 }
874                 else if(dl->type==DL_INDEX3) {
875                         totvert+= dl->nr;
876                         totvlak+= dl->parts;
877                 }
878                 dl= dl->next;
879         }
880         if(totvert==0) {
881                 /* error("can't convert"); */
882                 /* Make Sure you check ob->data is a curve */
883                 return;
884         }
885
886         /* make mesh */
887         me= add_mesh("Mesh");
888         me->totvert= totvert;
889         me->totface= totvlak;
890
891         me->totcol= cu->totcol;
892         me->mat= cu->mat;
893         cu->mat= 0;
894         cu->totcol= 0;
895
896         mvert= CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, me->totvert);
897         mface= CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, me->totface);
898         me->mvert= mvert;
899         me->mface= mface;
900
901         /* verts and faces */
902         vertcount= 0;
903
904         dl= cu->disp.first;
905         while(dl) {
906                 int smooth= dl->rt & CU_SMOOTH ? 1 : 0;
907                 
908                 if(dl->type==DL_SEGM) {
909                         startvert= vertcount;
910                         a= dl->parts*dl->nr;
911                         data= dl->verts;
912                         while(a--) {
913                                 VECCOPY(mvert->co, data);
914                                 data+=3;
915                                 vertcount++;
916                                 mvert++;
917                         }
918
919                         for(a=0; a<dl->parts; a++) {
920                                 ofs= a*dl->nr;
921                                 for(b=1; b<dl->nr; b++) {
922                                         mface->v1= startvert+ofs+b-1;
923                                         mface->v2= startvert+ofs+b;
924                                         if(smooth) mface->flag |= ME_SMOOTH;
925                                         mface++;
926                                 }
927                         }
928
929                 }
930                 else if(dl->type==DL_POLY) {
931                         /* 3d polys are not filled */
932                         if(cu->flag & CU_3D) {
933                                 startvert= vertcount;
934                                 a= dl->parts*dl->nr;
935                                 data= dl->verts;
936                                 while(a--) {
937                                         VECCOPY(mvert->co, data);
938                                         data+=3;
939                                         vertcount++;
940                                         mvert++;
941                                 }
942         
943                                 for(a=0; a<dl->parts; a++) {
944                                         ofs= a*dl->nr;
945                                         for(b=0; b<dl->nr; b++) {
946                                                 mface->v1= startvert+ofs+b;
947                                                 if(b==dl->nr-1) mface->v2= startvert+ofs;
948                                                 else mface->v2= startvert+ofs+b+1;
949                                                 if(smooth) mface->flag |= ME_SMOOTH;
950                                                 mface++;
951                                         }
952                                 }
953                         }
954                 }
955                 else if(dl->type==DL_INDEX3) {
956                         startvert= vertcount;
957                         a= dl->nr;
958                         data= dl->verts;
959                         while(a--) {
960                                 VECCOPY(mvert->co, data);
961                                 data+=3;
962                                 vertcount++;
963                                 mvert++;
964                         }
965
966                         a= dl->parts;
967                         index= dl->index;
968                         while(a--) {
969                                 mface->v1= startvert+index[0];
970                                 mface->v2= startvert+index[2];
971                                 mface->v3= startvert+index[1];
972                                 mface->v4= 0;
973                                 test_index_face(mface, NULL, 0, 3);
974                                 
975                                 if(smooth) mface->flag |= ME_SMOOTH;
976                                 mface++;
977                                 index+= 3;
978                         }
979         
980         
981                 }
982                 else if(dl->type==DL_SURF) {
983                         startvert= vertcount;
984                         a= dl->parts*dl->nr;
985                         data= dl->verts;
986                         while(a--) {
987                                 VECCOPY(mvert->co, data);
988                                 data+=3;
989                                 vertcount++;
990                                 mvert++;
991                         }
992
993                         for(a=0; a<dl->parts; a++) {
994
995                                 if( (dl->flag & DL_CYCL_V)==0 && a==dl->parts-1) break;
996
997                                 if(dl->flag & DL_CYCL_U) {                      /* p2 -> p1 -> */
998                                         p1= startvert+ dl->nr*a;        /* p4 -> p3 -> */
999                                         p2= p1+ dl->nr-1;               /* -----> next row */
1000                                         p3= p1+ dl->nr;
1001                                         p4= p2+ dl->nr;
1002                                         b= 0;
1003                                 }
1004                                 else {
1005                                         p2= startvert+ dl->nr*a;
1006                                         p1= p2+1;
1007                                         p4= p2+ dl->nr;
1008                                         p3= p1+ dl->nr;
1009                                         b= 1;
1010                                 }
1011                                 if( (dl->flag & DL_CYCL_V) && a==dl->parts-1) {
1012                                         p3-= dl->parts*dl->nr;
1013                                         p4-= dl->parts*dl->nr;
1014                                 }
1015
1016                                 for(; b<dl->nr; b++) {
1017                                         mface->v1= p1;
1018                                         mface->v2= p3;
1019                                         mface->v3= p4;
1020                                         mface->v4= p2;
1021                                         mface->mat_nr= (unsigned char)dl->col;
1022                                         test_index_face(mface, NULL, 0, 4);
1023                                         
1024                                         if(smooth) mface->flag |= ME_SMOOTH;
1025                                         mface++;
1026
1027                                         p4= p3; 
1028                                         p3++;
1029                                         p2= p1; 
1030                                         p1++;
1031                                 }
1032                         }
1033
1034                 }
1035
1036                 dl= dl->next;
1037         }
1038
1039         make_edges(me, 0);      // all edges
1040         mesh_calc_normals(me->mvert, me->totvert, me->mface, me->totface, NULL);
1041
1042         if(ob->data) {
1043                 free_libblock(&G.main->curve, ob->data);
1044         }
1045         ob->data= me;
1046         ob->type= OB_MESH;
1047         
1048         /* other users */
1049         ob1= G.main->object.first;
1050         while(ob1) {
1051                 if(ob1->data==cu) {
1052                         ob1->type= OB_MESH;
1053                 
1054                         ob1->data= ob->data;
1055                         id_us_plus((ID *)ob->data);
1056                 }
1057                 ob1= ob1->id.next;
1058         }
1059
1060 }
1061
1062 typedef struct EdgeLink {
1063         Link *next, *prev;
1064         void *edge;
1065 } EdgeLink;
1066
1067 typedef struct VertLink {
1068         Link *next, *prev;
1069         int index;
1070 } VertLink;
1071
1072 static void prependPolyLineVert(ListBase *lb, int index)
1073 {
1074         VertLink *vl= MEM_callocN(sizeof(VertLink), "VertLink");
1075         vl->index = index;
1076         BLI_addhead(lb, vl);
1077 }
1078
1079 static void appendPolyLineVert(ListBase *lb, int index)
1080 {
1081         VertLink *vl= MEM_callocN(sizeof(VertLink), "VertLink");
1082         vl->index = index;
1083         BLI_addtail(lb, vl);
1084 }
1085
1086 void mesh_to_curve(Scene *scene, Object *ob)
1087 {
1088         /* make new mesh data from the original copy */
1089         DerivedMesh *dm= mesh_get_derived_final(scene, ob, CD_MASK_MESH);
1090
1091         MVert *mverts= dm->getVertArray(dm);
1092         MEdge *med, *medge= dm->getEdgeArray(dm);
1093         MFace *mf,  *mface= dm->getTessFaceArray(dm);
1094
1095         int totedge = dm->getNumEdges(dm);
1096         int totface = dm->getNumTessFaces(dm);
1097         int totedges = 0;
1098         int i;
1099
1100         /* only to detect edge polylines */
1101         EdgeHash *eh = BLI_edgehash_new();
1102         EdgeHash *eh_edge = BLI_edgehash_new();
1103
1104
1105         ListBase edges = {NULL, NULL};
1106
1107         /* create edges from all faces (so as to find edges not in any faces) */
1108         mf= mface;
1109         for (i = 0; i < totface; i++, mf++) {
1110                 if (!BLI_edgehash_haskey(eh, mf->v1, mf->v2))
1111                         BLI_edgehash_insert(eh, mf->v1, mf->v2, NULL);
1112                 if (!BLI_edgehash_haskey(eh, mf->v2, mf->v3))
1113                         BLI_edgehash_insert(eh, mf->v2, mf->v3, NULL);
1114
1115                 if (mf->v4) {
1116                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v4))
1117                                 BLI_edgehash_insert(eh, mf->v3, mf->v4, NULL);
1118                         if (!BLI_edgehash_haskey(eh, mf->v4, mf->v1))
1119                                 BLI_edgehash_insert(eh, mf->v4, mf->v1, NULL);
1120                 } else {
1121                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v1))
1122                                 BLI_edgehash_insert(eh, mf->v3, mf->v1, NULL);
1123                 }
1124         }
1125
1126         med= medge;
1127         for(i=0; i<totedge; i++, med++) {
1128                 if (!BLI_edgehash_haskey(eh, med->v1, med->v2)) {
1129                         EdgeLink *edl= MEM_callocN(sizeof(EdgeLink), "EdgeLink");
1130
1131                         BLI_edgehash_insert(eh_edge, med->v1, med->v2, NULL);
1132                         edl->edge= med;
1133
1134                         BLI_addtail(&edges, edl);       totedges++;
1135                 }
1136         }
1137         BLI_edgehash_free(eh_edge, NULL);
1138         BLI_edgehash_free(eh, NULL);
1139
1140         if(edges.first) {
1141                 Curve *cu = add_curve(ob->id.name+2, OB_CURVE);
1142                 cu->flag |= CU_3D;
1143
1144                 while(edges.first) {
1145                         /* each iteration find a polyline and add this as a nurbs poly spline */
1146
1147                         ListBase polyline = {NULL, NULL}; /* store a list of VertLink's */
1148                         int closed = FALSE;
1149                         int totpoly= 0;
1150                         MEdge *med_current= ((EdgeLink *)edges.last)->edge;
1151                         int startVert= med_current->v1;
1152                         int endVert= med_current->v2;
1153                         int ok= TRUE;
1154
1155                         appendPolyLineVert(&polyline, startVert);       totpoly++;
1156                         appendPolyLineVert(&polyline, endVert);         totpoly++;
1157                         BLI_freelinkN(&edges, edges.last);                      totedges--;
1158
1159                         while(ok) { /* while connected edges are found... */
1160                                 ok = FALSE;
1161                                 i= totedges;
1162                                 while(i) {
1163                                         EdgeLink *edl;
1164
1165                                         i-=1;
1166                                         edl= BLI_findlink(&edges, i);
1167                                         med= edl->edge;
1168
1169                                         if(med->v1==endVert) {
1170                                                 endVert = med->v2;
1171                                                 appendPolyLineVert(&polyline, med->v2); totpoly++;
1172                                                 BLI_freelinkN(&edges, edl);                             totedges--;
1173                                                 ok= TRUE;
1174                                         }
1175                                         else if(med->v2==endVert) {
1176                                                 endVert = med->v1;
1177                                                 appendPolyLineVert(&polyline, endVert); totpoly++;
1178                                                 BLI_freelinkN(&edges, edl);                             totedges--;
1179                                                 ok= TRUE;
1180                                         }
1181                                         else if(med->v1==startVert) {
1182                                                 startVert = med->v2;
1183                                                 prependPolyLineVert(&polyline, startVert);      totpoly++;
1184                                                 BLI_freelinkN(&edges, edl);                                     totedges--;
1185                                                 ok= TRUE;
1186                                         }
1187                                         else if(med->v2==startVert) {
1188                                                 startVert = med->v1;
1189                                                 prependPolyLineVert(&polyline, startVert);      totpoly++;
1190                                                 BLI_freelinkN(&edges, edl);                                     totedges--;
1191                                                 ok= TRUE;
1192                                         }
1193                                 }
1194                         }
1195
1196                         /* Now we have a polyline, make into a curve */
1197                         if(startVert==endVert) {
1198                                 BLI_freelinkN(&polyline, polyline.last);
1199                                 totpoly--;
1200                                 closed = TRUE;
1201                         }
1202
1203                         /* --- nurbs --- */
1204                         {
1205                                 Nurb *nu;
1206                                 BPoint *bp;
1207                                 VertLink *vl;
1208
1209                                 /* create new 'nurb' within the curve */
1210                                 nu = (Nurb *)MEM_callocN(sizeof(Nurb), "MeshNurb");
1211
1212                                 nu->pntsu= totpoly;
1213                                 nu->pntsv= 1;
1214                                 nu->orderu= 4;
1215                                 nu->flagu= 2 | (closed ? CU_CYCLIC:0);  /* endpoint */
1216                                 nu->resolu= 12;
1217
1218                                 nu->bp= (BPoint *)MEM_callocN(sizeof(BPoint)*totpoly, "bpoints");
1219
1220                                 /* add points */
1221                                 vl= polyline.first;
1222                                 for (i=0, bp=nu->bp; i < totpoly; i++, bp++, vl=(VertLink *)vl->next) {
1223                                         copy_v3_v3(bp->vec, mverts[vl->index].co);
1224                                         bp->f1= SELECT;
1225                                         bp->radius = bp->weight = 1.0;
1226                                 }
1227                                 BLI_freelistN(&polyline);
1228
1229                                 /* add nurb to curve */
1230                                 BLI_addtail(&cu->nurb, nu);
1231                         }
1232                         /* --- done with nurbs --- */
1233                 }
1234
1235                 ((Mesh *)ob->data)->id.us--;
1236                 ob->data= cu;
1237                 ob->type= OB_CURVE;
1238         }
1239
1240         dm->release(dm);
1241 }
1242
1243 void mesh_delete_material_index(Mesh *me, int index)
1244 {
1245         int i;
1246
1247         for (i=0; i<me->totface; i++) {
1248                 MFace *mf = &((MFace*) me->mface)[i];
1249                 if (mf->mat_nr && mf->mat_nr>=index) 
1250                         mf->mat_nr--;
1251         }
1252 }
1253
1254 void mesh_set_smooth_flag(Object *meshOb, int enableSmooth) 
1255 {
1256         Mesh *me = meshOb->data;
1257         int i;
1258
1259         for (i=0; i<me->totface; i++) {
1260                 MFace *mf = &((MFace*) me->mface)[i];
1261
1262                 if (enableSmooth) {
1263                         mf->flag |= ME_SMOOTH;
1264                 } else {
1265                         mf->flag &= ~ME_SMOOTH;
1266                 }
1267         }
1268
1269 // XXX do this in caller        DAG_id_flush_update(&me->id, OB_RECALC_DATA);
1270 }
1271
1272 void mesh_calc_normals(MVert *mverts, int numVerts, MFace *mfaces, int numFaces, float **faceNors_r) 
1273 {
1274         float (*tnorms)[3]= MEM_callocN(numVerts*sizeof(*tnorms), "tnorms");
1275         float *fnors= MEM_mallocN(sizeof(*fnors)*3*numFaces, "meshnormals");
1276         int i;
1277
1278         for (i=0; i<numFaces; i++) {
1279                 MFace *mf= &mfaces[i];
1280                 float *f_no= &fnors[i*3];
1281
1282                 if (mf->v4)
1283                         normal_quad_v3( f_no,mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, mverts[mf->v4].co);
1284                 else
1285                         normal_tri_v3( f_no,mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co);
1286                 
1287                 add_v3_v3v3(tnorms[mf->v1], tnorms[mf->v1], f_no);
1288                 add_v3_v3v3(tnorms[mf->v2], tnorms[mf->v2], f_no);
1289                 add_v3_v3v3(tnorms[mf->v3], tnorms[mf->v3], f_no);
1290                 if (mf->v4)
1291                         add_v3_v3v3(tnorms[mf->v4], tnorms[mf->v4], f_no);
1292         }
1293         for (i=0; i<numVerts; i++) {
1294                 MVert *mv= &mverts[i];
1295                 float *no= tnorms[i];
1296                 
1297                 if (normalize_v3(no)==0.0) {
1298                         VECCOPY(no, mv->co);
1299                         normalize_v3(no);
1300                 }
1301
1302                 mv->no[0]= (short)(no[0]*32767.0);
1303                 mv->no[1]= (short)(no[1]*32767.0);
1304                 mv->no[2]= (short)(no[2]*32767.0);
1305         }
1306         
1307         MEM_freeN(tnorms);
1308
1309         if (faceNors_r) {
1310                 *faceNors_r = fnors;
1311         } else {
1312                 MEM_freeN(fnors);
1313         }
1314 }
1315
1316 float (*mesh_getVertexCos(Mesh *me, int *numVerts_r))[3]
1317 {
1318         int i, numVerts = me->totvert;
1319         float (*cos)[3] = MEM_mallocN(sizeof(*cos)*numVerts, "vertexcos1");
1320         
1321         if (numVerts_r) *numVerts_r = numVerts;
1322         for (i=0; i<numVerts; i++)
1323                 VECCOPY(cos[i], me->mvert[i].co);
1324         
1325         return cos;
1326 }
1327
1328 UvVertMap *make_uv_vert_map(struct MFace *mface, struct MTFace *tface, unsigned int totface, unsigned int totvert, int selected, float *limit)
1329 {
1330         UvVertMap *vmap;
1331         UvMapVert *buf;
1332         MFace *mf;
1333         MTFace *tf;
1334         unsigned int a;
1335         int     i, totuv, nverts;
1336
1337         totuv = 0;
1338
1339         /* generate UvMapVert array */
1340         mf= mface;
1341         tf= tface;
1342         for(a=0; a<totface; a++, mf++, tf++)
1343                 if(!selected || (!(mf->flag & ME_HIDE) && (mf->flag & ME_FACE_SEL)))
1344                         totuv += (mf->v4)? 4: 3;
1345                 
1346         if(totuv==0)
1347                 return NULL;
1348         
1349         vmap= (UvVertMap*)MEM_callocN(sizeof(*vmap), "UvVertMap");
1350         if (!vmap)
1351                 return NULL;
1352
1353         vmap->vert= (UvMapVert**)MEM_callocN(sizeof(*vmap->vert)*totvert, "UvMapVert*");
1354         buf= vmap->buf= (UvMapVert*)MEM_callocN(sizeof(*vmap->buf)*totuv, "UvMapVert");
1355
1356         if (!vmap->vert || !vmap->buf) {
1357                 free_uv_vert_map(vmap);
1358                 return NULL;
1359         }
1360
1361         mf= mface;
1362         tf= tface;
1363         for(a=0; a<totface; a++, mf++, tf++) {
1364                 if(!selected || (!(mf->flag & ME_HIDE) && (mf->flag & ME_FACE_SEL))) {
1365                         nverts= (mf->v4)? 4: 3;
1366
1367                         for(i=0; i<nverts; i++) {
1368                                 buf->tfindex= i;
1369                                 buf->f= a;
1370                                 buf->separate = 0;
1371                                 buf->next= vmap->vert[*(&mf->v1 + i)];
1372                                 vmap->vert[*(&mf->v1 + i)]= buf;
1373                                 buf++;
1374                         }
1375                 }
1376         }
1377         
1378         /* sort individual uvs for each vert */
1379         tf= tface;
1380         for(a=0; a<totvert; a++) {
1381                 UvMapVert *newvlist= NULL, *vlist=vmap->vert[a];
1382                 UvMapVert *iterv, *v, *lastv, *next;
1383                 float *uv, *uv2, uvdiff[2];
1384
1385                 while(vlist) {
1386                         v= vlist;
1387                         vlist= vlist->next;
1388                         v->next= newvlist;
1389                         newvlist= v;
1390
1391                         uv= (tf+v->f)->uv[v->tfindex];
1392                         lastv= NULL;
1393                         iterv= vlist;
1394
1395                         while(iterv) {
1396                                 next= iterv->next;
1397
1398                                 uv2= (tf+iterv->f)->uv[iterv->tfindex];
1399                                 sub_v2_v2v2(uvdiff, uv2, uv);
1400
1401
1402                                 if(fabs(uv[0]-uv2[0]) < limit[0] && fabs(uv[1]-uv2[1]) < limit[1]) {
1403                                         if(lastv) lastv->next= next;
1404                                         else vlist= next;
1405                                         iterv->next= newvlist;
1406                                         newvlist= iterv;
1407                                 }
1408                                 else
1409                                         lastv=iterv;
1410
1411                                 iterv= next;
1412                         }
1413
1414                         newvlist->separate = 1;
1415                 }
1416
1417                 vmap->vert[a]= newvlist;
1418         }
1419         
1420         return vmap;
1421 }
1422
1423 UvMapVert *get_uv_map_vert(UvVertMap *vmap, unsigned int v)
1424 {
1425         return vmap->vert[v];
1426 }
1427
1428 void free_uv_vert_map(UvVertMap *vmap)
1429 {
1430         if (vmap) {
1431                 if (vmap->vert) MEM_freeN(vmap->vert);
1432                 if (vmap->buf) MEM_freeN(vmap->buf);
1433                 MEM_freeN(vmap);
1434         }
1435 }
1436
1437 /* Generates a map where the key is the vertex and the value is a list
1438    of faces that use that vertex as a corner. The lists are allocated
1439    from one memory pool. */
1440 void create_vert_face_map(ListBase **map, IndexNode **mem, const MFace *mface, const int totvert, const int totface)
1441 {
1442         int i,j;
1443         IndexNode *node = NULL;
1444         
1445         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
1446         (*mem) = MEM_callocN(sizeof(IndexNode) * totface*4, "vert face map mem");
1447         node = *mem;
1448         
1449         /* Find the users */
1450         for(i = 0; i < totface; ++i){
1451                 for(j = 0; j < (mface[i].v4?4:3); ++j, ++node) {
1452                         node->index = i;
1453                         BLI_addtail(&(*map)[((unsigned int*)(&mface[i]))[j]], node);
1454                 }
1455         }
1456 }
1457
1458 /* Generates a map where the key is the vertex and the value is a list
1459    of edges that use that vertex as an endpoint. The lists are allocated
1460    from one memory pool. */
1461 void create_vert_edge_map(ListBase **map, IndexNode **mem, const MEdge *medge, const int totvert, const int totedge)
1462 {
1463         int i, j;
1464         IndexNode *node = NULL;
1465  
1466         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
1467         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge * 2, "vert edge map mem");
1468         node = *mem;
1469        
1470         /* Find the users */
1471         for(i = 0; i < totedge; ++i){
1472                 for(j = 0; j < 2; ++j, ++node) {
1473                         node->index = i;
1474                         BLI_addtail(&(*map)[((unsigned int*)(&medge[i].v1))[j]], node);
1475                 }
1476         }
1477 }
1478
1479 /* Partial Mesh Visibility */
1480 PartialVisibility *mesh_pmv_copy(PartialVisibility *pmv)
1481 {
1482         PartialVisibility *n= MEM_dupallocN(pmv);
1483         n->vert_map= MEM_dupallocN(pmv->vert_map);
1484         n->edge_map= MEM_dupallocN(pmv->edge_map);
1485         n->old_edges= MEM_dupallocN(pmv->old_edges);
1486         n->old_faces= MEM_dupallocN(pmv->old_faces);
1487         return n;
1488 }
1489
1490 void mesh_pmv_free(PartialVisibility *pv)
1491 {
1492         MEM_freeN(pv->vert_map);
1493         MEM_freeN(pv->edge_map);
1494         MEM_freeN(pv->old_faces);
1495         MEM_freeN(pv->old_edges);
1496         MEM_freeN(pv);
1497 }
1498
1499 void mesh_pmv_revert(Object *ob, Mesh *me)
1500 {
1501         if(me->pv) {
1502                 unsigned i;
1503                 MVert *nve, *old_verts;
1504                 
1505                 /* Reorder vertices */
1506                 nve= me->mvert;
1507                 old_verts = MEM_mallocN(sizeof(MVert)*me->pv->totvert,"PMV revert verts");
1508                 for(i=0; i<me->pv->totvert; ++i)
1509                         old_verts[i]= nve[me->pv->vert_map[i]];
1510
1511                 /* Restore verts, edges and faces */
1512                 CustomData_free_layer_active(&me->vdata, CD_MVERT, me->totvert);
1513                 CustomData_free_layer_active(&me->edata, CD_MEDGE, me->totedge);
1514                 CustomData_free_layer_active(&me->fdata, CD_MFACE, me->totface);
1515
1516                 CustomData_add_layer(&me->vdata, CD_MVERT, CD_ASSIGN, old_verts, me->pv->totvert);
1517                 CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, me->pv->old_edges, me->pv->totedge);
1518                 CustomData_add_layer(&me->fdata, CD_MFACE, CD_ASSIGN, me->pv->old_faces, me->pv->totface);
1519                 mesh_update_customdata_pointers(me);
1520
1521                 me->totvert= me->pv->totvert;
1522                 me->totedge= me->pv->totedge;
1523                 me->totface= me->pv->totface;
1524
1525                 me->pv->old_edges= NULL;
1526                 me->pv->old_faces= NULL;
1527
1528                 /* Free maps */
1529                 MEM_freeN(me->pv->edge_map);
1530                 me->pv->edge_map= NULL;
1531                 MEM_freeN(me->pv->vert_map);
1532                 me->pv->vert_map= NULL;
1533
1534 // XXX do this in caller                DAG_id_flush_update(&me->id, OB_RECALC_DATA);
1535         }
1536 }
1537
1538 void mesh_pmv_off(Object *ob, Mesh *me)
1539 {
1540         if(ob && me->pv) {
1541                 mesh_pmv_revert(ob, me);
1542                 MEM_freeN(me->pv);
1543                 me->pv= NULL;
1544         }
1545 }
1546
1547 static void mesh_loops_to_corners(CustomData *fdata, CustomData *ldata, 
1548                            CustomData *pdata, int lindex[3], int findex, 
1549                            int polyindex, int numTex, int numCol) 
1550 {
1551         MTFace *texface;
1552         MTexPoly *texpoly;
1553         MCol *mcol;
1554         MLoopCol *mloopcol;
1555         MLoopUV *mloopuv;
1556         int i, j, hasWCol = CustomData_has_layer(ldata, CD_WEIGHT_MLOOPCOL);
1557
1558         for(i=0; i < numTex; i++){
1559                 texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
1560                 texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, polyindex, i);
1561                 
1562                 texface->tpage = texpoly->tpage;
1563                 texface->flag = texpoly->flag;
1564                 texface->transp = texpoly->transp;
1565                 texface->mode = texpoly->mode;
1566                 texface->tile = texpoly->tile;
1567                 texface->unwrap = texpoly->unwrap;
1568
1569                 for (j=0; j<3; j++) {
1570                         mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, lindex[j], i);
1571                         texface->uv[j][0] = mloopuv->uv[0];
1572                         texface->uv[j][1] = mloopuv->uv[1];
1573                 }
1574         }
1575
1576         for(i=0; i < numCol; i++){
1577                 mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
1578
1579                 for (j=0; j<3; j++) {
1580                         mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, lindex[j], i);
1581                         mcol[j].r = mloopcol->r;
1582                         mcol[j].g = mloopcol->g;
1583                         mcol[j].b = mloopcol->b;
1584                         mcol[j].a = mloopcol->a;
1585                 }
1586         }
1587
1588         if (hasWCol) {
1589                 mcol = CustomData_get(fdata,  findex, CD_WEIGHT_MCOL);
1590
1591                 for (j=0; j<3; j++) {
1592                         mloopcol = CustomData_get(ldata, lindex[j], CD_WEIGHT_MLOOPCOL);
1593                         mcol[j].r = mloopcol->r;
1594                         mcol[j].g = mloopcol->g;
1595                         mcol[j].b = mloopcol->b;
1596                         mcol[j].a = mloopcol->a;
1597                 }
1598         }
1599 }
1600
1601 /*this function recreates a tesselation.
1602
1603   returns number of tesselation faces.*/
1604 int mesh_recalcTesselation(CustomData *fdata, 
1605                            CustomData *ldata, CustomData *pdata,
1606                            MVert *mvert, int totface, int totloop, 
1607                            int totpoly, int use_poly_origindex)
1608 {
1609         MPoly *mp, *mpoly;
1610         MLoop *ml, *mloop;
1611         MFace *mf = NULL, *mface;
1612         BLI_array_declare(mf);
1613         EditVert *v, *lastv, *firstv;
1614         EditFace *f;
1615         BLI_array_declare(origIndex);
1616         int i, j, k, lindex[3], *origIndex = NULL, *polyorigIndex;
1617         int numTex, numCol;
1618
1619         mpoly = CustomData_get_layer(pdata, CD_MPOLY);
1620         mloop = CustomData_get_layer(ldata, CD_MLOOP);
1621
1622         numTex = CustomData_number_of_layers(ldata, CD_MLOOPUV);
1623         numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
1624         
1625         k = 0;
1626         mp = mpoly;
1627         polyorigIndex = use_poly_origindex? CustomData_get_layer(pdata, CD_ORIGINDEX) : NULL;
1628         for (i=0; i<totpoly; i++, mp++) {
1629                 ml = mloop + mp->loopstart;
1630                 firstv = NULL;
1631                 lastv = NULL;
1632                 for (j=0; j<mp->totloop; j++, ml++) {
1633                         v = BLI_addfillvert(mvert[ml->v].co);
1634                         if (polyorigIndex)
1635                                 v->tmp.l = polyorigIndex[i];
1636                         else
1637                                 v->tmp.l = i;
1638
1639                         v->keyindex = mp->loopstart + j;
1640
1641                         if (lastv)
1642                                 BLI_addfilledge(lastv, v);
1643
1644                         if (!firstv)
1645                                 firstv = v;
1646                         lastv = v;
1647                 }
1648                 BLI_addfilledge(lastv, firstv);
1649                 
1650                 BLI_edgefill(0, 0);
1651                 for (f=fillfacebase.first; f; f=f->next) {
1652                         BLI_array_growone(mf);
1653                         BLI_array_growone(origIndex);
1654
1655                         /*these are loop indices, they'll be transformed
1656                           into vert indices later.*/
1657                         mf[k].v1 = f->v1->keyindex;
1658                         mf[k].v2 = f->v2->keyindex;
1659                         mf[k].v3 = f->v3->keyindex;
1660                         mf[k].mat_nr = mp->mat_nr;
1661                         mf[k].flag = mp->flag;
1662                         origIndex[k] = f->v1->tmp.l;
1663
1664                         k++;
1665                 }
1666
1667                 BLI_end_edgefill();
1668         }
1669
1670         CustomData_free(fdata, totface);
1671         memset(fdata, 0, sizeof(CustomData));
1672         totface = k;
1673         
1674         CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mf, totface);
1675         CustomData_add_layer(fdata, CD_ORIGINDEX, CD_ASSIGN, origIndex, totface);
1676         CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
1677
1678         mface = mf;
1679         for (i=0; i<totface; i++, mf++) {
1680                 /*ensure winding is correct*/
1681                 if (mf->v1 > mf->v2) {
1682                         SWAP(int, mf->v1, mf->v2);
1683                 }
1684                 if (mf->v2 > mf->v3) {
1685                         SWAP(int, mf->v2, mf->v3);
1686                 }
1687                 if (mf->v1 > mf->v2) {
1688                         SWAP(int, mf->v1, mf->v2);
1689                 }
1690
1691                 lindex[0] = mf->v1;
1692                 lindex[1] = mf->v2;
1693                 lindex[2] = mf->v3;
1694
1695                 /*transform loop indices to vert indices*/
1696                 mf->v1 = mloop[mf->v1].v;
1697                 mf->v2 = mloop[mf->v2].v;
1698                 mf->v3 = mloop[mf->v3].v;
1699
1700                 mesh_loops_to_corners(fdata, ldata, pdata,
1701                         lindex, i, origIndex[i], numTex, numCol);
1702         }
1703
1704         return totface;
1705 }
1706
1707 /*
1708  * COMPUTE POLY NORMAL
1709  *
1710  * Computes the normal of a planar 
1711  * polygon See Graphics Gems for 
1712  * computing newell normal.
1713  *
1714 */
1715 static void mesh_calc_ngon_normal(MPoly *mpoly, MLoop *loopstart, 
1716                                   MVert *mvert, float *normal)
1717 {
1718
1719         MVert *v1, *v2, *v3;
1720         double u[3],  v[3], w[3];
1721         double n[3] = {0.0, 0.0, 0.0}, l;
1722         int i, s=0;
1723
1724         for(i = 0; i < mpoly->totloop; i++){
1725                 v1 = mvert + loopstart[i].v;
1726                 v2 = mvert + loopstart[(i+1)%mpoly->totloop].v;
1727                 v3 = mvert + loopstart[(i+2)%mpoly->totloop].v;
1728                 
1729                 VECCOPY(u, v1->co);
1730                 VECCOPY(v, v2->co);
1731                 VECCOPY(w, v3->co);
1732
1733                 /*this fixes some weird numerical error*/
1734                 if (i==0) {
1735                         u[0] += 0.0001f;
1736                         u[1] += 0.0001f;
1737                         u[2] += 0.0001f;
1738                 }
1739                 
1740                 /* newell's method
1741                 
1742                 so thats?:
1743                 (a[1] - b[1]) * (a[2] + b[2]);
1744                 a[1]*b[2] - b[1]*a[2] - b[1]*b[2] + a[1]*a[2]
1745
1746                 odd.  half of that is the cross product. . .what's the
1747                 other half?
1748
1749                 also could be like a[1]*(b[2] + a[2]) - b[1]*(a[2] - b[2])
1750                 */
1751
1752                 n[0] += (u[1] - v[1]) * (u[2] + v[2]);
1753                 n[1] += (u[2] - v[2]) * (u[0] + v[0]);
1754                 n[2] += (u[0] - v[0]) * (u[1] + v[1]);
1755         }
1756         
1757         l = n[0]*n[0]+n[1]*n[1]+n[2]*n[2];
1758         l = sqrt(l);
1759
1760         if (l == 0.0) {
1761                 normal[0] = 0.0f;
1762                 normal[1] = 0.0f;
1763                 normal[2] = 1.0f;
1764
1765                 return;
1766         } else l = 1.0f / l;
1767
1768         n[0] *= l;
1769         n[1] *= l;
1770         n[2] *= l;
1771         
1772         normal[0] = (float) n[0];
1773         normal[1] = (float) n[1];
1774         normal[2] = (float) n[2];
1775
1776 }
1777
1778 void mesh_calc_poly_normal(MPoly *mpoly, MLoop *loopstart, 
1779                            MVert *mvarray, float *no)
1780 {
1781         if(mpoly->totloop > 4) {
1782                 mesh_calc_ngon_normal(mpoly, loopstart, mvarray, no);
1783         }
1784         else if(mpoly->totloop == 3){
1785                 MVert *v1, *v2, *v3;
1786
1787                 v1 = mvarray + (loopstart++)->v;
1788                 v2 = mvarray + (loopstart++)->v;
1789                 v3 = mvarray + loopstart->v;
1790                 normal_tri_v3( no,v1->co, v2->co, v3->co);
1791         }
1792         else if(mpoly->totloop == 4){
1793                 MVert *v1, *v2, *v3, *v4;
1794
1795                 v1 = mvarray + (loopstart++)->v;
1796                 v2 = mvarray + (loopstart++)->v;
1797                 v3 = mvarray + (loopstart++)->v;
1798                 v4 = mvarray + loopstart->v;
1799                 normal_quad_v3( no,v1->co, v2->co, v3->co, v4->co);
1800         }
1801         else{ /*horrible, two sided face!*/
1802                 no[0] = 0.0;
1803                 no[1] = 0.0;
1804                 no[2] = 1.0;
1805         }
1806 }