Clifford Wolf:

	Prep for dxftess-cgal hole detection



git-svn-id: http://svn.clifford.at/openscad/trunk@389 b57f626f-c46c-0410-a088-ec61d464b74c

1 files changed, 145 insertions, 29 deletions

diff --git a/src/dxftess-cgal.cc b/src/dxftess-cgal.cc
index 14fbc5e..3c71f2f 100644
--- a/src/dxftess-cgal.cc
+++ b/src/dxftess-cgal.cc
@@ -1,4 +1,8 @@
 #include "printutils.h"
+#include "dxftess.h"
+#include "dxfdata.h"
+#include "polyset.h"
+#include "grid.h"
 
 #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
 #include <CGAL/Constrained_Delaunay_triangulation_2.h>
@@ -21,68 +25,180 @@ typedef CDT::Point CDTPoint;
 
 template <class T> class DummyCriteria {
 public:
-  typedef double Quality;
-  class Is_bad {
-  public:
+	typedef double Quality;
+	class Is_bad {
+	public:
 		CGAL::Mesh_2::Face_badness operator()(const Quality) const {
 			return CGAL::Mesh_2::NOT_BAD;
 		}
 		CGAL::Mesh_2::Face_badness operator()(const typename T::Face_handle&, Quality&q) const {
 			q = 1;
 			return CGAL::Mesh_2::NOT_BAD;
-    }
+		}
 	};
 	Is_bad is_bad_object() const { return Is_bad(); }
 };
 
