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