fix [#25283] Edge length display difficult to read
[blender.git] / source / blender / editors / mesh / editmesh_tools.c
1  /* $Id$
2  *
3  * ***** BEGIN GPL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18  *
19  * The Original Code is Copyright (C) 2004 by Blender Foundation.
20  * All rights reserved.
21  *
22  * The Original Code is: all of this file.
23  *
24  * Contributor(s): Johnny Matthews, Geoffrey Bantle.
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 /*
30
31 editmesh_tool.c: UI called tools for editmesh, geometry changes here, otherwise in mods.c
32
33 */
34
35 #include <stdlib.h>
36 #include <string.h>
37 #include <math.h>
38 #include <float.h>
39
40 #include "BLO_sys_types.h" // for intptr_t support
41
42 #include "DNA_meshdata_types.h"
43 #include "DNA_modifier_types.h"
44 #include "DNA_object_types.h"
45 #include "DNA_scene_types.h"
46 #include "DNA_key_types.h"
47
48 #include "MEM_guardedalloc.h"
49
50 #include "RNA_define.h"
51 #include "RNA_access.h"
52
53 #include "BLI_blenlib.h"
54 #include "BLI_math.h"
55 #include "BLI_editVert.h"
56 #include "BLI_rand.h"
57 #include "BLI_ghash.h"
58 #include "BLI_linklist.h"
59 #include "BLI_heap.h"
60 #include "BLI_scanfill.h"
61
62 #include "BKE_context.h"
63 #include "BKE_depsgraph.h"
64 #include "BKE_global.h"
65 #include "BKE_key.h"
66 #include "BKE_mesh.h"
67 #include "BKE_bmesh.h"
68 #include "BKE_report.h"
69
70
71 #include "WM_api.h"
72 #include "WM_types.h"
73
74 #include "ED_mesh.h"
75 #include "ED_screen.h"
76 #include "ED_transform.h"
77 #include "ED_view3d.h"
78 #include "ED_object.h"
79
80
81 #include "mesh_intern.h"
82
83 /* XXX */
84 static void waitcursor(int UNUSED(val)) {}
85 #define add_numbut(a, b, c, d, e, f, g) {}
86
87 /* XXX */
88
89 /* RNA corner cut enum property - used in multiple files for tools
90  * that need this property for esubdivideflag() */
91 EnumPropertyItem corner_type_items[] = {
92         {SUBDIV_CORNER_PATH,  "PATH", 0, "Path", ""},
93         {SUBDIV_CORNER_INNERVERT,  "INNER_VERTEX", 0, "Inner Vertex", ""},
94         {SUBDIV_CORNER_FAN,  "FAN",  0, "Fan", ""},
95         {0, NULL, 0, NULL, NULL}};
96
97
98 /* local prototypes ---------------*/
99 static void free_tagged_edges_faces(EditMesh *em, EditEdge *eed, EditFace *efa);
100 int EdgeLoopDelete(EditMesh *em, wmOperator *op);
101
102 /********* qsort routines *********/
103
104
105 typedef struct xvertsort {
106         float x;
107         EditVert *v1;
108 } xvertsort;
109
110 static int vergxco(const void *v1, const void *v2)
111 {
112         const xvertsort *x1=v1, *x2=v2;
113
114         if( x1->x > x2->x ) return 1;
115         else if( x1->x < x2->x) return -1;
116         return 0;
117 }
118
119 struct facesort {
120         uintptr_t x;
121         struct EditFace *efa;
122 };
123
124
125 static int vergface(const void *v1, const void *v2)
126 {
127         const struct facesort *x1=v1, *x2=v2;
128
129         if( x1->x > x2->x ) return 1;
130         else if( x1->x < x2->x) return -1;
131         return 0;
132 }
133
134
135 /* *********************************** */
136
137 static void convert_to_triface(EditMesh *em, int direction)
138 {
139         EditFace *efa, *efan, *next;
140         float fac;
141
142         efa= em->faces.last;
143         while(efa) {
144                 next= efa->prev;
145                 if(efa->v4) {
146                         if(efa->f & SELECT) {
147                                 /* choose shortest diagonal for split */
148                                 fac= len_v3v3(efa->v1->co, efa->v3->co) - len_v3v3(efa->v2->co, efa->v4->co);
149                                 /* this makes sure exact squares get split different in both cases */
150                                 if( (direction==0 && fac<FLT_EPSILON) || (direction && fac>0.0f) ) {
151                                         efan= EM_face_from_faces(em, efa, NULL, 0, 1, 2, -1);
152                                         if(efa->f & SELECT) EM_select_face(efan, 1);
153                                         efan= EM_face_from_faces(em, efa, NULL, 0, 2, 3, -1);
154                                         if(efa->f & SELECT) EM_select_face(efan, 1);
155                                 }
156                                 else {
157                                         efan= EM_face_from_faces(em, efa, NULL, 0, 1, 3, -1);
158                                         if(efa->f & SELECT) EM_select_face(efan, 1);
159                                         efan= EM_face_from_faces(em, efa, NULL, 1, 2, 3, -1);
160                                         if(efa->f & SELECT) EM_select_face(efan, 1);
161                                 }
162
163                                 BLI_remlink(&em->faces, efa);
164                                 free_editface(em, efa);
165                         }
166                 }
167                 efa= next;
168         }
169
170         EM_fgon_flags(em);      // redo flags and indices for fgons
171
172
173 }
174
175 int removedoublesflag(EditMesh *em, short flag, short automerge, float limit)           /* return amount */
176 {
177         /*
178                 flag -          Test with vert->flags
179                 automerge -     Alternative operation, merge unselected into selected.
180                                         Used for "Auto Weld" mode. warning.
181                 limit -         Quick manhattan distance between verts.
182         */
183
184         /* all verts with (flag & 'flag') are being evaluated */
185         EditVert *eve, *v1, *nextve;
186         EditEdge *eed, *e1, *nexted;
187         EditFace *efa, *nextvl;
188         xvertsort *sortblock, *sb, *sb1;
189         struct facesort *vlsortblock, *vsb, *vsb1;
190         int a, b, test, amount;
191
192
193         /* flag 128 is cleared, count */
194
195         /* Normal non weld operation */
196         eve= em->verts.first;
197         amount= 0;
198         while(eve) {
199                 eve->f &= ~128;
200                 if(eve->h==0 && (automerge || (eve->f & flag))) amount++;
201                 eve= eve->next;
202         }
203         if(amount==0) return 0;
204
205         /* allocate memory and qsort */
206         sb= sortblock= MEM_mallocN(sizeof(xvertsort)*amount,"sortremovedoub");
207         eve= em->verts.first;
208         while(eve) {
209                 if(eve->h==0 && (automerge || (eve->f & flag))) {
210                         sb->x= eve->co[0]+eve->co[1]+eve->co[2];
211                         sb->v1= eve;
212                         sb++;
213                 }
214                 eve= eve->next;
215         }
216         qsort(sortblock, amount, sizeof(xvertsort), vergxco);
217
218
219         /* test for doubles */
220         sb= sortblock;
221         if (automerge) {
222                 for(a=0; a<amount; a++, sb++) {
223                         eve= sb->v1;
224                         if( (eve->f & 128)==0 ) {
225                                 sb1= sb+1;
226                                 for(b=a+1; b<amount && (eve->f & 128)==0; b++, sb1++) {
227                                         if(sb1->x - sb->x > limit) break;
228
229                                         /* when automarge, only allow unselected->selected */
230                                         v1= sb1->v1;
231                                         if( (v1->f & 128)==0 ) {
232                                                 if ((eve->f & flag)==0 && (v1->f & flag)==1) {
233                                                         if(     (float)fabs(v1->co[0]-eve->co[0])<=limit &&
234                                                                 (float)fabs(v1->co[1]-eve->co[1])<=limit &&
235                                                                 (float)fabs(v1->co[2]-eve->co[2])<=limit)
236                                                         {       /* unique bit */
237                                                                 eve->f|= 128;
238                                                                 eve->tmp.v = v1;
239                                                         }
240                                                 } else if(      (eve->f & flag)==1 && (v1->f & flag)==0 ) {
241                                                         if(     (float)fabs(v1->co[0]-eve->co[0])<=limit &&
242                                                                 (float)fabs(v1->co[1]-eve->co[1])<=limit &&
243                                                                 (float)fabs(v1->co[2]-eve->co[2])<=limit)
244                                                         {       /* unique bit */
245                                                                 v1->f|= 128;
246                                                                 v1->tmp.v = eve;
247                                                         }
248                                                 }
249                                         }
250                                 }
251                         }
252                 }
253         } else {
254                 for(a=0; a<amount; a++, sb++) {
255                         eve= sb->v1;
256                         if( (eve->f & 128)==0 ) {
257                                 sb1= sb+1;
258                                 for(b=a+1; b<amount; b++, sb1++) {
259                                         /* first test: simpel dist */
260                                         if(sb1->x - sb->x > limit) break;
261                                         v1= sb1->v1;
262
263                                         /* second test: is vertex allowed */
264                                         if( (v1->f & 128)==0 ) {
265                                                 if(     (float)fabs(v1->co[0]-eve->co[0])<=limit &&
266                                                         (float)fabs(v1->co[1]-eve->co[1])<=limit &&
267                                                         (float)fabs(v1->co[2]-eve->co[2])<=limit)
268                                                 {
269                                                         v1->f|= 128;
270                                                         v1->tmp.v = eve;
271                                                 }
272                                         }
273                                 }
274                         }
275                 }
276         }
277         MEM_freeN(sortblock);
278
279         if (!automerge)
280                 for(eve = em->verts.first; eve; eve=eve->next)
281                         if((eve->f & flag) && (eve->f & 128))
282                                 EM_data_interp_from_verts(em, eve, eve->tmp.v, eve->tmp.v, 0.5f);
283
284         /* test edges and insert again */
285         eed= em->edges.first;
286         while(eed) {
287                 eed->f2= 0;
288                 eed= eed->next;
289         }
290         eed= em->edges.last;
291         while(eed) {
292                 nexted= eed->prev;
293
294                 if(eed->f2==0) {
295                         if( (eed->v1->f & 128) || (eed->v2->f & 128) ) {
296                                 remedge(em, eed);
297
298                                 if(eed->v1->f & 128) eed->v1 = eed->v1->tmp.v;
299                                 if(eed->v2->f & 128) eed->v2 = eed->v2->tmp.v;
300                                 e1= addedgelist(em, eed->v1, eed->v2, eed);
301
302                                 if(e1) {
303                                         e1->f2= 1;
304                                         if(eed->f & SELECT)
305                                                 e1->f |= SELECT;
306                                 }
307                                 if(e1!=eed) free_editedge(em, eed);
308                         }
309                 }
310                 eed= nexted;
311         }
312
313         /* first count amount of test faces */
314         efa= (struct EditFace *)em->faces.first;
315         amount= 0;
316         while(efa) {
317                 efa->f1= 0;
318                 if(efa->v1->f & 128) efa->f1= 1;
319                 else if(efa->v2->f & 128) efa->f1= 1;
320                 else if(efa->v3->f & 128) efa->f1= 1;
321                 else if(efa->v4 && (efa->v4->f & 128)) efa->f1= 1;
322
323                 if(efa->f1==1) amount++;
324                 efa= efa->next;
325         }
326
327         /* test faces for double vertices, and if needed remove them */
328         efa= (struct EditFace *)em->faces.first;
329         while(efa) {
330                 nextvl= efa->next;
331                 if(efa->f1==1) {
332
333                         if(efa->v1->f & 128) efa->v1= efa->v1->tmp.v;
334                         if(efa->v2->f & 128) efa->v2= efa->v2->tmp.v;
335                         if(efa->v3->f & 128) efa->v3= efa->v3->tmp.v;
336                         if(efa->v4 && (efa->v4->f & 128)) efa->v4= efa->v4->tmp.v;
337
338                         test= 0;
339                         if(efa->v1==efa->v2) test+=1;
340                         if(efa->v2==efa->v3) test+=2;
341                         if(efa->v3==efa->v1) test+=4;
342                         if(efa->v4==efa->v1) test+=8;
343                         if(efa->v3==efa->v4) test+=16;
344                         if(efa->v2==efa->v4) test+=32;
345
346                         if(test) {
347                                 if(efa->v4) {
348                                         if(test==1 || test==2) {
349                                                 efa->v2= efa->v3;
350                                                 efa->v3= efa->v4;
351                                                 efa->v4= 0;
352
353                                                 EM_data_interp_from_faces(em, efa, NULL, efa, 0, 2, 3, 3);
354
355                                                 test= 0;
356                                         }
357                                         else if(test==8 || test==16) {
358                                                 efa->v4= 0;
359                                                 test= 0;
360                                         }
361                                         else {
362                                                 BLI_remlink(&em->faces, efa);
363                                                 free_editface(em, efa);
364                                                 amount--;
365                                         }
366                                 }
367                                 else {
368                                         BLI_remlink(&em->faces, efa);
369                                         free_editface(em, efa);
370                                         amount--;
371                                 }
372                         }
373
374                         if(test==0) {
375                                 /* set edge pointers */
376                                 efa->e1= findedgelist(em, efa->v1, efa->v2);
377                                 efa->e2= findedgelist(em, efa->v2, efa->v3);
378                                 if(efa->v4==0) {
379                                         efa->e3= findedgelist(em, efa->v3, efa->v1);
380                                         efa->e4= 0;
381                                 }
382                                 else {
383                                         efa->e3= findedgelist(em, efa->v3, efa->v4);
384                                         efa->e4= findedgelist(em, efa->v4, efa->v1);
385                                 }
386                         }
387                 }
388                 efa= nextvl;
389         }
390
391         /* double faces: sort block */
392         /* count again, now all selected faces */
393         amount= 0;
394         efa= em->faces.first;
395         while(efa) {
396                 efa->f1= 0;
397                 if(faceselectedOR(efa, 1)) {
398                         efa->f1= 1;
399                         amount++;
400                 }
401                 efa= efa->next;
402         }
403
404         if(amount) {
405                 /* double faces: sort block */
406                 vsb= vlsortblock= MEM_mallocN(sizeof(struct facesort)*amount, "sortremovedoub");
407                 efa= em->faces.first;
408                 while(efa) {
409                         if(efa->f1 & 1) {
410                                 if(efa->v4) vsb->x= (uintptr_t) MIN4( (uintptr_t)efa->v1, (uintptr_t)efa->v2, (uintptr_t)efa->v3, (uintptr_t)efa->v4);
411                                 else vsb->x= (uintptr_t) MIN3( (uintptr_t)efa->v1, (uintptr_t)efa->v2, (uintptr_t)efa->v3);
412
413                                 vsb->efa= efa;
414                                 vsb++;
415                         }
416                         efa= efa->next;
417                 }
418
419                 qsort(vlsortblock, amount, sizeof(struct facesort), vergface);
420
421                 vsb= vlsortblock;
422                 for(a=0; a<amount; a++) {
423                         efa= vsb->efa;
424                         if( (efa->f1 & 128)==0 ) {
425                                 vsb1= vsb+1;
426
427                                 for(b=a+1; b<amount; b++) {
428
429                                         /* first test: same pointer? */
430                                         if(vsb->x != vsb1->x) break;
431
432                                         /* second test: is test permitted? */
433                                         efa= vsb1->efa;
434                                         if( (efa->f1 & 128)==0 ) {
435                                                 if( compareface(efa, vsb->efa)) efa->f1 |= 128;
436
437                                         }
438                                         vsb1++;
439                                 }
440                         }
441                         vsb++;
442                 }
443
444                 MEM_freeN(vlsortblock);
445
446                 /* remove double faces */
447                 efa= (struct EditFace *)em->faces.first;
448                 while(efa) {
449                         nextvl= efa->next;
450                         if(efa->f1 & 128) {
451                                 BLI_remlink(&em->faces, efa);
452                                 free_editface(em, efa);
453                         }
454                         efa= nextvl;
455                 }
456         }
457
458         /* remove double vertices */
459         a= 0;
460         eve= (struct EditVert *)em->verts.first;
461         while(eve) {
462                 nextve= eve->next;
463                 if(automerge || eve->f & flag) {
464                         if(eve->f & 128) {
465                                 a++;
466                                 BLI_remlink(&em->verts, eve);
467                                 free_editvert(em, eve);
468                         }
469                 }
470                 eve= nextve;
471         }
472
473         return a;       /* amount */
474 }
475
476 static int removedoublesflag_exec(bContext *C, wmOperator *op)
477 {
478         Object *obedit= CTX_data_edit_object(C);
479         EditMesh *em= BKE_mesh_get_editmesh(((Mesh *)obedit->data));
480
481         int count = removedoublesflag(em,1,0,RNA_float_get(op->ptr, "limit"));
482         
483         if(count) {
484                 recalc_editnormals(em);
485
486                 DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
487                 WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
488         }
489
490         BKE_reportf(op->reports, RPT_INFO, "Removed %d vertices", count);
491         BKE_mesh_end_editmesh(obedit->data, em);
492
493         return OPERATOR_FINISHED;
494 }
495
496 void MESH_OT_remove_doubles(wmOperatorType *ot)
497 {
498         PropertyRNA *prop;
499
500         /* identifiers */
501         ot->name= "Remove Doubles";
502         ot->description= "Remove duplicate vertices";
503         ot->idname= "MESH_OT_remove_doubles";
504
505         /* api callbacks */
506         ot->exec= removedoublesflag_exec;
507         ot->poll= ED_operator_editmesh;
508
509         /* flags */
510         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
511
512         prop= RNA_def_float(ot->srna, "limit", 0.0001f, 0.000001f, 50.0f, "Merge Threshold", "Minimum distance between merged verts", 0.00001f, 2.0f);
513         RNA_def_property_ui_range(prop,  0.000001f, 50.0f, 0.001, 5);
514 }
515
516 // XXX is this needed?
517 /* called from buttons */
518 static void xsortvert_flag__doSetX(void *userData, EditVert *UNUSED(eve), int x, int UNUSED(y), int index)
519 {
520         xvertsort *sortblock = userData;
521
522         sortblock[index].x = x;
523 }
524
525 /* all verts with (flag & 'flag') are sorted */
526 void xsortvert_flag(bContext *C, int flag)
527 {
528         ViewContext vc;
529         EditVert *eve;
530         xvertsort *sortblock;
531         ListBase tbase;
532         int i, amount;
533
534         em_setup_viewcontext(C, &vc);
535
536         amount = BLI_countlist(&vc.em->verts);
537         sortblock = MEM_callocN(sizeof(xvertsort)*amount,"xsort");
538         for (i=0,eve= vc.em->verts.first; eve; i++,eve=eve->next)
539                 if(eve->f & flag)
540                         sortblock[i].v1 = eve;
541
542         ED_view3d_init_mats_rv3d(vc.obedit, vc.rv3d);
543         mesh_foreachScreenVert(&vc, xsortvert_flag__doSetX, sortblock, 0);
544
545         qsort(sortblock, amount, sizeof(xvertsort), vergxco);
546
547                 /* make temporal listbase */
548         tbase.first= tbase.last= 0;
549         for (i=0; i<amount; i++) {
550                 eve = sortblock[i].v1;
551
552                 if (eve) {
553                         BLI_remlink(&vc.em->verts, eve);
554                         BLI_addtail(&tbase, eve);
555                 }
556         }
557
558         addlisttolist(&vc.em->verts, &tbase);
559
560         MEM_freeN(sortblock);
561
562 }
563
564 /* called from buttons */
565 void hashvert_flag(EditMesh *em, int flag)
566 {
567         /* switch vertex order using hash table */
568         EditVert *eve;
569         struct xvertsort *sortblock, *sb, onth, *newsort;
570         ListBase tbase;
571         int amount, a, b;
572
573         /* count */
574         eve= em->verts.first;
575         amount= 0;
576         while(eve) {
577                 if(eve->f & flag) amount++;
578                 eve= eve->next;
579         }
580         if(amount==0) return;
581
582         /* allocate memory */
583         sb= sortblock= (struct xvertsort *)MEM_mallocN(sizeof(struct xvertsort)*amount,"sortremovedoub");
584         eve= em->verts.first;
585         while(eve) {
586                 if(eve->f & flag) {
587                         sb->v1= eve;
588                         sb++;
589                 }
590                 eve= eve->next;
591         }
592
593         BLI_srand(1);
594
595         sb= sortblock;
596         for(a=0; a<amount; a++, sb++) {
597                 b= (int)(amount*BLI_drand());
598                 if(b>=0 && b<amount) {
599                         newsort= sortblock+b;
600                         onth= *sb;
601                         *sb= *newsort;
602                         *newsort= onth;
603                 }
604         }
605
606         /* make temporal listbase */
607         tbase.first= tbase.last= 0;
608         sb= sortblock;
609         while(amount--) {
610                 eve= sb->v1;
611                 BLI_remlink(&em->verts, eve);
612                 BLI_addtail(&tbase, eve);
613                 sb++;
614         }
615
616         addlisttolist(&em->verts, &tbase);
617
618         MEM_freeN(sortblock);
619
620 }
621
622 /* generic extern called extruder */
623 static void extrude_mesh(Object *obedit, EditMesh *em, wmOperator *op, short type)
624 {
625         float nor[3]= {0.0, 0.0, 0.0};
626         short transmode= 0;
627
628         if(type<1) return;
629
630         if(type==1)  transmode= extrudeflag(obedit, em, SELECT, nor, 0);
631         else if(type==4) transmode= extrudeflag_verts_indiv(em, SELECT, nor);
632         else if(type==3) transmode= extrudeflag_edges_indiv(em, SELECT, nor);
633         else transmode= extrudeflag_face_indiv(em, SELECT, nor);
634
635         EM_stats_update(em);
636
637         if(transmode==0) {
638                 BKE_report(op->reports, RPT_ERROR, "Not a valid selection for extrude");
639         }
640         else {
641                 EM_fgon_flags(em);
642
643                         /* We need to force immediate calculation here because
644                         * transform may use derived objects (which are now stale).
645                         *
646                         * This shouldn't be necessary, derived queries should be
647                         * automatically building this data if invalid. Or something.
648                         */
649                 DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
650
651                 /* individual faces? */
652 //              BIF_TransformSetUndo("Extrude");
653                 if(type==2) {
654 //                      initTransform(TFM_SHRINKFATTEN, CTX_NO_PET|CTX_NO_MIRROR);
655 //                      Transform();
656                 }
657                 else {
658 //                      initTransform(TFM_TRANSLATION, CTX_NO_PET|CTX_NO_MIRROR);
659                         if(transmode=='n') {
660                                 mul_m4_v3(obedit->obmat, nor);
661                                 sub_v3_v3(nor, obedit->obmat[3]);
662 //                              BIF_setSingleAxisConstraint(nor, "along normal");
663                         }
664 //                      Transform();
665                 }
666         }
667
668 }
669
670 // XXX should be a menu item
671 static int mesh_extrude_invoke(bContext *C, wmOperator *op, wmEvent *UNUSED(event))
672 {
673         Object *obedit= CTX_data_edit_object(C);
674         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
675         
676         extrude_mesh(obedit, em, op, RNA_int_get(op->ptr, "type"));
677
678         BKE_mesh_end_editmesh(obedit->data, em);
679
680         DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
681         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
682
683         return OPERATOR_FINISHED;
684 }
685
686 /* extrude without transform */
687 static int mesh_extrude_exec(bContext *C, wmOperator *op)
688 {
689         Object *obedit= CTX_data_edit_object(C);
690         EditMesh *em= BKE_mesh_get_editmesh(obedit->data);
691
692         extrude_mesh(obedit, em, op, RNA_int_get(op->ptr, "type"));
693
694         DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
695         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
696
697         BKE_mesh_end_editmesh(obedit->data, em);
698         return OPERATOR_FINISHED;
699 }
700
701 EnumPropertyItem extrude_items[] = {
702                 {1, "REGION", 0, "Region", ""},
703                 {2, "FACES", 0, "Individual Faces", ""},
704                 {3, "EDGES", 0, "Only Edges", ""},
705                 {4, "VERTS", 0, "Only Vertices", ""},
706                 {0, NULL, 0, NULL, NULL}};
707
708
709 static EnumPropertyItem *extrude_itemf(bContext *C, PointerRNA *UNUSED(ptr), int *free)
710 {
711         EnumPropertyItem *item= NULL;
712         Object *obedit= CTX_data_edit_object(C);
713         EditMesh *em;
714
715         int totitem= 0;
716
717         if(!obedit)
718                 return extrude_items;
719
720         em = BKE_mesh_get_editmesh(obedit->data);
721
722         EM_stats_update(em);
723
724         if(em->selectmode & SCE_SELECT_VERTEX) {
725                 if(em->totvertsel==0) {}
726                 else if(em->totvertsel==1) { RNA_enum_item_add(&item, &totitem, &extrude_items[3]); }
727                 else if(em->totedgesel==0) { RNA_enum_item_add(&item, &totitem, &extrude_items[3]); }
728                 else if(em->totfacesel==0) {
729                         RNA_enum_item_add(&item, &totitem, &extrude_items[2]);
730                         RNA_enum_item_add(&item, &totitem, &extrude_items[3]);
731                 }
732                 else if(em->totfacesel==1) {
733                         RNA_enum_item_add(&item, &totitem, &extrude_items[0]);
734                         RNA_enum_item_add(&item, &totitem, &extrude_items[2]);
735                         RNA_enum_item_add(&item, &totitem, &extrude_items[3]);
736                 }
737                 else {
738                         RNA_enum_item_add(&item, &totitem, &extrude_items[0]);
739                         RNA_enum_item_add(&item, &totitem, &extrude_items[1]);
740                         RNA_enum_item_add(&item, &totitem, &extrude_items[2]);
741                         RNA_enum_item_add(&item, &totitem, &extrude_items[3]);
742                 }
743         }
744         else if(em->selectmode & SCE_SELECT_EDGE) {
745                 if (em->totedgesel==0) {}
746                 else if (em->totedgesel==1) { RNA_enum_item_add(&item, &totitem, &extrude_items[2]); }
747                 else if(em->totfacesel==0) { RNA_enum_item_add(&item, &totitem, &extrude_items[2]); }
748                 else if(em->totfacesel==1) {
749                         RNA_enum_item_add(&item, &totitem, &extrude_items[0]);
750                         RNA_enum_item_add(&item, &totitem, &extrude_items[2]);
751                 }
752                 else {
753                         RNA_enum_item_add(&item, &totitem, &extrude_items[0]);
754                         RNA_enum_item_add(&item, &totitem, &extrude_items[1]);
755                         RNA_enum_item_add(&item, &totitem, &extrude_items[2]);
756                 }
757         }
758         else {
759                 if (em->totfacesel == 0) {}
760                 else if (em->totfacesel == 1) { RNA_enum_item_add(&item, &totitem, &extrude_items[0]); }
761                 else {
762                         RNA_enum_item_add(&item, &totitem, &extrude_items[0]);
763                         RNA_enum_item_add(&item, &totitem, &extrude_items[1]);
764                 }
765         }
766
767         if(item) {
768                 RNA_enum_item_end(&item, &totitem);
769                 *free= 1;
770                 return item;
771         }
772         else {
773                 return NULL;
774         }
775 }
776
777 void MESH_OT_extrude(wmOperatorType *ot)
778 {
779         PropertyRNA *prop;
780
781         /* identifiers */
782         ot->name= "Extrude";
783         ot->description= "Extrude selected vertices, edges or faces";
784         ot->idname= "MESH_OT_extrude";
785
786         /* api callbacks */
787         ot->invoke= mesh_extrude_invoke;
788         ot->exec= mesh_extrude_exec;
789         ot->poll= ED_operator_editmesh;
790
791         /* flags */
792         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
793
794         /* properties */
795         prop= RNA_def_enum(ot->srna, "type", extrude_items, 0, "Type", "");
796         RNA_def_property_flag(prop, PROP_HIDDEN);
797         RNA_def_enum_funcs(prop, extrude_itemf);
798         ot->prop= prop;
799 }
800
801 static int split_mesh(bContext *C, wmOperator *UNUSED(op))
802 {
803         Object *obedit= CTX_data_edit_object(C);
804         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
805
806         WM_cursor_wait(1);
807
808         /* make duplicate first */
809         adduplicateflag(em, SELECT);
810         /* old faces have flag 128 set, delete them */
811         delfaceflag(em, 128);
812         recalc_editnormals(em);
813
814         WM_cursor_wait(0);
815
816         DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
817         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
818
819         BKE_mesh_end_editmesh(obedit->data, em);
820         return OPERATOR_FINISHED;
821 }
822
823 void MESH_OT_split(wmOperatorType *ot)
824 {
825         /* identifiers */
826         ot->name= "Split";
827         ot->description= "Split selected geometry into separate disconnected mesh";
828         ot->idname= "MESH_OT_split";
829
830         /* api callbacks */
831         ot->exec= split_mesh;
832         ot->poll= ED_operator_editmesh;
833
834         /* flags */
835         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
836 }
837
838
839 static int extrude_repeat_mesh(bContext *C, wmOperator *op)
840 {
841         Object *obedit= CTX_data_edit_object(C);
842         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
843
844         RegionView3D *rv3d = ED_view3d_context_rv3d(C);
845
846         int steps = RNA_int_get(op->ptr,"steps");
847
848         float offs = RNA_float_get(op->ptr,"offset");
849
850         float dvec[3], tmat[3][3], bmat[3][3], nor[3]= {0.0, 0.0, 0.0};
851         short a;
852
853         /* dvec */
854         dvec[0]= rv3d->persinv[2][0];
855         dvec[1]= rv3d->persinv[2][1];
856         dvec[2]= rv3d->persinv[2][2];
857         normalize_v3(dvec);
858         dvec[0]*= offs;
859         dvec[1]*= offs;
860         dvec[2]*= offs;
861
862         /* base correction */
863         copy_m3_m4(bmat, obedit->obmat);
864         invert_m3_m3(tmat, bmat);
865         mul_m3_v3(tmat, dvec);
866
867         for(a=0; a<steps; a++) {
868                 extrudeflag(obedit, em, SELECT, nor, 0);
869                 translateflag(em, SELECT, dvec);
870         }
871
872         recalc_editnormals(em);
873
874         EM_fgon_flags(em);
875
876         DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
877         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
878
879         BKE_mesh_end_editmesh(obedit->data, em);
880         return OPERATOR_FINISHED;
881 }
882
883 void MESH_OT_extrude_repeat(wmOperatorType *ot)
884 {
885         /* identifiers */
886         ot->name= "Extrude Repeat Mesh";
887         ot->description= "Extrude selected vertices, edges or faces repeatedly";
888         ot->idname= "MESH_OT_extrude_repeat";
889
890         /* api callbacks */
891         ot->exec= extrude_repeat_mesh;
892         ot->poll= ED_operator_editmesh;
893
894         /* flags */
895         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
896
897         /* props */
898         RNA_def_float(ot->srna, "offset", 2.0f, 0.0f, 100.0f, "Offset", "", 0.0f, FLT_MAX);
899         RNA_def_int(ot->srna, "steps", 10, 0, 180, "Steps", "", 0, INT_MAX);
900 }
901
902 /* ************************** spin operator ******************** */
903
904
905 static int spin_mesh(bContext *C, wmOperator *op, float *dvec, int steps, float degr, int dupli )
906 {
907         Object *obedit= CTX_data_edit_object(C);
908         ToolSettings *ts= CTX_data_tool_settings(C);
909         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
910         EditVert *eve,*nextve;
911         float nor[3]= {0.0f, 0.0f, 0.0f};
912         float si, n[3], q[4], cmat[3][3], imat[3][3], tmat[3][3];
913         float cent[3], bmat[3][3];
914         float phi;
915         short a, ok= 1;
916
917         RNA_float_get_array(op->ptr, "center", cent);
918
919         /* imat and center and size */
920         copy_m3_m4(bmat, obedit->obmat);
921         invert_m3_m3(imat,bmat);
922
923         cent[0]-= obedit->obmat[3][0];
924         cent[1]-= obedit->obmat[3][1];
925         cent[2]-= obedit->obmat[3][2];
926         mul_m3_v3(imat, cent);
927
928         phi= degr*M_PI/360.0;
929         phi/= steps;
930         if(ts->editbutflag & B_CLOCKWISE) phi= -phi;
931
932         RNA_float_get_array(op->ptr, "axis", n);
933         normalize_v3(n);
934
935         q[0]= (float)cos(phi);
936         si= (float)sin(phi);
937         q[1]= n[0]*si;
938         q[2]= n[1]*si;
939         q[3]= n[2]*si;
940         quat_to_mat3( cmat,q);
941
942         mul_m3_m3m3(tmat,cmat,bmat);
943         mul_m3_m3m3(bmat,imat,tmat);
944
945         if(dupli==0)
946                 if(ts->editbutflag & B_KEEPORIG)
947                         adduplicateflag(em, 1);
948
949         for(a=0; a<steps; a++) {
950                 if(dupli==0) ok= extrudeflag(obedit, em, SELECT, nor, 0);
951                 else adduplicateflag(em, SELECT);
952
953                 if(ok==0)
954                         break;
955
956                 rotateflag(em, SELECT, cent, bmat);
957                 if(dvec) {
958                         mul_m3_v3(bmat,dvec);
959                         translateflag(em, SELECT, dvec);
960                 }
961         }
962
963         if(ok==0) {
964                 /* no vertices or only loose ones selected, remove duplicates */
965                 eve= em->verts.first;
966                 while(eve) {
967                         nextve= eve->next;
968                         if(eve->f & SELECT) {
969                                 BLI_remlink(&em->verts,eve);
970                                 free_editvert(em, eve);
971                         }
972                         eve= nextve;
973                 }
974         }
975         else {
976                 recalc_editnormals(em);
977
978                 EM_fgon_flags(em);
979
980                 DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
981         }
982
983         BKE_mesh_end_editmesh(obedit->data, em);
984         return ok;
985 }
986
987 static int spin_mesh_exec(bContext *C, wmOperator *op)
988 {
989         Object *obedit= CTX_data_edit_object(C);
990         int ok;
991
992         ok= spin_mesh(C, op, NULL, RNA_int_get(op->ptr,"steps"), RNA_float_get(op->ptr,"degrees"), RNA_boolean_get(op->ptr,"dupli"));
993         if(ok==0) {
994                 BKE_report(op->reports, RPT_ERROR, "No valid vertices are selected");
995                 return OPERATOR_CANCELLED;
996         }
997
998         DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
999         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
1000
1001         return OPERATOR_FINISHED;
1002 }
1003
1004 /* get center and axis, in global coords */
1005 static int spin_mesh_invoke(bContext *C, wmOperator *op, wmEvent *UNUSED(event))
1006 {
1007         Scene *scene = CTX_data_scene(C);
1008         View3D *v3d = CTX_wm_view3d(C);
1009         RegionView3D *rv3d= ED_view3d_context_rv3d(C);
1010
1011         RNA_float_set_array(op->ptr, "center", give_cursor(scene, v3d));
1012         RNA_float_set_array(op->ptr, "axis", rv3d->viewinv[2]);
1013
1014         return spin_mesh_exec(C, op);
1015 }
1016
1017 void MESH_OT_spin(wmOperatorType *ot)
1018 {
1019         /* identifiers */
1020         ot->name= "Spin";
1021         ot->description= "Extrude selected vertices in a circle around the cursor in indicated viewport";
1022         ot->idname= "MESH_OT_spin";
1023
1024         /* api callbacks */
1025         ot->invoke= spin_mesh_invoke;
1026         ot->exec= spin_mesh_exec;
1027         ot->poll= EM_view3d_poll;
1028
1029         /* flags */
1030         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1031
1032         /* props */
1033         RNA_def_int(ot->srna, "steps", 9, 0, INT_MAX, "Steps", "Steps", 0, 128);
1034         RNA_def_boolean(ot->srna, "dupli", 0, "Dupli", "Make Duplicates");
1035         RNA_def_float(ot->srna, "degrees", 90.0f, -FLT_MAX, FLT_MAX, "Degrees", "Degrees", -360.0f, 360.0f);
1036
1037         RNA_def_float_vector_xyz(ot->srna, "center", 3, NULL, -FLT_MAX, FLT_MAX, "Center", "Center in global view space", -FLT_MAX, FLT_MAX);
1038         RNA_def_float_vector(ot->srna, "axis", 3, NULL, -1.0f, 1.0f, "Axis", "Axis in global view space", -FLT_MAX, FLT_MAX);
1039
1040 }
1041
1042 static int screw_mesh_exec(bContext *C, wmOperator *op)
1043 {
1044         Object *obedit= CTX_data_edit_object(C);
1045         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
1046         EditVert *eve,*v1=0,*v2=0;
1047         EditEdge *eed;
1048         float dvec[3], nor[3];
1049         int steps, turns;
1050
1051         turns= RNA_int_get(op->ptr, "turns");
1052         steps= RNA_int_get(op->ptr, "steps");
1053
1054         /* clear flags */
1055         for(eve= em->verts.first; eve; eve= eve->next)
1056                 eve->f1= 0;
1057
1058         /* edges set flags in verts */
1059         for(eed= em->edges.first; eed; eed= eed->next) {
1060                 if(eed->v1->f & SELECT) {
1061                         if(eed->v2->f & SELECT) {
1062                                 /* watch: f1 is a byte */
1063                                 if(eed->v1->f1<2) eed->v1->f1++;
1064                                 if(eed->v2->f1<2) eed->v2->f1++;
1065                         }
1066                 }
1067         }
1068         /* find two vertices with eve->f1==1, more or less is wrong */
1069         for(eve= em->verts.first; eve; eve= eve->next) {
1070                 if(eve->f1==1) {
1071                         if(v1==NULL) v1= eve;
1072                         else if(v2==NULL) v2= eve;
1073                         else {
1074                                 v1= NULL;
1075                                 break;
1076                         }
1077                 }
1078         }
1079         if(v1==NULL || v2==NULL) {
1080                 BKE_report(op->reports, RPT_ERROR, "You have to select a string of connected vertices too");
1081                 BKE_mesh_end_editmesh(obedit->data, em);
1082                 return OPERATOR_CANCELLED;
1083         }
1084
1085         /* calculate dvec */
1086         dvec[0]= ( v1->co[0]- v2->co[0] )/steps;
1087         dvec[1]= ( v1->co[1]- v2->co[1] )/steps;
1088         dvec[2]= ( v1->co[2]- v2->co[2] )/steps;
1089
1090         VECCOPY(nor, obedit->obmat[2]);
1091
1092         if(nor[0]*dvec[0]+nor[1]*dvec[1]+nor[2]*dvec[2]>0.000) {
1093                 dvec[0]= -dvec[0];
1094                 dvec[1]= -dvec[1];
1095                 dvec[2]= -dvec[2];
1096         }
1097
1098         if(spin_mesh(C, op, dvec, turns*steps, 360.0f*turns, 0)) {
1099                 DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
1100                 WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
1101
1102                 BKE_mesh_end_editmesh(obedit->data, em);
1103                 return OPERATOR_FINISHED;
1104         }
1105         else {
1106                 BKE_report(op->reports, RPT_ERROR, "No valid vertices are selected");
1107                 BKE_mesh_end_editmesh(obedit->data, em);
1108                 return OPERATOR_CANCELLED;
1109         }
1110 }
1111
1112 /* get center and axis, in global coords */
1113 static int screw_mesh_invoke(bContext *C, wmOperator *op, wmEvent *UNUSED(event))
1114 {
1115         Scene *scene = CTX_data_scene(C);
1116         View3D *v3d = CTX_wm_view3d(C);
1117         RegionView3D *rv3d= ED_view3d_context_rv3d(C);
1118
1119         RNA_float_set_array(op->ptr, "center", give_cursor(scene, v3d));
1120         RNA_float_set_array(op->ptr, "axis", rv3d->viewinv[1]);
1121
1122         return screw_mesh_exec(C, op);
1123 }
1124
1125 void MESH_OT_screw(wmOperatorType *ot)
1126 {
1127         /* identifiers */
1128         ot->name= "Screw";
1129         ot->description= "Extrude selected vertices in screw-shaped rotation around the cursor in indicated viewport";
1130         ot->idname= "MESH_OT_screw";
1131
1132         /* api callbacks */
1133         ot->invoke= screw_mesh_invoke;
1134         ot->exec= screw_mesh_exec;
1135         ot->poll= EM_view3d_poll;
1136
1137         /* flags */
1138         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1139
1140         /*props */
1141         RNA_def_int(ot->srna, "steps", 9, 0, INT_MAX, "Steps", "Steps", 0, 256);
1142         RNA_def_int(ot->srna, "turns", 1, 0, INT_MAX, "Turns", "Turns", 0, 256);
1143
1144         RNA_def_float_vector_xyz(ot->srna, "center", 3, NULL, -FLT_MAX, FLT_MAX, "Center", "Center in global view space", -FLT_MAX, FLT_MAX);
1145         RNA_def_float_vector(ot->srna, "axis", 3, NULL, -1.0f, 1.0f, "Axis", "Axis in global view space", -FLT_MAX, FLT_MAX);
1146 }
1147
1148 static void erase_edges(EditMesh *em, ListBase *l)
1149 {
1150         EditEdge *ed, *nexted;
1151
1152         ed = (EditEdge *) l->first;
1153         while(ed) {
1154                 nexted= ed->next;
1155                 if( (ed->v1->f & SELECT) || (ed->v2->f & SELECT) ) {
1156                         remedge(em, ed);
1157                         free_editedge(em, ed);
1158                 }
1159                 ed= nexted;
1160         }
1161 }
1162
1163 static void erase_faces(EditMesh *em, ListBase *l)
1164 {
1165         EditFace *f, *nextf;
1166
1167         f = (EditFace *) l->first;
1168
1169         while(f) {
1170                 nextf= f->next;
1171                 if( faceselectedOR(f, SELECT) ) {
1172                         BLI_remlink(l, f);
1173                         free_editface(em, f);
1174                 }
1175                 f = nextf;
1176         }
1177 }
1178
1179 static void erase_vertices(EditMesh *em, ListBase *l)
1180 {
1181         EditVert *v, *nextv;
1182
1183         v = (EditVert *) l->first;
1184         while(v) {
1185                 nextv= v->next;
1186                 if(v->f & 1) {
1187                         BLI_remlink(l, v);
1188                         free_editvert(em, v);
1189                 }
1190                 v = nextv;
1191         }
1192 }
1193
1194 static void delete_mesh(EditMesh *em, wmOperator *op, int event)
1195 {
1196         EditFace *efa, *nextvl;
1197         EditVert *eve,*nextve;
1198         EditEdge *eed,*nexted;
1199         int count;
1200         const char *str="Erase";
1201
1202
1203         if(event<1) return;
1204
1205         if(event==10 ) {
1206                 str= "Erase Vertices";
1207                 erase_edges(em, &em->edges);
1208                 erase_faces(em, &em->faces);
1209                 erase_vertices(em, &em->verts);
1210         }
1211         else if(event==6) {
1212                 if(!EdgeLoopDelete(em, op))
1213                         return;
1214
1215                 str= "Erase Edge Loop";
1216         }
1217         else if(event==4) {
1218                 str= "Erase Edges & Faces";
1219                 efa= em->faces.first;
1220                 while(efa) {
1221                         nextvl= efa->next;
1222                         /* delete only faces with 1 or more edges selected */
1223                         count= 0;
1224                         if(efa->e1->f & SELECT) count++;
1225                         if(efa->e2->f & SELECT) count++;
1226                         if(efa->e3->f & SELECT) count++;
1227                         if(efa->e4 && (efa->e4->f & SELECT)) count++;
1228                         if(count) {
1229                                 BLI_remlink(&em->faces, efa);
1230                                 free_editface(em, efa);
1231                         }
1232                         efa= nextvl;
1233                 }
1234                 eed= em->edges.first;
1235                 while(eed) {
1236                         nexted= eed->next;
1237                         if(eed->f & SELECT) {
1238                                 remedge(em, eed);
1239                                 free_editedge(em, eed);
1240                         }
1241                         eed= nexted;
1242                 }
1243                 efa= em->faces.first;
1244                 while(efa) {
1245                         nextvl= efa->next;
1246                         event=0;
1247                         if( efa->v1->f & SELECT) event++;
1248                         if( efa->v2->f & SELECT) event++;
1249                         if( efa->v3->f & SELECT) event++;
1250                         if(efa->v4 && (efa->v4->f & SELECT)) event++;
1251
1252                         if(event>1) {
1253                                 BLI_remlink(&em->faces, efa);
1254                                 free_editface(em, efa);
1255                         }
1256                         efa= nextvl;
1257                 }
1258         }
1259         else if(event==1) {
1260                 str= "Erase Edges";
1261                 // faces first
1262                 efa= em->faces.first;
1263                 while(efa) {
1264                         nextvl= efa->next;
1265                         event=0;
1266                         if( efa->e1->f & SELECT) event++;
1267                         if( efa->e2->f & SELECT) event++;
1268                         if( efa->e3->f & SELECT) event++;
1269                         if(efa->e4 && (efa->e4->f & SELECT)) event++;
1270
1271                         if(event) {
1272                                 BLI_remlink(&em->faces, efa);
1273                                 free_editface(em, efa);
1274                         }
1275                         efa= nextvl;
1276                 }
1277                 eed= em->edges.first;
1278                 while(eed) {
1279                         nexted= eed->next;
1280                         if(eed->f & SELECT) {
1281                                 remedge(em, eed);
1282                                 free_editedge(em, eed);
1283                         }
1284                         eed= nexted;
1285                 }
1286                 /* to remove loose vertices: */
1287                 eed= em->edges.first;
1288                 while(eed) {
1289                         if( eed->v1->f & SELECT) eed->v1->f-=SELECT;
1290                         if( eed->v2->f & SELECT) eed->v2->f-=SELECT;
1291                         eed= eed->next;
1292                 }
1293                 eve= em->verts.first;
1294                 while(eve) {
1295                         nextve= eve->next;
1296                         if(eve->f & SELECT) {
1297                                 BLI_remlink(&em->verts,eve);
1298                                 free_editvert(em, eve);
1299                         }
1300                         eve= nextve;
1301                 }
1302
1303         }
1304         else if(event==2) {
1305                 str="Erase Faces";
1306                 delfaceflag(em, SELECT);
1307         }
1308         else if(event==3) {
1309                 str= "Erase All";
1310                 if(em->verts.first) free_vertlist(em, &em->verts);
1311                 if(em->edges.first) free_edgelist(em, &em->edges);
1312                 if(em->faces.first) free_facelist(em, &em->faces);
1313                 if(em->selected.first) BLI_freelistN(&(em->selected));
1314         }
1315         else if(event==5) {
1316                 str= "Erase Only Faces";
1317                 efa= em->faces.first;
1318                 while(efa) {
1319                         nextvl= efa->next;
1320                         if(efa->f & SELECT) {
1321                                 BLI_remlink(&em->faces, efa);
1322                                 free_editface(em, efa);
1323                         }
1324                         efa= nextvl;
1325                 }
1326         }
1327
1328         EM_fgon_flags(em);      // redo flags and indices for fgons
1329 }
1330
1331 /* Note, these values must match delete_mesh() event values */
1332 static EnumPropertyItem prop_mesh_delete_types[] = {
1333         {10,"VERT",             0, "Vertices", ""},
1334         {1, "EDGE",             0, "Edges", ""},
1335         {2, "FACE",             0, "Faces", ""},
1336         {3, "ALL",              0, "All", ""},
1337         {4, "EDGE_FACE",0, "Edges & Faces", ""},
1338         {5, "ONLY_FACE",0, "Only Faces", ""},
1339         {6, "EDGE_LOOP",0, "Edge Loop", ""},
1340         {0, NULL, 0, NULL, NULL}
1341 };
1342
1343 static int delete_mesh_exec(bContext *C, wmOperator *op)
1344 {
1345         Object *obedit= CTX_data_edit_object(C);
1346         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
1347         int type= RNA_enum_get(op->ptr, "type");
1348
1349         if(type==6)
1350                 return WM_operator_name_call(C, "MESH_OT_delete_edgeloop", WM_OP_EXEC_DEFAULT, NULL);
1351
1352         delete_mesh(em, op, type);
1353
1354         DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
1355         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
1356
1357         BKE_mesh_end_editmesh(obedit->data, em);
1358         return OPERATOR_FINISHED;
1359 }
1360
1361 void MESH_OT_delete(wmOperatorType *ot)
1362 {
1363         /* identifiers */
1364         ot->name= "Delete";
1365         ot->description= "Delete selected vertices, edges or faces";
1366         ot->idname= "MESH_OT_delete";
1367
1368         /* api callbacks */
1369         ot->invoke= WM_menu_invoke;
1370         ot->exec= delete_mesh_exec;
1371
1372         ot->poll= ED_operator_editmesh;
1373
1374         /* flags */
1375         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1376
1377         /*props */
1378         ot->prop= RNA_def_enum(ot->srna, "type", prop_mesh_delete_types, 10, "Type", "Method used for deleting mesh data");
1379 }
1380
1381
1382 /*GB*/
1383 /*-------------------------------------------------------------------------------*/
1384 /*--------------------------- Edge Based Subdivide ------------------------------*/
1385
1386 #define EDGENEW 2
1387 #define FACENEW 2
1388 #define EDGEINNER  4
1389 #define EDGEOLD  8
1390
1391 /*used by faceloop cut to select only edges valid for edge slide*/
1392 #define DOUBLEOPFILL 16
1393
1394 /* calculates offset for co, based on fractal, sphere or smooth settings  */
1395 static void alter_co(float *co, EditEdge *edge, float smooth, float fractal, int beauty, float perc)
1396 {
1397         float vec1[3], fac;
1398
1399         if(beauty & B_SMOOTH) {
1400                 /* we calculate an offset vector vec1[], to be added to *co */
1401                 float len, fac, nor[3], nor1[3], nor2[3];
1402
1403                 sub_v3_v3v3(nor, edge->v1->co, edge->v2->co);
1404                 len= 0.5f*normalize_v3(nor);
1405
1406                 VECCOPY(nor1, edge->v1->no);
1407                 VECCOPY(nor2, edge->v2->no);
1408
1409                 /* cosine angle */
1410                 fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
1411
1412                 vec1[0]= fac*nor1[0];
1413                 vec1[1]= fac*nor1[1];
1414                 vec1[2]= fac*nor1[2];
1415
1416                 /* cosine angle */
1417                 fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
1418
1419                 vec1[0]+= fac*nor2[0];
1420                 vec1[1]+= fac*nor2[1];
1421                 vec1[2]+= fac*nor2[2];
1422
1423                 /* falloff for multi subdivide */
1424                 smooth *= sqrt(fabs(1.0f - 2.0f*fabs(0.5f-perc)));
1425
1426                 vec1[0]*= smooth*len;
1427                 vec1[1]*= smooth*len;
1428                 vec1[2]*= smooth*len;
1429
1430                 co[0] += vec1[0];
1431                 co[1] += vec1[1];
1432                 co[2] += vec1[2];
1433         }
1434         else if(beauty & B_SPHERE) { /* subdivide sphere */
1435                 normalize_v3(co);
1436                 co[0]*= smooth;
1437                 co[1]*= smooth;
1438                 co[2]*= smooth;
1439         }
1440
1441         if(beauty & B_FRACTAL) {
1442                 fac= fractal*len_v3v3(edge->v1->co, edge->v2->co);
1443                 vec1[0]= fac*(float)(0.5-BLI_drand());
1444                 vec1[1]= fac*(float)(0.5-BLI_drand());
1445                 vec1[2]= fac*(float)(0.5-BLI_drand());
1446                 add_v3_v3(co, vec1);
1447         }
1448 }
1449
1450 /* assumes in the edge is the correct interpolated vertices already */
1451 /* percent defines the interpolation, smooth, fractal and beauty are for special options */
1452 /* results in new vertex with correct coordinate, vertex normal and weight group info */
1453 static EditVert *subdivide_edge_addvert(EditMesh *em, EditEdge *edge, float smooth, float fractal, int beauty, float percent)
1454 {
1455         EditVert *ev;
1456         float co[3];
1457
1458         co[0] = (edge->v2->co[0]-edge->v1->co[0])*percent + edge->v1->co[0];
1459         co[1] = (edge->v2->co[1]-edge->v1->co[1])*percent + edge->v1->co[1];
1460         co[2] = (edge->v2->co[2]-edge->v1->co[2])*percent + edge->v1->co[2];
1461
1462         /* offset for smooth or sphere or fractal */
1463         alter_co(co, edge, smooth, fractal, beauty, percent);
1464
1465         /* clip if needed by mirror modifier */
1466         if (edge->v1->f2) {
1467                 if ( edge->v1->f2 & edge->v2->f2 & 1) {
1468                         co[0]= 0.0f;
1469                 }
1470                 if ( edge->v1->f2 & edge->v2->f2 & 2) {
1471                         co[1]= 0.0f;
1472                 }
1473                 if ( edge->v1->f2 & edge->v2->f2 & 4) {
1474                         co[2]= 0.0f;
1475                 }
1476         }
1477
1478         ev = addvertlist(em, co, NULL);
1479
1480         /* vert data (vgroups, ..) */
1481         EM_data_interp_from_verts(em, edge->v1, edge->v2, ev, percent);
1482
1483         /* normal */
1484         ev->no[0] = (edge->v2->no[0]-edge->v1->no[0])*percent + edge->v1->no[0];
1485         ev->no[1] = (edge->v2->no[1]-edge->v1->no[1])*percent + edge->v1->no[1];
1486         ev->no[2] = (edge->v2->no[2]-edge->v1->no[2])*percent + edge->v1->no[2];
1487         normalize_v3(ev->no);
1488
1489         return ev;
1490 }
1491
1492 static void flipvertarray(EditVert** arr, short size)
1493 {
1494         EditVert *hold;
1495         int i;
1496
1497         for(i=0; i<size/2; i++) {
1498                 hold = arr[i];
1499                 arr[i] = arr[size-i-1];
1500                 arr[size-i-1] = hold;
1501         }
1502 }
1503
1504 static void facecopy(EditMesh *em, EditFace *source, EditFace *target)
1505 {
1506         float *v1 = source->v1->co, *v2 = source->v2->co, *v3 = source->v3->co;
1507         float *v4 = source->v4? source->v4->co: NULL;
1508         float w[4][4];
1509
1510         CustomData_em_copy_data(&em->fdata, &em->fdata, source->data, &target->data);
1511
1512         target->mat_nr = source->mat_nr;
1513         target->flag   = source->flag;
1514         target->h          = source->h;
1515
1516         interp_weights_face_v3( w[0],v1, v2, v3, v4, target->v1->co);
1517         interp_weights_face_v3( w[1],v1, v2, v3, v4, target->v2->co);
1518         interp_weights_face_v3( w[2],v1, v2, v3, v4, target->v3->co);
1519         if (target->v4)
1520                 interp_weights_face_v3( w[3],v1, v2, v3, v4, target->v4->co);
1521
1522         CustomData_em_interp(&em->fdata, &source->data, NULL, (float*)w, 1, target->data);
1523 }
1524
1525 static void fill_quad_single(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1526 {
1527         EditEdge *cedge=NULL;
1528         EditVert *v[4], **verts;
1529         EditFace *hold;
1530         short start=0, end, left, right, vertsize,i;
1531
1532         v[0] = efa->v1;
1533         v[1] = efa->v2;
1534         v[2] = efa->v3;
1535         v[3] = efa->v4;
1536
1537         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1538         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
1539         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
1540         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}
1541
1542         // Point verts to the array of new verts for cedge
1543         verts = BLI_ghash_lookup(gh, cedge);
1544         //This is the index size of the verts array
1545         vertsize = numcuts+2;
1546
1547         // Is the original v1 the same as the first vert on the selected edge?
1548         // if not, the edge is running the opposite direction in this face so flip
1549         // the array to the correct direction
1550
1551         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1552         end     = (start+1)%4;
1553         left   = (start+2)%4;
1554         right  = (start+3)%4;
1555
1556         /*
1557         We should have something like this now
1558
1559                           end            start
1560                            3   2   1   0
1561                            |---*---*---|
1562                            |               |
1563                            |               |
1564                            |               |
1565                            -------------
1566                           left     right
1567
1568         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
1569         and 0,1,2... are the indexes of the new verts stored in verts
1570
1571         We will fill this case like this or this depending on even or odd cuts
1572
1573                            |---*---*---|                  |---*---|
1574                            |  /  \  |             |  / \  |
1575                            | /     \ |            | /   \ |
1576                            |/            \|               |/     \|
1577                            -------------                  ---------
1578         */
1579
1580         // Make center face
1581         if(vertsize % 2 == 0) {
1582                 hold = addfacelist(em, verts[(vertsize-1)/2],verts[((vertsize-1)/2)+1],v[left],v[right], NULL,NULL);
1583                 hold->e2->f2 |= EDGEINNER;
1584                 hold->e4->f2 |= EDGEINNER;
1585         }else{
1586                 hold = addfacelist(em, verts[(vertsize-1)/2],v[left],v[right],NULL, NULL,NULL);
1587                 hold->e1->f2 |= EDGEINNER;
1588                 hold->e3->f2 |= EDGEINNER;
1589         }
1590         facecopy(em, efa,hold);
1591
1592         // Make side faces
1593         for(i=0;i<(vertsize-1)/2;i++) {
1594                 hold = addfacelist(em, verts[i],verts[i+1],v[right],NULL,NULL,NULL);
1595                 facecopy(em, efa,hold);
1596                 if(i+1 != (vertsize-1)/2) {
1597                         if(seltype == SUBDIV_SELECT_INNER) {
1598                                 hold->e2->f2 |= EDGEINNER;
1599                         }
1600                 }
1601                 hold = addfacelist(em, verts[vertsize-2-i],verts[vertsize-1-i],v[left],NULL,NULL,NULL);
1602                 facecopy(em, efa,hold);
1603                 if(i+1 != (vertsize-1)/2) {
1604                         if(seltype == SUBDIV_SELECT_INNER) {
1605                                  hold->e3->f2 |= EDGEINNER;
1606                         }
1607                 }
1608         }
1609 }
1610
1611 static void fill_tri_single(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1612 {
1613         EditEdge *cedge=NULL;
1614         EditVert *v[3], **verts;
1615         EditFace *hold;
1616         short start=0, end, op, vertsize,i;
1617
1618         v[0] = efa->v1;
1619         v[1] = efa->v2;
1620         v[2] = efa->v3;
1621
1622         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1623         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
1624         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
1625
1626         // Point verts to the array of new verts for cedge
1627         verts = BLI_ghash_lookup(gh, cedge);
1628         //This is the index size of the verts array
1629         vertsize = numcuts+2;
1630
1631         // Is the original v1 the same as the first vert on the selected edge?
1632         // if not, the edge is running the opposite direction in this face so flip
1633         // the array to the correct direction
1634
1635         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1636            end  = (start+1)%3;
1637            op    = (start+2)%3;
1638
1639         /*
1640         We should have something like this now
1641
1642                           end            start
1643                            3   2   1   0
1644                            |---*---*---|
1645                            \               |
1646                                  \               |
1647                                    \       |
1648                                          \       |
1649                                            \   |
1650                                                  \ |
1651                                                    |op
1652
1653         where start,end,op are indexes of EditFace->v1, etc (stored in v)
1654         and 0,1,2... are the indexes of the new verts stored in verts
1655
1656         We will fill this case like this or this depending on even or odd cuts
1657
1658                            3   2   1   0
1659                            |---*---*---|
1660                            \    \  \   |
1661                                  \      \ \  |
1662                                    \   \ \ |
1663                                          \  \ \|
1664                                            \ \\|
1665                                                  \ |
1666                                                    |op
1667         */
1668
1669         // Make side faces
1670         for(i=0;i<(vertsize-1);i++) {
1671                 hold = addfacelist(em, verts[i],verts[i+1],v[op],NULL,NULL,NULL);
1672                 if(i+1 != vertsize-1) {
1673                         if(seltype == SUBDIV_SELECT_INNER) {
1674                                  hold->e2->f2 |= EDGEINNER;
1675                         }
1676                 }
1677                 facecopy(em, efa,hold);
1678         }
1679 }
1680
1681 static void fill_quad_double_op(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1682 {
1683         EditEdge *cedge[2]={NULL, NULL};
1684         EditVert *v[4], **verts[2];
1685         EditFace *hold;
1686         short start=0, end, left, right, vertsize,i;
1687
1688         v[0] = efa->v1;
1689         v[1] = efa->v2;
1690         v[2] = efa->v3;
1691         v[3] = efa->v4;
1692
1693         if(efa->e1->f & SELECT)   { cedge[0] = efa->e1;  cedge[1] = efa->e3; start = 0;}
1694         else if(efa->e2->f & SELECT)      { cedge[0] = efa->e2;  cedge[1] = efa->e4; start = 1;}
1695
1696         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1697         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1698         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1699         //This is the index size of the verts array
1700         vertsize = numcuts+2;
1701
1702         // Is the original v1 the same as the first vert on the selected edge?
1703         // if not, the edge is running the opposite direction in this face so flip
1704         // the array to the correct direction
1705
1706         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1707         end     = (start+1)%4;
1708         left   = (start+2)%4;
1709         right  = (start+3)%4;
1710         if(verts[1][0] != v[left]) {flipvertarray(verts[1],numcuts+2);}
1711         /*
1712         We should have something like this now
1713
1714                           end            start
1715                            3   2   1   0
1716                            |---*---*---|
1717                            |               |
1718                            |               |
1719                            |               |
1720                            |---*---*---|
1721                            0   1   2   3
1722                           left     right
1723
1724         We will fill this case like this or this depending on even or odd cuts
1725
1726                            |---*---*---|
1727                            |   |   |   |
1728                            |   |   |   |
1729                            |   |   |   |
1730                            |---*---*---|
1731         */
1732
1733         // Make side faces
1734         for(i=0;i<vertsize-1;i++) {
1735                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-2-i],verts[1][vertsize-1-i],NULL,NULL);
1736                 if(i < vertsize-2) {
1737                         hold->e2->f2 |= EDGEINNER;
1738                         hold->e2->f2 |= DOUBLEOPFILL;
1739                 }
1740                 facecopy(em, efa,hold);
1741         }
1742 }
1743
1744 static void fill_quad_double_adj_path(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1745 {
1746         EditEdge *cedge[2]={NULL, NULL};
1747         EditVert *v[4], **verts[2];
1748         EditFace *hold;
1749         short start=0, start2=0, vertsize,i;
1750         int ctrl= 0; // XXX
1751
1752         v[0] = efa->v1;
1753         v[1] = efa->v2;
1754         v[2] = efa->v3;
1755         v[3] = efa->v4;
1756
1757         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
1758         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
1759         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3;}
1760         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0;}
1761
1762         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1763         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1764         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1765         //This is the index size of the verts array
1766         vertsize = numcuts+2;
1767
1768         // Is the original v1 the same as the first vert on the selected edge?
1769         // if not, the edge is running the opposite direction in this face so flip
1770         // the array to the correct direction
1771
1772         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1773         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1774         /*
1775         We should have something like this now
1776
1777                            end           start
1778                                 3   2   1   0
1779                 start2 0|---*---*---|
1780                                 |                  |
1781                            1*              |
1782                                 |                  |
1783                            2*              |
1784                                 |                  |
1785                  end2  3|-----------|
1786
1787         We will fill this case like this or this depending on even or odd cuts
1788                            |---*---*---|
1789                            | /   /   / |
1790                            *   /   /   |
1791                            | /   /       |
1792                            *   /           |
1793                            | /           |
1794                            |-----------|
1795         */
1796
1797         // Make outside tris
1798         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
1799         /* when ctrl is depressed, only want verts on the cutline selected */
1800         if (ctrl)
1801                 hold->e3->f2 |= EDGEINNER;
1802         facecopy(em, efa,hold);
1803         hold = addfacelist(em, verts[0][0],verts[1][vertsize-1],v[(start2+2)%4],NULL,NULL,NULL);
1804         /* when ctrl is depressed, only want verts on the cutline selected */
1805         if (ctrl)
1806                 hold->e1->f2 |= EDGEINNER;
1807         facecopy(em, efa,hold);
1808         //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
1809         //      hold->e1->h |= EM_FGON;
1810         //}
1811         // Make side faces
1812
1813         for(i=0;i<numcuts;i++) {
1814                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);
1815                 hold->e2->f2 |= EDGEINNER;
1816                 facecopy(em, efa,hold);
1817         }
1818         //EM_fgon_flags(em);
1819
1820 }
1821
1822 static void fill_quad_double_adj_fan(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1823 {
1824         EditEdge *cedge[2]={NULL, NULL};
1825         EditVert *v[4], *op=NULL, **verts[2];
1826         EditFace *hold;
1827         short start=0, start2=0, vertsize,i;
1828
1829         v[0] = efa->v1;
1830         v[1] = efa->v2;
1831         v[2] = efa->v3;
1832         v[3] = efa->v4;
1833
1834         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1835         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1836         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1837         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1838
1839
1840         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1841         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1842         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1843         //This is the index size of the verts array
1844         vertsize = numcuts+2;
1845
1846         // Is the original v1 the same as the first vert on the selected edge?
1847         // if not, the edge is running the opposite direction in this face so flip
1848         // the array to the correct direction
1849
1850         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1851         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1852         /*
1853         We should have something like this now
1854
1855                            end           start
1856                                 3   2   1   0
1857                 start2 0|---*---*---|
1858                                 |                  |
1859                            1*              |
1860                                 |                  |
1861                            2*              |
1862                                 |                  |
1863                  end2  3|-----------|op
1864
1865         We will fill this case like this or this (warning horrible ascii art follows)
1866                            |---*---*---|
1867                            | \  \   \  |
1868                            *---\  \  \ |
1869                            |   \ \ \  \|
1870                            *---- \ \  \ |
1871                            |    ---  \\\|
1872                            |-----------|
1873         */
1874
1875         for(i=0;i<=numcuts;i++) {
1876                 hold = addfacelist(em, op,verts[1][numcuts-i],verts[1][numcuts-i+1],NULL,NULL,NULL);
1877                 hold->e1->f2 |= EDGEINNER;
1878                 facecopy(em, efa,hold);
1879
1880                 hold = addfacelist(em, op,verts[0][i],verts[0][i+1],NULL,NULL,NULL);
1881                 hold->e3->f2 |= EDGEINNER;
1882                 facecopy(em, efa,hold);
1883         }
1884 }
1885
1886 static void fill_quad_double_adj_inner(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1887 {
1888         EditEdge *cedge[2]={NULL, NULL};
1889         EditVert *v[4], *op=NULL, **verts[2],**inner;
1890         EditFace *hold;
1891         short start=0, start2=0, vertsize,i;
1892         float co[3];
1893
1894         v[0] = efa->v1;
1895         v[1] = efa->v2;
1896         v[2] = efa->v3;
1897         v[3] = efa->v4;
1898
1899         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1900         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1901         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1902         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1903
1904
1905         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1906         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1907         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1908         //This is the index size of the verts array
1909         vertsize = numcuts+2;
1910
1911         // Is the original v1 the same as the first vert on the selected edge?
1912         // if not, the edge is running the opposite direction in this face so flip
1913         // the array to the correct direction
1914
1915         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1916         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1917         /*
1918         We should have something like this now
1919
1920                            end           start
1921                                 3   2   1   0
1922                 start2 0|---*---*---|
1923                                 |                  |
1924                            1*              |
1925                                 |                  |
1926                            2*              |
1927                                 |                  |
1928                  end2  3|-----------|op
1929
1930         We will fill this case like this or this (warning horrible ascii art follows)
1931                            |---*-----*---|
1932                            | *     /     |
1933                            *   \ /       |
1934                            |    *        |
1935                            | /    \          |
1936                            *        \    |
1937                            |           \ |
1938                            |-------------|
1939         */
1940
1941         // Add Inner Vert(s)
1942         inner = MEM_mallocN(sizeof(EditVert*)*numcuts,"New inner verts");
1943
1944         for(i=0;i<numcuts;i++) {
1945                 co[0] = (verts[0][numcuts-i]->co[0] + verts[1][i+1]->co[0] ) / 2 ;
1946                 co[1] = (verts[0][numcuts-i]->co[1] + verts[1][i+1]->co[1] ) / 2 ;
1947                 co[2] = (verts[0][numcuts-i]->co[2] + verts[1][i+1]->co[2] ) / 2 ;
1948                 inner[i] = addvertlist(em, co, NULL);
1949                 inner[i]->f2 |= EDGEINNER;
1950
1951                 EM_data_interp_from_verts(em, verts[0][numcuts-i], verts[1][i+1], inner[i], 0.5f);
1952         }
1953
1954         // Add Corner Quad
1955         hold = addfacelist(em, verts[0][numcuts+1],verts[1][1],inner[0],verts[0][numcuts],NULL,NULL);
1956         hold->e2->f2 |= EDGEINNER;
1957         hold->e3->f2 |= EDGEINNER;
1958         facecopy(em, efa,hold);
1959         // Add Bottom Quads
1960         hold = addfacelist(em, verts[0][0],verts[0][1],inner[numcuts-1],op,NULL,NULL);
1961         hold->e2->f2 |= EDGEINNER;
1962         facecopy(em, efa,hold);
1963
1964         hold = addfacelist(em, op,inner[numcuts-1],verts[1][numcuts],verts[1][numcuts+1],NULL,NULL);
1965         hold->e2->f2 |= EDGEINNER;
1966         facecopy(em, efa,hold);
1967
1968         //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
1969         //      hold->e1->h |= EM_FGON;
1970         //}
1971         // Add Fill Quads (if # cuts > 1)
1972
1973         for(i=0;i<numcuts-1;i++) {
1974                 hold = addfacelist(em, inner[i],verts[1][i+1],verts[1][i+2],inner[i+1],NULL,NULL);
1975                 hold->e1->f2 |= EDGEINNER;
1976                 hold->e3->f2 |= EDGEINNER;
1977                 facecopy(em, efa,hold);
1978
1979                 hold = addfacelist(em, inner[i],inner[i+1],verts[0][numcuts-1-i],verts[0][numcuts-i],NULL,NULL);
1980                 hold->e2->f2 |= EDGEINNER;
1981                 hold->e4->f2 |= EDGEINNER;
1982                 facecopy(em, efa,hold);
1983
1984                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
1985                 //      hold->e1->h |= EM_FGON;
1986                 //}
1987         }
1988
1989         //EM_fgon_flags(em);
1990
1991         MEM_freeN(inner);
1992 }
1993
1994 static void fill_tri_double(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1995 {
1996         EditEdge *cedge[2]={NULL, NULL};
1997         EditVert *v[3], **verts[2];
1998         EditFace *hold;
1999         short start=0, start2=0, vertsize,i;
2000
2001         v[0] = efa->v1;
2002         v[1] = efa->v2;
2003         v[2] = efa->v3;
2004
2005         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
2006         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
2007         if(efa->e3->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e1; start = 2; start2 = 0;}
2008
2009         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2010         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
2011         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
2012         //This is the index size of the verts array
2013         vertsize = numcuts+2;
2014
2015         // Is the original v1 the same as the first vert on the selected edge?
2016         // if not, the edge is running the opposite direction in this face so flip
2017         // the array to the correct direction
2018
2019         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
2020         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
2021         /*
2022         We should have something like this now
2023
2024                            end           start
2025                                 3   2   1   0
2026                 start2 0|---*---*---|
2027                                 |                /
2028                            1*      /
2029                                 |        /
2030                            2*   /
2031                                 | /
2032                  end2  3|
2033
2034         We will fill this case like this or this depending on even or odd cuts
2035                            |---*---*---|
2036                            | /   /   /
2037                            *   /   /
2038                            | /   /
2039                            *   /
2040                            | /
2041                            |
2042         */
2043
2044         // Make outside tri
2045         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
2046         hold->e3->f2 |= EDGEINNER;
2047         facecopy(em, efa,hold);
2048         // Make side faces
2049
2050         for(i=0;i<numcuts;i++) {
2051                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);
2052                 hold->e2->f2 |= EDGEINNER;
2053                 facecopy(em, efa,hold);
2054         }
2055 }
2056
2057 static void fill_quad_triple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
2058 {
2059         EditEdge *cedge[3]={0};
2060         EditVert *v[4], **verts[3];
2061         EditFace *hold;
2062         short start=0, start2=0, start3=0, vertsize, i, repeats;
2063
2064         v[0] = efa->v1;
2065         v[1] = efa->v2;
2066         v[2] = efa->v3;
2067         v[3] = efa->v4;
2068
2069         if(!(efa->e1->f & SELECT)) {
2070                 cedge[0] = efa->e2;
2071                 cedge[1] = efa->e3;
2072                 cedge[2] = efa->e4;
2073                 start = 1;start2 = 2;start3 = 3;
2074         }
2075         if(!(efa->e2->f & SELECT)) {
2076                 cedge[0] = efa->e3;
2077                 cedge[1] = efa->e4;
2078                 cedge[2] = efa->e1;
2079                 start = 2;start2 = 3;start3 = 0;
2080         }
2081         if(!(efa->e3->f & SELECT)) {
2082                 cedge[0] = efa->e4;
2083                 cedge[1] = efa->e1;
2084                 cedge[2] = efa->e2;
2085                 start = 3;start2 = 0;start3 = 1;
2086         }
2087         if(!(efa->e4->f & SELECT)) {
2088                 cedge[0] = efa->e1;
2089                 cedge[1] = efa->e2;
2090                 cedge[2] = efa->e3;
2091                 start = 0;start2 = 1;start3 = 2;
2092         }
2093         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2094         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
2095         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
2096         verts[2] = BLI_ghash_lookup(gh, cedge[2]);
2097         //This is the index size of the verts array
2098         vertsize = numcuts+2;
2099
2100         // Is the original v1 the same as the first vert on the selected edge?
2101         // if not, the edge is running the opposite direction in this face so flip
2102         // the array to the correct direction
2103
2104         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
2105         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
2106         if(verts[2][0] != v[start3]) {flipvertarray(verts[2],numcuts+2);}
2107         /*
2108          We should have something like this now
2109
2110          start2
2111          3   2   1   0
2112          start3 0|---*---*---|3
2113          |                 |
2114          1*                *2
2115          |                 |
2116          2*                *1
2117          |                 |
2118          3|-----------|0 start
2119
2120          We will fill this case like this or this depending on even or odd cuts
2121          there are a couple of differences. For odd cuts, there is a tri in the
2122          middle as well as 1 quad at the bottom (not including the extra quads
2123          for odd cuts > 1
2124
2125          For even cuts, there is a quad in the middle and 2 quads on the bottom
2126
2127          they are numbered here for clarity
2128
2129          1 outer tris and bottom quads
2130          2 inner tri or quad
2131          3 repeating quads
2132
2133          |---*---*---*---|
2134          |1/   /  \   \ 1|
2135          |/ 3 / \  3 \|
2136          *  /   2   \   *
2137          | /              \  |
2138          |/                     \ |
2139          *---------------*
2140          |        3             |
2141          |                         |
2142          *---------------*
2143          |                         |
2144          |        1             |
2145          |                         |
2146          |---------------|
2147
2148          |---*---*---*---*---|
2149          | 1/   /        \   \ 1|
2150          | /   /           \   \ |
2151          |/ 3 /          \ 3 \|
2152          *   /             \   *
2153          |  /                    \  |
2154          | /       2       \ |
2155          |/                              \|
2156          *-------------------*
2157          |                                 |
2158          |               3               |
2159          |                                 |
2160          *-------------------*
2161          |                                 |
2162          |               1               |
2163          |                                 |
2164          *-------------------*
2165          |                                 |
2166          |              1                 |
2167          |                                 |
2168          |-------------------|
2169
2170          */
2171
2172         // Make outside tris
2173         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
2174         hold->e3->f2 |= EDGEINNER;
2175         facecopy(em, efa,hold);
2176         hold = addfacelist(em, verts[1][vertsize-2],verts[1][vertsize-1],verts[2][1],NULL,NULL,NULL);
2177         hold->e3->f2 |= EDGEINNER;
2178         facecopy(em, efa,hold);
2179         // Make bottom quad
2180         hold = addfacelist(em, verts[0][0],verts[0][1],verts[2][vertsize-2],verts[2][vertsize-1],NULL,NULL);
2181         hold->e2->f2 |= EDGEINNER;
2182         facecopy(em, efa,hold);
2183         //If it is even cuts, add the 2nd lower quad
2184         if(numcuts % 2 == 0) {
2185                 hold = addfacelist(em, verts[0][1],verts[0][2],verts[2][vertsize-3],verts[2][vertsize-2],NULL,NULL);
2186                 hold->e2->f2 |= EDGEINNER;
2187                 facecopy(em, efa,hold);
2188                 // Also Make inner quad
2189                 hold = addfacelist(em, verts[1][numcuts/2],verts[1][(numcuts/2)+1],verts[2][numcuts/2],verts[0][(numcuts/2)+1],NULL,NULL);
2190                 hold->e3->f2 |= EDGEINNER;
2191                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2192                 //      hold->e3->h |= EM_FGON;
2193                 //}
2194                 facecopy(em, efa,hold);
2195                 repeats = (numcuts / 2) -1;
2196         } else {
2197                 // Make inner tri
2198                 hold = addfacelist(em, verts[1][(numcuts/2)+1],verts[2][(numcuts/2)+1],verts[0][(numcuts/2)+1],NULL,NULL,NULL);
2199                 hold->e2->f2 |= EDGEINNER;
2200                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2201                 //      hold->e2->h |= EM_FGON;
2202                 //}
2203                 facecopy(em, efa,hold);
2204                 repeats = ((numcuts+1) / 2)-1;
2205         }
2206
2207         // cuts for 1 and 2 do not have the repeating quads
2208         if(numcuts < 3) {repeats = 0;}
2209         for(i=0;i<repeats;i++) {
2210                 //Make side repeating Quads
2211                 hold = addfacelist(em, verts[1][i+1],verts[1][i+2],verts[0][vertsize-i-3],verts[0][vertsize-i-2],NULL,NULL);
2212                 hold->e2->f2 |= EDGEINNER;
2213                 facecopy(em, efa,hold);
2214                 hold = addfacelist(em, verts[1][vertsize-i-3],verts[1][vertsize-i-2],verts[2][i+1],verts[2][i+2],NULL,NULL);
2215                 hold->e4->f2 |= EDGEINNER;
2216                 facecopy(em, efa,hold);
2217         }
2218         // Do repeating bottom quads
2219         for(i=0;i<repeats;i++) {
2220                 if(numcuts % 2 == 1) {
2221                         hold = addfacelist(em, verts[0][1+i],verts[0][2+i],verts[2][vertsize-3-i],verts[2][vertsize-2-i],NULL,NULL);
2222                 } else {
2223                         hold = addfacelist(em, verts[0][2+i],verts[0][3+i],verts[2][vertsize-4-i],verts[2][vertsize-3-i],NULL,NULL);
2224                 }
2225                 hold->e2->f2 |= EDGEINNER;
2226                 facecopy(em, efa,hold);
2227         }
2228         //EM_fgon_flags(em);
2229 }
2230
2231 static void fill_quad_quadruple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, float smooth, float fractal, int beauty)
2232 {
2233         EditVert **verts[4], ***innerverts;
2234         EditFace *hold;
2235         EditEdge temp;
2236         short vertsize, i, j;
2237
2238         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2239         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2240         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2241         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2242         verts[3] = BLI_ghash_lookup(gh, efa->e4);
2243
2244         //This is the index size of the verts array
2245         vertsize = numcuts+2;
2246
2247         // Is the original v1 the same as the first vert on the selected edge?
2248         // if not, the edge is running the opposite direction in this face so flip
2249         // the array to the correct direction
2250
2251         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2252         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}
2253         if(verts[2][0] == efa->v3) {flipvertarray(verts[2],numcuts+2);}
2254         if(verts[3][0] == efa->v4) {flipvertarray(verts[3],numcuts+2);}
2255         /*
2256         We should have something like this now
2257                                           1
2258
2259                                 3   2   1   0
2260                            0|---*---*---|0
2261                                 |           |
2262                            1*           *1
2263                          2  |           |   4
2264                            2*           *2
2265                                 |           |
2266                            3|---*---*---|3
2267                                 3   2   1   0
2268
2269                                           3
2270         // we will fill a 2 dim array of editvert*s to make filling easier
2271         //  the innervert order is shown
2272
2273                                 0   0---1---2---3
2274                                         |   |   |   |
2275                                 1   0---1---2---3
2276                                         |   |   |   |
2277                                 2   0---1---2---3
2278                                         |   |   |   |
2279                                 3   0---1---2---3
2280
2281          */
2282         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts outer array");
2283         for(i=0;i<numcuts+2;i++) {
2284                 innerverts[i] = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts inner array");
2285         }
2286
2287         // first row is e1 last row is e3
2288         for(i=0;i<numcuts+2;i++) {
2289                 innerverts[0][i]                  = verts[0][(numcuts+1)-i];
2290                 innerverts[numcuts+1][i]  = verts[2][(numcuts+1)-i];
2291         }
2292
2293         for(i=1;i<=numcuts;i++) {
2294                 /* we create a fake edge for the next loop */
2295                 temp.v2 = innerverts[i][0]                      = verts[1][i];
2296                 temp.v1 = innerverts[i][numcuts+1]  = verts[3][i];
2297
2298                 for(j=1;j<=numcuts;j++) {
2299                         float percent= (float)j/(float)(numcuts+1);
2300
2301                         innerverts[i][(numcuts+1)-j]= subdivide_edge_addvert(em, &temp, smooth, fractal, beauty, percent);
2302                 }
2303         }
2304         // Fill with faces
2305         for(i=0;i<numcuts+1;i++) {
2306                 for(j=0;j<numcuts+1;j++) {
2307                         hold = addfacelist(em, innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],innerverts[i+1][j+1],NULL,NULL);
2308                         hold->e1->f2 = EDGENEW;
2309                         hold->e2->f2 = EDGENEW;
2310                         hold->e3->f2 = EDGENEW;
2311                         hold->e4->f2 = EDGENEW;
2312
2313                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2314                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2315                         if(i != numcuts) { hold->e3->f2 |= EDGEINNER; }
2316                         if(j != numcuts) { hold->e4->f2 |= EDGEINNER; }
2317
2318                         facecopy(em, efa,hold);
2319                 }
2320         }
2321         // Clean up our dynamic multi-dim array
2322         for(i=0;i<numcuts+2;i++) {
2323            MEM_freeN(innerverts[i]);
2324         }
2325         MEM_freeN(innerverts);
2326 }
2327
2328 static void fill_tri_triple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, float smooth, float fractal, int beauty)
2329 {
2330         EditVert **verts[3], ***innerverts;
2331         short vertsize, i, j;
2332         EditFace *hold;
2333         EditEdge temp;
2334
2335         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2336         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2337         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2338         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2339
2340         //This is the index size of the verts array
2341         vertsize = numcuts+2;
2342
2343         // Is the original v1 the same as the first vert on the selected edge?
2344         // if not, the edge is running the opposite direction in this face so flip
2345         // the array to the correct direction
2346
2347         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2348         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}
2349         if(verts[2][0] != efa->v3) {flipvertarray(verts[2],numcuts+2);}
2350         /*
2351         We should have something like this now
2352                                            3
2353
2354                                 3   2   1   0
2355                            0|---*---*---|3
2356                                 |                 /
2357                   1     1*              *2
2358                                 |         /
2359                            2*   *1         2
2360                                 |  /
2361                            3|/
2362                                  0
2363
2364         we will fill a 2 dim array of editvert*s to make filling easier
2365
2366                                                 3
2367
2368                          0  0---1---2---3---4
2369                                 | / | /  |/  | /
2370                          1  0---1----2---3
2371            1            | /  | / | /
2372                          2  0----1---2   2
2373                                 |  / |  /
2374                                 |/   |/
2375                          3  0---1
2376                                 |  /
2377                                 |/
2378                          4  0
2379
2380         */
2381
2382         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"tri-tri subdiv inner verts outer array");
2383         for(i=0;i<numcuts+2;i++) {
2384                   innerverts[i] = MEM_mallocN(sizeof(EditVert*)*((numcuts+2)-i),"tri-tri subdiv inner verts inner array");
2385         }
2386         //top row is e3 backwards
2387         for(i=0;i<numcuts+2;i++) {
2388                   innerverts[0][i]                = verts[2][(numcuts+1)-i];
2389         }
2390
2391         for(i=1;i<=numcuts+1;i++) {
2392                 //fake edge, first vert is from e1, last is from e2
2393                 temp.v1= innerverts[i][0]                         = verts[0][i];
2394                 temp.v2= innerverts[i][(numcuts+1)-i]  = verts[1][(numcuts+1)-i];
2395
2396                 for(j=1;j<(numcuts+1)-i;j++) {
2397                         float percent= (float)j/(float)((numcuts+1)-i);
2398
2399                         innerverts[i][((numcuts+1)-i)-j]= subdivide_edge_addvert(em, &temp, smooth, fractal, beauty, 1-percent);
2400                 }
2401         }
2402
2403         // Now fill the verts with happy little tris :)
2404         for(i=0;i<=numcuts+1;i++) {
2405                 for(j=0;j<(numcuts+1)-i;j++) {
2406                         //We always do the first tri
2407                         hold = addfacelist(em, innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],NULL,NULL,NULL);
2408                         hold->e1->f2 |= EDGENEW;
2409                         hold->e2->f2 |= EDGENEW;
2410                         hold->e3->f2 |= EDGENEW;
2411                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2412                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2413                         if(j+1 != (numcuts+1)-i) {hold->e3->f2 |= EDGEINNER;}
2414
2415                         facecopy(em, efa,hold);
2416                         //if there are more to come, we do the 2nd
2417                         if(j+1 <= numcuts-i) {
2418                                 hold = addfacelist(em, innerverts[i+1][j],innerverts[i+1][j+1],innerverts[i][j+1],NULL,NULL,NULL);
2419                                 facecopy(em, efa,hold);
2420                                 hold->e1->f2 |= EDGENEW;
2421                                 hold->e2->f2 |= EDGENEW;
2422                                 hold->e3->f2 |= EDGENEW;
2423                         }
2424                 }
2425         }
2426
2427         // Clean up our dynamic multi-dim array
2428         for(i=0;i<numcuts+2;i++) {
2429                 MEM_freeN(innerverts[i]);
2430         }
2431         MEM_freeN(innerverts);
2432 }
2433
2434 //Next two fill types are for knife exact only and are provided to allow for knifing through vertices
2435 //This means there is no multicut!
2436 static void fill_quad_doublevert(EditMesh *em, EditFace *efa, int v1, int v2)
2437 {
2438         EditFace *hold;
2439         /*
2440                 Depending on which two vertices have been knifed through (v1 and v2), we
2441                 triangulate like the patterns below.
2442                                 X-------|       |-------X
2443                                 | \     |       |     / |
2444                                 |   \   |       |   /   |
2445                                 |         \     |       | /         |
2446                                 --------X       X--------
2447         */
2448
2449         if(v1 == 1 && v2 == 3){
2450                 hold= addfacelist(em, efa->v1, efa->v2, efa->v3, 0, efa, NULL);
2451                 hold->e1->f2 |= EDGENEW;
2452                 hold->e2->f2 |= EDGENEW;
2453                 hold->e3->f2 |= EDGENEW;
2454                 hold->e3->f2 |= EDGEINNER;
2455                 facecopy(em, efa, hold);
2456
2457                 hold= addfacelist(em, efa->v1, efa->v3, efa->v4, 0, efa, NULL);
2458                 hold->e1->f2 |= EDGENEW;
2459                 hold->e2->f2 |= EDGENEW;
2460                 hold->e3->f2 |= EDGENEW;
2461                 hold->e1->f2 |= EDGEINNER;
2462                 facecopy(em, efa, hold);
2463         }
2464         else{
2465                 hold= addfacelist(em, efa->v1, efa->v2, efa->v4, 0, efa, NULL);
2466                 hold->e1->f2 |= EDGENEW;
2467                 hold->e2->f2 |= EDGENEW;
2468                 hold->e3->f2 |= EDGENEW;
2469                 hold->e2->f2 |= EDGEINNER;
2470                 facecopy(em, efa, hold);
2471
2472                 hold= addfacelist(em, efa->v2, efa->v3, efa->v4, 0, efa, NULL);
2473                 hold->e1->f2 |= EDGENEW;
2474                 hold->e2->f2 |= EDGENEW;
2475                 hold->e3->f2 |= EDGENEW;
2476                 hold->e3->f2 |= EDGEINNER;
2477                 facecopy(em, efa, hold);
2478         }
2479 }
2480
2481 static void fill_quad_singlevert(EditMesh *em, EditFace *efa, struct GHash *gh)
2482 {
2483         EditEdge *cedge=NULL;
2484         EditVert *v[4], **verts;
2485         EditFace *hold;
2486         short start=0, end, left, right, vertsize;
2487
2488         v[0] = efa->v1;
2489         v[1] = efa->v2;
2490         v[2] = efa->v3;
2491         v[3] = efa->v4;
2492
2493         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
2494         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
2495         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
2496         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}
2497
2498         // Point verts to the array of new verts for cedge
2499         verts = BLI_ghash_lookup(gh, cedge);
2500         //This is the index size of the verts array
2501         vertsize = 3;
2502
2503         // Is the original v1 the same as the first vert on the selected edge?
2504         // if not, the edge is running the opposite direction in this face so flip
2505         // the array to the correct direction
2506
2507         if(verts[0] != v[start]) {flipvertarray(verts,3);}
2508         end     = (start+1)%4;
2509         left   = (start+2)%4;
2510         right  = (start+3)%4;
2511
2512 /*
2513         We should have something like this now
2514
2515                           end            start
2516                            2     1     0
2517                            |-----*-----|
2518                            |               |
2519                            |               |
2520                            |               |
2521                            -------------
2522                           left     right
2523
2524         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
2525         and 0,1,2 are the indexes of the new verts stored in verts. We fill like
2526         this, depending on whether its vertex 'left' or vertex 'right' thats
2527         been knifed through...
2528
2529                                 |---*---|       |---*---|
2530                                 |  /    |       |    \  |
2531                                 | /             |       |         \ |
2532                                 |/              |       |          \|
2533                                 X--------       --------X
2534 */
2535
2536         if(v[left]->f1){
2537                 //triangle is composed of cutvert, end and left
2538                 hold = addfacelist(em, verts[1],v[end],v[left],NULL, NULL,NULL);
2539                 hold->e1->f2 |= EDGENEW;
2540                 hold->e2->f2 |= EDGENEW;
2541                 hold->e3->f2 |= EDGENEW;
2542                 hold->e3->f2 |= EDGEINNER;
2543                 facecopy(em, efa, hold);
2544
2545                 //quad is composed of cutvert, left, right and start
2546                 hold = addfacelist(em, verts[1],v[left],v[right],v[start], NULL, NULL);
2547                 hold->e1->f2 |= EDGENEW;
2548                 hold->e2->f2 |= EDGENEW;
2549                 hold->e3->f2 |= EDGENEW;
2550                 hold->e4->f2 |= EDGENEW;
2551                 hold->e1->f2 |= EDGEINNER;
2552                 facecopy(em, efa, hold);
2553         }
2554         else if(v[right]->f1){
2555                 //triangle is composed of cutvert, right and start
2556                 hold = addfacelist(em, verts[1],v[right],v[start], NULL, NULL, NULL);
2557                 hold->e1->f2 |= EDGENEW;
2558                 hold->e2->f2 |= EDGENEW;
2559                 hold->e3->f2 |= EDGENEW;
2560                 hold->e1->f2 |= EDGEINNER;
2561                 facecopy(em, efa, hold);
2562                 //quad is composed of cutvert, end, left, right
2563                 hold = addfacelist(em, verts[1],v[end], v[left], v[right], NULL, NULL);
2564                 hold->e1->f2 |= EDGENEW;
2565                 hold->e2->f2 |= EDGENEW;
2566                 hold->e3->f2 |= EDGENEW;
2567                 hold->e4->f2 |= EDGENEW;
2568                 hold->e4->f2 |= EDGEINNER;
2569                 facecopy(em, efa, hold);
2570         }
2571
2572 }
2573
2574 // This function takes an example edge, the current point to create and
2575 // the total # of points to create, then creates the point and return the
2576 // editvert pointer to it.
2577 static EditVert *subdivideedgenum(EditMesh *em, EditEdge *edge, int curpoint, int totpoint, float smooth, float fractal, int beauty)
2578 {
2579         EditVert *ev;
2580         float percent;
2581
2582         if (beauty & (B_PERCENTSUBD) && totpoint == 1)
2583                 //percent=(float)(edge->tmp.l)/32768.0f;
2584                 percent= edge->tmp.fp;
2585         else
2586                 percent= (float)curpoint/(float)(totpoint+1);
2587
2588         ev= subdivide_edge_addvert(em, edge, smooth, fractal, beauty, percent);
2589         ev->f = edge->v1->f;
2590
2591         return ev;
2592 }
2593
2594 void esubdivideflag(Object *obedit, EditMesh *em, int flag, float smooth, float fractal, int beauty, int numcuts, int corner_pattern, int seltype)
2595 {
2596         EditFace *ef;
2597         EditEdge *eed, *cedge, *sort[4];
2598         EditVert *eve, **templist;
2599         struct GHash *gh;
2600         float length[4], v1mat[3], v2mat[3], v3mat[3], v4mat[3];
2601         int i, j, edgecount, touchcount, facetype,hold;
2602         ModifierData *md= obedit->modifiers.first;
2603         int ctrl= 0; // XXX
2604
2605         //Set faces f1 to 0 cause we need it later
2606         for(ef=em->faces.first;ef;ef = ef->next) ef->f1 = 0;
2607         for(eve=em->verts.first; eve; eve=eve->next) {
2608                 if(!(beauty & B_KNIFE)) /* knife sets this flag for vertex cuts */
2609                         eve->f1 = 0;
2610                 eve->f2 = 0;
2611         }
2612
2613         for (; md; md=md->next) {
2614                 if (md->type==eModifierType_Mirror) {
2615                         MirrorModifierData *mmd = (MirrorModifierData*) md;
2616
2617                         if(mmd->flag & MOD_MIR_CLIPPING) {
2618                                 for (eve= em->verts.first; eve; eve= eve->next) {
2619                                         eve->f2= 0;
2620                                         switch(mmd->axis){
2621                                                 case 0:
2622                                                         if (fabs(eve->co[0]) < mmd->tolerance)
2623                                                                 eve->f2 |= 1;
2624                                                         break;
2625                                                 case 1:
2626                                                         if (fabs(eve->co[1]) < mmd->tolerance)
2627                                                                 eve->f2 |= 2;
2628                                                         break;
2629                                                 case 2:
2630                                                         if (fabs(eve->co[2]) < mmd->tolerance)
2631                                                                 eve->f2 |= 4;
2632                                                         break;
2633                                         }
2634                                 }
2635                         }
2636                 }
2637         }
2638
2639         //Flush vertex flags upward to the edges
2640         for(eed = em->edges.first;eed;eed = eed->next) {
2641                 //if(eed->f & flag && eed->v1->f == eed->v2->f) {
2642                 //      eed->f |= eed->v1->f;
2643                 // }
2644                 eed->f2 = 0;
2645                 if(eed->f & flag) {
2646                         eed->f2 |= EDGEOLD;
2647                 }
2648         }
2649
2650         // We store an array of verts for each edge that is subdivided,
2651         // we put this array as a value in a ghash which is keyed by the EditEdge*
2652
2653         // Now for beauty subdivide deselect edges based on length
2654         if(beauty & B_BEAUTY) {
2655                 for(ef = em->faces.first;ef;ef = ef->next) {
2656                         if(!ef->v4) {
2657                                 continue;
2658                         }
2659                         if(ef->f & SELECT) {
2660                                 VECCOPY(v1mat, ef->v1->co);
2661                                 VECCOPY(v2mat, ef->v2->co);
2662                                 VECCOPY(v3mat, ef->v3->co);
2663                                 VECCOPY(v4mat, ef->v4->co);
2664                                 mul_mat3_m4_v3(obedit->obmat, v1mat);
2665                                 mul_mat3_m4_v3(obedit->obmat, v2mat);
2666                                 mul_mat3_m4_v3(obedit->obmat, v3mat);
2667                                 mul_mat3_m4_v3(obedit->obmat, v4mat);
2668
2669                                 length[0] = len_v3v3(v1mat, v2mat);
2670                                 length[1] = len_v3v3(v2mat, v3mat);
2671                                 length[2] = len_v3v3(v3mat, v4mat);
2672                                 length[3] = len_v3v3(v4mat, v1mat);
2673                                 sort[0] = ef->e1;
2674                                 sort[1] = ef->e2;
2675                                 sort[2] = ef->e3;
2676                                 sort[3] = ef->e4;
2677
2678
2679                                 // Beauty Short Edges
2680                                 if(beauty & B_BEAUTY_SHORT) {
2681                                         for(j=0;j<2;j++) {
2682                                                 hold = -1;
2683                                                 for(i=0;i<4;i++) {
2684                                                         if(length[i] < 0) {
2685                                                                 continue;
2686                                                         } else if(hold == -1) {
2687                                                                 hold = i;
2688                                                         } else {
2689                                                                 if(length[hold] < length[i]) {
2690                                                                         hold = i;
2691                                                                 }
2692                                                         }
2693                                                 }
2694                                                 if (hold > -1) {
2695                                                         sort[hold]->f &= ~SELECT;
2696                                                         sort[hold]->f2 |= EDGENEW;
2697                                                         length[hold] = -1;
2698                                                 }
2699                                         }
2700                                 }
2701
2702                                 // Beauty Long Edges
2703                                 else {
2704                                          for(j=0;j<2;j++) {
2705                                                 hold = -1;
2706                                                 for(i=0;i<4;i++) {
2707                                                         if(length[i] < 0) {
2708                                                                 continue;
2709                                                         } else if(hold == -1) {
2710                                                                 hold = i;
2711                                                         } else {
2712                                                                 if(length[hold] > length[i]) {
2713                                                                         hold = i;
2714                                                                 }
2715                                                         }
2716                                                 }
2717                                                 if (hold > -1) {
2718                                                         sort[hold]->f &= ~SELECT;
2719                                                         sort[hold]->f2 |= EDGENEW;
2720                                                         length[hold] = -1;
2721                                                 }
2722                                         }
2723                                 }
2724                         }
2725                 }
2726         }
2727
2728         gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "subdivideedgenum gh");
2729
2730         // If we are knifing, We only need the selected edges that were cut, so deselect if it was not cut
2731         if(beauty & B_KNIFE) {
2732                 for(eed= em->edges.first;eed;eed=eed->next) {
2733                         if( eed->tmp.fp == 0 ) {
2734                                 EM_select_edge(eed,0);
2735                         }
2736                 }
2737         }
2738         // So for each edge, if it is selected, we allocate an array of size cuts+2
2739         // so we can have a place for the v1, the new verts and v2
2740         for(eed=em->edges.first;eed;eed = eed->next) {
2741                 if(eed->f & flag) {
2742                         templist = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"vertlist");
2743                         templist[0] = eed->v1;
2744                         for(i=0;i<numcuts;i++) {
2745                                 // This function creates the new vert and returns it back
2746                                 // to the array
2747                                 templist[i+1] = subdivideedgenum(em, eed, i+1, numcuts, smooth, fractal, beauty);
2748                                 //while we are here, we can copy edge info from the original edge
2749                                 cedge = addedgelist(em, templist[i],templist[i+1],eed);
2750                                 // Also set the edge f2 to EDGENEW so that we can use this info later
2751                                 cedge->f2 = EDGENEW;
2752                         }
2753                         templist[i+1] = eed->v2;
2754                         //Do the last edge too
2755                         cedge = addedgelist(em, templist[i],templist[i+1],eed);
2756                         cedge->f2 = EDGENEW;
2757                         // Now that the edge is subdivided, we can put its verts in the ghash
2758                         BLI_ghash_insert(gh, eed, templist);
2759                 }
2760         }
2761
2762 //      DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
2763         // Now for each face in the mesh we need to figure out How many edges were cut
2764         // and which filling method to use for that face
2765         for(ef = em->faces.first;ef;ef = ef->next) {
2766                 edgecount = 0;
2767                 facetype = 3;
2768                 if(ef->e1->f & flag) {edgecount++;}
2769                 if(ef->e2->f & flag) {edgecount++;}
2770                 if(ef->e3->f & flag) {edgecount++;}
2771                 if(ef->v4) {
2772                         facetype = 4;
2773                         if(ef->e4->f & flag) {edgecount++;}
2774                 }
2775                 if(facetype == 4) {
2776                         switch(edgecount) {
2777                                 case 0:
2778                                         if(beauty & B_KNIFE && numcuts == 1){
2779                                                 /*Test for when knifing through two opposite verts but no edges*/
2780                                                 touchcount = 0;
2781                                                 if(ef->v1->f1) touchcount++;
2782                                                 if(ef->v2->f1) touchcount++;
2783                                                 if(ef->v3->f1) touchcount++;
2784                                                 if(ef->v4->f1) touchcount++;
2785                                                 if(touchcount == 2){
2786                                                         if(ef->v1->f1 && ef->v3->f1){
2787                                                                 ef->f1 = SELECT;
2788                                                                 fill_quad_doublevert(em, ef, 1, 3);
2789                                                         }
2790                                                         else if(ef->v2->f1 && ef->v4->f1){
2791                                                                 ef->f1 = SELECT;
2792                                                                 fill_quad_doublevert(em, ef, 2, 4);
2793                                                         }
2794                                                 }
2795                                         }
2796                                         break;
2797
2798                                 case 1:
2799                                         if(beauty & B_KNIFE && numcuts == 1){
2800                                                 /*Test for when knifing through an edge and one vert*/
2801                                                 touchcount = 0;
2802                                                 if(ef->v1->f1) touchcount++;
2803                                                 if(ef->v2->f1) touchcount++;
2804                                                 if(ef->v3->f1) touchcount++;
2805                                                 if(ef->v4->f1) touchcount++;
2806
2807                                                 if(touchcount == 1){
2808                                                         if( (ef->e1->f & flag && ( !ef->e1->v1->f1 && !ef->e1->v2->f1 )) ||
2809                                                                 (ef->e2->f & flag && ( !ef->e2->v1->f1 && !ef->e2->v2->f1 )) ||
2810                                                                 (ef->e3->f & flag && ( !ef->e3->v1->f1 && !ef->e3->v2->f1 )) ||
2811                                                                 (ef->e4->f & flag && ( !ef->e4->v1->f1 && !ef->e4->v2->f1 )) ){
2812
2813                                                                 ef->f1 = SELECT;
2814                                                                 fill_quad_singlevert(em, ef, gh);
2815                                                         }
2816                                                         else{
2817                                                                 ef->f1 = SELECT;
2818                                                                 fill_quad_single(em, ef, gh, numcuts, seltype);
2819                                                         }
2820                                                 }
2821                                                 else{
2822                                                         ef->f1 = SELECT;
2823                                                         fill_quad_single(em, ef, gh, numcuts, seltype);
2824                                                 }
2825                                         }
2826                                         else{
2827                                                 ef->f1 = SELECT;
2828                                                 fill_quad_single(em, ef, gh, numcuts, seltype);
2829                                         }
2830                                         break;
2831                                 case 2: ef->f1 = SELECT;
2832                                         // if there are 2, we check if edge 1 and 3 are either both on or off that way
2833                                         // we can tell if the selected pair is Adjacent or Opposite of each other
2834                                         if((ef->e1->f & flag && ef->e3->f & flag) ||
2835                                            (ef->e2->f & flag && ef->e4->f & flag)) {
2836                                                 fill_quad_double_op(em, ef, gh, numcuts);
2837                                         }else{
2838                                                 switch(corner_pattern) {
2839                                                         case 0: fill_quad_double_adj_path(em, ef, gh, numcuts); break;
2840                                                         case 1: fill_quad_double_adj_inner(em, ef, gh, numcuts); break;
2841                                                         case 2: fill_quad_double_adj_fan(em, ef, gh, numcuts); break;
2842                                                 }
2843
2844                                         }
2845                                                 break;
2846                                 case 3: ef->f1 = SELECT;
2847                                         fill_quad_triple(em, ef, gh, numcuts);
2848                                         break;
2849                                 case 4: ef->f1 = SELECT;
2850                                         fill_quad_quadruple(em, ef, gh, numcuts, smooth, fractal, beauty);
2851                                         break;
2852                         }
2853                 } else {
2854                         switch(edgecount) {
2855                                 case 0: break;
2856                                 case 1: ef->f1 = SELECT;
2857                                         fill_tri_single(em, ef, gh, numcuts, seltype);
2858                                         break;
2859                                 case 2: ef->f1 = SELECT;
2860                                         fill_tri_double(em, ef, gh, numcuts);
2861                                         break;
2862                                 case 3: ef->f1 = SELECT;
2863                                         fill_tri_triple(em, ef, gh, numcuts, smooth, fractal, beauty);
2864                                         break;
2865                         }
2866                 }
2867         }
2868
2869         // Delete Old Edges and Faces
2870         for(eed = em->edges.first;eed;eed = eed->next) {
2871                 if(BLI_ghash_haskey(gh,eed)) {
2872                         eed->f1 = SELECT;
2873                 } else {
2874                         eed->f1 = 0;
2875                 }
2876         }
2877         free_tagged_edges_faces(em, em->edges.first, em->faces.first);
2878
2879         if(seltype == SUBDIV_SELECT_ORIG  && !ctrl) {
2880                 /* bugfix: vertex could get flagged as "not-selected"
2881                 // solution: clear flags before, not at the same time as setting SELECT flag -dg
2882                 */
2883                 for(eed = em->edges.first;eed;eed = eed->next) {
2884                         if(!(eed->f2 & EDGENEW || eed->f2 & EDGEOLD)) {
2885                                 eed->f &= !flag;
2886                                 EM_select_edge(eed,0);
2887                         }
2888                 }
2889                 for(eed = em->edges.first;eed;eed = eed->next) {
2890                         if(eed->f2 & EDGENEW || eed->f2 & EDGEOLD) {
2891                                 eed->f |= flag;
2892                                 EM_select_edge(eed,1);
2893                         }
2894                 }
2895         } else if ((seltype == SUBDIV_SELECT_INNER || seltype == SUBDIV_SELECT_INNER_SEL)|| ctrl) {
2896                 for(eed = em->edges.first;eed;eed = eed->next) {
2897                         if(eed->f2 & EDGEINNER) {
2898                                 eed->f |= flag;
2899                                 EM_select_edge(eed,1);
2900                                 if(eed->v1->f & EDGEINNER) eed->v1->f |= SELECT;
2901                                 if(eed->v2->f & EDGEINNER) eed->v2->f |= SELECT;
2902                         }else{
2903                                 eed->f &= !flag;
2904                                 EM_select_edge(eed,0);
2905                         }
2906                 }
2907         } else if(seltype == SUBDIV_SELECT_LOOPCUT){
2908                 for(eed = em->edges.first;eed;eed = eed->next) {
2909                         if(eed->f2 & DOUBLEOPFILL){
2910                                 eed->f |= flag;
2911                                 EM_select_edge(eed,1);
2912                         }else{
2913                                 eed->f &= !flag;
2914                                 EM_select_edge(eed,0);
2915                         }
2916                 }
2917         }
2918          if(em->selectmode & SCE_SELECT_VERTEX) {
2919                  for(eed = em->edges.first;eed;eed = eed->next) {
2920                         if(eed->f & SELECT) {
2921                                 eed->v1->f |= SELECT;
2922                                 eed->v2->f |= SELECT;
2923                         }
2924                 }
2925         }
2926
2927         //fix hide flags for edges. First pass, hide edges of hidden faces
2928         for(ef=em->faces.first; ef; ef=ef->next){
2929                 if(ef->h){
2930                         ef->e1->h |= 1;
2931                         ef->e2->h |= 1;
2932                         ef->e3->h |= 1;
2933                         if(ef->e4) ef->e4->h |= 1;
2934                 }
2935         }
2936         //second pass: unhide edges of visible faces adjacent to hidden faces
2937         for(ef=em->faces.first; ef; ef=ef->next){
2938                 if(ef->h == 0){
2939                         ef->e1->h &= ~1;
2940                         ef->e2->h &= ~1;
2941                         ef->e3->h &= ~1;
2942                         if(ef->e4) ef->e4->h &= ~1;
2943                 }
2944         }
2945
2946         //third pass: unhide edges that have both verts visible
2947         //(these were missed if all faces were hidden, bug #21976)
2948         for(eed=em->edges.first; eed; eed=eed->next){
2949                 if(eed->v1->h == 0 && eed->v2->h == 0)
2950                         eed->h &= ~1;
2951         }
2952
2953         // Free the ghash and call MEM_freeN on all the value entries to return
2954         // that memory
2955         BLI_ghash_free(gh, NULL, (GHashValFreeFP)MEM_freeN);
2956
2957         EM_selectmode_flush(em);
2958         for(ef=em->faces.first;ef;ef = ef->next) {
2959                 if(ef->e4) {
2960                         if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) &&
2961                          (ef->e3->f & SELECT && ef->e4->f & SELECT) ) {
2962                                 ef->f |= SELECT;
2963                         }
2964                 } else {
2965                         if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) && ef->e3->f & SELECT) {
2966                                 ef->f |= SELECT;
2967                         }
2968                 }
2969         }
2970
2971         recalc_editnormals(em);
2972 }
2973
2974 static int count_selected_edges(EditEdge *ed)
2975 {
2976         int totedge = 0;
2977         while(ed) {
2978                 ed->tmp.p = 0;
2979                 if( ed->f & SELECT ) totedge++;
2980                 ed= ed->next;
2981         }
2982         return totedge;
2983 }
2984
2985 /* hurms, as if this makes code readable! It's pointerpointer hiding... (ton) */
2986 typedef EditFace *EVPtr;
2987 typedef EVPtr EVPTuple[2];
2988
2989 /** builds EVPTuple array efaa of face tuples (in fact pointers to EditFaces)
2990         sharing one edge.
2991         arguments: selected edge list, face list.
2992         Edges will also be tagged accordingly (see eed->f2)               */
2993
2994 static int collect_quadedges(EVPTuple *efaa, EditEdge *eed, EditFace *efa)
2995 {
2996         EditEdge *e1, *e2, *e3;
2997         EVPtr *evp;
2998         int i = 0;
2999
3000         /* run through edges, if selected, set pointer edge-> facearray */
3001         while(eed) {
3002                 eed->f2= 0;
3003                 eed->f1= 0;
3004                 if( eed->f & SELECT ) {
3005                         eed->tmp.p = (EditVert *) (&efaa[i]);
3006                         i++;
3007                 }
3008                 else eed->tmp.p = NULL;
3009
3010                 eed= eed->next;
3011         }
3012
3013
3014         /* find edges pointing to 2 faces by procedure:
3015
3016         - run through faces and their edges, increase
3017           face counter e->f1 for each face
3018         */
3019
3020         while(efa) {
3021                 efa->f1= 0;
3022                 if(efa->v4==0 && (efa->f & SELECT)) {  /* if selected triangle */
3023                         e1= efa->e1;
3024                         e2= efa->e2;