Preserve non-flat faces in boolean modifier

This commit implements dissolving of edges which were used
to triangulate non-flat faces. This slows things down a bit
(around 5% on heave mesh with all faces triangulated).

We could improve speed of dissolve a bit here (so not a bell
to add an option for triangulation yet).

Also fixed wrong edge origindex mapping.

10 files changed, 263 insertions, 7 deletions

diff --git a/extern/carve/CMakeLists.txt b/extern/carve/CMakeLists.txt
index 11a92f92abc..5754290d710 100644
--- a/extern/carve/CMakeLists.txt
+++ b/extern/carve/CMakeLists.txt
@@ -140,6 +140,7 @@ set(SRC
 	include/carve/tag.hpp
 	include/carve/timing.hpp
 	include/carve/tree.hpp
+	include/carve/triangle_intersection.hpp
 	include/carve/triangulator.hpp
 	include/carve/triangulator_impl.hpp
 	include/carve/util.hpp
diff --git a/extern/carve/bundle.sh b/extern/carve/bundle.sh
index 91d5f44a880..2a3e621fab0 100755
--- a/extern/carve/bundle.sh
+++ b/extern/carve/bundle.sh
@@ -111,6 +111,7 @@ cat > SConscript << EOF
 Import ('env')
 
 sources = env.Glob('lib/*.cpp')
+sources += env.Glob('*.cc')
 
 defs = []
 incs = ['include']
diff --git a/extern/carve/carve-capi.cc b/extern/carve/carve-capi.cc
index ed46d196d72..319a20129d1 100644
--- a/extern/carve/carve-capi.cc
+++ b/extern/carve/carve-capi.cc
@@ -30,6 +30,7 @@
 #include <carve/interpolator.hpp>
 #include <carve/rescale.hpp>
 #include <carve/csg_triangulator.hpp>
+#include <carve/mesh_simplify.hpp>
 
 using carve::mesh::MeshSet;
 
@@ -38,6 +39,7 @@ typedef std::pair<MeshSet<3>::vertex_t *, MeshSet<3>::vertex_t *> VertexPair;
 typedef carve::interpolate::VertexAttr<OrigIndex> OrigVertMapping;
 typedef carve::interpolate::FaceAttr<OrigIndex> OrigFaceMapping;
 typedef carve::interpolate::FaceEdgeAttr<OrigIndex> OrigFaceEdgeMapping;
+typedef carve::interpolate::FaceEdgeAttr<bool> FaceEdgeTriangulatedFlag;
 
 typedef struct CarveMeshDescr {
 	// Stores mesh data itself.
@@ -57,6 +59,8 @@ typedef struct CarveMeshDescr {
 	// Mapping from the face edges back to (original edge index, original loop index).
 	OrigFaceEdgeMapping orig_face_edge_mapping;
 
+	FaceEdgeTriangulatedFlag face_edge_triangulated_flag;
+
 	// Mapping from the faces back to original poly index.
 	OrigFaceMapping orig_face_mapping;
 } CarveMeshDescr;
@@ -131,6 +135,7 @@ void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
                                   const std::vector<int> &orig_poly_index_map,
                                   OrigVertMapping *orig_vert_mapping,
                                   OrigFaceEdgeMapping *orig_face_edge_mapping,
+                                  FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
                                   OrigFaceMapping *orig_face_attr)
 {
 	MeshSet<3> *poly = mesh->poly;
@@ -169,6 +174,9 @@ void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
 				                                     std::make_pair(which_mesh,
 				                                                    orig_loop_index));
 			}
+			else {
+				face_edge_triangulated_flag->setAttribute(face, edge_iter.idx(), true);
+			}
 		}
 	}
 }
