Backported #638 from unstable

1 files changed, 25 insertions, 25 deletions

diff --git a/src/CGALEvaluator.cc b/src/CGALEvaluator.cc
index 60d98b8..b5abde3 100644
--- a/src/CGALEvaluator.cc
+++ b/src/CGALEvaluator.cc
@@ -131,7 +131,7 @@ CGAL_Nef_polyhedron CGALEvaluator::applyHull(const CgaladvNode &node)
 	CGAL_Nef_polyhedron N;
 	std::list<CGAL_Nef_polyhedron2*> polys;
 	std::list<CGAL_Nef_polyhedron2::Point> points2d;
-	std::list<CGAL_Polyhedron::Vertex::Point_3> points3d;
+	std::vector<CGAL_Polyhedron::Vertex::Point_3> points3d;
 	int dim = 0;
 	BOOST_FOREACH(const ChildItem &item, this->visitedchildren[node.index()]) {
 		const AbstractNode *chnode = item.first;
@@ -159,26 +159,8 @@ CGAL_Nef_polyhedron CGALEvaluator::applyHull(const CgaladvNode &node)
 			}
 		}
 		else if (dim == 3) {
-			CGAL_Polyhedron P;
-			if (!chN.p3->is_simple()) {
-				PRINT("Hull() currently requires a valid 2-manifold. Please modify your design. See http://en.wikibooks.org/wiki/OpenSCAD_User_Manual/STL_Import_and_Export");
-			}
-			else {
-				bool err = false;
-				std::string errmsg("");
-				try {
-					err = nefworkaround::convert_to_Polyhedron<CGAL_Kernel3>( *(chN.p3), P );
-					//chN.p3->convert_to_Polyhedron(P);
-				} catch (const CGAL::Failure_exception &e) {
-					err = true;
-					errmsg = std::string(e.what());
-				}
-				if (err) {
-					PRINTB("ERROR: CGAL NefPolyhedron->Polyhedron conversion failed. %s", errmsg);
-				} else {
-					std::transform(P.vertices_begin(), P.vertices_end(), std::back_inserter(points3d), 
-										 boost::bind(static_cast<const CGAL_Polyhedron::Vertex::Point_3&(CGAL_Polyhedron::Vertex::*)() const>(&CGAL_Polyhedron::Vertex::point), _1));
-				}
+			for (CGAL_Nef_polyhedron3::Vertex_const_iterator i = chN.p3->vertices_begin(); i != chN.p3->vertices_end(); ++i) {
+				points3d.push_back(i->point());
 			}
 		}
 		chnode->progress_report();
@@ -191,10 +173,28 @@ CGAL_Nef_polyhedron CGALEvaluator::applyHull(const CgaladvNode &node)
 																										 CGAL_Nef_polyhedron2::INCLUDED));
 	}
 	else if (dim == 3) {
-		CGAL_Polyhedron P;
-		if (points3d.size()>3)
-			CGAL::convex_hull_3(points3d.begin(), points3d.end(), P);
-		N = CGAL_Nef_polyhedron(new CGAL_Nef_polyhedron3(P));
+		if (points3d.size() > 3) {
+
+    // Remove all duplicated points (speeds up the convex_hull computation significantly)
+			std::vector<CGAL_Polyhedron::Vertex::Point_3> unique_points;
+			Grid3d<int> grid(GRID_FINE);
+			
+			BOOST_FOREACH(CGAL_Polyhedron::Vertex::Point_3 const& p, points3d) {
+				double x = to_double(p.x()), y = to_double(p.y()), z = to_double(p.z());
+				int& v = grid.align(x,y,z);
+				if (v == 0) {
+					unique_points.push_back(CGAL_Polyhedron::Vertex::Point_3(x,y,z));
+					v = 1;
+				}
+			}
+
+			// Apply hull
+			if (points3d.size() >= 4) {
+				CGAL_Polyhedron P;
+				CGAL::convex_hull_3(unique_points.begin(), unique_points.end(), P);
+				N = CGAL_Nef_polyhedron(new CGAL_Nef_polyhedron3(P));
+			}
+		}
 	}
 	return N;
 }