Initial revision
[blender.git] / source / blender / src / editmesh.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: all of this file.
27  *
28  * Contributor(s): none yet.
29  *
30  * ***** END GPL/BL DUAL LICENSE BLOCK *****
31  */
32
33 #include <stdlib.h>
34 #include <string.h>
35 #include <math.h>
36
37 #ifdef WIN32
38 #include "BLI_winstuff.h"
39 #endif
40 #include "MEM_guardedalloc.h"
41
42 #include "BLI_blenlib.h"
43 #include "BLI_arithb.h"
44 #include "BLI_editVert.h"
45 #include "BLI_rand.h"
46
47 #include "MTC_matrixops.h"
48
49 #include "DNA_mesh_types.h"
50 #include "DNA_object_types.h"
51 #include "DNA_screen_types.h"
52 #include "DNA_key_types.h"
53 #include "DNA_scene_types.h"
54 #include "DNA_view3d_types.h"
55 #include "DNA_material_types.h"
56 #include "DNA_texture_types.h"
57
58 #include "BKE_utildefines.h"
59 #include "BKE_key.h"
60 #include "BKE_object.h"
61 #include "BKE_texture.h"
62 #include "BKE_displist.h"
63 #include "BKE_global.h"
64 #include "BKE_library.h"
65 #include "BKE_main.h"
66 #include "BKE_material.h"
67 #include "BKE_mesh.h"
68
69 #include "BIF_gl.h"
70 #include "BIF_graphics.h"
71 #include "BIF_editkey.h"
72 #include "BIF_space.h"
73 #include "BIF_toolbox.h"
74 #include "BIF_screen.h"
75 #include "BIF_interface.h"
76 #include "BIF_editmesh.h"
77 #include "BIF_mywindow.h"
78
79 #include "BSE_view.h"
80 #include "BSE_edit.h"
81 #include "BSE_trans_types.h"
82
83 #include "BDR_drawobject.h"
84 #include "BDR_editobject.h"
85 #include "BDR_editface.h"
86 #include "BDR_vpaint.h"
87
88 #include "mydevice.h"
89 #include "blendef.h"
90 #include "interface.h" /* MAART: for NUM and FLO types */
91 #include "nla.h"                /* For __NLA : Important - Do not remove! */
92 #include "render.h"
93
94 /****/
95
96 static void free_editverts(ListBase *edve);
97 static float convex(float *v1, float *v2, float *v3, float *v4);
98
99 /****/
100
101
102 /* extern ListBase fillvertbase, filledgebase; */ /* scanfill.c, in
103     the lib... already in BLI_blenlib.h */
104
105 /*  voor debug:
106 #define free(a)                 freeN(a)
107 #define malloc(a)               mallocN(a, "malloc")
108 #define calloc(a, b)    callocN((a)*(b), "calloc")
109 #define freelist(a)             freelistN(a)
110 */
111
112 extern short editbutflag;
113
114 static float icovert[12][3] = {
115         {0,0,-200}, 
116         {144.72, -105.144,-89.443},
117         {-55.277, -170.128,-89.443}, 
118         {-178.885,0,-89.443},
119         {-55.277,170.128,-89.443}, 
120         {144.72,105.144,-89.443},
121         {55.277,-170.128,89.443},
122         {-144.72,-105.144,89.443},
123         {-144.72,105.144,89.443},
124         {55.277,170.128,89.443},
125         {178.885,0,89.443},
126         {0,0,200}
127 };
128 static short icovlak[20][3] = {
129         {1,0,2},
130         {1,0,5},
131         {2,0,3},
132         {3,0,4},
133         {4,0,5},
134         {1,5,10},
135         {2,1,6},
136         {3,2,7},
137         {4,3,8},
138         {5,4,9},
139         {10,1,6},
140         {6,2,7},
141         {7,3,8},
142         {8,4,9},
143         {9,5,10},
144         {6,10,11},
145         {7,6,11},
146         {8,7,11},
147         {9,8,11},
148         {10,9,11}
149 };
150
151 /* DEFINES */
152 #define UVCOPY(t, s) memcpy(t, s, 2 * sizeof(float));
153
154 #define TEST_EDITMESH   if(G.obedit==0) return; \
155                                                 if( (G.vd->lay & G.obedit->lay)==0 ) return;
156
157 #define FACE_MARKCLEAR(f) (f->f1 = 1)
158
159 /* ***************** HASH ********************* */
160
161 /* HASH struct voor snel opzoeken edges */
162 struct HashEdge {
163         struct EditEdge *eed;
164         struct HashEdge *next;
165 };
166
167 struct HashEdge *hashedgetab=0;
168
169 /********* qsort routines *********/
170
171
172 struct xvertsort {
173         float x;
174         EditVert *v1;
175 };
176
177 /* Functions */
178 static int vergxco(const void *v1, const void *v2)
179 {
180         const struct xvertsort *x1=v1, *x2=v2;
181
182         if( x1->x > x2->x ) return 1;
183         else if( x1->x < x2->x) return -1;
184         return 0;
185 }
186
187 struct vlaksort {
188         long x;
189         struct EditVlak *evl;
190 };
191
192
193 static int vergvlak(const void *v1, const void *v2)
194 {
195         const struct vlaksort *x1=v1, *x2=v2;
196         
197         if( x1->x > x2->x ) return 1;
198         else if( x1->x < x2->x) return -1;
199         return 0;
200 }
201
202
203 /* ************ ADD / REMOVE / FIND ****************** */
204
205 #define EDHASH(a, b)    ( (a)*256 + (b) )
206 #define EDHASHSIZE      65536
207
208 #if 0
209 static void check_hashedge(void)
210 {
211         int i, i2,  doubedge=0;
212         struct HashEdge *he,  *he2;
213         
214         for (i=0; i<64; i++) {
215                 he= hashedgetab+i;
216                 
217                 while (he && he->eed) {
218                         for (i2=i+1; i2<64; i2++) {
219                                 he2= hashedgetab+i2;
220                                 
221                                 while (he2) {
222                                         if (he->eed == he2->eed) doubedge++;
223                                                                         
224                                         he2= he2->next;
225                                 }       
226                         }
227                         
228                         he= he->next;
229                 }       
230         }
231         
232         if (doubedge) printf("%d double edges!\n", doubedge);
233 }
234 #endif
235
236 EditVert *addvertlist(float *vec)
237 {
238         EditVert *eve;
239         static unsigned char hashnr= 0;
240
241         eve= calloc(sizeof(EditVert),1);
242         BLI_addtail(&G.edve, eve);
243         
244         if(vec) VECCOPY(eve->co, vec);
245
246         eve->hash= hashnr++;
247
248         return eve;
249 }
250
251 EditEdge *findedgelist(EditVert *v1, EditVert *v2)
252 {
253         EditVert *v3;
254         struct HashEdge *he;
255
256         if(hashedgetab==0) {
257                 hashedgetab= MEM_callocN(EDHASHSIZE*sizeof(struct HashEdge), "hashedgetab");
258         }
259         
260         /* swap ? */
261         if( (long)v1 > (long)v2) {
262                 v3= v2; 
263                 v2= v1; 
264                 v1= v3;
265         }
266         
267         /* eerst even op de flip-plek kijken */
268         
269 /*      he= hashedgetab + EDHASH(v2->hash, v1->hash); */
270 /*      if(he->eed && he->eed->v1==v1 && he->eed->v2==v2) return he->eed; */
271         
272         
273         he= hashedgetab + EDHASH(v1->hash, v2->hash);
274         
275         while(he) {
276                 
277                 if(he->eed && he->eed->v1==v1 && he->eed->v2==v2) return he->eed;
278                 
279                 he= he->next;
280         }
281         return 0;
282 }
283
284 static void insert_hashedge(EditEdge *eed)
285 {
286         /* er van uitgaande dat eed nog niet in lijst zit, en eerst een find is gedaan */
287         
288         struct HashEdge *first, *he;
289
290         /* eerst even op de flip-plek kijken */
291 /*      he= hashedgetab + EDHASH(eed->v2->hash, eed->v1->hash); */
292
293 /*      if(he->eed==0) { */
294 /*              he->eed= eed; */
295 /*              return; */
296 /*      } */
297
298         first= hashedgetab + EDHASH(eed->v1->hash, eed->v2->hash);
299
300         if( first->eed==0 ) {
301                 first->eed= eed;
302         }
303         else {
304                 he= (struct HashEdge *)malloc(sizeof(struct HashEdge)); 
305                 he->eed= eed;
306                 he->next= first->next;
307                 first->next= he;
308         }
309 }
310
311 static void remove_hashedge(EditEdge *eed)
312 {
313         /* er van uitgaande dat eed in lijst zit */
314         
315         struct HashEdge *first, *he, *prev=NULL;
316
317
318         /* eerst even op de flip-plek kijken */
319 /*      first= hashedgetab + EDHASH(eed->v2->hash, eed->v1->hash); */
320
321 /*      if(first->eed==eed) { */
322                 /* uit lijst verwijderen */
323                 
324 /*              if(first->next) { */
325 /*                      he= first->next; */
326 /*                      first->eed= he->eed; */
327 /*                      first->next= he->next; */
328 /*                      free(he); */
329 /*              } */
330 /*              else first->eed= 0; */
331
332 /*              return; */
333 /*      } */
334
335
336         he=first= hashedgetab + EDHASH(eed->v1->hash, eed->v2->hash);
337
338         while(he) {
339                 if(he->eed == eed) {
340                         /* uit lijst verwijderen */
341                         if(he==first) {
342                                 if(first->next) {
343                                         he= first->next;
344                                         first->eed= he->eed;
345                                         first->next= he->next;
346                                         free(he);
347                                 }
348                                 else he->eed= 0;
349                         }
350                         else {
351                                 prev->next= he->next;
352                                 free(he);
353                         }
354                         return;
355                 }
356                 prev= he;
357                 he= he->next;
358         }
359 }
360
361 void free_hashedgetab(void)
362 {
363         struct HashEdge *he, *first, *hen;
364         int a;
365 /*      int test[30], nr, toted=0; */
366         
367         /* for(a=0; a<30; a++) test[a]=0; */
368         
369         if(hashedgetab) {
370         
371                 first= hashedgetab;
372                 for(a=0; a<EDHASHSIZE; a++, first++) {
373                         he= first->next;
374                         /* nr= 0; */
375                         /* if(first->eed) toted++; */
376                         /* if(first->eed) nr++; */
377                         while(he) {
378                                 hen= he->next;
379                                 free(he);
380                                 he= hen;
381                                 /* nr++; */
382                         }
383                         /* if(nr>29) nr= 29; */
384                         /* test[nr]++; */
385                 }
386                 MEM_freeN(hashedgetab);
387                 hashedgetab= 0;
388
389                 /* printf("toted %d\n", toted); */
390                 /* toted= 0; */
391                 /* for(a=0; a<30; a++) { */
392                 /*      printf("tab %d %d\n", a, test[a]); */
393                 /* } */
394         }
395 }
396
397 EditEdge *addedgelist(EditVert *v1, EditVert *v2)
398 {
399         EditVert *v3;
400         EditEdge *eed;
401         int swap= 0;
402         
403         /* swap ? */
404         if(v1>v2) {
405                 v3= v2; 
406                 v2= v1; 
407                 v1= v3;
408                 swap= 1;
409         }
410
411         if(v1==v2) return 0;
412         if(v1==0 || v2==0) return 0;
413         
414         /* opzoeken in hashlijst */
415         eed= findedgelist(v1, v2);
416         
417         if(eed==0) {
418
419                 eed= (EditEdge *)calloc(sizeof(EditEdge), 1);
420                 eed->v1= v1;
421                 eed->v2= v2;
422                 BLI_addtail(&G.eded, eed);
423                 eed->dir= swap;
424                 insert_hashedge(eed);
425         }
426         return eed;
427 }
428
429
430 void remedge(EditEdge *eed)
431 {
432
433         BLI_remlink(&G.eded, eed);
434
435         remove_hashedge(eed);
436 }
437
438 static void freevlak(EditVlak *evl)
439 {
440         free(evl);
441 }
442
443 static void freevlaklist(ListBase *lb)
444 {
445         EditVlak *evl, *next;
446         
447         evl= lb->first;
448         while(evl) {
449                 next= evl->next;
450                 freevlak(evl);
451                 evl= next;
452         }
453         lb->first= lb->last= 0;
454 }
455
456 EditVlak *addvlaklist(EditVert *v1, EditVert *v2, EditVert *v3, EditVert *v4, EditVlak *example)
457 {
458         EditVlak *evl;
459         EditEdge *e1, *e2=0, *e3=0, *e4=0;
460         
461
462         /* voeg vlak toe aan lijst en doe meteen de edges */
463         e1= addedgelist(v1, v2);
464         if(v3) e2= addedgelist(v2, v3);
465         if(v4) e3= addedgelist(v3, v4); else e3= addedgelist(v3, v1);
466         if(v4) e4= addedgelist(v4, v1);
467         
468         if(v1==v2 || v2==v3 || v1==v3) return 0;
469         if(e2==0) return 0;
470
471         evl= (EditVlak *)calloc(sizeof(EditVlak), 1);
472         evl->v1= v1;
473         evl->v2= v2;
474         evl->v3= v3;
475         evl->v4= v4;
476
477         evl->e1= e1;
478         evl->e2= e2;
479         evl->e3= e3;
480         evl->e4= e4;
481
482         if(example) {
483                 evl->mat_nr= example->mat_nr;
484                 evl->tface= example->tface;
485                 evl->flag= example->flag;
486                 memcpy(evl->col, example->col, sizeof(example->col));
487                 memcpy(evl->uv, example->uv, sizeof(example->uv));
488         }
489         else { 
490                 if (G.obedit && G.obedit->actcol)
491                         evl->mat_nr= G.obedit->actcol-1;
492                 default_uv(evl->uv, 1.0);
493
494                 /* Initialize colors */
495                 evl->col[0]= evl->col[1]= evl->col[2]= evl->col[3]= vpaint_get_current_col();
496         }
497         
498         BLI_addtail(&G.edvl, evl);
499
500         if(evl->v4) CalcNormFloat4(v1->co, v2->co, v3->co, v4->co, evl->n);
501         else CalcNormFloat(v1->co, v2->co, v3->co, evl->n);
502
503         return evl;
504 }
505
506 static int comparevlak(EditVlak *vl1, EditVlak *vl2)
507 {
508         EditVert *v1, *v2, *v3, *v4;
509         
510         if(vl1->v4 && vl2->v4) {
511                 v1= vl2->v1;
512                 v2= vl2->v2;
513                 v3= vl2->v3;
514                 v4= vl2->v4;
515                 
516                 if(vl1->v1==v1 || vl1->v2==v1 || vl1->v3==v1 || vl1->v4==v1) {
517                         if(vl1->v1==v2 || vl1->v2==v2 || vl1->v3==v2 || vl1->v4==v2) {
518                                 if(vl1->v1==v3 || vl1->v2==v3 || vl1->v3==v3 || vl1->v4==v3) {
519                                         if(vl1->v1==v4 || vl1->v2==v4 || vl1->v3==v4 || vl1->v4==v4) {
520                                                 return 1;
521                                         }
522                                 }
523                         }
524                 }
525         }
526         else if(vl1->v4==0 && vl2->v4==0) {
527                 v1= vl2->v1;
528                 v2= vl2->v2;
529                 v3= vl2->v3;
530
531                 if(vl1->v1==v1 || vl1->v2==v1 || vl1->v3==v1) {
532                         if(vl1->v1==v2 || vl1->v2==v2 || vl1->v3==v2) {
533                                 if(vl1->v1==v3 || vl1->v2==v3 || vl1->v3==v3) {
534                                         return 1;
535                                 }
536                         }
537                 }
538         }
539
540         return 0;
541 }
542
543
544 #if 0
545 static int dubbelvlak(EditVlak *evltest)
546 {
547         
548         EditVlak *evl;
549         
550         evl= G.edvl.first;
551         while(evl) {
552                 if(evl!=evltest) {
553                         if(comparevlak(evltest, evl)) return 1;
554                 }
555                 evl= evl->next;
556         }
557         return 0;
558 }
559 #endif
560
561 static int exist_vlak(EditVert *v1, EditVert *v2, EditVert *v3, EditVert *v4)
562 {
563         EditVlak *evl, evltest;
564         
565         evltest.v1= v1;
566         evltest.v2= v2;
567         evltest.v3= v3;
568         evltest.v4= v4;
569         
570         evl= G.edvl.first;
571         while(evl) {
572                 if(comparevlak(&evltest, evl)) return 1;
573                 evl= evl->next;
574         }
575         return 0;
576 }
577
578
579 static int vlakselectedOR(EditVlak *evl, int flag)
580 {
581         
582         if(evl->v1->f & flag) return 1;
583         if(evl->v2->f & flag) return 1;
584         if(evl->v3->f & flag) return 1;
585         if(evl->v4 && (evl->v4->f & 1)) return 1;
586         return 0;
587 }
588
589 int vlakselectedAND(EditVlak *evl, int flag)
590 {
591         if(evl->v1->f & flag) {
592                 if(evl->v2->f & flag) {
593                         if(evl->v3->f & flag) {
594                                 if(evl->v4) {
595                                         if(evl->v4->f & flag) return 1;
596                                 }
597                                 else return 1;
598                         }
599                 }
600         }
601         return 0;
602 }
603
604 void recalc_editnormals(void)
605 {
606         EditVlak *evl;
607
608         evl= G.edvl.first;
609         while(evl) {
610                 if(evl->v4) CalcNormFloat4(evl->v1->co, evl->v2->co, evl->v3->co, evl->v4->co, evl->n);
611                 else CalcNormFloat(evl->v1->co, evl->v2->co, evl->v3->co, evl->n);
612                 evl= evl->next;
613         }
614 }
615
616 static void flipvlak(EditVlak *evl)
617 {
618         if(evl->v4) {
619                 SWAP(EditVert *, evl->v2, evl->v4);
620                 SWAP(EditEdge *, evl->e1, evl->e4);
621                 SWAP(EditEdge *, evl->e2, evl->e3);
622                 SWAP(unsigned int, evl->col[1], evl->col[3]);
623                 if(evl->tface) {
624                         SWAP(float, evl->uv[1][0], evl->uv[3][0]);
625                         SWAP(float, evl->uv[1][1], evl->uv[3][1]);
626                 }
627         }
628         else {
629                 SWAP(EditVert *, evl->v2, evl->v3);
630                 SWAP(EditEdge *, evl->e1, evl->e3);
631                 SWAP(unsigned int, evl->col[1], evl->col[2]);
632                 evl->e2->dir= 1-evl->e2->dir;
633                 if(evl->tface) {
634                         SWAP(float, evl->uv[1][0], evl->uv[2][0]);
635                         SWAP(float, evl->uv[1][1], evl->uv[2][1]);
636                 }
637         }
638         if(evl->v4) CalcNormFloat4(evl->v1->co, evl->v2->co, evl->v3->co, evl->v4->co, evl->n);
639         else CalcNormFloat(evl->v1->co, evl->v2->co, evl->v3->co, evl->n);
640 }
641
642
643 void flip_editnormals(void)
644 {
645         EditVlak *evl;
646         
647         evl= G.edvl.first;
648         while(evl) {
649                 if( vlakselectedAND(evl, 1) ) {
650                         flipvlak(evl);
651                 }
652                 evl= evl->next;
653         }
654 }
655
656 /* ************************ IN & OUT ***************************** */
657
658 static void edge_normal_compare(EditEdge *eed, EditVlak *evl1)
659 {
660         EditVlak *evl2;
661         float cent1[3], cent2[3];
662         float inp;
663         
664         evl2= (EditVlak *)eed->vn;
665         if(evl1==evl2) return;
666         
667         inp= evl1->n[0]*evl2->n[0] + evl1->n[1]*evl2->n[1] + evl1->n[2]*evl2->n[2];
668         if(inp<0.999 && inp >-0.999) eed->f= 1;
669                 
670         if(evl1->v4) CalcCent4f(cent1, evl1->v1->co, evl1->v2->co, evl1->v3->co, evl1->v4->co);
671         else CalcCent3f(cent1, evl1->v1->co, evl1->v2->co, evl1->v3->co);
672         if(evl2->v4) CalcCent4f(cent2, evl2->v1->co, evl2->v2->co, evl2->v3->co, evl2->v4->co);
673         else CalcCent3f(cent2, evl2->v1->co, evl2->v2->co, evl2->v3->co);
674         
675         VecSubf(cent1, cent2, cent1);
676         Normalise(cent1);
677         inp= cent1[0]*evl1->n[0] + cent1[1]*evl1->n[1] + cent1[2]*evl1->n[2]; 
678
679         if(inp < -0.001 ) eed->f1= 1;
680 }
681
682 static void edge_drawflags(void)
683 {
684         EditVert *eve;
685         EditEdge *eed, *e1, *e2, *e3, *e4;
686         EditVlak *evl;
687         
688         /* - tel aantal keren in vlakken gebruikt: 0 en 1 is tekenen
689          * - edges meer dan 1 keer: in *vn zit pointer naar (eerste) vlak
690          * - loop alle vlakken af, is normaal te afwijkend: tekenen (flag wordt 1)
691          */
692         
693         recalc_editnormals();
694         
695         /* init */
696         eve= G.edve.first;
697         while(eve) {
698                 eve->f1= 1;             /* wordt bij test op nul gezet */
699                 eve= eve->next;
700         }
701         eed= G.eded.first;
702         while(eed) {
703                 eed->f= eed->f1= 0;
704                 eed->vn= 0;
705                 eed= eed->next;
706         }
707
708         evl= G.edvl.first;
709         while(evl) {
710                 e1= evl->e1;
711                 e2= evl->e2;
712                 e3= evl->e3;
713                 e4= evl->e4;
714                 if(e1->f<3) e1->f+= 1;
715                 if(e2->f<3) e2->f+= 1;
716                 if(e3->f<3) e3->f+= 1;
717                 if(e4 && e4->f<3) e4->f+= 1;
718                 
719                 if(e1->vn==0) e1->vn= (EditVert *)evl;
720                 if(e2->vn==0) e2->vn= (EditVert *)evl;
721                 if(e3->vn==0) e3->vn= (EditVert *)evl;
722                 if(e4 && e4->vn==0) e4->vn= (EditVert *)evl;
723                 
724                 evl= evl->next;
725         }
726
727         if(G.f & G_ALLEDGES) {
728                 evl= G.edvl.first;
729                 while(evl) {
730                         if(evl->e1->f>=2) evl->e1->f= 1;
731                         if(evl->e2->f>=2) evl->e2->f= 1;
732                         if(evl->e3->f>=2) evl->e3->f= 1;
733                         if(evl->e4 && evl->e4->f>=2) evl->e4->f= 1;
734                         
735                         evl= evl->next;
736                 }               
737         }       
738         else {
739                 
740                 /* single-edges afvangen voor cylinder flag */
741                 
742                 eed= G.eded.first;
743                 while(eed) {
744                         if(eed->f==1) eed->f1= 1;
745                         eed= eed->next;
746                 }
747
748                 /* alle vlakken, alle edges met flag==2: vergelijk normaal */
749                 evl= G.edvl.first;
750                 while(evl) {
751                         if(evl->e1->f==2) edge_normal_compare(evl->e1, evl);
752                         if(evl->e2->f==2) edge_normal_compare(evl->e2, evl);
753                         if(evl->e3->f==2) edge_normal_compare(evl->e3, evl);
754                         if(evl->e4 && evl->e4->f==2) edge_normal_compare(evl->e4, evl);
755                         
756                         evl= evl->next;
757                 }
758                 
759                 /* sphere collision flag */
760                 
761                 eed= G.eded.first;
762                 while(eed) {
763                         if(eed->f1!=1) {
764                                 eed->v1->f1= eed->v2->f1= 0;
765                         }
766                         eed= eed->next;
767                 }
768                 
769         }
770 }
771
772 static int contrpuntnorm(float *n, float *puno)
773 {
774         float inp;
775
776         inp= n[0]*puno[0]+n[1]*puno[1]+n[2]*puno[2];
777
778         /* angles 90 degrees: dont flip */
779         if(inp> -0.000001) return 0;
780
781         return 1;
782 }
783
784 void vertexnormals(int testflip)
785 {
786         Mesh *me;
787         EditVert *eve;
788         EditVlak *evl;  
789         float n1[3], n2[3], n3[3], n4[3], co[4], fac1, fac2, fac3, fac4, *temp;
790         float *f1, *f2, *f3, *f4, xn, yn, zn;
791         float opp, len;
792         
793         if(G.obedit && G.obedit->type==OB_MESH) {
794                 me= G.obedit->data;
795                 if((me->flag & ME_TWOSIDED)==0) testflip= 0;
796         }
797
798         if(G.totvert==0) return;
799
800         if(G.totface==0) {
801                 /* namaak puno's voor halopuno! */
802                 eve= G.edve.first;
803                 while(eve) {
804                         VECCOPY(eve->no, eve->co);
805                         Normalise( (float *)eve->no);
806                         eve= eve->next;
807                 }
808                 return;
809         }
810
811         /* clear normals */     
812         eve= G.edve.first;
813         while(eve) {
814                 eve->no[0]= eve->no[1]= eve->no[2]= 0.0;
815                 eve= eve->next;
816         }
817         
818         /* berekenen cos hoeken en oppervlakte en optellen bij puno */
819         evl= G.edvl.first;
820         while(evl) {
821                 VecSubf(n1, evl->v2->co, evl->v1->co);
822                 VecSubf(n2, evl->v3->co, evl->v2->co);
823                 Normalise(n1);
824                 Normalise(n2);
825
826                 if(evl->v4==0) {
827                         VecSubf(n3, evl->v1->co, evl->v3->co);
828                         Normalise(n3);
829                         
830                         /* opp= AreaT3Dfl(evl->v1->co, evl->v2->co, evl->v3->co); */
831                         /* if(opp!=0.0) opp=1.0/opp;  */
832                         /* opp= sqrt(opp); */
833                         /* for smooth subdivide...*/
834                         opp= 1.0;
835                         co[0]= opp*saacos(-n3[0]*n1[0]-n3[1]*n1[1]-n3[2]*n1[2]);
836                         co[1]= opp*saacos(-n1[0]*n2[0]-n1[1]*n2[1]-n1[2]*n2[2]);
837                         co[2]= opp*saacos(-n2[0]*n3[0]-n2[1]*n3[1]-n2[2]*n3[2]);
838                         
839                 }
840                 else {
841                         VecSubf(n3, evl->v4->co, evl->v3->co);
842                         VecSubf(n4, evl->v1->co, evl->v4->co);
843                         Normalise(n3);
844                         Normalise(n4);
845                         
846                         /* opp= AreaQ3Dfl(evl->v1->co, evl->v2->co, evl->v3->co, evl->v4->co); */
847                         /* if(opp!=0.0) opp=1.0/opp;  */
848                         /* opp= sqrt(opp); */
849                         /* for smooth subdivide...*/
850                         opp= 1.0;
851                         co[0]= opp*saacos(-n4[0]*n1[0]-n4[1]*n1[1]-n4[2]*n1[2]);
852                         co[1]= opp*saacos(-n1[0]*n2[0]-n1[1]*n2[1]-n1[2]*n2[2]);
853                         co[2]= opp*saacos(-n2[0]*n3[0]-n2[1]*n3[1]-n2[2]*n3[2]);
854                         co[3]= opp*saacos(-n3[0]*n4[0]-n3[1]*n4[1]-n3[2]*n4[2]);
855                 }
856                 
857                 temp= evl->v1->no;
858                 if(testflip && contrpuntnorm(evl->n, temp) ) co[0]= -co[0];
859                 temp[0]+= co[0]*evl->n[0];
860                 temp[1]+= co[0]*evl->n[1];
861                 temp[2]+= co[0]*evl->n[2];
862                 
863                 temp= evl->v2->no;
864                 if(testflip && contrpuntnorm(evl->n, temp) ) co[1]= -co[1];
865                 temp[0]+= co[1]*evl->n[0];
866                 temp[1]+= co[1]*evl->n[1];
867                 temp[2]+= co[1]*evl->n[2];
868                 
869                 temp= evl->v3->no;
870                 if(testflip && contrpuntnorm(evl->n, temp) ) co[2]= -co[2];
871                 temp[0]+= co[2]*evl->n[0];
872                 temp[1]+= co[2]*evl->n[1];
873                 temp[2]+= co[2]*evl->n[2];
874                 
875                 if(evl->v4) {
876                         temp= evl->v4->no;
877                         if(testflip && contrpuntnorm(evl->n, temp) ) co[3]= -co[3];
878                         temp[0]+= co[3]*evl->n[0];
879                         temp[1]+= co[3]*evl->n[1];
880                         temp[2]+= co[3]*evl->n[2];
881                 }
882                 
883                 evl= evl->next;
884         }
885
886         /* normaliseren puntnormalen */
887         eve= G.edve.first;
888         while(eve) {
889                 len= Normalise(eve->no);
890                 if(len==0.0) {
891                         VECCOPY(eve->no, eve->co);
892                         Normalise( eve->no);
893                 }
894                 eve= eve->next;
895         }
896         
897         /* puntnormaal omklap-vlaggen voor bij shade */
898         evl= G.edvl.first;
899         while(evl) {
900                 evl->f=0;                       
901
902                 if(testflip) {
903                         f1= evl->v1->no;
904                         f2= evl->v2->no;
905                         f3= evl->v3->no;
906                         
907                         fac1= evl->n[0]*f1[0] + evl->n[1]*f1[1] + evl->n[2]*f1[2];
908                         if(fac1<0.0) {
909                                 evl->f = ME_FLIPV1;
910                         }
911                         fac2= evl->n[0]*f2[0] + evl->n[1]*f2[1] + evl->n[2]*f2[2];
912                         if(fac2<0.0) {
913                                 evl->f += ME_FLIPV2;
914                         }
915                         fac3= evl->n[0]*f3[0] + evl->n[1]*f3[1] + evl->n[2]*f3[2];
916                         if(fac3<0.0) {
917                                 evl->f += ME_FLIPV3;
918                         }
919                         if(evl->v4) {
920                                 f4= evl->v4->no;
921                                 fac4= evl->n[0]*f4[0] + evl->n[1]*f4[1] + evl->n[2]*f4[2];
922                                 if(fac4<0.0) {
923                                         evl->f += ME_FLIPV4;
924                                 }
925                         }
926                 }
927                 /* proj voor cubemap! */
928                 xn= fabs(evl->n[0]);
929                 yn= fabs(evl->n[1]);
930                 zn= fabs(evl->n[2]);
931                 
932                 if(zn>xn && zn>yn) evl->f += ME_PROJXY;
933                 else if(yn>xn && yn>zn) evl->f += ME_PROJXZ;
934                 else evl->f += ME_PROJYZ;
935                 
936                 evl= evl->next;
937         }
938 }
939
940 void free_editMesh(void)
941 {
942
943 //      if(G.edve.first) BLI_freelist(&G.edve);
944         if(G.edve.first) free_editverts(&G.edve);
945         if(G.eded.first) BLI_freelist(&G.eded);
946         if(G.edvl.first) freevlaklist(&G.edvl);
947         free_hashedgetab();
948         G.totvert= G.totface= 0;
949 }
950
951 static void free_editverts(ListBase *edve) {
952 #ifdef __NLA
953         EditVert *eve;
954 #endif
955
956         if (!edve)
957                 return;
958
959         if (!edve->first)
960                 return;
961
962 #ifdef __NLA
963         for (eve= edve->first; eve; eve=eve->next){
964                 if (eve->dw)
965                         MEM_freeN (eve->dw);
966         }
967 #endif
968
969         BLI_freelist (edve);
970
971 }
972
973 static void free_editvert (EditVert *eve)
974 {
975 #ifdef __NLA
976         if (eve->dw)
977                 MEM_freeN (eve->dw);
978 #endif
979         free (eve);
980 }
981
982 void make_editMesh(void)
983 {
984         Mesh *me;
985         MFace *mface;
986         TFace *tface;
987         MVert *mvert;
988         KeyBlock *actkey=0;
989         EditVert *eve, **evlist, *eve1, *eve2, *eve3, *eve4;
990         EditVlak *evl;
991         int tot, a;
992
993         if(G.obedit==0) return;
994
995         /* ivm reload */
996         free_editMesh();
997         
998         me= get_mesh(G.obedit);
999         G.totvert= tot= me->totvert;
1000
1001         if(tot==0) {
1002                 countall();
1003                 return;
1004         }
1005         
1006         waitcursor(1);
1007
1008         /* keys? */
1009         if(me->key) {
1010                 actkey= me->key->block.first;
1011                 while(actkey) {
1012                         if(actkey->flag & SELECT) break;
1013                         actkey= actkey->next;
1014                 }
1015         }
1016
1017         if(actkey) {
1018                 key_to_mesh(actkey, me);
1019                 tot= actkey->totelem;
1020         }
1021
1022         /* editverts aanmaken */
1023         mvert= me->mvert;
1024
1025         evlist= (EditVert **)MEM_mallocN(tot*sizeof(void *),"evlist");
1026         for(a=0; a<tot; a++, mvert++) {
1027                 eve= addvertlist(mvert->co);
1028                 evlist[a]= eve;
1029                 eve->no[0]= mvert->no[0]/32767.0;
1030                 eve->no[1]= mvert->no[1]/32767.0;
1031                 eve->no[2]= mvert->no[2]/32767.0;
1032 #ifdef __NLA
1033
1034                 /* OLD VERSION */
1035                 /*
1036                 eve->totweight = mvert->totweight;
1037                 if (mvert->dw){
1038                         eve->dw = BLI_callocN (sizeof(MDeformWeight) * mvert->totweight, "deformWeight");
1039                         memcpy (eve->dw, mvert->dw, sizeof(MDeformWeight) * mvert->totweight);
1040                 }
1041                 */
1042
1043                 /* NEW VERSION */
1044                 if (me->dvert){
1045                         eve->totweight = me->dvert[a].totweight;
1046                         if (me->dvert[a].dw){
1047                                 eve->dw = MEM_callocN (sizeof(MDeformWeight) * me->dvert[a].totweight, "deformWeight");
1048                                 memcpy (eve->dw, me->dvert[a].dw, sizeof(MDeformWeight) * me->dvert[a].totweight);
1049                         }
1050                 }
1051
1052 #endif
1053         }
1054
1055         if(actkey && actkey->totelem!=me->totvert);
1056         else {
1057                 unsigned int *mcol;
1058                 
1059                 /* edges en vlakken maken */
1060                 mface= me->mface;
1061                 tface= me->tface;
1062                 mcol= (unsigned int *)me->mcol;
1063                 
1064                 for(a=0; a<me->totface; a++, mface++) {
1065                         eve1= evlist[mface->v1];
1066                         eve2= evlist[mface->v2];
1067                         if(mface->v3) eve3= evlist[mface->v3]; else eve3= 0;
1068                         if(mface->v4) eve4= evlist[mface->v4]; else eve4= 0;
1069                         
1070                         evl= addvlaklist(eve1, eve2, eve3, eve4, NULL);
1071                         
1072                         if(evl) {
1073                                 if(mcol) memcpy(evl->col, mcol, 4*sizeof(int));
1074
1075                                 if(me->tface) {
1076                                         memcpy(evl->col, tface->col, sizeof(tface->col));
1077                                         memcpy(evl->uv, tface->uv, sizeof(tface->uv));
1078
1079                                         if( tface->flag & TF_SELECT) {
1080                                                 if(G.f & G_FACESELECT) {
1081                                                         eve1->f |= 1;
1082                                                         eve2->f |= 1;
1083                                                         if(eve3) eve3->f |= 1;
1084                                                         if(eve4) eve4->f |= 1;
1085                                                 }
1086                                         }
1087                                 }
1088                         
1089                                 evl->mat_nr= mface->mat_nr;
1090                                 evl->flag= mface->flag;
1091                                 evl->tface= tface;
1092                         }
1093
1094                         if(me->tface) tface++;
1095                         if(mcol) mcol+=4;
1096                 }
1097         }
1098         MEM_freeN(evlist);
1099         
1100         countall();
1101         
1102         if (mesh_uses_displist(me))
1103                 makeDispList(G.obedit);
1104         
1105         waitcursor(0);
1106 }
1107
1108 /** Rotates MFace and UVFace vertices in case the last
1109   * vertex index is = 0. 
1110   * This function is a hack and may only be called in the
1111   * conversion from EditMesh to Mesh data.
1112   * This function is similar to test_index_mface in
1113   * blenkernel/intern/mesh.c. 
1114   * To not clutter the blenkernel code with more bad level
1115   * calls/structures, this function resides here.
1116   */
1117
1118
1119 static void fix_faceindices(MFace *mface, EditVlak *evl, int nr)
1120 {
1121         int a;
1122         float tmpuv[2];
1123         unsigned int tmpcol;
1124
1125 /*
1126 mface =  ((MFace *) me->mface) + index;
1127         tface =  ((TFace *) me->tface) + index;
1128
1129 */
1130
1131         /* first test if the face is legal */
1132
1133         if(mface->v3 && mface->v3==mface->v4) {
1134                 mface->v4= 0;
1135                 nr--;
1136         }
1137         if(mface->v2 && mface->v2==mface->v3) {
1138                 mface->v3= mface->v4;
1139                 mface->v4= 0;
1140                 nr--;
1141         }
1142         if(mface->v1==mface->v2) {
1143                 mface->v2= mface->v3;
1144                 mface->v3= mface->v4;
1145                 mface->v4= 0;
1146                 nr--;
1147         }
1148
1149         /* voorkom dat een nul op de verkeerde plek staat */
1150         if(nr==2) {
1151                 if(mface->v2==0) SWAP(int, mface->v1, mface->v2);
1152         }
1153         else if(nr==3) {
1154                 if(mface->v3==0) {
1155                         SWAP(int, mface->v1, mface->v2);
1156                         SWAP(int, mface->v2, mface->v3);
1157                         /* rotate face UV coordinates, too */
1158                         UVCOPY(tmpuv, evl->uv[0]);
1159                         UVCOPY(evl->uv[0], evl->uv[1]);
1160                         UVCOPY(evl->uv[1], evl->uv[2]);
1161                         UVCOPY(evl->uv[2], tmpuv);
1162                         /* same with vertex colours */
1163                         tmpcol = evl->col[0];
1164                         evl->col[0] = evl->col[1];
1165                         evl->col[1] = evl->col[2];
1166                         evl->col[2] = tmpcol;
1167
1168                         
1169                         a= mface->edcode;
1170                         mface->edcode= 0;
1171                         if(a & ME_V1V2) mface->edcode |= ME_V3V1;
1172                         if(a & ME_V2V3) mface->edcode |= ME_V1V2;
1173                         if(a & ME_V3V1) mface->edcode |= ME_V2V3;
1174                         
1175                         a= mface->puno;
1176                         mface->puno &= ~15;
1177                         if(a & ME_FLIPV1) mface->puno |= ME_FLIPV2;
1178                         if(a & ME_FLIPV2) mface->puno |= ME_FLIPV3;
1179                         if(a & ME_FLIPV3) mface->puno |= ME_FLIPV1;
1180                 }
1181         }
1182         else if(nr==4) {
1183                 if(mface->v3==0 || mface->v4==0) {
1184                         SWAP(int, mface->v1, mface->v3);
1185                         SWAP(int, mface->v2, mface->v4);
1186                         /* swap UV coordinates */
1187                         UVCOPY(tmpuv, evl->uv[0]);
1188                         UVCOPY(evl->uv[0], evl->uv[2]);
1189                         UVCOPY(evl->uv[2], tmpuv);
1190                         UVCOPY(tmpuv, evl->uv[1]);
1191                         UVCOPY(evl->uv[1], evl->uv[3]);
1192                         UVCOPY(evl->uv[3], tmpuv);
1193                         /* swap vertex colours */
1194                         tmpcol = evl->col[0];
1195                         evl->col[0] = evl->col[2];
1196                         evl->col[2] = tmpcol;
1197                         tmpcol = evl->col[1];
1198                         evl->col[1] = evl->col[3];
1199                         evl->col[3] = tmpcol;
1200
1201                         a= mface->edcode;
1202                         mface->edcode= 0;
1203                         if(a & ME_V1V2) mface->edcode |= ME_V3V4;
1204                         if(a & ME_V2V3) mface->edcode |= ME_V2V3;
1205                         if(a & ME_V3V4) mface->edcode |= ME_V1V2;
1206                         if(a & ME_V4V1) mface->edcode |= ME_V4V1;
1207
1208                         a= mface->puno;
1209                         mface->puno &= ~15;
1210                         if(a & ME_FLIPV1) mface->puno |= ME_FLIPV3;
1211                         if(a & ME_FLIPV2) mface->puno |= ME_FLIPV4;
1212                         if(a & ME_FLIPV3) mface->puno |= ME_FLIPV1;
1213                         if(a & ME_FLIPV4) mface->puno |= ME_FLIPV2;
1214                 }
1215         }
1216
1217 }
1218
1219
1220
1221 /* load from EditMode to Mesh */
1222
1223 void load_editMesh(void)
1224 {
1225         Mesh *me;
1226         MFace *mface;
1227         MVert *mvert;
1228         MSticky *ms;
1229         KeyBlock *actkey=0;
1230         EditVert *eve;
1231         EditVlak *evl;
1232         EditEdge *eed;
1233         float *fp, nor[3];
1234         int i, a, ototvert;
1235 #ifdef __NLA
1236         MDeformVert *dvert;
1237         int     usedDvert = 0;
1238 #endif
1239
1240         waitcursor(1);
1241         countall();
1242         
1243         me= get_mesh(G.obedit);
1244         
1245         ototvert= me->totvert;
1246         
1247         /* zijn er keys? */
1248         if(me->key) {
1249                 actkey= me->key->block.first;
1250                 while(actkey) {
1251                         if(actkey->flag & SELECT) break;
1252                         actkey= actkey->next;
1253                 }
1254         }
1255
1256         
1257         if(actkey && me->key->refkey!=actkey) {
1258                 /* aktieve key && niet de refkey: alleen vertices */
1259                                 
1260                 if(G.totvert) {
1261                         if(actkey->data) MEM_freeN(actkey->data);
1262                 
1263                         fp=actkey->data= MEM_callocN(me->key->elemsize*G.totvert, "actkey->data");
1264                         actkey->totelem= G.totvert;
1265         
1266                         eve= G.edve.first;
1267                         while(eve) {
1268                                 VECCOPY(fp, eve->co);
1269                                 fp+= 3;
1270                                 eve= eve->next;
1271                         }
1272                 }
1273         }
1274         else if(me->key && actkey==0) {
1275                 /* er zijn keys, alleen veranderingen in mverts schrijven */
1276                 /* als aantal vertices verschillen, beetje onvoorspelbaar */
1277                         
1278                 eve= G.edve.first;
1279                 mvert= me->mvert;
1280                 for(a=0; a<me->totvert; a++, mvert++) {
1281                         VECCOPY(mvert->co, eve->co);
1282                         eve= eve->next;
1283                         if(eve==0) break;
1284                 }
1285         }
1286         else {
1287                 /* als er keys zijn: de refkey, anders gewoon de me */
1288                 
1289                 /* deze telt ook of edges niet in vlakken zitten: */
1290                 /* eed->f==0 niet in vlak, f==1 is tekenen */
1291                 /* eed->f1 : flag voor dynaface (cylindertest) */
1292                 /* eve->f1 : flag voor dynaface (sphere test) */
1293                 edge_drawflags();
1294         
1295                 /* LET OP: op evl->f de punoflag */
1296                 vertexnormals( (me->flag & ME_NOPUNOFLIP)==0 );
1297         
1298                 eed= G.eded.first;
1299                 while(eed) {
1300                         if(eed->f==0) G.totface++;
1301                         eed= eed->next;
1302                 }
1303         
1304                 /* nieuw Face blok */
1305                 if(G.totface==0) mface= 0;
1306                 else mface= MEM_callocN(G.totface*sizeof(MFace), "loadeditMesh1");
1307                 /* nieuw Vertex blok */
1308                 if(G.totvert==0) mvert= 0;
1309                 else mvert= MEM_callocN(G.totvert*sizeof(MVert), "loadeditMesh2");
1310
1311 #ifdef __NLA
1312                 if (G.totvert==0) dvert=0;
1313                 else dvert = MEM_callocN(G.totvert*sizeof(MDeformVert), "loadeditMesh3");
1314
1315                 if (me->dvert) free_dverts(me->dvert, me->totvert);
1316                 me->dvert=dvert;
1317 #endif          
1318                 if(me->mvert) MEM_freeN(me->mvert);
1319                 me->mvert= mvert;
1320
1321                 if(me->mface) MEM_freeN(me->mface);
1322                 me->mface= mface;
1323                 me->totvert= G.totvert;
1324                 me->totface= G.totface;
1325                 
1326                 /* de vertices, gebruik ->vn als teller */
1327                 eve= G.edve.first;
1328                 a=0;
1329
1330
1331
1332                 while(eve) {
1333                         VECCOPY(mvert->co, eve->co);
1334                         mvert->mat_nr= 255;  /* waarvoor ook al weer, haloos? */
1335                         
1336                         /* puno */
1337                         VECCOPY(nor, eve->no);
1338                         VecMulf(nor, 32767.0);
1339                         VECCOPY(mvert->no, nor);
1340 #ifdef __NLA
1341 /*                      OLD VERSION */
1342 /*                      mvert->totweight = eve->totweight;
1343                         if (eve->dw){
1344                                 int     cv;
1345                                 mvert->dw = BLI_callocN (sizeof(MDeformWeight)*eve->totweight, "deformWeight");
1346                                 memcpy (mvert->dw, eve->dw, sizeof(MDeformWeight)*eve->totweight);
1347                         }
1348 */
1349                         /* NEW VERSION */
1350                         if (dvert){
1351                                 dvert->totweight=eve->totweight;
1352                                 if (eve->dw){
1353                                         dvert->dw = MEM_callocN (sizeof(MDeformWeight)*eve->totweight, "deformWeight");
1354                                         memcpy (dvert->dw, eve->dw, sizeof(MDeformWeight)*eve->totweight);
1355                                         usedDvert++;
1356                                 }
1357                         }
1358 #endif
1359
1360                         eve->vn= (EditVert *)(long)(a++);  /* teller */
1361                         
1362                         mvert->flag= 0;
1363                         if(eve->f1==1) mvert->flag |= ME_SPHERETEST;
1364                         
1365                         eve= eve->next;
1366                         mvert++;
1367 #ifdef __NLA
1368                         dvert++;
1369 #endif
1370                 }
1371         
1372 #ifdef __NLA
1373                 /* If we didn't actually need the dverts, get rid of them */
1374                 if (!usedDvert){
1375                         free_dverts(me->dvert, G.totvert);
1376                         me->dvert=NULL;
1377                 }
1378 #endif
1379
1380                 /* de vlakken */
1381                 evl= G.edvl.first;
1382                 i = 0;
1383                 while(evl) {
1384                         mface= &((MFace *) me->mface)[i];
1385
1386                         mface->v1= (unsigned int) evl->v1->vn;
1387                         mface->v2= (unsigned int) evl->v2->vn;
1388                         mface->v3= (unsigned int) evl->v3->vn;
1389                         if(evl->v4) mface->v4= (unsigned int) evl->v4->vn;
1390                         
1391                         mface->mat_nr= evl->mat_nr;
1392                         mface->puno= evl->f;
1393                         mface->flag= evl->flag;
1394                         
1395                         /* mat_nr in vertex */
1396                         if(me->totcol>1) {
1397                                 mvert= me->mvert+mface->v1;
1398                                 if(mvert->mat_nr == 255) mvert->mat_nr= mface->mat_nr;
1399                                 mvert= me->mvert+mface->v2;
1400                                 if(mvert->mat_nr == 255) mvert->mat_nr= mface->mat_nr;
1401                                 mvert= me->mvert+mface->v3;
1402                                 if(mvert->mat_nr == 255) mvert->mat_nr= mface->mat_nr;
1403                                 if(mface->v4) {
1404                                         mvert= me->mvert+mface->v4;
1405                                         if(mvert->mat_nr == 255) mvert->mat_nr= mface->mat_nr;
1406                                 }
1407                         }
1408                         
1409                         /* dyna cilinder flag minder kritisch testen: 'dubbel' in vlakken laten zitten. 
1410                          * gaat anders fout bij scherpe hoeken (inpspeed voor een wel, ander niet!)
1411                          * Mogelijk oplossen door volgorde aan te passen: sphere-cyl-face. Kost te veel?
1412                          */
1413
1414                         /* letop: evl->e1->f==0 is losse edge */ 
1415                         
1416                         if(evl->e1->f==1) {
1417                                 mface->edcode |= ME_V1V2; 
1418                                 evl->e1->f= 2;
1419                         }                       
1420                         if(evl->e2->f==1) {
1421                                 mface->edcode |= ME_V2V3; 
1422                                 evl->e2->f= 2;
1423                         }
1424                         if(evl->e3->f==1) {
1425                                 if(evl->v4) {
1426                                         mface->edcode |= ME_V3V4;
1427                                 }
1428                                 else {
1429                                         mface->edcode |= ME_V3V1;
1430                                 }
1431                                 evl->e3->f= 2;
1432                         }
1433                         if(evl->e4 && evl->e4->f==1) {
1434                                 mface->edcode |= ME_V4V1; 
1435                                 evl->e4->f= 2;
1436                         }
1437                         
1438                         /* geen index '0' op plek 3 of 4 */
1439                         if(evl->v4) fix_faceindices(mface, evl, 4);
1440                         else fix_faceindices(mface, evl, 3);
1441                         
1442                         i++;
1443                         evl= evl->next;
1444                 }
1445                 
1446                 /* losse edges als vlak toevoegen */
1447                 eed= G.eded.first;
1448                 while(eed) {
1449                         if( eed->f==0 ) {
1450                                 mface= &((MFace *) me->mface)[i];
1451                                 mface->v1= (unsigned int) eed->v1->vn;
1452                                 mface->v2= (unsigned int) eed->v2->vn;
1453                                 test_index_mface(mface, 2);
1454                                 mface->edcode= ME_V1V2;
1455                                 i++;
1456                         }
1457                         eed= eed->next;
1458                 }
1459                 
1460                 tex_space_mesh(me);
1461                 if(actkey) mesh_to_key(me, actkey);
1462                 
1463                 /* texmesh: ahv ->tface alles opnieuw maken */
1464                 if(me->tface && me->totface) {
1465                         TFace *tfn, *tf;
1466                         
1467                         tf=tfn= MEM_callocN(sizeof(TFace)*me->totface, "tface");
1468                         evl= G.edvl.first;
1469                         while(evl) {
1470                                 
1471                                 if(evl->tface) *tf= *(evl->tface);
1472                                 else default_tface(tf);
1473                                 
1474                                 memcpy(tf->col, evl->col, sizeof(tf->col));
1475                                 memcpy(tf->uv, evl->uv, sizeof(tf->uv));
1476                                 
1477                                 if(G.f & G_FACESELECT) {
1478                                         if( vlakselectedAND(evl, 1) ) tf->flag |= TF_SELECT;
1479                                         else tf->flag &= ~TF_SELECT;
1480                                 }
1481                                 
1482                                 /* sometimes editmode doesn't free (before render) */
1483                                 evl->tface= tf;
1484
1485                                 tf++;
1486                                 evl= evl->next;
1487                         }
1488                         
1489                         MEM_freeN(me->tface);
1490                         me->tface= tfn;
1491                 }
1492                 else if(me->tface) {
1493                         /* freeN(me->tface); */
1494                         /* me->tface= 0; */
1495                 }
1496                 
1497                 /* mcol: ahv indexnrs opnieuw maken */
1498                 if(me->mcol && me->totface) {
1499                         unsigned int *mcn, *mc;
1500                         
1501                         mc=mcn= MEM_mallocN(4*sizeof(int)*me->totface, "mcol");
1502                         evl= G.edvl.first;
1503                         while(evl) {
1504                         
1505                                 memcpy(mc, evl->col, 4*sizeof(int));
1506                                 
1507                                 mc+=4;
1508                                 evl= evl->next;
1509                         }
1510                         
1511                         MEM_freeN(me->mcol);
1512                         me->mcol= (MCol *)mcn;
1513                 }
1514                 else if(me->mcol) {
1515                         MEM_freeN(me->mcol);
1516                         me->mcol= 0;
1517                 }
1518         }
1519         
1520         if(actkey) do_spec_key(me->key);
1521         
1522         /* voor zekerheid: ->vn pointers wissen */
1523         eve= G.edve.first;
1524         while(eve) {
1525                 eve->vn= 0;
1526                 eve= eve->next;
1527         }
1528
1529         /* displisten van alle users, ook deze */
1530         freedisplist(&me->disp);
1531         freedisplist(&G.obedit->disp);
1532         
1533         /* sticky */
1534         if(me->msticky) {
1535                 if (ototvert<me->totvert) {
1536                         ms= MEM_callocN(me->totvert*sizeof(MSticky), "msticky");
1537                         memcpy(ms, me->msticky, ototvert*sizeof(MSticky));
1538                         MEM_freeN(me->msticky);
1539                         me->msticky= ms;
1540                         error("Sticky was too small");
1541                 }
1542         }
1543         waitcursor(0);
1544 }
1545
1546
1547 void remake_editMesh(void)
1548 {
1549
1550         if(okee("Reload Original data")==0) return;
1551         
1552         make_editMesh();
1553         allqueue(REDRAWVIEW3D, 0);
1554         makeDispList(G.obedit);
1555 }
1556
1557 /* *********************  TOOLS  ********************* */
1558
1559
1560
1561 void make_sticky(void)
1562 {
1563         Object *ob;
1564         Base *base;
1565         MVert *mvert;
1566         Mesh *me;
1567         MSticky *ms;
1568         float ho[4], mat[4][4];
1569         int a;
1570         
1571         if(G.scene->camera==0) return;
1572         
1573         if(G.obedit) {
1574                 error("Unable to perform function in EditMode");
1575                 return;
1576         }
1577         base= FIRSTBASE;
1578         while(base) {
1579                 if TESTBASELIB(base) {
1580                         if(base->object->type==OB_MESH) {
1581                                 ob= base->object;
1582                                 
1583                                 me= ob->data;
1584                                 mvert= me->mvert;
1585                                 if(me->msticky) MEM_freeN(me->msticky);
1586                                 me->msticky= MEM_mallocN(me->totvert*sizeof(MSticky), "sticky");
1587                                 
1588                                 /* stukje roteerscene */                
1589                                 R.r= G.scene->r;
1590                                 R.r.xsch= (R.r.size*R.r.xsch)/100;
1591                                 R.r.ysch= (R.r.size*R.r.ysch)/100;
1592                                 
1593                                 R.afmx= R.r.xsch/2;
1594                                 R.afmy= R.r.ysch/2;
1595                                 
1596                                 R.ycor= ( (float)R.r.yasp)/( (float)R.r.xasp);
1597                 
1598                                 R.rectx= R.r.xsch; 
1599                                 R.recty= R.r.ysch;
1600                                 R.xstart= -R.afmx; 
1601                                 R.ystart= -R.afmy;
1602                                 R.xend= R.xstart+R.rectx-1;
1603                                 R.yend= R.ystart+R.recty-1;
1604                 
1605                                 where_is_object(G.scene->camera);
1606                                 Mat4CpyMat4(R.viewinv, G.scene->camera->obmat);
1607                                 Mat4Ortho(R.viewinv);
1608                                 Mat4Invert(R.viewmat, R.viewinv);
1609                                 
1610                                 RE_setwindowclip(1, -1);
1611                 
1612                                 where_is_object(ob);
1613                                 Mat4MulMat4(mat, ob->obmat, R.viewmat);
1614                 
1615                                 ms= me->msticky;
1616                                 for(a=0; a<me->totvert; a++, ms++, mvert++) {
1617                                         VECCOPY(ho, mvert->co);
1618                                         Mat4MulVecfl(mat, ho);
1619                                         RE_projectverto(ho, ho);
1620                                         ms->co[0]= ho[0]/ho[3];
1621                                         ms->co[1]= ho[1]/ho[3];
1622                                 }
1623                         }
1624                 }
1625                 base= base->next;
1626         }
1627         allqueue(REDRAWBUTSEDIT, 0);
1628 }
1629
1630 void fasterdraw(void)
1631 {
1632         Base *base;
1633         Mesh *me;
1634         MFace *mface;
1635         int toggle, a;
1636
1637         if(G.obedit) return;
1638
1639         /* vlaggen resetten */
1640         me= G.main->mesh.first;
1641         while(me) {
1642                 me->flag &= ~ME_ISDONE;
1643                 me= me->id.next;
1644         }
1645
1646         base= FIRSTBASE;
1647         while(base) {
1648                 if( TESTBASELIB(base) && (base->object->type==OB_MESH)) {
1649                         me= base->object->data;
1650                         if(me->id.lib==0 && (me->flag & ME_ISDONE)==0) {
1651                                 me->flag |= ME_ISDONE;
1652                                 mface= me->mface;
1653                                 toggle= 0;
1654                                 for(a=0; a<me->totface; a++) {
1655                                         if( (mface->edcode & ME_V1V2) && ( (toggle++) & 1) ) {
1656                                                 mface->edcode-= ME_V1V2;
1657                                         }
1658                                         if( (mface->edcode & ME_V2V3) && ( (toggle++) & 1)) {
1659                                                 mface->edcode-= ME_V2V3;
1660                                         }
1661                                         if( (mface->edcode & ME_V3V1) && ( (toggle++) & 1)) {
1662                                                 mface->edcode-= ME_V3V1;
1663                                         }
1664                                         if( (mface->edcode & ME_V4V1) && ( (toggle++) & 1)) {
1665                                                 mface->edcode-= ME_V4V1;
1666                                         }
1667                                         if( (mface->edcode & ME_V3V4) && ( (toggle++) & 1)) {
1668                                                 mface->edcode-= ME_V3V4;
1669                                         }
1670                                         mface++;
1671                                 }
1672                         }
1673                 }
1674                 base= base->next;
1675         }
1676
1677         /* belangrijk?: vlaggen weer resetten */
1678         me= G.main->mesh.first;
1679         while(me) {
1680                 me->flag &= ~ME_ISDONE;
1681                 me= me->id.next;
1682         }
1683
1684         allqueue(REDRAWVIEW3D, 0);
1685 }
1686
1687 void slowerdraw(void)           /* reset fasterdraw */
1688 {
1689         Base *base;
1690         Mesh *me;
1691         MFace *mface;
1692         int a;
1693
1694         if(G.obedit) return;
1695
1696         base= FIRSTBASE;
1697         while(base) {
1698                 if( TESTBASELIB(base) && (base->object->type==OB_MESH)) {
1699                         me= base->object->data;
1700                         if(me->id.lib==0) {
1701                                 
1702                                 mface= me->mface;
1703                                 
1704                                 for(a=0; a<me->totface; a++) {
1705                                 
1706                                         mface->edcode |= ME_V1V2|ME_V2V3;
1707                                         mface++;
1708                                 }
1709                         }
1710                 }
1711                 base= base->next;
1712         }
1713
1714         allqueue(REDRAWVIEW3D, 0);
1715 }
1716
1717
1718 void convert_to_triface(int all)
1719 {
1720         EditVlak *evl, *evln, *next;
1721         
1722         evl= G.edvl.first;
1723         while(evl) {
1724                 next= evl->next;
1725                 if(evl->v4) {
1726                         if(all || vlakselectedAND(evl, 1) ) {
1727                                 
1728                                 evln= addvlaklist(evl->v1, evl->v2, evl->v3, 0, evl);
1729                                 evln= addvlaklist(evl->v1, evl->v3, evl->v4, 0, evl);
1730
1731                                 if(evl->tface) {
1732                                         evln->uv[1][0]= evln->uv[2][0];
1733                                         evln->uv[1][1]= evln->uv[2][1];
1734                                         evln->uv[2][0]= evln->uv[3][0];
1735                                         evln->uv[2][1]= evln->uv[3][1];
1736                                 }
1737                                 
1738                                 evln->col[1]= evln->col[2];
1739                                 evln->col[2]= evln->col[3];
1740                                 
1741                                 BLI_remlink(&G.edvl, evl);
1742                                 freevlak(evl);
1743                         }
1744                 }
1745                 evl= next;
1746         }
1747         
1748 }
1749
1750
1751 void deselectall_mesh(void)     /* toggle */
1752 {
1753         EditVert *eve;
1754         int a;
1755         
1756         if(G.obedit->lay & G.vd->lay) {
1757                 a= 0;
1758                 eve= G.edve.first;
1759                 while(eve) {
1760                         if(eve->f & 1) {
1761                                 a= 1;
1762                                 break;
1763                         }
1764                         eve= eve->next;
1765                 }
1766                 eve= G.edve.first;
1767                 while(eve) {
1768                         if(eve->h==0) {
1769                                 if(a) eve->f&= -2;
1770                                 else eve->f|= 1;
1771                         }
1772                         eve= eve->next;
1773                 }
1774                 tekenvertices_ext(a==0);
1775         }
1776         countall();
1777 }
1778
1779
1780 void righthandfaces(int select) /* maakt vlakken rechtsdraaiend */
1781 {
1782         EditEdge *eed, *ed1, *ed2, *ed3, *ed4;
1783         EditVlak *evl, *startvl;
1784         float maxx, nor[3], cent[3];
1785         int totsel, found, foundone, direct, turn;
1786
1787    /* op basis selectconnected om losse objecten te onderscheiden */
1788
1789         /* tel per edge hoeveel vlakken het heeft */
1790
1791         /* vind het meest linkse, voorste, bovenste vlak */
1792
1793         /* zet normaal naar buiten en de eerste richtings vlaggen in de edges */
1794
1795         /* loop object af en zet richtingen / richtingsvlaggen: alleen bij edges van 1 of 2 vlakken */
1796         /* dit is in feit de select connected */
1797
1798         /* indien nog (selected) vlakken niet gedaan: opnieuw vind de meest linkse ... */
1799
1800         waitcursor(1);
1801
1802         eed= G.eded.first;
1803         while(eed) {
1804                 eed->f= 0;
1805                 eed->f1= 0;
1806                 eed= eed->next;
1807         }
1808
1809         /* vlakken en edges tellen */
1810         totsel= 0;
1811         evl= G.edvl.first;
1812         while(evl) {
1813                 if(select==0 || vlakselectedAND(evl, 1) ) {
1814                         evl->f= 1;
1815                         totsel++;
1816                         evl->e1->f1++;
1817                         evl->e2->f1++;
1818                         evl->e3->f1++;
1819                         if(evl->v4) evl->e4->f1++;
1820                 }
1821                 else evl->f= 0;
1822
1823                 evl= evl->next;
1824         }
1825
1826         while(totsel>0) {
1827                 /* van buiten naar binnen */
1828
1829                 evl= G.edvl.first;
1830                 startvl= 0;
1831                 maxx= -1.0e10;
1832
1833                 while(evl) {
1834                         if(evl->f) {
1835                                 CalcCent3f(cent, evl->v1->co, evl->v2->co, evl->v3->co);
1836                                 cent[0]= fabs(cent[0])+fabs(cent[1])+fabs(cent[2]);
1837                                 
1838                                 if(cent[0]>maxx) {
1839                                         maxx= cent[0];
1840                                         startvl= evl;
1841                                 }
1842                         }
1843                         evl= evl->next;
1844                 }
1845                 
1846                 /* eerste vlak goedzetten: normaal berekenen */
1847                 CalcNormFloat(startvl->v1->co, startvl->v2->co, startvl->v3->co, nor);
1848                 CalcCent3f(cent, startvl->v1->co, startvl->v2->co, startvl->v3->co);
1849                 
1850                 /* eerste normaal staat zus of zo */
1851                 if(select) {
1852                         if(select==2) {
1853                                 if(cent[0]*nor[0]+cent[1]*nor[1]+cent[2]*nor[2] > 0.0) flipvlak(startvl);
1854                         }
1855                         else {
1856                                 if(cent[0]*nor[0]+cent[1]*nor[1]+cent[2]*nor[2] < 0.0) flipvlak(startvl);
1857                         }
1858                 }
1859                 else if(cent[0]*nor[0]+cent[1]*nor[1]+cent[2]*nor[2] < 0.0) flipvlak(startvl);
1860
1861
1862                 eed= startvl->e1;
1863                 if(eed->v1==startvl->v1) eed->f= 1; 
1864                 else eed->f= 2;
1865                 
1866                 eed= startvl->e2;
1867                 if(eed->v1==startvl->v2) eed->f= 1; 
1868                 else eed->f= 2;
1869                 
1870                 eed= startvl->e3;
1871                 if(eed->v1==startvl->v3) eed->f= 1; 
1872                 else eed->f= 2;
1873                 
1874                 eed= startvl->e4;
1875                 if(eed) {
1876                         if(eed->v1==startvl->v4) eed->f= 1; 
1877                         else eed->f= 2;
1878                 }
1879                 
1880                 startvl->f= 0;
1881                 totsel--;
1882
1883                 /* de normalen testen */
1884                 found= 1;
1885                 direct= 1;
1886                 while(found) {
1887                         found= 0;
1888                         if(direct) evl= G.edvl.first;
1889                         else evl= G.edvl.last;
1890                         while(evl) {
1891                                 if(evl->f) {
1892                                         turn= 0;
1893                                         foundone= 0;
1894
1895                                         ed1= evl->e1;
1896                                         ed2= evl->e2;
1897                                         ed3= evl->e3;
1898                                         ed4= evl->e4;
1899
1900                                         if(ed1->f) {
1901                                                 if(ed1->v1==evl->v1 && ed1->f==1) turn= 1;
1902                                                 if(ed1->v2==evl->v1 && ed1->f==2) turn= 1;
1903                                                 foundone= 1;
1904                                         }
1905                                         else if(ed2->f) {
1906                                                 if(ed2->v1==evl->v2 && ed2->f==1) turn= 1;
1907                                                 if(ed2->v2==evl->v2 && ed2->f==2) turn= 1;
1908                                                 foundone= 1;
1909                                         }
1910                                         else if(ed3->f) {
1911                                                 if(ed3->v1==evl->v3 && ed3->f==1) turn= 1;
1912                                                 if(ed3->v2==evl->v3 && ed3->f==2) turn= 1;
1913                                                 foundone= 1;
1914                                         }
1915                                         else if(ed4 && ed4->f) {
1916                                                 if(ed4->v1==evl->v4 && ed4->f==1) turn= 1;
1917                                                 if(ed4->v2==evl->v4 && ed4->f==2) turn= 1;
1918                                                 foundone= 1;
1919                                         }
1920
1921                                         if(foundone) {
1922                                                 found= 1;
1923                                                 totsel--;
1924                                                 evl->f= 0;
1925
1926                                                 if(turn) {
1927                                                         if(ed1->v1==evl->v1) ed1->f= 2; 
1928                                                         else ed1->f= 1;
1929                                                         if(ed2->v1==evl->v2) ed2->f= 2; 
1930                                                         else ed2->f= 1;
1931                                                         if(ed3->v1==evl->v3) ed3->f= 2; 
1932                                                         else ed3->f= 1;
1933                                                         if(ed4) {
1934                                                                 if(ed4->v1==evl->v4) ed4->f= 2; 
1935                                                                 else ed4->f= 1;
1936                                                         }
1937
1938                                                         flipvlak(evl);
1939
1940                                                 }
1941                                                 else {
1942                                                         if(ed1->v1== evl->v1) ed1->f= 1; 
1943                                                         else ed1->f= 2;
1944                                                         if(ed2->v1==evl->v2) ed2->f= 1; 
1945                                                         else ed2->f= 2;
1946                                                         if(ed3->v1==evl->v3) ed3->f= 1; 
1947                                                         else ed3->f= 2;
1948                                                         if(ed4) {
1949                                                                 if(ed4->v1==evl->v4) ed4->f= 1; 
1950                                                                 else ed4->f= 2;
1951                                                         }
1952                                                 }
1953                                         }
1954                                 }
1955                                 if(direct) evl= evl->next;
1956                                 else evl= evl->prev;
1957                         }
1958                         direct= 1-direct;
1959                 }
1960         }
1961
1962         recalc_editnormals();
1963         
1964         makeDispList(G.obedit);
1965         
1966         waitcursor(0);
1967 }
1968
1969 static EditVert *findnearestvert(short sel)
1970 {
1971         /* als sel==1 krijgen vertices met flag==1 een nadeel */
1972         EditVert *eve,*act=0;
1973         static EditVert *acto=0;
1974         short dist=100,temp,mval[2];
1975
1976         if(G.edve.first==0) return 0;
1977
1978         /* projektie doen */
1979         calc_meshverts_ext();   /* drawobject.c */
1980         
1981         /* er wordt geteld van acto->next tot last en van first tot acto */
1982         /* bestaat acto ? */
1983         eve= G.edve.first;
1984         while(eve) {
1985                 if(eve==acto) break;
1986                 eve= eve->next;
1987         }
1988         if(eve==0) acto= G.edve.first;
1989
1990         if(acto==0) return 0;
1991
1992         /* is er een aangegeven vertex? deel 1 */
1993         getmouseco_areawin(mval);
1994         eve= acto->next;
1995         while(eve) {
1996                 if(eve->h==0) {
1997                         temp= abs(mval[0]- eve->xs)+ abs(mval[1]- eve->ys);
1998                         if( (eve->f & 1)==sel ) temp+=5;
1999                         if(temp<dist) {
2000                                 act= eve;
2001                                 dist= temp;
2002                                 if(dist<4) break;
2003                         }
2004                 }
2005                 eve= eve->next;
2006         }
2007         /* is er een aangegeven vertex? deel 2 */
2008         if(dist>3) {
2009                 eve= G.edve.first;
2010                 while(eve) {
2011                         if(eve->h==0) {
2012                                 temp= abs(mval[0]- eve->xs)+ abs(mval[1]- eve->ys);
2013                                 if( (eve->f & 1)==sel ) temp+=5;
2014                                 if(temp<dist) {
2015                                         act= eve;
2016                                         if(temp<4) break;
2017                                         dist= temp;
2018                                 }
2019                                 if(eve== acto) break;
2020                         }
2021                         eve= eve->next;
2022                 }
2023         }
2024
2025         acto= act;
2026         return act;
2027 }
2028
2029 static void tekenvertices_special(int mode, EditVert *act)
2030 {
2031         /* voor speciale gevallen:
2032          * mode 0: deselect geselecteerde, teken ze,  behalve act
2033          * mode 1: teken alleen act
2034          */
2035         ScrArea *tempsa, *sa;
2036         View3D *vd;
2037         EditVert *eve;
2038         float mat[4][4];
2039         int doit=0;
2040         
2041         /* eerst testen of er wel special vertices zijn */
2042         
2043         eve= (EditVert *)G.edve.first;
2044         while(eve) {
2045                 eve->f1= 0;
2046                 if(eve->h==0) {
2047                         if(mode==0) {
2048                                 if(eve!=act && eve->f & 1) {
2049                                         doit= 1;
2050                                         eve->f1= 1;
2051                                         eve->f -= 1;
2052                                 }
2053                         }
2054                         else if(mode==1) {
2055                                 if(eve==act) eve->f1= 1;
2056                                 doit= 1;
2057                         }
2058                 }
2059                 eve= eve->next;
2060         }
2061         if(doit==0) return;
2062         
2063         if(G.f & (G_FACESELECT+G_DRAWFACES)) {
2064                 scrarea_queue_winredraw(curarea);
2065                 return;
2066         }
2067         
2068         if(G.zbuf) glDisable(GL_DEPTH_TEST);
2069         
2070         glDrawBuffer(GL_FRONT);
2071
2072         /* alle views aflopen */
2073         tempsa= curarea;
2074         sa= G.curscreen->areabase.first;
2075         while(sa) {
2076                 if(sa->spacetype==SPACE_VIEW3D) {
2077                         vd= sa->spacedata.first;
2078                         if(G.obedit->lay & vd->lay) {
2079                                 areawinset(sa->win);
2080                                 mymultmatrix(G.obedit->obmat);
2081
2082                                 MTC_Mat4SwapMat4(G.vd->persmat, mat);
2083                                 mygetsingmatrix(G.vd->persmat);
2084                         
2085                                 tekenvertices(0);
2086                                 tekenvertices(1);
2087                                 
2088                                 MTC_Mat4SwapMat4(G.vd->persmat, mat);
2089
2090                                 sa->win_swap= WIN_FRONT_OK;
2091                                 
2092                                 myloadmatrix(G.vd->viewmat);
2093                         }
2094                 }
2095                 sa= sa->next;
2096         }
2097         if(curarea!=tempsa) areawinset(tempsa->win);
2098         
2099         glDrawBuffer(GL_BACK);
2100         if(G.zbuf) glEnable(GL_DEPTH_TEST);
2101 }
2102
2103 void mouse_mesh(void)
2104 {
2105         EditVert *act=0;
2106
2107         act= findnearestvert(1);
2108         if(act) {
2109                 
2110                 if((G.qual & LR_SHIFTKEY)==0) {
2111                         tekenvertices_special(0, act);
2112                 }
2113                 if( (act->f & 1)==0) act->f+= 1;
2114                 else if(G.qual & LR_SHIFTKEY) act->f-= 1;
2115
2116                 tekenvertices_special(1, act);
2117                 countall();
2118         }
2119
2120         rightmouse_transform();
2121 }
2122
2123 static void selectconnectedAll(void)
2124 {
2125         EditVert *v1,*v2;
2126         EditEdge *eed;
2127         short flag=1,toggle=0;
2128
2129         if(G.eded.first==0) return;
2130
2131         while(flag==1) {
2132                 flag= 0;
2133                 toggle++;
2134                 if(toggle & 1) eed= G.eded.first;
2135                 else eed= G.eded.last;
2136                 while(eed) {
2137                         v1= eed->v1;
2138                         v2= eed->v2;
2139                         if(eed->h==0) {
2140                                 if(v1->f & 1) {
2141                                         if( (v2->f & 1)==0 ) {
2142                                                 v2->f |= 1;
2143                                                 flag= 1;
2144                                         }
2145                                 }
2146                                 else if(v2->f & 1) {
2147                                         if( (v1->f & 1)==0 ) {
2148                                                 v1->f |= 1;
2149                                                 flag= 1;
2150                                         }
2151                                 }
2152                         }
2153                         if(toggle & 1) eed= eed->next;
2154                         else eed= eed->prev;
2155                 }
2156         }
2157         countall();
2158
2159         tekenvertices_ext(1);
2160
2161 }
2162
2163
2164 void selectconnected_mesh(void)
2165 {
2166         EditVert *eve,*v1,*v2,*act= 0;
2167         EditEdge *eed;
2168         short flag=1,sel,toggle=0;
2169
2170         if(G.eded.first==0) return;
2171
2172         if(G.qual & LR_CTRLKEY) {
2173                 selectconnectedAll();
2174                 return;
2175         }
2176
2177         sel= 3;
2178         if(G.qual & LR_SHIFTKEY) sel=2;
2179
2180         act= findnearestvert(sel-2);
2181         if(act==0) {
2182                 error(" Nothing indicated ");
2183                 return;
2184         }
2185
2186         /* testflaggen wissen */
2187         eve= G.edve.first;
2188         while(eve) {
2189                 eve->f&= ~2;
2190                 eve= eve->next;
2191         }
2192         act->f= (act->f & ~3) | sel;
2193
2194         while(flag==1) {
2195                 flag= 0;
2196                 toggle++;
2197                 if(toggle & 1) eed= G.eded.first;
2198                 else eed= G.eded.last;
2199                 while(eed) {
2200                         v1= eed->v1;
2201                         v2= eed->v2;
2202                         if(eed->h==0) {
2203                                 if(v1->f & 2) {
2204                                         if( (v2->f & 2)==0 ) {
2205                                                 v2->f= (v2->f & ~3) | sel;
2206                                                 flag= 1;
2207                                         }
2208                                 }
2209                                 else if(v2->f & 2) {
2210                                         if( (v1->f & 2)==0 ) {
2211                                                 v1->f= (v1->f & ~3) | sel;
2212                                                 flag= 1;
2213                                         }
2214                                 }
2215                         }
2216                         if(toggle & 1) eed= eed->next;
2217                         else eed= eed->prev;
2218                 }
2219         }
2220         countall();
2221         
2222         tekenvertices_ext( sel==3 );
2223 }
2224
2225
2226 short extrudeflag(short flag,short type)
2227 {
2228         /* als type=1 worden oude extrudevlakken verwijderd (ivm spin etc) */
2229         /* alle verts met (flag & 'flag') extrude */
2230         /* van oude wordt flag 'flag' gewist, van nieuwe gezet */
2231
2232         EditVert *eve, *v1, *v2, *v3, *v4, *nextve;
2233         EditEdge *eed, *e1, *e2, *e3, *e4, *nexted;
2234         EditVlak *evl, *nextvl;
2235         short sel=0, deloud= 0;
2236
2237         if(G.obedit==0 || get_mesh(G.obedit)==0) return 0;
2238
2239         /* de vert flag f1 wissen, hiermee test op losse geselecteerde vert */
2240         eve= G.edve.first;
2241         while(eve) {
2242                 if(eve->f & flag) eve->f1= 1;
2243                 else eve->f1= 0;
2244                 eve= eve->next;
2245         }
2246         /* de edges tellerflag wissen, als selected op 1 zetten */
2247         eed= G.eded.first;
2248         while(eed) {
2249                 if( (eed->v1->f & flag) && (eed->v2->f & flag) ) {
2250                         eed->f= 1;
2251                         eed->v1->f1= 0;
2252                         eed->v2->f1= 0;
2253                 }
2254                 else eed->f= 0;
2255                 
2256                 eed->f1= 1;             /* aangeven is 'oude' edge (er worden in deze routine nieuwe gemaakt */
2257                 
2258                 eed= eed->next;
2259         }
2260
2261
2262         /* in alle vlak sel een dupl.flag zetten en bijhorende edgeflags ophogen */
2263
2264         evl= G.edvl.first;
2265         while(evl) {
2266                 evl->f= 0;
2267                 
2268                 if(vlakselectedAND(evl, flag)) {
2269                         e1= evl->e1;
2270                         e2= evl->e2;
2271                         e3= evl->e3;
2272                         e4= evl->e4;
2273
2274                         if(e1->f < 3) e1->f++;
2275                         if(e2->f < 3) e2->f++;
2276                         if(e3->f < 3) e3->f++;
2277                         if(e4 && e4->f < 3) e4->f++;
2278                         evl->f= 1;
2279                 }
2280                 else if(vlakselectedOR(evl, flag)) {
2281                         e1= evl->e1;
2282                         e2= evl->e2;
2283                         e3= evl->e3;
2284                         e4= evl->e4;
2285                         
2286                         if( (e1->v1->f & flag) && (e1->v2->f & flag) ) e1->f1= 2;
2287                         if( (e2->v1->f & flag) && (e2->v2->f & flag) ) e2->f1= 2;
2288                         if( (e3->v1->f & flag) && (e3->v2->f & flag) ) e3->f1= 2;
2289                         if( e4 && (e4->v1->f & flag) && (e4->v2->f & flag) ) e4->f1= 2;
2290                 }
2291                 
2292                 evl= evl->next;
2293         }
2294
2295         /* set direction of edges */
2296         evl= G.edvl.first;
2297         while(evl) {
2298                 if(evl->f== 0) {
2299                         if(evl->e1->f==2) {
2300                                 if(evl->e1->v1 == evl->v1) evl->e1->dir= 0;
2301                                 else evl->e1->dir= 1;
2302                         }
2303                         if(evl->e2->f==2) {
2304                                 if(evl->e2->v1 == evl->v2) evl->e2->dir= 0;
2305                                 else evl->e2->dir= 1;
2306                         }
2307                         if(evl->e3->f==2) {
2308                                 if(evl->e3->v1 == evl->v3) evl->e3->dir= 0;
2309                                 else evl->e3->dir= 1;
2310                         }
2311                         if(evl->e4 && evl->e4->f==2) {
2312                                 if(evl->e4->v1 == evl->v4) evl->e4->dir= 0;
2313                                 else evl->e4->dir= 1;
2314                         }
2315                 }
2316                 evl= evl->next;
2317         }       
2318
2319
2320         /* de stand van zaken nu:
2321                 eve->f1==1: losse selected vertex 
2322
2323                 eed->f==0 : edge niet selected, geen extrude
2324                 eed->f==1 : edge selected, komt niet in vlak voor, extrude
2325                 eed->f==2 : edge selected, komt 1 keer in vlak voor, extrude
2326                 eed->f==3 : edge selected, komt in meer vlakken voor, geen extrude
2327                 
2328                 eed->f1==0: nieuwe edge
2329                 eed->f1==1: edge selected,  komt in selected vlak voor,  als f==3: remove
2330                 eed->f1==2: edge selected, komt in NIET selected vlak voor
2331                                         
2332                                         
2333                 evl->f==1 : vlak dupliceren
2334         */
2335
2336         /* alle geselecteerde vertices kopieeren, */
2337         /* de pointer naar nieuwe vert in oude struct schrijven op eve->vn */
2338         eve= G.edve.last;
2339         while(eve) {
2340                 eve->f&= ~128;  /* wissen voor test later op losse verts */
2341                 if(eve->f & flag) {
2342                         sel= 1;
2343                         v1= addvertlist(0);
2344                         
2345                         VECCOPY(v1->co, eve->co);
2346                         v1->f= eve->f;
2347                         eve->f-= flag;
2348                         eve->vn= v1;
2349                 }
2350                 else eve->vn= 0;
2351                 eve= eve->prev;
2352         }
2353
2354         if(sel==0) return 0;
2355
2356         /* alle edges met eed->f==1 of eed->f==2 worden vlakken */
2357         /* als deloud==1 worden edges eed->f>2 verwijderd */
2358         eed= G.eded.last;
2359         while(eed) {
2360                 nexted= eed->prev;
2361                 if( eed->f<3) {
2362                         eed->v1->f|=128;  /* =geen losse vert! */
2363                         eed->v2->f|=128;
2364                 }
2365                 if( (eed->f==1 || eed->f==2) ) {
2366                         if(eed->f1==2) deloud=1;
2367                         
2368                         /* that dir thing does work somewhat... */
2369                         
2370                         if(eed->dir==1) addvlaklist(eed->v1, eed->v2, eed->v2->vn, eed->v1->vn, NULL);
2371                         else addvlaklist(eed->v2, eed->v1, eed->v1->vn, eed->v2->vn, NULL);
2372                 }
2373
2374                 eed= nexted;
2375         }
2376         if(deloud) {
2377                 eed= G.eded.first;
2378                 while(eed) {
2379                         nexted= eed->next;
2380                         if(eed->f==3 && eed->f1==1) {
2381                                 remedge(eed);
2382                                 free(eed);
2383                         }
2384                         eed= nexted;
2385                 }
2386         }
2387         /* de vlakken dupliceren, eventueel oude verwijderen  */
2388         evl= G.edvl.first;
2389         while(evl) {
2390                 nextvl= evl->next;
2391                 if(evl->f & 1) {
2392                 
2393                         v1= evl->v1->vn;
2394                         v2= evl->v2->vn;
2395                         v3= evl->v3->vn;
2396                         if(evl->v4) v4= evl->v4->vn; else v4= 0;
2397                         
2398                         addvlaklist(v1, v2, v3, v4, evl);
2399                         
2400                         if(deloud) {
2401                                 BLI_remlink(&G.edvl, evl);
2402                                 freevlak(evl);
2403                         }
2404                         
2405                 }
2406                 evl= nextvl;
2407         }
2408         /* alle verts met eve->vn!=0 
2409                 als eve->f1==1: edge maken
2410                 als flag!=128 :als deloud==1:  verwijderen
2411         */
2412         eve= G.edve.last;
2413         while(eve) {
2414                 nextve= eve->prev;
2415                 if(eve->vn) {
2416                         if(eve->f1==1) addedgelist(eve,eve->vn);
2417                         else if( (eve->f & 128)==0) {
2418                                 if(deloud) {
2419                                         BLI_remlink(&G.edve,eve);
2420 //                                      free(eve);
2421                                         free_editvert(eve);
2422                                         eve= NULL;
2423                                 }
2424                         }
2425                 }
2426                 if(eve) eve->f&= ~128;
2427                 
2428                 eve= nextve;
2429         }
2430
2431         /* debug temp: testen op consistente:
2432         evl= G.edvl.first;
2433         while(evl) {
2434                 e1= findedgelist(evl->v1, evl->v2);
2435                 e2= findedgelist(evl->v2, evl->v3);
2436                 e3= findedgelist(evl->v3, evl->v1);
2437                 if(e1==0 || e2==0 || e3==0) {
2438                         error("edge not in edgelist");
2439                         break;
2440                 } 
2441                 evl= evl->next;
2442         }
2443         */
2444
2445         return 1;
2446 }
2447
2448 void rotateflag(short flag, float *cent, float rotmat[][3])
2449 {
2450         /* alle verts met (flag & 'flag') rotate */
2451
2452         EditVert *eve;
2453
2454         eve= G.edve.first;
2455         while(eve) {
2456                 if(eve->f & flag) {
2457                         eve->co[0]-=cent[0];
2458                         eve->co[1]-=cent[1];
2459                         eve->co[2]-=cent[2];
2460                         Mat3MulVecfl(rotmat,eve->co);
2461                         eve->co[0]+=cent[0];
2462                         eve->co[1]+=cent[1];
2463                         eve->co[2]+=cent[2];
2464                 }
2465                 eve= eve->next;
2466         }
2467 }
2468
2469 void translateflag(short flag, float *vec)
2470 {
2471         /* alle verts met (flag & 'flag') translate */
2472
2473         EditVert *eve;
2474
2475         eve= G.edve.first;
2476         while(eve) {
2477                 if(eve->f & flag) {
2478                         eve->co[0]+=vec[0];
2479                         eve->co[1]+=vec[1];
2480                         eve->co[2]+=vec[2];
2481                 }
2482                 eve= eve->next;
2483         }
2484 }
2485
2486 short removedoublesflag(short flag, float limit)                /* return aantal */
2487 {
2488         /* alle verts met (flag & 'flag') worden getest */
2489         EditVert *eve, *v1, *nextve;
2490         EditEdge *eed, *e1, *nexted;
2491         EditVlak *evl, *nextvl;
2492         struct xvertsort *sortblock, *sb, *sb1;
2493         struct vlaksort *vlsortblock, *vsb, *vsb1;
2494         float dist;
2495         int a, b, test, aantal;
2496
2497         /* flag 128 wordt gewist, aantal tellen */
2498         eve= G.edve.first;
2499         aantal= 0;
2500         while(eve) {
2501                 eve->f&= ~128;
2502                 if(eve->f & flag) aantal++;
2503                 eve= eve->next;
2504         }
2505         if(aantal==0) return 0;
2506
2507         /* geheugen reserveren en qsorten */
2508         sb= sortblock= (struct xvertsort *)MEM_mallocN(sizeof(struct xvertsort)*aantal,"sortremovedoub");
2509         eve= G.edve.first;
2510         while(eve) {
2511                 if(eve->f & flag) {
2512                         sb->x= eve->co[0]+eve->co[1]+eve->co[2];
2513                         sb->v1= eve;
2514                         sb++;
2515                 }
2516                 eve= eve->next;
2517         }
2518         qsort(sortblock, aantal, sizeof(struct xvertsort), vergxco);
2519
2520         /* testen op doubles */
2521         sb= sortblock;
2522         for(a=0; a<aantal; a++) {
2523                 eve= sb->v1;
2524                 if( (eve->f & 128)==0 ) {
2525                         sb1= sb+1;
2526                         for(b=a+1; b<aantal; b++) {
2527                                 /* eerste test: simpel dist */
2528                                 dist= sb1->x - sb->x;
2529                                 if(dist > limit) break;
2530                                 
2531                                 /* tweede test: is vertex toegestaan */
2532                                 v1= sb1->v1;
2533                                 if( (v1->f & 128)==0 ) {
2534                                         
2535                                         dist= fabs(v1->co[0]-eve->co[0]);
2536                                         if(dist<=limit) {
2537                                                 dist= fabs(v1->co[1]-eve->co[1]);
2538                                                 if(dist<=limit) {
2539                                                         dist= fabs(v1->co[2]-eve->co[2]);
2540                                                         if(dist<=limit) {
2541                                                                 v1->f|= 128;
2542                                                                 v1->vn= eve;
2543                                                         }
2544                                                 }
2545                                         }
2546                                 }
2547                                 sb1++;
2548                         }
2549                 }
2550                 sb++;
2551         }
2552         MEM_freeN(sortblock);
2553
2554         /* edges testen en opnieuw invoegen */
2555         eed= G.eded.first;
2556         while(eed) {
2557                 eed->f= 0;
2558                 eed= eed->next;
2559         }
2560         eed= G.eded.last;
2561         while(eed) {
2562                 nexted= eed->prev;
2563
2564                 if(eed->f==0) {
2565                         if( (eed->v1->f & 128) || (eed->v2->f & 128) ) {
2566                                 remedge(eed);
2567
2568                                 if(eed->v1->f & 128) eed->v1= eed->v1->vn;
2569                                 if(eed->v2->f & 128) eed->v2= eed->v2->vn;
2570
2571                                 e1= addedgelist(eed->v1,eed->v2);
2572                                 
2573                                 if(e1) e1->f= 1;
2574                                 if(e1!=eed) free(eed);
2575                         }
2576                 }
2577                 eed= nexted;
2578         }
2579
2580         /* eerst aantal testvlakken tellen */
2581         evl= (struct EditVlak *)G.edvl.first;
2582         aantal= 0;
2583         while(evl) {
2584                 evl->f= 0;
2585                 if(evl->v1->f & 128) evl->f= 1;
2586                 else if(evl->v2->f & 128) evl->f= 1;
2587                 else if(evl->v3->f & 128) evl->f= 1;
2588                 else if(evl->v4 && (evl->v4->f & 128)) evl->f= 1;
2589                 
2590                 if(evl->f==1) aantal++;
2591                 evl= evl->next;
2592         }
2593
2594         /* vlakken testen op dubbele punten en eventueel verwijderen */
2595         evl= (struct EditVlak *)G.edvl.first;
2596         while(evl) {
2597                 nextvl= evl->next;
2598                 if(evl->f==1) {
2599                         
2600                         if(evl->v1->f & 128) evl->v1= evl->v1->vn;
2601                         if(evl->v2->f & 128) evl->v2= evl->v2->vn;
2602                         if(evl->v3->f & 128) evl->v3= evl->v3->vn;
2603                         if(evl->v4 && (evl->v4->f & 128)) evl->v4= evl->v4->vn;
2604                 
2605                         test= 0;
2606                         if(evl->v1==evl->v2) test+=1;
2607                         if(evl->v2==evl->v3) test+=2;
2608                         if(evl->v3==evl->v1) test+=4;
2609                         if(evl->v4==evl->v1) test+=8;
2610                         if(evl->v3==evl->v4) test+=16;
2611                         if(evl->v2==evl->v4) test+=32;
2612                         
2613                         if(test) {
2614                                 if(evl->v4) {
2615                                         if(test==1 || test==2) {
2616                                                 evl->v2= evl->v3;
2617                                                 evl->v3= evl->v4;
2618                                                 evl->v4= 0;
2619                                                 test= 0;
2620                                         }
2621                                         else if(test==8 || test==16) {
2622                                                 evl->v4= 0;
2623                                                 test= 0;
2624                                         }
2625                                         else {
2626                                                 BLI_remlink(&G.edvl, evl);
2627                                                 freevlak(evl);
2628                                                 aantal--;
2629                                         }
2630                                 }
2631                                 else {
2632                                         BLI_remlink(&G.edvl, evl);
2633                                         freevlak(evl);
2634                                         aantal--;
2635                                 }
2636                         }
2637                         
2638                         if(test==0) {
2639                                 /* edgepointers goedzetten */
2640                                 evl->e1= findedgelist(evl->v1, evl->v2);
2641                                 evl->e2= findedgelist(evl->v2, evl->v3);
2642                                 if(evl->v4==0) {
2643                                         evl->e3= findedgelist(evl->v3, evl->v1);
2644                                         evl->e4= 0;
2645                                 }
2646                                 else {
2647                                         evl->e3= findedgelist(evl->v3, evl->v4);
2648                                         evl->e4= findedgelist(evl->v4, evl->v1);
2649                                 }
2650                         }
2651                 }
2652                 evl= nextvl;
2653         }
2654
2655         /* dubbele vlakken: sortblock */
2656         /* opnieuw tellen, nu alle selected vlakken */
2657         aantal= 0;
2658         evl= G.edvl.first;
2659         while(evl) {
2660                 evl->f= 0;
2661                 if(vlakselectedAND(evl, 1)) {
2662                         evl->f= 1;
2663                         aantal++;
2664                 }
2665                 evl= evl->next;
2666         }
2667
2668         if(aantal) {
2669                 /* dubbele vlakken: sortblock */
2670                 vsb= vlsortblock= MEM_mallocN(sizeof(struct vlaksort)*aantal, "sortremovedoub");
2671                 evl= G.edvl.first;
2672                 while(evl) {
2673                         if(evl->f & 1) {
2674                                 if(evl->v4) vsb->x= (long) MIN4( (long)evl->v1, (long)evl->v2, (long)evl->v3, (long)evl->v4);
2675                                 else vsb->x= (long) MIN3( (long)evl->v1, (long)evl->v2, (long)evl->v3);
2676
2677                                 vsb->evl= evl;
2678                                 vsb++;
2679                         }
2680                         evl= evl->next;
2681                 }
2682                 
2683                 qsort(vlsortblock, aantal, sizeof(struct vlaksort), vergvlak);
2684                         
2685                 vsb= vlsortblock;
2686                 for(a=0; a<aantal; a++) {
2687                         evl= vsb->evl;
2688                         if( (evl->f & 128)==0 ) {
2689                                 vsb1= vsb+1;
2690
2691                                 for(b=a+1; b<aantal; b++) {
2692                                 
2693                                         /* eerste test: zelfde poin? */
2694                                         if(vsb->x != vsb1->x) break;
2695                                         
2696                                         /* tweede test: is test toegestaan */
2697                                         evl= vsb1->evl;
2698                                         if( (evl->f & 128)==0 ) {
2699                                                 if( comparevlak(evl, vsb->evl)) evl->f |= 128;
2700                                                 
2701                                         }
2702                                         vsb1++;
2703                                 }
2704                         }
2705                         vsb++;
2706                 }
2707                 
2708                 MEM_freeN(vlsortblock);
2709                 
2710                 /* dubbele vlakken eruit */
2711                 evl= (struct EditVlak *)G.edvl.first;
2712                 while(evl) {
2713                         nextvl= evl->next;
2714                         if(evl->f & 128) {
2715                                 BLI_remlink(&G.edvl, evl);
2716                                 freevlak(evl);
2717                         }
2718                         evl= nextvl;
2719                 }
2720         }
2721         
2722         /* dubbele vertices eruit */
2723         a= 0;
2724         eve= (struct EditVert *)G.edve.first;
2725         while(eve) {
2726                 nextve= eve->next;
2727                 if(eve->f & flag) {
2728                         if(eve->f & 128) {
2729                                 a++;
2730                                 BLI_remlink(&G.edve, eve);
2731                                 
2732 //                              free(eve);
2733                                 free_editvert(eve);
2734                         }
2735                 }
2736                 eve= nextve;
2737         }
2738         return a;       /* aantal */
2739 }
2740
2741 void xsortvert_flag(int flag)
2742 //short flag;
2743 {
2744         /* alle verts met (flag & 'flag') worden gesorteerd */
2745         EditVert *eve;
2746         struct xvertsort *sortblock, *sb;
2747         ListBase tbase;
2748         int aantal;
2749         
2750         /* aantal tellen */
2751         eve= G.edve.first;
2752         aantal= 0;
2753         while(eve) {
2754                 if(eve->f & flag) aantal++;
2755                 eve= eve->next;
2756         }
2757         if(aantal==0) return;
2758
2759         /* geheugen reserveren en qsorten */
2760         sb= sortblock= (struct xvertsort *)MEM_mallocN(sizeof(struct xvertsort)*aantal,"sortremovedoub");
2761         eve= G.edve.first;
2762         while(eve) {
2763                 if(eve->f & flag) {
2764                         sb->x= eve->xs;
2765                         sb->v1= eve;
2766                         sb++;
2767                 }
2768                 eve= eve->next;
2769         }
2770         qsort(sortblock, aantal, sizeof(struct xvertsort), vergxco);
2771         
2772         /* tijdelijke listbase maken */
2773         tbase.first= tbase.last= 0;
2774         sb= sortblock;
2775         while(aantal--) {
2776                 eve= sb->v1;
2777                 BLI_remlink(&G.edve, eve);
2778                 BLI_addtail(&tbase, eve);
2779                 sb++;
2780         }
2781         
2782         addlisttolist(&G.edve, &tbase);
2783         
2784         MEM_freeN(sortblock);
2785 }
2786
2787
2788 void hashvert_flag(int flag)
2789 {
2790         EditVert *eve;
2791         struct xvertsort *sortblock, *sb, onth, *newsort;
2792         ListBase tbase;
2793         int aantal, a, b;
2794         
2795         /* aantal tellen */
2796         eve= G.edve.first;
2797         aantal= 0;
2798         while(eve) {
2799                 if(eve->f & flag) aantal++;
2800                 eve= eve->next;
2801         }
2802         if(aantal==0) return;
2803
2804         /* geheugen reserveren */
2805         sb= sortblock= (struct xvertsort *)MEM_mallocN(sizeof(struct xvertsort)*aantal,"sortremovedoub");
2806         eve= G.edve.first;
2807         while(eve) {
2808                 if(eve->f & flag) {
2809                         sb->v1= eve;
2810                         sb++;
2811                 }
2812                 eve= eve->next;
2813         }
2814
2815         BLI_srand(1);
2816         
2817         sb= sortblock;
2818         for(a=0; a<aantal; a++, sb++) {
2819                 b= aantal*BLI_drand();
2820                 if(b>=0 && b<aantal) {
2821                         newsort= sortblock+b;
2822                         onth= *sb;
2823                         *sb= *newsort;
2824                         *newsort= onth;
2825                 }
2826         }
2827
2828         /* tijdelijke listbase maken */
2829         tbase.first= tbase.last= 0;
2830         sb= sortblock;
2831         while(aantal--) {
2832                 eve= sb->v1;
2833                 BLI_remlink(&G.edve, eve);
2834                 BLI_addtail(&tbase, eve);
2835                 sb++;
2836         }
2837         
2838         addlisttolist(&G.edve, &tbase);
2839         
2840         MEM_freeN(sortblock);
2841 }
2842
2843 static unsigned int cpack_half(unsigned int col1, unsigned int col2)
2844 {
2845         char *cp1, *cp2, *cp;
2846         unsigned int col=0;
2847         
2848         cp1= (char *)&col1;
2849         cp2= (char *)&col2;
2850         cp=  (char *)&col;
2851         
2852         cp[0]= (cp1[0]+cp2[0])>>1;
2853         cp[1]= (cp1[1]+cp2[1])>>1;
2854         cp[2]= (cp1[2]+cp2[2])>>1;
2855         cp[3]= (cp1[3]+cp2[3])>>1;
2856         
2857         return col;
2858 }
2859
2860
2861 static void uv_half(float *uv, float *uv1, float *uv2)
2862 {
2863         uv[0]= (uv1[0]+uv2[0])/2.0;
2864         uv[1]= (uv1[1]+uv2[1])/2.0;
2865         
2866 }
2867
2868 static void uv_quart(float *uv, float *uv1)
2869 {
2870         uv[0]= (uv1[0]+uv1[2]+uv1[4]+uv1[6])/4.0;
2871         uv[1]= (uv1[1]+uv1[3]+uv1[5]+uv1[7])/4.0;
2872 }
2873
2874 static void set_wuv(int tot, EditVlak *evl, int v1, int v2, int v3, int v4)
2875 {
2876         /* deze vreemde fie alleen bij de subdiv te gebruiken, de 'w' in de naam slaat nergens op! */
2877         float *uv, uvo[4][2];
2878         unsigned int *col, colo[4], col1, col2;
2879         int a, v;
2880         
2881         memcpy(uvo, evl->uv, sizeof(uvo));
2882         uv= evl->uv[0];
2883
2884         memcpy(colo, evl->col, sizeof(colo));
2885         col= evl->col;
2886         
2887         if(tot==4) {
2888                 for(a=0; a<4; a++, uv+=2, col++) {
2889                         if(a==0) v= v1;
2890                         else if(a==1) v= v2;
2891                         else if(a==2) v= v3;
2892                         else v= v4;
2893                         
2894                         if(a==3 && v4==0) break;
2895                         
2896                         if(v<=4) {
2897                                 uv[0]= uvo[v-1][0];
2898                                 uv[1]= uvo[v-1][1];
2899                                 *col= colo[v-1];
2900                         }
2901                         else if(v==8) {
2902                                 uv_half(uv, uvo[3], uvo[0]);
2903                                 *col= cpack_half(colo[3], colo[0]);
2904                         }
2905                         else if(v==9) {
2906                                 uv_quart(uv, uvo[0]);
2907                                 col1= cpack_half(colo[1], colo[0]);
2908                                 col2= cpack_half(colo[2], colo[3]);
2909                                 *col= cpack_half(col1, col2);
2910                         }
2911                         else {
2912                                 uv_half(uv, uvo[v-5], uvo[v-4]);
2913                                 *col= cpack_half(colo[v-5], colo[v-4]);
2914                         }
2915                 }
2916         }
2917         else {
2918                 for(a=0; a<3; a++, uv+=2, col++) {
2919                         if(a==0) v= v1;
2920                         else if(a==1) v= v2;
2921                         else v= v3;
2922                 
2923                         if(v<=4) {
2924                                 uv[0]= uvo[v-1][0];
2925                                 uv[1]= uvo[v-1][1];
2926                                 *col= colo[v-1];
2927                         }
2928                         else if(v==7) {
2929                                 uv_half(uv, uvo[2], uvo[0]);
2930                                 *col= cpack_half(colo[2], colo[0]);
2931                         }
2932                         else {
2933                                 uv_half(uv, uvo[v-5], uvo[v-4]);
2934                                 *col= cpack_half(colo[v-5], colo[v-4]);
2935                         }
2936                 }
2937         }
2938 }
2939
2940 static EditVert *vert_from_number(EditVlak *evl, int nr)
2941 {
2942         switch(nr) {
2943         case 0:
2944                 return 0;
2945         case 1:
2946                 return evl->v1;
2947         case 2:
2948                 return evl->v2;
2949         case 3:
2950                 return evl->v3;
2951         case 4:
2952                 return evl->v4;
2953         case 5:
2954                 return evl->e1->vn;
2955         case 6:
2956                 return evl->e2->vn;
2957         case 7:
2958                 return evl->e3->vn;
2959         case 8:
2960                 return evl->e4->vn;
2961         }
2962         
2963         return NULL;
2964 }
2965
2966 static void addvlak_subdiv(EditVlak *evl, int val1, int val2, int val3, int val4, EditVert *eve)
2967 {
2968         EditVlak *w;
2969         EditVert *v1, *v2, *v3, *v4;
2970         
2971         if(val1==9) v1= eve;
2972         else v1= vert_from_number(evl, val1);
2973         
2974         if(val2==9) v2= eve;
2975         else v2= vert_from_number(evl, val2);
2976
2977         if(val3==9) v3= eve;
2978         else v3= vert_from_number(evl, val3);
2979
2980         if(val4==9) v4= eve;
2981         else v4= vert_from_number(evl, val4);
2982         
2983         w= addvlaklist(v1, v2, v3, v4, evl);
2984
2985         if(w) {
2986                 if(evl->v4) set_wuv(4, w, val1, val2, val3, val4);
2987                 else set_wuv(3, w, val1, val2, val3, val4);
2988         }
2989 }
2990
2991 static float smoothperc= 0.0;
2992
2993 static void smooth_subdiv_vec(float *v1, float *v2, float *n1, float *n2, float *vec)
2994 {
2995         float len, fac, nor[3], nor1[3], nor2[3];
2996         
2997         VecSubf(nor, v1, v2);
2998         len= 0.5*Normalise(nor);
2999
3000         VECCOPY(nor1, n1);
3001         VECCOPY(nor2, n2);
3002
3003         /* cosine angle */
3004         fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
3005         
3006         vec[0]= fac*nor1[0];
3007         vec[1]= fac*nor1[1];
3008         vec[2]= fac*nor1[2];
3009
3010         /* cosine angle */
3011         fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
3012         
3013         vec[0]+= fac*nor2[0];
3014         vec[1]+= fac*nor2[1];
3015         vec[2]+= fac*nor2[2];
3016
3017         vec[0]*= smoothperc*len;
3018         vec[1]*= smoothperc*len;
3019         vec[2]*= smoothperc*len;
3020 }
3021
3022 static void smooth_subdiv_quad(EditVlak *evl, float *vec)
3023 {
3024         
3025         float nor1[3], nor2[3];
3026         float vec1[3], vec2[3];
3027         float cent[3];
3028         
3029         /* vlr->e1->vn is new vertex inbetween v1 / v2 */
3030         
3031         VecMidf(nor1, evl->v1->no, evl->v2->no);
3032         Normalise(nor1);
3033         VecMidf(nor2, evl->v3->no, evl->v4->no);
3034         Normalise(nor2);
3035
3036         smooth_subdiv_vec( evl->e1->vn->co, evl->e3->vn->co, nor1, nor2, vec1);
3037
3038         VecMidf(nor1, evl->v2->no, evl->v3->no);
3039         Normalise(nor1);
3040         VecMidf(nor2, evl->v4->no, evl->v1->no);
3041         Normalise(nor2);
3042
3043         smooth_subdiv_vec( evl->e2->vn->co, evl->e4->vn->co, nor1, nor2, vec2);
3044
3045         VecAddf(vec1, vec1, vec2);
3046
3047         CalcCent4f(cent, evl->v1->co,  evl->v2->co,  evl->v3->co,  evl->v4->co);
3048         VecAddf(vec, cent, vec1);
3049 }
3050
3051 void subdivideflag(int flag, float rad, int beauty)
3052 {
3053         /* divide alle vlakken met (vertflag & flag) */
3054         /* als rad>0.0 zet dan nieuw vert op afstand rad van 0,0,0 */
3055         extern float doublimit;
3056         EditVert *eve;
3057         EditEdge *eed, *e1, *e2, *e3, *e4, *nexted;
3058         EditVlak *evl;
3059         float fac, vec[3], vec1[3], len1, len2, len3;
3060         short test;
3061         
3062         if(beauty & B_SMOOTH) {
3063                 short perc= 100;
3064
3065                 if(button(&perc, 10, 500, "Percentage:")==0) return;
3066                 
3067                 smoothperc= 0.292*perc/100.0;
3068         }
3069
3070         /* edgeflags */
3071         eed= G.eded.first;
3072         while(eed) {
3073                 
3074                 if( (eed->v1->f & flag) && (eed->v2->f & flag) ) eed->f= flag;
3075                 else eed->f= 0;
3076                 
3077                 eed= eed->next;
3078         }
3079         
3080         /* als beauty: opp testen en edgeflags wissen van 'lelijke' edges */
3081         if(beauty & B_BEAUTY) {
3082                 evl= G.edvl.first;
3083                 while(evl) {
3084                         if( vlakselectedAND(evl, flag) ) {
3085                                 if(evl->v4) {
3086                                 
3087                                         /* opp */
3088                                         len1= AreaQ3Dfl(evl->v1->co, evl->v2->co, evl->v3->co, evl->v4->co);
3089                                         if(len1 <= doublimit) {
3090                                                 evl->e1->f = 0;
3091                                                 evl->e2->f = 0;
3092                                                 evl->e3->f = 0;
3093                                                 evl->e4->f = 0;
3094                                         }
3095                                         else {
3096                                                 len1= VecLenf(evl->v1->co, evl->v2->co) + VecLenf(evl->v3->co, evl->v4->co);
3097                                                 len2= VecLenf(evl->v2->co, evl->v3->co) + VecLenf(evl->v1->co, evl->v4->co);
3098                                                 
3099                                                 if(len1 < len2) {
3100                                                         evl->e1->f = 0;
3101                                                         evl->e3->f = 0;
3102                                                 }
3103                                                 else if(len1 > len2) {
3104                                                         evl->e2->f = 0;
3105                                                         evl->e4->f = 0;
3106                                                 }
3107                                         }
3108                                 }
3109                                 else {
3110
3111                                         /* opp */
3112                                         len1= AreaT3Dfl(evl->v1->co, evl->v2->co, evl->v3->co);
3113                                         if(len1 <= doublimit) {
3114                                                 evl->e1->f = 0;
3115                                                 evl->e2->f = 0;
3116                                                 evl->e3->f = 0;
3117                                         }
3118                                         else {
3119         
3120                                                 len1= VecLenf(evl->v1->co, evl->v2->co) ;
3121                                                 len2= VecLenf(evl->v2->co, evl->v3->co) ;
3122                                                 len3= VecLenf(evl->v3->co, evl->v1->co) ;
3123                                                 
3124                                                 if(len1<len2 && len1<len3) {
3125                                                         evl->e1->f = 0;
3126                                                 }
3127                                                 else if(len2<len3 && len2<len1) {
3128                                                         evl->e2->f = 0;
3129                                                 }
3130                                                 else if(len3<len2 && len3<len1) {
3131                                                         evl->e3->f = 0;
3132                                                 }
3133                                         }
3134                                 }
3135                         }
3136                         evl= evl->next;
3137                 }
3138         }
3139
3140         if(beauty & B_SMOOTH) {
3141                 
3142                 vertexnormals(0);               /* no1*/
3143                         
3144         }
3145         
3146         /* nieuw punt maken en in edge wegschrijven, flag wissen! is voor vlakkenmaak stuk nodig */
3147         eed= G.eded.first;
3148         while(eed) {
3149                 if(eed->f & flag) {
3150                         
3151                         vec[0]= (eed->v1->co[0]+eed->v2->co[0])/2.0;
3152                         vec[1]= (eed->v1->co[1]+eed->v2->co[1])/2.0;
3153                         vec[2]= (eed->v1->co[2]+eed->v2->co[2])/2.0;
3154
3155                         if(rad > 0.0) {   /* perf sph */
3156                                 Normalise(vec);
3157                                 vec[0]*= rad;
3158                                 vec[1]*= rad;
3159                                 vec[2]*= rad;
3160                         }
3161                         else if(rad< 0.0) {  /* fract */
3162                                 fac= rad* VecLenf(eed->v1->co, eed->v2->co);
3163                                 vec1[0]= fac*BLI_drand();
3164                                 vec1[1]= fac*BLI_drand();
3165                                 vec1[2]= fac*BLI_drand();
3166                                 VecAddf(vec, vec, vec1);
3167                         }
3168                         
3169                         if(beauty & B_SMOOTH) {
3170                                 smooth_subdiv_vec(eed->v1->co, eed->v2->co, eed->v1->no, eed->v2->no, vec1);
3171                                 VecAddf(vec, vec, vec1);
3172                         }
3173                         
3174                         eed->vn= addvertlist(vec);
3175                         eed->vn->f= eed->v1->f;
3176
3177                 }
3178                 else eed->vn= 0;
3179                 
3180                 eed->f= 0; /* moet! */
3181                 
3182                 eed= eed->next;
3183         }
3184
3185         /* alle vlakken testen op subdiv edges, 8 of 16 gevallen! */
3186
3187         evl= G.edvl.last;
3188         while(evl) {
3189                 if( vlakselectedOR(evl, flag) ) {
3190                         e1= evl->e1;
3191                         e2= evl->e2;
3192                         e3= evl->e3;
3193                         e4= evl->e4;
3194
3195                         test= 0;
3196                         if(e1 && e1->vn) { 
3197                                 test+= 1; 
3198                                 e1->f= 1;
3199                         }
3200                         if(e2 && e2->vn) { 
3201                                 test+= 2; 
3202                                 e2->f= 1;