diff options
| -rw-r--r-- | dxfdata.cc | 88 | ||||
| -rw-r--r-- | dxftess.cc | 2 | ||||
| -rw-r--r-- | openscad.h | 19 |
3 files changed, 74 insertions, 35 deletions
@@ -21,6 +21,7 @@ #include "openscad.h" #include <QFile> +#include <assert.h> DxfData::DxfData(double fn, double fs, double fa, QString filename, QString layername, double xorigin, double yorigin, double scale) { @@ -31,10 +32,17 @@ DxfData::DxfData(double fn, double fs, double fa, QString filename, QString laye return; } - // WARNING: The algorithms used here are extreamly sub-optimal and perform - // as bad as O(n^3). So for reading large DXF paths one might consider optimizing - // the code in this function.. QVector<Line> lines; + Grid2d< QVector<int> > grid; + +#define ADD_LINE(_x1, _y1, _x2, _y2) do { \ + double _p1x = _x1, _p1y = _y1, _p2x = _x2, _p2y = _y2; \ + grid.align(_p1x, _p1y); \ + grid.align(_p2x, _p2y); \ + grid.data(_p1x, _p1y).append(lines.count()); \ + grid.data(_p2x, _p2y).append(lines.count()); \ + lines.append(Line(p(_p1x, _p1y), p(_p2x, _p2y))); \ + } while (0) QString mode, layer; double x1 = 0, x2 = 0, y1 = 0, y2 = 0; @@ -57,15 +65,15 @@ DxfData::DxfData(double fn, double fs, double fa, QString filename, QString laye { case 0: if (mode == "LINE" && (layername.isNull() || layername == layer)) { - lines.append(Line(p(x1, y1), p(x2, y2))); + ADD_LINE(x1, y1, x2, y2); } if (mode == "CIRCLE" && (layername.isNull() || layername == layer)) { int n = get_fragments_from_r(radius, fn, fs, fa); for (int i = 0; i < n; i++) { double a1 = (2*M_PI*i)/n; double a2 = (2*M_PI*(i+1))/n; - lines.append(Line(p(cos(a1)*radius + x1, sin(a1)*radius + y1), - p(cos(a2)*radius + x1, sin(a2)*radius + y1))); + ADD_LINE(cos(a1)*radius + x1, sin(a1)*radius + y1, + cos(a2)*radius + x1, sin(a2)*radius + y1); } } if (mode == "ARC" && (layername.isNull() || layername == layer)) { @@ -78,8 +86,8 @@ DxfData::DxfData(double fn, double fs, double fa, QString filename, QString laye double a2 = ((stop_angle-start_angle)*(i+1))/n; a1 = (start_angle + a1) * M_PI / 180.0; a2 = (start_angle + a2) * M_PI / 180.0; - lines.append(Line(p(cos(a1)*radius + x1, sin(a1)*radius + y1), - p(cos(a2)*radius + x1, sin(a2)*radius + y1))); + ADD_LINE(cos(a1)*radius + x1, sin(a1)*radius + y1, + cos(a2)*radius + x1, sin(a2)*radius + y1); } } if (in_entities_section) { @@ -125,20 +133,24 @@ DxfData::DxfData(double fn, double fs, double fa, QString filename, QString laye i.key(), QString::number(i.value()), filename); } + QHash<int, int> enabled_lines; + for (int i = 0; i < lines.count(); i++) { + enabled_lines[i] = i; + } + // extract all open paths - while (lines.count() > 0) + while (enabled_lines.count() > 0) { int current_line, current_point; - for (int i = 0; i < lines.count(); i++) { + foreach (int i, enabled_lines) { for (int j = 0; j < 2; j++) { - for (int k = 0; k < lines.count(); k++) { - if (i == k) + QVector<int> *lv = &grid.data(lines[i].p[j]->x, lines[i].p[j]->y); + for (int ki = 0; ki < lv->count(); ki++) { + int k = lv->at(ki); + if (k == i || lines[k].disabled) continue; - if (lines[i].p[j] == lines[k].p[0]) - goto next_open_path_j; - if (lines[i].p[j] == lines[k].p[1]) - goto next_open_path_j; + goto next_open_path_j; } current_line = i; current_point = j; @@ -157,14 +169,19 @@ DxfData::DxfData(double fn, double fs, double fa, QString filename, QString laye while (1) { this_path->points.append(lines[current_line].p[!current_point]); Point *ref_point = lines[current_line].p[!current_point]; - lines.remove(current_line); - for (int k = 0; k < lines.count(); k++) { - if (ref_point == lines[k].p[0]) { + lines[current_line].disabled = true; + enabled_lines.remove(current_line); + QVector<int> *lv = &grid.data(ref_point->x, ref_point->y); + for (int ki = 0; ki < lv->count(); ki++) { + int k = lv->at(ki); + if (lines[k].disabled) + continue; + if (grid.eq(ref_point->x, ref_point->y, lines[k].p[0]->x, lines[k].p[0]->y)) { current_line = k; current_point = 0; goto found_next_line_in_open_path; } - if (ref_point == lines[k].p[1]) { + if (grid.eq(ref_point->x, ref_point->y, lines[k].p[1]->x, lines[k].p[1]->y)) { current_line = k; current_point = 1; goto found_next_line_in_open_path; @@ -176,9 +193,10 @@ DxfData::DxfData(double fn, double fs, double fa, QString filename, QString laye } // extract all closed paths - while (lines.count() > 0) + while (enabled_lines.count() > 0) { - int current_line = 0, current_point = 0; + int current_line = enabled_lines.begin().value(), current_point = 0; + assert(lines[current_line].disabled == false); paths.append(Path()); Path *this_path = &paths.last(); @@ -188,14 +206,19 @@ DxfData::DxfData(double fn, double fs, double fa, QString filename, QString laye while (1) { this_path->points.append(lines[current_line].p[!current_point]); Point *ref_point = lines[current_line].p[!current_point]; - lines.remove(current_line); - for (int k = 0; k < lines.count(); k++) { - if (ref_point == lines[k].p[0]) { + lines[current_line].disabled = true; + enabled_lines.remove(current_line); + QVector<int> *lv = &grid.data(ref_point->x, ref_point->y); + for (int ki = 0; ki < lv->count(); ki++) { + int k = lv->at(ki); + if (lines[k].disabled) + continue; + if (grid.eq(ref_point->x, ref_point->y, lines[k].p[0]->x, lines[k].p[0]->y)) { current_line = k; current_point = 0; goto found_next_line_in_closed_path; } - if (ref_point == lines[k].p[1]) { + if (grid.eq(ref_point->x, ref_point->y, lines[k].p[1]->x, lines[k].p[1]->y)) { current_line = k; current_point = 1; goto found_next_line_in_closed_path; @@ -250,22 +273,21 @@ DxfData::DxfData(double fn, double fs, double fa, QString filename, QString laye #if 0 printf("----- DXF Data -----\n"); for (int i = 0; i < paths.count(); i++) { - printf("Path %d (%s, %s):\n", i, paths[i].is_closed ? "closed" : "open", - paths[i].is_inner ? "inner" : "outer"); + if (paths[i].is_closed) + printf("Path %d (closed, %s):\n", i, paths[i].is_inner ? "inner" : "outer"); + else + printf("Path %d (open):\n", i); for (int j = 0; j < paths[i].points.count(); j++) printf(" %f %f\n", paths[i].points[j]->x, paths[i].points[j]->y); } printf("--------------------\n"); + fflush(stdout); #endif } DxfData::Point *DxfData::p(double x, double y) { - for (int i = 0; i < points.count(); i++) { - if (abs(points[i].x - x) < 0.01 && abs(points[i].y - y) < 0.01) - return &points[i]; - } points.append(Point(x, y)); - return &points[points.count()-1]; + return &points.last(); } @@ -199,6 +199,7 @@ void dxf_tesselate(PolySet *ps, DxfData *dxf, bool up, double h) // GLU tessing might merge points into edges. This is ok for GL displaying but // creates invalid polyeders for CGAL. So we split this tirangles up again in order // to create polyeders that are also accepted by CGAL.. +#if 1 bool added_triangles = true; while (added_triangles) { @@ -215,6 +216,7 @@ void dxf_tesselate(PolySet *ps, DxfData *dxf, bool up, double h) } } } +#endif for (int i = 0; i < tess_tri.count(); i++) { #if 0 @@ -106,6 +106,13 @@ public: } return false; } + bool eq(double x1, double y1, double x2, double y2) { + align(x1, y1); + align(x2, y2); + if (fabs(x1 - x2) < res && fabs(y1 - y2) < res) + return true; + return false; + } T &data(double x, double y) { return align(x, y); } @@ -161,6 +168,13 @@ public: return false; } + bool eq(double x1, double y1, double z1, double x2, double y2, double z2) { + align(x1, y1, z1); + align(x2, y2, z2); + if (fabs(x1 - x2) < res && fabs(y1 - y2) < res && fabs(z1 - z2) < res) + return true; + return false; + } T &data(double x, double y, double z) { return align(x, y, z); } @@ -395,8 +409,9 @@ public: }; struct Line { Point *p[2]; - Line(Point *p1, Point *p2) { p[0] = p1; p[1] = p2; } - Line() { p[0] = NULL; p[1] = NULL; } + bool disabled; + Line(Point *p1, Point *p2) { p[0] = p1; p[1] = p2; disabled = false; } + Line() { p[0] = NULL; p[1] = NULL; disabled = false; } }; struct Path { QList<Point*> points; |