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