-void dxf_tesselate(PolySet *ps, DxfData *dxf, double rot, bool up, bool do_triangle_splitting, double h)
+struct triangle {
+	struct { double x, y; } p[3];
+	bool is_inner, is_marked;
+};
+
+struct point_info_t
+{
+	int pathidx, pointidx;
+	int max_pointidx_in_path;
+	QList<int> triangles;
+
+	struct point_info_t *neigh_up;
+	struct point_info_t *neigh_down;
+
+	point_info_t() : pathidx(-1), pointidx(-1), max_pointidx_in_path(-1) { }
+	point_info_t(int a, int b, int c) : pathidx(a), pointidx(b), max_pointidx_in_path(c) { }
+};
+
+#if 0
+void mark_inner_outer(QList<struct triangle> &t, Grid2d<point_info_t> &p, int idx, bool inner)
+{
+	if (t[idx].is_marked)
+		return;
+
+	if (inner)
+		t[idx].is_inner = true;
+
+	FIXME
+}
+#endif
+
+void dxf_tesselate(PolySet *ps, DxfData *dxf, double rot, bool up, bool /* do_triangle_splitting */, double h)
 {
 	CDT cdt;
 
-  //       <pathidx,pointidx>
-	Grid3d< QPair<int,int> > point_to_path(GRID_FINE);
+	QList<struct triangle> tri;
+	Grid2d<point_info_t> point_info(GRID_FINE);
+
+	double far_left_x = 0;
+	struct point_info_t *far_left_p = NULL;
 
-	for (int i = 0; i < dxf->paths.count(); i++) {
+	for (int i = 0; i < dxf->paths.count(); i++)
+	{
 		if (!dxf->paths[i].is_closed)
 			continue;
+
 		Vertex_handle first, prev;
-		for (int j = 1; j < dxf->paths[i].points.count(); j++) {
+		struct point_info_t *first_pi = NULL, *prev_pi = NULL;
+		for (int j = 1; j < dxf->paths[i].points.count(); j++)
+		{
 			double x = dxf->paths[i].points[j]->x;
 			double y = dxf->paths[i].points[j]->y;
-			point_to_path.data(x, y, h) = QPair<int,int>(i, j);
+
+			struct point_info_t *pi = &point_info.align(x, y);
+			*pi = point_info_t(i, j, dxf->paths[i].points.count()-1);
+
+			if (j == 1) {
+				first_pi = pi;
+			} else {
+				prev_pi->neigh_up = pi;
+				pi->neigh_down = prev_pi;
+			}
+			prev_pi = pi;
+
+			if (far_left_p == NULL || x < far_left_x) {
+				far_left_x = x;
+				far_left_p = &point_info.data(x, y);
+			}
+
 			Vertex_handle vh = cdt.insert(CDTPoint(x, y));
 			if (j == 1) {
 				first = vh;
-			}
-			else {
+			} else {
 				cdt.insert_constraint(prev, vh);
 			}
 			prev = vh;
 		}
+
+		prev_pi->neigh_up = first_pi;
+		first_pi->neigh_down = prev_pi;
+
  		cdt.insert_constraint(prev, first);
 	}
 
 	std::list<CDTPoint> list_of_seeds;
-// FIXME: Give hints about holes here
-// 	list_of_seeds.push_back(CDTPoint(-1, -1));
-// 	list_of_seeds.push_back(CDTPoint(20, 50));
-	CGAL::refine_Delaunay_mesh_2_without_edge_refinement(cdt, list_of_seeds.begin(), list_of_seeds.end(), 
-															 DummyCriteria<CDT>());
+	CGAL::refine_Delaunay_mesh_2_without_edge_refinement(cdt,
+			list_of_seeds.begin(), list_of_seeds.end(), DummyCriteria<CDT>());
+
 	CDT::Finite_faces_iterator iter = cdt.finite_faces_begin();
-  for( ; iter != cdt.finite_faces_end(); ++iter) {
-		if (!iter->is_in_domain()) continue;
-		ps->append_poly();
+	for(; iter != cdt.finite_faces_end(); ++iter)
+	{
+		if (!iter->is_in_domain())
+			continue;
+
+		int idx = tri.size();
+		tri.append(triangle());
+
+		for (int i=0; i<3; i++) {
+			double px = iter->vertex(i)->point()[0];
+			double py = iter->vertex(i)->point()[1];
+			point_info.align(px, py).triangles.append(idx);
+			tri[idx].p[i].x = px;
+			tri[idx].p[i].y = py;
+		}
+	}
+
+#if 0
+	for (int i = 0; i < far_left_p->triangles.size(); i++)
+	{
+		int idx = far_left_p->triangles[i];
+		point_info_t *p0 = &point_info.data(tri[idx].p[0].x, tri[idx].p[0].y);
+		point_info_t *p1 = &point_info.data(tri[idx].p[1].x, tri[idx].p[1].y);
+		point_info_t *p2 = &point_info.data(tri[idx].p[2].x, tri[idx].p[2].y);
+		point_info_t *mp = NULL, *np1 = NULL, *np2 = NULL;
+
+		if (p0 == far_left_p)
+			mp = p0, np1 = p1, np2 = p2;
+		else if (p1 == far_left_p)
+			mp = p1, np1 = p0, np2 = p2;
+		else if (p2 == far_left_p)
+			mp = p2, np1 = p0, np2 = p1;
+		else
+			continue;
 
+		if (mp->neigh_up == np2 || mp->neigh_down == np1) {
+			point_info_t *t = np1;
+			np1 = np2;
+			np2 = t;
+		}
+
+		if (mp->neigh_up == np1 && mp->neigh_down == np2) {
+			mark_inner_outer(tri, point_info, idx, true);
+			break;
+		}
+
+		if (mp->neigh_up == np1) {
+			FIXME
+		}
+
+		if (mp->neigh_up == np1) {
+			FIXME
+		}
+	}
+#endif
+
+	for(int i = 0; i < tri.size(); i++)
+	{
+		// if (!tri[i].is_inner)
+		//	continue;
+
+		ps->append_poly();
 		int path[3], point[3];
-		for (int i=0;i<3;i++) {
-			int idx = up ? i : (2-i);
-			double px = iter->vertex(idx)->point()[0];
-			double py = iter->vertex(idx)->point()[1];
-			ps->append_vertex(px *  cos(rot*M_PI/180) + py * sin(rot*M_PI/180),
-												px * -sin(rot*M_PI/180) + py * cos(rot*M_PI/180),
-												h);
-			path[i] = point_to_path.data(px, py, h).first;
-			point[i] = point_to_path.data(px, py, h).second;
+		for (int j=0;j<3;j++) {
+			int idx = up ? j : (2-j);
+			double px = tri[i].p[idx].x;
+			double py = tri[i].p[idx].y;
+			ps->append_vertex(px * cos(rot*M_PI/180) + py * sin(rot*M_PI/180),
+					px * -sin(rot*M_PI/180) + py * cos(rot*M_PI/180), h);
+			path[j] = point_info.data(px, py).pathidx;
+			point[j] = point_info.data(px, py).pointidx;
 		}
 
 		if (path[0] == path[1] && point[0] == 1 && point[1] == 2)