Carve booleans library integration

==================================

Merging Carve library integration project into the trunk.

This commit switches Boolean modifier to another library which handles
mesh boolean operations in much stable and faster way, resolving old
well-known limitations of intern boolop library.

Carve is integrating as alternative interface for boolop library and
which makes it totally transparent for blender sources to switch between
old-fashioned boolop and new Carve backends.

Detailed changes in this commit:

- Integrated needed subset of Carve library sources into extern/
  Added script for re-bundling it (currently works only if repo
  was cloned by git-svn).
- Added BOP_CarveInterface for boolop library which can be used by
  Boolean modifier.
- Carve backend is enabled by default, can be disabled by WITH_BF_CARVE
  SCons option and WITH_CARVE CMake option.
- If Boost library is found in build environment it'll be used for
  unordered collections. If Boost isn't found, it'll fallback to TR1
  implementation for GCC compilers. Boost is obligatory if MSVC is used.

Tested on Linux 64bit and Windows 7 64bit.

NOTE: behavior of flat objects was changed. E.g. Plane-Sphere now gives
      plane with circle hole, not plane with semisphere. Don't think
      it's really issue because it's not actually defined behavior in
      such situations and both of ways might be useful. Since it's
      only known "regression" think it's OK to deal with it.

Details are there http://wiki.blender.org/index.php/User:Nazg-gul/CarveBooleans

Special thanks to:

- Ken Hughes: author of original carve integration patch.
- Campbell Barton: help in project development, review tests.
- Tobias Sargeant: author of Carve library, help in resolving some
                   merge stoppers, bug fixing.

18 files changed, 522 insertions, 85 deletions

diff --git a/intern/boolop/CMakeLists.txt b/intern/boolop/CMakeLists.txt
index 29ea1a28c5f..d0870c8da9c 100644
--- a/intern/boolop/CMakeLists.txt
+++ b/intern/boolop/CMakeLists.txt
@@ -39,43 +39,71 @@ set(INC_SYS
 
 )
 
