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