Bmesh booleans fail on simple cube array
Open, ConfirmedPublic

Description

This Bmesh based boolean setup brings wrong results compared to Carve. It's a typical use case from a visualization project.

array.blend

Tested with the official Blender release on Windows 7 64

Some background:

I'm doing architectural visualizations so I often use boolean operations to create flexible and changeable setups of facades in case architects change their minds about a design during the project. When using booleans on a regular basis on complex stuff like me then it is inevitable to recognize that the Bmesh booleans are still inferior to those of Carve. Since I assume that Carve is a library you would like to drop at some point in the future, I would like to express my concerns that this must not happen until Bmesh booleans are at least as reliable as Carve is. This should really be a condition from my point of view as a user, some people have to work with it after all.

Anyways, I have great respect for your work and I'm willing to provide more bug reports on the matter until this target is reached. Consider this only being the first one.

Details

Type
Bug
Konstantin (Ko) triaged this task as "Confirmed" priority.Dec 3 2016, 1:29 PM
Konstantin (Ko) added a subscriber: Konstantin (Ko).

Do not hope for a quick solution to this problem. Developer of modelling tools and bmesh has withdrew from active blender development. It could take years before bmesh boolean mode will be corrected by someone else

Then I suggest to change the default method back to Carve until someone will take care of the Bmesh method. In the current state and without active development this is an experimental feature at best.

BMesh Boolean currently has it's own limitations and failure cases.

To check some of them you can look at the task T47030 that tracked related issues.

Using 'Carve' fixes the issue. Head over to the Modifier stack and use the Drop-down menu for the Boolean Modifier to change the solver from BMesh to Carve.

Using Carve actually doesn't fix the issue in Bmesh but thanks anyway. ;)

Here's what I've found:

  • bm_face_split_edgenet_find_connection( ) creates edges that are parallel to other edges. This causes face creation to fail when it sorts the edges by angle.
  • bm_face_split_edgenet_find_loop_pair( ) fails when multiple boundaries and wires are connected as it gives priority to wires, in some cases it selects edges that cannot form a face.

Additionally I get a failed assert on line 560, the stack 'vert_queue' is overflowing, I'm not sure what the reasoning behind it's declared size is so I didn't change it.

This works for the given case:

1diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
2index 6ce7c10..56548d1 100644
3--- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
4+++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
5@@ -105,6 +105,16 @@ static void normalize_v2_m3_v3v3(float out[2], float axis_mat[3][3], const float
6​ normalize_v2(out);
7​ }
8
9+static float angle_clockwise_v2v2(const float v1[2], const float v2[2]) {
10+ float angle = dot_v2v2(v1, v2);
11+
12+ /* same formula as line_point_side_v2() with the first argument zero */
13+ if (((v1[0] - v2[0]) * v2[1]) > (v2[0] * (v1[1] - v2[1]))) {
14+ return angle;
15+ } else {
16+ return -2 - angle;
17+ }
18+}
19
20​ /**
21​ * \note Be sure to update #bm_face_split_edgenet_find_loop_pair_exists
22@@ -152,33 +162,32 @@ static bool bm_face_split_edgenet_find_loop_pair(
23​ }
24​ e_pair[0] = BLI_SMALLSTACK_POP(edges_boundary);
25
26- /* use to hold boundary OR wire edges */
27- BLI_SMALLSTACK_DECLARE(edges_search, BMEdge *);
28-
29​ /* attempt one boundary and one wire, or 2 boundary */
30- if (edges_wire_len == 0) {
31- if (edges_boundary_len > 1) {
32- e_pair[1] = BLI_SMALLSTACK_POP(edges_boundary);
33-
34- if (edges_boundary_len > 2) {
35- BLI_SMALLSTACK_SWAP(edges_search, edges_boundary);
36- }
37- }
38- else {
39- /* one boundary and no wire */
40- return false;
41- }
42+ if (edges_wire_len > 0) {
43+ /* use one boundary and one wire */
44+ e_pair[1] = BLI_SMALLSTACK_POP(edges_wire);
45+ }
46+ else if (edges_boundary_len > 1) {
47+ /* use 2 boundaries */
48+ e_pair[1] = BLI_SMALLSTACK_POP(edges_boundary);
49​ }
50​ else {
51- e_pair[1] = BLI_SMALLSTACK_POP(edges_wire);
52- if (edges_wire_len > 1) {
53- BLI_SMALLSTACK_SWAP(edges_search, edges_wire);
54- }
55+ /* one boundary and no wire */
56+ return false;
57+ }
58+
59+ /* flip based on winding */
60+ l_walk = bm_edge_flagged_radial_first(e_pair[0]);
61+ swap = false;
62+ if (face_normal == l_walk->f->no) {
63+ swap = !swap;
64+ }
65+ if (l_walk->v != v_init) {
66+ swap = !swap;
67​ }
68
69- /* if we swapped above, search this list for the best edge */
70- if (!BLI_SMALLSTACK_IS_EMPTY(edges_search)) {
71- /* find the best edge in 'edge_list' to use for 'e_pair[1]' */
72+ /* if there are more edges, search for the best edge to use for 'e_pair[1]'*/
73+ if (edges_wire_len > 1 || edges_boundary_len > 2) {
74​ const BMVert *v_prev = BM_edge_other_vert(e_pair[0], v_init);
75​ const BMVert *v_next = BM_edge_other_vert(e_pair[1], v_init);
76
77@@ -186,32 +195,23 @@ static bool bm_face_split_edgenet_find_loop_pair(
78
79​ normalize_v2_m3_v3v3(dir_prev, face_normal_matrix, v_prev->co, v_init->co);
80​ normalize_v2_m3_v3v3(dir_next, face_normal_matrix, v_next->co, v_init->co);
81- float angle_best_cos = dot_v2v2(dir_next, dir_prev);
82+ float angle_best_cos = angle_clockwise_v2v2(dir_prev, dir_next);
83
84​ BMEdge *e;
85- while ((e = BLI_SMALLSTACK_POP(edges_search))) {
86+ while ((e = BLI_SMALLSTACK_POP(edges_boundary)) || (e = BLI_SMALLSTACK_POP(edges_wire))) {
87​ v_next = BM_edge_other_vert(e, v_init);
88​ float dir_test[2];
89
90​ normalize_v2_m3_v3v3(dir_test, face_normal_matrix, v_next->co, v_init->co);
91- const float angle_test_cos = dot_v2v2(dir_prev, dir_test);
92+ const float angle_test_cos = angle_clockwise_v2v2(dir_prev, dir_test);
93
94- if (angle_test_cos > angle_best_cos) {
95+ if (swap ? (angle_test_cos > angle_best_cos) : (angle_test_cos < angle_best_cos)) {
96​ angle_best_cos = angle_test_cos;
97​ e_pair[1] = e;
98​ }
99​ }
100​ }
101
102- /* flip based on winding */
103- l_walk = bm_edge_flagged_radial_first(e_pair[0]);
104- swap = false;
105- if (face_normal == l_walk->f->no) {
106- swap = !swap;
107- }
108- if (l_walk->v != v_init) {
109- swap = !swap;
110- }
111​ if (swap) {
112​ SWAP(BMEdge *, e_pair[0], e_pair[1]);
113​ }
114@@ -255,18 +255,16 @@ static bool bm_face_split_edgenet_find_loop_pair_exists(
115​ }
116
117​ /* attempt one boundary and one wire, or 2 boundary */
118- if (edges_wire_len == 0) {
119- if (edges_boundary_len >= 2) {
120- /* pass */
121- }
122- else {
123- /* one boundary and no wire */
124- return false;
125- }
126+ if (edges_wire_len > 0) {
127+ /* pass */
128​ }
129- else {
130+ else if (edges_boundary_len > 1) {
131​ /* pass */
132​ }
133+ else {
134+ /* one boundary and no wire */
135+ return false;
136+ }
137
138​ return true;
139​ }
140@@ -978,8 +976,8 @@ static int bm_face_split_edgenet_find_connection(
141​ for (int j = 0; j < 2; j++) {
142​ BMVert *v_iter = v_pair[j];
143​ if (BM_elem_flag_test(v_iter, VERT_IS_VALID)) {
144- if (direction_sign ? (v_iter->co[SORT_AXIS] >= v_origin->co[SORT_AXIS]) :
145- (v_iter->co[SORT_AXIS] <= v_origin->co[SORT_AXIS]))
146+ if (direction_sign ? (v_iter->co[SORT_AXIS] > v_origin->co[SORT_AXIS]) :
147+ (v_iter->co[SORT_AXIS] < v_origin->co[SORT_AXIS]))
148​ {
149​ BLI_SMALLSTACK_PUSH(vert_search, v_iter);
150​ BLI_SMALLSTACK_PUSH(vert_blacklist, v_iter);

Add Comment