Bmesh booleans fail on simple cube array #50165

New Issue

Kai Kostack · 2016-12-03T11:31:28+01:00

Kai Kostack commented

2016-12-03 11:31:28 +01:00

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.

This Bmesh based boolean setup brings wrong results compared to Carve. It's a typical use case from a visualization project. ![array.jpg](https://archive.blender.org/developer/F413550/array.jpg) [array.blend](https://archive.blender.org/developer/F413552/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.

Kai Kostack commented

2016-12-03 11:31:28 +01:00

Changed status to: 'Open'

Kai Kostack commented

2016-12-03 11:31:28 +01:00

Added subscriber: @KaiKostack-3

Konstantin commented

2016-12-03 13:29:05 +01:00

Added subscriber: @Ko

Konstantin commented

2016-12-03 13:29:05 +01:00

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

Kai Kostack commented

2016-12-03 14:00:59 +01:00

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.

Vuk Gardašević commented

2016-12-03 17:45:02 +01:00

Added subscriber: @VukGardasevic

Vuk Gardašević commented

2016-12-03 17:45:02 +01:00

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

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

BMesh Boolean currently has it's own limitations and failure cases. To check some of them you can look at the task #47030 that tracked related issues.

marc dion commented

2016-12-11 02:13:14 +01:00

Added subscriber: @MarcClintDion

marc dion commented

2016-12-11 02:13:14 +01:00

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' 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. ![bMeshToCarve.jpg](https://archive.blender.org/developer/F416536/bMeshToCarve.jpg)

Kai Kostack commented

2016-12-11 10:22:03 +01:00

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

Kenrick commented

2017-01-08 00:59:10 +01:00

Added subscriber: @Prototype-1

Kenrick commented

2017-01-08 00:59:10 +01:00

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:
P434: Possible fix for #50165

diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
index 6ce7c10..56548d1 100644
--- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
+++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
@@ -105,6 +105,16 @@ static void normalize_v2_m3_v3v3(float out- [x], float axis_mat- [x]- [x], const float
 	normalize_v2(out);
 }
 
+static float angle_clockwise_v2v2(const float v1- [x], const float v2[2]) {
+	float angle = dot_v2v2(v1, v2);
+
+	/* same formula as line_point_side_v2() with the first argument zero */
+	if (((v1- [x] - v2- [x]) * v2- [x]) > (v2- [x] * (v1- [x] - v2[1]))) {
+		return angle;
+	} else {
+		return -2 - angle;
+	}
+}
 
 /**
  * \note Be sure to update #bm_face_split_edgenet_find_loop_pair_exists
@@ -152,33 +162,32 @@ static bool bm_face_split_edgenet_find_loop_pair(
 	}
 	e_pair- [x] = BLI_SMALLSTACK_POP(edges_boundary);
 
-	/* use to hold boundary OR wire edges */
-	BLI_SMALLSTACK_DECLARE(edges_search, BMEdge *);
-
 	/* attempt one boundary and one wire, or 2 boundary */