@@ -177,6 +185,7 @@ void initOrigIndexMapping(CarveMeshDescr *left_mesh,
                           CarveMeshDescr *right_mesh,
                           OrigVertMapping *orig_vert_mapping,
                           OrigFaceEdgeMapping *orig_face_edge_mapping,
+                          FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
                           OrigFaceMapping *orig_face_mapping)
 {
 	initOrigIndexMeshFaceMapping(left_mesh,
@@ -185,6 +194,7 @@ void initOrigIndexMapping(CarveMeshDescr *left_mesh,
 	                             left_mesh->orig_poly_index_map,
 	                             orig_vert_mapping,
 	                             orig_face_edge_mapping,
+	                             face_edge_triangulated_flag,
 	                             orig_face_mapping);
 
 	initOrigIndexMeshFaceMapping(right_mesh,
@@ -193,9 +203,119 @@ void initOrigIndexMapping(CarveMeshDescr *left_mesh,
 	                             right_mesh->orig_poly_index_map,
 	                             orig_vert_mapping,
 	                             orig_face_edge_mapping,
+	                             face_edge_triangulated_flag,
 	                             orig_face_mapping);
 }
 
+void origEdgeMappingForFace(MeshSet<3>::face_t *face,
+                            OrigFaceEdgeMapping *orig_face_edge_mapping,
+                            std::unordered_map<VertexPair, OrigIndex> *edge_origindex_map)
+{
+	OrigIndex origindex_none = std::make_pair((int)CARVE_MESH_NONE, -1);
+
+	MeshSet<3>::edge_t *edge = face->edge;
+	for (int i = 0;
+	     i < face->n_edges;
+	     ++i, edge = edge->next)
+	{
+		MeshSet<3>::vertex_t *v1 = edge->vert;
+		MeshSet<3>::vertex_t *v2 = edge->next->vert;
+
+		OrigIndex orig_edge_index =
+			orig_face_edge_mapping->getAttribute(edge->face, i, origindex_none);
+
+		edgeIndexMap_put(edge_origindex_map, v1, v2, orig_edge_index);
+	}
+}
+
+void dissolveTriangulatedEdges(MeshSet<3>::mesh_t *mesh,
+                               OrigFaceEdgeMapping *orig_face_edge_mapping,
+                               FaceEdgeTriangulatedFlag *face_edge_triangulated_flag)
+{
+	typedef std::unordered_set<MeshSet<3>::edge_t *> edge_set_t;
+	typedef std::unordered_set<MeshSet<3>::face_t *> face_set_t;
+	edge_set_t triangulated_face_edges;
+
+	for (int face_index = 0; face_index < mesh->faces.size(); face_index++) {
+		MeshSet<3>::face_t *face = mesh->faces[face_index];
+		MeshSet<3>::edge_t *edge = face->edge;
+		for (int edge_index = 0;
+		     edge_index < face->n_edges;
+		     ++edge_index, edge = edge->next)
+		{
+			const bool is_triangulated_edge =
+				face_edge_triangulated_flag->getAttribute(face,
+				                                          edge_index,
+				                                          false);
+			if (is_triangulated_edge) {
+				MeshSet<3>::edge_t *e1 = std::min(edge, edge->rev);
+				triangulated_face_edges.insert(e1);
+			}
+		}
+	}
+
+	if (triangulated_face_edges.size()) {
+		face_set_t triangulated_faces;
+		std::unordered_map<VertexPair, OrigIndex> edge_origindex_map;
+
+		for (edge_set_t::iterator it = triangulated_face_edges.begin();
+		     it != triangulated_face_edges.end();
+		     ++it)
+		{
+			MeshSet<3>::edge_t *edge = *it;
+
+			origEdgeMappingForFace(edge->face,
+			                       orig_face_edge_mapping,
+			                       &edge_origindex_map);
+			triangulated_faces.insert(edge->face);
+
+			origEdgeMappingForFace(edge->rev->face,
+			                       orig_face_edge_mapping,
+			                       &edge_origindex_map);
+			triangulated_faces.insert(edge->rev->face);
+		}
+
+		carve::mesh::MeshSimplifier simplifier;
+		simplifier.dissolveMeshEdges(mesh, triangulated_face_edges);
+
+		for (int face_index = 0; face_index < mesh->faces.size(); face_index++) {
+			MeshSet<3>::face_t *face = mesh->faces[face_index];
+
+			if (triangulated_faces.find(face) != triangulated_faces.end()) {
+				MeshSet<3>::edge_t *edge = face->edge;
+				for (int edge_index = 0;
+				     edge_index < face->n_edges;
+				     ++edge_index, edge = edge->next)
+				{
+					MeshSet<3>::vertex_t *v1 = edge->vert;
+					MeshSet<3>::vertex_t *v2 = edge->next->vert;
+
+					OrigIndex orig_edge_index =
+						edgeIndexMap_get(edge_origindex_map,
+						                 v1,
+						                 v2);
+
+					orig_face_edge_mapping->setAttribute(face, edge_index, orig_edge_index);
+				}
+			}
+		}
+	}
+}
+
+void dissolveTriangulatedEdges(CarveMeshDescr *mesh_descr)
+{
+	MeshSet<3> *poly = mesh_descr->poly;
+	FaceEdgeTriangulatedFlag *face_edge_triangulated_flag =
+		&mesh_descr->face_edge_triangulated_flag;
+
+	for (int i = 0; i < poly->meshes.size(); ++i) {
+		MeshSet<3>::mesh_t *mesh = poly->meshes[i];
+		dissolveTriangulatedEdges(mesh,
+		                          &mesh_descr->orig_face_edge_mapping,
+		                          face_edge_triangulated_flag);
+	}
+}
+
 }  // namespace
 
 CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
@@ -271,6 +391,7 @@ CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
 			                                      &mesh_descr->orig_poly_index_map);
 
 			num_tessellated_polys += num_triangles;
