Fix T40551: Boolean Modifier distorts UVs

Mapping to original face was never working 100% reliably actually,
now use more robust method for this.

3 files changed, 51 insertions, 46 deletions

diff --git a/extern/carve/carve-capi.cc b/extern/carve/carve-capi.cc
index af9ecad685d..d8c7727605c 100644
--- a/extern/carve/carve-capi.cc
+++ b/extern/carve/carve-capi.cc
@@ -48,8 +48,8 @@ typedef struct CarveMeshDescr {
 	// N-th element of the vector indicates index of an original mesh loop.
 	std::unordered_map<std::pair<int, int>, int> orig_loop_index_map;
 
-	// N-th element of the vector indicates index of an original mesh poly.
-	std::vector<int> orig_poly_index_map;
+	// Mapping from carve face to an original face index in DM.
+	std::unordered_map<const MeshSet<3>::face_t *, int> orig_poly_index_map;
 
 	// The folloving mapping is only filled in for output mesh.
 
@@ -150,7 +150,7 @@ inline int indexOf(const T *element, const std::vector<T> &vector_from)
 void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
                                   int which_mesh,
                                   std::unordered_map<std::pair<int, int>, int> &orig_loop_index_map,
-                                  const std::vector<int> &orig_poly_index_map,
+                                  std::unordered_map<const MeshSet<3>::face_t*, int> &orig_poly_index_map,
                                   OrigVertMapping *orig_vert_mapping,
                                   OrigFaceEdgeMapping *orig_face_edge_mapping,
                                   FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
@@ -177,7 +177,7 @@ void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
 		const MeshSet<3>::face_t *face = *face_iter;
 
 		// Mapping from carve face back to original poly index.
-		int orig_poly_index = orig_poly_index_map[i];
+		int orig_poly_index = orig_poly_index_map[face];
 		orig_face_attr->setAttribute(face, std::make_pair(which_mesh, orig_poly_index));
 
 		for (MeshSet<3>::face_t::const_edge_iter_t edge_iter = face->begin();
@@ -566,14 +566,14 @@ CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
 
 	// Import verices from external mesh to Carve.
 	int num_verts = mesh_importer->getNumVerts(import_data);
-	std::vector<carve::geom3d::Vector> vertices;
-	vertices.reserve(num_verts);
+	std::vector<MeshSet<3>::vertex_t> vertex_storage;
+	vertex_storage.reserve(num_verts);
 	for (int i = 0; i < num_verts; i++) {
 		float position[3];
 		mesh_importer->getVertCoord(import_data, i, position);
-		vertices.push_back(carve::geom::VECTOR(position[0],
-		                                       position[1],
-		                                       position[2]));
+		vertex_storage.push_back(carve::geom::VECTOR(position[0],
+		                                             position[1],
+		                                             position[2]));
 	}
 
 	// Import polys from external mesh to Carve.
@@ -581,14 +581,13 @@ CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
 	int *verts_of_poly_dynamic = NULL;
 	int verts_of_poly_dynamic_size = 0;
 
-	int num_loops = mesh_importer->getNumLoops(import_data);
 	int num_polys = mesh_importer->getNumPolys(import_data);
 	int loop_index = 0;
-	int num_tessellated_polys = 0;
 	std::vector<int> face_indices;
-	face_indices.reserve(num_loops);
-	mesh_descr->orig_poly_index_map.reserve(num_polys);
 	TrianglesStorage triangles_storage;
+	std::vector<MeshSet<3>::face_t *> faces;
+	std::vector<MeshSet<3>::vertex_t *> face_vertices;
+	faces.reserve(num_polys);
 	for (int i = 0; i < num_polys; i++) {
 		int verts_per_poly =
 			mesh_importer->getNumPolyVerts(import_data, i);
@@ -611,32 +610,39 @@ CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
 		mesh_importer->getPolyVerts(import_data, i, verts_of_poly);
 
 		carve::math::Matrix3 axis_matrix;
-		if (!carve_checkPolyPlanarAndGetNormal(vertices,
+		if (!carve_checkPolyPlanarAndGetNormal(vertex_storage,
 		                                       verts_per_poly,
 		                                       verts_of_poly,
 		                                       &axis_matrix)) {
+			face_indices.clear();
 			int num_triangles = carve_triangulatePoly(import_data,
 			                                          mesh_importer,
-			                                          vertices,
+			                                          vertex_storage,
 			                                          verts_per_poly,
 			                                          verts_of_poly,
 			                                          axis_matrix,
 			                                          &face_indices,
 			                                          &triangles_storage);
-
 			for (int j = 0; j < num_triangles; ++j) {
-				mesh_descr->orig_poly_index_map.push_back(i);
+				MeshSet<3>::face_t *face = new MeshSet<3>::face_t(
+					&vertex_storage[face_indices[j * 3]],
+					&vertex_storage[face_indices[j * 3 + 1]],
+					&vertex_storage[face_indices[j * 3 + 2]]);
+				mesh_descr->orig_poly_index_map[face] = i;
+				faces.push_back(face);
 			}
-
-			num_tessellated_polys += num_triangles;
 		}
 		else {
-			face_indices.push_back(verts_per_poly);
+			face_vertices.clear();
+			face_vertices.reserve(verts_per_poly);
 			for (int j = 0; j < verts_per_poly; ++j) {
-				face_indices.push_back(verts_of_poly[j]);
+				face_vertices.push_back(&vertex_storage[verts_of_poly[j]]);
 			}
-			mesh_descr->orig_poly_index_map.push_back(i);
-			num_tessellated_polys++;
+			MeshSet<3>::face_t *face =
+				new MeshSet<3>::face_t(face_vertices.begin(),
+				                       face_vertices.end());
+			mesh_descr->orig_poly_index_map[face] = i;
+			faces.push_back(face);
 		}
 
 		for (int j = 0; j < verts_per_poly; ++j) {
@@ -650,9 +656,9 @@ CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
 		delete [] verts_of_poly_dynamic;
 	}
 
-	mesh_descr->poly = new MeshSet<3> (vertices,
-	                                   num_tessellated_polys,
-	                                   face_indices);
+	std::vector<MeshSet<3>::mesh_t *> meshes;
+	MeshSet<3>::mesh_t::create(faces.begin(), faces.end(), meshes, carve::mesh::MeshOptions());
+	mesh_descr->poly = new MeshSet<3> (vertex_storage, meshes);
 
 	return mesh_descr;
 
diff --git a/extern/carve/carve-util.cc b/extern/carve/carve-util.cc
index d02b786fd2a..1106fa16a21 100644
--- a/extern/carve/carve-util.cc
+++ b/extern/carve/carve-util.cc
@@ -498,7 +498,7 @@ static inline void add_newell_cross_v3_v3v3(const Vector &v_prev,
 }
 
 // Axis matrix is being set for non-flat ngons only.
-bool carve_checkPolyPlanarAndGetNormal(const std::vector<Vector> &vertices,
+bool carve_checkPolyPlanarAndGetNormal(const std::vector<MeshSet<3>::vertex_t> &vertex_storage,
                                        const int verts_per_poly,
                                        const int *verts_of_poly,
                                        Matrix3 *axis_matrix_r)
@@ -510,10 +510,10 @@ bool carve_checkPolyPlanarAndGetNormal(const std::vector<Vector> &vertices,
 	else if (verts_per_poly == 4) {
 		// Presumably faster than using generig n-gon check for quads.
 
-		const Vector &v1 = vertices[verts_of_poly[0]],
-		             &v2 = vertices[verts_of_poly[1]],
-		             &v3 = vertices[verts_of_poly[2]],
-		             &v4 = vertices[verts_of_poly[3]];
+		const Vector &v1 = vertex_storage[verts_of_poly[0]].v,
+		             &v2 = vertex_storage[verts_of_poly[1]].v,
+		             &v3 = vertex_storage[verts_of_poly[2]].v,
+		             &v4 = vertex_storage[verts_of_poly[3]].v;
 
 		Vector vec1, vec2, vec3, cross;
 
@@ -532,14 +532,14 @@ bool carve_checkPolyPlanarAndGetNormal(const std::vector<Vector> &vertices,
 		return fabs(production) < magnitude;
 	}
 	else {
-		const Vector *vert_prev = &vertices[verts_of_poly[verts_per_poly - 1]];
-		const Vector *vert_curr = &vertices[verts_of_poly[0]];
+		const Vector *vert_prev = &vertex_storage[verts_of_poly[verts_per_poly - 1]].v;
+		const Vector *vert_curr = &vertex_storage[verts_of_poly[0]].v;
 
 		Vector normal = carve::geom::VECTOR(0.0, 0.0, 0.0);
 		for (int i = 0; i < verts_per_poly; i++) {
 			add_newell_cross_v3_v3v3(*vert_prev, *vert_curr, &normal);
 			vert_prev = vert_curr;
-			vert_curr = &vertices[verts_of_poly[(i + 1) % verts_per_poly]];
+			vert_curr = &vertex_storage[verts_of_poly[(i + 1) % verts_per_poly]].v;
 		}
 
 		if (normal.length2() < FLT_EPSILON) {
@@ -552,11 +552,11 @@ bool carve_checkPolyPlanarAndGetNormal(const std::vector<Vector> &vertices,
 			normal.normalize();
 			axis_dominant_v3_to_m3__bli(axis_matrix_r, normal);
 
-			Vector first_projected = *axis_matrix_r * vertices[verts_of_poly[0]];
+			Vector first_projected = *axis_matrix_r * vertex_storage[verts_of_poly[0]].v;
 			double min_z = first_projected[2], max_z = first_projected[2];
 
 			for (int i = 1; i < verts_per_poly; i++) {
-				const Vector &vertex = vertices[verts_of_poly[i]];
+				const Vector &vertex = vertex_storage[verts_of_poly[i]].v;
 				Vector projected = *axis_matrix_r * vertex;
 				if (projected[2] < min_z) {
 					min_z = projected[2];
@@ -579,7 +579,7 @@ bool carve_checkPolyPlanarAndGetNormal(const std::vector<Vector> &vertices,
 
 namespace {
 
-int triangulateNGon_carveTriangulator(const std::vector<Vector> &vertices,
+int triangulateNGon_carveTriangulator(const std::vector<MeshSet<3>::vertex_t> &vertex_storage,
                                       const int verts_per_poly,
                                       const int *verts_of_poly,
                                       const Matrix3 &axis_matrix,
@@ -590,7 +590,7 @@ int triangulateNGon_carveTriangulator(const std::vector<Vector> &vertices,
 	std::vector<carve::geom::vector<2> > poly_2d;
 	poly_2d.reserve(verts_per_poly);
 	for (int i = 0; i < verts_per_poly; ++i) {
-		projected = axis_matrix * vertices[verts_of_poly[i]];
+		projected = axis_matrix * vertex_storage[verts_of_poly[i]].v;
 		poly_2d.push_back(carve::geom::VECTOR(projected[0], projected[1]));
 	}
 
@@ -602,7 +602,7 @@ int triangulateNGon_carveTriangulator(const std::vector<Vector> &vertices,
 
 int triangulateNGon_importerTriangulator(struct ImportMeshData *import_data,
                                          CarveMeshImporter *mesh_importer,
-                                         const std::vector<Vector> &vertices,
+                                         const std::vector<MeshSet<3>::vertex_t> &vertex_storage,
                                          const int verts_per_poly,
                                          const int *verts_of_poly,
                                          const Matrix3 &axis_matrix,
@@ -615,7 +615,7 @@ int triangulateNGon_importerTriangulator(struct ImportMeshData *import_data,
 	Vector2D *poly_2d = new Vector2D[verts_per_poly];
 	Vector projected;
 	for (int i = 0; i < verts_per_poly; ++i) {
-		projected = axis_matrix * vertices[verts_of_poly[i]];
+		projected = axis_matrix * vertex_storage[verts_of_poly[i]].v;
 		poly_2d[i][0] = projected[0];
 		poly_2d[i][1] = projected[1];
 	}
@@ -663,7 +663,6 @@ bool pushTriangle(int v1, int v2, int v3,
 	assert(triangle.b < triangle.c);
 
 	if (triangles_storage->find(triangle) == triangles_storage->end()) {
-		face_indices->push_back(3);
 		face_indices->push_back(v1);
 		face_indices->push_back(v2);
 		face_indices->push_back(v3);
@@ -680,7 +679,7 @@ bool pushTriangle(int v1, int v2, int v3,
 
 int carve_triangulatePoly(struct ImportMeshData *import_data,
                           CarveMeshImporter *mesh_importer,
-                          const std::vector<Vector> &vertices,
+                          const std::vector<MeshSet<3>::vertex_t> &vertex_storage,
                           const int verts_per_poly,
                           const int *verts_of_poly,
                           const Matrix3 &axis_matrix,
@@ -725,14 +724,14 @@ int carve_triangulatePoly(struct ImportMeshData *import_data,
 		if (mesh_importer->triangulate2DPoly) {
 			triangulateNGon_importerTriangulator(import_data,
 			                                     mesh_importer,
-			                                     vertices,
+			                                     vertex_storage,
 			                                     verts_per_poly,
 			                                     verts_of_poly,
 			                                     axis_matrix,
 			                                     &triangles);
 		}
 		else {
-			triangulateNGon_carveTriangulator(vertices,
+			triangulateNGon_carveTriangulator(vertex_storage,
 			                                  verts_per_poly,
 			                                  verts_of_poly,
 			                                  axis_matrix,
diff --git a/extern/carve/carve-util.h b/extern/carve/carve-util.h
index f650810e9e3..0b509aa3cab 100644
--- a/extern/carve/carve-util.h
+++ b/extern/carve/carve-util.h
@@ -74,14 +74,14 @@ bool carve_unionIntersections(carve::csg::CSG *csg,
                               carve::mesh::MeshSet<3> **left_r,
                               carve::mesh::MeshSet<3> **right_r);
 
-bool carve_checkPolyPlanarAndGetNormal(const std::vector<carve::geom3d::Vector> &vertices,
+bool carve_checkPolyPlanarAndGetNormal(const std::vector<carve::mesh::MeshSet<3>::vertex_t> &vertex_storage,
                                        const int verts_per_poly,
                                        const int *verts_of_poly,
                                        carve::math::Matrix3 *axis_matrix_r);
 
 int carve_triangulatePoly(struct ImportMeshData *import_data,
                           CarveMeshImporter *mesh_importer,
-                          const std::vector<carve::geom3d::Vector> &vertices,
+                          const std::vector<carve::mesh::MeshSet<3>::vertex_t> &vertex_storage,
                           const int verts_per_poly,
                           const int *verts_of_poly,
                           const carve::math::Matrix3 &axis_matrix,