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