+			loop_index += verts_per_poly;
 		}
 		else {
 			face_indices.push_back(verts_per_poly);
@@ -345,6 +466,7 @@ bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
 		initOrigIndexMapping(left_mesh, right_mesh,
 		                     &output_descr->orig_vert_mapping,
 		                     &output_descr->orig_face_edge_mapping,
+		                     &output_descr->face_edge_triangulated_flag,
 		                     &output_descr->orig_face_mapping);
 
 		carve::csg::CSG csg;
@@ -354,6 +476,7 @@ bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
 
 		output_descr->orig_vert_mapping.installHooks(csg);
 		output_descr->orig_face_edge_mapping.installHooks(csg);
+		output_descr->face_edge_triangulated_flag.installHooks(csg);
 		output_descr->orig_face_mapping.installHooks(csg);
 
 		// Prepare operands for actual boolean operation.
@@ -383,6 +506,8 @@ bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
 		                                 carve::csg::CSG::CLASSIFY_EDGE);
 		if (output_descr->poly) {
 			output_descr->poly->transform(rev_r);
+
+			dissolveTriangulatedEdges(output_descr);
 		}
 	}
 	catch (carve::exception e) {
diff --git a/extern/carve/carve-util.cc b/extern/carve/carve-util.cc
index b9b7fb1c03f..b1943a6dd74 100644
--- a/extern/carve/carve-util.cc
+++ b/extern/carve/carve-util.cc
@@ -619,6 +619,7 @@ int triangulateNGon_carveTriangulator(const std::vector<Vector> &vertices,
 	}
 
 	carve::triangulate::triangulate(poly_2d, *triangles);
+	carve::triangulate::improve(poly_2d, *triangles);
 
 	return triangles->size();
 }
