Quite a large one this time... but now we have:
[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 #ifdef WIN32
42 #include "BLI_winstuff.h"
43 #endif
44
45 #include <stdlib.h>
46 #include <string.h>
47 #include <stdio.h>
48 #include <math.h>
49
50 #include "MEM_guardedalloc.h"
51
52 #include "DNA_ID.h"
53 #include "DNA_curve_types.h"
54 #include "DNA_material_types.h"
55 #include "DNA_object_types.h"
56 #include "DNA_image_types.h"
57 #include "DNA_key_types.h"
58 #include "DNA_mesh_types.h"
59 #include "DNA_meshdata_types.h"
60
61 #include "BKE_main.h"
62 #include "BKE_global.h"
63 #include "BKE_mesh.h"
64 #include "BKE_subsurf.h"
65 #include "BKE_displist.h"
66 #include "BKE_library.h"
67 #include "BKE_material.h"
68 #include "BKE_key.h"
69 /* these 2 are only used by conversion functions */
70 #include "BKE_curve.h"
71 /* -- */
72 #include "BKE_object.h"
73 #include "BKE_utildefines.h"
74 #include "BKE_bad_level_calls.h"
75
76 #include "BLI_blenlib.h"
77 #include "BLI_editVert.h"
78 #include "BLI_arithb.h"
79
80
81
82 int update_realtime_texture(TFace *tface, double time)
83 {
84         Image *ima;
85         int     inc = 0;
86         float   diff;
87         int     newframe;
88
89         ima = tface->tpage;
90
91         if (!ima)
92                 return 0;
93
94         if (ima->lastupdate<0)
95                 ima->lastupdate = 0;
96
97         if (ima->lastupdate>time)
98                 ima->lastupdate=(float)time;
99
100         if(ima->tpageflag & IMA_TWINANIM) {
101                 if(ima->twend >= ima->xrep*ima->yrep) ima->twend= ima->xrep*ima->yrep-1;
102                 
103                 /* check: is the bindcode not in the array? Then free. (still to do) */
104                 
105                 diff = (float)(time-ima->lastupdate);
106
107                 inc = (int)(diff*(float)ima->animspeed);
108
109                 ima->lastupdate+=((float)inc/(float)ima->animspeed);
110
111                 newframe = ima->lastframe+inc;
112
113                 if (newframe > (int)ima->twend)
114                         newframe = (int)ima->twsta-1 + (newframe-ima->twend)%(ima->twend-ima->twsta);
115
116                 ima->lastframe = newframe;
117         }
118         return inc;
119 }
120
121 float get_mvert_weight (Object *ob, int vert, int defgroup)
122 {
123         int     i;
124         Mesh *me;
125         float   result;
126
127         me=ob->data;
128
129         if (!me->dvert)
130                 return 0.0F;
131
132         result=0.0F;
133
134         for (i=0; i<me->dvert[vert].totweight; i++){
135                 if (me->dvert[vert].dw[i].def_nr==defgroup)
136                         result+=me->dvert[vert].dw[i].weight;           
137         }
138
139         return result;
140 }
141
142 void unlink_mesh(Mesh *me)
143 {
144         int a;
145         
146         if(me==0) return;
147         
148         for(a=0; a<me->totcol; a++) {
149                 if(me->mat[a]) me->mat[a]->id.us--;
150                 me->mat[a]= 0;
151         }
152         if(me->key) me->key->id.us--;
153         me->key= 0;
154         
155         if(me->texcomesh) me->texcomesh= 0;
156 }
157
158
159 /* do not free mesh itself */
160 void free_mesh(Mesh *me)
161 {
162
163         unlink_mesh(me);
164
165         if(me->mvert) MEM_freeN(me->mvert);
166         if(me->medge) MEM_freeN(me->medge);
167         if(me->mface) MEM_freeN(me->mface);
168         
169         if(me->tface) MEM_freeN(me->tface);
170         if(me->dvert) free_dverts(me->dvert, me->totvert);
171         if(me->mcol) MEM_freeN(me->mcol);
172         if(me->msticky) MEM_freeN(me->msticky);
173
174         if(me->mat) MEM_freeN(me->mat);
175         if(me->orco) MEM_freeN(me->orco);
176
177         if(me->bb) MEM_freeN(me->bb);
178         if(me->disp.first) freedisplist(&me->disp);
179 }
180
181 void copy_dverts(MDeformVert *dst, MDeformVert *src, int copycount)
182 {
183         /* Assumes dst is already set up */
184         int i;
185
186         if (!src || !dst)
187                 return;
188
189         memcpy (dst, src, copycount * sizeof(MDeformVert));
190         
191         for (i=0; i<copycount; i++){
192                 if (src[i].dw){
193                         dst[i].dw = MEM_callocN (sizeof(MDeformWeight)*src[i].totweight, "copy_deformWeight");
194                         memcpy (dst[i].dw, src[i].dw, sizeof (MDeformWeight)*src[i].totweight);
195                 }
196         }
197
198 }
199 void free_dverts(MDeformVert *dvert, int totvert)
200 {
201         /* Instead of freeing the verts directly,
202         call this function to delete any special
203         vert data */
204         int     i;
205
206         if (!dvert)
207                 return;
208
209         /* Free any special data from the verts */
210         for (i=0; i<totvert; i++){
211                 if (dvert[i].dw) MEM_freeN (dvert[i].dw);
212         }
213         MEM_freeN (dvert);
214 }
215
216 Mesh *add_mesh()
217 {
218         Mesh *me;
219         
220         me= alloc_libblock(&G.main->mesh, ID_ME, "Mesh");
221         
222         me->size[0]= me->size[1]= me->size[2]= 1.0;
223         me->smoothresh= 30;
224         me->texflag= AUTOSPACE;
225         me->flag= ME_TWOSIDED;
226         me->subdiv= 1;
227         me->subdivr = 1;
228         me->bb= unit_boundbox();
229         
230         return me;
231 }
232
233 Mesh *copy_mesh(Mesh *me)
234 {
235         Mesh *men;
236         int a;
237         
238         men= copy_libblock(me);
239         
240         men->mat= MEM_dupallocN(me->mat);
241         for(a=0; a<men->totcol; a++) {
242                 id_us_plus((ID *)men->mat[a]);
243         }
244         id_us_plus((ID *)men->texcomesh);
245
246         men->mvert= MEM_dupallocN(me->mvert);
247         men->medge= MEM_dupallocN(me->medge);
248         men->mface= MEM_dupallocN(me->mface);
249         men->tface= MEM_dupallocN(me->tface);
250         men->dface= NULL;
251
252         if (me->dvert){
253                 men->dvert = MEM_mallocN (sizeof (MDeformVert)*me->totvert, "MDeformVert");
254                 copy_dverts(men->dvert, me->dvert, me->totvert);
255         }
256
257         men->mcol= MEM_dupallocN(me->mcol);
258         men->msticky= MEM_dupallocN(me->msticky);
259         men->texcomesh= NULL;
260         men->orco= NULL;
261         men->bb= MEM_dupallocN(men->bb);
262         
263         copy_displist(&men->disp, &me->disp);
264         
265         men->key= copy_key(me->key);
266         if(men->key) men->key->from= (ID *)men;
267         
268         return men;
269 }
270
271 void make_local_tface(Mesh *me)
272 {
273         TFace *tface;
274         Image *ima;
275         int a;
276         
277         if(me->tface==0) return;
278         
279         a= me->totface;
280         tface= me->tface;
281         while(a--) {
282                 
283                 /* special case: ima always local immediately */
284                 if(tface->tpage) {
285                         ima= tface->tpage;
286                         if(ima->id.lib) {
287                                 ima->id.lib= 0;
288                                 ima->id.flag= LIB_LOCAL;
289                                 new_id(0, (ID *)ima, 0);
290                         }
291                 }
292                 tface++;
293         }
294         
295 }
296
297 void make_local_mesh(Mesh *me)
298 {
299         Object *ob;
300         Mesh *men;
301         int local=0, lib=0;
302
303         /* - only lib users: do nothing
304             * - only local users: set flag
305             * - mixed: make copy
306             */
307         
308         if(me->id.lib==0) return;
309         if(me->id.us==1) {
310                 me->id.lib= 0;
311                 me->id.flag= LIB_LOCAL;
312                 new_id(0, (ID *)me, 0);
313                 
314                 if(me->tface) make_local_tface(me);
315                 
316                 return;
317         }
318         
319         ob= G.main->object.first;
320         while(ob) {
321                 if( me==get_mesh(ob) ) {
322                         if(ob->id.lib) lib= 1;
323                         else local= 1;
324                 }
325                 ob= ob->id.next;
326         }
327         
328         if(local && lib==0) {
329                 me->id.lib= 0;
330                 me->id.flag= LIB_LOCAL;
331                 new_id(0, (ID *)me, 0);
332                 
333                 if(me->tface) make_local_tface(me);
334                 
335         }
336         else if(local && lib) {
337                 men= copy_mesh(me);
338                 men->id.us= 0;
339                 
340                 ob= G.main->object.first;
341                 while(ob) {
342                         if( me==get_mesh(ob) ) {                                
343                                 if(ob->id.lib==0) {
344                                         set_mesh(ob, men);
345                                 }
346                         }
347                         ob= ob->id.next;
348                 }
349         }
350 }
351
352 void boundbox_mesh(Mesh *me, float *loc, float *size)
353 {
354         MVert *mvert;
355         BoundBox *bb;
356         float min[3], max[3];
357         float mloc[3], msize[3];
358         int a;
359         
360         if(me->bb==0) me->bb= MEM_callocN(sizeof(BoundBox), "boundbox");
361         bb= me->bb;
362         
363         INIT_MINMAX(min, max);
364
365         if (!loc) loc= mloc;
366         if (!size) size= msize;
367         
368         mvert= me->mvert;
369         for(a=0; a<me->totvert; a++, mvert++) {
370                 DO_MINMAX(mvert->co, min, max);
371         }
372
373         if(me->totvert) {
374                 loc[0]= (min[0]+max[0])/2.0f;
375                 loc[1]= (min[1]+max[1])/2.0f;
376                 loc[2]= (min[2]+max[2])/2.0f;
377                 
378                 size[0]= (max[0]-min[0])/2.0f;
379                 size[1]= (max[1]-min[1])/2.0f;
380                 size[2]= (max[2]-min[2])/2.0f;
381         }
382         else {
383                 loc[0]= loc[1]= loc[2]= 0.0;
384                 size[0]= size[1]= size[2]= 0.0;
385         }
386         
387         bb->vec[0][0]=bb->vec[1][0]=bb->vec[2][0]=bb->vec[3][0]= loc[0]-size[0];
388         bb->vec[4][0]=bb->vec[5][0]=bb->vec[6][0]=bb->vec[7][0]= loc[0]+size[0];
389         
390         bb->vec[0][1]=bb->vec[1][1]=bb->vec[4][1]=bb->vec[5][1]= loc[1]-size[1];
391         bb->vec[2][1]=bb->vec[3][1]=bb->vec[6][1]=bb->vec[7][1]= loc[1]+size[1];
392
393         bb->vec[0][2]=bb->vec[3][2]=bb->vec[4][2]=bb->vec[7][2]= loc[2]-size[2];
394         bb->vec[1][2]=bb->vec[2][2]=bb->vec[5][2]=bb->vec[6][2]= loc[2]+size[2];
395 }
396
397 void tex_space_mesh(Mesh *me)
398 {
399         KeyBlock *kb;
400         float *fp, loc[3], size[3], min[3], max[3];
401         int a;
402
403         boundbox_mesh(me, loc, size);
404
405         if(me->texflag & AUTOSPACE) {
406                 if(me->key) {
407                         kb= me->key->refkey;
408                         if (kb) {
409                                 
410                                 INIT_MINMAX(min, max);
411                                 
412                                 fp= kb->data;
413                                 for(a=0; a<kb->totelem; a++, fp+=3) {   
414                                         DO_MINMAX(fp, min, max);
415                                 }
416                                 if(kb->totelem) {
417                                         loc[0]= (min[0]+max[0])/2.0f; loc[1]= (min[1]+max[1])/2.0f; loc[2]= (min[2]+max[2])/2.0f;
418                                         size[0]= (max[0]-min[0])/2.0f; size[1]= (max[1]-min[1])/2.0f; size[2]= (max[2]-min[2])/2.0f;
419                                 }
420                                 else {
421                                         loc[0]= loc[1]= loc[2]= 0.0;
422                                         size[0]= size[1]= size[2]= 0.0;
423                                 }
424                                 
425                         }
426                 }
427
428                 VECCOPY(me->loc, loc);
429                 VECCOPY(me->size, size);
430                 me->rot[0]= me->rot[1]= me->rot[2]= 0.0;
431
432                 if(me->size[0]==0.0) me->size[0]= 1.0;
433                 else if(me->size[0]>0.0 && me->size[0]<0.00001) me->size[0]= 0.00001;
434                 else if(me->size[0]<0.0 && me->size[0]> -0.00001) me->size[0]= -0.00001;
435         
436                 if(me->size[1]==0.0) me->size[1]= 1.0;
437                 else if(me->size[1]>0.0 && me->size[1]<0.00001) me->size[1]= 0.00001;
438                 else if(me->size[1]<0.0 && me->size[1]> -0.00001) me->size[1]= -0.00001;
439         
440                 if(me->size[2]==0.0) me->size[2]= 1.0;
441                 else if(me->size[2]>0.0 && me->size[2]<0.00001) me->size[2]= 0.00001;
442                 else if(me->size[2]<0.0 && me->size[2]> -0.00001) me->size[2]= -0.00001;
443         }
444         
445 }
446
447 void make_orco_displist_mesh(Object *ob, int subdivlvl)
448 {
449         Mesh *me;
450         DispListMesh *dlm;
451         int i;
452         
453         me= ob->data;
454
455                 /* if there's a key, set the first one */
456         if(me->key && me->texcomesh==0) {
457                 cp_key(0, me->totvert, me->totvert, (char*) me->mvert->co, me->key, me->key->refkey, 0);
458         }
459
460         dlm= subsurf_make_dispListMesh_from_mesh(me, NULL, subdivlvl, me->flag);
461         
462                 /* Restore correct key */
463         do_ob_key(ob);
464
465         if (me->orco) MEM_freeN(me->orco);
466         me->orco= MEM_mallocN(dlm->totvert*3*sizeof(float), "mesh displist orco");
467         
468         for(i=0; i<dlm->totvert; i++) {
469                 float *fp= &me->orco[i*3];
470
471                 VECCOPY(fp, dlm->mvert[i].co);
472
473                 fp[0]= (fp[0]-me->loc[0])/me->size[0];
474                 fp[1]= (fp[1]-me->loc[1])/me->size[1];
475                 fp[2]= (fp[2]-me->loc[2])/me->size[2];
476         }
477         
478         displistmesh_free(dlm);
479 }
480
481 void make_orco_mesh(Mesh *me)
482 {
483         MVert *mvert;
484         KeyBlock *kb;
485         float *orco, *fp;
486         int a, totvert;
487         
488         totvert= me->totvert;
489         if(totvert==0) return;
490         orco= me->orco= MEM_mallocN(sizeof(float)*3*totvert, "orco mesh");
491
492         if(me->key && me->texcomesh==0) {
493                 kb= me->key->refkey;
494                 if (kb) {               /***** BUG *****/
495                         fp= kb->data;
496                         
497                         for(a=0; a<totvert; a++, orco+=3) {
498                                 orco[0]= (fp[0]-me->loc[0])/me->size[0];
499                                 orco[1]= (fp[1]-me->loc[1])/me->size[1];
500                                 orco[2]= (fp[2]-me->loc[2])/me->size[2];
501                                 
502                                 /* only increase mvert when totvert <= kb->totelem */
503                                 if(a<kb->totelem) fp+=3;
504                         }
505                 }
506         }
507         else {
508                 if(me->texcomesh) {
509                         me= me->texcomesh;
510                 }       
511         
512                 mvert= me->mvert;
513                 for(a=0; a<totvert; a++, orco+=3) {
514                         orco[0]= (mvert->co[0]-me->loc[0])/me->size[0];
515                         orco[1]= (mvert->co[1]-me->loc[1])/me->size[1];
516                         orco[2]= (mvert->co[2]-me->loc[2])/me->size[2];
517                         
518                         /* only increase mvert when totvert <= me->totvert */
519                         if(a<me->totvert) mvert++;
520                 }
521         }
522 }
523
524 /** rotates the vertices of a face in case v[2] or v[3] (vertex index)
525   * is = 0.
526   * Helaas, the MFace structure has no pointer to its
527   * texture face, therefore, texture can not be fixed inside
528   * this function. 
529   * 
530   * see also blender/src/editmesh.c, fix_faceindices()
531
532   * THIS FUNCTION WILL BE DINOSOURCE. For the moment, another hack
533         is added to fix texture coordinates / vertex colors:
534
535         void test_index_face(MFace *mface, TFace *tface, int nr)
536   */
537
538 void test_index_mface(MFace *mface, int nr)
539 {
540         int a;
541
542         
543         /* first test if the face is legal */
544
545         if(mface->v3 && mface->v3==mface->v4) {
546                 mface->v4= 0;
547                 nr--;
548         }
549         if(mface->v2 && mface->v2==mface->v3) {
550                 mface->v3= mface->v4;
551                 mface->v4= 0;
552                 nr--;
553         }
554         if(mface->v1==mface->v2) {
555                 mface->v2= mface->v3;
556                 mface->v3= mface->v4;
557                 mface->v4= 0;
558                 nr--;
559         }
560
561         /* prevent a zero at wrong index location */
562         if(nr==2) {
563                 if(mface->v2==0) SWAP(int, mface->v1, mface->v2);
564         }
565         else if(nr==3) {
566                 if(mface->v3==0) {
567                         SWAP(int, mface->v1, mface->v2);
568                         SWAP(int, mface->v2, mface->v3);
569                         
570                         a= mface->edcode;
571                         mface->edcode= 0;
572                         if(a & ME_V1V2) mface->edcode |= ME_V3V1;
573                         if(a & ME_V2V3) mface->edcode |= ME_V1V2;
574                         if(a & ME_V3V1) mface->edcode |= ME_V2V3;
575                         
576                         a= mface->puno;
577                         mface->puno &= ~15;
578                         if(a & ME_FLIPV1) mface->puno |= ME_FLIPV2;
579                         if(a & ME_FLIPV2) mface->puno |= ME_FLIPV3;
580                         if(a & ME_FLIPV3) mface->puno |= ME_FLIPV1;
581                 }
582         }
583         else if(nr==4) {
584                 if(mface->v3==0 || mface->v4==0) {
585                         SWAP(int, mface->v1, mface->v3);
586                         SWAP(int, mface->v2, mface->v4);
587                         a= mface->edcode;
588                         mface->edcode= 0;
589                         if(a & ME_V1V2) mface->edcode |= ME_V3V4;
590                         if(a & ME_V2V3) mface->edcode |= ME_V2V3;
591                         if(a & ME_V3V4) mface->edcode |= ME_V1V2;
592                         if(a & ME_V4V1) mface->edcode |= ME_V4V1;
593
594                         a= mface->puno;
595                         mface->puno &= ~15;
596                         if(a & ME_FLIPV1) mface->puno |= ME_FLIPV3;
597                         if(a & ME_FLIPV2) mface->puno |= ME_FLIPV4;
598                         if(a & ME_FLIPV3) mface->puno |= ME_FLIPV1;
599                         if(a & ME_FLIPV4) mface->puno |= ME_FLIPV2;
600                 }
601         }
602 }
603
604 /**     This function should die as soon as there is another mesh
605         structure. Functionality is the same as
606
607                 void test_index_mface()
608
609         but it fixes texture coordinates as well. 
610 */
611
612 #define UVCOPY(t, s) memcpy(t, s, 2 * sizeof(float));
613 void test_index_face(MFace *mface, TFace *tface, int nr)
614 {
615         int a;
616         float tmpuv[2];
617         unsigned int tmpcol;
618
619
620         /* first test if the face is legal */
621
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==2) {
640                 if(mface->v2==0) SWAP(int, mface->v1, mface->v2);
641         }
642         else if(nr==3) {
643                 if(mface->v3==0) {
644                         SWAP(int, mface->v1, mface->v2);
645                         SWAP(int, mface->v2, mface->v3);
646                         /* rotate face UV coordinates, too */
647                         UVCOPY(tmpuv, tface->uv[0]);
648                         UVCOPY(tface->uv[0], tface->uv[1]);
649                         UVCOPY(tface->uv[1], tface->uv[2]);
650                         UVCOPY(tface->uv[2], tmpuv);
651                         /* same with vertex colours */
652                         tmpcol = tface->col[0];
653                         tface->col[0] = tface->col[1];
654                         tface->col[1] = tface->col[2];
655                         tface->col[2] = tmpcol;
656
657                         
658                         a= mface->edcode;
659                         mface->edcode= 0;
660                         if(a & ME_V1V2) mface->edcode |= ME_V3V1;
661                         if(a & ME_V2V3) mface->edcode |= ME_V1V2;
662                         if(a & ME_V3V1) mface->edcode |= ME_V2V3;
663                         
664                         a= mface->puno;
665                         mface->puno &= ~15;
666                         if(a & ME_FLIPV1) mface->puno |= ME_FLIPV2;
667                         if(a & ME_FLIPV2) mface->puno |= ME_FLIPV3;
668                         if(a & ME_FLIPV3) mface->puno |= ME_FLIPV1;
669                 }
670         }
671         else if(nr==4) {
672                 if(mface->v3==0 || mface->v4==0) {
673                         SWAP(int, mface->v1, mface->v3);
674                         SWAP(int, mface->v2, mface->v4);
675                         /* swap UV coordinates */
676                         UVCOPY(tmpuv, tface->uv[0]);
677                         UVCOPY(tface->uv[0], tface->uv[2]);
678                         UVCOPY(tface->uv[2], tmpuv);
679                         UVCOPY(tmpuv, tface->uv[1]);
680                         UVCOPY(tface->uv[1], tface->uv[3]);
681                         UVCOPY(tface->uv[3], tmpuv);
682                         /* swap vertex colours */
683                         tmpcol = tface->col[0];
684                         tface->col[0] = tface->col[2];
685                         tface->col[2] = tmpcol;
686                         tmpcol = tface->col[1];
687                         tface->col[1] = tface->col[3];
688                         tface->col[3] = tmpcol;
689
690                         a= mface->edcode;
691                         mface->edcode= 0;
692                         if(a & ME_V1V2) mface->edcode |= ME_V3V4;
693                         if(a & ME_V2V3) mface->edcode |= ME_V2V3;
694                         if(a & ME_V3V4) mface->edcode |= ME_V1V2;
695                         if(a & ME_V4V1) mface->edcode |= ME_V4V1;
696
697                         a= mface->puno;
698                         mface->puno &= ~15;
699                         if(a & ME_FLIPV1) mface->puno |= ME_FLIPV3;
700                         if(a & ME_FLIPV2) mface->puno |= ME_FLIPV4;
701                         if(a & ME_FLIPV3) mface->puno |= ME_FLIPV1;
702                         if(a & ME_FLIPV4) mface->puno |= ME_FLIPV2;
703                 }
704         }
705 }
706
707 void flipnorm_mesh(Mesh *me)
708 {
709         MFace *mface;
710         MVert *mvert;
711         DispList *dl;
712         float *fp;
713         int a, temp;
714         
715         mvert= me->mvert;
716         a= me->totvert;
717         while(a--) {
718                 mvert->no[0]= -mvert->no[0];
719                 mvert->no[1]= -mvert->no[1];
720                 mvert->no[2]= -mvert->no[2];
721                 mvert++;
722         }
723         
724         mface= me->mface;
725         a= me->totface;
726         while(a--) {
727                 if(mface->v3) {
728                         if(mface->v4) {
729                                 SWAP(int, mface->v4, mface->v1);
730                                 SWAP(int, mface->v3, mface->v2);
731                                 test_index_mface(mface, 4);
732                                 temp= mface->puno;
733                                 mface->puno &= ~15;
734                                 if(temp & ME_FLIPV1) mface->puno |= ME_FLIPV4;
735                                 if(temp & ME_FLIPV2) mface->puno |= ME_FLIPV3;
736                                 if(temp & ME_FLIPV3) mface->puno |= ME_FLIPV2;
737                                 if(temp & ME_FLIPV4) mface->puno |= ME_FLIPV1;
738                         }
739                         else {
740                                 SWAP(int, mface->v3, mface->v1);
741                                 test_index_mface(mface, 3);
742                                 temp= mface->puno;
743                                 mface->puno &= ~15;
744                                 if(temp & ME_FLIPV1) mface->puno |= ME_FLIPV3;
745                                 if(temp & ME_FLIPV2) mface->puno |= ME_FLIPV2;
746                                 if(temp & ME_FLIPV3) mface->puno |= ME_FLIPV1;
747                         }
748                 }
749                 mface++;
750         }
751
752         if(me->disp.first) {
753                 dl= me->disp.first;
754                 fp= dl->nors;
755                 if(fp) {
756                         a= dl->nr;
757                         while(a--) {
758                                 fp[0]= -fp[0];
759                                 fp[1]= -fp[1];
760                                 fp[2]= -fp[2];
761                                 fp+= 3;
762                         }
763                 }
764         }
765 }
766
767 Mesh *get_mesh(Object *ob)
768 {
769         
770         if(ob==0) return 0;
771         if(ob->type==OB_MESH) return ob->data;
772         else return 0;
773 }
774
775 void set_mesh(Object *ob, Mesh *me)
776 {
777         Mesh *old=0;
778         
779         if(ob==0) return;
780         
781         if(ob->type==OB_MESH) {
782                 old= ob->data;
783                 old->id.us--;
784                 ob->data= me;
785                 id_us_plus((ID *)me);
786         }
787         
788         test_object_materials((ID *)me);
789 }
790
791 /* ************** make edges in a Mesh, for outside of editmode */
792
793 struct edgesort {
794         int v1, v2;
795         int flag;
796 };
797
798 /* edges have to be added with lowest index first for sorting */
799 static void to_edgesort(struct edgesort *ed, int v1, int v2, int flag)
800 {
801         if(v1<v2) {
802                 ed->v1= v1; ed->v2= v2;
803         }
804         else {
805                 ed->v1= v2; ed->v2= v1;
806         }
807         ed->flag= flag;
808 }
809
810 static int vergedgesort(const void *v1, const void *v2)
811 {
812         const struct edgesort *x1=v1, *x2=v2;
813
814         if( x1->v1 > x2->v1) return 1;
815         else if( x1->v1 < x2->v1) return -1;
816         else if( x1->v2 > x2->v2) return 1;
817         else if( x1->v2 < x2->v2) return -1;
818         
819         return 0;
820 }
821
822
823 void make_edges(Mesh *me)
824 {
825         MFace *mface;
826         MEdge *medge;
827         struct edgesort *edsort, *ed;
828         int a, totedge=0, final=0;
829         
830         /* we put all edges in array, sort them, and detect doubles that way */
831         
832         for(a= me->totface, mface= me->mface; a>0; a--, mface++) {
833                 if(mface->v4) totedge+=4;
834                 else if(mface->v3) totedge+=3;
835                 else totedge+=1;
836         }
837         
838         if(totedge==0) return;
839         
840         ed= edsort= MEM_mallocN(totedge*sizeof(struct edgesort), "edgesort");
841         
842         for(a= me->totface, mface= me->mface; a>0; a--, mface++) {
843                 
844                 to_edgesort(ed, mface->v1, mface->v2, mface->edcode & ME_V1V2);
845                 ed++;
846                 if(mface->v4) {
847                         to_edgesort(ed, mface->v2, mface->v3, mface->edcode & ME_V2V3);
848                         ed++;
849                         to_edgesort(ed, mface->v3, mface->v4, mface->edcode & ME_V3V4);
850                         ed++;
851                         to_edgesort(ed, mface->v4, mface->v1, mface->edcode & ME_V4V1);
852                         ed++;
853                 }
854                 else if(mface->v3) {
855                         to_edgesort(ed, mface->v2, mface->v3, mface->edcode & ME_V2V3);
856                         ed++;
857                         to_edgesort(ed, mface->v3, mface->v1, mface->edcode & ME_V3V1);
858                         ed++;
859                 }
860         }
861         
862         qsort(edsort, totedge, sizeof(struct edgesort), vergedgesort);
863         
864         /* count final amount */
865         for(a=totedge, ed=edsort; a>1; a--, ed++) {
866                 /* edge is unique when it differs from next edge, or is last */
867                 if(ed->v1 != (ed+1)->v1 || ed->v2 != (ed+1)->v2) final++;
868                 else {
869                         /* this makes sure identical edges both get draw flag */
870                         if(ed->flag) (ed+1)->flag= 1;
871                         else if((ed+1)->flag) ed->flag= 1;
872                 }
873         }
874         final++;
875         
876         medge= me->medge= MEM_callocN(final*sizeof(MEdge), "make mesh edges");
877         me->totedge= final;
878         
879         for(a=totedge, ed=edsort; a>1; a--, ed++) {
880                 /* edge is unique when it differs from next edge, or is last */
881                 if(ed->v1 != (ed+1)->v1 || ed->v2 != (ed+1)->v2) {
882                         medge->v1= ed->v1;
883                         medge->v2= ed->v2;
884                         if(ed->flag) medge->flag= ME_EDGEDRAW;
885                         medge++;
886                 }
887         }
888         /* last edge */
889         medge->v1= ed->v1;
890         medge->v2= ed->v2;
891         if(ed->flag) medge->flag= ME_EDGEDRAW;
892
893         MEM_freeN(edsort);
894 }
895
896
897
898 void mball_to_mesh(ListBase *lb, Mesh *me)
899 {
900         DispList *dl;
901         MVert *mvert;
902         MFace *mface;
903         float *nors, *verts;
904         int a, *index;
905         
906         dl= lb->first;
907         if(dl==0) return;
908
909         if(dl->type==DL_INDEX4) {
910                 me->flag= ME_NOPUNOFLIP;
911                 me->totvert= dl->nr;
912                 me->totface= dl->parts;
913                 
914                 me->mvert=mvert= MEM_callocN(dl->nr*sizeof(MVert), "mverts");
915                 a= dl->nr;
916                 nors= dl->nors;
917                 verts= dl->verts;
918                 while(a--) {
919                         VECCOPY(mvert->co, verts);
920                         mvert->no[0]= (short int)(nors[0]*32767.0);
921                         mvert->no[1]= (short int)(nors[1]*32767.0);
922                         mvert->no[2]= (short int)(nors[2]*32767.0);
923                         mvert++;
924                         nors+= 3;
925                         verts+= 3;
926                 }
927                 
928                 me->mface=mface= MEM_callocN(dl->parts*sizeof(MFace), "mface");
929                 a= dl->parts;
930                 index= dl->index;
931                 while(a--) {
932                         mface->v1= index[0];
933                         mface->v2= index[1];
934                         mface->v3= index[2];
935                         mface->v4= index[3];
936
937                         mface->puno= 0;
938                         mface->edcode= ME_V1V2+ME_V2V3;
939                         mface->flag = ME_SMOOTH;
940                         
941                         mface++;
942                         index+= 4;
943                 }
944         }       
945 }
946
947 void nurbs_to_mesh(Object *ob)
948 {
949         Object *ob1;
950         DispList *dl;
951         Mesh *me;
952         Curve *cu;
953         MVert *mvert;
954         MFace *mface;
955         float *data;
956         int a, b, ofs, vertcount, startvert, totvert=0, totvlak=0;
957         int p1, p2, p3, p4, *index;
958
959         cu= ob->data;
960
961         if(ob->type==OB_CURVE) {
962                 /* rule: dl->type INDEX3 always as first in list */
963                 dl= cu->disp.first;
964                 if(dl->type!=DL_INDEX3) {
965                         curve_to_filledpoly(ob->data, &cu->disp);
966                 }
967         }
968
969         /* count */
970         dl= cu->disp.first;
971         while(dl) {
972                 if(dl->type==DL_SEGM) {
973                         totvert+= dl->parts*dl->nr;
974                         totvlak+= dl->parts*(dl->nr-1);
975                 }
976                 else if(dl->type==DL_POLY) {
977                         /* cyclic polys are filled. except when 3D */
978                         if(cu->flag & CU_3D) {
979                                 totvert+= dl->parts*dl->nr;
980                                 totvlak+= dl->parts*dl->nr;
981                         }
982                 }
983                 else if(dl->type==DL_SURF) {
984                         totvert+= dl->parts*dl->nr;
985                         totvlak+= (dl->parts-1+((dl->flag & 2)==2))*(dl->nr-1+(dl->flag & 1));
986                 }
987                 else if(dl->type==DL_INDEX3) {
988                         totvert+= dl->nr;
989                         totvlak+= dl->parts;
990                 }
991                 dl= dl->next;
992         }
993         if(totvert==0) {
994                 error("can't convert");
995                 return;
996         }
997
998         /* make mesh */
999         me= add_mesh();
1000         me->totvert= totvert;
1001         me->totface= totvlak;
1002
1003         me->totcol= cu->totcol;
1004         me->mat= cu->mat;
1005         cu->mat= 0;
1006         cu->totcol= 0;
1007
1008         mvert=me->mvert= MEM_callocN(me->totvert*sizeof(MVert), "cumesh1");
1009         mface=me->mface= MEM_callocN(me->totface*sizeof(MFace), "cumesh2");
1010
1011         /* verts and faces */
1012         vertcount= 0;
1013
1014         dl= cu->disp.first;
1015         while(dl) {
1016                 if(dl->type==DL_SEGM) {
1017                         startvert= vertcount;
1018                         a= dl->parts*dl->nr;
1019                         data= dl->verts;
1020                         while(a--) {
1021                                 VECCOPY(mvert->co, data);
1022                                 data+=3;
1023                                 vertcount++;
1024                                 mvert++;
1025                         }
1026
1027                         for(a=0; a<dl->parts; a++) {
1028                                 ofs= a*dl->nr;
1029                                 for(b=1; b<dl->nr; b++) {
1030                                         mface->v1= startvert+ofs+b-1;
1031                                         mface->v2= startvert+ofs+b;
1032                                         mface->edcode= ME_V1V2;
1033                                         test_index_mface(mface, 2);
1034                                         mface++;
1035                                 }
1036                         }
1037
1038                 }
1039                 else if(dl->type==DL_POLY) {
1040                         /* 3d polys are not filled */
1041                         if(cu->flag & CU_3D) {
1042                                 startvert= vertcount;
1043                                 a= dl->parts*dl->nr;
1044                                 data= dl->verts;
1045                                 while(a--) {
1046                                         VECCOPY(mvert->co, data);
1047                                         data+=3;
1048                                         vertcount++;
1049                                         mvert++;
1050                                 }
1051         
1052                                 for(a=0; a<dl->parts; a++) {
1053                                         ofs= a*dl->nr;
1054                                         for(b=0; b<dl->nr; b++) {
1055                                                 mface->v1= startvert+ofs+b;
1056                                                 if(b==dl->nr-1) mface->v2= startvert+ofs;
1057                                                 else mface->v2= startvert+ofs+b+1;
1058                                                 mface->edcode= ME_V1V2;
1059                                                 test_index_mface(mface, 2);
1060                                                 mface++;
1061                                         }
1062                                 }
1063                         }
1064                 }
1065                 else if(dl->type==DL_INDEX3) {
1066                         startvert= vertcount;
1067                         a= dl->nr;
1068                         data= dl->verts;
1069                         while(a--) {
1070                                 VECCOPY(mvert->co, data);
1071                                 data+=3;
1072                                 vertcount++;
1073                                 mvert++;
1074                         }
1075
1076                         a= dl->parts;
1077                         index= dl->index;
1078                         while(a--) {
1079                                 mface->v1= startvert+index[0];
1080                                 mface->v2= startvert+index[1];
1081                                 mface->v3= startvert+index[2];
1082                                 mface->v4= 0;
1083         
1084                                 mface->puno= 7;
1085                                 mface->edcode= ME_V1V2+ME_V2V3;
1086                                 test_index_mface(mface, 3);
1087                                 
1088                                 mface++;
1089                                 index+= 3;
1090                         }
1091         
1092         
1093                 }
1094                 else if(dl->type==DL_SURF) {
1095                         startvert= vertcount;
1096                         a= dl->parts*dl->nr;
1097                         data= dl->verts;
1098                         while(a--) {
1099                                 VECCOPY(mvert->co, data);
1100                                 data+=3;
1101                                 vertcount++;
1102                                 mvert++;
1103                         }
1104
1105                         for(a=0; a<dl->parts; a++) {
1106
1107                                 if( (dl->flag & 2)==0 && a==dl->parts-1) break;
1108
1109                                 if(dl->flag & 1) {                      /* p2 -> p1 -> */
1110                                         p1= startvert+ dl->nr*a;        /* p4 -> p3 -> */
1111                                         p2= p1+ dl->nr-1;               /* -----> next row */
1112                                         p3= p1+ dl->nr;
1113                                         p4= p2+ dl->nr;
1114                                         b= 0;
1115                                 }
1116                                 else {
1117                                         p2= startvert+ dl->nr*a;
1118                                         p1= p2+1;
1119                                         p4= p2+ dl->nr;
1120                                         p3= p1+ dl->nr;
1121                                         b= 1;
1122                                 }
1123                                 if( (dl->flag & 2) && a==dl->parts-1) {
1124                                         p3-= dl->parts*dl->nr;
1125                                         p4-= dl->parts*dl->nr;
1126                                 }
1127
1128                                 for(; b<dl->nr; b++) {
1129                                         mface->v1= p1;
1130                                         mface->v2= p3;
1131                                         mface->v3= p4;
1132                                         mface->v4= p2;
1133                                         mface->mat_nr= (unsigned char)dl->col;
1134                                         mface->edcode= ME_V1V2+ME_V2V3;
1135                                         test_index_mface(mface, 4);
1136                                         mface++;
1137
1138                                         p4= p3; 
1139                                         p3++;
1140                                         p2= p1; 
1141                                         p1++;
1142                                 }
1143                         }
1144
1145                 }
1146
1147                 dl= dl->next;
1148         }
1149
1150         if(ob->data) {
1151                 free_libblock(&G.main->curve, ob->data);
1152         }
1153         ob->data= me;
1154         ob->type= OB_MESH;
1155         
1156         tex_space_mesh(me);
1157         
1158         /* other users */
1159         ob1= G.main->object.first;
1160         while(ob1) {
1161                 if(ob1->data==cu) {
1162                         ob1->type= OB_MESH;
1163                 
1164                         ob1->data= ob->data;
1165                         id_us_plus((ID *)ob->data);
1166                 }
1167                 ob1= ob1->id.next;
1168         }
1169
1170 }
1171
1172 void edge_drawflags_mesh(Mesh *me)
1173 {
1174         MFace *mface;
1175         int a;
1176         
1177         mface= me->mface;
1178         for(a=0; a<me->totface; a++, mface++) {
1179                 mface->edcode= ME_V1V2|ME_V2V3|ME_V3V4|ME_V4V1;
1180         }
1181 }
1182
1183 void tface_to_mcol(Mesh *me)
1184 {
1185         TFace *tface;
1186         unsigned int *mcol;
1187         int a;
1188         
1189         me->mcol= MEM_mallocN(4*sizeof(int)*me->totface, "nepmcol");
1190         mcol= (unsigned int *)me->mcol;
1191         
1192         a= me->totface;
1193         tface= me->tface;
1194         while(a--) {
1195                 memcpy(mcol, tface->col, 16);
1196                 mcol+= 4;
1197                 tface++;
1198         }
1199 }
1200
1201 void mcol_to_tface(Mesh *me, int freedata)
1202 {
1203         TFace *tface;
1204         unsigned int *mcol;
1205         int a;
1206         
1207         a= me->totface;
1208         tface= me->tface;
1209         mcol= (unsigned int *)me->mcol;
1210         while(a--) {
1211                 memcpy(tface->col, mcol, 16);
1212                 mcol+= 4;
1213                 tface++;
1214         }
1215         
1216         if(freedata) {
1217                 MEM_freeN(me->mcol);
1218                 me->mcol= 0;
1219         }
1220 }
1221
1222 int mesh_uses_displist(Mesh *me) {
1223         return (me->flag&ME_SUBSURF);
1224 }
1225
1226 void mesh_calculate_vertex_normals(Mesh *me)
1227 {
1228         float (*tempNorms)[3]= MEM_callocN(me->totvert*sizeof(*tempNorms), "tempNorms");
1229         int i;
1230
1231         for (i=0; i<me->totface; i++) {
1232                 MFace *mf= &((MFace*) me->mface)[i];
1233                 float f_no[3];
1234
1235                 if (!mf->v3)
1236                         continue;
1237                         
1238                 if (mf->v4) {
1239                         CalcNormFloat4(me->mvert[mf->v1].co, me->mvert[mf->v2].co, me->mvert[mf->v3].co, me->mvert[mf->v4].co, f_no);
1240                 } else {
1241                         CalcNormFloat(me->mvert[mf->v1].co, me->mvert[mf->v2].co, me->mvert[mf->v3].co, f_no);
1242                 }
1243                 
1244                 VecAddf(tempNorms[mf->v1], tempNorms[mf->v1], f_no);
1245                 VecAddf(tempNorms[mf->v2], tempNorms[mf->v2], f_no);
1246                 VecAddf(tempNorms[mf->v3], tempNorms[mf->v3], f_no);
1247                 if (mf->v4)
1248                         VecAddf(tempNorms[mf->v4], tempNorms[mf->v4], f_no);
1249         }
1250         for (i=0; i<me->totvert; i++) {
1251                 MVert *mv= &me->mvert[i];
1252                 float *no= tempNorms[i];
1253                 
1254                 Normalise(no);
1255                 mv->no[0]= (short)(no[0]*32767.0);
1256                 mv->no[1]= (short)(no[1]*32767.0);
1257                 mv->no[2]= (short)(no[2]*32767.0);
1258         }
1259         
1260         MEM_freeN(tempNorms);
1261 }
1262
1263 void mesh_delete_material_index(Mesh *me, int index) {
1264         int i;
1265
1266         for (i=0; i<me->totface; i++) {
1267                 MFace *mf = &((MFace*) me->mface)[i];
1268                 if (mf->mat_nr && mf->mat_nr>=index) 
1269                         mf->mat_nr--;
1270         }
1271 }
1272
1273 void mesh_set_smooth_flag(Mesh *me, int enableSmooth) {
1274         int i;
1275
1276         for (i=0; i<me->totface; i++) {
1277                 MFace *mf = &((MFace*) me->mface)[i];
1278
1279                 if (enableSmooth) {
1280                         mf->flag |= ME_SMOOTH;
1281                 } else {
1282                         mf->flag &= ~ME_SMOOTH;
1283                 }
1284         }
1285 }