diff options
Diffstat (limited to 'src/2geom/shape.cpp')
| -rw-r--r-- | src/2geom/shape.cpp | 492 |
1 files changed, 341 insertions, 151 deletions
diff --git a/src/2geom/shape.cpp b/src/2geom/shape.cpp index 670792521..54218d4d9 100644 --- a/src/2geom/shape.cpp +++ b/src/2geom/shape.cpp @@ -1,23 +1,39 @@ #include "shape.h" #include "utils.h" #include "sweep.h" +#include "ord.h" #include <iostream> #include <algorithm> +#include <cstdlib> namespace Geom { -// Utility funcs - -// Yes, xor is !=, but I'm pretty sure this is safer in the event of strange bools -bool logical_xor (bool a, bool b) { return (a || b) && !(a && b); } - // A little sugar for appending a list to another template<typename T> void append(T &a, T const &b) { a.insert(a.end(), b.begin(), b.end()); } +//Orders a list of indices according to their containment within eachother. +struct ContainmentOrder { + std::vector<Region> const *rs; + explicit ContainmentOrder(std::vector<Region> const *r) : rs(r) {} + bool operator()(unsigned a, unsigned b) const { return (*rs)[b].contains((*rs)[a]); } +}; + +//Returns the list of regions containing a particular point. Useful in tandem with ContainmentOrder +std::vector<unsigned> Shape::containment_list(Point p) const { + std::vector<Rect> pnt; + pnt.push_back(Rect(p, p)); + std::vector<std::vector<unsigned> > cull = sweep_bounds(pnt, bounds(*this)); + std::vector<unsigned> containers; + if(cull[0].size() == 0) return containers; + for(unsigned i = 0; i < cull[0].size(); i++) + if(content[cull[0][i]].contains(p)) containers.push_back(cull[0][i]); + return containers; +} + /* Used within shape_boolean and related functions, as the name describes, finds the * first false within the list of lists of booleans. */ @@ -77,8 +93,6 @@ Shape shape_boolean(bool rev, Shape const & a, Shape const & b, CrossingSet cons for(unsigned i = 0; i < crs.size(); i++) visited.push_back(std::vector<bool>(crs[i].size(), false)); - //bool const exception = - //Traverse the crossings, creating chunks Regions chunks; while(true) { @@ -115,35 +129,32 @@ Shape shape_boolean(bool rev, Shape const & a, Shape const & b, CrossingSet cons //If true, then we are on the 'subtraction diagonal' bool const on_sub = logical_xor(a.fill, b.fill); - //If true, then the hole must be inside the other to be included - bool const a_mode = logical_xor(logical_xor(!rev, a.fill), on_sub), - b_mode = logical_xor(logical_xor(!rev, b.fill), on_sub); + //If true, outer paths are filled + bool const res_fill = rev ? (on_sub || (a.fill && b.fill)) : (a.fill && b.fill); //Handle unintersecting portions for(unsigned i = 0; i < crs.size(); i++) { if(crs[i].size() == 0) { - Region r(i < ac.size() ? ac[i] : bc[i - ac.size()]); - bool mode(i < ac.size() ? a_mode : b_mode); + bool env; + bool on_a = i < ac.size(); + Region const & r(on_a ? ac[i] : bc[i - ac.size()]); + Shape const & other(on_a ? b : a); - if(logical_xor(r.fill, i < ac.size() ? a.fill : b.fill)) { - //is an inner (fill is opposite the outside fill) - Point exemplar = r.boundary.initialPoint(); - Regions const & others = i < ac.size() ? bc : ac; - for(unsigned j = 0; j < others.size(); j++) { - if(others[j].contains(exemplar)) { - //contained in another - if(mode) chunks.push_back(r); - goto skip; - } - } + std::vector<unsigned> containers = other.containment_list(r.boundary.initialPoint()); + if(containers.empty()) { + //not included in any container, the environment fill is the opposite of the outer fill + env = !res_fill; + if(on_sub && logical_xor(other.fill, res_fill)) env = !env; //If on the subtractor, invert the environment fill + } else { + //environment fill is the same as the inner-most container + std::vector<unsigned>::iterator cit = std::min_element(containers.begin(), containers.end(), ContainmentOrder(&other.content)); + env = other[*cit].isFill(); } - //disjoint - if(!mode) chunks.push_back(r); - skip: (void)0; + if(!logical_xor(rev, env)) chunks.push_back(r); //When unioning, environment must be hole for inclusion, when intersecting, it must be filled } } - return Shape(chunks); + return Shape(chunks, res_fill); } // Just a convenience wrapper for shape_boolean, which handles the crossings @@ -176,8 +187,11 @@ Shape shape_boolean_rb(bool rev, Shape const &a, Shape const &b, CrossingSet con * to be specified as a logic table. This logic table is 4 bit-flags, which * correspond to the elements of the 'truth table' for a particular operation. * These flags are defined with the enums starting with BOOLOP_ . + * + * NOTE: currently doesn't work, as the CrossingSet reversal functions crash */ Shape boolop(Shape const &a, Shape const &b, unsigned flags, CrossingSet const &crs) { + throw NotImplemented(); flags &= 15; if(flags <= BOOLOP_UNION) { switch(flags) { @@ -194,6 +208,7 @@ Shape boolop(Shape const &a, Shape const &b, unsigned flags, CrossingSet const & case BOOLOP_UNION: return shape_boolean(false, a, b); } } else { + flags = ~flags & 15; switch(flags - BOOLOP_NEITHER) { case BOOLOP_SUBTRACT_A_B: return shape_boolean_ra(false, a, b, crs); case BOOLOP_SUBTRACT_B_A: return shape_boolean_rb(false, a, b, crs); @@ -203,7 +218,7 @@ Shape boolop(Shape const &a, Shape const &b, unsigned flags, CrossingSet const & return res; } } - return boolop(a, b, ~flags, crs).inverse(); + return boolop(a, b, flags, crs).inverse(); } return Shape(); } @@ -230,7 +245,8 @@ Shape boolop(Shape const &a, Shape const &b, unsigned flags) { case BOOLOP_UNION: return shape_boolean(false, a, b); } } else { - switch(flags - BOOLOP_NEITHER) { + flags = ~flags & 15; + switch(flags) { case BOOLOP_SUBTRACT_A_B: return shape_boolean(false, b, a.inverse()); case BOOLOP_SUBTRACT_B_A: return shape_boolean(false, a, b.inverse()); case BOOLOP_EXCLUSION: { @@ -239,150 +255,323 @@ Shape boolop(Shape const &a, Shape const &b, unsigned flags) { return res; } //return boolop(a, b, flags, crossings_between(a, b)); } - return boolop(a, b, ~flags).inverse(); + return boolop(a, b, flags).inverse(); } return Shape(); } - int paths_winding(std::vector<Path> const &ps, Point p) { - int ret; + int ret = 0; for(unsigned i = 0; i < ps.size(); i++) ret += winding(ps[i], p); return ret; } -std::vector<double> y_of_roots(std::vector<Path> const & ps, double x) { - std::vector<double> res; - for(unsigned i = 0; i < ps.size(); i++) { - std::vector<double> temp = ps[i].roots(x, X); - for(unsigned i = 0; i < temp.size(); i++) - res.push_back(ps[i].valueAt(temp[i], Y)); - } - std::sort(res.begin(), res.end()); - return res; -} - -struct Edge { - unsigned ix; - double from, to; - bool rev; - int wind; - Edge(unsigned i, double ft, double tt, bool r, unsigned w) : ix(i), from(ft), to(tt), rev(r), wind(w) {} - Edge(unsigned i, double ft, double tt, bool r, std::vector<Path> const &ps) : ix(i), from(ft), to(tt), rev(r) { - //TODO: get the edge wind data some other way - Point p = ps[i].pointAt(ft); - std::vector<double> rs = y_of_roots(ps, p[X]); - unsigned interv = std::lower_bound(rs.begin(), rs.end(), p[Y]) - rs.begin(); - wind = interv % 2; +void add_to_shape(Shape &s, Path const &p, bool fill) { + if(fill) + s.content.push_back(Region(p).asFill()); + else + s.content.push_back(Region(p).asHole()); +} + +int inner_winding(Path const & p, std::vector<Path> const &ps) { + Point pnt = p.initialPoint(); + return paths_winding(ps, pnt) - winding(p, pnt) + 1; +} + +double fudgerize(double d, bool rev) { + double ret = rev ? d - 0.01 : d + 0.01; + if(ret < 0) ret = 0; + return ret; +} + +unsigned pick_coincident(unsigned ix, unsigned jx, bool &rev, std::vector<Path> const &ps, CrossingSet const &crs) { + unsigned ex_jx = jx; + unsigned oix = crs[ix][jx].getOther(ix); + double otime = crs[ix][jx].getTime(oix); + Point cross_point = ps[oix].pointAt(otime), + along = ps[oix].pointAt(fudgerize(otime, rev)) - cross_point, + prev = -along; + bool ex_dir = rev; + for(unsigned k = jx; k < crs[ix].size(); k++) { + unsigned koix = crs[ix][k].getOther(ix); + if(koix == oix) { + if(!near(otime, crs[ix][k].getTime(oix))) break; + for(unsigned dir = 0; dir < 2; dir++) { + Point val = ps[ix].pointAt(fudgerize(crs[ix][k].getTime(ix), dir)) - cross_point; + Cmp to_prev = cmp(cross(val, prev), 0); + Cmp from_along = cmp(cross(along, val), 0); + Cmp c = cmp(from_along, to_prev); + if(c == EQUAL_TO && from_along == LESS_THAN) { + ex_jx = k; + prev = val; + ex_dir = dir; + } + } + } } - double initial() { return rev ? to : from; } - double final() { return rev ? from : to; } - void addTo(Path &res, std::vector<Path> const &ps) { - if(rev) { - Path p = ps[ix].portion(to, from).reverse(); - for(unsigned i = 0; i < p.size(); i++) - res.append(p[i]); - } else { - ps[ix].appendPortionTo(res, from, to); + rev = ex_dir; + return ex_jx; +} + +unsigned crossing_along(double t, unsigned ix, unsigned jx, bool dir, Crossings const & crs) { + Crossing cur = Crossing(t, t, ix, ix, false); + if(jx < crs.size()) { + double ct = crs[jx].getTime(ix); + if(t == ct) { + cur = crs[jx]; + if(cur.a == cur.b) { + if(jx+1 <= crs.size() && crs[jx+1].getOther(ix) == ix) return jx+1; + if(jx > 0 && crs[jx-1].getOther(ix) == ix) return jx-1; + } } } -}; + if(!dir) { + jx = std::upper_bound(crs.begin(), crs.end(), cur, CrossingOrder(ix)) - crs.begin(); + } else { + jx = std::lower_bound(crs.begin(), crs.end(), cur, CrossingOrder(ix)) - crs.begin(); + if(jx == 0) jx = crs.size() - 1; else jx--; + jx = std::lower_bound(crs.begin(), crs.end(), crs[jx], CrossingOrder(ix)) - crs.begin(); + } + if(jx >= crs.size()) jx = 0; + return jx; +} -typedef std::vector<Edge> Edges; +void crossing_dual(unsigned &i, unsigned &j, CrossingSet const & crs) { + Crossing cur = crs[i][j]; + i = cur.getOther(i); + std::cout << i << "\n"; + if(crs[i].empty()) + j = 0; + else + j = std::lower_bound(crs[i].begin(), crs[i].end(), cur, CrossingOrder(i)) - crs[i].begin(); +} -double point_cosine(Point a, Point b, Point c) { - Point db = b - a, dc = c - a; - return cross(db, dc) / (db.length() * dc.length()); +//locate a crossing on the outside, by casting a ray through the middle of the bbox +void outer_crossing(unsigned &ix, unsigned &jx, bool & dir, std::vector<Path> const & ps, CrossingSet const & crs) { + Rect bounds = ps[ix].boundsFast(); + double ry = bounds[Y].middle(); + double max_val = bounds.left(), max_t = 0; + ix = ps.size(); + for(unsigned i = 0; i < ps.size(); i++) { + if(!crs[i].empty()) { + std::vector<double> rts = ps[i].roots(ry, Y); + for(unsigned j = 0; j < rts.size(); j++) { + double val = ps[i].valueAt(rts[j], X); + if(val > max_val) { + ix = i; + max_val = val; + max_t = rts[j]; + } + } + } + } + if(ix != ps.size()) { + dir = ps[ix].valueAt(max_t + 0.01, Y) > + ps[ix].valueAt(max_t - 0.01, Y); + jx = crossing_along(max_t, ix, jx, dir, crs[ix]); + } } -//sanitize -Regions regionize_paths(std::vector<Path> const &ps, bool evenodd) { - CrossingSet crs = crossings_among(ps); +std::vector<Path> inner_sanitize(std::vector<Path> const & ps) { + CrossingSet crs(crossings_among(ps)); - Edges es; + Regions chunks; - for(unsigned i = 0; i < crs.size(); i++) { - for(unsigned j = 0; j < crs[i].size(); j++) { - Crossing cur = crs[i][j]; - int io = i, jo = j; + std::vector<bool> used_path(ps.size(), false); + std::vector<std::vector<bool> > visited; + for(unsigned i = 0; i < crs.size(); i++) + visited.push_back(std::vector<bool>(crs[i].size(), false)); + + std::vector<Path> result_paths; + + while(true) { + unsigned ix = 0, jx = 0; + bool dir = false; + + //find an outer crossing by trying various paths and checking if the crossings are used + for(; ix < crs.size(); ix++) { + //TODO: optimize so it doesn't unecessarily check stuff + bool cont = true; + for(unsigned j = 0; j < crs[ix].size(); j++) { + if(!visited[ix][j]) { cont = false; break; } + } + if(cont) continue; + unsigned rix = ix, rjx = jx; + outer_crossing(rix, rjx, dir, ps, crs); + if(rix >= crs.size() || visited[rix][rjx]) continue; + ix = rix; jx = rjx; + break; + } + if(ix == crs.size()) break; + crossing_dual(ix, jx, crs); + + dir = !dir; + + Path res; + do { + visited[ix][jx] = true; + //unsigned nix = ix, njx = jx; + //crossing_dual(nix, njx, crs); + //visited[nix][njx] = true; + unsigned fix = ix, fjx = jx; - jo++; - if(jo >= crs[io].size()) jo = 0; - //std::cout << io << ", " << jo << "\n"; - if(cur.a == i) - es.push_back(Edge(i, cur.ta, crs[io][jo].ta, false, ps)); - else - es.push_back(Edge(i, cur.tb, crs[io][jo].tb, false, ps)); + bool new_dir = dir; - jo-=2; - if(jo < 0) jo += crs[io].size(); - // std::cout << io << ", " << jo << "\n"; - if(cur.a == i) - es.push_back(Edge(i, crs[io][jo].ta, cur.ta, true, ps)); - else - es.push_back(Edge(i, crs[io][jo].tb, cur.tb, true, ps)); - } + jx = crossing_along(crs[ix][jx].getTime(ix), ix, jx, dir, crs[ix]); + if(crs[ix][jx].a != crs[ix][jx].b) crossing_dual(ix, jx, crs); else new_dir = !new_dir; + jx = pick_coincident(ix, jx, new_dir, ps, crs); + + //unsigned nix = ix, njx = jx; + //crossing_dual(nix, njx, crs); + + Crossing from = crs[fix][fjx], + to = crs[ix][jx]; + if(dir) { + // backwards + std::cout << "r" << ix << "[" << from.getTime(ix) << ", " << to.getTime(ix) << "]\n"; + Path p = ps[ix].portion(from.getTime(ix), to.getTime(ix)).reverse(); + for(unsigned i = 0; i < p.size(); i++) + res.append(p[i]); + } else { + // forwards + std::cout << "f" << ix << "[" << from.getTime(ix) << ", " << to.getTime(ix) << "]\n"; + ps[ix].appendPortionTo(res, from.getTime(ix), to.getTime(ix)); + } + dir = new_dir; + } while(!visited[ix][jx]); + std::cout << "added " << res.size() << "\n"; + result_paths.push_back(res); } - for(unsigned i = 0; i<crs.size(); i++) { - if(crs[i].empty()) { - es.push_back(Edge(i, 0, ps[i].size(), false, ps)); - es.push_back(Edge(i, ps[i].size(), 0, true, ps)); - } + for(unsigned i = 0; i < crs.size(); i++) { + if(crs[i].empty() && !used_path[i]) + result_paths.push_back(ps[i]); } - - Edges es2; - //filter - for(unsigned i = 0; i < es.size(); i++) { - if(true) //(evenodd && es[i].wind % 2 == 0) || (!evenodd && es[i].wind == 0)) - es2.push_back(es[i]); + return result_paths; +} + +Shape sanitize(std::vector<Path> const & ps) { + std::vector<Path> res; + for(unsigned i = 0; i < ps.size(); i++) { + append(res, inner_sanitize(std::vector<Path>(1, ps[i]))); + } + return stopgap_cleaner(res); +} + +/* WIP sanitizer: +unsigned pick_coincident(unsigned ix, unsigned jx, bool pref, bool &rev, std::vector<Path> const &ps, CrossingSet const &crs) { + unsigned ex_jx = jx; + unsigned oix = crs[ix][jx].getOther(ix); + double otime = crs[ix][jx].getTime(oix); + Point cross_point = ps[oix].pointAt(otime), + along = ps[oix].pointAt(otime + (rev ? -0.01 : 0.01)) - cross_point, + prev = -along; + bool ex_dir = rev; + for(unsigned k = jx; k < crs[ix].size(); k++) { + unsigned koix = crs[ix][k].getOther(ix); + if(koix == oix) { + if(!near(otime, crs[ix][k].getTime(oix))) break; + for(unsigned dir = 0; dir < 2; dir++) { + Point val = ps[ix].pointAt(crs[ix][k].getTime(ix) + (dir ? -0.01 : 0.01)) - cross_point; + Cmp to_prev = cmp(cross(val, prev), 0); + Cmp from_along = cmp(cross(along, val), 0); + Cmp c = cmp(from_along, to_prev); + if(c == EQUAL_TO && (from_along == LESS_THAN) == pref) { + ex_jx = k; + prev = val; + ex_dir = dir; + } + } + } } - es = es2; + rev = ex_dir; + return ex_jx; +} + +unsigned corner_index(unsigned &i) { + div_t div_res = div(i, 4); + i = div_res.quot; + return div_res.rem; +} + +bool corner_direction(unsigned ix, unsigned jc, unsigned corner, CrossingSet const &crs) { + if(crs[ix][jc].a == ix) return corner > 1; else return corner %2 == 1; +} + +Shape sanitize(std::vector<Path> const & ps) { + CrossingSet crs = crossings_among(ps); - std::cout << es.size() << " edges\n"; + //Keep track of which CORNERS we've hit. + // FF FR RF RR, first is A dir, second B dir + std::vector<std::vector<bool> > visited; + for(unsigned i = 0; i < crs.size(); i++) + visited.push_back(std::vector<bool>(crs[i].size()*4, false)); Regions chunks; - for(unsigned i = 0; i < es.size(); i++) { - Edge cur = es[i]; - if(cur.rev) - chunks.push_back(Region(ps[cur.ix].portion(cur.from, cur.to).reverse(), cur.wind % 2 != 0)); - else - chunks.push_back(Region(ps[cur.ix].portion(cur.from, cur.to), cur.wind % 2 != 0)); - } - return chunks; - - //Regions chunks; - std::vector<bool> used(es2.size(), false); while(true) { - unsigned i = std::find(used.begin(), used.end(), false) - used.begin(); - if(i == used.size()) break; + unsigned i, j; + first_false(visited, i, j); + unsigned corner = corner_index(j); + + if(i == visited.size()) break; + + bool dir = corner_direction(i, j, corner, crs); + + //Figure out whether we hug the path cw or ccw, based on the orientation of the initial corner: + unsigned oix = crs[i][j].getOther(i); + double otime = crs[i][j].getTime(oix); + bool odir = (oix == crs[i][j].a) ? corner > 1 : corner % 2 == 1; + Point cross_point = ps[oix].pointAt(otime), + along = ps[oix].pointAt(otime + (odir ? -0.01 : 0.01)) - cross_point, + val = ps[i].pointAt(crs[i][j].getTime(i) + (dir ? -0.01 : 0.01)) - cross_point; + + Cmp from_along = cmp(cross(along, val), 0); + bool cw = from_along == LESS_THAN; + std::cout << "cw = " << cw << "\n"; Path res; do { - es2[i].addTo(res, ps); - Point pnt = res.finalPoint(); - std::vector<unsigned> poss; - for(unsigned j = 0; j < es2.size(); j++) - if(near(pnt, ps[es2[j].ix].pointAt(es2[j].initial()))) poss.push_back(j); - if(poss.empty()) break; - unsigned best = 0; - if(poss.size() > 1) { - double crossval = 10; - Point along = ps[i].pointAt(es2[i].final()+0.1); - for(unsigned j = 0; j < poss.size(); j++) { - unsigned ix = poss[j]; - double val = point_cosine(pnt, along, ps[ix].pointAt(es2[ix].initial()+.01)); - if(val < crossval) { - crossval = val; - best = j; - } - } + Crossing cur = crs[i][j]; + visited[i][j*4+corner] = true; + + unsigned fix = i, fjx = j; + crossing_dual(i, j, crs); + visited[i][j*4+corner] = true; + i = fix; j = fjx; + + j = crossing_along(crs[i][j].getTime(i), i, j, dir, crs[i]); + + crossing_dual(i, j, crs); + + bool new_dir = dir; + pick_coincident(i, j, cw, new_dir, ps, crs); + + Crossing from = crs[fix][fjx], + to = crs[i][j]; + if(dir) { + // backwards + std::cout << "r" << i << "[" << to.getTime(i) << ", " << from.getTime(i) << "]\n"; + Path p = ps[i].portion(to.getTime(i) + 0.001, from.getTime(i)).reverse(); + for(unsigned k = 0; k < p.size(); k++) + res.append(p[k]); + } else { + // forwards + std::cout << "f" << i << "[" << from.getTime(i) << ", " << to.getTime(i) << "]\n"; + ps[i].appendPortionTo(res, from.getTime(i) + 0.001, to.getTime(i)); } - i = poss[best]; - } while(!used[i]); + if(i == to.a) + corner = (new_dir ? 2 : 0) + (dir ? 1 : 0); + else + corner = (new_dir ? 1 : 0) + (dir ? 2 : 0); + dir = new_dir; + } while(!visited[i][j*4+corner]); chunks.push_back(Region(res)); +// if(use) { +// chunks.push_back(Region(res, true)); +// } } - return chunks; -} + return Shape(chunks); +// return ret; +} */ /* This transforms a shape by a matrix. In the case that the matrix flips * the shape, it reverses the paths in order to preserve the fill. @@ -404,18 +593,19 @@ Shape Shape::inverse() const { return ret; } -struct ContainmentOrder { - std::vector<Region> const *rs; - explicit ContainmentOrder(std::vector<Region> const *r) : rs(r) {} - bool operator()(unsigned a, unsigned b) const { return (*rs)[b].contains((*rs)[a]); } -}; - bool Shape::contains(Point const &p) const { - std::vector<Rect> pnt; - pnt.push_back(Rect(p, p)); - std::vector<std::vector<unsigned> > cull = sweep_bounds(pnt, bounds(*this)); - if(cull[0].size() == 0) return !fill; - return content[*min_element(cull[0].begin(), cull[0].end(), ContainmentOrder(&content))].isFill(); + std::vector<unsigned> containers = containment_list(p); + if(containers.empty()) return !isFill(); + unsigned ix = *min_element(containers.begin(), containers.end(), ContainmentOrder(&content)); + return content[ix].isFill(); +} + +Shape stopgap_cleaner(std::vector<Path> const &ps) { + if(ps.empty()) return Shape(false); + Shape ret; + for(unsigned i = 0; i < ps.size(); i++) + add_to_shape(ret, ps[i], inner_winding(ps[i], ps) % 2 != 0); + return ret; } bool Shape::inside_invariants() const { //semi-slow & easy to violate |