/ dashing.hh
dashing.hh
1 /* 2 Copyright (c) 2015 Jeff Epler 3 4 This software is provided 'as-is', without any express or implied 5 warranty. In no event will the authors be held liable for any damages 6 arising from the use of this software. 7 8 Permission is granted to anyone to use this software for any purpose, 9 including commercial applications, and to alter it and redistribute it 10 freely, subject to the following restrictions: 11 12 1. The origin of this software must not be misrepresented; you must not 13 claim that you wrote the original software. If you use this software 14 in a product, an acknowledgement in the product documentation would be 15 appreciated but is not required. 16 2. Altered source versions must be plainly marked as such, and must not be 17 misrepresented as being the original software. 18 3. This notice may not be removed or altered from any source distribution. 19 */ 20 21 #ifndef DASHING_H 22 #define DASHING_H 23 24 #include <cmath> 25 #include <cassert> 26 #include <vector> 27 #include <string> 28 #include <fstream> 29 #include <stdexcept> 30 #include <boost/algorithm/string/replace.hpp> 31 #include <boost/algorithm/string/trim.hpp> 32 33 namespace dashing 34 { 35 36 struct PSMatrix { 37 double a, b, c, d, e, f; 38 39 PSMatrix inverse() const; 40 double determinant() const { return a * d - b * c; } 41 }; 42 43 PSMatrix Translation(double x, double y); 44 PSMatrix Rotation(double theta); 45 PSMatrix XSkew(double xk); 46 PSMatrix YScale(double ys); 47 48 struct Point { double x, y; }; 49 inline Point operator*(const Point &p, const PSMatrix &m) { 50 return Point{ p.x*m.a + p.y*m.c + m.e, 51 p.x*m.b + p.y*m.d + m.f }; 52 } 53 inline Point operator*(const Point &p, double d) 54 { 55 return Point{ p.x * d, p.y * d }; 56 } 57 inline Point operator*(double d, const Point &p) 58 { 59 return Point{ p.x * d, p.y * d }; 60 } 61 inline Point operator+(const Point &p, const Point &q) 62 { 63 return Point{ p.x + q.x, p.y * q.y }; 64 } 65 66 PSMatrix operator*(const PSMatrix &m1, const PSMatrix m2); 67 68 struct Dash { 69 PSMatrix tr, tf; 70 std::vector<double> dash, sum; 71 72 Dash(double th, double x0, double y0, double dx, double dy, 73 const std::vector<double>::const_iterator dbegin, 74 const std::vector<double>::const_iterator dend); 75 76 static Dash FromString(const std::string &line, double scale); 77 }; 78 79 struct Segment { Point p, q; bool swapped; }; 80 struct Intersection { double u; bool positive; }; 81 inline bool operator<(const Intersection &a, const Intersection &b) 82 { 83 return a.u < b.u; 84 } 85 86 // "sort" a segment so that its first component has the lower y-value 87 inline void ysort(Segment &s) { 88 if(s.p.y < s.q.y) return; 89 s.swapped = ! s.swapped; 90 std::swap(s.p, s.q); 91 } 92 93 inline double intceil(double x) { return int(ceil(x)); } 94 inline double intfloor(double x) { return int(floor(x)); } 95 96 inline double pythonmod(double a, double b) { 97 auto r = a - floor(a / b) * b; 98 if(r == b) return 0; 99 return r; 100 } 101 102 inline size_t utoidx(const Dash &d, double u, double &o) { 103 u = pythonmod(u, d.sum.back()); 104 for(size_t i = 1; i != d.sum.size(); i++) { 105 if(u < d.sum[i]) { o = u - d.sum[i-1]; return i-1; } 106 } 107 abort(); // should be unreachable 108 } 109 110 template<class Cb> 111 void uvdraw(const Dash &pattern, double v, double u1, double u2, Cb cb) { 112 if(pattern.dash.empty()) { cb(v, u1, u2); return; } 113 double o; 114 auto i = utoidx(pattern, u1, o); 115 const auto &pi = pattern.dash[i]; 116 if(pi >= 0) { cb(v, u1, std::min(u2, u1+pi-o)); u1 += pi-o; } 117 else { u1 -= pi+o; } 118 i = i + 1; 119 if(i == pattern.dash.size()) i = 0; 120 for(auto u = u1; u < u2;) { 121 const auto &pi = pattern.dash[i]; 122 if(pi >= 0) { cb(v, u, std::min(u2, u+pi)); u += pi; } 123 else { u -= pi; } 124 i = i + 1; 125 if(i == pattern.dash.size()) i = 0; 126 } 127 } 128 129 template<class Cb, class Wr> 130 void uvspans(const Dash &pattern, std::vector<Segment> && segments, Cb cb, std::vector<Intersection> &uu, Wr wr) { 131 if(segments.empty()) return; // no segments 132 133 for(auto &s : segments) ysort(s); 134 std::sort(segments.begin(), segments.end(), 135 [](const Segment &a, const Segment &b) { 136 return a.p.y < b.p.y; // sort in increasing p.y 137 }); 138 139 // we want to maintain the heap condition in such a way that we can always 140 // quickly pop items that our span has moved past. 141 // C++ heaps are max-heaps, so we need a decreasing sort. 142 auto heapcmp = [](const Segment &a, const Segment &b) { 143 return b.q.y < a.q.y; // sort in decreasing q.y; 144 }; 145 146 auto segments_begin = segments.begin(); 147 auto heap_begin = segments.begin(), heap_end = segments.begin(); 148 149 auto vstart = intfloor(segments.front().p.y); 150 auto vend = intceil(std::max_element(segments.begin(), segments.end(), 151 [](const Segment &a, const Segment &b) { 152 return a.q.y < b.q.y; // sort in increasing q.y; 153 })->q.y); 154 155 // sweep-line algorithm to intersects spans with segments 156 // "active" holds segments that may intersect with this span; 157 // when v moves below an active segment, drop it from the active heap. 158 // when v moves into a remaining segment, move it from segments to active. 159 for(auto v = vstart; v != vend; v++) { 160 uu.clear(); 161 162 while(heap_begin != heap_end && heap_begin->q.y < v) 163 { 164 std::pop_heap(heap_begin, heap_end, heapcmp); 165 heap_end --; 166 } 167 while(segments_begin != segments.end() && segments_begin->p.y < v) { 168 const auto &s = *segments_begin; 169 if(s.q.y >= v) { 170 *heap_end++ = s; 171 std::push_heap(heap_begin, heap_end, heapcmp); 172 } 173 segments_begin ++; 174 } 175 176 for(const auto &s : boost::make_iterator_range(heap_begin, heap_end)) { 177 auto du = s.q.x - s.p.x; 178 auto dv = s.q.y - s.p.y; 179 assert(dv); 180 if(dv) uu.push_back( 181 Intersection{s.p.x + du * (v - s.p.y) / dv,s.swapped}); 182 } 183 std::sort(uu.begin(), uu.end()); 184 int winding = 0; 185 double old_u = -std::numeric_limits<double>::infinity(); 186 for(const auto &isect : uu) { 187 if(wr(winding)) uvdraw(pattern, v, old_u, isect.u, cb); 188 winding += 2*isect.positive - 1; 189 old_u = isect.u; 190 } 191 } 192 } 193 194 struct HatchPattern { 195 std::vector<Dash> d; 196 static HatchPattern FromFile(std::istream &fi, double scale) { 197 HatchPattern result; 198 199 std::string line; 200 while(getline(fi, line)) { 201 auto i = line.find(";"); 202 if(i != line.npos) line.erase(i, line.npos); 203 boost::algorithm::trim(line); 204 if(line.empty()) continue; 205 if(line[0] == '*') continue; 206 result.d.push_back(Dash::FromString(line, scale)); 207 } 208 return result; 209 } 210 211 static HatchPattern FromFile(const char *filename, double scale) { 212 std::ifstream fi(filename); 213 return FromFile(fi, scale); 214 } 215 }; 216 217 template<class It, class Cb, class Wr> 218 void xyhatch(const Dash &pattern, It start, It end, Cb cb, std::vector<Segment> &uvsegments, std::vector<Intersection> &uu, Wr wr) { 219 uvsegments.clear(); 220 bool swapped = pattern.tf.determinant() < 0; 221 std::transform(start, end, std::back_inserter(uvsegments), 222 [&](const Segment &s) 223 { return Segment{s.p * pattern.tf, s.q * pattern.tf, swapped != s.swapped }; 224 }); 225 uvspans(pattern, std::move(uvsegments), [&](double v, double u1, double u2) { 226 Point p{u1, v}, q{u2, v}; 227 Segment xy{ p * pattern.tr, q * pattern.tr, false }; 228 cb(xy); 229 }, uu, wr); 230 } 231 232 template<class It, class Cb, class Wr> 233 void xyhatch(const HatchPattern &pattern, It start, It end, Cb cb, Wr wr) { 234 std::vector<Segment> uvsegments; 235 uvsegments.reserve(end-start); 236 std::vector<Intersection> uu; 237 uu.reserve(8); 238 for(const auto &i : pattern.d) xyhatch(i, start, end, cb, uvsegments, uu, wr); 239 } 240 241 template<class C, class Cb, class Wr> 242 void xyhatch(const HatchPattern &pattern, const C &c, Cb cb, Wr wr) { 243 xyhatch(pattern, c.begin(), c.end(), cb, wr); 244 } 245 246 } 247 #endif