[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [43642] trunk/blender: Fix #29934: New Carve library can't execute boolean operations in some cases

Sergey Sharybin sergey.vfx at gmail.com
Mon Jan 23 18:43:55 CET 2012


Revision: 43642
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=43642
Author:   nazgul
Date:     2012-01-23 17:43:41 +0000 (Mon, 23 Jan 2012)
Log Message:
-----------
Fix #29934: New Carve library can't execute boolean operations in some cases

Issue was caused by left boolean operand consist of several intersecting manifolds
which make Carve triangulator confused and which can't be resolved in general case.
Added mesh pre-processing before actual applying boolean operator on it. This
preprocessing applies union operation on intersecting manifolds of the same object
so intersection edge loop with second object wouldn't confuse tesselator and correct
result would be returned.
Detecting of intersecting manifolds is based on AABB intersection check which leads
to some extra union operation called, but it's possible to speed things up from
Carve side so union operation of two not intersecting meshes would work faster.
Additional condition for running union for manifold is this manifolds intersects
AABB of second operand, so mesh topology wouldn't be changed at all in areas
where there's definitely no intersection between operands. It might be improved
so only manifolds which actually intersects second operand would be joined
together, but it'll slow things down a bit and prefer to do it only if it'll
be really a problem.

Additional change is fixed memory leak when boolean operation fails to run -
it was missed "delete" call if exception happens in Carve library.

>From side effects of this change might be named boolean operation between
suzanne and another object: suzanne is consist of three intersecting open
manifolds, so this new meshes preprocessing leads to missed eyes in result
because of failure of merging two open manifolds. Don't think making suzanne
work for all setups should really be a goal, it's a bit crappy mesh for CSG
algorithms.

Modified Paths:
--------------
    trunk/blender/intern/boolop/intern/BOP_CarveInterface.cpp
    trunk/blender/source/blender/modifiers/intern/MOD_boolean_util.c

Modified: trunk/blender/intern/boolop/intern/BOP_CarveInterface.cpp
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_CarveInterface.cpp	2012-01-23 17:17:08 UTC (rev 43641)
+++ trunk/blender/intern/boolop/intern/BOP_CarveInterface.cpp	2012-01-23 17:43:41 UTC (rev 43642)
@@ -36,6 +36,8 @@
 #include <carve/interpolator.hpp>
 #include <carve/rescale.hpp>
 
+#include <iostream>
+
 typedef unsigned int uint;
 
 #define MAX(x,y) ((x)>(y)?(x):(y))
@@ -61,10 +63,159 @@
 	return 1;
 }
 
