improved method of getting the tangent axis from a bmesh triangle,
[blender-staging.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 <stddef.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "DNA_scene_types.h"
39
40 #include "BLI_math.h"
41 #include "BLI_listbase.h"
42
43 #include "bmesh.h"
44
45 static void recount_totsels(BMesh *bm)
46 {
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 #pragma omp parallel for schedule(dynamic)
60         for (i = 0; i < 3; i++) {
61                 BMIter iter;
62                 BMElem *ele;
63                 int count = 0;
64
65                 BM_ITER_MESH (ele, &iter, bm, iter_types[i]) {
66                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) count += 1;
67                 }
68                 *tots[i] = count;
69         }
70 }
71
72 /**
73  * \brief Select Mode Flush
74  *
75  * Makes sure to flush selections 'upwards'
76  * (ie: all verts of an edge selects the edge and so on).
77  * This should only be called by system and not tool authors.
78  */
79 void BM_mesh_select_mode_flush_ex(BMesh *bm, const short selectmode)
80 {
81         BMEdge *e;
82         BMLoop *l_iter;
83         BMLoop *l_first;
84         BMFace *f;
85
86         BMIter eiter;
87         BMIter fiter;
88
89         if (selectmode & SCE_SELECT_VERTEX) {
90                 /* both loops only set edge/face flags and read off verts */
91 #pragma omp parallel sections if (bm->totedge + bm->totface >= BM_OMP_LIMIT)
92                 {
93 #pragma omp section
94                         {
95                                 BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
96                                         if (BM_elem_flag_test(e->v1, BM_ELEM_SELECT) &&
97                                                 BM_elem_flag_test(e->v2, BM_ELEM_SELECT) &&
98                                                 !BM_elem_flag_test(e, BM_ELEM_HIDDEN))
99                                         {
100                                                 BM_elem_flag_enable(e, BM_ELEM_SELECT);
101                                         }
102                                         else {
103                                                 BM_elem_flag_disable(e, BM_ELEM_SELECT);
104                                         }
105                                 }
106                         }
107 #pragma omp section
108                         {
109                                 BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
110                                         bool ok = true;
111                                         if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
112                                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
113                                                 do {
114                                                         if (!BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) {
115                                                                 ok = false;
116                                                                 break;
117                                                         }
118                                                 } while ((l_iter = l_iter->next) != l_first);
119                                         }
120                                         else {
121                                                 ok = false;
122                                         }
123
124                                         BM_elem_flag_set(f, BM_ELEM_SELECT, ok);
125                                 }
126                         }
127                 }
128                 /* end sections */
129         }
130         else if (selectmode & SCE_SELECT_EDGE) {
131                 BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
132                         bool ok = true;
133                         if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
134                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
135                                 do {
136                                         if (!BM_elem_flag_test(l_iter->e, BM_ELEM_SELECT)) {
137                                                 ok = false;
138                                                 break;
139                                         }
140                                 } while ((l_iter = l_iter->next) != l_first);
141                         }
142                         else {
143                                 ok = false;
144                         }
145
146                         BM_elem_flag_set(f, BM_ELEM_SELECT, ok);
147                 }
148         }
149
150         /* Remove any deselected elements from the BMEditSelection */
151         BM_select_history_validate(bm);
152
153         recount_totsels(bm);
154 }
155
156 void BM_mesh_select_mode_flush(BMesh *bm)
157 {
158         BM_mesh_select_mode_flush_ex(bm, bm->selectmode);
159 }
160
161 /**
162  * mode independent flushing up/down
163  */
164 void BM_mesh_deselect_flush(BMesh *bm)
165 {
166         BMEdge *e;
167         BMLoop *l_iter;
168         BMLoop *l_first;
169         BMFace *f;
170
171         BMIter eiter;
172         BMIter fiter;
173
174         bool ok;
175
176         /* we can use 2 sections here because the second loop isnt checking edge selection */
177 #pragma omp parallel sections if (bm->totedge + bm->totface >= BM_OMP_LIMIT)
178         {
179 #pragma omp section
180                 {
181                         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
182                                 if (!(BM_elem_flag_test(e->v1, BM_ELEM_SELECT) &&
183                                       BM_elem_flag_test(e->v2, BM_ELEM_SELECT) &&
184                                       !BM_elem_flag_test(e, BM_ELEM_HIDDEN)))
185                                 {
186                                         BM_elem_flag_disable(e, BM_ELEM_SELECT);
187                                 }
188                         }
189                 }
190
191 #pragma omp section
192                 {
193                         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
194                                 ok = true;
195                                 if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
196                                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
197                                         do {
198                                                 if (!BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) {
199                                                         ok = false;
200                                                         break;
201                                                 }
202                                         } while ((l_iter = l_iter->next) != l_first);
203                                 }
204                                 else {
205                                         ok = false;
206                                 }
207
208                                 if (ok == false) {
209                                         BM_elem_flag_disable(f, BM_ELEM_SELECT);
210                                 }
211                         }
212                 }
213         }
214         /* end sections */
215
216         /* Remove any deselected elements from the BMEditSelection */
217         BM_select_history_validate(bm);
218
219         recount_totsels(bm);
220 }
221
222
223 /**
224  * mode independent flushing up/down
225  */
226 void BM_mesh_select_flush(BMesh *bm)
227 {
228         BMEdge *e;
229         BMLoop *l_iter;
230         BMLoop *l_first;
231         BMFace *f;
232
233         BMIter eiter;
234         BMIter fiter;
235
236         bool ok;
237
238         /* we can use 2 sections here because the second loop isnt checking edge selection */
239 #pragma omp parallel sections if (bm->totedge + bm->totface >= BM_OMP_LIMIT)
240         {
241 #pragma omp section
242                 {
243                         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
244                                 if (BM_elem_flag_test(e->v1, BM_ELEM_SELECT) &&
245                                     BM_elem_flag_test(e->v2, BM_ELEM_SELECT) &&
246                                     !BM_elem_flag_test(e, BM_ELEM_HIDDEN))
247                                 {
248                                         BM_elem_flag_enable(e, BM_ELEM_SELECT);
249                                 }
250                         }
251                 }
252
253 #pragma omp section
254                 {
255                         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
256                                 ok = true;
257                                 if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
258                                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
259                                         do {
260                                                 if (!BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) {
261                                                         ok = false;
262                                                         break;
263                                                 }
264                                         } while ((l_iter = l_iter->next) != l_first);
265                                 }
266                                 else {
267                                         ok = false;
268                                 }
269
270                                 if (ok) {
271                                         BM_elem_flag_enable(f, BM_ELEM_SELECT);
272                                 }
273                         }
274                 }
275         }
276
277         recount_totsels(bm);
278 }
279
280 /**
281  * \brief Select Vert
282  *
283  * Changes selection state of a single vertex
284  * in a mesh
285  */
286 void BM_vert_select_set(BMesh *bm, BMVert *v, const bool select)
287 {
288         BLI_assert(v->head.htype == BM_VERT);
289
290         if (BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
291                 return;
292         }
293
294         if (select) {
295                 if (!BM_elem_flag_test(v, BM_ELEM_SELECT)) {
296                         bm->totvertsel += 1;
297                         BM_elem_flag_enable(v, BM_ELEM_SELECT);
298                 }
299         }
300         else {
301                 if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
302                         bm->totvertsel -= 1;
303                         BM_elem_flag_disable(v, BM_ELEM_SELECT);
304                 }
305         }
306 }
307
308 /**
309  * \brief Select Edge
310  *
311  * Changes selection state of a single edge in a mesh.
312  */
313 void BM_edge_select_set(BMesh *bm, BMEdge *e, const bool select)
314 {
315         BLI_assert(e->head.htype == BM_EDGE);
316
317         if (BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
318                 return;
319         }
320
321         if (select) {
322                 if (!BM_elem_flag_test(e, BM_ELEM_SELECT)) bm->totedgesel += 1;
323
324                 BM_elem_flag_enable(e, BM_ELEM_SELECT);
325                 BM_vert_select_set(bm, e->v1, true);
326                 BM_vert_select_set(bm, e->v2, true);
327         }
328         else {
329                 if (BM_elem_flag_test(e, BM_ELEM_SELECT)) bm->totedgesel -= 1;
330                 BM_elem_flag_disable(e, BM_ELEM_SELECT);
331
332                 if (bm->selectmode == SCE_SELECT_EDGE ||
333                     bm->selectmode == SCE_SELECT_FACE ||
334                     bm->selectmode == (SCE_SELECT_EDGE | SCE_SELECT_FACE))
335                 {
336
337                         BMIter iter;
338                         BMVert *verts[2] = {e->v1, e->v2};
339                         BMEdge *e2;
340                         int i;
341
342                         for (i = 0; i < 2; i++) {
343                                 int deselect = 1;
344
345                                 for (e2 = BM_iter_new(&iter, bm, BM_EDGES_OF_VERT, verts[i]); e2; e2 = BM_iter_step(&iter)) {
346                                         if (e2 == e) {
347                                                 continue;
348                                         }
349
350                                         if (BM_elem_flag_test(e2, BM_ELEM_SELECT)) {
351                                                 deselect = 0;
352                                                 break;
353                                         }
354                                 }
355
356                                 if (deselect) {
357                                         BM_vert_select_set(bm, verts[i], false);
358                                 }
359                         }
360                 }
361                 else {
362                         BM_vert_select_set(bm, e->v1, false);
363                         BM_vert_select_set(bm, e->v2, false);
364                 }
365
366         }
367 }
368
369 /**
370  * \brief Select Face
371  *
372  * Changes selection state of a single
373  * face in a mesh.
374  */
375 void BM_face_select_set(BMesh *bm, BMFace *f, const bool select)
376 {
377         BMLoop *l_iter;
378         BMLoop *l_first;
379
380         BLI_assert(f->head.htype == BM_FACE);
381
382         if (BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
383                 return;
384         }
385
386         if (select) {
387                 if (!BM_elem_flag_test(f, BM_ELEM_SELECT)) {
388                         bm->totfacesel++;
389                 }
390
391                 BM_elem_flag_enable(f, BM_ELEM_SELECT);
392                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
393                 do {
394                         BM_vert_select_set(bm, l_iter->v, true);
395                         BM_edge_select_set(bm, l_iter->e, true);
396                 } while ((l_iter = l_iter->next) != l_first);
397         }
398         else {
399                 BMIter liter;
400                 BMLoop *l;
401
402                 if (BM_elem_flag_test(f, BM_ELEM_SELECT)) bm->totfacesel -= 1;
403                 BM_elem_flag_disable(f, BM_ELEM_SELECT);
404
405                 /* flush down to edges */
406                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
407                         BMIter fiter;
408                         BMFace *f2;
409                         BM_ITER_ELEM (f2, &fiter, l->e, BM_FACES_OF_EDGE) {
410                                 if (BM_elem_flag_test(f2, BM_ELEM_SELECT))
411                                         break;
412                         }
413
414                         if (!f2) {
415                                 BM_edge_select_set(bm, l->e, false);
416                         }
417                 }
418
419                 /* flush down to verts */
420                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
421                         BMIter eiter;
422                         BMEdge *e;
423                         BM_ITER_ELEM (e, &eiter, l->v, BM_EDGES_OF_VERT) {
424                                 if (BM_elem_flag_test(e, BM_ELEM_SELECT))
425                                         break;
426                         }
427
428                         if (!e) {
429                                 BM_vert_select_set(bm, l->v, false);
430                         }
431                 }
432         }
433 }
434
435 /**
436  * Select Mode Set
437  *
438  * Sets the selection mode for the bmesh,
439  * updating the selection state.
440  */
441 void BM_mesh_select_mode_set(BMesh *bm, int selectmode)
442 {
443         BMIter iter;
444         BMElem *ele;
445         
446         bm->selectmode = selectmode;
447
448         if (bm->selectmode & SCE_SELECT_VERTEX) {
449                 /* disabled because selection flushing handles these */
450 #if 0
451                 BM_ITER_MESH (ele, &iter, bm, BM_EDGES_OF_MESH) {
452                         BM_elem_flag_disable(ele, BM_ELEM_SELECT);
453                 }
454                 BM_ITER_MESH (ele, &iter, bm, BM_FACES_OF_MESH) {
455                         BM_elem_flag_disable(ele, BM_ELEM_SELECT);
456                 }
457 #endif
458                 BM_mesh_select_mode_flush(bm);
459         }
460         else if (bm->selectmode & SCE_SELECT_EDGE) {
461                 /* disabled because selection flushing handles these */
462 #if 0
463                 BM_ITER_MESH (ele, &iter, bm, BM_VERTS_OF_MESH) {
464                         BM_elem_flag_disable(ele, BM_ELEM_SELECT);
465                 }
466 #endif
467
468                 BM_ITER_MESH (ele, &iter, bm, BM_EDGES_OF_MESH) {
469                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
470                                 BM_edge_select_set(bm, (BMEdge *)ele, true);
471                         }
472                 }
473                 BM_mesh_select_mode_flush(bm);
474         }
475         else if (bm->selectmode & SCE_SELECT_FACE) {
476                 /* disabled because selection flushing handles these */
477 #if 0
478                 BM_ITER_MESH (ele, &iter, bm, BM_EDGES_OF_MESH) {
479                         BM_elem_flag_disable(ele, BM_ELEM_SELECT);
480                 }
481 #endif
482                 BM_ITER_MESH (ele, &iter, bm, BM_FACES_OF_MESH) {
483                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
484                                 BM_face_select_set(bm, (BMFace *)ele, true);
485                         }
486                 }
487                 BM_mesh_select_mode_flush(bm);
488         }
489 }
490
491 /**
492  * counts number of elements with flag enabled/disabled
493  */
494 static int bm_mesh_flag_count(BMesh *bm, const char htype, const char hflag,
495                               const short respecthide, const bool test_for_enabled)
496 {
497         BMElem *ele;
498         BMIter iter;
499         int tot = 0;
500
501         if (htype & BM_VERT) {
502                 for (ele = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); ele; ele = BM_iter_step(&iter)) {
503                         if (respecthide && BM_elem_flag_test(ele, BM_ELEM_HIDDEN)) continue;
504                         if (BM_elem_flag_test_bool(ele, hflag) == test_for_enabled) tot++;
505                 }
506         }
507         if (htype & BM_EDGE) {
508                 for (ele = BM_iter_new(&iter, bm, BM_EDGES_OF_MESH, NULL); ele; ele = BM_iter_step(&iter)) {
509                         if (respecthide && BM_elem_flag_test(ele, BM_ELEM_HIDDEN)) continue;
510                         if (BM_elem_flag_test_bool(ele, hflag) == test_for_enabled) tot++;
511                 }
512         }
513         if (htype & BM_FACE) {
514                 for (ele = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); ele; ele = BM_iter_step(&iter)) {
515                         if (respecthide && BM_elem_flag_test(ele, BM_ELEM_HIDDEN)) continue;
516                         if (BM_elem_flag_test_bool(ele, hflag) == test_for_enabled) tot++;
517                 }
518         }
519
520         return tot;
521 }
522
523 int BM_mesh_elem_hflag_count_enabled(BMesh *bm, const char htype, const char hflag, const bool respecthide)
524 {
525         return bm_mesh_flag_count(bm, htype, hflag, respecthide, true);
526 }
527
528 int BM_mesh_elem_hflag_count_disabled(BMesh *bm, const char htype, const char hflag, const bool respecthide)
529 {
530         return bm_mesh_flag_count(bm, htype, hflag, respecthide, false);
531 }
532
533 /**
534  * \note use BM_elem_flag_test(ele, BM_ELEM_SELECT) to test selection
535  * \note by design, this will not touch the editselection history stuff
536  */
537 void BM_elem_select_set(BMesh *bm, BMElem *ele, const bool select)
538 {
539         switch (ele->head.htype) {
540                 case BM_VERT:
541                         BM_vert_select_set(bm, (BMVert *)ele, select);
542                         break;
543                 case BM_EDGE:
544                         BM_edge_select_set(bm, (BMEdge *)ele, select);
545                         break;
546                 case BM_FACE:
547                         BM_face_select_set(bm, (BMFace *)ele, select);
548                         break;
549                 default:
550                         BLI_assert(0);
551                         break;
552         }
553 }
554
555 /* this replaces the active flag used in uv/face mode */
556 void BM_active_face_set(BMesh *bm, BMFace *efa)
557 {
558         bm->act_face = efa;
559 }
560
561 BMFace *BM_active_face_get(BMesh *bm, const bool is_sloppy, const bool is_selected)
562 {
563         if (bm->act_face && (!is_selected || BM_elem_flag_test(bm->act_face, BM_ELEM_SELECT))) {
564                 return bm->act_face;
565         }
566         else if (is_sloppy) {
567                 BMIter iter;
568                 BMFace *f = NULL;
569                 BMEditSelection *ese;
570                 
571                 /* Find the latest non-hidden face from the BMEditSelection */
572                 ese = bm->selected.last;
573                 for ( ; ese; ese = ese->prev) {
574                         if (ese->htype == BM_FACE) {
575                                 f = (BMFace *)ese->ele;
576                                 
577                                 if (BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
578                                         f = NULL;
579                                 }
580                                 else if (is_selected && !BM_elem_flag_test(f, BM_ELEM_SELECT)) {
581                                         f = NULL;
582                                 }
583                                 else {
584                                         break;
585                                 }
586                         }
587                 }
588                 /* Last attempt: try to find any selected face */
589                 if (f == NULL) {
590                         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
591                                 if (BM_elem_flag_test(f, BM_ELEM_SELECT)) {
592                                         break;
593                                 }
594                         }
595                 }
596                 return f; /* can still be null */
597         }
598         return NULL;
599 }
600
601 /**
602  * Generic way to get data from an EditSelection type
603  * These functions were written to be used by the Modifier widget
604  * when in Rotate about active mode, but can be used anywhere.
605  *
606  * - #BM_editselection_center
607  * - #BM_editselection_normal
608  * - #BM_editselection_plane
609  */
610 void BM_editselection_center(BMEditSelection *ese, float r_center[3])
611 {
612         if (ese->htype == BM_VERT) {
613                 BMVert *eve = (BMVert *)ese->ele;
614                 copy_v3_v3(r_center, eve->co);
615         }
616         else if (ese->htype == BM_EDGE) {
617                 BMEdge *eed = (BMEdge *)ese->ele;
618                 mid_v3_v3v3(r_center, eed->v1->co, eed->v2->co);
619         }
620         else if (ese->htype == BM_FACE) {
621                 BMFace *efa = (BMFace *)ese->ele;
622                 BM_face_calc_center_bounds(efa, r_center);
623         }
624 }
625
626 void BM_editselection_normal(BMEditSelection *ese, float r_normal[3])
627 {
628         if (ese->htype == BM_VERT) {
629                 BMVert *eve = (BMVert *)ese->ele;
630                 copy_v3_v3(r_normal, eve->no);
631         }
632         else if (ese->htype == BM_EDGE) {
633                 BMEdge *eed = (BMEdge *)ese->ele;
634                 float plane[3]; /* need a plane to correct the normal */
635                 float vec[3]; /* temp vec storage */
636                 
637                 add_v3_v3v3(r_normal, eed->v1->no, eed->v2->no);
638                 sub_v3_v3v3(plane, eed->v2->co, eed->v1->co);
639                 
640                 /* the 2 vertex normals will be close but not at rightangles to the edge
641                  * for rotate about edge we want them to be at right angles, so we need to
642                  * do some extra colculation to correct the vert normals,
643                  * we need the plane for this */
644                 cross_v3_v3v3(vec, r_normal, plane);
645                 cross_v3_v3v3(r_normal, plane, vec);
646                 normalize_v3(r_normal);
647                 
648         }
649         else if (ese->htype == BM_FACE) {
650                 BMFace *efa = (BMFace *)ese->ele;
651                 copy_v3_v3(r_normal, efa->no);
652         }
653 }
654
655 /* Calculate a plane that is rightangles to the edge/vert/faces normal
656  * also make the plane run along an axis that is related to the geometry,
657  * because this is used for the manipulators Y axis. */
658 void BM_editselection_plane(BMEditSelection *ese, float r_plane[3])
659 {
660         if (ese->htype == BM_VERT) {
661                 BMVert *eve = (BMVert *)ese->ele;
662                 float vec[3] = {0.0f, 0.0f, 0.0f};
663                 
664                 if (ese->prev) { /* use previously selected data to make a useful vertex plane */
665                         BM_editselection_center(ese->prev, vec);
666                         sub_v3_v3v3(r_plane, vec, eve->co);
667                 }
668                 else {
669                         /* make a fake  plane thats at rightangles to the normal
670                          * we cant make a crossvec from a vec thats the same as the vec
671                          * unlikely but possible, so make sure if the normal is (0, 0, 1)
672                          * that vec isn't the same or in the same direction even. */
673                         if      (eve->no[0] < 0.5f) vec[0] = 1.0f;
674                         else if (eve->no[1] < 0.5f) vec[1] = 1.0f;
675                         else                        vec[2] = 1.0f;
676                         cross_v3_v3v3(r_plane, eve->no, vec);
677                 }
678         }
679         else if (ese->htype == BM_EDGE) {
680                 BMEdge *eed = (BMEdge *)ese->ele;
681
682                 /* the plane is simple, it runs along the edge
683                  * however selecting different edges can swap the direction of the y axis.
684                  * this makes it less likely for the y axis of the manipulator
685                  * (running along the edge).. to flip less often.
686                  * at least its more predictable */
687                 if (eed->v2->co[1] > eed->v1->co[1]) {  /* check which to do first */
688                         sub_v3_v3v3(r_plane, eed->v2->co, eed->v1->co);
689                 }
690                 else {
691                         sub_v3_v3v3(r_plane, eed->v1->co, eed->v2->co);
692                 }
693                 
694         }
695         else if (ese->htype == BM_FACE) {
696                 BMFace *efa = (BMFace *)ese->ele;
697                 float vec[3] = {0.0f, 0.0f, 0.0f};
698                 
699                 /* for now, use face normal */
700
701                 /* make a fake plane thats at rightangles to the normal
702                  * we cant make a crossvec from a vec thats the same as the vec
703                  * unlikely but possible, so make sure if the normal is (0, 0, 1)
704                  * that vec isn't the same or in the same direction even. */
705                 if (UNLIKELY(efa->len < 3)) {
706                         /* crappy fallback method */
707                         if      (efa->no[0] < 0.5f)     vec[0] = 1.0f;
708                         else if (efa->no[1] < 0.5f)     vec[1] = 1.0f;
709                         else                        vec[2] = 1.0f;
710                         cross_v3_v3v3(r_plane, efa->no, vec);
711                 }
712                 else {
713                         if (efa->len == 3) {
714                                 BMVert *verts[3];
715                                 float lens[3];
716                                 float difs[3];
717                                 int  order[3] = {0, 1, 2};
718
719                                 BM_face_as_array_vert_tri(efa, verts);
720
721                                 lens[0] = len_v3v3(verts[0]->co, verts[1]->co);
722                                 lens[1] = len_v3v3(verts[1]->co, verts[2]->co);
723                                 lens[2] = len_v3v3(verts[2]->co, verts[0]->co);
724
725                                 /* find the shortest or the longest loop */
726                                 difs[0] = fabsf(lens[1] - lens[2]);
727                                 difs[1] = fabsf(lens[2] - lens[0]);
728                                 difs[2] = fabsf(lens[0] - lens[1]);
729
730                                 axis_sort_v3(difs, order);
731                                 sub_v3_v3v3(r_plane, verts[order[0]]->co, verts[(order[0] + 1) % 3]->co);
732                         }
733                         else if (efa->len == 4) {
734                                 BMVert *verts[4];
735                                 float vecA[3], vecB[3];
736
737                                 // BM_iter_as_array(NULL, BM_VERTS_OF_FACE, efa, (void **)verts, 4);
738                                 BM_face_as_array_vert_quad(efa, verts);
739
740                                 sub_v3_v3v3(vecA, verts[3]->co, verts[2]->co);
741                                 sub_v3_v3v3(vecB, verts[0]->co, verts[1]->co);
742                                 add_v3_v3v3(r_plane, vecA, vecB);
743
744                                 sub_v3_v3v3(vecA, verts[0]->co, verts[3]->co);
745                                 sub_v3_v3v3(vecB, verts[1]->co, verts[2]->co);
746                                 add_v3_v3v3(vec, vecA, vecB);
747                                 /* use the biggest edge length */
748                                 if (dot_v3v3(r_plane, r_plane) < dot_v3v3(vec, vec)) {
749                                         copy_v3_v3(r_plane, vec);
750                                 }
751                         }
752                         else {
753                                 BMLoop *l_long  = BM_face_find_longest_loop(efa);
754
755                                 sub_v3_v3v3(r_plane, l_long->v->co, l_long->next->v->co);
756                         }
757
758                 }
759         }
760         normalize_v3(r_plane);
761 }
762
763
764 /* --- macro wrapped funcs --- */
765 bool _bm_select_history_check(BMesh *bm, const BMHeader *ele)
766 {
767         return (BLI_findptr(&bm->selected, ele, offsetof(BMEditSelection, ele)) != NULL);
768 }
769
770 bool _bm_select_history_remove(BMesh *bm, BMHeader *ele)
771 {
772         BMEditSelection *ese = BLI_findptr(&bm->selected, ele, offsetof(BMEditSelection, ele));
773         if (ese) {
774                 BLI_freelinkN(&bm->selected, ese);
775                 return true;
776         }
777         else {
778                 return false;
779         }
780 }
781
782 void _bm_select_history_store_notest(BMesh *bm, BMHeader *ele)
783 {
784         BMEditSelection *ese = (BMEditSelection *) MEM_callocN(sizeof(BMEditSelection), "BMEdit Selection");
785         ese->htype = ele->htype;
786         ese->ele = (BMElem *)ele;
787         BLI_addtail(&(bm->selected), ese);
788 }
789
790 void _bm_select_history_store(BMesh *bm, BMHeader *ele)
791 {
792         if (!BM_select_history_check(bm, (BMElem *)ele)) {
793                 BM_select_history_store_notest(bm, (BMElem *)ele);
794         }
795 }
796 /* --- end macro wrapped funcs --- */
797
798
799 void BM_select_history_clear(BMesh *bm)
800 {
801         BLI_freelistN(&bm->selected);
802         bm->selected.first = bm->selected.last = NULL;
803 }
804
805
806 void BM_select_history_validate(BMesh *bm)
807 {
808         BMEditSelection *ese, *nextese;
809
810         ese = bm->selected.first;
811
812         while (ese) {
813                 nextese = ese->next;
814                 if (!BM_elem_flag_test(ese->ele, BM_ELEM_SELECT)) {
815                         BLI_freelinkN(&(bm->selected), ese);
816                 }
817                 ese = nextese;
818         }
819 }
820
821 /* utility function */
822 bool BM_select_history_active_get(BMesh *bm, BMEditSelection *ese)
823 {
824         BMEditSelection *ese_last = bm->selected.last;
825         BMFace *efa = BM_active_face_get(bm, false, false);
826
827         ese->next = ese->prev = NULL;
828
829         if (ese_last) {
830                 if (ese_last->htype == BM_FACE) { /* if there is an active face, use it over the last selected face */
831                         if (efa) {
832                                 ese->ele = (BMElem *)efa;
833                         }
834                         else {
835                                 ese->ele = ese_last->ele;
836                         }
837                         ese->htype = BM_FACE;
838                 }
839                 else {
840                         ese->ele =   ese_last->ele;
841                         ese->htype = ese_last->htype;
842                 }
843         }
844         else if (efa) { /* no */
845                 ese->ele   = (BMElem *)efa;
846                 ese->htype = BM_FACE;
847         }
848         else {
849                 ese->ele = NULL;
850                 return false;
851         }
852
853         return true;
854 }
855
856 void BM_mesh_elem_hflag_disable_test(BMesh *bm, const char htype, const char hflag,
857                                      const bool respecthide, const char hflag_test)
858 {
859         const char iter_types[3] = {BM_VERTS_OF_MESH,
860                                     BM_EDGES_OF_MESH,
861                                     BM_FACES_OF_MESH};
862
863         const char flag_types[3] = {BM_VERT, BM_EDGE, BM_FACE};
864
865         int i;
866
867         if (hflag & BM_ELEM_SELECT) {
868                 BM_select_history_clear(bm);
869         }
870
871         if ((htype == (BM_VERT | BM_EDGE | BM_FACE)) &&
872             (hflag == BM_ELEM_SELECT) &&
873             (respecthide == false) &&
874             (hflag_test == 0))
875         {
876                 /* fast path for deselect all, avoid topology loops
877                  * since we know all will be de-selected anyway. */
878
879 #pragma omp parallel for schedule(dynamic) if (bm->totvert + bm->totedge + bm->totface >= BM_OMP_LIMIT)
880                 for (i = 0; i < 3; i++) {
881                         BMIter iter;
882                         BMElem *ele;
883
884                         ele = BM_iter_new(&iter, bm, iter_types[i], NULL);
885                         for ( ; ele; ele = BM_iter_step(&iter)) {
886                                 BM_elem_flag_disable(ele, BM_ELEM_SELECT);
887                         }
888                 }
889
890                 bm->totvertsel = bm->totedgesel = bm->totfacesel = 0;
891         }
892         else {
893                 for (i = 0; i < 3; i++) {
894                         BMIter iter;
895                         BMElem *ele;
896
897                         if (htype & flag_types[i]) {
898                                 ele = BM_iter_new(&iter, bm, iter_types[i], NULL);
899                                 for ( ; ele; ele = BM_iter_step(&iter)) {
900
901                                         if (respecthide && BM_elem_flag_test(ele, BM_ELEM_HIDDEN)) {
902                                                 continue;
903                                         }
904                                         if (hflag_test && !BM_elem_flag_test(ele, hflag_test)) {
905                                                 continue;
906                                         }
907
908                                         if (hflag & BM_ELEM_SELECT) {
909                                                 BM_elem_select_set(bm, ele, false);
910                                         }
911                                         BM_elem_flag_disable(ele, hflag);
912                                 }
913                         }
914                 }
915         }
916 }
917
918 void BM_mesh_elem_hflag_enable_test(BMesh *bm, const char htype, const char hflag,
919                                     const bool respecthide, const char hflag_test)
920 {
921         const char iter_types[3] = {BM_VERTS_OF_MESH,
922                                     BM_EDGES_OF_MESH,
923                                     BM_FACES_OF_MESH};
924
925         const char flag_types[3] = {BM_VERT, BM_EDGE, BM_FACE};
926
927         /* use the nosel version when setting so under no
928          * condition may a hidden face become selected.
929          * Applying other flags to hidden faces is OK. */
930         const char hflag_nosel = hflag & ~BM_ELEM_SELECT;
931
932         BMIter iter;
933         BMElem *ele;
934         int i;
935
936         if (hflag & BM_ELEM_SELECT) {
937                 BM_select_history_clear(bm);
938         }
939
940         /* note, better not attempt a fast path for selection as done with de-select
941          * because hidden geometry and different selection modes can give different results,
942          * we could of course check for no hidden faces and then use quicker method but its not worth it. */
943
944         for (i = 0; i < 3; i++) {
945                 if (htype & flag_types[i]) {
946                         ele = BM_iter_new(&iter, bm, iter_types[i], NULL);
947                         for ( ; ele; ele = BM_iter_step(&iter)) {
948
949                                 if (respecthide && BM_elem_flag_test(ele, BM_ELEM_HIDDEN)) {
950                                         continue;
951                                 }
952                                 if (hflag_test && !BM_elem_flag_test(ele, hflag_test)) {
953                                         continue;
954                                 }
955
956                                 if (hflag & BM_ELEM_SELECT) {
957                                         BM_elem_select_set(bm, ele, true);
958                                 }
959                                 BM_elem_flag_enable(ele, hflag_nosel);
960                         }
961                 }
962         }
963 }
964
965 void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag,
966                                     const bool respecthide)
967 {
968         /* call with 0 hflag_test */
969         BM_mesh_elem_hflag_disable_test(bm, htype, hflag, respecthide, 0);
970 }
971
972 void BM_mesh_elem_hflag_enable_all(BMesh *bm, const char htype, const char hflag,
973                                    const bool respecthide)
974 {
975         /* call with 0 hflag_test */
976         BM_mesh_elem_hflag_enable_test(bm, htype, hflag, respecthide, 0);
977 }
978
979 /***************** Mesh Hiding stuff *********** */
980
981 static void vert_flush_hide_set(BMVert *v)
982 {
983         BMIter iter;
984         BMEdge *e;
985         bool hide = true;
986
987         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
988                 hide = hide && BM_elem_flag_test(e, BM_ELEM_HIDDEN);
989         }
990
991         BM_elem_flag_set(v, BM_ELEM_HIDDEN, hide);
992 }
993
994 static void edge_flush_hide(BMEdge *e)
995 {
996         BMIter iter;
997         BMFace *f;
998         bool hide = true;
999
1000         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
1001                 hide = hide && BM_elem_flag_test(f, BM_ELEM_HIDDEN);
1002         }
1003
1004         BM_elem_flag_set(e, BM_ELEM_HIDDEN, hide);
1005 }
1006
1007 void BM_vert_hide_set(BMVert *v, const bool hide)
1008 {
1009         /* vert hiding: vert + surrounding edges and faces */
1010         BMIter iter, fiter;
1011         BMEdge *e;
1012         BMFace *f;
1013
1014         BLI_assert(v->head.htype == BM_VERT);
1015
1016         BM_elem_flag_set(v, BM_ELEM_HIDDEN, hide);
1017
1018         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
1019                 BM_elem_flag_set(e, BM_ELEM_HIDDEN, hide);
1020
1021                 BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
1022                         BM_elem_flag_set(f, BM_ELEM_HIDDEN, hide);
1023                 }
1024         }
1025 }
1026
1027 void BM_edge_hide_set(BMEdge *e, const bool hide)
1028 {
1029         BMIter iter;
1030         BMFace *f;
1031         /* BMVert *v; */
1032
1033         BLI_assert(e->head.htype == BM_EDGE);
1034
1035         /* edge hiding: faces around the edge */
1036         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
1037                 BM_elem_flag_set(f, BM_ELEM_HIDDEN, hide);
1038         }
1039         
1040         BM_elem_flag_set(e, BM_ELEM_HIDDEN, hide);
1041
1042         /* hide vertices if necessary */
1043         vert_flush_hide_set(e->v1);
1044         vert_flush_hide_set(e->v2);
1045 }
1046
1047 void BM_face_hide_set(BMFace *f, const bool hide)
1048 {
1049         BMIter iter;
1050         BMLoop *l;
1051
1052         BLI_assert(f->head.htype == BM_FACE);
1053
1054         BM_elem_flag_set(f, BM_ELEM_HIDDEN, hide);
1055
1056         BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
1057                 edge_flush_hide(l->e);
1058         }
1059
1060         BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
1061                 vert_flush_hide_set(l->v);
1062         }
1063 }
1064
1065 void _bm_elem_hide_set(BMesh *bm, BMHeader *head, const bool hide)
1066 {
1067         /* Follow convention of always deselecting before
1068          * hiding an element */
1069         switch (head->htype) {
1070                 case BM_VERT:
1071                         if (hide) BM_vert_select_set(bm, (BMVert *)head, false);
1072                         BM_vert_hide_set((BMVert *)head, hide);
1073                         break;
1074                 case BM_EDGE:
1075                         if (hide) BM_edge_select_set(bm, (BMEdge *)head, false);
1076                         BM_edge_hide_set((BMEdge *)head, hide);
1077                         break;
1078                 case BM_FACE:
1079                         if (hide) BM_face_select_set(bm, (BMFace *)head, false);
1080                         BM_face_hide_set((BMFace *)head, hide);
1081                         break;
1082                 default:
1083                         BMESH_ASSERT(0);
1084                         break;
1085         }
1086 }