52c094acca443bb0df963a4b710b1a7bbba8bca5
[blender.git] / source / blender / blenkernel / intern / mesh.c
1
2 /*  mesh.c
3  *
4  *  
5  * 
6  * $Id$
7  *
8  * ***** BEGIN GPL/BL DUAL 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. The Blender
14  * Foundation also sells licenses for use in proprietary software under
15  * the Blender License.  See http://www.blender.org/BL/ for information
16  * about this.
17  *
18  * This program is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
21  * GNU General Public License for more details.
22  *
23  * You should have received a copy of the GNU General Public License
24  * along with this program; if not, write to the Free Software Foundation,
25  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
26  *
27  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
28  * All rights reserved.
29  *
30  * The Original Code is: all of this file.
31  *
32  * Contributor(s): none yet.
33  *
34  * ***** END GPL/BL DUAL LICENSE BLOCK *****
35  */
36
37 #ifdef HAVE_CONFIG_H
38 #include <config.h>
39 #endif
40
41 #include <stdlib.h>
42 #include <string.h>
43 #include <stdio.h>
44 #include <math.h>
45
46 #include "MEM_guardedalloc.h"
47
48 #include "DNA_ID.h"
49 #include "DNA_curve_types.h"
50 #include "DNA_material_types.h"
51 #include "DNA_object_types.h"
52 #include "DNA_image_types.h"
53 #include "DNA_key_types.h"
54 #include "DNA_mesh_types.h"
55 #include "DNA_meshdata_types.h"
56 #include "DNA_ipo_types.h"
57
58 #include "BDR_sculptmode.h"
59
60 #include "BKE_customdata.h"
61 #include "BKE_depsgraph.h"
62 #include "BKE_main.h"
63 #include "BKE_DerivedMesh.h"
64 #include "BKE_global.h"
65 #include "BKE_mesh.h"
66 #include "BKE_subsurf.h"
67 #include "BKE_displist.h"
68 #include "BKE_library.h"
69 #include "BKE_material.h"
70 #include "BKE_key.h"
71 /* these 2 are only used by conversion functions */
72 #include "BKE_curve.h"
73 /* -- */
74 #include "BKE_object.h"
75 #include "BKE_utildefines.h"
76 #include "BKE_bad_level_calls.h"
77
78 #ifdef WITH_VERSE
79 #include "BKE_verse.h"
80 #endif
81
82 #include "BLI_blenlib.h"
83 #include "BLI_editVert.h"
84 #include "BLI_arithb.h"
85
86 #include "multires.h"
87
88 int update_realtime_texture(MTFace *tface, double time)
89 {
90         Image *ima;
91         int     inc = 0;
92         float   diff;
93         int     newframe;
94
95         ima = tface->tpage;
96
97         if (!ima)
98                 return 0;
99
100         if (ima->lastupdate<0)
101                 ima->lastupdate = 0;
102
103         if (ima->lastupdate>time)
104                 ima->lastupdate=(float)time;
105
106         if(ima->tpageflag & IMA_TWINANIM) {
107                 if(ima->twend >= ima->xrep*ima->yrep) ima->twend= ima->xrep*ima->yrep-1;
108                 
109                 /* check: is the bindcode not in the array? Then free. (still to do) */
110                 
111                 diff = (float)(time-ima->lastupdate);
112
113                 inc = (int)(diff*(float)ima->animspeed);
114
115                 ima->lastupdate+=((float)inc/(float)ima->animspeed);
116
117                 newframe = ima->lastframe+inc;
118
119                 if (newframe > (int)ima->twend)
120                         newframe = (int)ima->twsta-1 + (newframe-ima->twend)%(ima->twend-ima->twsta);
121
122                 ima->lastframe = newframe;
123         }
124         return inc;
125 }
126
127 void mesh_update_customdata_pointers(Mesh *me)
128 {
129         me->mvert = CustomData_get_layer(&me->vdata, CD_MVERT);
130         me->dvert = CustomData_get_layer(&me->vdata, CD_MDEFORMVERT);
131         me->msticky = CustomData_get_layer(&me->vdata, CD_MSTICKY);
132
133         me->medge = CustomData_get_layer(&me->edata, CD_MEDGE);
134
135         me->mface = CustomData_get_layer(&me->fdata, CD_MFACE);
136         me->mcol = CustomData_get_layer(&me->fdata, CD_MCOL);
137         me->mtface = CustomData_get_layer(&me->fdata, CD_MTFACE);
138 }
139
140 /* Note: unlinking is called when me->id.us is 0, question remains how
141  * much unlinking of Library data in Mesh should be done... probably
142  * we need a more generic method, like the expand() functions in
143  * readfile.c */
144
145 void unlink_mesh(Mesh *me)
146 {
147         int a;
148         
149         if(me==0) return;
150         
151         for(a=0; a<me->totcol; a++) {
152                 if(me->mat[a]) me->mat[a]->id.us--;
153                 me->mat[a]= 0;
154         }
155
156         if(me->key) {
157                 me->key->id.us--;
158                 if (me->key->id.us == 0 && me->key->ipo )
159                         me->key->ipo->id.us--;
160         }
161         me->key= 0;
162         
163         if(me->texcomesh) me->texcomesh= 0;
164 }
165
166
167 /* do not free mesh itself */
168 void free_mesh(Mesh *me)
169 {
170         unlink_mesh(me);
171
172         if(me->pv) {
173                 if(me->pv->vert_map) MEM_freeN(me->pv->vert_map);
174                 if(me->pv->edge_map) MEM_freeN(me->pv->edge_map);
175                 if(me->pv->old_faces) MEM_freeN(me->pv->old_faces);
176                 if(me->pv->old_edges) MEM_freeN(me->pv->old_edges);
177                 MEM_freeN(me->pv);
178         }
179
180         CustomData_free(&me->vdata, me->totvert);
181         CustomData_free(&me->edata, me->totedge);
182         CustomData_free(&me->fdata, me->totface);
183
184         if(me->mat) MEM_freeN(me->mat);
185         
186         if(me->bb) MEM_freeN(me->bb);
187         if(me->mselect) MEM_freeN(me->mselect);
188
189         if(me->mr) multires_free(me->mr);
190 }
191
192 void copy_dverts(MDeformVert *dst, MDeformVert *src, int copycount)
193 {
194         /* Assumes dst is already set up */
195         int i;
196
197         if (!src || !dst)
198                 return;
199
200         memcpy (dst, src, copycount * sizeof(MDeformVert));
201         
202         for (i=0; i<copycount; i++){
203                 if (src[i].dw){
204                         dst[i].dw = MEM_callocN (sizeof(MDeformWeight)*src[i].totweight, "copy_deformWeight");
205                         memcpy (dst[i].dw, src[i].dw, sizeof (MDeformWeight)*src[i].totweight);
206                 }
207         }
208
209 }
210
211 void free_dverts(MDeformVert *dvert, int totvert)
212 {
213         /* Instead of freeing the verts directly,
214         call this function to delete any special
215         vert data */
216         int     i;
217
218         if (!dvert)
219                 return;
220
221         /* Free any special data from the verts */
222         for (i=0; i<totvert; i++){
223                 if (dvert[i].dw) MEM_freeN (dvert[i].dw);
224         }
225         MEM_freeN (dvert);
226 }
227
228 Mesh *add_mesh()
229 {
230         Mesh *me;
231         
232         me= alloc_libblock(&G.main->mesh, ID_ME, "Mesh");
233         
234         me->size[0]= me->size[1]= me->size[2]= 1.0;
235         me->smoothresh= 30;
236         me->texflag= AUTOSPACE;
237         me->flag= ME_TWOSIDED;
238         me->bb= unit_boundbox();
239
240 #ifdef WITH_VERSE
241         me->vnode = NULL;
242 #endif
243
244         return me;
245 }
246
247 Mesh *copy_mesh(Mesh *me)
248 {
249         Mesh *men;
250         int a;
251         
252         men= copy_libblock(me);
253         
254         men->mat= MEM_dupallocN(me->mat);
255         for(a=0; a<men->totcol; a++) {
256                 id_us_plus((ID *)men->mat[a]);
257         }
258         id_us_plus((ID *)men->texcomesh);
259
260         CustomData_copy(&me->vdata, &men->vdata, CD_MASK_MESH, CD_DUPLICATE, men->totvert);
261         CustomData_copy(&me->edata, &men->edata, CD_MASK_MESH, CD_DUPLICATE, men->totedge);
262         CustomData_copy(&me->fdata, &men->fdata, CD_MASK_MESH, CD_DUPLICATE, men->totface);
263         mesh_update_customdata_pointers(men);
264
265         if (me->mtface){
266                 /* ensure indirect linked data becomes lib-extern */
267                 MTFace *tface= me->mtface;
268                 for(a=0; a<me->totface; a++, tface++)
269                         if(tface->tpage)
270                                 id_lib_extern((ID*)tface->tpage);
271         }
272         
273         if(me->mr)
274                 men->mr= multires_copy(me->mr);
275
276         men->mselect= NULL;
277
278         men->bb= MEM_dupallocN(men->bb);
279         
280         men->key= copy_key(me->key);
281         if(men->key) men->key->from= (ID *)men;
282
283 #ifdef WITH_VERSE
284         men->vnode = NULL;
285 #endif  
286
287         return men;
288 }
289
290 void make_local_tface(Mesh *me)
291 {
292         MTFace *tface;
293         Image *ima;
294         int a;
295         
296         if(me->mtface==0) return;
297         
298         a= me->totface;
299         tface= me->mtface;
300         while(a--) {
301                 
302                 /* special case: ima always local immediately */
303                 if(tface->tpage) {
304                         ima= tface->tpage;
305                         if(ima->id.lib) {
306                                 ima->id.lib= 0;
307                                 ima->id.flag= LIB_LOCAL;
308                                 new_id(0, (ID *)ima, 0);
309                         }
310                 }
311                 tface++;
312         }
313         
314 }
315
316 void make_local_mesh(Mesh *me)
317 {
318         Object *ob;
319         Mesh *men;
320         int local=0, lib=0;
321
322         /* - only lib users: do nothing
323             * - only local users: set flag
324             * - mixed: make copy
325             */
326         
327         if(me->id.lib==0) return;
328         if(me->id.us==1) {
329                 me->id.lib= 0;
330                 me->id.flag= LIB_LOCAL;
331                 new_id(0, (ID *)me, 0);
332                 
333                 if(me->mtface) make_local_tface(me);
334                 
335                 return;
336         }
337         
338         ob= G.main->object.first;
339         while(ob) {
340                 if( me==get_mesh(ob) ) {
341                         if(ob->id.lib) lib= 1;
342                         else local= 1;
343                 }
344                 ob= ob->id.next;
345         }
346         
347         if(local && lib==0) {
348                 me->id.lib= 0;
349                 me->id.flag= LIB_LOCAL;
350                 new_id(0, (ID *)me, 0);
351                 
352                 if(me->mtface) make_local_tface(me);
353                 
354         }
355         else if(local && lib) {
356                 men= copy_mesh(me);
357                 men->id.us= 0;
358                 
359                 ob= G.main->object.first;
360                 while(ob) {
361                         if( me==get_mesh(ob) ) {                                
362                                 if(ob->id.lib==0) {
363                                         set_mesh(ob, men);
364                                 }
365                         }
366                         ob= ob->id.next;
367                 }
368         }
369 }
370
371 void boundbox_mesh(Mesh *me, float *loc, float *size)
372 {
373         MVert *mvert;
374         BoundBox *bb;
375         float min[3], max[3];
376         float mloc[3], msize[3];
377         int a;
378         
379         if(me->bb==0) me->bb= MEM_callocN(sizeof(BoundBox), "boundbox");
380         bb= me->bb;
381         
382         INIT_MINMAX(min, max);
383
384         if (!loc) loc= mloc;
385         if (!size) size= msize;
386         
387         mvert= me->mvert;
388         for(a=0; a<me->totvert; a++, mvert++) {
389                 DO_MINMAX(mvert->co, min, max);
390         }
391
392         if(!me->totvert) {
393                 min[0] = min[1] = min[2] = -1.0f;
394                 max[0] = max[1] = max[2] = 1.0f;
395         }
396
397         loc[0]= (min[0]+max[0])/2.0f;
398         loc[1]= (min[1]+max[1])/2.0f;
399         loc[2]= (min[2]+max[2])/2.0f;
400                 
401         size[0]= (max[0]-min[0])/2.0f;
402         size[1]= (max[1]-min[1])/2.0f;
403         size[2]= (max[2]-min[2])/2.0f;
404         
405         boundbox_set_from_min_max(bb, min, max);
406 }
407
408 void tex_space_mesh(Mesh *me)
409 {
410         KeyBlock *kb;
411         float *fp, loc[3], size[3], min[3], max[3];
412         int a;
413
414         boundbox_mesh(me, loc, size);
415
416         if(me->texflag & AUTOSPACE) {
417                 if(me->key) {
418                         kb= me->key->refkey;
419                         if (kb) {
420                                 
421                                 INIT_MINMAX(min, max);
422                                 
423                                 fp= kb->data;
424                                 for(a=0; a<kb->totelem; a++, fp+=3) {   
425                                         DO_MINMAX(fp, min, max);
426                                 }
427                                 if(kb->totelem) {
428                                         loc[0]= (min[0]+max[0])/2.0f; loc[1]= (min[1]+max[1])/2.0f; loc[2]= (min[2]+max[2])/2.0f;
429                                         size[0]= (max[0]-min[0])/2.0f; size[1]= (max[1]-min[1])/2.0f; size[2]= (max[2]-min[2])/2.0f;
430                                 }
431                                 else {
432                                         loc[0]= loc[1]= loc[2]= 0.0;
433                                         size[0]= size[1]= size[2]= 0.0;
434                                 }
435                                 
436                         }
437                 }
438
439                 for (a=0; a<3; a++) {
440                         if(size[a]==0.0) size[a]= 1.0;
441                         else if(size[a]>0.0 && size[a]<0.00001) size[a]= 0.00001;
442                         else if(size[a]<0.0 && size[a]> -0.00001) size[a]= -0.00001;
443                 }
444
445                 VECCOPY(me->loc, loc);
446                 VECCOPY(me->size, size);
447                 me->rot[0]= me->rot[1]= me->rot[2]= 0.0;
448         }
449 }
450
451 BoundBox *mesh_get_bb(Mesh *me)
452 {
453         if (!me->bb) {
454                 tex_space_mesh(me);
455         }
456
457         return me->bb;
458 }
459
460 void mesh_get_texspace(Mesh *me, float *loc_r, float *rot_r, float *size_r)
461 {
462         if (!me->bb) {
463                 tex_space_mesh(me);
464         }
465
466         if (loc_r) VECCOPY(loc_r, me->loc);
467         if (rot_r) VECCOPY(rot_r, me->rot);
468         if (size_r) VECCOPY(size_r, me->size);
469 }
470
471 static float *make_orco_mesh_internal(Object *ob, int render)
472 {
473         Mesh *me = ob->data;
474         float (*orcoData)[3];
475         int a, totvert;
476         float loc[3], size[3];
477         DerivedMesh *dm;
478         float (*vcos)[3] = MEM_callocN(sizeof(*vcos)*me->totvert, "orco mesh");
479
480                 /* Get appropriate vertex coordinates */
481
482         if(me->key && me->texcomesh==0 && me->key->refkey) {
483                 KeyBlock *kb= me->key->refkey;
484                 float *fp= kb->data;
485                 totvert= MIN2(kb->totelem, me->totvert);
486
487                 for(a=0; a<totvert; a++, fp+=3) {
488                         vcos[a][0]= fp[0];
489                         vcos[a][1]= fp[1];
490                         vcos[a][2]= fp[2];
491                 }
492         }
493         else {
494                 Mesh *tme = me->texcomesh?me->texcomesh:me;
495                 MVert *mvert = tme->mvert;
496                 totvert = MIN2(tme->totvert, me->totvert);
497
498                 for(a=0; a<totvert; a++, mvert++) {
499                         vcos[a][0]= mvert->co[0];
500                         vcos[a][1]= mvert->co[1];
501                         vcos[a][2]= mvert->co[2];
502                 }
503         }
504
505                 /* Apply orco-changing modifiers */
506
507         if (render) {
508                 dm = mesh_create_derived_no_deform_render(ob, vcos, CD_MASK_BAREMESH);
509         } else {
510                 dm = mesh_create_derived_no_deform(ob, vcos, CD_MASK_BAREMESH);
511         }
512         totvert = dm->getNumVerts(dm);
513
514         orcoData = MEM_mallocN(sizeof(*orcoData)*totvert, "orcoData");
515         dm->getVertCos(dm, orcoData);
516         dm->release(dm);
517         MEM_freeN(vcos);
518
519         mesh_get_texspace(me->texcomesh?me->texcomesh:me, loc, NULL, size);
520
521         for(a=0; a<totvert; a++) {
522                 float *co = orcoData[a];
523                 co[0] = (co[0]-loc[0])/size[0];
524                 co[1] = (co[1]-loc[1])/size[1];
525                 co[2] = (co[2]-loc[2])/size[2];
526         }
527
528         return (float*) orcoData;
529 }
530
531 float *mesh_create_orco_render(Object *ob) 
532 {
533         return make_orco_mesh_internal(ob, 1);
534 }
535
536 float *mesh_create_orco(Object *ob)
537 {
538         return make_orco_mesh_internal(ob, 0);
539 }
540
541 /* rotates the vertices of a face in case v[2] or v[3] (vertex index) is = 0.
542    this is necessary to make the if(mface->v4) check for quads work */
543 void test_index_face(MFace *mface, CustomData *fdata, int mfindex, int nr)
544 {
545         /* first test if the face is legal */
546         if(mface->v3 && mface->v3==mface->v4) {
547                 mface->v4= 0;
548                 nr--;
549         }
550         if(mface->v2 && mface->v2==mface->v3) {
551                 mface->v3= mface->v4;
552                 mface->v4= 0;
553                 nr--;
554         }
555         if(mface->v1==mface->v2) {
556                 mface->v2= mface->v3;
557                 mface->v3= mface->v4;
558                 mface->v4= 0;
559                 nr--;
560         }
561
562         /* prevent a zero at wrong index location */
563         if(nr==3) {
564                 if(mface->v3==0) {
565                         static int corner_indices[4] = {1, 2, 0, 3};
566
567                         SWAP(int, mface->v1, mface->v2);
568                         SWAP(int, mface->v2, mface->v3);
569
570                         if(fdata)
571                                 CustomData_swap(fdata, mfindex, corner_indices);
572                 }
573         }
574         else if(nr==4) {
575                 if(mface->v3==0 || mface->v4==0) {
576                         static int corner_indices[4] = {2, 3, 0, 1};
577
578                         SWAP(int, mface->v1, mface->v3);
579                         SWAP(int, mface->v2, mface->v4);
580
581                         if(fdata)
582                                 CustomData_swap(fdata, mfindex, corner_indices);
583                 }
584         }
585 }
586
587 Mesh *get_mesh(Object *ob)
588 {
589         
590         if(ob==0) return 0;
591         if(ob->type==OB_MESH) return ob->data;
592         else return 0;
593 }
594
595 void set_mesh(Object *ob, Mesh *me)
596 {
597         Mesh *old=0;
598         
599         if(ob==0) return;
600         
601         if(ob->type==OB_MESH) {
602                 old= ob->data;
603                 old->id.us--;
604                 ob->data= me;
605                 id_us_plus((ID *)me);
606         }
607         
608         test_object_materials((ID *)me);
609 }
610
611 /* ************** make edges in a Mesh, for outside of editmode */
612
613 struct edgesort {
614         int v1, v2;
615         short is_loose, is_draw;
616 };
617
618 /* edges have to be added with lowest index first for sorting */
619 static void to_edgesort(struct edgesort *ed, int v1, int v2, short is_loose, short is_draw)
620 {
621         if(v1<v2) {
622                 ed->v1= v1; ed->v2= v2;
623         }
624         else {
625                 ed->v1= v2; ed->v2= v1;
626         }
627         ed->is_loose= is_loose;
628         ed->is_draw= is_draw;
629 }
630
631 static int vergedgesort(const void *v1, const void *v2)
632 {
633         const struct edgesort *x1=v1, *x2=v2;
634
635         if( x1->v1 > x2->v1) return 1;
636         else if( x1->v1 < x2->v1) return -1;
637         else if( x1->v2 > x2->v2) return 1;
638         else if( x1->v2 < x2->v2) return -1;
639         
640         return 0;
641 }
642
643 void make_edges(Mesh *me, int old)
644 {
645         MFace *mface;
646         MEdge *medge;
647         struct edgesort *edsort, *ed;
648         int a, totedge=0, final=0;
649         
650         /* we put all edges in array, sort them, and detect doubles that way */
651         
652         for(a= me->totface, mface= me->mface; a>0; a--, mface++) {
653                 if(mface->v4) totedge+=4;
654                 else if(mface->v3) totedge+=3;
655                 else totedge+=1;
656         }
657         
658         if(totedge==0) {
659                 /* flag that mesh has edges */
660                 me->medge = MEM_callocN(0, "make mesh edges");
661                 me->totedge = 0;
662                 return;
663         }
664         
665         ed= edsort= MEM_mallocN(totedge*sizeof(struct edgesort), "edgesort");
666         
667         for(a= me->totface, mface= me->mface; a>0; a--, mface++) {
668                 to_edgesort(ed++, mface->v1, mface->v2, !mface->v3, mface->edcode & ME_V1V2);
669                 if(mface->v4) {
670                         to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
671                         to_edgesort(ed++, mface->v3, mface->v4, 0, mface->edcode & ME_V3V4);
672                         to_edgesort(ed++, mface->v4, mface->v1, 0, mface->edcode & ME_V4V1);
673                 }
674                 else if(mface->v3) {
675                         to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
676                         to_edgesort(ed++, mface->v3, mface->v1, 0, mface->edcode & ME_V3V1);
677                 }
678         }
679         
680         qsort(edsort, totedge, sizeof(struct edgesort), vergedgesort);
681         
682         /* count final amount */
683         for(a=totedge, ed=edsort; a>1; a--, ed++) {
684                 /* edge is unique when it differs from next edge, or is last */
685                 if(ed->v1 != (ed+1)->v1 || ed->v2 != (ed+1)->v2) final++;
686         }
687         final++;
688         
689
690         medge= me->medge= CustomData_add_layer(&me->edata, CD_MEDGE, 0, NULL, final);
691         me->totedge= final;
692         
693         for(a=totedge, ed=edsort; a>1; a--, ed++) {
694                 /* edge is unique when it differs from next edge, or is last */
695                 if(ed->v1 != (ed+1)->v1 || ed->v2 != (ed+1)->v2) {
696                         medge->v1= ed->v1;
697                         medge->v2= ed->v2;
698                         if(old==0 || ed->is_draw) medge->flag= ME_EDGEDRAW|ME_EDGERENDER;
699                         if(ed->is_loose) medge->flag|= ME_LOOSEEDGE;
700                         medge++;
701                 }
702                 else {
703                         /* equal edge, we merge the drawflag */
704                         (ed+1)->is_draw |= ed->is_draw;
705                 }
706         }
707         /* last edge */
708         medge->v1= ed->v1;
709         medge->v2= ed->v2;
710         medge->flag= ME_EDGEDRAW;
711         if(ed->is_loose) medge->flag|= ME_LOOSEEDGE;
712         medge->flag |= ME_EDGERENDER;
713
714         MEM_freeN(edsort);
715
716         mesh_strip_loose_faces(me);
717 }
718
719 void mesh_strip_loose_faces(Mesh *me)
720 {
721         int a,b;
722
723         for (a=b=0; a<me->totface; a++) {
724                 if (me->mface[a].v3) {
725                         if (a!=b) {
726                                 memcpy(&me->mface[b],&me->mface[a],sizeof(me->mface[b]));
727                                 CustomData_copy_data(&me->fdata, &me->fdata, a, b, 1);
728                                 CustomData_free_elem(&me->fdata, a, 1);
729                         }
730                         b++;
731                 }
732         }
733         me->totface = b;
734 }
735
736
737 void mball_to_mesh(ListBase *lb, Mesh *me)
738 {
739         DispList *dl;
740         MVert *mvert;
741         MFace *mface;
742         float *nors, *verts;
743         int a, *index;
744         
745         dl= lb->first;
746         if(dl==0) return;
747
748         if(dl->type==DL_INDEX4) {
749                 me->flag= ME_NOPUNOFLIP;
750                 me->totvert= dl->nr;
751                 me->totface= dl->parts;
752                 
753                 mvert= CustomData_add_layer(&me->vdata, CD_MVERT, 0, NULL, dl->nr);
754                 mface= CustomData_add_layer(&me->fdata, CD_MFACE, 0, NULL, dl->parts);
755                 me->mvert= mvert;
756                 me->mface= mface;
757
758                 a= dl->nr;
759                 nors= dl->nors;
760                 verts= dl->verts;
761                 while(a--) {
762                         VECCOPY(mvert->co, verts);
763                         mvert->no[0]= (short int)(nors[0]*32767.0);
764                         mvert->no[1]= (short int)(nors[1]*32767.0);
765                         mvert->no[2]= (short int)(nors[2]*32767.0);
766                         mvert++;
767                         nors+= 3;
768                         verts+= 3;
769                 }
770                 
771                 a= dl->parts;
772                 index= dl->index;
773                 while(a--) {
774                         mface->v1= index[0];
775                         mface->v2= index[1];
776                         mface->v3= index[2];
777                         mface->v4= index[3];
778                         mface->flag= ME_SMOOTH;
779
780                         if(mface->v3==mface->v4)
781                                 mface->v4= 0;
782
783                         mface++;
784                         index+= 4;
785                 }
786
787                 make_edges(me, 0);      // all edges
788         }       
789 }
790
791 void nurbs_to_mesh(Object *ob)
792 {
793         Object *ob1;
794         DispList *dl;
795         Mesh *me;
796         Curve *cu;
797         MVert *mvert;
798         MFace *mface;
799         float *data;
800         int a, b, ofs, vertcount, startvert, totvert=0, totvlak=0;
801         int p1, p2, p3, p4, *index;
802
803         cu= ob->data;
804
805         /* count */
806         dl= cu->disp.first;
807         while(dl) {
808                 if(dl->type==DL_SEGM) {
809                         totvert+= dl->parts*dl->nr;
810                         totvlak+= dl->parts*(dl->nr-1);
811                 }
812                 else if(dl->type==DL_POLY) {
813                         /* cyclic polys are filled. except when 3D */
814                         if(cu->flag & CU_3D) {
815                                 totvert+= dl->parts*dl->nr;
816                                 totvlak+= dl->parts*dl->nr;
817                         }
818                 }
819                 else if(dl->type==DL_SURF) {
820                         totvert+= dl->parts*dl->nr;
821                         totvlak+= (dl->parts-1+((dl->flag & DL_CYCL_V)==2))*(dl->nr-1+(dl->flag & DL_CYCL_U));
822                 }
823                 else if(dl->type==DL_INDEX3) {
824                         totvert+= dl->nr;
825                         totvlak+= dl->parts;
826                 }
827                 dl= dl->next;
828         }
829         if(totvert==0) {
830                 error("can't convert");
831                 return;
832         }
833
834         /* make mesh */
835         me= add_mesh();
836         me->totvert= totvert;
837         me->totface= totvlak;
838
839         me->totcol= cu->totcol;
840         me->mat= cu->mat;
841         cu->mat= 0;
842         cu->totcol= 0;
843
844         mvert= CustomData_add_layer(&me->vdata, CD_MVERT, 0, NULL, me->totvert);
845         mface= CustomData_add_layer(&me->fdata, CD_MFACE, 0, NULL, me->totface);
846         me->mvert= mvert;
847         me->mface= mface;
848
849         /* verts and faces */
850         vertcount= 0;
851
852         dl= cu->disp.first;
853         while(dl) {
854                 if(dl->type==DL_SEGM) {
855                         startvert= vertcount;
856                         a= dl->parts*dl->nr;
857                         data= dl->verts;
858                         while(a--) {
859                                 VECCOPY(mvert->co, data);
860                                 data+=3;
861                                 vertcount++;
862                                 mvert++;
863                         }
864
865                         for(a=0; a<dl->parts; a++) {
866                                 ofs= a*dl->nr;
867                                 for(b=1; b<dl->nr; b++) {
868                                         mface->v1= startvert+ofs+b-1;
869                                         mface->v2= startvert+ofs+b;
870                                         mface++;
871                                 }
872                         }
873
874                 }
875                 else if(dl->type==DL_POLY) {
876                         /* 3d polys are not filled */
877                         if(cu->flag & CU_3D) {
878                                 startvert= vertcount;
879                                 a= dl->parts*dl->nr;
880                                 data= dl->verts;
881                                 while(a--) {
882                                         VECCOPY(mvert->co, data);
883                                         data+=3;
884                                         vertcount++;
885                                         mvert++;
886                                 }
887         
888                                 for(a=0; a<dl->parts; a++) {
889                                         ofs= a*dl->nr;
890                                         for(b=0; b<dl->nr; b++) {
891                                                 mface->v1= startvert+ofs+b;
892                                                 if(b==dl->nr-1) mface->v2= startvert+ofs;
893                                                 else mface->v2= startvert+ofs+b+1;
894                                                 mface++;
895                                         }
896                                 }
897                         }
898                 }
899                 else if(dl->type==DL_INDEX3) {
900                         startvert= vertcount;
901                         a= dl->nr;
902                         data= dl->verts;
903                         while(a--) {
904                                 VECCOPY(mvert->co, data);
905                                 data+=3;
906                                 vertcount++;
907                                 mvert++;
908                         }
909
910                         a= dl->parts;
911                         index= dl->index;
912                         while(a--) {
913                                 mface->v1= startvert+index[0];
914                                 mface->v2= startvert+index[1];
915                                 mface->v3= startvert+index[2];
916                                 mface->v4= 0;
917                                 test_index_face(mface, NULL, 0, 3);
918                                 
919                                 mface++;
920                                 index+= 3;
921                         }
922         
923         
924                 }
925                 else if(dl->type==DL_SURF) {
926                         startvert= vertcount;
927                         a= dl->parts*dl->nr;
928                         data= dl->verts;
929                         while(a--) {
930                                 VECCOPY(mvert->co, data);
931                                 data+=3;
932                                 vertcount++;
933                                 mvert++;
934                         }
935
936                         for(a=0; a<dl->parts; a++) {
937
938                                 if( (dl->flag & DL_CYCL_V)==0 && a==dl->parts-1) break;
939
940                                 if(dl->flag & DL_CYCL_U) {                      /* p2 -> p1 -> */
941                                         p1= startvert+ dl->nr*a;        /* p4 -> p3 -> */
942                                         p2= p1+ dl->nr-1;               /* -----> next row */
943                                         p3= p1+ dl->nr;
944                                         p4= p2+ dl->nr;
945                                         b= 0;
946                                 }
947                                 else {
948                                         p2= startvert+ dl->nr*a;
949                                         p1= p2+1;
950                                         p4= p2+ dl->nr;
951                                         p3= p1+ dl->nr;
952                                         b= 1;
953                                 }
954                                 if( (dl->flag & DL_CYCL_V) && a==dl->parts-1) {
955                                         p3-= dl->parts*dl->nr;
956                                         p4-= dl->parts*dl->nr;
957                                 }
958
959                                 for(; b<dl->nr; b++) {
960                                         mface->v1= p1;
961                                         mface->v2= p3;
962                                         mface->v3= p4;
963                                         mface->v4= p2;
964                                         mface->mat_nr= (unsigned char)dl->col;
965                                         test_index_face(mface, NULL, 0, 4);
966                                         mface++;
967
968                                         p4= p3; 
969                                         p3++;
970                                         p2= p1; 
971                                         p1++;
972                                 }
973                         }
974
975                 }
976
977                 dl= dl->next;
978         }
979
980         make_edges(me, 0);      // all edges
981         mesh_calc_normals(me->mvert, me->totvert, me->mface, me->totface, NULL);
982
983         if(ob->data) {
984                 free_libblock(&G.main->curve, ob->data);
985         }
986         ob->data= me;
987         ob->type= OB_MESH;
988         
989         /* other users */
990         ob1= G.main->object.first;
991         while(ob1) {
992                 if(ob1->data==cu) {
993                         ob1->type= OB_MESH;
994                 
995                         ob1->data= ob->data;
996                         id_us_plus((ID *)ob->data);
997                 }
998                 ob1= ob1->id.next;
999         }
1000
1001 }
1002
1003 void mesh_delete_material_index(Mesh *me, int index) {
1004         int i;
1005
1006         for (i=0; i<me->totface; i++) {
1007                 MFace *mf = &((MFace*) me->mface)[i];
1008                 if (mf->mat_nr && mf->mat_nr>=index) 
1009                         mf->mat_nr--;
1010         }
1011 }
1012
1013 void mesh_set_smooth_flag(Object *meshOb, int enableSmooth) {
1014         Mesh *me = meshOb->data;
1015         int i;
1016
1017         for (i=0; i<me->totface; i++) {
1018                 MFace *mf = &((MFace*) me->mface)[i];
1019
1020                 if (enableSmooth) {
1021                         mf->flag |= ME_SMOOTH;
1022                 } else {
1023                         mf->flag &= ~ME_SMOOTH;
1024                 }
1025         }
1026
1027         DAG_object_flush_update(G.scene, meshOb, OB_RECALC_DATA);
1028 }
1029
1030 void mesh_calc_normals(MVert *mverts, int numVerts, MFace *mfaces, int numFaces, float **faceNors_r) 
1031 {
1032         float (*tnorms)[3]= MEM_callocN(numVerts*sizeof(*tnorms), "tnorms");
1033         float *fnors= MEM_mallocN(sizeof(*fnors)*3*numFaces, "meshnormals");
1034         int i;
1035
1036         for (i=0; i<numFaces; i++) {
1037                 MFace *mf= &mfaces[i];
1038                 float *f_no= &fnors[i*3];
1039
1040                 if (mf->v4)
1041                         CalcNormFloat4(mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, mverts[mf->v4].co, f_no);
1042                 else
1043                         CalcNormFloat(mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, f_no);
1044                 
1045                 VecAddf(tnorms[mf->v1], tnorms[mf->v1], f_no);
1046                 VecAddf(tnorms[mf->v2], tnorms[mf->v2], f_no);
1047                 VecAddf(tnorms[mf->v3], tnorms[mf->v3], f_no);
1048                 if (mf->v4)
1049                         VecAddf(tnorms[mf->v4], tnorms[mf->v4], f_no);
1050         }
1051         for (i=0; i<numVerts; i++) {
1052                 MVert *mv= &mverts[i];
1053                 float *no= tnorms[i];
1054                 
1055                 if (Normalise(no)==0.0) {
1056                         VECCOPY(no, mv->co);
1057                         Normalise(no);
1058                 }
1059
1060                 mv->no[0]= (short)(no[0]*32767.0);
1061                 mv->no[1]= (short)(no[1]*32767.0);
1062                 mv->no[2]= (short)(no[2]*32767.0);
1063         }
1064         
1065         MEM_freeN(tnorms);
1066
1067         if (faceNors_r) {
1068                 *faceNors_r = fnors;
1069         } else {
1070                 MEM_freeN(fnors);
1071         }
1072 }
1073
1074 float (*mesh_getVertexCos(Mesh *me, int *numVerts_r))[3]
1075 {
1076 #ifdef WITH_VERSE
1077         if(me->vnode) {
1078                 struct VLayer *vlayer;
1079                 struct VerseVert *vvert;
1080                 unsigned int i, numVerts;
1081                 float (*cos)[3];
1082
1083                 vlayer = find_verse_layer_type((VGeomData*)((VNode*)me->vnode)->data, VERTEX_LAYER);
1084
1085                 vvert = vlayer->dl.lb.first;
1086                 numVerts = vlayer->dl.da.count;
1087                 cos = MEM_mallocN(sizeof(*cos)*numVerts, "verse_vertexcos");
1088
1089                 for(i=0; i<numVerts && vvert; vvert = vvert->next, i++) {
1090                         VECCOPY(cos[i], vvert->co);
1091                 }
1092
1093                 return cos;
1094         }
1095         else {
1096 #endif
1097                 int i, numVerts = me->totvert;
1098                 float (*cos)[3] = MEM_mallocN(sizeof(*cos)*numVerts, "vertexcos1");
1099         
1100                 if (numVerts_r) *numVerts_r = numVerts;
1101                 for (i=0; i<numVerts; i++) {
1102                         VECCOPY(cos[i], me->mvert[i].co);
1103                 }
1104         
1105                 return cos;
1106 #ifdef WITH_VERSE
1107         }
1108 #endif
1109 }
1110
1111 /* UvVertMap */
1112
1113 struct UvVertMap {
1114         struct UvMapVert **vert;
1115         struct UvMapVert *buf;
1116 };
1117
1118 UvVertMap *make_uv_vert_map(struct MFace *mface, struct MTFace *tface, unsigned int totface, unsigned int totvert, int selected, float *limit)
1119 {
1120         UvVertMap *vmap;
1121         UvMapVert *buf;
1122         MFace *mf;
1123         MTFace *tf;
1124         unsigned int a;
1125         int     i, totuv, nverts;
1126
1127         totuv = 0;
1128
1129         /* generate UvMapVert array */
1130         mf= mface;
1131         tf= tface;
1132         for(a=0; a<totface; a++, mf++, tf++)
1133                 if(!selected || (!(tf->flag & TF_HIDE) && (tf->flag & TF_SELECT)))
1134                         totuv += (mf->v4)? 4: 3;
1135                 
1136         if(totuv==0)
1137                 return NULL;
1138         
1139         vmap= (UvVertMap*)MEM_mallocN(sizeof(*vmap), "UvVertMap");
1140         if (!vmap)
1141                 return NULL;
1142
1143         vmap->vert= (UvMapVert**)MEM_callocN(sizeof(*vmap->vert)*totvert, "UvMapVert*");
1144         buf= vmap->buf= (UvMapVert*)MEM_mallocN(sizeof(*vmap->buf)*totuv, "UvMapVert");
1145
1146         if (!vmap->vert || !vmap->buf) {
1147                 free_uv_vert_map(vmap);
1148                 return NULL;
1149         }
1150
1151         mf= mface;
1152         tf= tface;
1153         for(a=0; a<totface; a++, mf++, tf++) {
1154                 if(!selected || (!(tf->flag & TF_HIDE) && (tf->flag & TF_SELECT))) {
1155                         nverts= (mf->v4)? 4: 3;
1156
1157                         for(i=0; i<nverts; i++) {
1158                                 buf->tfindex= i;
1159                                 buf->f= a;
1160                                 buf->separate = 0;
1161                                 buf->next= vmap->vert[*(&mf->v1 + i)];
1162                                 vmap->vert[*(&mf->v1 + i)]= buf;
1163                                 buf++;
1164                         }
1165                 }
1166         }
1167         
1168         /* sort individual uvs for each vert */
1169         tf= tface;
1170         for(a=0; a<totvert; a++) {
1171                 UvMapVert *newvlist= NULL, *vlist=vmap->vert[a];
1172                 UvMapVert *iterv, *v, *lastv, *next;
1173                 float *uv, *uv2, uvdiff[2];
1174
1175                 while(vlist) {
1176                         v= vlist;
1177                         vlist= vlist->next;
1178                         v->next= newvlist;
1179                         newvlist= v;
1180
1181                         uv= (tf+v->f)->uv[v->tfindex];
1182                         lastv= NULL;
1183                         iterv= vlist;
1184
1185                         while(iterv) {
1186                                 next= iterv->next;
1187
1188                                 uv2= (tf+iterv->f)->uv[iterv->tfindex];
1189                                 Vec2Subf(uvdiff, uv2, uv);
1190
1191
1192                                 if(fabs(uv[0]-uv2[0]) < limit[0] && fabs(uv[1]-uv2[1]) < limit[1]) {
1193                                         if(lastv) lastv->next= next;
1194                                         else vlist= next;
1195                                         iterv->next= newvlist;
1196                                         newvlist= iterv;
1197                                 }
1198                                 else
1199                                         lastv=iterv;
1200
1201                                 iterv= next;
1202                         }
1203
1204                         newvlist->separate = 1;
1205                 }
1206
1207                 vmap->vert[a]= newvlist;
1208         }
1209         
1210         return vmap;
1211 }
1212
1213 UvMapVert *get_uv_map_vert(UvVertMap *vmap, unsigned int v)
1214 {
1215         return vmap->vert[v];
1216 }
1217
1218 void free_uv_vert_map(UvVertMap *vmap)
1219 {
1220         if (vmap) {
1221                 if (vmap->vert) MEM_freeN(vmap->vert);
1222                 if (vmap->buf) MEM_freeN(vmap->buf);
1223                 MEM_freeN(vmap);
1224         }
1225 }
1226