Fix T41360: Crash on Boolean Modifier

The issue was caused by the wrong attributes maps in certain
circumstances after union intersections.

Namely issue might have happen when more than one iteration of
union was happening and it was caused by the fact that new faces
might be allocated on the same address as freed face from the
old mesh.

Didn't find a nicer fix for this apart from correcting the whole
attributes map after each union step.

We could try removing attributes for the meshes which are getting
deleted, but in asymptotic it's gonna to give exactly the same
complexity as the current approach.

3 files changed, 40 insertions, 21 deletions

diff --git a/extern/carve/carve-capi.cc b/extern/carve/carve-capi.cc
index d8c7727605c..5648977ad27 100644
--- a/extern/carve/carve-capi.cc
+++ b/extern/carve/carve-capi.cc
@@ -555,6 +555,19 @@ void cleanupFaceEdgeAttrs(const MeshSet<3> *left,
 	interpolator->swapAttributes(&new_interpolator);
 }
 
+void cleanupFaceEdgeAttrsCallback(const MeshSet<3> *left,
+                                  const MeshSet<3> *right,
+                                  void *descr_v)
+{
+	CarveMeshDescr *descr = (CarveMeshDescr *) descr_v;
+	cleanupFaceEdgeAttrs(left,
+	                     right,
+	                     &descr->face_edge_triangulated_flag);
+	cleanupFaceEdgeAttrs(left,
+	                     right,
+	                     &descr->orig_face_edge_mapping);
+}
+
 }  // namespace
 
 CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
@@ -737,14 +750,9 @@ bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
 		// intersecting that meshes tessellation of operation result can't be
 		// done properly. The only way to make such situations working is to
 		// union intersecting meshes of the same operand.
-		if (carve_unionIntersections(&csg, &left, &right)) {
-			cleanupFaceEdgeAttrs(left,
-			                     right,
-			                     &output_descr->face_edge_triangulated_flag);
-			cleanupFaceEdgeAttrs(left,
-			                     right,
-			                     &output_descr->orig_face_edge_mapping);
-		}
+		carve_unionIntersections(&csg, &left, &right,
+		                         cleanupFaceEdgeAttrsCallback,
+		                         (void *) output_descr);
 
 		left_mesh->poly = left;
 		right_mesh->poly = right;
diff --git a/extern/carve/carve-util.cc b/extern/carve/carve-util.cc
index 1106fa16a21..0dff1deb750 100644
--- a/extern/carve/carve-util.cc
+++ b/extern/carve/carve-util.cc
@@ -365,7 +365,10 @@ MeshSet<3> *getIntersectedOperand(std::vector<MeshSet<3>::mesh_t*> *meshes,
 
 MeshSet<3> *unionIntersectingMeshes(carve::csg::CSG *csg,
                                     MeshSet<3> *poly,
-                                    const MeshSet<3>::aabb_t &otherAABB)
+                                    const MeshSet<3> *other_poly,
+                                    const MeshSet<3>::aabb_t &otherAABB,
+                                    UnionIntersectionsCallback callback,
+                                    void *user_data)
 {
 	if (poly->meshes.size() <= 1) {
 		return poly;
@@ -409,6 +412,7 @@ MeshSet<3> *unionIntersectingMeshes(carve::csg::CSG *csg,
 				                                  carve::csg::CSG::UNION,
 				                                  NULL, carve::csg::CSG::CLASSIFY_EDGE);
 
+				callback(result, other_poly, user_data);
 				delete left;
 				delete right;
 
@@ -420,6 +424,8 @@ MeshSet<3> *unionIntersectingMeshes(carve::csg::CSG *csg,
 
 			MeshSet<3> *result = meshSetFromTwoMeshes(left->meshes, right->meshes);
 
+			callback(result, other_poly, user_data);
+
 			delete left;
 			delete right;
 
@@ -455,37 +461,36 @@ MeshSet<3> *unionIntersectingMeshes(carve::csg::CSG *csg,
 
 // TODO(sergey): This function is to be totally re-implemented to make it
 // more clear what's going on and hopefully optimize it as well.
-bool carve_unionIntersections(carve::csg::CSG *csg,
+void carve_unionIntersections(carve::csg::CSG *csg,
                               MeshSet<3> **left_r,
-                              MeshSet<3> **right_r)
+                              MeshSet<3> **right_r,
+                              UnionIntersectionsCallback callback,
+                              void *user_data)
 {
 	MeshSet<3> *left = *left_r, *right = *right_r;
-	bool changed = false;
 
 	if (left->meshes.size() == 1 && right->meshes.size() == 0) {
-		return false;
+		return;
 	}
 
 	MeshSet<3>::aabb_t leftAABB = left->getAABB();
 	MeshSet<3>::aabb_t rightAABB = right->getAABB();;
 
-	left = unionIntersectingMeshes(csg, left, rightAABB);
-	right = unionIntersectingMeshes(csg, right, leftAABB);
+	left = unionIntersectingMeshes(csg, left, right, rightAABB,
+	                               callback, user_data);
+	right = unionIntersectingMeshes(csg, right, left, leftAABB,
+	                                callback, user_data);
 
 	if (left != *left_r) {
-		changed = true;
 		delete *left_r;
 	}
 
 	if (right != *right_r) {
-		changed = true;
 		delete *right_r;
 	}
 
 	*left_r = left;
 	*right_r = right;
-
-	return changed;
 }
 
 static inline void add_newell_cross_v3_v3v3(const Vector &v_prev,
diff --git a/extern/carve/carve-util.h b/extern/carve/carve-util.h
index 0b509aa3cab..3edf1bb1c02 100644
--- a/extern/carve/carve-util.h
+++ b/extern/carve/carve-util.h
@@ -70,9 +70,15 @@ void carve_getRescaleMinMax(const carve::mesh::MeshSet<3> *left,
                             carve::geom3d::Vector *min,
                             carve::geom3d::Vector *max);
 
-bool carve_unionIntersections(carve::csg::CSG *csg,
+typedef void (*UnionIntersectionsCallback) (const carve::mesh::MeshSet<3> *left,
+                                            const carve::mesh::MeshSet<3> *right,
+                                            void *userdata);
+
+void carve_unionIntersections(carve::csg::CSG *csg,
                               carve::mesh::MeshSet<3> **left_r,
-                              carve::mesh::MeshSet<3> **right_r);
+                              carve::mesh::MeshSet<3> **right_r,
+                              UnionIntersectionsCallback callback,
+                              void *user_data);
 
 bool carve_checkPolyPlanarAndGetNormal(const std::vector<carve::mesh::MeshSet<3>::vertex_t> &vertex_storage,
                                        const int verts_per_poly,