1
2
3 #include "tl2lautocloser.h"
4
5 #include "tgl.h"
6 #include "tenv.h"
7 #include "tvectorimage.h"
8 #include "tstroke.h"
9
10 #include <QDebug>
11
12 TEnv::DoubleVar VectorCloseValue("VectorCloseValue", 5);
13
14 //=============================================================================
15 #ifdef _WIN32
16
17 class MyTimer {
18 bool m_enabled;
19 LARGE_INTEGER m_freq;
20 LARGE_INTEGER m_startTime, m_overhead;
21
22 public:
MyTimer()23 MyTimer() : m_enabled(false) {
24 if (QueryPerformanceFrequency(&m_freq)) {
25 m_enabled = true;
26 LARGE_INTEGER curTime;
27 QueryPerformanceCounter(&m_startTime);
28 QueryPerformanceCounter(&curTime);
29 m_overhead.QuadPart = curTime.QuadPart - m_startTime.QuadPart;
30 }
31 }
32
start()33 void start() {
34 if (!m_enabled) return;
35 QueryPerformanceCounter(&m_startTime);
36 }
37
elapsedSeconds()38 double elapsedSeconds() {
39 LARGE_INTEGER curTime;
40 QueryPerformanceCounter(&curTime);
41 LONGLONG microseconds = 1000000 * (curTime.QuadPart - m_startTime.QuadPart -
42 m_overhead.QuadPart) /
43 m_freq.QuadPart;
44 return 0.000001 * (double)microseconds;
45 }
46 };
47 #endif
48
49 //=============================================================================
50
51 namespace {
52
53 // find the stroke curvature at w
54 // cfr. http://en.wikipedia.org/wiki/Curvature
getCurvature(TStroke * stroke,double w)55 TPointD getCurvature(TStroke *stroke, double w) {
56 const double h = 0.0001;
57 double w0 = std::max(0.0, w - h);
58 double w1 = std::min(1.0, w + h);
59 TPointD p0 = stroke->getPoint(w0);
60 TPointD p1 = stroke->getPoint(w1);
61 double ds = norm(p0 - p1);
62 double f = (w1 - w0) / ds;
63
64 TPointD d = stroke->getSpeed(w) * f;
65 TPointD d0 = stroke->getSpeed(w0) * f;
66 TPointD d1 = stroke->getSpeed(w1) * f;
67 TPointD dd = (d1 - d0) * (1.0 / ds);
68
69 double c = (d.x * dd.y - d.y * dd.x) / pow(d.x * d.x + d.y * d.y, 1.5);
70 TPointD crv = normalize(rotate90(d)) * c;
71
72 return crv;
73 }
74
75 //===========================================================================
76
77 //
78 // A point along a stroke: ths stroke itself, pos, w,s, crv
79 //
80 struct StrokePoint {
81 double w, s;
82 TPointD pos, crv, crvdir; // crvdir is crv normalized (or 0)
83 TPointD tgdir; // tgdir is the normalized tangent
84 TStroke *stroke;
StrokePoint__anondca71ed60111::StrokePoint85 StrokePoint(TStroke *stroke_, double s_)
86 : stroke(stroke_), w(stroke_->getParameterAtLength(s_)), s(s_) {
87 pos = stroke->getPoint(w);
88 crv = getCurvature(stroke, w);
89 double c = norm(crv);
90 if (c > 0)
91 crvdir = crv * (1.0 / c);
92 else
93 crvdir = TPointD();
94 tgdir = stroke->getSpeed(w);
95 double tgdirNorm = norm(tgdir);
96 if (tgdirNorm > 0.000001)
97 tgdir = tgdir * (1.0 / tgdirNorm);
98 else
99 tgdir = TPointD(0, 0);
100 }
StrokePoint__anondca71ed60111::StrokePoint101 StrokePoint() : w(0), s(0), pos(), crv(), crvdir(), stroke(0) {}
102 };
103
104 //===========================================================================
105
106 // a set of StrokePoint evenly spaced along the whole stroke
107 // (curvilinear distance between two adjacent point is "inc")
108 struct StrokePointSet {
109 TStroke *stroke;
110 std::vector<StrokePoint> points;
StrokePointSet__anondca71ed60111::StrokePointSet111 StrokePointSet(TStroke *stroke_ = 0) : stroke(stroke_) {
112 const double inc = VectorCloseValue;
113 if (stroke_) {
114 double length = stroke->getLength();
115 double s = 0;
116 if (stroke->isSelfLoop()) length -= inc;
117 while (s < length) {
118 points.push_back(StrokePoint(stroke, s));
119 s += inc;
120 }
121 }
122 }
123 };
124
125 //===========================================================================
126
127 class StrokesIntersection {
128 public:
129 std::vector<double> m_ida, m_idb; // distances to the closest intersection
130 // (referred to StrokePointSet)
131
StrokesIntersection()132 StrokesIntersection() {}
133 StrokesIntersection(const StrokePointSet &psa, const StrokePointSet &psb,
134 const std::vector<DoublePair> *intersection);
135
~StrokesIntersection()136 ~StrokesIntersection() {}
137
138 void update(const StrokePointSet &psa, const StrokePointSet &psb,
139 const std::vector<DoublePair> &intersections);
140
141 static void wrap(std::vector<double> &is, TStroke *stroke);
142
143 static void computeIntersectionDistances(std::vector<double> &id,
144 const StrokePointSet &ps,
145 const std::vector<double> &is);
146
swapped() const147 StrokesIntersection *swapped() const {
148 StrokesIntersection *s = new StrokesIntersection();
149 s->m_ida = m_idb;
150 s->m_idb = m_ida;
151 return s;
152 }
153 };
154
155 //---------------------------------------------------------------------------
156
StrokesIntersection(const StrokePointSet & psa,const StrokePointSet & psb,const std::vector<DoublePair> * intersections)157 StrokesIntersection::StrokesIntersection(
158 const StrokePointSet &psa, const StrokePointSet &psb,
159 const std::vector<DoublePair> *intersections) {
160 if (!psa.stroke || !psb.stroke) return; // it should never happen
161 std::vector<DoublePair> myIntersections;
162 if (!intersections) {
163 intersections = &myIntersections;
164 intersect(psa.stroke, psb.stroke, myIntersections);
165 }
166 update(psa, psb, *intersections);
167 }
168
169 //---------------------------------------------------------------------------
170
update(const StrokePointSet & psa,const StrokePointSet & psb,const std::vector<DoublePair> & intersections)171 void StrokesIntersection::update(const StrokePointSet &psa,
172 const StrokePointSet &psb,
173 const std::vector<DoublePair> &intersections) {
174 TStroke *strokea = psa.stroke;
175 TStroke *strokeb = psb.stroke;
176 m_ida.clear();
177 m_idb.clear();
178
179 if (!strokea || !strokeb) return; // it should never happen
180
181 m_ida.resize(psa.points.size(), -1);
182 m_idb.resize(psb.points.size(), -1);
183
184 int n = (int)intersections.size();
185 if (n <= 0) return;
186
187 // compute intersection arclengths
188 std::vector<double> isa(n), isb(n);
189 for (int i = 0; i < n; i++) {
190 isa[i] = strokea->getLength(intersections[i].first);
191 isb[i] = strokeb->getLength(intersections[i].second);
192 }
193
194 if (strokea == strokeb) {
195 // una sola stroke. ogni intersezione deve valere per due
196 isa.insert(isa.end(), isb.begin(), isb.end());
197 std::sort(isa.begin(), isa.end());
198 isb = isa;
199 } else {
200 // due stroke. ordino
201 std::sort(isa.begin(), isa.end());
202 std::sort(isb.begin(), isb.end());
203 }
204 if (strokea->isSelfLoop() && !isa.empty()) wrap(isa, strokea);
205 if (strokeb->isSelfLoop() && !isb.empty()) wrap(isb, strokeb);
206 computeIntersectionDistances(m_ida, psa, isa);
207 computeIntersectionDistances(m_idb, psb, isb);
208 }
209
210 //---------------------------------------------------------------------------
211
212 // the stroke is a self loop. the last intersection is mirrored before s=0
213 // the first intersection is mirroed after s=length
wrap(std::vector<double> & is,TStroke * stroke)214 void StrokesIntersection::wrap(std::vector<double> &is, TStroke *stroke) {
215 assert(stroke->isSelfLoop());
216 if (!is.empty()) {
217 double length = stroke->getLength();
218 is.insert(is.begin(), is.back() - length);
219 is.push_back(is[1] + length);
220 }
221 }
222
223 //---------------------------------------------------------------------------
224
225 // for each StrokePoint computes the related intersection distance (i.e. the
226 // distance to
227 // the closest intersection)
computeIntersectionDistances(std::vector<double> & id,const StrokePointSet & ps,const std::vector<double> & is)228 void StrokesIntersection::computeIntersectionDistances(
229 std::vector<double> &id, const StrokePointSet &ps,
230 const std::vector<double> &is) {
231 id.clear();
232 id.resize(ps.points.size(), -1);
233 int isn = (int)is.size();
234 int k = 0;
235 for (int i = 0; i < (int)ps.points.size(); i++) {
236 double d = -1;
237 if (k < isn) {
238 double s = ps.points[i].s;
239 while (k + 1 < isn && is[k + 1] < s) k++;
240 if (is[k] > s)
241 d = is[k] - s;
242 else if (k + 1 < isn)
243 d = std::min(is[k + 1] - s, s - is[k]);
244 else
245 d = s - is[k];
246 }
247 id[i] = d;
248 }
249 }
250 //---------------------------------------------------------------------------
251
252 } // namespace
253
254 //=============================================================================
255
256 class TL2LAutocloser::Imp {
257 public:
258 double m_maxDist2;
259 std::map<TStroke *, StrokePointSet *> m_strokes;
260 std::map<std::pair<TStroke *, TStroke *>, StrokesIntersection *>
261 m_intersections;
262
263 // debug
264 std::pair<StrokePointSet *, StrokePointSet *> m_lastStrokePair;
265 std::vector<TL2LAutocloser::Segment> m_segments;
266
Imp()267 Imp()
268 : m_maxDist2(50 * 50)
269 , m_lastStrokePair((StrokePointSet *)0, (StrokePointSet *)0) {}
270 ~Imp();
271
getPointSet(TStroke * stroke)272 StrokePointSet *getPointSet(TStroke *stroke) {
273 std::map<TStroke *, StrokePointSet *>::iterator it = m_strokes.find(stroke);
274 if (it != m_strokes.end()) return it->second;
275 StrokePointSet *ps = new StrokePointSet(stroke);
276 m_strokes[stroke] = ps;
277 return ps;
278 }
279
getIntersection(TStroke * strokea,TStroke * strokeb,const std::vector<DoublePair> * intersection)280 StrokesIntersection *getIntersection(
281 TStroke *strokea, TStroke *strokeb,
282 const std::vector<DoublePair> *intersection) {
283 std::map<std::pair<TStroke *, TStroke *>, StrokesIntersection *>::iterator
284 it = m_intersections.find(std::make_pair(strokea, strokeb));
285 if (it != m_intersections.end()) return it->second;
286 StrokesIntersection *si =
287 new StrokesIntersection(strokea, strokeb, intersection);
288 m_intersections[std::make_pair(strokea, strokeb)] = si;
289 m_intersections[std::make_pair(strokeb, strokea)] = si->swapped();
290 return si;
291 }
292
293 void search(std::vector<TL2LAutocloser::Segment> &segments, TStroke *strokea,
294 TStroke *strokeb, const std::vector<DoublePair> *intersection);
295
296 void drawLinks();
297 void drawStroke(StrokePointSet *);
298 void drawStrokes();
299 };
300
301 //-----------------------------------------------------------------------------
302
~Imp()303 TL2LAutocloser::Imp::~Imp() {
304 std::map<TStroke *, StrokePointSet *>::iterator i;
305 for (i = m_strokes.begin(); i != m_strokes.end(); ++i) delete i->second;
306 std::map<std::pair<TStroke *, TStroke *>, StrokesIntersection *>::iterator j;
307 for (j = m_intersections.begin(); j != m_intersections.end(); ++j)
308 delete j->second;
309 m_strokes.clear();
310 m_intersections.clear();
311 }
312
313 //-----------------------------------------------------------------------------
314
drawLinks()315 void TL2LAutocloser::Imp::drawLinks() {
316 glColor3d(0, 0, 1);
317 glBegin(GL_LINES);
318 for (int i = 0; i < (int)m_segments.size(); i++) {
319 tglVertex(m_segments[i].p0);
320 tglVertex(m_segments[i].p1);
321 }
322 glEnd();
323 }
324
drawStroke(StrokePointSet * ps)325 void TL2LAutocloser::Imp::drawStroke(StrokePointSet *ps) {
326 if (ps && ps->points.size() >= 2) {
327 glBegin(GL_LINES);
328 for (int i = 0; i < (int)ps->points.size(); i++)
329 tglVertex(ps->points[i].pos);
330 glEnd();
331 }
332 }
333
drawStrokes()334 void TL2LAutocloser::Imp::drawStrokes() {
335 if (m_lastStrokePair.first) {
336 if (m_lastStrokePair.first == m_lastStrokePair.second) {
337 glColor3d(1, 0, 1);
338 drawStroke(m_lastStrokePair.first);
339 } else {
340 glColor3d(1, 0, 0);
341 drawStroke(m_lastStrokePair.first);
342 glColor3d(0, 1, 0);
343 drawStroke(m_lastStrokePair.second);
344 }
345 }
346 }
347
348 //-----------------------------------------------------------------------------
349
350 // search autoclose segments
search(std::vector<TL2LAutocloser::Segment> & segments,TStroke * strokea,TStroke * strokeb,const std::vector<DoublePair> * intersections)351 void TL2LAutocloser::Imp::search(std::vector<TL2LAutocloser::Segment> &segments,
352 TStroke *strokea, TStroke *strokeb,
353 const std::vector<DoublePair> *intersections) {
354 m_lastStrokePair.first = m_lastStrokePair.second = 0;
355 if (strokea == 0 || strokeb == 0) return;
356 /*
357 #ifdef _WIN32
358 MyTimer timer;
359 qDebug() << "search started";
360 timer.start();
361 #endif
362 */
363 bool sameStroke = strokea == strokeb;
364
365 StrokePointSet *psa = getPointSet(strokea);
366 StrokePointSet *psb = sameStroke ? psa : getPointSet(strokeb);
367 m_lastStrokePair.first = psa;
368 m_lastStrokePair.second = psb;
369 StrokesIntersection *si = getIntersection(strokea, strokeb, intersections);
370
371 // find links (i.e. best matching point in psb for each point in psa)
372
373 std::vector<std::pair<int, int>> links;
374 int na = (int)psa->points.size();
375 int nb = (int)psb->points.size();
376 int i;
377 for (i = 0; i < na; i++) {
378 double minDist2 = 0;
379 int k = -1;
380
381 int j0 = 0;
382 if (sameStroke) j0 = i + 1;
383 for (int j = 0; j < nb; j++) {
384 TPointD delta = psb->points[j].pos - psa->points[i].pos;
385 double dist2 = norm2(delta);
386
387 if (dist2 > m_maxDist2) continue;
388 if (dist2 < 0.000001) continue;
389
390 double dist = sqrt(dist2);
391 delta = delta * (1.0 / dist);
392 double cs = 0.005;
393
394 if ((psa->points[i].crvdir * delta) > -cs) continue;
395 if ((psb->points[j].crvdir * delta) < cs) continue;
396
397 if (sameStroke) {
398 double ds = fabs(psa->points[i].s - psb->points[j].s);
399 if (ds < dist * 1.5) continue;
400 }
401 if ((si->m_ida[i] > 0 && si->m_ida[i] < dist) ||
402 (si->m_idb[j] > 0 && si->m_idb[j] < dist))
403 continue;
404 if (k < 0 || dist2 < minDist2) {
405 k = j;
406 minDist2 = dist2;
407 }
408 }
409 if (k >= 0 && (!sameStroke || k > i) && (0 < i && i < na - 1) &&
410 (0 < k && k < nb - 1)) {
411 links.push_back(std::make_pair(i, k));
412 }
413 }
414
415 /*
416 for(i=0;i<(int)links.size();i++)
417 {
418 int ia = links[i].first;
419 int ib = links[i].second;
420 double mind2 = norm2(psa->points[ia].pos - psb->points[ib].pos);
421 TL2LAutocloser::Segment segment;
422 segment.stroke0 = strokea;
423 segment.stroke1 = strokeb;
424 segment.w0 = psa->points[ia].w;
425 segment.w1 = psb->points[ib].w;
426 segment.p0 = strokea->getThickPoint(segment.w0);
427 segment.p1 = strokeb->getThickPoint(segment.w1);
428 segment.dist2 = mind2;
429 segments.push_back(segment);
430 }
431 */
432
433 // select best links
434 for (i = 0; i < (int)links.size(); i++) {
435 int ia = links[i].first;
436 int ib = links[i].second;
437 double d2 = norm2(psa->points[ia].pos - psb->points[ib].pos);
438 double mind2 = d2;
439 int k = i;
440 while (i + 1 < (int)links.size()) {
441 int ia2 = links[i + 1].first;
442 int ib2 = links[i + 1].second;
443 double d22 = norm2(psa->points[ia2].pos - psb->points[ib2].pos);
444 double d2m = (d2 + d22) * 0.5;
445 double dsa = psa->points[ia2].s - psa->points[ia].s;
446 double dsb = psb->points[ib2].s - psb->points[ib].s;
447 if (dsa * dsa > d2m || dsb * dsb > d2m) break;
448 if (d22 < mind2) {
449 mind2 = d22;
450 k = i + 1;
451 }
452 ia = ia2;
453 ib = ib2;
454 d2 = d22;
455 i++;
456 }
457 ia = links[k].first;
458 ib = links[k].second;
459 TL2LAutocloser::Segment segment;
460 segment.stroke0 = strokea;
461 segment.stroke1 = strokeb;
462 segment.w0 = psa->points[ia].w;
463 segment.w1 = psb->points[ib].w;
464 segment.p0 = strokea->getThickPoint(segment.w0);
465 segment.p1 = strokeb->getThickPoint(segment.w1);
466 segment.dist2 = mind2;
467 segments.push_back(segment);
468 }
469 /*
470 #ifdef _WIN32
471 double elapsed = timer.elapsedSeconds();
472 qDebug() << "search completed. time=" << elapsed << "s";
473 #endif
474 */
475 }
476
477 //=============================================================================
478
TL2LAutocloser()479 TL2LAutocloser::TL2LAutocloser() : m_imp(new Imp()) {}
480
481 //-----------------------------------------------------------------------------
482
~TL2LAutocloser()483 TL2LAutocloser::~TL2LAutocloser() {}
484
485 //-----------------------------------------------------------------------------
486
setMaxDistance2(double dist2)487 void TL2LAutocloser::setMaxDistance2(double dist2) {
488 m_imp->m_maxDist2 = dist2;
489 }
490
491 //-----------------------------------------------------------------------------
492
getMaxDistance2() const493 double TL2LAutocloser::getMaxDistance2() const { return m_imp->m_maxDist2; }
494
495 //-----------------------------------------------------------------------------
496
search(std::vector<Segment> & segments,TStroke * stroke0,TStroke * stroke1)497 void TL2LAutocloser::search(std::vector<Segment> &segments, TStroke *stroke0,
498 TStroke *stroke1) {
499 if (stroke0 && stroke1) m_imp->search(segments, stroke0, stroke1, 0);
500 }
501
502 //-----------------------------------------------------------------------------
503
search(std::vector<Segment> & segments,TStroke * stroke0,TStroke * stroke1,const std::vector<DoublePair> & intersection)504 void TL2LAutocloser::search(std::vector<Segment> &segments, TStroke *stroke0,
505 TStroke *stroke1,
506 const std::vector<DoublePair> &intersection) {
507 if (stroke0 && stroke1)
508 m_imp->search(segments, stroke0, stroke1, &intersection);
509 }
510
511 //-----------------------------------------------------------------------------
512
draw()513 void TL2LAutocloser::draw() {
514 m_imp->drawStrokes();
515 m_imp->drawLinks();
516 }
517