@@ -737,9 +738,9 @@ int carve_triangulatePoly(struct ImportMeshData *import_data,
 		}
 
 		for (int i = 0; i < triangles.size(); ++i) {
-			int v1 = triangles[i].c,
+			int v1 = triangles[i].a,
 			    v2 = triangles[i].b,
-			    v3 = triangles[i].a;
+			    v3 = triangles[i].c;
 
 			// Sanity check of the triangle.
 			assert(v1 != v2);
@@ -750,13 +751,15 @@ int carve_triangulatePoly(struct ImportMeshData *import_data,
 			assert(v3 < verts_per_poly);
 
 			face_indices->push_back(3);
-			face_indices->push_back(verts_of_poly[v3]);
-			face_indices->push_back(verts_of_poly[v2]);
 			face_indices->push_back(verts_of_poly[v1]);
+			face_indices->push_back(verts_of_poly[v2]);
+			face_indices->push_back(verts_of_poly[v3]);
 
 #define CHECK_TRIANGLE_LOOP_INDEX(v1, v2) \
 	{ \
-		if (v2 == v1 + 1) { \
+		int v1_ = std::min(v1, v2), \
+		    v2_ = std::max(v1, v2); \
+		if (v1_ + 1 == v2_ || v1_ + verts_per_poly == v2_ + 1) { \
 			orig_loop_index_map->push_back(start_loop_index + v1); \
 		} \
 		else { \
diff --git a/extern/carve/files.txt b/extern/carve/files.txt
index f7da6038692..5c02a04dfe2 100644
--- a/extern/carve/files.txt
+++ b/extern/carve/files.txt
@@ -1,6 +1,7 @@
 include/carve/vertex_impl.hpp
 include/carve/aabb_impl.hpp
 include/carve/csg.hpp
+include/carve/triangle_intersection.hpp
 include/carve/pointset_iter.hpp
 include/carve/debug_hooks.hpp
 include/carve/mesh.hpp
diff --git a/extern/carve/include/carve/mesh_simplify.hpp b/extern/carve/include/carve/mesh_simplify.hpp
index 1c5169caf58..2126c57011b 100644
--- a/extern/carve/include/carve/mesh_simplify.hpp
+++ b/extern/carve/include/carve/mesh_simplify.hpp
@@ -32,8 +32,6 @@
 #include <algorithm>
 #include <vector>
 
-#include "write_ply.hpp"
-
 
 namespace carve {
   namespace mesh {
@@ -1184,6 +1182,33 @@ namespace carve {
         return modifications;
       }
 
+      void dissolveMeshEdges(mesh_t *mesh, std::unordered_set<edge_t *> dissolve_edges) {
+        while (dissolve_edges.size()) {
+            MeshSet<3>::edge_t *edge = *dissolve_edges.begin();
+            if (edge->face == edge->rev->face) {
+                dissolve_edges.erase(edge);
+                continue;
+            }
+
+            MeshSet<3>::edge_t *removed = edge->mergeFaces();
+            if (removed == NULL) {
+                dissolve_edges.erase(edge);
+            } else {
+                MeshSet<3>::edge_t *e = removed;
+                do {
+                    MeshSet<3>::edge_t *n = e->next;
+                    dissolve_edges.erase(std::min(e, e->rev));
+                    delete e->rev;
+                    delete e;
+                    e = n;
+                } while (e != removed);
+            }
+        }
+
+        removeRemnantFaces(mesh);
+        cleanFaceEdges(mesh);
+        mesh->cacheEdges();
+     }
 
 
       size_t improveMesh(meshset_t *meshset,
diff --git a/extern/carve/include/carve/triangle_intersection.hpp b/extern/carve/include/carve/triangle_intersection.hpp
new file mode 100644
index 00000000000..f1f4c2137f1
--- /dev/null
+++ b/extern/carve/include/carve/triangle_intersection.hpp
@@ -0,0 +1,53 @@
+// Begin License:
+// Copyright (C) 2006-2011 Tobias Sargeant (tobias.sargeant@gmail.com).
+// All rights reserved.
+//
+// This file is part of the Carve CSG Library (http://carve-csg.com/)
+//
+// This file may be used under the terms of the GNU General Public
+// License version 2.0 as published by the Free Software Foundation
+// and appearing in the file LICENSE.GPL2 included in the packaging of
+// this file.
+//
+// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
+// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE.
+// End:
+
+
+#pragma once
+
+#include <carve/carve.hpp>
+
+#include <carve/geom.hpp>
+
+namespace carve {
+  namespace geom {
+
+    enum TriangleIntType {
+      TR_TYPE_NONE = 0,
+      TR_TYPE_TOUCH = 1,
+      TR_TYPE_INT = 2
+    };
+
+    enum TriangleInt {
+      TR_INT_NONE = 0,      // no intersection.
+      TR_INT_INT = 1,       // intersection.
+      TR_INT_VERT = 2,      // intersection due to shared vertex.
+      TR_INT_EDGE = 3,      // intersection due to shared edge.
+      TR_INT_TRI = 4        // intersection due to identical triangle.
+    };
+
+    TriangleInt triangle_intersection(const vector<2> tri_a[3], const vector<2> tri_b[3]);
+    TriangleInt triangle_intersection(const vector<3> tri_a[3], const vector<3> tri_b[3]);
+
+    bool triangle_intersection_simple(const vector<2> tri_a[3], const vector<2> tri_b[3]);
+    bool triangle_intersection_simple(const vector<3> tri_a[3], const vector<3> tri_b[3]);
+
+    TriangleIntType triangle_intersection_exact(const vector<2> tri_a[3], const vector<2> tri_b[3]);
+    TriangleIntType triangle_intersection_exact(const vector<3> tri_a[3], const vector<3> tri_b[3]);
+
+    TriangleIntType triangle_linesegment_intersection_exact(const vector<2> tri_a[3], const vector<2> line_b[2]);
+    TriangleIntType triangle_point_intersection_exact(const vector<2> tri_a[3], const vector<2> &pt_b);
+  }
+}
diff --git a/extern/carve/include/carve/win32.h b/extern/carve/include/carve/win32.h
index 81b2ea4d6fa..81b2ea4d6fa 100644..100755
--- a/extern/carve/include/carve/win32.h
+++ b/extern/carve/include/carve/win32.h
diff --git a/extern/carve/patches/mesh_simplify_dissolve_edges.patch b/extern/carve/patches/mesh_simplify_dissolve_edges.patch
new file mode 100644
index 00000000000..bd671bfcbcf
--- /dev/null
+++ b/extern/carve/patches/mesh_simplify_dissolve_edges.patch
@@ -0,0 +1,46 @@
+diff -r e82d852e4fb0 include/carve/mesh_simplify.hpp
+--- a/include/carve/mesh_simplify.hpp	Wed Jan 15 13:16:14 2014 +1100
++++ b/include/carve/mesh_simplify.hpp	Mon Feb 24 18:02:07 2014 +0600
+@@ -32,8 +32,6 @@
+ #include <algorithm>
+ #include <vector>
+ 
+-#include "write_ply.hpp"
+-
+ 
+ namespace carve {
+   namespace mesh {
+@@ -1184,6 +1182,33 @@
+         return modifications;
+       }
+ 
++      void dissolveMeshEdges(mesh_t *mesh, std::unordered_set<edge_t *> dissolve_edges) {
++        while (dissolve_edges.size()) {
++            MeshSet<3>::edge_t *edge = *dissolve_edges.begin();
++            if (edge->face == edge->rev->face) {
++                dissolve_edges.erase(edge);
++                continue;
++            }
++
++            MeshSet<3>::edge_t *removed = edge->mergeFaces();
++            if (removed == NULL) {
++                dissolve_edges.erase(edge);
++            } else {
++                MeshSet<3>::edge_t *e = removed;
++                do {
++                    MeshSet<3>::edge_t *n = e->next;
++                    dissolve_edges.erase(std::min(e, e->rev));
++                    delete e->rev;
++                    delete e;
++                    e = n;
++                } while (e != removed);
++            }
++        }
++
++        removeRemnantFaces(mesh);
++        cleanFaceEdges(mesh);
++        mesh->cacheEdges();
++     }
+ 
+ 
+       size_t improveMesh(meshset_t *meshset,
diff --git a/extern/carve/patches/series b/extern/carve/patches/series
index 30937b4b9cf..2c187af4808 100644
--- a/extern/carve/patches/series
+++ b/extern/carve/patches/series
@@ -6,3 +6,4 @@ gcc46.patch
 clang_is_heap_fix.patch
 strict_flags.patch
 interpolator_reorder.patch
+mesh_simplify_dissolve_edges.patch