DAG_id_tag_update was being called with non object ID's and OB_RECALC_* flags which...
[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, 0);
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         BLI_movelisttolist(&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         BLI_movelisttolist(&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_WARNING, "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, 0);
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, 0);
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, 0);
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, 0);
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, 0);
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, 0);
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_WARNING, "No valid vertices are selected");
995                 return OPERATOR_CANCELLED;
996         }
997
998         DAG_id_tag_update(obedit->data, 0);
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_WARNING, "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, 0);
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_WARNING, "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, 0);
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_validate_data(&em->fdata, target->data, target->v4 ? 4 : 3);
1523         CustomData_em_interp(&em->fdata, &source->data, NULL, (float*)w, 1, target->data);
1524 }
1525
1526 static void fill_quad_single(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1527 {
1528         EditEdge *cedge=NULL;
1529         EditVert *v[4], **verts;
1530         EditFace *hold;
1531         short start=0, end, left, right, vertsize,i;
1532
1533         v[0] = efa->v1;
1534         v[1] = efa->v2;
1535         v[2] = efa->v3;
1536         v[3] = efa->v4;
1537
1538         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1539         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
1540         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
1541         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}
1542
1543         // Point verts to the array of new verts for cedge
1544         verts = BLI_ghash_lookup(gh, cedge);
1545         //This is the index size of the verts array
1546         vertsize = numcuts+2;
1547
1548         // Is the original v1 the same as the first vert on the selected edge?
1549         // if not, the edge is running the opposite direction in this face so flip
1550         // the array to the correct direction
1551
1552         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1553         end     = (start+1)%4;
1554         left   = (start+2)%4;
1555         right  = (start+3)%4;
1556
1557         /*
1558         We should have something like this now
1559
1560                           end            start
1561                            3   2   1   0
1562                            |---*---*---|
1563                            |               |
1564                            |               |
1565                            |               |
1566                            -------------
1567                           left     right
1568
1569         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
1570         and 0,1,2... are the indexes of the new verts stored in verts
1571
1572         We will fill this case like this or this depending on even or odd cuts
1573
1574                            |---*---*---|                  |---*---|
1575                            |  /  \  |             |  / \  |
1576                            | /     \ |            | /   \ |
1577                            |/            \|               |/     \|
1578                            -------------                  ---------
1579         */
1580
1581         // Make center face
1582         if(vertsize % 2 == 0) {
1583                 hold = addfacelist(em, verts[(vertsize-1)/2],verts[((vertsize-1)/2)+1],v[left],v[right], NULL,NULL);
1584                 hold->e2->f2 |= EDGEINNER;
1585                 hold->e4->f2 |= EDGEINNER;
1586         }else{
1587                 hold = addfacelist(em, verts[(vertsize-1)/2],v[left],v[right],NULL, NULL,NULL);
1588                 hold->e1->f2 |= EDGEINNER;
1589                 hold->e3->f2 |= EDGEINNER;
1590         }
1591         facecopy(em, efa,hold);
1592
1593         // Make side faces
1594         for(i=0;i<(vertsize-1)/2;i++) {
1595                 hold = addfacelist(em, verts[i],verts[i+1],v[right],NULL,NULL,NULL);
1596                 facecopy(em, efa,hold);
1597                 if(i+1 != (vertsize-1)/2) {
1598                         if(seltype == SUBDIV_SELECT_INNER) {
1599                                 hold->e2->f2 |= EDGEINNER;
1600                         }
1601                 }
1602                 hold = addfacelist(em, verts[vertsize-2-i],verts[vertsize-1-i],v[left],NULL,NULL,NULL);
1603                 facecopy(em, efa,hold);
1604                 if(i+1 != (vertsize-1)/2) {
1605                         if(seltype == SUBDIV_SELECT_INNER) {
1606                                  hold->e3->f2 |= EDGEINNER;
1607                         }
1608                 }
1609         }
1610 }
1611
1612 static void fill_tri_single(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1613 {
1614         EditEdge *cedge=NULL;
1615         EditVert *v[3], **verts;
1616         EditFace *hold;
1617         short start=0, end, op, vertsize,i;
1618
1619         v[0] = efa->v1;
1620         v[1] = efa->v2;
1621         v[2] = efa->v3;
1622
1623         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1624         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
1625         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
1626
1627         // Point verts to the array of new verts for cedge
1628         verts = BLI_ghash_lookup(gh, cedge);
1629         //This is the index size of the verts array
1630         vertsize = numcuts+2;
1631
1632         // Is the original v1 the same as the first vert on the selected edge?
1633         // if not, the edge is running the opposite direction in this face so flip
1634         // the array to the correct direction
1635
1636         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1637            end  = (start+1)%3;
1638            op    = (start+2)%3;
1639
1640         /*
1641         We should have something like this now
1642
1643                           end            start
1644                            3   2   1   0
1645                            |---*---*---|
1646                            \               |
1647                                  \               |
1648                                    \       |
1649                                          \       |
1650                                            \   |
1651                                                  \ |
1652                                                    |op
1653
1654         where start,end,op are indexes of EditFace->v1, etc (stored in v)
1655         and 0,1,2... are the indexes of the new verts stored in verts
1656
1657         We will fill this case like this or this depending on even or odd cuts
1658
1659                            3   2   1   0
1660                            |---*---*---|
1661                            \    \  \   |
1662                                  \      \ \  |
1663                                    \   \ \ |
1664                                          \  \ \|
1665                                            \ \\|
1666                                                  \ |
1667                                                    |op
1668         */
1669
1670         // Make side faces
1671         for(i=0;i<(vertsize-1);i++) {
1672                 hold = addfacelist(em, verts[i],verts[i+1],v[op],NULL,NULL,NULL);
1673                 if(i+1 != vertsize-1) {
1674                         if(seltype == SUBDIV_SELECT_INNER) {
1675                                  hold->e2->f2 |= EDGEINNER;
1676                         }
1677                 }
1678                 facecopy(em, efa,hold);
1679         }
1680 }
1681
1682 static void fill_quad_double_op(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1683 {
1684         EditEdge *cedge[2]={NULL, NULL};
1685         EditVert *v[4], **verts[2];
1686         EditFace *hold;
1687         short start=0, end, left, right, vertsize,i;
1688
1689         v[0] = efa->v1;
1690         v[1] = efa->v2;
1691         v[2] = efa->v3;
1692         v[3] = efa->v4;
1693
1694         if(efa->e1->f & SELECT)   { cedge[0] = efa->e1;  cedge[1] = efa->e3; start = 0;}
1695         else if(efa->e2->f & SELECT)      { cedge[0] = efa->e2;  cedge[1] = efa->e4; start = 1;}
1696
1697         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1698         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1699         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1700         //This is the index size of the verts array
1701         vertsize = numcuts+2;
1702
1703         // Is the original v1 the same as the first vert on the selected edge?
1704         // if not, the edge is running the opposite direction in this face so flip
1705         // the array to the correct direction
1706
1707         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1708         end     = (start+1)%4;
1709         left   = (start+2)%4;
1710         right  = (start+3)%4;
1711         if(verts[1][0] != v[left]) {flipvertarray(verts[1],numcuts+2);}
1712         /*
1713         We should have something like this now
1714
1715                           end            start
1716                            3   2   1   0
1717                            |---*---*---|
1718                            |               |
1719                            |               |
1720                            |               |
1721                            |---*---*---|
1722                            0   1   2   3
1723                           left     right
1724
1725         We will fill this case like this or this depending on even or odd cuts
1726
1727                            |---*---*---|
1728                            |   |   |   |
1729                            |   |   |   |
1730                            |   |   |   |
1731                            |---*---*---|
1732         */
1733
1734         // Make side faces
1735         for(i=0;i<vertsize-1;i++) {
1736                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-2-i],verts[1][vertsize-1-i],NULL,NULL);
1737                 if(i < vertsize-2) {
1738                         hold->e2->f2 |= EDGEINNER;
1739                         hold->e2->f2 |= DOUBLEOPFILL;
1740                 }
1741                 facecopy(em, efa,hold);
1742         }
1743 }
1744
1745 static void fill_quad_double_adj_path(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1746 {
1747         EditEdge *cedge[2]={NULL, NULL};
1748         EditVert *v[4], **verts[2];
1749         EditFace *hold;
1750         short start=0, start2=0, vertsize,i;
1751         int ctrl= 0; // XXX
1752
1753         v[0] = efa->v1;
1754         v[1] = efa->v2;
1755         v[2] = efa->v3;
1756         v[3] = efa->v4;
1757
1758         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
1759         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
1760         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3;}
1761         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0;}
1762
1763         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1764         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1765         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1766         //This is the index size of the verts array
1767         vertsize = numcuts+2;
1768
1769         // Is the original v1 the same as the first vert on the selected edge?
1770         // if not, the edge is running the opposite direction in this face so flip
1771         // the array to the correct direction
1772
1773         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1774         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1775         /*
1776         We should have something like this now
1777
1778                            end           start
1779                                 3   2   1   0
1780                 start2 0|---*---*---|
1781                                 |                  |
1782                            1*              |
1783                                 |                  |
1784                            2*              |
1785                                 |                  |
1786                  end2  3|-----------|
1787
1788         We will fill this case like this or this depending on even or odd cuts
1789                            |---*---*---|
1790                            | /   /   / |
1791                            *   /   /   |
1792                            | /   /       |
1793                            *   /           |
1794                            | /           |
1795                            |-----------|
1796         */
1797
1798         // Make outside tris
1799         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
1800         /* when ctrl is depressed, only want verts on the cutline selected */
1801         if (ctrl)
1802                 hold->e3->f2 |= EDGEINNER;
1803         facecopy(em, efa,hold);
1804         hold = addfacelist(em, verts[0][0],verts[1][vertsize-1],v[(start2+2)%4],NULL,NULL,NULL);
1805         /* when ctrl is depressed, only want verts on the cutline selected */
1806         if (ctrl)
1807                 hold->e1->f2 |= EDGEINNER;
1808         facecopy(em, efa,hold);
1809         //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
1810         //      hold->e1->h |= EM_FGON;
1811         //}
1812         // Make side faces
1813
1814         for(i=0;i<numcuts;i++) {
1815                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);
1816                 hold->e2->f2 |= EDGEINNER;
1817                 facecopy(em, efa,hold);
1818         }
1819         //EM_fgon_flags(em);
1820
1821 }
1822
1823 static void fill_quad_double_adj_fan(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1824 {
1825         EditEdge *cedge[2]={NULL, NULL};
1826         EditVert *v[4], *op=NULL, **verts[2];
1827         EditFace *hold;
1828         short start=0, start2=0, vertsize,i;
1829
1830         v[0] = efa->v1;
1831         v[1] = efa->v2;
1832         v[2] = efa->v3;
1833         v[3] = efa->v4;
1834
1835         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1836         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1837         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1838         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1839
1840
1841         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1842         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1843         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1844         //This is the index size of the verts array
1845         vertsize = numcuts+2;
1846
1847         // Is the original v1 the same as the first vert on the selected edge?
1848         // if not, the edge is running the opposite direction in this face so flip
1849         // the array to the correct direction
1850
1851         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1852         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1853         /*
1854         We should have something like this now
1855
1856                            end           start
1857                                 3   2   1   0
1858                 start2 0|---*---*---|
1859                                 |                  |
1860                            1*              |
1861                                 |                  |
1862                            2*              |
1863                                 |                  |
1864                  end2  3|-----------|op
1865
1866         We will fill this case like this or this (warning horrible ascii art follows)
1867                            |---*---*---|
1868                            | \  \   \  |
1869                            *---\  \  \ |
1870                            |   \ \ \  \|
1871                            *---- \ \  \ |
1872                            |    ---  \\\|
1873                            |-----------|
1874         */
1875
1876         for(i=0;i<=numcuts;i++) {
1877                 hold = addfacelist(em, op,verts[1][numcuts-i],verts[1][numcuts-i+1],NULL,NULL,NULL);
1878                 hold->e1->f2 |= EDGEINNER;
1879                 facecopy(em, efa,hold);
1880
1881                 hold = addfacelist(em, op,verts[0][i],verts[0][i+1],NULL,NULL,NULL);
1882                 hold->e3->f2 |= EDGEINNER;
1883                 facecopy(em, efa,hold);
1884         }
1885 }
1886
1887 static void fill_quad_double_adj_inner(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1888 {
1889         EditEdge *cedge[2]={NULL, NULL};
1890         EditVert *v[4], *op=NULL, **verts[2],**inner;
1891         EditFace *hold;
1892         short start=0, start2=0, vertsize,i;
1893         float co[3];
1894
1895         v[0] = efa->v1;
1896         v[1] = efa->v2;
1897         v[2] = efa->v3;
1898         v[3] = efa->v4;
1899
1900         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1901         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1902         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1903         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1904
1905
1906         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1907         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1908         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1909         //This is the index size of the verts array
1910         vertsize = numcuts+2;
1911
1912         // Is the original v1 the same as the first vert on the selected edge?
1913         // if not, the edge is running the opposite direction in this face so flip
1914         // the array to the correct direction
1915
1916         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1917         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1918         /*
1919         We should have something like this now
1920
1921                            end           start
1922                                 3   2   1   0
1923                 start2 0|---*---*---|
1924                                 |                  |
1925                            1*              |
1926                                 |                  |
1927                            2*              |
1928                                 |                  |
1929                  end2  3|-----------|op
1930
1931         We will fill this case like this or this (warning horrible ascii art follows)
1932                            |---*-----*---|
1933                            | *     /     |
1934                            *   \ /       |
1935                            |    *        |
1936                            | /    \          |
1937                            *        \    |
1938                            |           \ |
1939                            |-------------|
1940         */
1941
1942         // Add Inner Vert(s)
1943         inner = MEM_mallocN(sizeof(EditVert*)*numcuts,"New inner verts");
1944
1945         for(i=0;i<numcuts;i++) {
1946                 co[0] = (verts[0][numcuts-i]->co[0] + verts[1][i+1]->co[0] ) / 2 ;
1947                 co[1] = (verts[0][numcuts-i]->co[1] + verts[1][i+1]->co[1] ) / 2 ;
1948                 co[2] = (verts[0][numcuts-i]->co[2] + verts[1][i+1]->co[2] ) / 2 ;
1949                 inner[i] = addvertlist(em, co, NULL);
1950                 inner[i]->f2 |= EDGEINNER;
1951
1952                 EM_data_interp_from_verts(em, verts[0][numcuts-i], verts[1][i+1], inner[i], 0.5f);
1953         }
1954
1955         // Add Corner Quad
1956         hold = addfacelist(em, verts[0][numcuts+1],verts[1][1],inner[0],verts[0][numcuts],NULL,NULL);
1957         hold->e2->f2 |= EDGEINNER;
1958         hold->e3->f2 |= EDGEINNER;
1959         facecopy(em, efa,hold);
1960         // Add Bottom Quads
1961         hold = addfacelist(em, verts[0][0],verts[0][1],inner[numcuts-1],op,NULL,NULL);
1962         hold->e2->f2 |= EDGEINNER;
1963         facecopy(em, efa,hold);
1964
1965         hold = addfacelist(em, op,inner[numcuts-1],verts[1][numcuts],verts[1][numcuts+1],NULL,NULL);
1966         hold->e2->f2 |= EDGEINNER;
1967         facecopy(em, efa,hold);
1968
1969         //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
1970         //      hold->e1->h |= EM_FGON;
1971         //}
1972         // Add Fill Quads (if # cuts > 1)
1973
1974         for(i=0;i<numcuts-1;i++) {
1975                 hold = addfacelist(em, inner[i],verts[1][i+1],verts[1][i+2],inner[i+1],NULL,NULL);
1976                 hold->e1->f2 |= EDGEINNER;
1977                 hold->e3->f2 |= EDGEINNER;
1978                 facecopy(em, efa,hold);
1979
1980                 hold = addfacelist(em, inner[i],inner[i+1],verts[0][numcuts-1-i],verts[0][numcuts-i],NULL,NULL);
1981                 hold->e2->f2 |= EDGEINNER;
1982                 hold->e4->f2 |= EDGEINNER;
1983                 facecopy(em, efa,hold);
1984
1985                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
1986                 //      hold->e1->h |= EM_FGON;
1987                 //}
1988         }
1989
1990         //EM_fgon_flags(em);
1991
1992         MEM_freeN(inner);
1993 }
1994
1995 static void fill_tri_double(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1996 {
1997         EditEdge *cedge[2]={NULL, NULL};
1998         EditVert *v[3], **verts[2];
1999         EditFace *hold;
2000         short start=0, start2=0, vertsize,i;
2001
2002         v[0] = efa->v1;
2003         v[1] = efa->v2;
2004         v[2] = efa->v3;
2005
2006         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
2007         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
2008         if(efa->e3->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e1; start = 2; start2 = 0;}
2009
2010         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2011         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
2012         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
2013         //This is the index size of the verts array
2014         vertsize = numcuts+2;
2015
2016         // Is the original v1 the same as the first vert on the selected edge?
2017         // if not, the edge is running the opposite direction in this face so flip
2018         // the array to the correct direction
2019
2020         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
2021         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
2022         /*
2023         We should have something like this now
2024
2025                            end           start
2026                                 3   2   1   0
2027                 start2 0|---*---*---|
2028                                 |                /
2029                            1*      /
2030                                 |        /
2031                            2*   /
2032                                 | /
2033                  end2  3|
2034
2035         We will fill this case like this or this depending on even or odd cuts
2036                            |---*---*---|
2037                            | /   /   /
2038                            *   /   /
2039                            | /   /
2040                            *   /
2041                            | /
2042                            |
2043         */
2044
2045         // Make outside tri
2046         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
2047         hold->e3->f2 |= EDGEINNER;
2048         facecopy(em, efa,hold);
2049         // Make side faces
2050
2051         for(i=0;i<numcuts;i++) {
2052                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);
2053                 hold->e2->f2 |= EDGEINNER;
2054                 facecopy(em, efa,hold);
2055         }
2056 }
2057
2058 static void fill_quad_triple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
2059 {
2060         EditEdge *cedge[3]={0};
2061         EditVert *v[4], **verts[3];
2062         EditFace *hold;
2063         short start=0, start2=0, start3=0, vertsize, i, repeats;
2064
2065         v[0] = efa->v1;
2066         v[1] = efa->v2;
2067         v[2] = efa->v3;
2068         v[3] = efa->v4;
2069
2070         if(!(efa->e1->f & SELECT)) {
2071                 cedge[0] = efa->e2;
2072                 cedge[1] = efa->e3;
2073                 cedge[2] = efa->e4;
2074                 start = 1;start2 = 2;start3 = 3;
2075         }
2076         if(!(efa->e2->f & SELECT)) {
2077                 cedge[0] = efa->e3;
2078                 cedge[1] = efa->e4;
2079                 cedge[2] = efa->e1;
2080                 start = 2;start2 = 3;start3 = 0;
2081         }
2082         if(!(efa->e3->f & SELECT)) {
2083                 cedge[0] = efa->e4;
2084                 cedge[1] = efa->e1;
2085                 cedge[2] = efa->e2;
2086                 start = 3;start2 = 0;start3 = 1;
2087         }
2088         if(!(efa->e4->f & SELECT)) {
2089                 cedge[0] = efa->e1;
2090                 cedge[1] = efa->e2;
2091                 cedge[2] = efa->e3;
2092                 start = 0;start2 = 1;start3 = 2;
2093         }
2094         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2095         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
2096         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
2097         verts[2] = BLI_ghash_lookup(gh, cedge[2]);
2098         //This is the index size of the verts array
2099         vertsize = numcuts+2;
2100
2101         // Is the original v1 the same as the first vert on the selected edge?
2102         // if not, the edge is running the opposite direction in this face so flip
2103         // the array to the correct direction
2104
2105         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
2106         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
2107         if(verts[2][0] != v[start3]) {flipvertarray(verts[2],numcuts+2);}
2108         /*
2109          We should have something like this now
2110
2111          start2
2112          3   2   1   0
2113          start3 0|---*---*---|3
2114          |                 |
2115          1*                *2
2116          |                 |
2117          2*                *1
2118          |                 |
2119          3|-----------|0 start
2120
2121          We will fill this case like this or this depending on even or odd cuts
2122          there are a couple of differences. For odd cuts, there is a tri in the
2123          middle as well as 1 quad at the bottom (not including the extra quads
2124          for odd cuts > 1
2125
2126          For even cuts, there is a quad in the middle and 2 quads on the bottom
2127
2128          they are numbered here for clarity
2129
2130          1 outer tris and bottom quads
2131          2 inner tri or quad
2132          3 repeating quads
2133
2134          |---*---*---*---|
2135          |1/   /  \   \ 1|
2136          |/ 3 / \  3 \|
2137          *  /   2   \   *
2138          | /              \  |
2139          |/                     \ |
2140          *---------------*
2141          |        3             |
2142          |                         |
2143          *---------------*
2144          |                         |
2145          |        1             |
2146          |                         |
2147          |---------------|
2148
2149          |---*---*---*---*---|
2150          | 1/   /        \   \ 1|
2151          | /   /           \   \ |
2152          |/ 3 /          \ 3 \|
2153          *   /             \   *
2154          |  /                    \  |
2155          | /       2       \ |
2156          |/                              \|
2157          *-------------------*
2158          |                                 |
2159          |               3               |
2160          |                                 |
2161          *-------------------*
2162          |                                 |
2163          |               1               |
2164          |                                 |
2165          *-------------------*
2166          |                                 |
2167          |              1                 |
2168          |                                 |
2169          |-------------------|
2170
2171          */
2172
2173         // Make outside tris
2174         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
2175         hold->e3->f2 |= EDGEINNER;
2176         facecopy(em, efa,hold);
2177         hold = addfacelist(em, verts[1][vertsize-2],verts[1][vertsize-1],verts[2][1],NULL,NULL,NULL);
2178         hold->e3->f2 |= EDGEINNER;
2179         facecopy(em, efa,hold);
2180         // Make bottom quad
2181         hold = addfacelist(em, verts[0][0],verts[0][1],verts[2][vertsize-2],verts[2][vertsize-1],NULL,NULL);
2182         hold->e2->f2 |= EDGEINNER;
2183         facecopy(em, efa,hold);
2184         //If it is even cuts, add the 2nd lower quad
2185         if(numcuts % 2 == 0) {
2186                 hold = addfacelist(em, verts[0][1],verts[0][2],verts[2][vertsize-3],verts[2][vertsize-2],NULL,NULL);
2187                 hold->e2->f2 |= EDGEINNER;
2188                 facecopy(em, efa,hold);
2189                 // Also Make inner quad
2190                 hold = addfacelist(em, verts[1][numcuts/2],verts[1][(numcuts/2)+1],verts[2][numcuts/2],verts[0][(numcuts/2)+1],NULL,NULL);
2191                 hold->e3->f2 |= EDGEINNER;
2192                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2193                 //      hold->e3->h |= EM_FGON;
2194                 //}
2195                 facecopy(em, efa,hold);
2196                 repeats = (numcuts / 2) -1;
2197         } else {
2198                 // Make inner tri
2199                 hold = addfacelist(em, verts[1][(numcuts/2)+1],verts[2][(numcuts/2)+1],verts[0][(numcuts/2)+1],NULL,NULL,NULL);
2200                 hold->e2->f2 |= EDGEINNER;
2201                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2202                 //      hold->e2->h |= EM_FGON;
2203                 //}
2204                 facecopy(em, efa,hold);
2205                 repeats = ((numcuts+1) / 2)-1;
2206         }
2207
2208         // cuts for 1 and 2 do not have the repeating quads
2209         if(numcuts < 3) {repeats = 0;}
2210         for(i=0;i<repeats;i++) {
2211                 //Make side repeating Quads
2212                 hold = addfacelist(em, verts[1][i+1],verts[1][i+2],verts[0][vertsize-i-3],verts[0][vertsize-i-2],NULL,NULL);
2213                 hold->e2->f2 |= EDGEINNER;
2214                 facecopy(em, efa,hold);
2215                 hold = addfacelist(em, verts[1][vertsize-i-3],verts[1][vertsize-i-2],verts[2][i+1],verts[2][i+2],NULL,NULL);
2216                 hold->e4->f2 |= EDGEINNER;
2217                 facecopy(em, efa,hold);
2218         }
2219         // Do repeating bottom quads
2220         for(i=0;i<repeats;i++) {
2221                 if(numcuts % 2 == 1) {
2222                         hold = addfacelist(em, verts[0][1+i],verts[0][2+i],verts[2][vertsize-3-i],verts[2][vertsize-2-i],NULL,NULL);
2223                 } else {
2224                         hold = addfacelist(em, verts[0][2+i],verts[0][3+i],verts[2][vertsize-4-i],verts[2][vertsize-3-i],NULL,NULL);
2225                 }
2226                 hold->e2->f2 |= EDGEINNER;
2227                 facecopy(em, efa,hold);
2228         }
2229         //EM_fgon_flags(em);
2230 }
2231
2232 static void fill_quad_quadruple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, float smooth, float fractal, int beauty)
2233 {
2234         EditVert **verts[4], ***innerverts;
2235         EditFace *hold;
2236         EditEdge temp;
2237         short vertsize, i, j;
2238
2239         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2240         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2241         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2242         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2243         verts[3] = BLI_ghash_lookup(gh, efa->e4);
2244
2245         //This is the index size of the verts array
2246         vertsize = numcuts+2;
2247
2248         // Is the original v1 the same as the first vert on the selected edge?
2249         // if not, the edge is running the opposite direction in this face so flip
2250         // the array to the correct direction
2251
2252         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2253         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}
2254         if(verts[2][0] == efa->v3) {flipvertarray(verts[2],numcuts+2);}
2255         if(verts[3][0] == efa->v4) {flipvertarray(verts[3],numcuts+2);}
2256         /*
2257         We should have something like this now
2258                                           1
2259
2260                                 3   2   1   0
2261                            0|---*---*---|0
2262                                 |           |
2263                            1*           *1
2264                          2  |           |   4
2265                            2*           *2
2266                                 |           |
2267                            3|---*---*---|3
2268                                 3   2   1   0
2269
2270                                           3
2271         // we will fill a 2 dim array of editvert*s to make filling easier
2272         //  the innervert order is shown
2273
2274                                 0   0---1---2---3
2275                                         |   |   |   |
2276                                 1   0---1---2---3
2277                                         |   |   |   |
2278                                 2   0---1---2---3
2279                                         |   |   |   |
2280                                 3   0---1---2---3
2281
2282          */
2283         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts outer array");
2284         for(i=0;i<numcuts+2;i++) {
2285                 innerverts[i] = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts inner array");
2286         }
2287
2288         // first row is e1 last row is e3
2289         for(i=0;i<numcuts+2;i++) {
2290                 innerverts[0][i]                  = verts[0][(numcuts+1)-i];
2291                 innerverts[numcuts+1][i]  = verts[2][(numcuts+1)-i];
2292         }
2293
2294         for(i=1;i<=numcuts;i++) {
2295                 /* we create a fake edge for the next loop */
2296                 temp.v2 = innerverts[i][0]                      = verts[1][i];
2297                 temp.v1 = innerverts[i][numcuts+1]  = verts[3][i];
2298
2299                 for(j=1;j<=numcuts;j++) {
2300                         float percent= (float)j/(float)(numcuts+1);
2301
2302                         innerverts[i][(numcuts+1)-j]= subdivide_edge_addvert(em, &temp, smooth, fractal, beauty, percent);
2303                 }
2304         }
2305         // Fill with faces
2306         for(i=0;i<numcuts+1;i++) {
2307                 for(j=0;j<numcuts+1;j++) {
2308                         hold = addfacelist(em, innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],innerverts[i+1][j+1],NULL,NULL);
2309                         hold->e1->f2 = EDGENEW;
2310                         hold->e2->f2 = EDGENEW;
2311                         hold->e3->f2 = EDGENEW;
2312                         hold->e4->f2 = EDGENEW;
2313
2314                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2315                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2316                         if(i != numcuts) { hold->e3->f2 |= EDGEINNER; }
2317                         if(j != numcuts) { hold->e4->f2 |= EDGEINNER; }
2318
2319                         facecopy(em, efa,hold);
2320                 }
2321         }
2322         // Clean up our dynamic multi-dim array
2323         for(i=0;i<numcuts+2;i++) {
2324            MEM_freeN(innerverts[i]);
2325         }
2326         MEM_freeN(innerverts);
2327 }
2328
2329 static void fill_tri_triple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, float smooth, float fractal, int beauty)
2330 {
2331         EditVert **verts[3], ***innerverts;
2332         short vertsize, i, j;
2333         EditFace *hold;
2334         EditEdge temp;
2335
2336         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2337         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2338         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2339         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2340
2341         //This is the index size of the verts array
2342         vertsize = numcuts+2;
2343
2344         // Is the original v1 the same as the first vert on the selected edge?
2345         // if not, the edge is running the opposite direction in this face so flip
2346         // the array to the correct direction
2347
2348         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2349         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}
2350         if(verts[2][0] != efa->v3) {flipvertarray(verts[2],numcuts+2);}
2351         /*
2352         We should have something like this now
2353                                            3
2354
2355                                 3   2   1   0
2356                            0|---*---*---|3
2357                                 |                 /
2358                   1     1*              *2
2359                                 |         /
2360                            2*   *1         2
2361                                 |  /
2362                            3|/
2363                                  0
2364
2365         we will fill a 2 dim array of editvert*s to make filling easier
2366
2367                                                 3
2368
2369                          0  0---1---2---3---4
2370                                 | / | /  |/  | /
2371                          1  0---1----2---3
2372            1            | /  | / | /
2373                          2  0----1---2   2
2374                                 |  / |  /
2375                                 |/   |/
2376                          3  0---1
2377                                 |  /
2378                                 |/
2379                          4  0
2380
2381         */
2382
2383         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"tri-tri subdiv inner verts outer array");
2384         for(i=0;i<numcuts+2;i++) {
2385                   innerverts[i] = MEM_mallocN(sizeof(EditVert*)*((numcuts+2)-i),"tri-tri subdiv inner verts inner array");
2386         }
2387         //top row is e3 backwards
2388         for(i=0;i<numcuts+2;i++) {
2389                   innerverts[0][i]                = verts[2][(numcuts+1)-i];
2390         }
2391
2392         for(i=1;i<=numcuts+1;i++) {
2393                 //fake edge, first vert is from e1, last is from e2
2394                 temp.v1= innerverts[i][0]                         = verts[0][i];
2395                 temp.v2= innerverts[i][(numcuts+1)-i]  = verts[1][(numcuts+1)-i];
2396
2397                 for(j=1;j<(numcuts+1)-i;j++) {
2398                         float percent= (float)j/(float)((numcuts+1)-i);
2399
2400                         innerverts[i][((numcuts+1)-i)-j]= subdivide_edge_addvert(em, &temp, smooth, fractal, beauty, 1-percent);
2401                 }
2402         }
2403
2404         // Now fill the verts with happy little tris :)
2405         for(i=0;i<=numcuts+1;i++) {
2406                 for(j=0;j<(numcuts+1)-i;j++) {
2407                         //We always do the first tri
2408                         hold = addfacelist(em, innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],NULL,NULL,NULL);
2409                         hold->e1->f2 |= EDGENEW;
2410                         hold->e2->f2 |= EDGENEW;
2411                         hold->e3->f2 |= EDGENEW;
2412                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2413                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2414                         if(j+1 != (numcuts+1)-i) {hold->e3->f2 |= EDGEINNER;}
2415
2416                         facecopy(em, efa,hold);
2417                         //if there are more to come, we do the 2nd
2418                         if(j+1 <= numcuts-i) {
2419                                 hold = addfacelist(em, innerverts[i+1][j],innerverts[i+1][j+1],innerverts[i][j+1],NULL,NULL,NULL);
2420                                 facecopy(em, efa,hold);
2421                                 hold->e1->f2 |= EDGENEW;
2422                                 hold->e2->f2 |= EDGENEW;
2423                                 hold->e3->f2 |= EDGENEW;
2424                         }
2425                 }
2426         }
2427
2428         // Clean up our dynamic multi-dim array
2429         for(i=0;i<numcuts+2;i++) {
2430                 MEM_freeN(innerverts[i]);
2431         }
2432         MEM_freeN(innerverts);
2433 }
2434
2435 //Next two fill types are for knife exact only and are provided to allow for knifing through vertices
2436 //This means there is no multicut!
2437 static void fill_quad_doublevert(EditMesh *em, EditFace *efa, int v1, int v2)
2438 {
2439         EditFace *hold;
2440         /*
2441                 Depending on which two vertices have been knifed through (v1 and v2), we
2442                 triangulate like the patterns below.
2443                                 X-------|       |-------X
2444                                 | \     |       |     / |
2445                                 |   \   |       |   /   |
2446                                 |         \     |       | /         |
2447                                 --------X       X--------
2448         */
2449
2450         if(v1 == 1 && v2 == 3){
2451                 hold= addfacelist(em, efa->v1, efa->v2, efa->v3, 0, efa, NULL);
2452                 hold->e1->f2 |= EDGENEW;
2453                 hold->e2->f2 |= EDGENEW;
2454                 hold->e3->f2 |= EDGENEW;
2455                 hold->e3->f2 |= EDGEINNER;
2456                 facecopy(em, efa, hold);
2457
2458                 hold= addfacelist(em, efa->v1, efa->v3, efa->v4, 0, efa, NULL);
2459                 hold->e1->f2 |= EDGENEW;
2460                 hold->e2->f2 |= EDGENEW;
2461                 hold->e3->f2 |= EDGENEW;
2462                 hold->e1->f2 |= EDGEINNER;
2463                 facecopy(em, efa, hold);
2464         }
2465         else{
2466                 hold= addfacelist(em, efa->v1, efa->v2, efa->v4, 0, efa, NULL);
2467                 hold->e1->f2 |= EDGENEW;
2468                 hold->e2->f2 |= EDGENEW;
2469                 hold->e3->f2 |= EDGENEW;
2470                 hold->e2->f2 |= EDGEINNER;
2471                 facecopy(em, efa, hold);
2472
2473                 hold= addfacelist(em, efa->v2, efa->v3, efa->v4, 0, efa, NULL);
2474                 hold->e1->f2 |= EDGENEW;
2475                 hold->e2->f2 |= EDGENEW;
2476                 hold->e3->f2 |= EDGENEW;
2477                 hold->e3->f2 |= EDGEINNER;
2478                 facecopy(em, efa, hold);
2479         }
2480 }
2481
2482 static void fill_quad_singlevert(EditMesh *em, EditFace *efa, struct GHash *gh)
2483 {
2484         EditEdge *cedge=NULL;
2485         EditVert *v[4], **verts;
2486         EditFace *hold;
2487         short start=0, end, left, right, vertsize;
2488
2489         v[0] = efa->v1;
2490         v[1] = efa->v2;
2491         v[2] = efa->v3;
2492         v[3] = efa->v4;
2493
2494         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
2495         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
2496         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
2497         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}
2498
2499         // Point verts to the array of new verts for cedge
2500         verts = BLI_ghash_lookup(gh, cedge);
2501         //This is the index size of the verts array
2502         vertsize = 3;
2503
2504         // Is the original v1 the same as the first vert on the selected edge?
2505         // if not, the edge is running the opposite direction in this face so flip
2506         // the array to the correct direction
2507
2508         if(verts[0] != v[start]) {flipvertarray(verts,3);}
2509         end     = (start+1)%4;
2510         left   = (start+2)%4;
2511         right  = (start+3)%4;
2512
2513 /*
2514         We should have something like this now
2515
2516                           end            start
2517                            2     1     0
2518                            |-----*-----|
2519                            |               |
2520                            |               |
2521                            |               |
2522                            -------------
2523                           left     right
2524
2525         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
2526         and 0,1,2 are the indexes of the new verts stored in verts. We fill like
2527         this, depending on whether its vertex 'left' or vertex 'right' thats
2528         been knifed through...
2529
2530                                 |---*---|       |---*---|
2531                                 |  /    |       |    \  |
2532                                 | /             |       |         \ |
2533                                 |/              |       |          \|
2534                                 X--------       --------X
2535 */
2536
2537         if(v[left]->f1){
2538                 //triangle is composed of cutvert, end and left
2539                 hold = addfacelist(em, verts[1],v[end],v[left],NULL, NULL,NULL);
2540                 hold->e1->f2 |= EDGENEW;
2541                 hold->e2->f2 |= EDGENEW;
2542                 hold->e3->f2 |= EDGENEW;
2543                 hold->e3->f2 |= EDGEINNER;
2544                 facecopy(em, efa, hold);
2545
2546                 //quad is composed of cutvert, left, right and start
2547                 hold = addfacelist(em, verts[1],v[left],v[right],v[start], NULL, NULL);
2548                 hold->e1->f2 |= EDGENEW;
2549                 hold->e2->f2 |= EDGENEW;
2550                 hold->e3->f2 |= EDGENEW;
2551                 hold->e4->f2 |= EDGENEW;
2552                 hold->e1->f2 |= EDGEINNER;
2553                 facecopy(em, efa, hold);
2554         }
2555         else if(v[right]->f1){
2556                 //triangle is composed of cutvert, right and start
2557                 hold = addfacelist(em, verts[1],v[right],v[start], NULL, NULL, NULL);
2558                 hold->e1->f2 |= EDGENEW;
2559                 hold->e2->f2 |= EDGENEW;
2560                 hold->e3->f2 |= EDGENEW;
2561                 hold->e1->f2 |= EDGEINNER;
2562                 facecopy(em, efa, hold);
2563                 //quad is composed of cutvert, end, left, right
2564                 hold = addfacelist(em, verts[1],v[end], v[left], v[right], NULL, NULL);
2565                 hold->e1->f2 |= EDGENEW;
2566                 hold->e2->f2 |= EDGENEW;
2567                 hold->e3->f2 |= EDGENEW;
2568                 hold->e4->f2 |= EDGENEW;
2569                 hold->e4->f2 |= EDGEINNER;
2570                 facecopy(em, efa, hold);
2571         }
2572
2573 }
2574
2575 // This function takes an example edge, the current point to create and
2576 // the total # of points to create, then creates the point and return the
2577 // editvert pointer to it.
2578 static EditVert *subdivideedgenum(EditMesh *em, EditEdge *edge, int curpoint, int totpoint, float smooth, float fractal, int beauty)
2579 {
2580         EditVert *ev;
2581         float percent;
2582
2583         if (beauty & (B_PERCENTSUBD) && totpoint == 1)
2584                 //percent=(float)(edge->tmp.l)/32768.0f;
2585                 percent= edge->tmp.fp;
2586         else
2587                 percent= (float)curpoint/(float)(totpoint+1);
2588
2589         ev= subdivide_edge_addvert(em, edge, smooth, fractal, beauty, percent);
2590         ev->f = edge->v1->f;
2591
2592         return ev;
2593 }
2594
2595 void esubdivideflag(Object *obedit, EditMesh *em, int flag, float smooth, float fractal, int beauty, int numcuts, int corner_pattern, int seltype)
2596 {
2597         EditFace *ef;
2598         EditEdge *eed, *cedge, *sort[4];
2599         EditVert *eve, **templist;
2600         struct GHash *gh;
2601         float length[4], v1mat[3], v2mat[3], v3mat[3], v4mat[3];
2602         int i, j, edgecount, touchcount, facetype,hold;
2603         ModifierData *md= obedit->modifiers.first;
2604         int ctrl= 0; // XXX
2605
2606         //Set faces f1 to 0 cause we need it later
2607         for(ef=em->faces.first;ef;ef = ef->next) ef->f1 = 0;
2608         for(eve=em->verts.first; eve; eve=eve->next) {
2609                 if(!(beauty & B_KNIFE)) /* knife sets this flag for vertex cuts */
2610                         eve->f1 = 0;
2611                 eve->f2 = 0;
2612         }
2613
2614         for (; md; md=md->next) {
2615                 if (md->type==eModifierType_Mirror) {
2616                         MirrorModifierData *mmd = (MirrorModifierData*) md;
2617
2618                         if(mmd->flag & MOD_MIR_CLIPPING) {
2619                                 for (eve= em->verts.first; eve; eve= eve->next) {
2620                                         eve->f2= 0;
2621                                         switch(mmd->axis){
2622                                                 case 0:
2623                                                         if (fabs(eve->co[0]) < mmd->tolerance)
2624                                                                 eve->f2 |= 1;
2625                                                         break;
2626                                                 case 1:
2627                                                         if (fabs(eve->co[1]) < mmd->tolerance)
2628                                                                 eve->f2 |= 2;
2629                                                         break;
2630                                                 case 2:
2631                                                         if (fabs(eve->co[2]) < mmd->tolerance)
2632                                                                 eve->f2 |= 4;
2633                                                         break;
2634                                         }
2635                                 }
2636                         }
2637                 }
2638         }
2639
2640         //Flush vertex flags upward to the edges
2641         for(eed = em->edges.first;eed;eed = eed->next) {
2642                 //if(eed->f & flag && eed->v1->f == eed->v2->f) {
2643                 //      eed->f |= eed->v1->f;
2644                 // }
2645                 eed->f2 = 0;
2646                 if(eed->f & flag) {
2647                         eed->f2 |= EDGEOLD;
2648                 }
2649         }
2650
2651         // We store an array of verts for each edge that is subdivided,
2652         // we put this array as a value in a ghash which is keyed by the EditEdge*
2653
2654         // Now for beauty subdivide deselect edges based on length
2655         if(beauty & B_BEAUTY) {
2656                 for(ef = em->faces.first;ef;ef = ef->next) {
2657                         if(!ef->v4) {
2658                                 continue;
2659                         }
2660                         if(ef->f & SELECT) {
2661                                 VECCOPY(v1mat, ef->v1->co);
2662                                 VECCOPY(v2mat, ef->v2->co);
2663                                 VECCOPY(v3mat, ef->v3->co);
2664                                 VECCOPY(v4mat, ef->v4->co);
2665                                 mul_mat3_m4_v3(obedit->obmat, v1mat);
2666                                 mul_mat3_m4_v3(obedit->obmat, v2mat);
2667                                 mul_mat3_m4_v3(obedit->obmat, v3mat);
2668                                 mul_mat3_m4_v3(obedit->obmat, v4mat);
2669
2670                                 length[0] = len_v3v3(v1mat, v2mat);
2671                                 length[1] = len_v3v3(v2mat, v3mat);
2672                                 length[2] = len_v3v3(v3mat, v4mat);
2673                                 length[3] = len_v3v3(v4mat, v1mat);
2674                                 sort[0] = ef->e1;
2675                                 sort[1] = ef->e2;
2676                                 sort[2] = ef->e3;
2677                                 sort[3] = ef->e4;
2678
2679
2680                                 // Beauty Short Edges
2681                                 if(beauty & B_BEAUTY_SHORT) {
2682                                         for(j=0;j<2;j++) {
2683                                                 hold = -1;
2684                                                 for(i=0;i<4;i++) {
2685                                                         if(length[i] < 0) {
2686                                                                 continue;
2687                                                         } else if(hold == -1) {
2688                                                                 hold = i;
2689                                                         } else {
2690                                                                 if(length[hold] < length[i]) {
2691                                                                         hold = i;
2692                                                                 }
2693                                                         }
2694                                                 }
2695                                                 if (hold > -1) {
2696                                                         sort[hold]->f &= ~SELECT;
2697                                                         sort[hold]->f2 |= EDGENEW;
2698                                                         length[hold] = -1;
2699                                                 }
2700                                         }
2701                                 }
2702
2703                                 // Beauty Long Edges
2704                                 else {
2705                                          for(j=0;j<2;j++) {
2706                                                 hold = -1;
2707                                                 for(i=0;i<4;i++) {
2708                                                         if(length[i] < 0) {
2709                                                                 continue;
2710                                                         } else if(hold == -1) {
2711                                                                 hold = i;
2712                                                         } else {
2713                                                                 if(length[hold] > length[i]) {
2714                                                                         hold = i;
2715                                                                 }
2716                                                         }
2717                                                 }
2718                                                 if (hold > -1) {
2719                                                         sort[hold]->f &= ~SELECT;
2720                                                         sort[hold]->f2 |= EDGENEW;
2721                                                         length[hold] = -1;
2722                                                 }
2723                                         }
2724                                 }
2725                         }
2726                 }
2727         }
2728
2729         gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "subdivideedgenum gh");
2730
2731         // If we are knifing, We only need the selected edges that were cut, so deselect if it was not cut
2732         if(beauty & B_KNIFE) {
2733                 for(eed= em->edges.first;eed;eed=eed->next) {
2734                         if( eed->tmp.fp == 0 ) {
2735                                 EM_select_edge(eed,0);
2736                         }
2737                 }
2738         }
2739         // So for each edge, if it is selected, we allocate an array of size cuts+2
2740         // so we can have a place for the v1, the new verts and v2
2741         for(eed=em->edges.first;eed;eed = eed->next) {
2742                 if(eed->f & flag) {
2743                         templist = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"vertlist");
2744                         templist[0] = eed->v1;
2745                         for(i=0;i<numcuts;i++) {
2746                                 // This function creates the new vert and returns it back
2747                                 // to the array
2748                                 templist[i+1] = subdivideedgenum(em, eed, i+1, numcuts, smooth, fractal, beauty);
2749                                 //while we are here, we can copy edge info from the original edge
2750                                 cedge = addedgelist(em, templist[i],templist[i+1],eed);
2751                                 // Also set the edge f2 to EDGENEW so that we can use this info later
2752                                 cedge->f2 = EDGENEW;
2753                         }
2754                         templist[i+1] = eed->v2;
2755                         //Do the last edge too
2756                         cedge = addedgelist(em, templist[i],templist[i+1],eed);
2757                         cedge->f2 = EDGENEW;
2758                         // Now that the edge is subdivided, we can put its verts in the ghash
2759                         BLI_ghash_insert(gh, eed, templist);
2760                 }
2761         }
2762
2763 //      DAG_id_tag_update(obedit->data, 0);
2764         // Now for each face in the mesh we need to figure out How many edges were cut
2765         // and which filling method to use for that face
2766         for(ef = em->faces.first;ef;ef = ef->next) {
2767                 edgecount = 0;
2768                 facetype = 3;
2769                 if(ef->e1->f & flag) {edgecount++;}
2770                 if(ef->e2->f & flag) {edgecount++;}
2771                 if(ef->e3->f & flag) {edgecount++;}
2772                 if(ef->v4) {
2773                         facetype = 4;
2774                         if(ef->e4->f & flag) {edgecount++;}
2775                 }
2776                 if(facetype == 4) {
2777                         switch(edgecount) {
2778                                 case 0:
2779                                         if(beauty & B_KNIFE && numcuts == 1){
2780                                                 /*Test for when knifing through two opposite verts but no edges*/
2781                                                 touchcount = 0;
2782                                                 if(ef->v1->f1) touchcount++;
2783                                                 if(ef->v2->f1) touchcount++;
2784                                                 if(ef->v3->f1) touchcount++;
2785                                                 if(ef->v4->f1) touchcount++;
2786                                                 if(touchcount == 2){
2787                                                         if(ef->v1->f1 && ef->v3->f1){
2788                                                                 ef->f1 = SELECT;
2789                                                                 fill_quad_doublevert(em, ef, 1, 3);
2790                                                         }
2791                                                         else if(ef->v2->f1 && ef->v4->f1){
2792                                                                 ef->f1 = SELECT;
2793                                                                 fill_quad_doublevert(em, ef, 2, 4);
2794                                                         }
2795                                                 }
2796                                         }
2797                                         break;
2798
2799                                 case 1:
2800                                         if(beauty & B_KNIFE && numcuts == 1){
2801                                                 /*Test for when knifing through an edge and one vert*/
2802                                                 touchcount = 0;
2803                                                 if(ef->v1->f1) touchcount++;
2804                                                 if(ef->v2->f1) touchcount++;
2805                                                 if(ef->v3->f1) touchcount++;
2806                                                 if(ef->v4->f1) touchcount++;
2807
2808                                                 if(touchcount == 1){
2809                                                         if( (ef->e1->f & flag && ( !ef->e1->v1->f1 && !ef->e1->v2->f1 )) ||
2810                                                                 (ef->e2->f & flag && ( !ef->e2->v1->f1 && !ef->e2->v2->f1 )) ||
2811                                                                 (ef->e3->f & flag && ( !ef->e3->v1->f1 && !ef->e3->v2->f1 )) ||
2812                                                                 (ef->e4->f & flag && ( !ef->e4->v1->f1 && !ef->e4->v2->f1 )) ){
2813
2814                                                                 ef->f1 = SELECT;
2815                                                                 fill_quad_singlevert(em, ef, gh);
2816                                                         }
2817                                                         else{
2818                                                                 ef->f1 = SELECT;
2819                                                                 fill_quad_single(em, ef, gh, numcuts, seltype);
2820                                                         }
2821                                                 }
2822                                                 else{
2823                                                         ef->f1 = SELECT;
2824                                                         fill_quad_single(em, ef, gh, numcuts, seltype);
2825                                                 }
2826                                         }
2827                                         else{
2828                                                 ef->f1 = SELECT;
2829                                                 fill_quad_single(em, ef, gh, numcuts, seltype);
2830                                         }
2831                                         break;
2832                                 case 2: ef->f1 = SELECT;
2833                                         // if there are 2, we check if edge 1 and 3 are either both on or off that way
2834                                         // we can tell if the selected pair is Adjacent or Opposite of each other
2835                                         if((ef->e1->f & flag && ef->e3->f & flag) ||
2836                                            (ef->e2->f & flag && ef->e4->f & flag)) {
2837                                                 fill_quad_double_op(em, ef, gh, numcuts);
2838                                         }else{
2839                                                 switch(corner_pattern) {
2840                                                         case 0: fill_quad_double_adj_path(em, ef, gh, numcuts); break;
2841                                                         case 1: fill_quad_double_adj_inner(em, ef, gh, numcuts); break;
2842                                                         case 2: fill_quad_double_adj_fan(em, ef, gh, numcuts); break;
2843                                                 }
2844
2845                                         }
2846                                                 break;
2847                                 case 3: ef->f1 = SELECT;
2848                                         fill_quad_triple(em, ef, gh, numcuts);
2849                                         break;
2850                                 case 4: ef->f1 = SELECT;
2851                                         fill_quad_quadruple(em, ef, gh, numcuts, smooth, fractal, beauty);
2852                                         break;
2853                         }
2854                 } else {
2855                         switch(edgecount) {
2856                                 case 0: break;
2857                                 case 1: ef->f1 = SELECT;
2858                                         fill_tri_single(em, ef, gh, numcuts, seltype);
2859                                         break;
2860                                 case 2: ef->f1 = SELECT;
2861                                         fill_tri_double(em, ef, gh, numcuts);
2862                                         break;
2863                                 case 3: ef->f1 = SELECT;
2864                                         fill_tri_triple(em, ef, gh, numcuts, smooth, fractal, beauty);
2865                                         break;
2866                         }
2867                 }
2868         }
2869
2870         // Delete Old Edges and Faces
2871         for(eed = em->edges.first;eed;eed = eed->next) {
2872                 if(BLI_ghash_haskey(gh,eed)) {
2873                         eed->f1 = SELECT;
2874                 } else {
2875                         eed->f1 = 0;
2876                 }
2877         }
2878         free_tagged_edges_faces(em, em->edges.first, em->faces.first);
2879
2880         if(seltype == SUBDIV_SELECT_ORIG  && !ctrl) {
2881                 /* bugfix: vertex could get flagged as "not-selected"
2882                 // solution: clear flags before, not at the same time as setting SELECT flag -dg
2883                 */
2884                 for(eed = em->edges.first;eed;eed = eed->next) {
2885                         if(!(eed->f2 & EDGENEW || eed->f2 & EDGEOLD)) {
2886                                 eed->f &= !flag;
2887                                 EM_select_edge(eed,0);
2888                         }
2889                 }
2890                 for(eed = em->edges.first;eed;eed = eed->next) {
2891                         if(eed->f2 & EDGENEW || eed->f2 & EDGEOLD) {
2892                                 eed->f |= flag;
2893                                 EM_select_edge(eed,1);
2894                         }
2895                 }
2896         } else if ((seltype == SUBDIV_SELECT_INNER || seltype == SUBDIV_SELECT_INNER_SEL)|| ctrl) {
2897                 for(eed = em->edges.first;eed;eed = eed->next) {
2898                         if(eed->f2 & EDGEINNER) {
2899                                 eed->f |= flag;
2900                                 EM_select_edge(eed,1);
2901                                 if(eed->v1->f & EDGEINNER) eed->v1->f |= SELECT;
2902                                 if(eed->v2->f & EDGEINNER) eed->v2->f |= SELECT;
2903                         }else{
2904                                 eed->f &= !flag;
2905                                 EM_select_edge(eed,0);
2906                         }
2907                 }
2908         } else if(seltype == SUBDIV_SELECT_LOOPCUT){
2909                 for(eed = em->edges.first;eed;eed = eed->next) {
2910                         if(eed->f2 & DOUBLEOPFILL){
2911                                 eed->f |= flag;
2912                                 EM_select_edge(eed,1);
2913                         }else{
2914                                 eed->f &= !flag;
2915                                 EM_select_edge(eed,0);
2916                         }
2917                 }
2918         }
2919          if(em->selectmode & SCE_SELECT_VERTEX) {
2920                  for(eed = em->edges.first;eed;eed = eed->next) {
2921                         if(eed->f & SELECT) {
2922                                 eed->v1->f |= SELECT;
2923                                 eed->v2->f |= SELECT;
2924                         }
2925                 }
2926         }
2927
2928         //fix hide flags for edges. First pass, hide edges of hidden faces
2929         for(ef=em->faces.first; ef; ef=ef->next){
2930                 if(ef->h){
2931                         ef->e1->h |= 1;
2932                         ef->e2->h |= 1;
2933                         ef->e3->h |= 1;
2934                         if(ef->e4) ef->e4->h |= 1;
2935                 }
2936         }
2937         //second pass: unhide edges of visible faces adjacent to hidden faces
2938         for(ef=em->faces.first; ef; ef=ef->next){
2939                 if(ef->h == 0){
2940                         ef->e1->h &= ~1;
2941                         ef->e2->h &= ~1;
2942                         ef->e3->h &= ~1;
2943                         if(ef->e4) ef->e4->h &= ~1;
2944                 }
2945         }
2946
2947         //third pass: unhide edges that have both verts visible
2948         //(these were missed if all faces were hidden, bug #21976)
2949         for(eed=em->edges.first; eed; eed=eed->next){
2950                 if(eed->v1->h == 0 && eed->v2->h == 0)
2951                         eed->h &= ~1;
2952         }
2953
2954         // Free the ghash and call MEM_freeN on all the value entries to return
2955         // that memory
2956         BLI_ghash_free(gh, NULL, (GHashValFreeFP)MEM_freeN);
2957
2958         EM_selectmode_flush(em);
2959         for(ef=em->faces.first;ef;ef = ef->next) {
2960                 if(ef->e4) {
2961                         if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) &&
2962                          (ef->e3->f & SELECT && ef->e4->f & SELECT) ) {
2963                                 ef->f |= SELECT;
2964                         }
2965                 } else {
2966                         if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) && ef->e3->f & SELECT) {
2967                                 ef->f |= SELECT;
2968                         }
2969                 }
2970         }
2971
2972         recalc_editnormals(em);
2973 }
2974
2975 static int count_selected_edges(EditEdge *ed)
2976 {
2977         int totedge = 0;
2978         while(ed) {
2979                 ed->tmp.p = 0;
2980                 if( ed->f & SELECT ) totedge++;
2981                 ed= ed->next;
2982         }
2983         return totedge;
2984 }
2985
2986 /* hurms, as if this makes code readable! It's pointerpointer hiding... (ton) */
2987 typedef EditFace *EVPtr;
2988 typedef EVPtr EVPTuple[2];
2989
2990 /** builds EVPTuple array efaa of face tuples (in fact pointers to EditFaces)
2991         sharing one edge.
2992         arguments: selected edge list, face list.
2993         Edges will also be tagged accordingly (see eed->f2)               */
2994
2995 static int collect_quadedges(EVPTuple *efaa, EditEdge *eed, EditFace *efa)
2996 {
2997         EditEdge *e1, *e2, *e3;
2998         EVPtr *evp;
2999         int i = 0;
3000
3001         /* run through edges, if selected, set pointer edge-> facearray */
3002         while(eed) {
3003                 eed->f2= 0;
3004                 eed->f1= 0;
3005                 if( eed->f & SELECT ) {
3006                         eed->tmp.p = (EditVert *) (&efaa[i]);
3007                         i++;
3008                 }
3009                 else eed->tmp.p = NULL;
3010
3011                 eed= eed->next;
3012         }
3013
3014
3015         /* find edges pointing to 2 faces by procedure:
3016
3017         - run through faces and their edges, increase
3018           face counter e->f1 for each face
3019         */
3020
3021         while(efa) {
3022                 efa->f1= 0;
3023                 if(efa->v4==0 && (efa->f & SELECT)) {  /* if selected triangle */
3024                         e1= efa->e1;
3025