-	if (edges_wire_len == 0) {
-		if (edges_boundary_len > 1) {
-			e_pair- [x] = BLI_SMALLSTACK_POP(edges_boundary);
-
-			if (edges_boundary_len > 2) {
-				BLI_SMALLSTACK_SWAP(edges_search, edges_boundary);
-			}
-		}
-		else {
-			/* one boundary and no wire */
-			return false;
-		}
+	if (edges_wire_len > 0) {
+		/* use one boundary and one wire */
+		e_pair- [x] = BLI_SMALLSTACK_POP(edges_wire);
+	}
+	else if (edges_boundary_len > 1) {
+		/* use 2 boundaries */
+		e_pair- [x] = BLI_SMALLSTACK_POP(edges_boundary);
 	}
 	else {
-		e_pair- [x] = BLI_SMALLSTACK_POP(edges_wire);
-		if (edges_wire_len > 1) {
-			BLI_SMALLSTACK_SWAP(edges_search, edges_wire);
-		}
+		/* one boundary and no wire */
+		return false;
+	}
+
+	/* flip based on winding */
+	l_walk = bm_edge_flagged_radial_first(e_pair[0]);
+	swap = false;
+	if (face_normal == l_walk->f->no) {
+		swap = !swap;
+	}
+	if (l_walk->v != v_init) {
+		swap = !swap;
 	}
 
-	/* if we swapped above, search this list for the best edge */
-	if (!BLI_SMALLSTACK_IS_EMPTY(edges_search)) {
-		/* find the best edge in 'edge_list' to use for 'e_pair[1]' */
+	/* if there are more edges, search for the best edge to use for 'e_pair[1]'*/
+	if (edges_wire_len > 1 || edges_boundary_len > 2) {
 		const BMVert *v_prev = BM_edge_other_vert(e_pair- [x], v_init);
 		const BMVert *v_next = BM_edge_other_vert(e_pair- [x], v_init);
 
@@ -186,32 +195,23 @@ static bool bm_face_split_edgenet_find_loop_pair(
 
 		normalize_v2_m3_v3v3(dir_prev, face_normal_matrix, v_prev->co, v_init->co);
 		normalize_v2_m3_v3v3(dir_next, face_normal_matrix, v_next->co, v_init->co);
-		float angle_best_cos = dot_v2v2(dir_next, dir_prev);
+		float angle_best_cos = angle_clockwise_v2v2(dir_prev, dir_next);
 
 		BMEdge *e;
-		while ((e = BLI_SMALLSTACK_POP(edges_search))) {
+		while ((e = BLI_SMALLSTACK_POP(edges_boundary)) || (e = BLI_SMALLSTACK_POP(edges_wire))) {
 			v_next = BM_edge_other_vert(e, v_init);
 			float dir_test[2];
 
 			normalize_v2_m3_v3v3(dir_test, face_normal_matrix, v_next->co, v_init->co);
-			const float angle_test_cos = dot_v2v2(dir_prev, dir_test);
+			const float angle_test_cos = angle_clockwise_v2v2(dir_prev, dir_test);
 
-			if (angle_test_cos > angle_best_cos) {
+			if (swap ? (angle_test_cos > angle_best_cos) : (angle_test_cos < angle_best_cos)) {
 				angle_best_cos = angle_test_cos;
 				e_pair- [x] = e;
 			}
 		}
 	}
 
-	/* flip based on winding */
-	l_walk = bm_edge_flagged_radial_first(e_pair[0]);
-	swap = false;
-	if (face_normal == l_walk->f->no) {
-		swap = !swap;
-	}
-	if (l_walk->v != v_init) {
-		swap = !swap;
-	}
 	if (swap) {
 		SWAP(BMEdge *, e_pair- [x], e_pair[1]);
 	}
@@ -255,18 +255,16 @@ static bool bm_face_split_edgenet_find_loop_pair_exists(
 	}
 
 	/* attempt one boundary and one wire, or 2 boundary */
-	if (edges_wire_len == 0) {
-		if (edges_boundary_len >= 2) {
-			/* pass */
-		}
-		else {
-			/* one boundary and no wire */
-			return false;
-		}
+	if (edges_wire_len > 0) {
+		/* pass */
 	}
-	else {
+	else if (edges_boundary_len > 1) {
 		/* pass */
 	}
+	else {
+		/* one boundary and no wire */
+		return false;
+	}
 
 	return true;
 }
@@ -978,8 +976,8 @@ static int bm_face_split_edgenet_find_connection(
 			for (int j = 0; j < 2; j++) {
 				BMVert *v_iter = v_pair[j];
 				if (BM_elem_flag_test(v_iter, VERT_IS_VALID)) {
-					if (direction_sign ? (v_iter->co[SORT_AXIS] >= v_origin->co[SORT_AXIS]) :
-					                     (v_iter->co[SORT_AXIS] <= v_origin->co[SORT_AXIS]))
+					if (direction_sign ? (v_iter->co[SORT_AXIS] > v_origin->co[SORT_AXIS]) :
+					                     (v_iter->co[SORT_AXIS] < v_origin->co[SORT_AXIS]))
 					{
 						BLI_SMALLSTACK_PUSH(vert_search, v_iter);
 						BLI_SMALLSTACK_PUSH(vert_blacklist, v_iter);

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: [P434: Possible fix for #50165](https://archive.blender.org/developer/P434.txt) ```diff diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c index 6ce7c10..56548d1 100644 --- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c +++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c @@ -105,6 +105,16 @@ static void normalize_v2_m3_v3v3(float out- [x], float axis_mat- [x]- [x], const float normalize_v2(out); } +static float angle_clockwise_v2v2(const float v1- [x], const float v2[2]) { + float angle = dot_v2v2(v1, v2); + + /* same formula as line_point_side_v2() with the first argument zero */ + if (((v1- [x] - v2- [x]) * v2- [x]) > (v2- [x] * (v1- [x] - v2[1]))) { + return angle; + } else { + return -2 - angle; + } +} /** * \note Be sure to update #bm_face_split_edgenet_find_loop_pair_exists @@ -152,33 +162,32 @@ static bool bm_face_split_edgenet_find_loop_pair( } e_pair- [x] = BLI_SMALLSTACK_POP(edges_boundary); - /* use to hold boundary OR wire edges */ - BLI_SMALLSTACK_DECLARE(edges_search, BMEdge *); - /* attempt one boundary and one wire, or 2 boundary */ - if (edges_wire_len == 0) { - if (edges_boundary_len > 1) { - e_pair- [x] = BLI_SMALLSTACK_POP(edges_boundary); - - if (edges_boundary_len > 2) { - BLI_SMALLSTACK_SWAP(edges_search, edges_boundary); - } - } - else { - /* one boundary and no wire */ - return false; - } + if (edges_wire_len > 0) { + /* use one boundary and one wire */ + e_pair- [x] = BLI_SMALLSTACK_POP(edges_wire); + } + else if (edges_boundary_len > 1) { + /* use 2 boundaries */ + e_pair- [x] = BLI_SMALLSTACK_POP(edges_boundary); } else { - e_pair- [x] = BLI_SMALLSTACK_POP(edges_wire); - if (edges_wire_len > 1) { - BLI_SMALLSTACK_SWAP(edges_search, edges_wire); - } + /* one boundary and no wire */ + return false; + } + + /* flip based on winding */ + l_walk = bm_edge_flagged_radial_first(e_pair[0]); + swap = false; + if (face_normal == l_walk->f->no) { + swap = !swap; + } + if (l_walk->v != v_init) { + swap = !swap; } - /* if we swapped above, search this list for the best edge */ - if (!BLI_SMALLSTACK_IS_EMPTY(edges_search)) { - /* find the best edge in 'edge_list' to use for 'e_pair[1]' */ + /* if there are more edges, search for the best edge to use for 'e_pair[1]'*/ + if (edges_wire_len > 1 || edges_boundary_len > 2) { const BMVert *v_prev = BM_edge_other_vert(e_pair- [x], v_init); const BMVert *v_next = BM_edge_other_vert(e_pair- [x], v_init); @@ -186,32 +195,23 @@ static bool bm_face_split_edgenet_find_loop_pair( normalize_v2_m3_v3v3(dir_prev, face_normal_matrix, v_prev->co, v_init->co); normalize_v2_m3_v3v3(dir_next, face_normal_matrix, v_next->co, v_init->co); - float angle_best_cos = dot_v2v2(dir_next, dir_prev); + float angle_best_cos = angle_clockwise_v2v2(dir_prev, dir_next); BMEdge *e; - while ((e = BLI_SMALLSTACK_POP(edges_search))) { + while ((e = BLI_SMALLSTACK_POP(edges_boundary)) || (e = BLI_SMALLSTACK_POP(edges_wire))) { v_next = BM_edge_other_vert(e, v_init); float dir_test[2]; normalize_v2_m3_v3v3(dir_test, face_normal_matrix, v_next->co, v_init->co); - const float angle_test_cos = dot_v2v2(dir_prev, dir_test); + const float angle_test_cos = angle_clockwise_v2v2(dir_prev, dir_test); - if (angle_test_cos > angle_best_cos) { + if (swap ? (angle_test_cos > angle_best_cos) : (angle_test_cos < angle_best_cos)) { angle_best_cos = angle_test_cos; e_pair- [x] = e; } } } - /* flip based on winding */ - l_walk = bm_edge_flagged_radial_first(e_pair[0]); - swap = false; - if (face_normal == l_walk->f->no) { - swap = !swap; - } - if (l_walk->v != v_init) { - swap = !swap; - } if (swap) { SWAP(BMEdge *, e_pair- [x], e_pair[1]); } @@ -255,18 +255,16 @@ static bool bm_face_split_edgenet_find_loop_pair_exists( } /* attempt one boundary and one wire, or 2 boundary */ - if (edges_wire_len == 0) { - if (edges_boundary_len >= 2) { - /* pass */ - } - else { - /* one boundary and no wire */ - return false; - } + if (edges_wire_len > 0) { + /* pass */ } - else { + else if (edges_boundary_len > 1) { /* pass */ } + else { + /* one boundary and no wire */ + return false; + } return true; } @@ -978,8 +976,8 @@ static int bm_face_split_edgenet_find_connection( for (int j = 0; j < 2; j++) { BMVert *v_iter = v_pair[j]; if (BM_elem_flag_test(v_iter, VERT_IS_VALID)) { - if (direction_sign ? (v_iter->co[SORT_AXIS] >= v_origin->co[SORT_AXIS]) : - (v_iter->co[SORT_AXIS] <= v_origin->co[SORT_AXIS])) + if (direction_sign ? (v_iter->co[SORT_AXIS] > v_origin->co[SORT_AXIS]) : + (v_iter->co[SORT_AXIS] < v_origin->co[SORT_AXIS])) { BLI_SMALLSTACK_PUSH(vert_search, v_iter); BLI_SMALLSTACK_PUSH(vert_blacklist, v_iter); ``` ![booleanBmeshFixed.PNG](https://archive.blender.org/developer/F429553/booleanBmeshFixed.PNG)

Ian Bruce commented

2017-05-29 21:53:13 +02:00

Added subscriber: @ian_bruce

Ian Bruce commented

2017-05-29 21:53:13 +02:00

For a much simpler testcase, apparently demonstrating a similar problem -- non-solid objects resulting from boolean intersect with BMesh -- see #51236 . Again, "Carve" produces the correct result, "BMesh" doesn't.

Campbell Barton commented

2017-09-16 09:15:28 +02:00

Added subscriber: @ideasman42

Campbell Barton commented

2017-09-16 09:15:28 +02:00

Changed status from 'Open' to: 'Resolved'

Campbell Barton closed this issue

2017-09-16 09:15:28 +02:00

Campbell Barton self-assigned this 2017-09-16 09:15:28 +02:00

Campbell Barton commented

2017-09-16 09:15:28 +02:00

@Prototype-1 - thanks for looking into a fix, however this now works in 2.79.

Although the changes in your patch may still be an improvement on the existing logic.
I've uploaded an updated version of your patch at D2844

I'd be interested to find if this fixed any cases that are broken in master.

Note the 'vert_queue' is overflowing bug you ran into has been fixed too 1247f609d4

@Prototype-1 - thanks for looking into a fix, however this now works in 2.79. Although the changes in your patch may still be an improvement on the existing logic. I've uploaded an updated version of your patch at [D2844](https://archive.blender.org/developer/D2844) I'd be interested to find if this fixed any cases that are broken in master. Note the `'vert_queue' is overflowing` bug you ran into has been fixed too 1247f609d4

Sign in to join this conversation.

No Label

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Bmesh booleans fail on simple cube array #50165