bmesh python api:
[blender.git] / source / blender / bmesh / intern / bmesh_marking.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar, Geoffrey Bantle, Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/intern/bmesh_marking.c
24  *  \ingroup bmesh
25  *
26  * Selection routines for bmesh structures.
27  * This is actually all old code ripped from
28  * editmesh_lib.c and slightly modified to work
29  * for bmesh's. This also means that it has some
30  * of the same problems.... something that
31  * that should be addressed eventually.
32  */
33
34 #include "MEM_guardedalloc.h"
35
36 #include "DNA_scene_types.h"
37
38 #include "BLI_math.h"
39 #include "BLI_listbase.h"
40
41 #include "bmesh.h"
42
43 static void recount_totsels(BMesh *bm)
44 {
45         BMIter iter;
46         BMElem *ele;
47         const char iter_types[3] = {BM_VERTS_OF_MESH,
48                                     BM_EDGES_OF_MESH,
49                                     BM_FACES_OF_MESH};
50         int *tots[3];
51         int i;
52
53         /* recount (tot * sel) variables */
54         bm->totvertsel = bm->totedgesel = bm->totfacesel = 0;
55         tots[0] = &bm->totvertsel;
56         tots[1] = &bm->totedgesel;
57         tots[2] = &bm->totfacesel;
58
59         for (i = 0; i < 3; i++) {
60                 ele = BM_iter_new(&iter, bm, iter_types[i], NULL);
61                 for ( ; ele; ele = BM_iter_step(&iter)) {
62                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) *tots[i] += 1;
63                 }
64         }
65 }
66
67 /**
68  * \brief Select Mode Flush
69  *
70  * Makes sure to flush selections 'upwards'
71  * (ie: all verts of an edge selects the edge and so on).
72  * This should only be called by system and not tool authors.
73  */
74 void BM_mesh_select_mode_flush(BMesh *bm)
75 {
76         BMEdge *e;
77         BMLoop *l_iter;
78         BMLoop *l_first;
79         BMFace *f;
80
81         BMIter edges;
82         BMIter faces;
83
84         int ok;
85
86         if (bm->selectmode & SCE_SELECT_VERTEX) {
87                 for (e = BM_iter_new(&edges, bm, BM_EDGES_OF_MESH, bm); e; e = BM_iter_step(&edges)) {
88                         if (BM_elem_flag_test(e->v1, BM_ELEM_SELECT) &&
89                             BM_elem_flag_test(e->v2, BM_ELEM_SELECT) &&
90                             !BM_elem_flag_test(e, BM_ELEM_HIDDEN))
91                         {
92                                 BM_elem_flag_enable(e, BM_ELEM_SELECT);
93                         }
94                         else {
95                                 BM_elem_flag_disable(e, BM_ELEM_SELECT);
96                         }
97                 }
98                 for (f = BM_iter_new(&faces, bm, BM_FACES_OF_MESH, bm); f; f = BM_iter_step(&faces)) {
99                         ok = TRUE;
100                         if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
101                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
102                                 do {
103                                         if (!BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) {
104                                                 ok = FALSE;
105                                                 break;
106                                         }
107                                 } while ((l_iter = l_iter->next) != l_first);
108                         }
109                         else {
110                                 ok = FALSE;
111                         }
112
113                         BM_elem_flag_set(f, BM_ELEM_SELECT, ok);
114                 }
115         }
116         else if (bm->selectmode & SCE_SELECT_EDGE) {
117                 for (f = BM_iter_new(&faces, bm, BM_FACES_OF_MESH, bm); f; f = BM_iter_step(&faces)) {
118                         ok = TRUE;
119                         if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
120                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
121                                 do {
122                                         if (!BM_elem_flag_test(l_iter->e, BM_ELEM_SELECT)) {
123                                                 ok = FALSE;
124                                                 break;
125                                         }
126                                 } while ((l_iter = l_iter->next) != l_first);
127                         }
128                         else {
129                                 ok = FALSE;
130                         }
131
132                         BM_elem_flag_set(f, BM_ELEM_SELECT, ok);
133                 }
134         }
135
136         /* Remove any deselected elements from the BMEditSelection */
137         BM_select_history_validate(bm);
138
139         recount_totsels(bm);
140 }
141
142 /**
143  * mode independent flushing up/down
144  */
145 void BM_mesh_deselect_flush(BMesh *bm)
146 {
147         BMEdge *e;
148         BMLoop *l_iter;
149         BMLoop *l_first;
150         BMFace *f;
151
152         BMIter edges;
153         BMIter faces;
154
155         int ok;
156
157         for (e = BM_iter_new(&edges, bm, BM_EDGES_OF_MESH, bm); e; e = BM_iter_step(&edges)) {
158                 if (!(BM_elem_flag_test(e->v1, BM_ELEM_SELECT) &&
159                       BM_elem_flag_test(e->v2, BM_ELEM_SELECT) &&
160                       !BM_elem_flag_test(e, BM_ELEM_HIDDEN)))
161                 {
162                         BM_elem_flag_disable(e, BM_ELEM_SELECT);
163                 }
164         }
165
166         for (f = BM_iter_new(&faces, bm, BM_FACES_OF_MESH, bm); f; f = BM_iter_step(&faces)) {
167                 ok = TRUE;
168                 if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
169                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
170                         do {
171                                 if (!BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) {
172                                         ok = FALSE;
173                                         break;
174                                 }
175                         } while ((l_iter = l_iter->next) != l_first);
176                 }
177                 else {
178                         ok = FALSE;
179                 }
180
181                 if (ok == FALSE) {
182                         BM_elem_flag_disable(f, BM_ELEM_SELECT);
183                 }
184         }
185
186         /* Remove any deselected elements from the BMEditSelection */
187         BM_select_history_validate(bm);
188
189         recount_totsels(bm);
190 }
191
192
193 /**
194  * mode independent flushing up/down
195  */
196 void BM_mesh_select_flush(BMesh *bm)
197 {
198         BMEdge *e;
199         BMLoop *l_iter;
200         BMLoop *l_first;
201         BMFace *f;
202
203         BMIter edges;
204         BMIter faces;
205
206         int ok;
207
208         for (e = BM_iter_new(&edges, bm, BM_EDGES_OF_MESH, bm); e; e = BM_iter_step(&edges)) {
209                 if (BM_elem_flag_test(e->v1, BM_ELEM_SELECT) &&
210                     BM_elem_flag_test(e->v2, BM_ELEM_SELECT) &&
211                     !BM_elem_flag_test(e, BM_ELEM_HIDDEN))
212                 {
213                         BM_elem_flag_enable(e, BM_ELEM_SELECT);
214                 }
215         }
216
217         for (f = BM_iter_new(&faces, bm, BM_FACES_OF_MESH, bm); f; f = BM_iter_step(&faces)) {
218                 ok = TRUE;
219                 if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
220                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
221                         do {
222                                 if (!BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) {
223                                         ok = FALSE;
224                                         break;
225                                 }
226                         } while ((l_iter = l_iter->next) != l_first);
227                 }
228                 else {
229                         ok = FALSE;
230                 }
231
232                 if (ok) {
233                         BM_elem_flag_enable(f, BM_ELEM_SELECT);
234                 }
235         }
236
237         recount_totsels(bm);
238 }
239
240 /**
241  * \brief Select Vert
242  *
243  * Changes selection state of a single vertex
244  * in a mesh
245  */
246 void BM_vert_select_set(BMesh *bm, BMVert *v, int select)
247 {
248         /* BMIter iter; */
249         /* BMEdge *e; */
250
251         if (BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
252                 return;
253         }
254
255         if (select) {
256                 if (!BM_elem_flag_test(v, BM_ELEM_SELECT)) {
257                         bm->totvertsel += 1;
258                         BM_elem_flag_enable(v, BM_ELEM_SELECT);
259                 }
260         }
261         else {
262                 if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
263                         bm->totvertsel -= 1;
264                         BM_elem_flag_disable(v, BM_ELEM_SELECT);
265                 }
266         }
267 }
268
269 /**
270  * \brief Select Edge
271  *
272  * Changes selection state of a single edge in a mesh.
273  */
274 void BM_edge_select_set(BMesh *bm, BMEdge *e, int select)
275 {
276         if (BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
277                 return;
278         }
279
280         if (select) {
281                 if (!BM_elem_flag_test(e, BM_ELEM_SELECT)) bm->totedgesel += 1;
282
283                 BM_elem_flag_enable(e, BM_ELEM_SELECT);
284                 BM_elem_select_set(bm, e->v1, TRUE);
285                 BM_elem_select_set(bm, e->v2, TRUE);
286         }
287         else {
288                 if (BM_elem_flag_test(e, BM_ELEM_SELECT)) bm->totedgesel -= 1;
289                 BM_elem_flag_disable(e, BM_ELEM_SELECT);
290
291                 if ( bm->selectmode == SCE_SELECT_EDGE ||
292                      bm->selectmode == SCE_SELECT_FACE ||
293                      bm->selectmode == (SCE_SELECT_EDGE | SCE_SELECT_FACE))
294                 {
295
296                         BMIter iter;
297                         BMVert *verts[2] = {e->v1, e->v2};
298                         BMEdge *e2;
299                         int i;
300
301                         for (i = 0; i < 2; i++) {
302                                 int deselect = 1;
303
304                                 for (e2 = BM_iter_new(&iter, bm, BM_EDGES_OF_VERT, verts[i]); e2; e2 = BM_iter_step(&iter)) {
305                                         if (e2 == e) {
306                                                 continue;
307                                         }
308
309                                         if (BM_elem_flag_test(e2, BM_ELEM_SELECT)) {
310                                                 deselect = 0;
311                                                 break;
312                                         }
313                                 }
314
315                 if (deselect) {
316                     BM_vert_select_set(bm, verts[i], FALSE);
317                 }
318                         }
319                 }
320                 else {
321                         BM_elem_select_set(bm, e->v1, FALSE);
322                         BM_elem_select_set(bm, e->v2, FALSE);
323                 }
324
325         }
326 }
327
328 /**
329  * \brief Select Face
330  *
331  * Changes selection state of a single
332  * face in a mesh.
333  */
334 void BM_face_select_set(BMesh *bm, BMFace *f, int select)
335 {
336         BMLoop *l_iter;
337         BMLoop *l_first;
338
339         if (BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
340                 return;
341         }
342
343         if (select) {
344                 if (!BM_elem_flag_test(f, BM_ELEM_SELECT)) {
345                         bm->totfacesel++;
346                 }
347
348                 BM_elem_flag_enable(f, BM_ELEM_SELECT);
349                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
350                 do {
351                         BM_vert_select_set(bm, l_iter->v, TRUE);
352                         BM_edge_select_set(bm, l_iter->e, TRUE);
353                 } while ((l_iter = l_iter->next) != l_first);
354         }
355         else {
356                 BMIter liter;
357                 BMLoop *l;
358
359                 if (BM_elem_flag_test(f, BM_ELEM_SELECT)) bm->totfacesel -= 1;
360                 BM_elem_flag_disable(f, BM_ELEM_SELECT);
361
362                 /* flush down to edges */
363                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
364                         BMIter fiter;
365                         BMFace *f2;
366                         BM_ITER(f2, &fiter, bm, BM_FACES_OF_EDGE, l->e) {
367                                 if (BM_elem_flag_test(f2, BM_ELEM_SELECT))
368                                         break;
369                         }
370
371                         if (!f2) {
372                                 BM_elem_select_set(bm, l->e, FALSE);
373                         }
374                 }
375
376                 /* flush down to verts */
377                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
378                         BMIter eiter;
379                         BMEdge *e;
380                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, l->v) {
381                                 if (BM_elem_flag_test(e, BM_ELEM_SELECT))
382                                         break;
383                         }
384
385                         if (!e) {
386                                 BM_elem_select_set(bm, l->v, FALSE);
387                         }
388                 }
389         }
390 }
391
392 /**
393  * Select Mode Set
394  *
395  * Sets the selection mode for the bmesh,
396  * updating the selection state.
397  */
398 void BM_select_mode_set(BMesh *bm, int selectmode)
399 {
400         BMVert *v;
401         BMEdge *e;
402         BMFace *f;
403         
404         BMIter verts;
405         BMIter edges;
406         BMIter faces;
407         
408         bm->selectmode = selectmode;
409
410         if (bm->selectmode & SCE_SELECT_VERTEX) {
411                 for (e = BM_iter_new(&edges, bm, BM_EDGES_OF_MESH, bm); e; e = BM_iter_step(&edges))
412                         BM_elem_flag_disable(e, 0);
413                 for (f = BM_iter_new(&faces, bm, BM_FACES_OF_MESH, bm); f; f = BM_iter_step(&faces))
414                         BM_elem_flag_disable(f, 0);
415                 BM_mesh_select_mode_flush(bm);
416         }
417         else if (bm->selectmode & SCE_SELECT_EDGE) {
418                 for (v = BM_iter_new(&verts, bm, BM_VERTS_OF_MESH, bm); v; v = BM_iter_step(&verts))
419                         BM_elem_flag_disable(v, 0);
420                 for (e = BM_iter_new(&edges, bm, BM_EDGES_OF_MESH, bm); e; e = BM_iter_step(&edges)) {
421                         if (BM_elem_flag_test(e, BM_ELEM_SELECT)) {
422                                 BM_edge_select_set(bm, e, TRUE);
423                         }
424                 }
425                 BM_mesh_select_mode_flush(bm);
426         }
427         else if (bm->selectmode & SCE_SELECT_FACE) {
428                 for (e = BM_iter_new(&edges, bm, BM_EDGES_OF_MESH, bm); e; e = BM_iter_step(&edges))
429                         BM_elem_flag_disable(e, 0);
430                 for (f = BM_iter_new(&faces, bm, BM_FACES_OF_MESH, bm); f; f = BM_iter_step(&faces)) {
431                         if (BM_elem_flag_test(f, BM_ELEM_SELECT)) {
432                                 BM_face_select_set(bm, f, TRUE);
433                         }
434                 }
435                 BM_mesh_select_mode_flush(bm);
436         }
437 }
438
439 /**
440  * counts number of elements with flag set
441  */
442 int BM_mesh_count_flag(BMesh *bm, const char htype, const char hflag, int respecthide)
443 {
444         BMElem *ele;
445         BMIter iter;
446         int tot = 0;
447
448         if (htype & BM_VERT) {
449                 for (ele = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); ele; ele = BM_iter_step(&iter)) {
450                         if (respecthide && BM_elem_flag_test(ele, BM_ELEM_HIDDEN)) continue;
451                         if (BM_elem_flag_test(ele, hflag)) tot++;
452                 }
453         }
454         if (htype & BM_EDGE) {
455                 for (ele = BM_iter_new(&iter, bm, BM_EDGES_OF_MESH, NULL); ele; ele = BM_iter_step(&iter)) {
456                         if (respecthide && BM_elem_flag_test(ele, BM_ELEM_HIDDEN)) continue;
457                         if (BM_elem_flag_test(ele, hflag)) tot++;
458                 }
459         }
460         if (htype & BM_FACE) {
461                 for (ele = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); ele; ele = BM_iter_step(&iter)) {
462                         if (respecthide && BM_elem_flag_test(ele, BM_ELEM_HIDDEN)) continue;
463                         if (BM_elem_flag_test(ele, hflag)) tot++;
464                 }
465         }
466
467         return tot;
468 }
469
470 /**
471  * \note use BM_elem_flag_test(ele, BM_ELEM_SELECT) to test selection
472  * \note by design, this will not touch the editselection history stuff
473  */
474 void _bm_elem_select_set(BMesh *bm, BMHeader *head, int select)
475 {
476         switch (head->htype) {
477                 case BM_VERT:
478                         BM_vert_select_set(bm, (BMVert *)head, select);
479                         break;
480                 case BM_EDGE:
481                         BM_edge_select_set(bm, (BMEdge *)head, select);
482                         break;
483                 case BM_FACE:
484                         BM_face_select_set(bm, (BMFace *)head, select);
485                         break;
486                 default:
487                         BLI_assert(0);
488                         break;
489         }
490 }
491
492 /* this replaces the active flag used in uv/face mode */
493 void BM_active_face_set(BMesh *bm, BMFace *efa)
494 {
495         bm->act_face = efa;
496 }
497
498 BMFace *BM_active_face_get(BMesh *bm, int sloppy)
499 {
500         if (bm->act_face) {
501                 return bm->act_face;
502         }
503         else if (sloppy) {
504                 BMIter iter;
505                 BMFace *f = NULL;
506                 BMEditSelection *ese;
507                 
508                 /* Find the latest non-hidden face from the BMEditSelection */
509                 ese = bm->selected.last;
510                 for ( ; ese; ese = ese->prev) {
511                         if (ese->htype == BM_FACE) {
512                                 f = (BMFace *)ese->ele;
513                                 
514                                 if (BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
515                                         f = NULL;
516                                 }
517                                 else {
518                                         break;
519                                 }
520                         }
521                 }
522                 /* Last attempt: try to find any selected face */
523                 if (f == NULL) {
524                         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
525                                 if (BM_elem_flag_test(f, BM_ELEM_SELECT)) {
526                                         break;
527                                 }
528                         }
529                 }
530                 return f; /* can still be null */
531         }
532         return NULL;
533 }
534
535 /**
536  * Generic way to get data from an EditSelection type
537  * These functions were written to be used by the Modifier widget
538  * when in Rotate about active mode, but can be used anywhere.
539  *
540  * - #EM_editselection_center
541  * - #EM_editselection_normal
542  * - #EM_editselection_plane
543  */
544 void BM_editselection_center(BMesh *bm, float r_center[3], BMEditSelection *ese)
545 {
546         if (ese->htype == BM_VERT) {
547                 BMVert *eve = (BMVert *)ese->ele;
548                 copy_v3_v3(r_center, eve->co);
549         }
550         else if (ese->htype == BM_EDGE) {
551                 BMEdge *eed = (BMEdge *)ese->ele;
552                 add_v3_v3v3(r_center, eed->v1->co, eed->v2->co);
553                 mul_v3_fl(r_center, 0.5);
554         }
555         else if (ese->htype == BM_FACE) {
556                 BMFace *efa = (BMFace *)ese->ele;
557                 BM_face_center_bounds_calc(bm, efa, r_center);
558         }
559 }
560
561 void BM_editselection_normal(float r_normal[3], BMEditSelection *ese)
562 {
563         if (ese->htype == BM_VERT) {
564                 BMVert *eve = (BMVert *)ese->ele;
565                 copy_v3_v3(r_normal, eve->no);
566         }
567         else if (ese->htype == BM_EDGE) {
568                 BMEdge *eed = (BMEdge *)ese->ele;
569                 float plane[3]; /* need a plane to correct the normal */
570                 float vec[3]; /* temp vec storage */
571                 
572                 add_v3_v3v3(r_normal, eed->v1->no, eed->v2->no);
573                 sub_v3_v3v3(plane, eed->v2->co, eed->v1->co);
574                 
575                 /* the 2 vertex normals will be close but not at rightangles to the edge
576                  * for rotate about edge we want them to be at right angles, so we need to
577                  * do some extra colculation to correct the vert normals,
578                  * we need the plane for this */
579                 cross_v3_v3v3(vec, r_normal, plane);
580                 cross_v3_v3v3(r_normal, plane, vec);
581                 normalize_v3(r_normal);
582                 
583         }
584         else if (ese->htype == BM_FACE) {
585                 BMFace *efa = (BMFace *)ese->ele;
586                 copy_v3_v3(r_normal, efa->no);
587         }
588 }
589
590 /* ref - editmesh_lib.cL:EM_editselection_plane() */
591
592 /* Calculate a plane that is rightangles to the edge/vert/faces normal
593  * also make the plane run along an axis that is related to the geometry,
594  * because this is used for the manipulators Y axis. */
595 void BM_editselection_plane(BMesh *bm, float r_plane[3], BMEditSelection *ese)
596 {
597         if (ese->htype == BM_VERT) {
598                 BMVert *eve = (BMVert *)ese->ele;
599                 float vec[3] = {0.0f, 0.0f, 0.0f};
600                 
601                 if (ese->prev) { /* use previously selected data to make a useful vertex plane */
602                         BM_editselection_center(bm, vec, ese->prev);
603                         sub_v3_v3v3(r_plane, vec, eve->co);
604                 }
605                 else {
606                         /* make a fake  plane thats at rightangles to the normal
607                          * we cant make a crossvec from a vec thats the same as the vec
608                          * unlikely but possible, so make sure if the normal is (0, 0, 1)
609                          * that vec isnt the same or in the same direction even. */
610                         if (eve->no[0] < 0.5f)          vec[0] = 1.0f;
611                         else if (eve->no[1] < 0.5f)     vec[1] = 1.0f;
612                         else                                            vec[2] = 1.0f;
613                         cross_v3_v3v3(r_plane, eve->no, vec);
614                 }
615         }
616         else if (ese->htype == BM_EDGE) {
617                 BMEdge *eed = (BMEdge *)ese->ele;
618
619                 /* the plane is simple, it runs along the edge
620                  * however selecting different edges can swap the direction of the y axis.
621                  * this makes it less likely for the y axis of the manipulator
622                  * (running along the edge).. to flip less often.
623                  * at least its more predictable */
624                 if (eed->v2->co[1] > eed->v1->co[1]) {  /* check which to do first */
625                         sub_v3_v3v3(r_plane, eed->v2->co, eed->v1->co);
626                 }
627                 else {
628                         sub_v3_v3v3(r_plane, eed->v1->co, eed->v2->co);
629                 }
630                 
631         }
632         else if (ese->htype == BM_FACE) {
633                 BMFace *efa = (BMFace *)ese->ele;
634                 float vec[3] = {0.0f, 0.0f, 0.0f};
635                 
636                 /* for now, use face normal */
637
638                 /* make a fake plane thats at rightangles to the normal
639                  * we cant make a crossvec from a vec thats the same as the vec
640                  * unlikely but possible, so make sure if the normal is (0, 0, 1)
641                  * that vec isnt the same or in the same direction even. */
642                 if (efa->len < 3) {
643                         /* crappy fallback method */
644                         if      (efa->no[0] < 0.5f)     vec[0] = 1.0f;
645                         else if (efa->no[1] < 0.5f)     vec[1] = 1.0f;
646                         else                        vec[2] = 1.0f;
647                         cross_v3_v3v3(r_plane, efa->no, vec);
648                 }
649                 else {
650                         BMVert *verts[4] = {NULL};
651
652                         BM_iter_as_array(bm, BM_VERTS_OF_FACE, efa, (void **)verts, 4);
653
654                         if (efa->len == 4) {
655                                 float vecA[3], vecB[3];
656                                 sub_v3_v3v3(vecA, verts[3]->co, verts[2]->co);
657                                 sub_v3_v3v3(vecB, verts[0]->co, verts[1]->co);
658                                 add_v3_v3v3(r_plane, vecA, vecB);
659
660                                 sub_v3_v3v3(vecA, verts[0]->co, verts[3]->co);
661                                 sub_v3_v3v3(vecB, verts[1]->co, verts[2]->co);
662                                 add_v3_v3v3(vec, vecA, vecB);
663                                 /* use the biggest edge length */
664                                 if (dot_v3v3(r_plane, r_plane) < dot_v3v3(vec, vec)) {
665                                         copy_v3_v3(r_plane, vec);
666                                 }
667                         }
668                         else {
669                                 /* BMESH_TODO (not urgent, use longest ngon edge for alignment) */
670
671                                 /* start with v1-2 */
672                                 sub_v3_v3v3(r_plane, verts[0]->co, verts[1]->co);
673
674                                 /* test the edge between v2-3, use if longer */
675                                 sub_v3_v3v3(vec, verts[1]->co, verts[2]->co);
676                                 if (dot_v3v3(r_plane, r_plane) < dot_v3v3(vec, vec))
677                                         copy_v3_v3(r_plane, vec);
678
679                                 /* test the edge between v1-3, use if longer */
680                                 sub_v3_v3v3(vec, verts[2]->co, verts[0]->co);
681                                 if (dot_v3v3(r_plane, r_plane) < dot_v3v3(vec, vec)) {
682                                         copy_v3_v3(r_plane, vec);
683                                 }
684                         }
685
686                 }
687         }
688         normalize_v3(r_plane);
689 }
690
691 int BM_select_history_check(BMesh *bm, const BMElem *ele)
692 {
693         BMEditSelection *ese;
694         
695         for (ese = bm->selected.first; ese; ese = ese->next) {
696                 if (ese->ele == ele) {
697                         return TRUE;
698                 }
699         }
700         
701         return FALSE;
702 }
703
704 int BM_select_history_remove(BMesh *bm, BMElem *ele)
705 {
706         BMEditSelection *ese;
707         for (ese = bm->selected.first; ese; ese = ese->next) {
708                 if (ese->ele == ele) {
709                         BLI_freelinkN(&(bm->selected), ese);
710                         return TRUE;
711                 }
712         }
713
714         return FALSE;
715 }
716
717 void BM_select_history_clear(BMesh *bm)
718 {
719         BLI_freelistN(&bm->selected);
720         bm->selected.first = bm->selected.last = NULL;
721 }
722
723 void BM_select_history_store(BMesh *bm, BMElem *ele)
724 {
725         BMEditSelection *ese;
726         if (!BM_select_history_check(bm, ele)) {
727                 ese = (BMEditSelection *) MEM_callocN(sizeof(BMEditSelection), "BMEdit Selection");
728                 ese->htype = ((BMHeader *)ele)->htype;
729                 ese->ele = ele;
730                 BLI_addtail(&(bm->selected), ese);
731         }
732 }
733
734 void BM_select_history_validate(BMesh *bm)
735 {
736         BMEditSelection *ese, *nextese;
737
738         ese = bm->selected.first;
739
740         while (ese) {
741                 nextese = ese->next;
742                 if (!BM_elem_flag_test(ese->ele, BM_ELEM_SELECT)) {
743                         BLI_freelinkN(&(bm->selected), ese);
744                 }
745                 ese = nextese;
746         }
747 }
748
749 void BM_mesh_elem_flag_disable_all(BMesh *bm, const char htype, const char hflag)
750 {
751         const char iter_types[3] = {BM_VERTS_OF_MESH,
752                                     BM_EDGES_OF_MESH,
753                                     BM_FACES_OF_MESH};
754         BMIter iter;
755         BMElem *ele;
756         int i;
757
758         if (hflag & BM_ELEM_SELECT) {
759                 BM_select_history_clear(bm);
760         }
761
762         if (htype == (BM_VERT | BM_EDGE | BM_FACE) && (hflag == BM_ELEM_SELECT)) {
763                 /* fast path for deselect all, avoid topology loops
764                  * since we know all will be de-selected anyway. */
765                 for (i = 0; i < 3; i++) {
766                         ele = BM_iter_new(&iter, bm, iter_types[i], NULL);
767                         for ( ; ele; ele = BM_iter_step(&iter)) {
768                                 BM_elem_flag_disable(ele, BM_ELEM_SELECT);
769                         }
770                 }
771                 bm->totvertsel = bm->totedgesel = bm->totfacesel = 0;
772         }
773         else {
774                 for (i = 0; i < 3; i++) {
775                         if (htype & iter_types[i]) {
776                                 ele = BM_iter_new(&iter, bm, iter_types[i], NULL);
777                                 for ( ; ele; ele = BM_iter_step(&iter)) {
778                                         if (hflag & BM_ELEM_SELECT) {
779                                                 BM_elem_select_set(bm, ele, FALSE);
780                                         }
781                                         BM_elem_flag_disable(ele, hflag);
782                                 }
783                         }
784                 }
785         }
786 }
787
788 void BM_mesh_elem_flag_enable_all(BMesh *bm, const char htype, const char hflag)
789 {
790         const char iter_types[3] = {BM_VERTS_OF_MESH,
791                                     BM_EDGES_OF_MESH,
792                                     BM_FACES_OF_MESH};
793         BMIter iter;
794         BMElem *ele;
795         int i;
796
797         if (hflag & BM_ELEM_SELECT) {
798                 BM_select_history_clear(bm);
799         }
800
801         /* note, better not attempt a fast path for selection as done with de-select
802          * because hidden geometry and different selection modes can give different results,
803          * we could ofcourse check for no hiddent faces and then use quicker method but its not worth it. */
804
805         for (i = 0; i < 3; i++) {
806                 if (htype & iter_types[i]) {
807                         ele = BM_iter_new(&iter, bm, iter_types[i], NULL);
808                         for ( ; ele; ele = BM_iter_step(&iter)) {
809                                 if (hflag & BM_ELEM_SELECT) {
810                                         BM_elem_select_set(bm, ele, TRUE);
811                                 }
812                                 BM_elem_flag_enable(ele, hflag);
813                         }
814                 }
815         }
816 }
817
818 /***************** Mesh Hiding stuff *********** */
819
820 static void vert_flush_hide_set(BMesh *bm, BMVert *v)
821 {
822         BMIter iter;
823         BMEdge *e;
824         int hide = TRUE;
825
826         BM_ITER(e, &iter, bm, BM_EDGES_OF_VERT, v) {
827                 hide = hide && BM_elem_flag_test(e, BM_ELEM_HIDDEN);
828         }
829
830         BM_elem_flag_set(v, BM_ELEM_HIDDEN, hide);
831 }
832
833 static void edge_flush_hide(BMesh *bm, BMEdge *e)
834 {
835         BMIter iter;
836         BMFace *f;
837         int hide = TRUE;
838
839         BM_ITER(f, &iter, bm, BM_FACES_OF_EDGE, e) {
840                 hide = hide && BM_elem_flag_test(f, BM_ELEM_HIDDEN);
841         }
842
843         BM_elem_flag_set(e, BM_ELEM_HIDDEN, hide);
844 }
845
846 void BM_vert_hide_set(BMesh *bm, BMVert *v, int hide)
847 {
848         /* vert hiding: vert + surrounding edges and faces */
849         BMIter iter, fiter;
850         BMEdge *e;
851         BMFace *f;
852
853         BM_elem_flag_set(v, BM_ELEM_HIDDEN, hide);
854
855         BM_ITER(e, &iter, bm, BM_EDGES_OF_VERT, v) {
856                 BM_elem_flag_set(e, BM_ELEM_HIDDEN, hide);
857
858                 BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, e) {
859                         BM_elem_flag_set(f, BM_ELEM_HIDDEN, hide);
860                 }
861         }
862 }
863
864 void BM_edge_hide_set(BMesh *bm, BMEdge *e, int hide)
865 {
866         BMIter iter;
867         BMFace *f;
868         /* BMVert *v; */
869
870         /* edge hiding: faces around the edge */
871         BM_ITER(f, &iter, bm, BM_FACES_OF_EDGE, e) {
872                 BM_elem_flag_set(f, BM_ELEM_HIDDEN, hide);
873         }
874         
875         BM_elem_flag_set(e, BM_ELEM_HIDDEN, hide);
876
877         /* hide vertices if necessary */
878         vert_flush_hide_set(bm, e->v1);
879         vert_flush_hide_set(bm, e->v2);
880 }
881
882 void BM_face_hide_set(BMesh *bm, BMFace *f, int hide)
883 {
884         BMIter iter;
885         BMLoop *l;
886
887         BM_elem_flag_set(f, BM_ELEM_HIDDEN, hide);
888
889         BM_ITER(l, &iter, bm, BM_LOOPS_OF_FACE, f) {
890                 edge_flush_hide(bm, l->e);
891         }
892
893         BM_ITER(l, &iter, bm, BM_LOOPS_OF_FACE, f) {
894                 vert_flush_hide_set(bm, l->v);
895         }
896 }
897
898 void _bm_elem_hide_set(BMesh *bm, BMHeader *head, int hide)
899 {
900         /* Follow convention of always deselecting before
901          * hiding an element */
902         switch (head->htype) {
903                 case BM_VERT:
904                         if (hide) BM_vert_select_set(bm, (BMVert *)head, FALSE);
905                         BM_vert_hide_set(bm, (BMVert *)head, hide);
906                         break;
907                 case BM_EDGE:
908                         if (hide) BM_edge_select_set(bm, (BMEdge *)head, FALSE);
909                         BM_edge_hide_set(bm, (BMEdge *)head, hide);
910                         break;
911                 case BM_FACE:
912                         if (hide) BM_face_select_set(bm, (BMFace *)head, FALSE);
913                         BM_face_hide_set(bm, (BMFace *)head, hide);
914                         break;
915                 default:
916                         BMESH_ASSERT(0);
917                         break;
918         }
919 }