+static carve::mesh::MeshSet<3> *Carve_meshSetFromMeshes(std::vector<carve::mesh::MeshSet<3>::mesh_t*> &meshes)
+{
+	std::vector<carve::mesh::MeshSet<3>::mesh_t*> new_meshes;
+
+	std::vector<carve::mesh::MeshSet<3>::mesh_t*>::iterator it = meshes.begin();
+	for(; it!=meshes.end(); it++) {
+		carve::mesh::MeshSet<3>::mesh_t *mesh = *it;
+		carve::mesh::MeshSet<3>::mesh_t *new_mesh = new carve::mesh::MeshSet<3>::mesh_t(mesh->faces);
+
+		new_meshes.push_back(new_mesh);
+	}
+
+	return new carve::mesh::MeshSet<3>(new_meshes);
+}
+
+static void Carve_getIntersectedOperandMeshes(std::vector<carve::mesh::MeshSet<3>::mesh_t*> &meshes,
+                                              std::vector<carve::mesh::MeshSet<3>::aabb_t> &precomputedAABB,
+                                              carve::mesh::MeshSet<3>::aabb_t &otherAABB,
+                                              std::vector<carve::mesh::MeshSet<3>::mesh_t*> &operandMeshes)
+{
+	std::vector<carve::mesh::MeshSet<3>::mesh_t*>::iterator it = meshes.begin();
+	std::vector<carve::mesh::MeshSet<3>::aabb_t>::iterator aabb_it = precomputedAABB.begin();
+	std::vector<carve::mesh::MeshSet<3>::aabb_t> usedAABB;
+
+	while(it != meshes.end()) {
+		carve::mesh::MeshSet<3>::mesh_t *mesh = *it;
+		carve::mesh::MeshSet<3>::aabb_t aabb = mesh->getAABB();
+		bool isIntersect = false;
+
+		std::vector<carve::mesh::MeshSet<3>::aabb_t>::iterator used_it = usedAABB.begin();
+		for(; used_it!=usedAABB.end(); used_it++) {
+			carve::mesh::MeshSet<3>::aabb_t usedAABB = *used_it;
+
+			if(usedAABB.intersects(aabb) && usedAABB.intersects(otherAABB)) {
+				isIntersect = true;
+				break;
+			}
+		}
+
+		if(!isIntersect) {
+			operandMeshes.push_back(mesh);
+			usedAABB.push_back(aabb);
+
+			it = meshes.erase(it);
+			aabb_it = precomputedAABB.erase(aabb_it);
+		}
+		else {
+			it++;
+			aabb_it++;
+		}
+	}
+}
+
+static carve::mesh::MeshSet<3> *Carve_getIntersectedOperand(std::vector<carve::mesh::MeshSet<3>::mesh_t*> &meshes,
+                                                            std::vector<carve::mesh::MeshSet<3>::aabb_t> &precomputedAABB,
+                                                            carve::mesh::MeshSet<3>::aabb_t &otherAABB)
+{
+	std::vector<carve::mesh::MeshSet<3>::mesh_t*> operandMeshes;
+	Carve_getIntersectedOperandMeshes(meshes, precomputedAABB, otherAABB, operandMeshes);
+
+	return Carve_meshSetFromMeshes(operandMeshes);
+}
+
+static carve::mesh::MeshSet<3> *Carve_unionIntersectingMeshes(carve::mesh::MeshSet<3> *poly,
+                                                              std::vector<carve::mesh::MeshSet<3>::aabb_t> &precomputedAABB,
+                                                              carve::mesh::MeshSet<3>::aabb_t &otherAABB,
+                                                              carve::interpolate::FaceAttr<uint> &oface_num)
+{
+	if(poly->meshes.size()<=1)
+		return poly;
+
+	carve::csg::CSG csg;
+
+	oface_num.installHooks(csg);
+	csg.hooks.registerHook(new carve::csg::CarveTriangulator, carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT);
+
+	std::vector<carve::mesh::MeshSet<3>::mesh_t*> orig_meshes = std::vector<carve::mesh::MeshSet<3>::mesh_t*>(poly->meshes.begin(), poly->meshes.end());
+
+	carve::mesh::MeshSet<3> *left = Carve_getIntersectedOperand(orig_meshes, precomputedAABB, otherAABB);
+
+	while(orig_meshes.size()) {
+		carve::mesh::MeshSet<3> *right = Carve_getIntersectedOperand(orig_meshes, precomputedAABB, otherAABB);
+
+		try {
+			carve::mesh::MeshSet<3> *result = csg.compute(left, right, carve::csg::CSG::UNION, NULL, carve::csg::CSG::CLASSIFY_EDGE);
+			delete left;
+			delete right;
+
+			left = result;
+		}
+		catch(carve::exception e) {
+			std::cerr << "CSG failed, exception " << e.str() << std::endl;
+
+			delete right;
+		}
+		catch(...) {
+			delete left;
+			delete right;
+
+			throw "Unknown error in Carve library";
+		}
+	}
+
+	return left;
+}
+
+static carve::mesh::MeshSet<3>::aabb_t Carve_computeAABB(carve::mesh::MeshSet<3> *poly,
+                                                         std::vector<carve::mesh::MeshSet<3>::aabb_t> &precomputedAABB)
+{
+	carve::mesh::MeshSet<3>::aabb_t overallAABB;
+	std::vector<carve::mesh::MeshSet<3>::mesh_t*>::iterator it = poly->meshes.begin();
+
+	for(; it!=poly->meshes.end(); it++) {
+		carve::mesh::MeshSet<3>::aabb_t aabb;
+		carve::mesh::MeshSet<3>::mesh_t *mesh = *it;
+
+		aabb = mesh->getAABB();
+		precomputedAABB.push_back(aabb);
+
+		overallAABB.unionAABB(aabb);
+	}
+
+	return overallAABB;
+}
+
+static void Carve_prepareOperands(carve::mesh::MeshSet<3> **left_r, carve::mesh::MeshSet<3> **right_r,
+                                  carve::interpolate::FaceAttr<uint> &oface_num)
+{
+	carve::mesh::MeshSet<3> *left, *right;
+
+	std::vector<carve::mesh::MeshSet<3>::aabb_t> left_precomputedAABB;
+	std::vector<carve::mesh::MeshSet<3>::aabb_t> right_precomputedAABB;
+
+	carve::mesh::MeshSet<3>::aabb_t leftAABB = Carve_computeAABB(*left_r, left_precomputedAABB);
+	carve::mesh::MeshSet<3>::aabb_t rightAABB = Carve_computeAABB(*right_r, right_precomputedAABB);
+
+	left = Carve_unionIntersectingMeshes(*left_r, left_precomputedAABB, rightAABB, oface_num);
+	right = Carve_unionIntersectingMeshes(*right_r, right_precomputedAABB, leftAABB, oface_num);
+
+	if(left != *left_r)
+		delete *left_r;
+
+	if(right != *right_r)
+		delete *right_r;
+
+	*left_r = left;
+	*right_r = right;
+}
+
 static carve::mesh::MeshSet<3> *Carve_addMesh(CSG_FaceIteratorDescriptor& face_it,
                                               CSG_VertexIteratorDescriptor& vertex_it,
                                               carve::interpolate::FaceAttr<uint> &oface_num,
-                                              uint &num_origfaces )
+                                              uint &num_origfaces)
 {
 	CSG_IVertex vertex;
 	std::vector<carve::geom3d::Vector> vertices;
@@ -360,6 +511,8 @@
 	left = Carve_addMesh(obAFaces, obAVertices, oface_num, num_origfaces );
 	right = Carve_addMesh(obBFaces, obBVertices, oface_num, num_origfaces );
 
+	Carve_prepareOperands(&left, &right, oface_num);
+
 	min.x = max.x = left->vertex_storage[0].v.x;
 	min.y = max.y = left->vertex_storage[0].v.y;
 	min.z = max.z = left->vertex_storage[0].v.z;
@@ -390,10 +543,26 @@
 	csg.hooks.registerHook(new carve::csg::CarveTriangulator, carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT);
 
 	oface_num.installHooks(csg);
-	output = csg.compute( left, right, op, NULL, carve::csg::CSG::CLASSIFY_EDGE);
+
+	try {
+		output = csg.compute( left, right, op, NULL, carve::csg::CSG::CLASSIFY_EDGE);
+	}
+	catch(carve::exception e) {
+		std::cerr << "CSG failed, exception " << e.str() << std::endl;
+	}
+	catch(...) {
+		delete left;
+		delete right;
+
+		throw "Unknown error in Carve library";
+	}
+
 	delete left;
 	delete right;
 
+	if(!output)
+		return BOP_ERROR;
+
 	output->transform(rev_r);
 
 	*outputMesh = Carve_exportMesh( output, oface_num, num_origfaces);

Modified: trunk/blender/source/blender/modifiers/intern/MOD_boolean_util.c
===================================================================
--- trunk/blender/source/blender/modifiers/intern/MOD_boolean_util.c	2012-01-23 17:17:08 UTC (rev 43641)
+++ trunk/blender/source/blender/modifiers/intern/MOD_boolean_util.c	2012-01-23 17:43:41 UTC (rev 43642)
@@ -522,7 +522,7 @@
 			CSG_FreeFaceDescriptor(&fd_o);
 		}
 		else
-			printf("Unknown internal error in boolean");
+			printf("Unknown internal error in boolean\n");
 
 		CSG_FreeBooleanOperation(bool_op);
 



More information about the Bf-blender-cvs mailing list