-set(SRC
-	intern/BOP_BBox.cpp
-	intern/BOP_BSPNode.cpp
-	intern/BOP_BSPTree.cpp
-	intern/BOP_Edge.cpp
-	intern/BOP_Face.cpp
-	intern/BOP_Face2Face.cpp
-	intern/BOP_Interface.cpp
-	intern/BOP_MathUtils.cpp
-	intern/BOP_Merge.cpp
-	intern/BOP_Merge2.cpp
-	intern/BOP_Mesh.cpp
-	intern/BOP_Segment.cpp
-	intern/BOP_Splitter.cpp
-	intern/BOP_Tag.cpp
-	intern/BOP_Triangulator.cpp
-	intern/BOP_Vertex.cpp
+if(NOT WITH_CARVE)
+	set(SRC
+		intern/BOP_BBox.cpp
+		intern/BOP_BSPNode.cpp
+		intern/BOP_BSPTree.cpp
+		intern/BOP_Edge.cpp
+		intern/BOP_Face.cpp
+		intern/BOP_Face2Face.cpp
+		intern/BOP_Interface.cpp
+		intern/BOP_MathUtils.cpp
+		intern/BOP_Merge.cpp
+		intern/BOP_Merge2.cpp
+		intern/BOP_Mesh.cpp
+		intern/BOP_Segment.cpp
+		intern/BOP_Splitter.cpp
+		intern/BOP_Tag.cpp
+		intern/BOP_Triangulator.cpp
+		intern/BOP_Vertex.cpp
 
-	extern/BOP_Interface.h
-	intern/BOP_BBox.h
-	intern/BOP_BSPNode.h
-	intern/BOP_BSPTree.h
-	intern/BOP_Chrono.h
-	intern/BOP_Edge.h
-	intern/BOP_Face.h
-	intern/BOP_Face2Face.h
-	intern/BOP_Indexs.h
-	intern/BOP_MathUtils.h
-	intern/BOP_Merge.h
-	intern/BOP_Merge2.h
-	intern/BOP_Mesh.h
-	intern/BOP_Misc.h
-	intern/BOP_Segment.h
-	intern/BOP_Splitter.h
-	intern/BOP_Tag.h
-	intern/BOP_Triangulator.h
-	intern/BOP_Vertex.h
-)
+		extern/BOP_Interface.h
+		intern/BOP_BBox.h
+		intern/BOP_BSPNode.h
+		intern/BOP_BSPTree.h
+		intern/BOP_Chrono.h
+		intern/BOP_Edge.h
+		intern/BOP_Face.h
+		intern/BOP_Face2Face.h
+		intern/BOP_Indexs.h
+		intern/BOP_MathUtils.h
+		intern/BOP_Merge.h
+		intern/BOP_Merge2.h
+		intern/BOP_Mesh.h
+		intern/BOP_Misc.h
+		intern/BOP_Segment.h
+		intern/BOP_Splitter.h
+		intern/BOP_Tag.h
+		intern/BOP_Triangulator.h
+		intern/BOP_Vertex.h
+	)
+else()
+	set(SRC
+		intern/BOP_CarveInterface.cpp
+		extern/BOP_Interface.h
+	)
+
+	list(APPEND INC
+		../../extern/carve/include
+	)
+
+	if(WITH_BOOST)
+		if(NOT MSVC)
+			# Boost is setting as preferred collections library in the Carve code when using MSVC compiler
+			add_definitions(
+				-DHAVE_BOOST_UNORDERED_COLLECTIONS
+			)
+		endif()
+
+		add_definitions(
+			-DCARVE_SYSTEM_BOOST
+		)
+
+		list(APPEND INC
+			${BOOST_INCLUDE_DIR}
+		)
+	endif()
+endif()
 
 blender_add_lib(bf_intern_bop "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/intern/boolop/SConscript b/intern/boolop/SConscript
index 5cf32862f96..4012b0fca39 100644
--- a/intern/boolop/SConscript
+++ b/intern/boolop/SConscript
@@ -1,14 +1,29 @@
 #!/usr/bin/python
 Import ('env')
 
-sources = env.Glob('intern/*.cpp')
-
 incs = '. intern extern ../moto/include ../container ../memutil'
 incs += ' ../../source/blender/makesdna ../../intern/guardedalloc'
 incs += ' ../../source/blender/blenlib'
 
+defs = []
+
+if not env['WITH_BF_CARVE']:
+    sources = env.Glob('intern/*.cpp')
+    sources.remove('intern' + os.sep + 'BOP_CarveInterface.cpp')
+else:
+    sources = env.Glob('intern/BOP_CarveInterface.cpp')
+    incs += ' ../../extern/carve/include'
+
+    if env['WITH_BF_BOOST']:
+        if env['OURPLATFORM'] not in ('win32-vc', 'win64-vc'):
+            # Boost is setting as preferred collections library in the Carve code when using MSVC compiler
+            defs.append('HAVE_BOOST_UNORDERED_COLLECTIONS')
+
+        defs.append('CARVE_SYSTEM_BOOST')
+        incs +=  ' ' + env['BF_BOOST_INC']
+
 if (env['OURPLATFORM'] == 'win32-mingw'):
     env.BlenderLib ('bf_intern_bop', sources, Split(incs) , [], libtype='intern', priority = 5 )
 else:
-    env.BlenderLib ('bf_intern_bop', sources, Split(incs) , [], libtype='intern', priority = 5 )
+    env.BlenderLib ('bf_intern_bop', sources, Split(incs) , defs, libtype='intern', priority = 5 )
 
diff --git a/intern/boolop/intern/BOP_BSPNode.cpp b/intern/boolop/intern/BOP_BSPNode.cpp
index 178961510d5..7d9071b3132 100644
--- a/intern/boolop/intern/BOP_BSPNode.cpp
+++ b/intern/boolop/intern/BOP_BSPNode.cpp
@@ -35,7 +35,6 @@
 #include "MT_assert.h"
 #include "MT_MinMax.h"
 #include <iostream>
-using namespace std;
 
 /**
  * Constructs a new BSP node.
@@ -707,13 +706,13 @@ int BOP_BSPNode::splitTriangle(MT_Point3* res,
  */
 void BOP_BSPNode::print(unsigned int deep)
 {
-	cout << "(" << deep << "," << m_plane << ")," << endl;
+	std::cout << "(" << deep << "," << m_plane << ")," << std::endl;
 	if (m_inChild != NULL)
 		m_inChild->print(deep + 1);
 	else
-		cout << "(" << deep+1 << ",None)," << endl;
+		std::cout << "(" << deep+1 << ",None)," << std::endl;
 	if (m_outChild != NULL)
 		m_outChild->print(deep + 1);
 	else
-		cout << "(" << deep+1 << ",None)," << endl;
+		std::cout << "(" << deep+1 << ",None)," << std::endl;
 }
diff --git a/intern/boolop/intern/BOP_BSPNode.h b/intern/boolop/intern/BOP_BSPNode.h
index 1a52f385ce7..9f924407b62 100644
--- a/intern/boolop/intern/BOP_BSPNode.h
+++ b/intern/boolop/intern/BOP_BSPNode.h
@@ -37,8 +37,8 @@
 #include "BOP_Tag.h"
 #include "BOP_Face.h"
 
-typedef vector<MT_Point3> BOP_BSPPoints;
-typedef vector<MT_Point3>::const_iterator BOP_IT_BSPPoints;
+typedef std::vector<MT_Point3> BOP_BSPPoints;
+typedef std::vector<MT_Point3>::const_iterator BOP_IT_BSPPoints;
 
 class BOP_BSPNode
 {
diff --git a/intern/boolop/intern/BOP_BSPTree.cpp b/intern/boolop/intern/BOP_BSPTree.cpp
index 0a8b3cc98fc..7a8ed417be4 100644
--- a/intern/boolop/intern/BOP_BSPTree.cpp
+++ b/intern/boolop/intern/BOP_BSPTree.cpp
@@ -33,7 +33,6 @@
 #include "BOP_BSPTree.h"
 #include <vector>
 #include <iostream>
-using namespace std;
 
 /**
  * Constructs a new BSP tree.
diff --git a/intern/boolop/intern/BOP_CarveInterface.cpp b/intern/boolop/intern/BOP_CarveInterface.cpp
new file mode 100644
index 00000000000..4db4fdd819d
--- /dev/null
+++ b/intern/boolop/intern/BOP_CarveInterface.cpp
@@ -0,0 +1,403 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file boolop/intern/BOP_CarveInterface.cpp
+ *  \ingroup boolopintern
+ */
+
+#include "../extern/BOP_Interface.h"
+#include "../../bsp/intern/BSP_CSGMesh_CFIterator.h"
+
+#include <carve/csg_triangulator.hpp>
+#include <carve/interpolator.hpp>
+#include <carve/rescale.hpp>
+
+typedef unsigned int uint;
+
+#define MAX(x,y) ((x)>(y)?(x):(y))
+#define MIN(x,y) ((x)<(y)?(x):(y))
+
+static int isFacePlanar(CSG_IFace &face, std::vector<carve::geom3d::Vector> &vertices)
+{
+	carve::geom3d::Vector v1, v2, v3, cross;
+
+	if (face.vertex_number == 4) {
+		v1 = vertices[face.vertex_index[1]] - vertices[face.vertex_index[0]];
+		v2 = vertices[face.vertex_index[3]] - vertices[face.vertex_index[0]];
+		v3 = vertices[face.vertex_index[2]] - vertices[face.vertex_index[0]];
+
+		cross = carve::geom::cross(v1, v2);
+
+		float production = carve::geom::dot(cross, v3);
+		float magnitude = 1e-6 * cross.length();
+
+		return fabs(production) < magnitude;
+	}
+
+	return 1;
+}
+
+static carve::mesh::MeshSet<3> *Carve_addMesh(CSG_FaceIteratorDescriptor& face_it,
+                                              CSG_VertexIteratorDescriptor& vertex_it,
+                                              carve::interpolate::FaceAttr<uint> &oface_num,
+                                              uint &num_origfaces )
+{
+	CSG_IVertex vertex;
+	std::vector<carve::geom3d::Vector> vertices;
+
+	while (!vertex_it.Done(vertex_it.it)) {
+		vertex_it.Fill(vertex_it.it,&vertex);
+		vertices.push_back(carve::geom::VECTOR(vertex.position[0],
+		                                       vertex.position[1],
+		                                       vertex.position[2]));
+		vertex_it.Step(vertex_it.it);
+	}
+
+	CSG_IFace face;
+	std::vector<int> f;
+	int numfaces = 0;
+
+	// now for the polygons.
+	// we may need to decalare some memory for user defined face properties.
+
+	std::vector<int> forig;
+	while (!face_it.Done(face_it.it)) {
+		face_it.Fill(face_it.it,&face);
+
+		if (isFacePlanar(face, vertices)) {
+			f.push_back(face.vertex_number);
+			f.push_back(face.vertex_index[0]);
+			f.push_back(face.vertex_index[1]);
+			f.push_back(face.vertex_index[2]);
+
+			if (face.vertex_number == 4)
+				f.push_back(face.vertex_index[3]);
+
+			forig.push_back(face.orig_face);
+			++numfaces;
+			face_it.Step(face_it.it);
+			++num_origfaces;
+		}
+		else {
+			f.push_back(3);
+			f.push_back(face.vertex_index[0]);
+			f.push_back(face.vertex_index[1]);
+			f.push_back(face.vertex_index[2]);
+
+			forig.push_back(face.orig_face);
+			++numfaces;
+
+			if (face.vertex_number == 4) {
+				f.push_back(3);
+				f.push_back(face.vertex_index[0]);
+				f.push_back(face.vertex_index[2]);
+				f.push_back(face.vertex_index[3]);
+
+				forig.push_back(face.orig_face);
+				++numfaces;
+			}
+
+			face_it.Step(face_it.it);
+			++num_origfaces;
+		}
+	}
+
+	carve::mesh::MeshSet<3> *poly = new carve::mesh::MeshSet<3> (vertices, numfaces, f);
+
+	uint i;
+	carve::mesh::MeshSet<3>::face_iter face_iter = poly->faceBegin();
+	for (i = 0; face_iter != poly->faceEnd(); ++face_iter, ++i) {
+		carve::mesh::MeshSet<3>::face_t *face = *face_iter;
+		oface_num.setAttribute(face, forig[i]);
+	}
+
+	return poly;
+}
+
+// check whether two faces share an edge, and if so merge them
+static uint quadMerge(std::map<carve::mesh::MeshSet<3>::vertex_t*, uint> *vertexToIndex_map,
+                      carve::mesh::MeshSet<3>::face_t *f1, carve::mesh::MeshSet<3>::face_t *f2,
+                      uint v, uint quad[4])
+{
+	uint current, n1, p1, n2, p2;
+	uint v1[3];
+	uint v2[3];
+
+	// get the vertex indices for each face
+	v1[0] = vertexToIndex_map->find(f1->edge->vert)->second;
+	v1[1] = vertexToIndex_map->find(f1->edge->next->vert)->second;
+	v1[2] = vertexToIndex_map->find(f1->edge->next->next->vert)->second;
+
+	v2[0] = vertexToIndex_map->find(f2->edge->vert)->second;
+	v2[1] = vertexToIndex_map->find(f2->edge->next->vert)->second;
+	v2[2] = vertexToIndex_map->find(f2->edge->next->next->vert)->second;
+
+	// locate the current vertex we're examining, and find the next and
+	// previous vertices based on the face windings
+	if (v1[0] == v) {current = 0; p1 = 2; n1 = 1;}
+	else if (v1[1] == v) {current = 1; p1 = 0; n1 = 2;}
+	else {current = 2; p1 = 1; n1 = 0;}
+
+	if (v2[0] == v) {p2 = 2; n2 = 1;}
+	else if (v2[1] == v) {p2 = 0; n2 = 2;}
+	else {p2 = 1; n2 = 0;}
+
+	// if we find a match, place indices into quad in proper order and return
+	// success code
+	if (v1[p1] == v2[n2]) {
+		quad[0] = v1[current];
+		quad[1] = v1[n1];
+		quad[2] = v1[p1];
+		quad[3] = v2[p2];
+
+		return 1;
+	}
+	else if (v1[n1] == v2[p2]) {
+		quad[0] = v1[current];
+		quad[1] = v2[n2];
+		quad[2] = v1[n1];
+		quad[3] = v1[p1];
+
+		return 1;
+	}
+
+	return 0;
+}
+
+static BSP_CSGMesh* Carve_exportMesh(carve::mesh::MeshSet<3>* &poly, carve::interpolate::FaceAttr<uint> &oface_num,
+                                     uint num_origfaces)
+{
+	uint i;
+	BSP_CSGMesh* outputMesh = BSP_CSGMesh::New();
+
+	if (outputMesh == NULL)
+		return NULL;
+
+	std::vector<BSP_MVertex>* vertices = new std::vector<BSP_MVertex>;
+
+	outputMesh->SetVertices(vertices);
+
+	std::map<carve::mesh::MeshSet<3>::vertex_t*, uint> vertexToIndex_map;
+	std::vector<carve::mesh::MeshSet<3>::vertex_t>::iterator it = poly->vertex_storage.begin();
+	for (i = 0; it != poly->vertex_storage.end(); ++i, ++it) {
+		carve::mesh::MeshSet<3>::vertex_t *vertex = &(*it);
+		vertexToIndex_map[vertex] = i;
+	}
+
+	for (i = 0; i < poly->vertex_storage.size(); ++i ) {
+		BSP_MVertex outVtx(MT_Point3 (poly->vertex_storage[i].v[0],
+		                              poly->vertex_storage[i].v[1],
+		                              poly->vertex_storage[i].v[2]));
+		outVtx.m_edges.clear();
+		outputMesh->VertexSet().push_back(outVtx);
+	}
+
+	// build vectors of faces for each original face and each vertex 
+	std::vector< std::vector<uint> > vi(poly->vertex_storage.size());
+	std::vector< std::vector<uint> > ofaces(num_origfaces);
+	carve::mesh::MeshSet<3>::face_iter face_iter = poly->faceBegin();
+	for (i = 0; face_iter != poly->faceEnd(); ++face_iter, ++i) {
+		carve::mesh::MeshSet<3>::face_t *f = *face_iter;
+		ofaces[oface_num.getAttribute(f)].push_back(i);
+		carve::mesh::MeshSet<3>::face_t::edge_iter_t edge_iter = f->begin();
+		for (; edge_iter != f->end(); ++edge_iter) {
+			int index = vertexToIndex_map[edge_iter->vert];
+			vi[index].push_back(i);
+		}
+	}
+
+	uint quadverts[4] = {0, 0, 0, 0};
+	// go over each set of faces which belong to an original face
+	std::vector< std::vector<uint> >::const_iterator fii;
+	uint orig = 0;
+	for (fii=ofaces.begin(); fii!=ofaces.end(); ++fii, ++orig) {
+		std::vector<uint> fl = *fii;
+		// go over a single set from an original face
+		while (fl.size() > 0) {
+			// remove one new face
+			uint findex = fl.back();
+			fl.pop_back();
+
+			carve::mesh::MeshSet<3>::face_t *f = *(poly->faceBegin() + findex);
+
+			// add all information except vertices to the output mesh
+			outputMesh->FaceSet().push_back(BSP_MFace());
+			BSP_MFace& outFace = outputMesh->FaceSet().back();
+			outFace.m_verts.clear();
+			outFace.m_plane.setValue(f->plane.N.v);
+			outFace.m_orig_face = orig;
+
+			// for each vertex of this face, check other faces containing
+			// that vertex to see if there is a neighbor also belonging to
+			// the original face
+			uint result = 0;
+
+			carve::mesh::MeshSet<3>::face_t::edge_iter_t edge_iter = f->begin();
+			for (; edge_iter != f->end(); ++edge_iter) {
+				int v = vertexToIndex_map[edge_iter->vert];
+				for (uint pos2=0; !result && pos2 < vi[v].size();pos2++) {
+
+					// if we find the current face, ignore it
+					uint otherf = vi[v][pos2];
+					if (findex == otherf)
+						continue;
+
+					carve::mesh::MeshSet<3>::face_t *f2 = *(poly->faceBegin() + otherf);
+
+					// if other face doesn't have the same original face,
+					// ignore it also
+					uint other_orig = oface_num.getAttribute(f2);
+					if (orig != other_orig)
+						continue;
+
+					// if, for some reason, we don't find the other face in
+					// the current set of faces, ignore it
+					uint other_index = 0;
+					while (other_index < fl.size() && fl[other_index] != otherf) ++other_index;
+					if (other_index == fl.size()) continue;
+
+					// see if the faces share an edge
+					result = quadMerge(&vertexToIndex_map, f, f2, v, quadverts);
+					// if faces can be merged, then remove the other face
+					// from the current set
+					if (result) {
+						uint replace = fl.back();
+						fl.pop_back();
+						if(otherf != replace)
+							fl[other_index] = replace;
+					}
+				}
+			}
+
+			// if we merged faces, use the list of common vertices; otherwise
+			// use the faces's vertices
+			if (result) {
+				// make quat using verts stored in result
+				outFace.m_verts.push_back(quadverts[0]);
+				outFace.m_verts.push_back(quadverts[1]);
+				outFace.m_verts.push_back(quadverts[2]);
+				outFace.m_verts.push_back(quadverts[3]);
+			} else {
+				carve::mesh::MeshSet<3>::face_t::edge_iter_t edge_iter = f->begin();
+				for (; edge_iter != f->end(); ++edge_iter) {
+					//int index = ofacevert_num.getAttribute(f, edge_iter.idx());
+					int index = vertexToIndex_map[edge_iter->vert];
+					outFace.m_verts.push_back( index );
+				}
+			}
+		}
+	}
+
+	// Build the mesh edges using topological informtion
+	outputMesh->BuildEdges();
+	
+	return outputMesh;
+}
+
+/**
+ * Performs a generic booleam operation, the entry point for external modules.
+ * @param opType Boolean operation type BOP_INTERSECTION, BOP_UNION, BOP_DIFFERENCE
+ * @param outputMesh Output mesh, the final result (the object C)
+ * @param obAFaces Object A faces list
+ * @param obAVertices Object A vertices list
+ * @param obBFaces Object B faces list
+ * @param obBVertices Object B vertices list
+ * @param interpFunc Interpolating function
+ * @return operation state: BOP_OK, BOP_NO_SOLID, BOP_ERROR
+ */
+BoolOpState BOP_performBooleanOperation(BoolOpType                    opType,
+                                        BSP_CSGMesh**                 outputMesh,
+                                        CSG_FaceIteratorDescriptor    obAFaces,
+                                        CSG_VertexIteratorDescriptor  obAVertices,
+                                        CSG_FaceIteratorDescriptor    obBFaces,
+                                        CSG_VertexIteratorDescriptor  obBVertices)
+{
+	carve::csg::CSG::OP op;
+	carve::mesh::MeshSet<3> *left, *right, *output;
+	carve::csg::CSG csg;
+	carve::geom3d::Vector min, max;
+	carve::interpolate::FaceAttr<uint> oface_num;
+	uint num_origfaces = 0;
+
+	switch (opType) {
+		case BOP_UNION:
+			op = carve::csg::CSG::UNION;
+			break;
+		case BOP_INTERSECTION:
+			op = carve::csg::CSG::INTERSECTION;
+			break;
+		case BOP_DIFFERENCE:
+			op = carve::csg::CSG::A_MINUS_B;
+			break;
+		default:
+			return BOP_ERROR;
+	}
+
+	left = Carve_addMesh(obAFaces, obAVertices, oface_num, num_origfaces );
+	right = Carve_addMesh(obBFaces, obBVertices, oface_num, num_origfaces );
+
+	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;
+	for (uint i = 1; i < left->vertex_storage.size(); ++i) {
+		min.x = MIN(min.x,left->vertex_storage[i].v.x);
+		min.y = MIN(min.y,left->vertex_storage[i].v.y);
+		min.z = MIN(min.z,left->vertex_storage[i].v.z);
+		max.x = MAX(max.x,left->vertex_storage[i].v.x);
+		max.y = MAX(max.y,left->vertex_storage[i].v.y);
+		max.z = MAX(max.z,left->vertex_storage[i].v.z);
+	}
+	for (uint i = 0; i < right->vertex_storage.size(); ++i) {
+		min.x = MIN(min.x,right->vertex_storage[i].v.x);
+		min.y = MIN(min.y,right->vertex_storage[i].v.y);
+		min.z = MIN(min.z,right->vertex_storage[i].v.z);
+		max.x = MAX(max.x,right->vertex_storage[i].v.x);
+		max.y = MAX(max.y,right->vertex_storage[i].v.y);
+		max.z = MAX(max.z,right->vertex_storage[i].v.z);
+	}
+
+	carve::rescale::rescale scaler(min.x, min.y, min.z, max.x, max.y, max.z);
+	carve::rescale::fwd fwd_r(scaler);
+	carve::rescale::rev rev_r(scaler); 
+
+	left->transform(fwd_r);
+	right->transform(fwd_r);
+
+	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);
+	delete left;
+	delete right;
+
+	output->transform(rev_r);
+
+	*outputMesh = Carve_exportMesh( output, oface_num, num_origfaces);
+	delete output;
+
+	return BOP_OK;
+}
diff --git a/intern/boolop/intern/BOP_Edge.cpp b/intern/boolop/intern/BOP_Edge.cpp
index c53dde35d33..fc03dd897d3 100644
--- a/intern/boolop/intern/BOP_Edge.cpp
+++ b/intern/boolop/intern/BOP_Edge.cpp
@@ -105,7 +105,6 @@ bool BOP_Edge::removeFace(BOP_Index i)
 #ifdef BOP_DEBUG
 
 #include <iostream>
-using namespace std;
 
 /**
  * Implements operator <<.
diff --git a/intern/boolop/intern/BOP_Face.h b/intern/boolop/intern/BOP_Face.h
index 7aaee2bd045..6f79b8b17c0 100644
--- a/intern/boolop/intern/BOP_Face.h
+++ b/intern/boolop/intern/BOP_Face.h
@@ -40,12 +40,11 @@
 #include "BOP_Misc.h"
 #include <iostream>
 #include <vector>
-using namespace std;
 
 class BOP_Face;
 
-typedef vector<BOP_Face *> BOP_Faces;
-typedef vector<BOP_Face *>::iterator BOP_IT_Faces;
+typedef std::vector<BOP_Face *> BOP_Faces;
+typedef std::vector<BOP_Face *>::iterator BOP_IT_Faces;
 
 class BOP_Face
 {
diff --git a/intern/boolop/intern/BOP_Indexs.h b/intern/boolop/intern/BOP_Indexs.h
index 74c2025e74a..4e71c66d4a4 100644
--- a/intern/boolop/intern/BOP_Indexs.h
+++ b/intern/boolop/intern/BOP_Indexs.h
@@ -34,10 +34,9 @@
 #define BOP_Indexs_H
 
 #include <vector>
-using namespace std;
 
 typedef unsigned int BOP_Index;
-typedef vector<BOP_Index> BOP_Indexs;
-typedef vector<BOP_Index>::iterator BOP_IT_Indexs;
+typedef std::vector<BOP_Index> BOP_Indexs;
+typedef std::vector<BOP_Index>::iterator BOP_IT_Indexs;
 
 #endif
diff --git a/intern/boolop/intern/BOP_Interface.cpp b/intern/boolop/intern/BOP_Interface.cpp
index f11c4eaffae..b18a4334263 100644
--- a/intern/boolop/intern/BOP_Interface.cpp
+++ b/intern/boolop/intern/BOP_Interface.cpp
@@ -86,7 +86,7 @@ BoolOpState BOP_performBooleanOperation(BoolOpType                    opType,
 										CSG_VertexIteratorDescriptor  obBVertices)
 {
 	#ifdef BOP_DEBUG
-	cout << "BEGIN BOP_performBooleanOperation" << endl;
+	std::cout << "BEGIN BOP_performBooleanOperation" << std::endl;
 	#endif
 
 	// Set invert flags depending on boolean operation type:
@@ -124,7 +124,7 @@ BoolOpState BOP_performBooleanOperation(BoolOpType                    opType,
 	*outputMesh = BOP_exportMesh(&meshC, invertMeshC);
 
 	#ifdef BOP_DEBUG
-	cout << "END BOP_performBooleanOperation" << endl;
+	std::cout << "END BOP_performBooleanOperation" << std::endl;
 	#endif
 	
 	return result;
@@ -151,7 +151,7 @@ BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
 	float t = 0.0f;
 	float c = 0.0f;
 	chrono.start();  
-	cout << "---" << endl;
+	std::cout << "---" << std::endl;
 	#endif
 
 	// Create BSPs trees for mesh A & B
@@ -163,7 +163,7 @@ BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
 
 	#ifdef BOP_DEBUG
 	c = chrono.stamp(); t += c;
-	cout << "Create BSP     " << c << endl;	
+	std::cout << "Create BSP     " << c << std::endl;	
 	#endif
 
 	unsigned int numVertices = meshC->getNumVertexs();
@@ -179,7 +179,7 @@ BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
 	
 	#ifdef BOP_DEBUG
 	c = chrono.stamp(); t += c;
-	cout << "mesh Filter    " << c << endl;	
+	std::cout << "mesh Filter    " << c << std::endl;	
 	#endif
 
 	// Face 2 Face
@@ -187,7 +187,7 @@ BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
 
 	#ifdef BOP_DEBUG
 	c = chrono.stamp(); t += c;
-	cout << "Face2Face      " << c << endl;
+	std::cout << "Face2Face      " << c << std::endl;
 	#endif
 
 	// BSP classification
@@ -196,7 +196,7 @@ BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
 	
 	#ifdef BOP_DEBUG
 	c = chrono.stamp(); t += c;
-	cout << "Classification " << c << endl;
+	std::cout << "Classification " << c << std::endl;
 	#endif
 	
 	// Process overlapped faces
@@ -204,7 +204,7 @@ BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
 	
 	#ifdef BOP_DEBUG
 	c = chrono.stamp(); t += c;
-	cout << "Remove overlap " << c << endl;
+	std::cout << "Remove overlap " << c << std::endl;
 	#endif
 
 	// Sew two meshes
@@ -212,7 +212,7 @@ BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
 
 	#ifdef BOP_DEBUG
 	c = chrono.stamp(); t += c;
-	cout << "Sew            " << c << endl;
+	std::cout << "Sew            " << c << std::endl;
 	#endif
 
 	// Merge faces
@@ -229,13 +229,13 @@ BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
 	static int state = -1;
 	if (G.rt == 100) {
 		if( state != 1 ) {
-			cout << "Boolean code using old merge technique." << endl;
+			std::cout << "Boolean code using old merge technique." << std::endl;
 			state = 1;
 		}
 		BOP_Merge::getInstance().mergeFaces(meshC,numVertices);
 	} else {
 		if( state != 0 ) {
-			cout << "Boolean code using new merge technique." << endl;
+			std::cout << "Boolean code using new merge technique." << std::endl;
 			state = 0;
 		}
 		BOP_Merge2::getInstance().mergeFaces(meshC,numVertices);
@@ -245,8 +245,8 @@ BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
 
 	#ifdef BOP_DEBUG
 	c = chrono.stamp(); t += c;
-	cout << "Merge faces    " << c << endl;
-	cout << "Total          " << t << endl;
+	std::cout << "Merge faces    " << c << std::endl;
+	std::cout << "Total          " << t << std::endl;
 	// Test integrity
 	meshC->testMesh();
 	#endif
@@ -460,7 +460,7 @@ BSP_CSGMesh* BOP_newEmptyMesh()
 	BSP_CSGMesh* mesh = BSP_CSGMesh::New();
 	if (mesh == NULL) return mesh;
 
-	vector<BSP_MVertex>* vertices = new vector<BSP_MVertex>;
+	std::vector<BSP_MVertex>* vertices = new std::vector<BSP_MVertex>;
 	
 	mesh->SetVertices(vertices);
 
@@ -481,8 +481,8 @@ BSP_CSGMesh* BOP_exportMesh(BOP_Mesh*                  mesh,
 	if (outputMesh == NULL) return NULL;
 
 	// vtx index dictionary, to translate indeces from input to output.
-	map<int,unsigned int> dic;
-	map<int,unsigned int>::iterator itDic;
+	std::map<int,unsigned int> dic;
+	std::map<int,unsigned int>::iterator itDic;
 
 	unsigned int count = 0;
 
diff --git a/intern/boolop/intern/BOP_MathUtils.cpp b/intern/boolop/intern/BOP_MathUtils.cpp
index aa9083d17b6..bcc0cca194e 100644
--- a/intern/boolop/intern/BOP_MathUtils.cpp
+++ b/intern/boolop/intern/BOP_MathUtils.cpp
@@ -34,7 +34,6 @@
  
 #include "BOP_MathUtils.h"
 #include <iostream>
-using namespace std;
 
 /**
  * Compares two scalars with EPSILON accuracy.
diff --git a/intern/boolop/intern/BOP_Merge.h b/intern/boolop/intern/BOP_Merge.h
index 64be7b18cb8..5a24579e7b5 100644
--- a/intern/boolop/intern/BOP_Merge.h
+++ b/intern/boolop/intern/BOP_Merge.h
@@ -41,8 +41,8 @@
 #include "BOP_MathUtils.h"
 #include "MEM_SmartPtr.h"
 
-typedef vector< BOP_Faces > BOP_LFaces;
-typedef vector< BOP_Faces >::iterator BOP_IT_LFaces;
+typedef std::vector< BOP_Faces > BOP_LFaces;
+typedef std::vector< BOP_Faces >::iterator BOP_IT_LFaces;
 
 class BOP_Merge {
 	private:
diff --git a/intern/boolop/intern/BOP_Merge2.h b/intern/boolop/intern/BOP_Merge2.h
index 2b79fd95ce6..78a4caff7d9 100644
--- a/intern/boolop/intern/BOP_Merge2.h
+++ b/intern/boolop/intern/BOP_Merge2.h
@@ -42,8 +42,8 @@
 #include "BOP_MathUtils.h"
 #include "MEM_SmartPtr.h"
 
-typedef vector< BOP_Faces > BOP_LFaces;
-typedef vector< BOP_Faces >::iterator BOP_IT_LFaces;
+typedef std::vector< BOP_Faces > BOP_LFaces;
+typedef std::vector< BOP_Faces >::iterator BOP_IT_LFaces;
 
 class BOP_Merge2 {
 	private:
diff --git a/intern/boolop/intern/BOP_Mesh.h b/intern/boolop/intern/BOP_Mesh.h
index 8550333664f..271e97fe454 100644
--- a/intern/boolop/intern/BOP_Mesh.h
+++ b/intern/boolop/intern/BOP_Mesh.h
@@ -40,10 +40,10 @@
 #include "BOP_Face.h"
 #include "DNA_listBase.h"
 
-typedef vector<BOP_Vertex *> BOP_Vertexs;
-typedef vector<BOP_Edge *> BOP_Edges;
-typedef vector<BOP_Vertex *>::iterator BOP_IT_Vertexs;
-typedef vector<BOP_Edge *>::iterator BOP_IT_Edges;
+typedef std::vector<BOP_Vertex *> BOP_Vertexs;
+typedef std::vector<BOP_Edge *> BOP_Edges;
+typedef std::vector<BOP_Vertex *>::iterator BOP_IT_Vertexs;
+typedef std::vector<BOP_Edge *>::iterator BOP_IT_Edges;
 
 #ifdef HASH
 typedef struct EdgeEntry {
diff --git a/intern/boolop/intern/BOP_Segment.cpp b/intern/boolop/intern/BOP_Segment.cpp
index a9c0d30da1c..79e04380015 100644
--- a/intern/boolop/intern/BOP_Segment.cpp
+++ b/intern/boolop/intern/BOP_Segment.cpp
@@ -242,8 +242,8 @@ unsigned int BOP_Segment::getConfig()
 /**
  * Implements operator <<
  */
-ostream &operator<<(ostream &stream, const BOP_Segment &c)
+std::ostream &operator<<(std::ostream &stream, const BOP_Segment &c)
 {
-	cout << "m_v1: " << c.m_v1 << "(" << c.m_cfg1 << ") m_v2: " << c.m_v2 << "(" << c.m_cfg2 << ")";
+	std::cout << "m_v1: " << c.m_v1 << "(" << c.m_cfg1 << ") m_v2: " << c.m_v2 << "(" << c.m_cfg2 << ")";
 	return stream;
 }
diff --git a/intern/boolop/intern/BOP_Segment.h b/intern/boolop/intern/BOP_Segment.h
index 44ea069dc8c..4a2b4509846 100644
--- a/intern/boolop/intern/BOP_Segment.h
+++ b/intern/boolop/intern/BOP_Segment.h
@@ -35,7 +35,6 @@
 
 #include "BOP_Indexs.h"
 #include <iostream>
-using namespace std;
 
 class BOP_Segment
 {
@@ -69,7 +68,7 @@ public:
 	void sort();
 	unsigned int getConfig();
 
-	friend   ostream &operator<<(ostream &stream, const BOP_Segment &c);
+	friend   std::ostream &operator<<(std::ostream &stream, const BOP_Segment &c);
 };
 
 #endif
diff --git a/intern/boolop/intern/BOP_Splitter.cpp b/intern/boolop/intern/BOP_Splitter.cpp
index 26b111ff552..0839b6af30b 100644
--- a/intern/boolop/intern/BOP_Splitter.cpp
+++ b/intern/boolop/intern/BOP_Splitter.cpp
@@ -34,7 +34,6 @@
 #include "BOP_Tag.h"
 
 #include <iostream>
-using namespace std;
 
 /**
  * Returns the split point resulting from intersect a plane and a mesh face  
diff --git a/intern/boolop/intern/BOP_Triangulator.cpp b/intern/boolop/intern/BOP_Triangulator.cpp
index 8f94eb1f7b7..ca1e3ad2b6b 100644
--- a/intern/boolop/intern/BOP_Triangulator.cpp
+++ b/intern/boolop/intern/BOP_Triangulator.cpp
@@ -32,7 +32,6 @@
  
 #include "BOP_Triangulator.h"
 #include <iostream>
-using namespace std;
 
 void BOP_addFace(BOP_Mesh* mesh, BOP_Faces *faces, BOP_Face* face, BOP_TAG tag);
 void BOP_splitQuad(BOP_Mesh* mesh, MT_Plane3 plane, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4,