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