2116acc337eb56c62e3e243141b22f4b4254bb6b
[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 enabled/disabled
441  */
442 static int bm_mesh_flag_count(BMesh *bm, const char htype, const char hflag,
443                                                           int respecthide, int test_for_enabled)
444 {
445         BMElem *ele;
446         BMIter iter;
447         int test = (test_for_enabled ? hflag : 0);
448         int tot = 0;
449
450         if (htype & BM_VERT) {
451                 for (ele = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); ele; ele = BM_iter_step(&iter)) {
452                         if (respecthide && BM_elem_flag_test(ele, BM_ELEM_HIDDEN)) continue;
453                         if (BM_elem_flag_test(ele, hflag) == test) tot++;
454                 }
455         }
456         if (htype & BM_EDGE) {
457                 for (ele = BM_iter_new(&iter, bm, BM_EDGES_OF_MESH, NULL); ele; ele = BM_iter_step(&iter)) {
458                         if (respecthide && BM_elem_flag_test(ele, BM_ELEM_HIDDEN)) continue;
459                         if (BM_elem_flag_test(ele, hflag) == test) tot++;
460                 }
461         }
462         if (htype & BM_FACE) {
463                 for (ele = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); ele; ele = BM_iter_step(&iter)) {
464                         if (respecthide && BM_elem_flag_test(ele, BM_ELEM_HIDDEN)) continue;
465                         if (BM_elem_flag_test(ele, hflag) == test) tot++;
466                 }
467         }
468
469         return tot;
470 }
471
472 int BM_mesh_enabled_flag_count(BMesh *bm, const char htype, const char hflag, int respecthide)
473 {
474         return bm_mesh_flag_count(bm, htype, hflag, respecthide, TRUE);
475 }
476
477 int BM_mesh_disabled_flag_count(BMesh *bm, const char htype, const char hflag, int respecthide)
478 {
479         return bm_mesh_flag_count(bm, htype, hflag, respecthide, FALSE);
480 }
481
482 /**
483  * \note use BM_elem_flag_test(ele, BM_ELEM_SELECT) to test selection
484  * \note by design, this will not touch the editselection history stuff
485  */
486 void _bm_elem_select_set(BMesh *bm, BMHeader *head, int select)
487 {
488         switch (head->htype) {
489                 case BM_VERT:
490                         BM_vert_select_set(bm, (BMVert *)head, select);
491                         break;
492                 case BM_EDGE:
493                         BM_edge_select_set(bm, (BMEdge *)head, select);
494                         break;
495                 case BM_FACE:
496                         BM_face_select_set(bm, (BMFace *)head, select);
497                         break;
498                 default:
499                         BLI_assert(0);
500                         break;
501         }
502 }
503
504 /* this replaces the active flag used in uv/face mode */
505 void BM_active_face_set(BMesh *bm, BMFace *efa)
506 {
507         bm->act_face = efa;
508 }
509
510 BMFace *BM_active_face_get(BMesh *bm, int sloppy)
511 {
512         if (bm->act_face) {
513                 return bm->act_face;
514         }
515         else if (sloppy) {
516                 BMIter iter;
517                 BMFace *f = NULL;
518                 BMEditSelection *ese;
519                 
520                 /* Find the latest non-hidden face from the BMEditSelection */
521                 ese = bm->selected.last;
522                 for ( ; ese; ese = ese->prev) {
523                         if (ese->htype == BM_FACE) {
524                                 f = (BMFace *)ese->ele;
525                                 
526                                 if (BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
527                                         f = NULL;
528                                 }
529                                 else {
530                                         break;
531                                 }
532                         }
533                 }
534                 /* Last attempt: try to find any selected face */
535                 if (f == NULL) {
536                         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
537                                 if (BM_elem_flag_test(f, BM_ELEM_SELECT)) {
538                                         break;
539                                 }
540                         }
541                 }
542                 return f; /* can still be null */
543         }
544         return NULL;
545 }
546
547 /**
548  * Generic way to get data from an EditSelection type
549  * These functions were written to be used by the Modifier widget
550  * when in Rotate about active mode, but can be used anywhere.
551  *
552  * - #EM_editselection_center
553  * - #EM_editselection_normal
554  * - #EM_editselection_plane
555  */
556 void BM_editselection_center(BMesh *bm, float r_center[3], BMEditSelection *ese)
557 {
558         if (ese->htype == BM_VERT) {
559                 BMVert *eve = (BMVert *)ese->ele;
560                 copy_v3_v3(r_center, eve->co);
561         }
562         else if (ese->htype == BM_EDGE) {
563                 BMEdge *eed = (BMEdge *)ese->ele;
564                 add_v3_v3v3(r_center, eed->v1->co, eed->v2->co);
565                 mul_v3_fl(r_center, 0.5);
566         }
567         else if (ese->htype == BM_FACE) {
568                 BMFace *efa = (BMFace *)ese->ele;
569                 BM_face_center_bounds_calc(bm, efa, r_center);
570         }
571 }
572
573 void BM_editselection_normal(float r_normal[3], BMEditSelection *ese)
574 {
575         if (ese->htype == BM_VERT) {
576                 BMVert *eve = (BMVert *)ese->ele;
577                 copy_v3_v3(r_normal, eve->no);
578         }
579         else if (ese->htype == BM_EDGE) {
580                 BMEdge *eed = (BMEdge *)ese->ele;
581                 float plane[3]; /* need a plane to correct the normal */
582                 float vec[3]; /* temp vec storage */
583                 
584                 add_v3_v3v3(r_normal, eed->v1->no, eed->v2->no);
585                 sub_v3_v3v3(plane, eed->v2->co, eed->v1->co);
586                 
587                 /* the 2 vertex normals will be close but not at rightangles to the edge
588                  * for rotate about edge we want them to be at right angles, so we need to
589                  * do some extra colculation to correct the vert normals,
590                  * we need the plane for this */
591                 cross_v3_v3v3(vec, r_normal, plane);
592                 cross_v3_v3v3(r_normal, plane, vec);
593                 normalize_v3(r_normal);
594                 
595         }
596         else if (ese->htype == BM_FACE) {
597                 BMFace *efa = (BMFace *)ese->ele;
598                 copy_v3_v3(r_normal, efa->no);
599         }
600 }
601
602 /* ref - editmesh_lib.cL:EM_editselection_plane() */
603
604 /* Calculate a plane that is rightangles to the edge/vert/faces normal
605  * also make the plane run along an axis that is related to the geometry,
606  * because this is used for the manipulators Y axis. */
607 void BM_editselection_plane(BMesh *bm, float r_plane[3], BMEditSelection *ese)
608 {
609         if (ese->htype == BM_VERT) {
610                 BMVert *eve = (BMVert *)ese->ele;
611                 float vec[3] = {0.0f, 0.0f, 0.0f};
612                 
613                 if (ese->prev) { /* use previously selected data to make a useful vertex plane */
614                         BM_editselection_center(bm, vec, ese->prev);
615                         sub_v3_v3v3(r_plane, vec, eve->co);
616                 }
617                 else {
618                         /* make a fake  plane thats at rightangles to the normal
619                          * we cant make a crossvec from a vec thats the same as the vec
620                          * unlikely but possible, so make sure if the normal is (0, 0, 1)
621                          * that vec isn't the same or in the same direction even. */
622                         if      (eve->no[0] < 0.5f) vec[0] = 1.0f;
623                         else if (eve->no[1] < 0.5f) vec[1] = 1.0f;
624                         else                        vec[2] = 1.0f;
625                         cross_v3_v3v3(r_plane, eve->no, vec);
626                 }
627         }
628         else if (ese->htype == BM_EDGE) {
629                 BMEdge *eed = (BMEdge *)ese->ele;
630
631                 /* the plane is simple, it runs along the edge
632                  * however selecting different edges can swap the direction of the y axis.
633                  * this makes it less likely for the y axis of the manipulator
634                  * (running along the edge).. to flip less often.
635                  * at least its more predictable */
636                 if (eed->v2->co[1] > eed->v1->co[1]) {  /* check which to do first */
637                         sub_v3_v3v3(r_plane, eed->v2->co, eed->v1->co);
638                 }
639                 else {
640                         sub_v3_v3v3(r_plane, eed->v1->co, eed->v2->co);
641                 }
642                 
643         }
644         else if (ese->htype == BM_FACE) {
645                 BMFace *efa = (BMFace *)ese->ele;
646                 float vec[3] = {0.0f, 0.0f, 0.0f};
647                 
648                 /* for now, use face normal */
649
650                 /* make a fake plane thats at rightangles to the normal
651                  * we cant make a crossvec from a vec thats the same as the vec
652                  * unlikely but possible, so make sure if the normal is (0, 0, 1)
653                  * that vec isn't the same or in the same direction even. */
654                 if (efa->len < 3) {
655                         /* crappy fallback method */
656                         if      (efa->no[0] < 0.5f)     vec[0] = 1.0f;
657                         else if (efa->no[1] < 0.5f)     vec[1] = 1.0f;
658                         else                        vec[2] = 1.0f;
659                         cross_v3_v3v3(r_plane, efa->no, vec);
660                 }
661                 else {
662                         BMVert *verts[4] = {NULL};
663
664                         BM_iter_as_array(bm, BM_VERTS_OF_FACE, efa, (void **)verts, 4);
665
666                         if (efa->len == 4) {
667                                 float vecA[3], vecB[3];
668                                 sub_v3_v3v3(vecA, verts[3]->co, verts[2]->co);
669                                 sub_v3_v3v3(vecB, verts[0]->co, verts[1]->co);
670                                 add_v3_v3v3(r_plane, vecA, vecB);
671
672                                 sub_v3_v3v3(vecA, verts[0]->co, verts[3]->co);
673                                 sub_v3_v3v3(vecB, verts[1]->co, verts[2]->co);
674                                 add_v3_v3v3(vec, vecA, vecB);
675                                 /* use the biggest edge length */
676                                 if (dot_v3v3(r_plane, r_plane) < dot_v3v3(vec, vec)) {
677                                         copy_v3_v3(r_plane, vec);
678                                 }
679                         }
680                         else {
681                                 /* BMESH_TODO (not urgent, use longest ngon edge for alignment) */
682
683                                 /* start with v1-2 */
684                                 sub_v3_v3v3(r_plane, verts[0]->co, verts[1]->co);
685
686                                 /* test the edge between v2-3, use if longer */
687                                 sub_v3_v3v3(vec, verts[1]->co, verts[2]->co);
688                                 if (dot_v3v3(r_plane, r_plane) < dot_v3v3(vec, vec))
689                                         copy_v3_v3(r_plane, vec);
690
691                                 /* test the edge between v1-3, use if longer */
692                                 sub_v3_v3v3(vec, verts[2]->co, verts[0]->co);
693                                 if (dot_v3v3(r_plane, r_plane) < dot_v3v3(vec, vec)) {
694                                         copy_v3_v3(r_plane, vec);
695                                 }
696                         }
697
698                 }
699         }
700         normalize_v3(r_plane);
701 }
702
703 int BM_select_history_check(BMesh *bm, const BMElem *ele)
704 {
705         BMEditSelection *ese;
706         
707         for (ese = bm->selected.first; ese; ese = ese->next) {
708                 if (ese->ele == ele) {
709                         return TRUE;
710                 }
711         }
712         
713         return FALSE;
714 }
715
716 int BM_select_history_remove(BMesh *bm, BMElem *ele)
717 {
718         BMEditSelection *ese;
719         for (ese = bm->selected.first; ese; ese = ese->next) {
720                 if (ese->ele == ele) {
721                         BLI_freelinkN(&(bm->selected), ese);
722                         return TRUE;
723                 }
724         }
725
726         return FALSE;
727 }
728
729 void BM_select_history_clear(BMesh *bm)
730 {
731         BLI_freelistN(&bm->selected);
732         bm->selected.first = bm->selected.last = NULL;
733 }
734
735 void BM_select_history_store_notest(BMesh *bm, BMElem *ele)
736 {
737         BMEditSelection *ese = (BMEditSelection *) MEM_callocN(sizeof(BMEditSelection), "BMEdit Selection");
738         ese->htype = ((BMHeader *)ele)->htype;
739         ese->ele = ele;
740         BLI_addtail(&(bm->selected), ese);
741 }
742
743 void BM_select_history_store(BMesh *bm, BMElem *ele)
744 {
745         if (!BM_select_history_check(bm, ele)) {
746                 BM_select_history_store_notest(bm, ele);
747         }
748 }
749
750 void BM_select_history_validate(BMesh *bm)
751 {
752         BMEditSelection *ese, *nextese;
753
754         ese = bm->selected.first;
755
756         while (ese) {
757                 nextese = ese->next;
758                 if (!BM_elem_flag_test(ese->ele, BM_ELEM_SELECT)) {
759                         BLI_freelinkN(&(bm->selected), ese);
760                 }
761                 ese = nextese;
762         }
763 }
764
765 void BM_mesh_elem_flag_disable_all(BMesh *bm, const char htype, const char hflag)
766 {
767         const char iter_types[3] = {BM_VERTS_OF_MESH,
768                                     BM_EDGES_OF_MESH,
769                                     BM_FACES_OF_MESH};
770
771         const char flag_types[3] = {BM_VERT, BM_EDGE, BM_FACE};
772
773         BMIter iter;
774         BMElem *ele;
775         int i;
776
777         if (hflag & BM_ELEM_SELECT) {
778                 BM_select_history_clear(bm);
779         }
780
781         if (htype == (BM_VERT | BM_EDGE | BM_FACE) && (hflag == BM_ELEM_SELECT)) {
782                 /* fast path for deselect all, avoid topology loops
783                  * since we know all will be de-selected anyway. */
784                 for (i = 0; i < 3; i++) {
785                         ele = BM_iter_new(&iter, bm, iter_types[i], NULL);
786                         for ( ; ele; ele = BM_iter_step(&iter)) {
787                                 BM_elem_flag_disable(ele, BM_ELEM_SELECT);
788                         }
789                 }
790                 bm->totvertsel = bm->totedgesel = bm->totfacesel = 0;
791         }
792         else {
793                 for (i = 0; i < 3; i++) {
794                         if (htype & flag_types[i]) {
795                                 ele = BM_iter_new(&iter, bm, iter_types[i], NULL);
796                                 for ( ; ele; ele = BM_iter_step(&iter)) {
797                                         if (hflag & BM_ELEM_SELECT) {
798                                                 BM_elem_select_set(bm, ele, FALSE);
799                                         }
800                                         BM_elem_flag_disable(ele, hflag);
801                                 }
802                         }
803                 }
804         }
805 }
806
807 void BM_mesh_elem_flag_enable_all(BMesh *bm, const char htype, const char hflag)
808 {
809         const char iter_types[3] = {BM_VERTS_OF_MESH,
810                                     BM_EDGES_OF_MESH,
811                                     BM_FACES_OF_MESH};
812
813         const char flag_types[3] = {BM_VERT, BM_EDGE, BM_FACE};
814
815         BMIter iter;
816         BMElem *ele;
817         int i;
818
819         if (hflag & BM_ELEM_SELECT) {
820                 BM_select_history_clear(bm);
821         }
822
823         /* note, better not attempt a fast path for selection as done with de-select
824          * because hidden geometry and different selection modes can give different results,
825          * we could ofcourse check for no hiddent faces and then use quicker method but its not worth it. */
826
827         for (i = 0; i < 3; i++) {
828                 if (htype & flag_types[i]) {
829                         ele = BM_iter_new(&iter, bm, iter_types[i], NULL);
830                         for ( ; ele; ele = BM_iter_step(&iter)) {
831                                 if (hflag & BM_ELEM_SELECT) {
832                                         BM_elem_select_set(bm, ele, TRUE);
833                                 }
834                                 BM_elem_flag_enable(ele, hflag);
835                         }
836                 }
837         }
838 }
839
840 /***************** Mesh Hiding stuff *********** */
841
842 static void vert_flush_hide_set(BMesh *bm, BMVert *v)
843 {
844         BMIter iter;
845         BMEdge *e;
846         int hide = TRUE;
847
848         BM_ITER(e, &iter, bm, BM_EDGES_OF_VERT, v) {
849                 hide = hide && BM_elem_flag_test(e, BM_ELEM_HIDDEN);
850         }
851
852         BM_elem_flag_set(v, BM_ELEM_HIDDEN, hide);
853 }
854
855 static void edge_flush_hide(BMesh *bm, BMEdge *e)
856 {
857         BMIter iter;
858         BMFace *f;
859         int hide = TRUE;
860
861         BM_ITER(f, &iter, bm, BM_FACES_OF_EDGE, e) {
862                 hide = hide && BM_elem_flag_test(f, BM_ELEM_HIDDEN);
863         }
864
865         BM_elem_flag_set(e, BM_ELEM_HIDDEN, hide);
866 }
867
868 void BM_vert_hide_set(BMesh *bm, BMVert *v, int hide)
869 {
870         /* vert hiding: vert + surrounding edges and faces */
871         BMIter iter, fiter;
872         BMEdge *e;
873         BMFace *f;
874
875         BM_elem_flag_set(v, BM_ELEM_HIDDEN, hide);
876
877         BM_ITER(e, &iter, bm, BM_EDGES_OF_VERT, v) {
878                 BM_elem_flag_set(e, BM_ELEM_HIDDEN, hide);
879
880                 BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, e) {
881                         BM_elem_flag_set(f, BM_ELEM_HIDDEN, hide);
882                 }
883         }
884 }
885
886 void BM_edge_hide_set(BMesh *bm, BMEdge *e, int hide)
887 {
888         BMIter iter;
889         BMFace *f;
890         /* BMVert *v; */
891
892         /* edge hiding: faces around the edge */
893         BM_ITER(f, &iter, bm, BM_FACES_OF_EDGE, e) {
894                 BM_elem_flag_set(f, BM_ELEM_HIDDEN, hide);
895         }
896         
897         BM_elem_flag_set(e, BM_ELEM_HIDDEN, hide);
898
899         /* hide vertices if necessary */
900         vert_flush_hide_set(bm, e->v1);
901         vert_flush_hide_set(bm, e->v2);
902 }
903
904 void BM_face_hide_set(BMesh *bm, BMFace *f, int hide)
905 {
906         BMIter iter;
907         BMLoop *l;
908
909         BM_elem_flag_set(f, BM_ELEM_HIDDEN, hide);
910
911         BM_ITER(l, &iter, bm, BM_LOOPS_OF_FACE, f) {
912                 edge_flush_hide(bm, l->e);
913         }
914
915         BM_ITER(l, &iter, bm, BM_LOOPS_OF_FACE, f) {
916                 vert_flush_hide_set(bm, l->v);
917         }
918 }
919
920 void _bm_elem_hide_set(BMesh *bm, BMHeader *head, int hide)
921 {
922         /* Follow convention of always deselecting before
923          * hiding an element */
924         switch (head->htype) {
925                 case BM_VERT:
926                         if (hide) BM_vert_select_set(bm, (BMVert *)head, FALSE);
927                         BM_vert_hide_set(bm, (BMVert *)head, hide);
928                         break;
929                 case BM_EDGE:
930                         if (hide) BM_edge_select_set(bm, (BMEdge *)head, FALSE);
931                         BM_edge_hide_set(bm, (BMEdge *)head, hide);
932                         break;
933                 case BM_FACE:
934                         if (hide) BM_face_select_set(bm, (BMFace *)head, FALSE);
935                         BM_face_hide_set(bm, (BMFace *)head, hide);
936                         break;
937                 default:
938                         BMESH_ASSERT(0);
939                         break;
940         }
941 }