summaryrefslogtreecommitdiff
path: root/src/polyset.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/polyset.cc')
-rw-r--r--src/polyset.cc280
1 files changed, 280 insertions, 0 deletions
diff --git a/src/polyset.cc b/src/polyset.cc
index 23b9876..7f3818f 100644
--- a/src/polyset.cc
+++ b/src/polyset.cc
@@ -314,5 +314,285 @@ BoundingBox PolySet::getBoundingBox() const
bbox.extend(p);
}
}
+<<<<<<< HEAD
+};
+
+CGAL_Nef_polyhedron PolySet::render_cgal_nef_polyhedron() const
+{
+ if (this->is2d)
+ {
+#if 0
+ // This version of the code causes problems in some cases.
+ // Example testcase: import_dxf("testdata/polygon8.dxf");
+ //
+ typedef std::list<CGAL_Nef_polyhedron2::Point> point_list_t;
+ typedef point_list_t::iterator point_list_it;
+ std::list< point_list_t > pdata_point_lists;
+ std::list < std::pair < point_list_it, point_list_it > > pdata;
+ Grid2d<CGAL_Nef_polyhedron2::Point> grid(GRID_COARSE);
+
+ for (int i = 0; i < this->polygons.size(); i++) {
+ pdata_point_lists.push_back(point_list_t());
+ for (int j = 0; j < this->polygons[i].size(); j++) {
+ double x = this->polygons[i][j].x;
+ double y = this->polygons[i][j].y;
+ CGAL_Nef_polyhedron2::Point p;
+ if (grid.has(x, y)) {
+ p = grid.data(x, y);
+ } else {
+ p = CGAL_Nef_polyhedron2::Point(x, y);
+ grid.data(x, y) = p;
+ }
+ pdata_point_lists.back().push_back(p);
+ }
+ pdata.push_back(std::make_pair(pdata_point_lists.back().begin(),
+ pdata_point_lists.back().end()));
+ }
+
+ CGAL_Nef_polyhedron2 N(pdata.begin(), pdata.end(), CGAL_Nef_polyhedron2::POLYGONS);
+ return CGAL_Nef_polyhedron(N);
+#endif
+#if 0
+ // This version of the code works fine but is pretty slow.
+ //
+ CGAL_Nef_polyhedron2 N;
+ Grid2d<CGAL_Nef_polyhedron2::Point> grid(GRID_COARSE);
+
+ for (int i = 0; i < this->polygons.size(); i++) {
+ std::list<CGAL_Nef_polyhedron2::Point> plist;
+ for (int j = 0; j < this->polygons[i].size(); j++) {
+ double x = this->polygons[i][j].x;
+ double y = this->polygons[i][j].y;
+ CGAL_Nef_polyhedron2::Point p;
+ if (grid.has(x, y)) {
+ p = grid.data(x, y);
+ } else {
+ p = CGAL_Nef_polyhedron2::Point(x, y);
+ grid.data(x, y) = p;
+ }
+ plist.push_back(p);
+ }
+ N += CGAL_Nef_polyhedron2(plist.begin(), plist.end(), CGAL_Nef_polyhedron2::INCLUDED);
+ }
+
+ return CGAL_Nef_polyhedron(N);
+#endif
+#if 1
+ // This version of the code does essentially the same thing as the 2nd
+ // version but merges some triangles before sending them to CGAL. This adds
+ // complexity but speeds up things..
+ //
+ struct PolyReducer
+ {
+ Grid2d<int> grid;
+ QHash< QPair<int,int>, QPair<int,int> > egde_to_poly;
+ QHash< int, CGAL_Nef_polyhedron2::Point > points;
+ QHash< int, QList<int> > polygons;
+ int poly_n;
+
+ void add_edges(int pn)
+ {
+ for (int j = 1; j <= this->polygons[pn].size(); j++) {
+ int a = this->polygons[pn][j-1];
+ int b = this->polygons[pn][j % this->polygons[pn].size()];
+ if (a > b) { a = a^b; b = a^b; a = a^b; }
+ if (this->egde_to_poly[QPair<int,int>(a, b)].first == 0)
+ this->egde_to_poly[QPair<int,int>(a, b)].first = pn;
+ else if (this->egde_to_poly[QPair<int,int>(a, b)].second == 0)
+ this->egde_to_poly[QPair<int,int>(a, b)].second = pn;
+ else
+ abort();
+ }
+ }
+
+ void del_poly(int pn)
+ {
+ for (int j = 1; j <= this->polygons[pn].size(); j++) {
+ int a = this->polygons[pn][j-1];
+ int b = this->polygons[pn][j % this->polygons[pn].size()];
+ if (a > b) { a = a^b; b = a^b; a = a^b; }
+ if (this->egde_to_poly[QPair<int,int>(a, b)].first == pn)
+ this->egde_to_poly[QPair<int,int>(a, b)].first = 0;
+ if (this->egde_to_poly[QPair<int,int>(a, b)].second == pn)
+ this->egde_to_poly[QPair<int,int>(a, b)].second = 0;
+ }
+ this->polygons.remove(pn);
+ }
+
+ PolyReducer(const PolySet *ps) : grid(GRID_COARSE), poly_n(1)
+ {
+ int point_n = 1;
+ for (int i = 0; i < ps->polygons.size(); i++) {
+ for (int j = 0; j < ps->polygons[i].size(); j++) {
+ double x = ps->polygons[i][j].x;
+ double y = ps->polygons[i][j].y;
+ if (this->grid.has(x, y)) {
+ int idx = this->grid.data(x, y);
+ // Filter away two vertices with the same index (due to grid)
+ // This could be done in a more general way, but we'd rather redo the entire
+ // grid concept instead.
+ if (this->polygons[this->poly_n].indexOf(idx) == -1) {
+ this->polygons[this->poly_n].append(this->grid.data(x, y));
+ }
+ } else {
+ this->grid.align(x, y) = point_n;
+ this->polygons[this->poly_n].append(point_n);
+ this->points[point_n] = CGAL_Nef_polyhedron2::Point(x, y);
+ point_n++;
+ }
+ }
+ if (this->polygons[this->poly_n].size() >= 3) {
+ add_edges(this->poly_n);
+ this->poly_n++;
+ }
+ else {
+ this->polygons.remove(this->poly_n);
+ }
+ }
+ }
+
+ int merge(int p1, int p1e, int p2, int p2e)
+ {
+ for (int i = 1; i < this->polygons[p1].size(); i++) {
+ int j = (p1e + i) % this->polygons[p1].size();
+ this->polygons[this->poly_n].append(this->polygons[p1][j]);
+ }
+ for (int i = 1; i < this->polygons[p2].size(); i++) {
+ int j = (p2e + i) % this->polygons[p2].size();
+ this->polygons[this->poly_n].append(this->polygons[p2][j]);
+ }
+ del_poly(p1);
+ del_poly(p2);
+ add_edges(this->poly_n);
+ return this->poly_n++;
+ }
+
+ void reduce()
+ {
+ QList<int> work_queue;
+ QHashIterator< int, QList<int> > it(polygons);
+ while (it.hasNext()) {
+ it.next();
+ work_queue.append(it.key());
+ }
+ while (!work_queue.isEmpty()) {
+ int poly1_n = work_queue.first();
+ work_queue.removeFirst();
+ if (!this->polygons.contains(poly1_n))
+ continue;
+ for (int j = 1; j <= this->polygons[poly1_n].size(); j++) {
+ int a = this->polygons[poly1_n][j-1];
+ int b = this->polygons[poly1_n][j % this->polygons[poly1_n].size()];
+ if (a > b) { a = a^b; b = a^b; a = a^b; }
+ if (this->egde_to_poly[QPair<int,int>(a, b)].first != 0 &&
+ this->egde_to_poly[QPair<int,int>(a, b)].second != 0) {
+ int poly2_n = this->egde_to_poly[QPair<int,int>(a, b)].first +
+ this->egde_to_poly[QPair<int,int>(a, b)].second - poly1_n;
+ int poly2_edge = -1;
+ for (int k = 1; k <= this->polygons[poly2_n].size(); k++) {
+ int c = this->polygons[poly2_n][k-1];
+ int d = this->polygons[poly2_n][k % this->polygons[poly2_n].size()];
+ if (c > d) { c = c^d; d = c^d; c = c^d; }
+ if (a == c && b == d) {
+ poly2_edge = k-1;
+ continue;
+ }
+ int poly3_n = this->egde_to_poly[QPair<int,int>(c, d)].first +
+ this->egde_to_poly[QPair<int,int>(c, d)].second - poly2_n;
+ if (poly3_n < 0)
+ continue;
+ if (poly3_n == poly1_n)
+ goto next_poly1_edge;
+ }
+ work_queue.append(merge(poly1_n, j-1, poly2_n, poly2_edge));
+ goto next_poly1;
+ }
+ next_poly1_edge:;
+ }
+ next_poly1:;
+ }
+ }
+
+ CGAL_Nef_polyhedron2 toNef()
+ {
+ CGAL_Nef_polyhedron2 N;
+
+ QHashIterator< int, QList<int> > it(polygons);
+ while (it.hasNext()) {
+ it.next();
+ std::list<CGAL_Nef_polyhedron2::Point> plist;
+ for (int j = 0; j < it.value().size(); j++) {
+ int p = it.value()[j];
+ plist.push_back(points[p]);
+ }
+ N += CGAL_Nef_polyhedron2(plist.begin(), plist.end(), CGAL_Nef_polyhedron2::INCLUDED);
+ }
+
+ return N;
+ }
+ };
+
+ PolyReducer pr(this);
+ // printf("Number of polygons before reduction: %d\n", pr.polygons.size());
+ pr.reduce();
+ // printf("Number of polygons after reduction: %d\n", pr.polygons.size());
+ return CGAL_Nef_polyhedron(pr.toNef());
+#endif
+#if 0
+ // This is another experimental version. I should run faster than the above,
+ // is a lot simpler and has only one known weakness: Degenerate polygons, which
+ // get repaired by GLUTess, might trigger a CGAL crash here. The only
+ // known case for this is triangle-with-duplicate-vertex.dxf
+ // FIXME: If we just did a projection, we need to recreate the border!
+ if (this->polygons.size() > 0) assert(this->borders.size() > 0);
+ CGAL_Nef_polyhedron2 N;
+ Grid2d<CGAL_Nef_polyhedron2::Point> grid(GRID_COARSE);
+
+ for (int i = 0; i < this->borders.size(); i++) {
+ std::list<CGAL_Nef_polyhedron2::Point> plist;
+ for (int j = 0; j < this->borders[i].size(); j++) {
+ double x = this->borders[i][j].x;
+ double y = this->borders[i][j].y;
+ CGAL_Nef_polyhedron2::Point p;
+ if (grid.has(x, y)) {
+ p = grid.data(x, y);
+ } else {
+ p = CGAL_Nef_polyhedron2::Point(x, y);
+ grid.data(x, y) = p;
+ }
+ plist.push_back(p);
+ }
+ // FIXME: If a border (path) has a duplicate vertex in dxf,
+ // the CGAL_Nef_polyhedron2 constructor will crash.
+ N ^= CGAL_Nef_polyhedron2(plist.begin(), plist.end(), CGAL_Nef_polyhedron2::INCLUDED);
+ }
+
+ return CGAL_Nef_polyhedron(N);
+
+#endif
+ }
+ else // not (this->is2d)
+ {
+ CGAL::Failure_behaviour old_behaviour = CGAL::set_error_behaviour(CGAL::THROW_EXCEPTION);
+ try {
+ CGAL_Polyhedron P;
+ CGAL_Build_PolySet builder(this);
+ P.delegate(builder);
+#if 0
+ std::cout << P;
+#endif
+ CGAL_Nef_polyhedron3 N(P);
+ return CGAL_Nef_polyhedron(N);
+ }
+ catch (CGAL::Assertion_exception e) {
+ PRINTF("CGAL error: %s", e.what());
+ CGAL::set_error_behaviour(old_behaviour);
+ return CGAL_Nef_polyhedron();
+ }
+ CGAL::set_error_behaviour(old_behaviour);
+ }
+ return CGAL_Nef_polyhedron();
+=======
return bbox;
+>>>>>>> upstream/visitor
}
contact: Jan Huwald // Impressum