1
2
3 #include "tinbetween.h"
4 #include "tcurves.h"
5 #include "tstroke.h"
6 #include "tpalette.h"
7 //#include "tcolorstyles.h"
8 //#include "tregion.h"
9 #include "tmathutil.h"
10 //#include "tstrokeutil.h"
11 //#include "tsystem.h"
12 #include <utility>
13 #include <limits>
14 #include <list>
15
16 #include "../tvectorimage/tvectorimageP.h"
17
18 //#include "tdebugmessage.h"
19 //--------------------------------------------------------------------------------------
20
average(std::vector<double> & values,double range=2.5)21 static double average(std::vector<double> &values, double range = 2.5) {
22 UINT size = values.size();
23 if (size == 0) return std::numeric_limits<double>::signaling_NaN();
24
25 if (size == 1) return values[0];
26
27 double sum = 0;
28 UINT j = 0;
29 for (; j < size; j++) {
30 sum += values[j];
31 }
32
33 double average = sum / size;
34
35 double variance = 0;
36 for (j = 0; j < size; j++) {
37 variance += (average - values[j]) * (average - values[j]);
38 }
39 variance /= size;
40
41 double err;
42 int acceptedNum = 0;
43 sum = 0;
44 for (j = 0; j < size; j++) {
45 err = values[j] - average;
46 err *= err;
47 if (err <= range * variance) {
48 sum += values[j];
49 acceptedNum++;
50 }
51 }
52
53 assert(acceptedNum > 0);
54 return (acceptedNum > 0) ? sum / (double)acceptedNum : average;
55 }
56
57 //--------------------------------------------------------------------------------------
58
weightedAverage(std::vector<double> & values,std::vector<double> & weights,double range=2.5)59 static double weightedAverage(std::vector<double> &values,
60 std::vector<double> &weights,
61 double range = 2.5) {
62 UINT size = values.size();
63 if (size == 0) return std::numeric_limits<double>::signaling_NaN();
64
65 double sum = 0;
66 double totalWeight = 0;
67 UINT j = 0;
68 for (; j < size; j++) {
69 sum += weights[j] * values[j];
70 totalWeight += weights[j];
71 }
72
73 assert(totalWeight > 0);
74 if (totalWeight == 0) return std::numeric_limits<double>::signaling_NaN();
75
76 double average = sum / totalWeight;
77
78 double variance = 0;
79 for (j = 0; j < size; j++) {
80 variance += weights[j] * (average - values[j]) * (average - values[j]);
81 }
82 variance /= totalWeight;
83
84 double err;
85 totalWeight = 0;
86 sum = 0;
87 for (j = 0; j < size; j++) {
88 err = values[j] - average;
89 err *= err;
90 if (err <= range * variance) {
91 sum += weights[j] * values[j];
92 totalWeight += weights[j];
93 }
94 }
95
96 assert(totalWeight > 0);
97 return (totalWeight != 0) ? sum / totalWeight : average;
98 }
99
100 //--------------------------------------------------------------------------------------
101
angleNumber(const std::vector<std::pair<int,double>> & corners,double angle)102 inline UINT angleNumber(const std::vector<std::pair<int, double>> &corners,
103 double angle) {
104 UINT count = 0;
105 UINT size = corners.size();
106 for (UINT j = 0; j < size; j++)
107 if (corners[j].second >= angle) count++;
108
109 return count;
110 }
111
112 //--------------------------------------------------------------------------------------
113
isTooComplex(UINT n1,UINT n2,UINT maxSubsetNumber=100)114 inline bool isTooComplex(UINT n1, UINT n2, UINT maxSubsetNumber = 100) {
115 UINT n, r;
116 if (n1 > n2) {
117 n = n1;
118 r = n2;
119 } else if (n1 < n2) {
120 n = n2;
121 r = n1;
122 } else {
123 assert(!"equal angle number");
124 return false;
125 }
126
127 if (n - r < r) r = n - r;
128
129 /*
130
131 n*(n-1)* ...(n-r+1) < n^r that must be <= 2^(num bits of UINT)-1
132
133 s:=sizeof(UINT)*8
134
135 if
136 n <= 2^( (s-1)/r) =>
137
138 log n <= (s-1)/r (the base of log is 2) =>
139
140 r*log n <= s-1 =>
141
142 log n^r <= log 2^(s-1) =>
143
144 n^r <= 2^(s-1) < (2^s)-1
145
146 */
147
148 const UINT one = 1;
149 if (n > (one << ((sizeof(UINT) * 8 - 1) / r))) return true;
150
151 UINT product1 = n; // product1 = n*(n-1)* ...(n-r+1)
152 for (UINT i = 1; i < r; i++) product1 *= --n;
153
154 UINT rFact = r;
155
156 while (r > 1) rFact *= --r;
157
158 return (product1 / rFact > maxSubsetNumber);
159 // product1/rFact is number of combination
160 // ( n )
161 // ( r )
162 }
163
164 //--------------------------------------------------------------------------------------
165
eraseSmallAngles(std::vector<std::pair<int,double>> & corners,double angle)166 static void eraseSmallAngles(std::vector<std::pair<int, double>> &corners,
167 double angle) {
168 std::vector<std::pair<int, double>>::iterator it = corners.begin();
169
170 while (it != corners.end()) {
171 if ((*it).second < angle)
172 it = corners.erase(it);
173 else
174 ++it;
175 }
176 }
177
178 //--------------------------------------------------------------------------------------
179 // output:
180 // min is the minimum angle greater or equal to minDegree (i.e the minimum angle
181 // of the corners)
182 // max is tha maximum angle greater or equal to minDegree
183
detectCorners(const TStroke * stroke,double minDegree,std::vector<std::pair<int,double>> & corners,double & min,double & max)184 static void detectCorners(const TStroke *stroke, double minDegree,
185 std::vector<std::pair<int, double>> &corners,
186 double &min, double &max) {
187 const double minSin = fabs(sin(minDegree * M_PI_180));
188 double angle, vectorialProduct, metaCornerLen, partialLen;
189
190 UINT quadCount1 = stroke->getChunkCount();
191 TPointD speed1, speed2;
192 int j;
193
194 TPointD tan1, tan2;
195 min = 180;
196 max = minDegree;
197 for (j = 1; j < (int)quadCount1; j++) {
198 speed1 = stroke->getChunk(j - 1)->getSpeed(1);
199 speed2 = stroke->getChunk(j)->getSpeed(0);
200 if (!(speed1 == TPointD() || speed2 == TPointD())) {
201 tan1 = normalize(speed1);
202 tan2 = normalize(speed2);
203
204 vectorialProduct = fabs(cross(tan1, tan2));
205
206 if (tan1 * tan2 < 0) {
207 angle = 180 - asin(tcrop(vectorialProduct, -1.0, 1.0)) * M_180_PI;
208 corners.push_back(std::make_pair(j, angle));
209
210 //------------------------------------------
211 // TDebugMessage::getStream()<<j<<" real angle";
212 // TDebugMessage::flush();
213 //------------------------------------------
214
215 if (min > angle) min = angle;
216 if (max < angle) max = angle;
217 } else if (vectorialProduct >= minSin) {
218 angle = asin(tcrop(vectorialProduct, -1.0, 1.0)) * M_180_PI;
219 corners.push_back(std::make_pair(j, angle));
220
221 //------------------------------------------
222 // TDebugMessage::getStream()<<j<<" real angle";
223 // TDebugMessage::flush();
224 //------------------------------------------
225
226 if (min > angle) min = angle;
227 if (max < angle) max = angle;
228 }
229 }
230 }
231
232 const double ratioLen = 2.5;
233 const double ratioAngle = 0.2;
234 std::vector<std::pair<int, double>>::iterator it = corners.begin();
235
236 for (j = 1; j < (int)quadCount1;
237 j++) //"meta angoli" ( meta perche' derivabili)
238 {
239 if (it != corners.end() && j == (*it).first) {
240 ++it;
241 continue;
242 }
243
244 if (j - 2 >= 0 &&
245 (corners.empty() || it == corners.begin() ||
246 j - 1 != (*(it - 1)).first) &&
247 j + 1 < (int)quadCount1 &&
248 (corners.empty() || it == corners.end() || j + 1 != (*it).first)) {
249 speed1 = stroke->getChunk(j - 2)->getSpeed(1);
250 speed2 = stroke->getChunk(j + 1)->getSpeed(0);
251 if (!(speed1 == TPointD() || speed2 == TPointD())) {
252 tan1 = normalize(speed1);
253 tan2 = normalize(speed2);
254 vectorialProduct = fabs(cross(tan1, tan2));
255
256 if (tan1 * tan2 < 0) {
257 angle = 180 - asin(tcrop(vectorialProduct, -1.0, 1.0)) * M_180_PI;
258
259 metaCornerLen = ratioLen * (stroke->getChunk(j - 1)->getLength() +
260 stroke->getChunk(j)->getLength());
261 partialLen = 0;
262 bool goodAngle = false;
263
264 for (int i = j - 3;
265 i >= 0 && (corners.empty() || it == corners.begin() ||
266 i + 1 != (*(it - 1)).first);
267 i--) {
268 tan1 = stroke->getChunk(i)->getSpeed(1);
269 if (tan1 == TPointD()) continue;
270 tan1 = normalize(tan1);
271
272 tan2 = stroke->getChunk(i + 1)->getSpeed(1);
273 if (tan2 == TPointD()) continue;
274 tan2 = normalize(tan2);
275
276 vectorialProduct = fabs(cross(tan1, tan2));
277 double nearAngle =
278 asin(tcrop(vectorialProduct, -1.0, 1.0)) * M_180_PI;
279 if (tan1 * tan2 < 0) nearAngle = 180 - nearAngle;
280
281 if (nearAngle > ratioAngle * angle) break;
282
283 partialLen += stroke->getChunk(i)->getLength();
284 if (partialLen > metaCornerLen) {
285 goodAngle = true;
286 break;
287 }
288 }
289 if (goodAngle) {
290 partialLen = 0;
291 for (int i = j + 2; i + 1 < (int)quadCount1 &&
292 (corners.empty() || it == corners.end() ||
293 i + 1 != (*it).first);
294 i++) {
295 tan1 = stroke->getChunk(i)->getSpeed(0);
296 if (tan1 == TPointD()) continue;
297 tan1 = normalize(tan1);
298
299 tan2 = stroke->getChunk(i + 1)->getSpeed(0);
300 if (tan2 == TPointD()) continue;
301 tan2 = normalize(tan2);
302
303 vectorialProduct = fabs(cross(tan1, tan2));
304 double nearAngle =
305 asin(tcrop(vectorialProduct, -1.0, 1.0)) * M_180_PI;
306 if (tan1 * tan2 < 0) nearAngle = 180 - nearAngle;
307
308 if (nearAngle > 0.1 * angle) break;
309
310 partialLen += stroke->getChunk(i)->getLength();
311 if (partialLen > metaCornerLen) {
312 goodAngle = true;
313 break;
314 }
315 }
316 }
317
318 if (goodAngle) {
319 // l'angolo viene un po' declassato in quanto meta
320 it = corners.insert(it, std::make_pair(j, angle * 0.7)) + 1;
321 if (min > angle) min = angle;
322 if (max < angle) max = angle;
323
324 // TDebugMessage::getStream()<<j<<" meta angle";
325 // TDebugMessage::flush();
326 }
327 }
328 }
329 }
330 }
331 }
332
333 //--------------------------------------------------------------------------------------
334
variance(std::vector<double> & values)335 static double variance(std::vector<double> &values) {
336 UINT size = values.size();
337 if (size == 0) return std::numeric_limits<double>::signaling_NaN();
338
339 double sum = 0;
340 UINT j = 0;
341 for (; j < size; j++) {
342 sum += values[j];
343 }
344
345 double average = sum / size;
346
347 double variance = 0;
348 for (j = 0; j < size; j++) {
349 variance += (average - values[j]) * (average - values[j]);
350 }
351
352 return variance / size;
353 }
354
355 //--------------------------------------------------------------------------------------
356
findBestSolution(const TStroke * stroke1,const TStroke * stroke2,std::pair<int,double> * partialAngles1,UINT partialAngles1Size,const std::vector<std::pair<int,double>> & angles2,UINT r,std::list<std::pair<int,double>> & partialSolution,double & bestValue,std::vector<int> & bestVector)357 static void findBestSolution(const TStroke *stroke1, const TStroke *stroke2,
358 std::pair<int, double> *partialAngles1,
359 UINT partialAngles1Size,
360 const std::vector<std::pair<int, double>> &angles2,
361 UINT r,
362 std::list<std::pair<int, double>> &partialSolution,
363 double &bestValue, std::vector<int> &bestVector) {
364 //-------------------------------------------------------------------
365 if (r == partialAngles1Size) {
366 UINT j;
367 std::vector<std::pair<int, double>> angles1;
368
369 std::list<std::pair<int, double>>::iterator it = partialSolution.begin();
370
371 for (; it != partialSolution.end(); ++it) {
372 angles1.push_back(*it);
373 }
374 for (j = 0; j < partialAngles1Size; j++) {
375 angles1.push_back(partialAngles1[j]);
376 }
377
378 UINT angles1Size = angles1.size();
379 std::vector<double> rationAngles(angles1Size), ratioLength(angles1Size + 1);
380 std::vector<double> ratioX, ratioY;
381
382 for (j = 0; j < angles1Size; j++) {
383 rationAngles[j] = fabs(angles1[j].second - angles2[j].second) /
384 (angles1[j].second + angles2[j].second);
385 }
386
387 UINT firstQuad1 = 0;
388 UINT firstQuad2 = 0;
389 UINT nextQuad1, nextQuad2;
390
391 TRectD bbox1 = stroke1->getBBox();
392 TRectD bbox2 = stroke2->getBBox();
393
394 double app, div;
395 double invTotalLen1 = stroke1->getLength();
396 assert(invTotalLen1 > 0);
397 invTotalLen1 = 1.0 / invTotalLen1;
398
399 double invTotalLen2 = stroke2->getLength();
400 assert(invTotalLen2 > 0);
401 invTotalLen2 = 1.0 / invTotalLen2;
402
403 for (j = 0; j <= angles1Size; j++) {
404 if (j < angles1Size) {
405 nextQuad1 = angles1[j].first;
406 nextQuad2 = angles2[j].first;
407 } else {
408 nextQuad1 = stroke1->getChunkCount();
409 nextQuad2 = stroke2->getChunkCount();
410 }
411
412 ratioLength[j] =
413 fabs(stroke1->getLengthAtControlPoint(nextQuad1 * 2) * invTotalLen1 -
414 stroke2->getLengthAtControlPoint(nextQuad2 * 2) * invTotalLen2);
415
416 TPointD p1(stroke1->getChunk(nextQuad1 - 1)->getP2() -
417 stroke1->getChunk(firstQuad1)->getP0());
418 p1.x = fabs(p1.x);
419 p1.y = fabs(p1.y);
420
421 TPointD p2(stroke2->getChunk(nextQuad2 - 1)->getP2() -
422 stroke2->getChunk(firstQuad2)->getP0());
423 p2.x = fabs(p2.x);
424 p2.y = fabs(p2.y);
425
426 app = fabs(bbox1.getLx() * p2.x - bbox2.getLx() * p1.x);
427 div = (bbox1.getLx() * p2.x + bbox2.getLx() * p1.x);
428 if (div) ratioX.push_back(app / div);
429
430 app = fabs(bbox1.getLy() * p2.y - bbox2.getLy() * p1.y);
431 div = (bbox1.getLy() * p2.y + bbox2.getLy() * p1.y);
432 if (div) ratioY.push_back(app / div);
433
434 firstQuad1 = nextQuad1;
435 firstQuad2 = nextQuad2;
436 }
437
438 double varAng, varX, varY, varLen;
439
440 varX = average(ratioX);
441 varY = average(ratioY);
442 varLen = average(ratioLength);
443 varAng = average(rationAngles);
444
445 double estimate = varX + varY + varAng + varLen;
446 /*
447 #ifdef _DEBUG
448 for(UINT dI=0; dI<angles1Size; dI++)
449 {
450 TDebugMessage::getStream() << angles1[dI].first<<" ";
451 }
452 TDebugMessage::flush();
453
454 TDebugMessage::getStream() <<"estimate "<< estimate<<"=" ;
455 TDebugMessage::flush();
456 TDebugMessage::getStream()<<varAng <<"+" ;
457 TDebugMessage::flush();
458 TDebugMessage::getStream()<<varX <<"+" ;
459 TDebugMessage::flush();
460 TDebugMessage::getStream()<<varY<<"+";
461 TDebugMessage::flush();
462 TDebugMessage::getStream()<<varLen;
463 TDebugMessage::flush();
464
465 #endif
466 */
467
468 if (estimate < bestValue) {
469 bestValue = estimate;
470 if (bestVector.size() != angles1Size) {
471 assert(!"bad size for bestVector");
472 bestVector.resize(angles1Size);
473 }
474
475 for (j = 0; j < angles1Size; j++) {
476 bestVector[j] = angles1[j].first;
477 }
478 }
479
480 return;
481 }
482
483 //-------------------------------------------------------------------
484
485 if (r == 1) {
486 for (UINT i = 0; i < partialAngles1Size; i++) {
487 findBestSolution(stroke1, stroke2, partialAngles1 + i, 1, angles2, 1,
488 partialSolution, bestValue, bestVector);
489 }
490 return;
491 }
492
493 partialSolution.push_back(partialAngles1[0]);
494 findBestSolution(stroke1, stroke2, partialAngles1 + 1, partialAngles1Size - 1,
495 angles2, r - 1, partialSolution, bestValue, bestVector);
496
497 partialSolution.pop_back();
498 findBestSolution(stroke1, stroke2, partialAngles1 + 1, partialAngles1Size - 1,
499 angles2, r, partialSolution, bestValue, bestVector);
500 }
501
502 //--------------------------------------------------------------------------------------
503
findBestSolution(const TStroke * stroke1,const TStroke * stroke2,std::vector<std::pair<int,double>> & angles1,const std::vector<std::pair<int,double>> & angles2,double & bestValue,std::vector<int> & bestVector)504 static void findBestSolution(const TStroke *stroke1, const TStroke *stroke2,
505 std::vector<std::pair<int, double>> &angles1,
506 const std::vector<std::pair<int, double>> &angles2,
507 double &bestValue, std::vector<int> &bestVector) {
508 assert(angles1.size() > angles2.size());
509
510 std::list<std::pair<int, double>> partialSolution;
511
512 findBestSolution(stroke1, stroke2, &(angles1[0]), angles1.size(), angles2,
513 angles2.size(), partialSolution, bestValue, bestVector);
514 }
515
516 //--------------------------------------------------------------------------------------
517
trivialSolution(const TStroke * stroke1,const TStroke * stroke2,const std::vector<std::pair<int,double>> & angles1,const std::vector<std::pair<int,double>> & angles2,std::vector<int> & solution)518 static void trivialSolution(const TStroke *stroke1, const TStroke *stroke2,
519 const std::vector<std::pair<int, double>> &angles1,
520 const std::vector<std::pair<int, double>> &angles2,
521 std::vector<int> &solution) {
522 assert(angles1.size() > angles2.size());
523
524 UINT j;
525 double subStrokeRatio2;
526
527 double invTotalLen2 = stroke2->getLength();
528 assert(invTotalLen2);
529 invTotalLen2 = 1.0 / invTotalLen2;
530
531 double invTotalLen1 = stroke1->getLength();
532 assert(invTotalLen1 > 0);
533 invTotalLen1 = 1.0 / invTotalLen1;
534
535 if (solution.size() != angles2.size()) {
536 assert(!"bad size for solution");
537 solution.resize(angles2.size());
538 }
539
540 int toBeErased = angles1.size() - angles2.size();
541 UINT count = 0;
542
543 double diff, ratio, oldRatio = 100;
544
545 subStrokeRatio2 =
546 stroke2->getLengthAtControlPoint(angles2[count].first * 2) * invTotalLen2;
547
548 for (j = 0; j < angles1.size() && count < solution.size(); j++) {
549 if (toBeErased == 0) {
550 solution[count++] = angles1[j].first;
551 } else {
552 ratio =
553 stroke1->getLengthAtControlPoint(angles1[j].first * 2) * invTotalLen1;
554 assert(ratio > 0 && ratio <= 1);
555
556 diff = ratio - subStrokeRatio2;
557 if (diff >= 0) {
558 if (fabs(diff) < fabs(oldRatio - subStrokeRatio2)) {
559 solution[count] = angles1[j].first;
560 oldRatio = 100;
561 } else {
562 assert(j > 0);
563 solution[count] = angles1[j - 1].first;
564 }
565 count++;
566 if (angles2.size() < count)
567 subStrokeRatio2 =
568 stroke2->getLengthAtControlPoint(angles2[count].first * 2) *
569 invTotalLen2;
570 else
571 subStrokeRatio2 = 1;
572 } else {
573 toBeErased--;
574 oldRatio = ratio;
575 }
576 }
577 }
578 assert(count == solution.size());
579 }
580
581 //--------------------------------------------------------------------------------------
582
extract(const TStroke * source,UINT firstQuad,UINT lastQuad)583 static TStroke *extract(const TStroke *source, UINT firstQuad, UINT lastQuad) {
584 UINT quadCount = source->getChunkCount();
585 if (firstQuad >= quadCount) {
586 assert(!"bad quadric index");
587 firstQuad = quadCount - 1;
588 }
589 if (lastQuad < firstQuad) {
590 assert(!"bad quadric index");
591 lastQuad = firstQuad;
592 }
593 if (lastQuad >= quadCount) {
594 assert(!"bad quadric index");
595 lastQuad = quadCount - 1;
596 }
597
598 UINT cpIndex0 = firstQuad * 2;
599 UINT cpIndex1 = lastQuad * 2 + 2;
600
601 std::vector<TThickPoint> points(cpIndex1 - cpIndex0 + 1);
602 UINT count = 0;
603 for (UINT j = cpIndex0; j <= cpIndex1; j++) {
604 points[count++] = source->getControlPoint(j);
605 }
606
607 return new TStroke(points);
608 }
609
610 //--------------------------------------------------------------------------------------
611
sample(const TStroke * stroke,int samplingSize,std::vector<TPointD> & sampledPoint)612 static void sample(const TStroke *stroke, int samplingSize,
613 std::vector<TPointD> &sampledPoint) {
614 double samplingFrequency = 1.0 / (double)samplingSize;
615 sampledPoint.resize(samplingSize);
616
617 double totalLen = stroke->getLength();
618 double step = totalLen * samplingFrequency;
619 double len = 0;
620
621 for (int p = 0; p < samplingSize - 1; p++) {
622 sampledPoint[p] = stroke->getPointAtLength(len);
623 len += step;
624 }
625 sampledPoint.back() =
626 stroke->getControlPoint(stroke->getControlPointCount() - 1);
627 }
628
629 //--------------------------------------------------------------------------------------
630
631 class TInbetween::Imp {
632 public:
633 //----------------------
634
635 struct StrokeTransform {
636 typedef enum { EQUAL, POINT, GENERAL } TransformationType;
637
638 TPointD m_translate;
639 TPointD m_rotationAndScaleCenter;
640 double m_scaleX, m_scaleY, m_rotation;
641
642 TransformationType m_type;
643
644 // saved for optimization
645 TAffine m_inverse;
646
647 std::vector<int> m_firstStrokeCornerIndexes;
648 std::vector<int> m_secondStrokeCornerIndexes;
649 };
650
651 //----------------------
652
653 TVectorImageP m_firstImage, m_lastImage;
654
655 std::vector<StrokeTransform> m_transformation;
656
657 void computeTransformation();
658
659 void transferColor(const TVectorImageP &destination) const;
660
661 TVectorImageP tween(double t) const;
662
Imp(const TVectorImageP firstImage,const TVectorImageP lastImage)663 Imp(const TVectorImageP firstImage, const TVectorImageP lastImage)
664 : m_firstImage(firstImage), m_lastImage(lastImage) {
665 computeTransformation();
666 }
667 };
668 //-------------------------------------------------------------------
669
TInbetween(const TVectorImageP firstImage,const TVectorImageP lastImage)670 TInbetween::TInbetween(const TVectorImageP firstImage,
671 const TVectorImageP lastImage)
672 : m_imp(new TInbetween::Imp(firstImage, lastImage)) {}
673
674 //-------------------------------------------------------------------
675
~TInbetween()676 TInbetween::~TInbetween() {}
677
678 //-------------------------------------------------------------------
679
computeTransformation()680 void TInbetween::Imp::computeTransformation() {
681 const UINT samplingPointNumber = 10;
682 const UINT bboxSamplingWeight = samplingPointNumber / 2;
683
684 StrokeTransform transform;
685 double cs, sn, totalLen1, totalLen2, constK, constQ, constB, constD, constA;
686 UINT cpCount1, cpCount2;
687 TPointD stroke1Centroid, stroke2Centroid, stroke1Begin, stroke2Begin,
688 stroke1End, stroke2End, versor1, versor2;
689 std::vector<TPointD> samplingPoint1(samplingPointNumber),
690 samplingPoint2(samplingPointNumber);
691 TStroke *stroke1, *stroke2;
692 std::vector<double> ratioSampling, weigths, subStrokeXScaling,
693 subStrokeYScaling;
694
695 UINT strokeCount1 = m_firstImage->getStrokeCount();
696 UINT strokeCount2 = m_lastImage->getStrokeCount();
697 if (strokeCount1 > strokeCount2) strokeCount1 = strokeCount2;
698
699 m_transformation.clear();
700 m_transformation.reserve(strokeCount1);
701
702 const int maxSubSetNum = (strokeCount1) ? 1000 / strokeCount1 : 1;
703
704 UINT j, p;
705
706 for (UINT i = 0; i < strokeCount1; i++) {
707 stroke1 = m_firstImage->getStroke(i);
708 stroke2 = m_lastImage->getStroke(i);
709
710 // check if the strokes are equal
711 cpCount1 = stroke1->getControlPointCount();
712 cpCount2 = stroke2->getControlPointCount();
713
714 transform.m_firstStrokeCornerIndexes.clear();
715 transform.m_secondStrokeCornerIndexes.clear();
716 transform.m_translate = TPointD();
717 transform.m_rotationAndScaleCenter = TPointD();
718 transform.m_scaleX = 0;
719 transform.m_scaleY = 0;
720 transform.m_rotation = 0;
721
722 bool isEqual = true;
723
724 if (cpCount1 == cpCount2) {
725 for (j = 0; j < cpCount1 && isEqual; j++) {
726 isEqual = (stroke1->getControlPoint(j) == stroke2->getControlPoint(j));
727 }
728 } else
729 isEqual = false;
730
731 if (isEqual) {
732 transform.m_type = StrokeTransform::EQUAL;
733 } else {
734 totalLen1 = stroke1->getLength();
735 totalLen2 = stroke2->getLength();
736
737 if (totalLen1 == 0 || totalLen2 == 0) {
738 if (totalLen1 == 0 && totalLen2 == 0) {
739 transform.m_type = StrokeTransform::POINT;
740 } else {
741 transform.m_inverse = TAffine();
742 transform.m_firstStrokeCornerIndexes.resize(2);
743 transform.m_firstStrokeCornerIndexes[0] = 0;
744 transform.m_firstStrokeCornerIndexes[1] = stroke1->getChunkCount();
745 transform.m_secondStrokeCornerIndexes.resize(2);
746 transform.m_secondStrokeCornerIndexes[0] = 0;
747 transform.m_secondStrokeCornerIndexes[1] = stroke2->getChunkCount();
748 }
749 } else {
750 const double startMinAngle = 30.0;
751 std::vector<std::pair<int, double>> angles1, angles2;
752
753 transform.m_type = StrokeTransform::GENERAL;
754
755 double minAngle, maxAngle;
756 int minAngle1, maxAngle1, minAngle2, maxAngle2;
757
758 angles1.clear();
759 angles2.clear();
760
761 // TDebugMessage::getStream()<<j<<" stroke1 corner detection";
762 // TDebugMessage::flush();
763
764 detectCorners(stroke1, startMinAngle, angles1, minAngle, maxAngle);
765 minAngle1 = (int)minAngle;
766 maxAngle1 = (int)maxAngle;
767
768 // TDebugMessage::getStream()<<j<<" stroke2 corner detection";
769 // TDebugMessage::flush();
770
771 detectCorners(stroke2, startMinAngle, angles2, minAngle, maxAngle);
772 minAngle2 = (int)minAngle;
773 maxAngle2 = (int)maxAngle;
774
775 if (angles1.empty()) angles2.clear();
776 if (angles2.empty()) angles1.clear();
777
778 /*
779 debugStream.open("c:\\temp\\inbetween.txt", ios_base::out);
780 debugStream <<"num angoli 1: "<< angles1.size() << endl;
781 debugStream <<"num angoli 2: "<< angles2.size() << endl;
782 */
783
784 double bestValue = (std::numeric_limits<double>::max)();
785
786 if (angles1.size() != angles2.size()) {
787 bestValue = (std::numeric_limits<double>::max)();
788
789 //--------------------------------------------------------------------------
790
791 if (isTooComplex(angles1.size(), angles2.size(), maxSubSetNum)) {
792 // debugStream <<"is too complex" << endl;
793 int firstAngle =
794 (int)((angles1.size() < angles2.size()) ? minAngle2
795 : minAngle1);
796 int lastAngle =
797 (int)((angles1.size() < angles2.size()) ? maxAngle1
798 : maxAngle2);
799 int bestAngle = (int)startMinAngle;
800
801 if ((int)(angles1.size() + angles2.size()) <
802 lastAngle - firstAngle + 1) {
803 double tempAngle;
804 std::vector<double> sortedAngles1, sortedAngles2;
805 sortedAngles1.reserve(angles1.size());
806 sortedAngles2.reserve(angles2.size());
807 for (j = 0; j < angles1.size(); j++) {
808 tempAngle = angles1[j].second;
809 if (tempAngle >= firstAngle && tempAngle <= lastAngle)
810 sortedAngles1.push_back(tempAngle);
811 }
812 for (j = 0; j < angles2.size(); j++) {
813 tempAngle = angles2[j].second;
814 if (tempAngle >= firstAngle && tempAngle <= lastAngle)
815 sortedAngles2.push_back(tempAngle);
816 }
817 std::vector<double> sortedAngles(sortedAngles1.size() +
818 sortedAngles2.size());
819
820 std::sort(sortedAngles1.begin(), sortedAngles1.end());
821 std::sort(sortedAngles2.begin(), sortedAngles2.end());
822 std::merge(sortedAngles1.begin(), sortedAngles1.end(),
823 sortedAngles2.begin(), sortedAngles2.end(),
824 sortedAngles.begin());
825
826 for (j = 0; j < sortedAngles.size(); j++) {
827 int numAng1 = angleNumber(angles1, sortedAngles[j]);
828 int numAng2 = angleNumber(angles2, sortedAngles[j]);
829 double val = (numAng1 == numAng2)
830 ? 0
831 : fabs((float)(numAng1 - numAng2)) /
832 (numAng1 + numAng2);
833 if (val < bestValue) {
834 bestValue = val;
835 bestAngle = (int)(sortedAngles[j]);
836 if (bestValue == 0 ||
837 !isTooComplex(numAng1, numAng2, maxSubSetNum))
838 break;
839 }
840 }
841
842 } else //-----------------------------------------------------
843 {
844 for (int angle = firstAngle; angle <= lastAngle; angle++) {
845 int numAng1 = angleNumber(angles1, angle);
846 int numAng2 = angleNumber(angles2, angle);
847 double val = (numAng1 == numAng2)
848 ? 0
849 : fabs((float)(numAng1 - numAng2)) /
850 (numAng1 + numAng2);
851 if (val < bestValue) {
852 bestValue = val;
853 bestAngle = angle;
854 if (bestValue == 0 ||
855 !isTooComplex(numAng1, numAng2, maxSubSetNum))
856 break;
857 }
858 }
859 }
860
861 eraseSmallAngles(angles1, bestAngle);
862 eraseSmallAngles(angles2, bestAngle);
863
864 /*
865 debugStream <<"bestAngle: "<< bestAngle << endl;
866 debugStream <<"num angoli 1: "<< angles1.size() << endl;
867 debugStream <<"num angoli 2: "<< angles2.size() << endl;
868 */
869 }
870 //--------------------------------------------------------------------------
871
872 bestValue = (std::numeric_limits<double>::max)();
873
874 if (angles1.size() == angles2.size()) {
875 transform.m_firstStrokeCornerIndexes.push_back(0);
876 for (j = 0; j < angles1.size(); j++)
877 transform.m_firstStrokeCornerIndexes.push_back(angles1[j].first);
878 transform.m_firstStrokeCornerIndexes.push_back(
879 stroke1->getChunkCount());
880
881 transform.m_secondStrokeCornerIndexes.push_back(0);
882 for (j = 0; j < angles2.size(); j++)
883 transform.m_secondStrokeCornerIndexes.push_back(angles2[j].first);
884 transform.m_secondStrokeCornerIndexes.push_back(
885 stroke2->getChunkCount());
886 } else {
887 if (isTooComplex(angles1.size(), angles2.size(), maxSubSetNum)) {
888 if (angles1.size() > angles2.size()) {
889 transform.m_firstStrokeCornerIndexes.resize(angles2.size());
890 trivialSolution(stroke1, stroke2, angles1, angles2,
891 transform.m_firstStrokeCornerIndexes);
892 transform.m_firstStrokeCornerIndexes.insert(
893 transform.m_firstStrokeCornerIndexes.begin(), 0);
894 transform.m_firstStrokeCornerIndexes.push_back(
895 stroke1->getChunkCount());
896
897 transform.m_secondStrokeCornerIndexes.push_back(0);
898 for (j = 0; j < angles2.size(); j++)
899 transform.m_secondStrokeCornerIndexes.push_back(
900 angles2[j].first);
901 transform.m_secondStrokeCornerIndexes.push_back(
902 stroke2->getChunkCount());
903 } else {
904 transform.m_firstStrokeCornerIndexes.push_back(0);
905 for (j = 0; j < angles1.size(); j++)
906 transform.m_firstStrokeCornerIndexes.push_back(
907 angles1[j].first);
908 transform.m_firstStrokeCornerIndexes.push_back(
909 stroke1->getChunkCount());
910
911 transform.m_secondStrokeCornerIndexes.resize(angles1.size());
912 trivialSolution(stroke2, stroke1, angles2, angles1,
913 transform.m_secondStrokeCornerIndexes);
914 transform.m_secondStrokeCornerIndexes.insert(
915 transform.m_secondStrokeCornerIndexes.begin(), 0);
916 transform.m_secondStrokeCornerIndexes.push_back(
917 stroke2->getChunkCount());
918 }
919 } else {
920 if (angles1.size() > angles2.size()) {
921 transform.m_firstStrokeCornerIndexes.resize(angles2.size());
922 findBestSolution(stroke1, stroke2, angles1, angles2, bestValue,
923 transform.m_firstStrokeCornerIndexes);
924 transform.m_firstStrokeCornerIndexes.insert(
925 transform.m_firstStrokeCornerIndexes.begin(), 0);
926 transform.m_firstStrokeCornerIndexes.push_back(
927 stroke1->getChunkCount());
928
929 transform.m_secondStrokeCornerIndexes.push_back(0);
930 for (j = 0; j < angles2.size(); j++)
931 transform.m_secondStrokeCornerIndexes.push_back(
932 angles2[j].first);
933 transform.m_secondStrokeCornerIndexes.push_back(
934 stroke2->getChunkCount());
935 } else {
936 transform.m_firstStrokeCornerIndexes.push_back(0);
937 for (j = 0; j < angles1.size(); j++)
938 transform.m_firstStrokeCornerIndexes.push_back(
939 angles1[j].first);
940 transform.m_firstStrokeCornerIndexes.push_back(
941 stroke1->getChunkCount());
942
943 transform.m_secondStrokeCornerIndexes.resize(angles1.size());
944 findBestSolution(stroke2, stroke1, angles2, angles1, bestValue,
945 transform.m_secondStrokeCornerIndexes);
946 transform.m_secondStrokeCornerIndexes.insert(
947 transform.m_secondStrokeCornerIndexes.begin(), 0);
948 transform.m_secondStrokeCornerIndexes.push_back(
949 stroke2->getChunkCount());
950 }
951 }
952 }
953 } else {
954 transform.m_firstStrokeCornerIndexes.push_back(0);
955 for (j = 0; j < angles1.size(); j++)
956 transform.m_firstStrokeCornerIndexes.push_back(angles1[j].first);
957 transform.m_firstStrokeCornerIndexes.push_back(
958 stroke1->getChunkCount());
959
960 transform.m_secondStrokeCornerIndexes.push_back(0);
961 for (j = 0; j < angles2.size(); j++)
962 transform.m_secondStrokeCornerIndexes.push_back(angles2[j].first);
963 transform.m_secondStrokeCornerIndexes.push_back(
964 stroke2->getChunkCount());
965 }
966
967 UINT cornerSize = transform.m_firstStrokeCornerIndexes.size();
968 assert(cornerSize == transform.m_secondStrokeCornerIndexes.size());
969 assert(cornerSize >= 2);
970
971 double totalRadRotation = 0;
972
973 TStroke *subStroke1 = 0;
974 TStroke *subStroke2 = 0;
975
976 stroke1Centroid = stroke1->getCentroid();
977 stroke2Centroid = stroke2->getCentroid();
978
979 #ifdef _DEBUG
980 assert(transform.m_firstStrokeCornerIndexes[0] == 0);
981 assert(transform.m_secondStrokeCornerIndexes[0] == 0);
982 assert(transform.m_firstStrokeCornerIndexes[cornerSize - 1] ==
983 stroke1->getChunkCount());
984 assert(transform.m_secondStrokeCornerIndexes[cornerSize - 1] ==
985 stroke2->getChunkCount());
986 for (j = 0; j < cornerSize - 1; j++) {
987 assert(transform.m_firstStrokeCornerIndexes[j] <
988 transform.m_firstStrokeCornerIndexes[j + 1]);
989 assert(transform.m_secondStrokeCornerIndexes[j] <
990 transform.m_secondStrokeCornerIndexes[j + 1]);
991
992 assert(transform.m_firstStrokeCornerIndexes[j] <
993 stroke1->getChunkCount());
994 assert(transform.m_secondStrokeCornerIndexes[j] <
995 stroke2->getChunkCount());
996 }
997 #endif
998
999 for (j = 0; j < cornerSize - 1; j++) {
1000 ///////////////////////////////////////// sampling
1001
1002 subStroke1 = extract(stroke1, transform.m_firstStrokeCornerIndexes[j],
1003 transform.m_firstStrokeCornerIndexes[j + 1] - 1);
1004 sample(subStroke1, samplingPointNumber, samplingPoint1);
1005 subStroke2 =
1006 extract(stroke2, transform.m_secondStrokeCornerIndexes[j],
1007 transform.m_secondStrokeCornerIndexes[j + 1] - 1);
1008 sample(subStroke2, samplingPointNumber, samplingPoint2);
1009
1010 ///////////////////////////////////////// compute Rotation
1011
1012 ratioSampling.clear();
1013 ratioSampling.reserve(samplingPointNumber);
1014 weigths.clear();
1015 weigths.reserve(samplingPointNumber);
1016
1017 TPointD pOld, pNew;
1018 // double totalW=0;
1019
1020 for (p = 0; p < samplingPointNumber; p++) {
1021 pOld = samplingPoint1[p];
1022 pNew = samplingPoint2[p];
1023 if (pOld == stroke1Centroid) continue;
1024 if (pNew == stroke2Centroid) continue;
1025 versor1 = normalize(pOld - stroke1Centroid);
1026 versor2 = normalize(pNew - stroke2Centroid);
1027 weigths.push_back(tdistance(pOld, stroke1Centroid) +
1028 tdistance(pNew, stroke2Centroid));
1029 cs = versor1 * versor2;
1030 sn = cross(versor1, versor2);
1031 double v = atan2(sn, cs);
1032 ratioSampling.push_back(v);
1033 }
1034 delete subStroke1;
1035 delete subStroke2;
1036 subStroke1 = 0;
1037 subStroke2 = 0;
1038
1039 double radRotation = weightedAverage(ratioSampling, weigths);
1040
1041 totalRadRotation += radRotation;
1042 }
1043 totalRadRotation /= (cornerSize - 1);
1044 transform.m_rotation = totalRadRotation * M_180_PI;
1045
1046 if (isAlmostZero(transform.m_rotation, 2)) {
1047 transform.m_rotation = 0.0;
1048 totalRadRotation = 0.0;
1049 }
1050
1051 #ifdef _DEBUG
1052 // TDebugMessage::getStream()<<"rotation "<< transform.m_rotation;
1053 // TDebugMessage::flush();
1054 #endif
1055
1056 ///////////////////////////////////////// compute Scale
1057
1058 if (transform.m_rotation == 0.0) {
1059 subStrokeXScaling.clear();
1060 subStrokeXScaling.reserve(cornerSize - 1);
1061 subStrokeYScaling.clear();
1062 subStrokeYScaling.reserve(cornerSize - 1);
1063
1064 for (j = 0; j < cornerSize - 1; j++) {
1065 ///////////////////////////////////////// sampling
1066
1067 subStroke1 =
1068 extract(stroke1, transform.m_firstStrokeCornerIndexes[j],
1069 transform.m_firstStrokeCornerIndexes[j + 1] - 1);
1070 sample(subStroke1, samplingPointNumber, samplingPoint1);
1071 subStroke2 =
1072 extract(stroke2, transform.m_secondStrokeCornerIndexes[j],
1073 transform.m_secondStrokeCornerIndexes[j + 1] - 1);
1074 sample(subStroke2, samplingPointNumber, samplingPoint2);
1075
1076 ///////////////////////////////////////// compute X Scale
1077
1078 ratioSampling.clear();
1079 ratioSampling.reserve(samplingPointNumber + bboxSamplingWeight);
1080 double appX, appY;
1081
1082 TPointD appPoint;
1083 double bboxXMin, bboxYMin, bboxXMax, bboxYMax;
1084 bboxXMin = bboxYMin = (std::numeric_limits<double>::max)();
1085 bboxXMax = bboxYMax = -(std::numeric_limits<double>::max)();
1086 int h;
1087
1088 for (h = 0; h < subStroke1->getControlPointCount(); ++h) {
1089 appPoint = subStroke1->getControlPoint(h);
1090 if (appPoint.x < bboxXMin) bboxXMin = appPoint.x;
1091 if (appPoint.x > bboxXMax) bboxXMax = appPoint.x;
1092 if (appPoint.y < bboxYMin) bboxYMin = appPoint.y;
1093 if (appPoint.y > bboxYMax) bboxYMax = appPoint.y;
1094 }
1095
1096 appX = bboxXMax - bboxXMin;
1097 appY = bboxYMax - bboxYMin;
1098
1099 if (appX) {
1100 bboxXMin = (std::numeric_limits<double>::max)();
1101 bboxXMax = -(std::numeric_limits<double>::max)();
1102 for (h = 0; h < subStroke2->getControlPointCount(); ++h) {
1103 appPoint = subStroke2->getControlPoint(h);
1104 if (appPoint.x < bboxXMin) bboxXMin = appPoint.x;
1105 if (appPoint.x > bboxXMax) bboxXMax = appPoint.x;
1106 }
1107 appX = (isAlmostZero(appX, 1e-01)) ? -1
1108 : (bboxXMax - bboxXMin) / appX;
1109 for (UINT tms = 0; tms < bboxSamplingWeight && appX >= 0; tms++)
1110 ratioSampling.push_back(appX);
1111
1112 for (p = 0; p < samplingPointNumber; p++) {
1113 appX = fabs(samplingPoint1[p].x - stroke1Centroid.x);
1114 if (appX)
1115 ratioSampling.push_back(
1116 fabs(samplingPoint2[p].x - stroke2Centroid.x) / appX);
1117 }
1118
1119 if (!ratioSampling.empty()) {
1120 subStrokeXScaling.push_back(average(ratioSampling));
1121 }
1122 }
1123
1124 ///////////////////////////////////////// compute Y Scale
1125
1126 ratioSampling.clear();
1127 ratioSampling.reserve(samplingPointNumber + bboxSamplingWeight);
1128
1129 if (appY) {
1130 bboxYMin = (std::numeric_limits<double>::max)();
1131 bboxYMax = -(std::numeric_limits<double>::max)();
1132 for (h = 0; h < subStroke2->getControlPointCount(); ++h) {
1133 appPoint = subStroke2->getControlPoint(h);
1134 if (appPoint.y < bboxYMin) bboxYMin = appPoint.y;
1135 if (appPoint.y > bboxYMax) bboxYMax = appPoint.y;
1136 }
1137
1138 appY = (isAlmostZero(appY, 1e-01)) ? -1
1139 : (bboxYMax - bboxYMin) / appY;
1140 for (UINT tms = 0; tms < bboxSamplingWeight && appY >= 0; tms++)
1141 ratioSampling.push_back(appY);
1142
1143 for (p = 0; p < samplingPointNumber; p++) {
1144 appY = fabs(samplingPoint1[p].y - stroke1Centroid.y);
1145 if (appY)
1146 ratioSampling.push_back(
1147 fabs(samplingPoint2[p].y - stroke2Centroid.y) / appY);
1148 }
1149
1150 if (!ratioSampling.empty()) {
1151 subStrokeYScaling.push_back(average(ratioSampling));
1152 }
1153 }
1154
1155 delete subStroke1;
1156 delete subStroke2;
1157 subStroke1 = 0;
1158 subStroke2 = 0;
1159 }
1160
1161 if (subStrokeXScaling.empty()) {
1162 transform.m_scaleX = 1.0;
1163 } else {
1164 transform.m_scaleX = average(subStrokeXScaling);
1165 if (isAlmostZero(transform.m_scaleX - 1.0))
1166 transform.m_scaleX = 1.0;
1167 }
1168
1169 if (subStrokeYScaling.empty()) {
1170 transform.m_scaleY = 1.0;
1171 } else {
1172 transform.m_scaleY = average(subStrokeYScaling);
1173 if (isAlmostZero(transform.m_scaleY - 1.0))
1174 transform.m_scaleY = 1.0;
1175 }
1176 /*
1177 #ifdef _DEBUG
1178
1179 TDebugMessage::getStream()<<"x scale "<< transform.m_scaleX ;
1180 TDebugMessage::flush();
1181 TDebugMessage::getStream()<<"y scale "<< transform.m_scaleY ;
1182 TDebugMessage::flush();
1183 #endif
1184 */
1185 } else {
1186 subStrokeXScaling.clear();
1187 subStrokeXScaling.reserve(cornerSize - 1);
1188
1189 for (j = 0; j < cornerSize - 1; j++) {
1190 ///////////////////////////////////////// sampling
1191
1192 subStroke1 =
1193 extract(stroke1, transform.m_firstStrokeCornerIndexes[j],
1194 transform.m_firstStrokeCornerIndexes[j + 1] - 1);
1195 sample(subStroke1, samplingPointNumber, samplingPoint1);
1196 subStroke2 =
1197 extract(stroke2, transform.m_secondStrokeCornerIndexes[j],
1198 transform.m_secondStrokeCornerIndexes[j + 1] - 1);
1199 sample(subStroke2, samplingPointNumber, samplingPoint2);
1200
1201 ///////////////////////////////////////// compute Scale
1202
1203 ratioSampling.clear();
1204 ratioSampling.reserve(samplingPointNumber + bboxSamplingWeight);
1205
1206 TRectD bbox1 = subStroke1->getBBox();
1207 double app = tdistance2(bbox1.getP00(), bbox1.getP11());
1208 if (app) {
1209 TRectD bbox2 =
1210 TRotation(transform.m_rotation).inv() * subStroke2->getBBox();
1211 app = sqrt(tdistance2(bbox2.getP00(), bbox2.getP11()) / app);
1212
1213 for (UINT tms = 0; tms < bboxSamplingWeight; tms++)
1214 ratioSampling.push_back(app);
1215
1216 double app;
1217 for (p = 0; p < samplingPointNumber; p++) {
1218 app = tdistance(samplingPoint1[p], stroke1Centroid);
1219 if (app) {
1220 ratioSampling.push_back(
1221 tdistance(samplingPoint2[p], stroke2Centroid) / app);
1222 }
1223 }
1224 }
1225 if (!ratioSampling.empty()) {
1226 subStrokeXScaling.push_back(average(ratioSampling));
1227 }
1228
1229 delete subStroke1;
1230 delete subStroke2;
1231 subStroke1 = 0;
1232 subStroke2 = 0;
1233 }
1234
1235 if (subStrokeXScaling.empty()) {
1236 transform.m_scaleX = transform.m_scaleY = 1.0;
1237 } else {
1238 transform.m_scaleX = transform.m_scaleY =
1239 average(subStrokeXScaling);
1240 if (isAlmostZero(transform.m_scaleX - 1.0, 0.00001))
1241 transform.m_scaleX = transform.m_scaleY = 1.0;
1242 }
1243 /*
1244 #ifdef _DEBUG
1245
1246 TDebugMessage::getStream()<<"scale "<< transform.m_scaleX ;
1247 TDebugMessage::flush();
1248 #endif
1249 */
1250 }
1251
1252 ///////////////////////////////////////// compute centre of Rotation and
1253 /// Scaling
1254
1255 std::vector<TPointD> vpOld(cornerSize), vpNew(cornerSize);
1256 TPointD pOld, pNew;
1257
1258 for (j = 0; j < cornerSize - 1; j++) {
1259 vpOld[j] = stroke1->getChunk(transform.m_firstStrokeCornerIndexes[j])
1260 ->getP0();
1261 vpNew[j] = stroke2->getChunk(transform.m_secondStrokeCornerIndexes[j])
1262 ->getP0();
1263 }
1264 vpOld[j] = stroke1->getControlPoint(stroke1->getControlPointCount());
1265 vpNew[j] = stroke2->getControlPoint(stroke2->getControlPointCount());
1266
1267 if (transform.m_rotation == 0.0) {
1268 if (transform.m_scaleX == 1.0 && transform.m_scaleY == 1.0) {
1269 transform.m_translate = stroke2Centroid - stroke1Centroid;
1270 transform.m_rotationAndScaleCenter = TPointD();
1271 } else {
1272 if (transform.m_scaleX == 1.0) {
1273 transform.m_rotationAndScaleCenter.x = 0;
1274 transform.m_translate.x = 0;
1275 for (j = 0; j < cornerSize; j++) {
1276 transform.m_translate.x += vpNew[j].x - vpOld[j].x;
1277 }
1278 transform.m_translate.x = transform.m_translate.x / cornerSize;
1279 } else {
1280 transform.m_rotationAndScaleCenter.x = 0;
1281
1282 for (j = 0; j < cornerSize; j++) {
1283 pOld = vpOld[j];
1284 pNew = vpNew[j];
1285 transform.m_rotationAndScaleCenter.x +=
1286 (transform.m_scaleX * pOld.x - pNew.x) /
1287 (transform.m_scaleX - 1.0);
1288 }
1289 transform.m_rotationAndScaleCenter.x =
1290 transform.m_rotationAndScaleCenter.x / cornerSize;
1291 transform.m_translate.x = 0;
1292 }
1293
1294 if (transform.m_scaleY == 1.0) {
1295 transform.m_rotationAndScaleCenter.y = 0;
1296 transform.m_translate.y = 0;
1297 for (j = 0; j < cornerSize; j++) {
1298 transform.m_translate.y += vpNew[j].y - vpOld[j].y;
1299 }
1300 transform.m_translate.y = transform.m_translate.y / cornerSize;
1301 } else {
1302 transform.m_rotationAndScaleCenter.y = 0;
1303
1304 for (j = 0; j < cornerSize; j++) {
1305 pOld = vpOld[j];
1306 pNew = vpNew[j];
1307 transform.m_rotationAndScaleCenter.y +=
1308 (transform.m_scaleY * pOld.y - pNew.y) /
1309 (transform.m_scaleY - 1.0);
1310 }
1311 transform.m_rotationAndScaleCenter.y =
1312 transform.m_rotationAndScaleCenter.y / cornerSize;
1313 transform.m_translate.y = 0;
1314 }
1315 }
1316
1317 } else {
1318 assert(transform.m_scaleX == transform.m_scaleY);
1319
1320 cs = transform.m_scaleX * cos(totalRadRotation);
1321 sn = transform.m_scaleX * sin(totalRadRotation);
1322
1323 // scelgo punti da usare come vincolo, per ottenere la translazione,
1324 // dato un centro di rotazione
1325
1326 // dato il punto pOld e pNew si calcola analiticamnete il punto di
1327 // rotazione e scala
1328 // che minimizza la traslazione aggiuntiva e la traslazione stessa
1329
1330 for (j = 0; j < cornerSize; j++) {
1331 pOld = vpOld[j];
1332 pNew = vpNew[j];
1333 constK = pNew.x - cs * pOld.x + sn * pOld.y;
1334 constQ = pNew.y - sn * pOld.x - cs * pOld.y;
1335 constB = 2 * (constK * (cs - 1.) + sn * constQ);
1336 constD = 2 * (constQ * (cs - 1.) - sn * constK);
1337 constA = transform.m_scaleX * transform.m_scaleX + 1 - 2 * cs;
1338 assert(constA > 0);
1339 constA = 1.0 / (2 * constA);
1340 transform.m_rotationAndScaleCenter.x += -constB * constA;
1341 transform.m_rotationAndScaleCenter.y += -constD * constA;
1342 }
1343
1344 transform.m_rotationAndScaleCenter =
1345 transform.m_rotationAndScaleCenter * (1.0 / (double)cornerSize);
1346
1347 transform.m_translate.x =
1348 (cs - 1.0) * transform.m_rotationAndScaleCenter.x -
1349 sn * transform.m_rotationAndScaleCenter.y + constK;
1350
1351 transform.m_translate.y =
1352 sn * transform.m_rotationAndScaleCenter.x +
1353 (cs - 1.0) * transform.m_rotationAndScaleCenter.y + constQ;
1354 }
1355
1356 /////////////////////////////////////////
1357
1358 transform.m_inverse = (TTranslation(transform.m_translate) *
1359 TScale(transform.m_rotationAndScaleCenter,
1360 transform.m_scaleX, transform.m_scaleY) *
1361 TRotation(transform.m_rotationAndScaleCenter,
1362 transform.m_rotation))
1363 .inv();
1364
1365 // debugStream.close();
1366 } // end if !isPoint
1367
1368 } // end if !isEqual
1369
1370 m_transformation.push_back(transform);
1371
1372 } // end for each stroke
1373 }
1374
1375 //-------------------------------------------------------------------
1376
tween(double t) const1377 TVectorImageP TInbetween::Imp::tween(double t) const {
1378 const double step = 5.0;
1379 const double interpolateError = 1.0;
1380
1381 TVectorImageP vi = new TVectorImage;
1382
1383 UINT strokeCount1 = m_firstImage->getStrokeCount();
1384 UINT strokeCount2 = m_lastImage->getStrokeCount();
1385 vi->setPalette(m_firstImage->getPalette());
1386 if (strokeCount1 > strokeCount2) strokeCount1 = strokeCount2;
1387
1388 assert(m_transformation.size() == strokeCount1);
1389
1390 double totalLen1, totalLen2, len1, len2, step1, step2;
1391 std::vector<TThickPoint> points;
1392 TStroke *stroke1, *stroke2, *subStroke1, *subStroke2, *stroke;
1393
1394 TAffine mt, invMatrix;
1395 TThickPoint point2, finalPoint;
1396 UINT i, j, cp, cpSize;
1397
1398 for (i = 0; i < strokeCount1; i++) {
1399 stroke1 = m_firstImage->getStroke(i);
1400 stroke2 = m_lastImage->getStroke(i);
1401
1402 if (m_transformation[i].m_type == StrokeTransform::EQUAL) {
1403 stroke = new TStroke(*stroke1);
1404 } else {
1405 points.clear();
1406 totalLen1 = stroke1->getLength();
1407 totalLen2 = stroke2->getLength();
1408 ;
1409
1410 if (stroke1->getControlPointCount() == stroke2->getControlPointCount() &&
1411 stroke1->isSelfLoop() && stroke2->isSelfLoop()) {
1412 for (int i = 0; i < stroke1->getControlPointCount(); i++) {
1413 TThickPoint p0 = stroke1->getControlPoint(i);
1414 TThickPoint p1 = stroke2->getControlPoint(i);
1415 points.push_back(p0 * (1 - t) + p1 * t);
1416 }
1417 stroke = new TStroke(points);
1418 } else if (m_transformation[i].m_type == StrokeTransform::POINT) {
1419 TThickPoint pOld = stroke1->getThickPointAtLength(0.5 * totalLen1);
1420 TThickPoint pNew = stroke2->getThickPointAtLength(0.5 * totalLen2);
1421 points.push_back(pOld * (1 - t) + pNew * t);
1422 points.push_back(points[0]);
1423 points.push_back(points[0]);
1424 stroke = new TStroke(points);
1425 } else {
1426 mt = (m_transformation[i].m_inverse.isIdentity())
1427 ? TAffine()
1428 : TTranslation(m_transformation[i].m_translate * t) *
1429 TScale(m_transformation[i].m_rotationAndScaleCenter,
1430 (1 - t) + t * m_transformation[i].m_scaleX,
1431 (1 - t) + t * m_transformation[i].m_scaleY) *
1432 TRotation(m_transformation[i].m_rotationAndScaleCenter,
1433 m_transformation[i].m_rotation * t);
1434
1435 UINT cornerSize = m_transformation[i].m_firstStrokeCornerIndexes.size();
1436 assert(cornerSize ==
1437 m_transformation[i].m_secondStrokeCornerIndexes.size());
1438 if (cornerSize > m_transformation[i].m_secondStrokeCornerIndexes.size())
1439 cornerSize = m_transformation[i].m_secondStrokeCornerIndexes.size();
1440
1441 assert(cornerSize >= 2);
1442
1443 std::vector<TThickPoint> controlPoints;
1444
1445 // if not m_transformation[i].m_findCorners => detect corner return
1446 // different size =>cornerSize==2
1447 // assert(!m_transformation[i].m_findCorners || cornerSize==2);
1448
1449 for (j = 0; j < cornerSize - 1; j++) {
1450 points.clear();
1451 subStroke1 = extract(
1452 stroke1, m_transformation[i].m_firstStrokeCornerIndexes[j],
1453 m_transformation[i].m_firstStrokeCornerIndexes[j + 1] - 1);
1454 subStroke2 = extract(
1455 stroke2, m_transformation[i].m_secondStrokeCornerIndexes[j],
1456 m_transformation[i].m_secondStrokeCornerIndexes[j + 1] - 1);
1457
1458 totalLen1 = subStroke1->getLength();
1459 totalLen2 = subStroke2->getLength();
1460
1461 if (totalLen1 > totalLen2) {
1462 step1 = step;
1463 step2 = (totalLen2 / totalLen1) * step;
1464 } else {
1465 step1 = (totalLen1 / totalLen2) * step;
1466 step2 = step;
1467 }
1468
1469 len1 = 0;
1470 len2 = 0;
1471
1472 while (len1 <= totalLen1 && len2 <= totalLen2) {
1473 point2 = subStroke2->getThickPointAtLength(len2);
1474 point2 = TThickPoint(m_transformation[i].m_inverse *
1475 subStroke2->getThickPointAtLength(len2),
1476 point2.thick);
1477 finalPoint =
1478 subStroke1->getThickPointAtLength(len1) * (1 - t) + t * point2;
1479
1480 points.push_back(TThickPoint(mt * (finalPoint), finalPoint.thick));
1481 len1 += step1;
1482 len2 += step2;
1483 }
1484 point2 = subStroke2->getThickPointAtLength(totalLen2);
1485 point2 = TThickPoint(m_transformation[i].m_inverse *
1486 subStroke2->getThickPointAtLength(totalLen2),
1487 point2.thick);
1488 finalPoint = subStroke1->getThickPointAtLength(totalLen1) * (1 - t) +
1489 t * point2;
1490
1491 points.push_back(TThickPoint(mt * (finalPoint), finalPoint.thick));
1492
1493 stroke = TStroke::interpolate(points, interpolateError, false
1494 /*m_transformation[i].m_findCorners*/);
1495
1496 if (j == 0)
1497 controlPoints.push_back(stroke->getControlPoint(0));
1498 else
1499 controlPoints.back() =
1500 (controlPoints.back() + stroke->getControlPoint(0)) * 0.5;
1501
1502 cpSize = stroke->getControlPointCount();
1503 for (cp = 1; cp < cpSize; cp++) {
1504 controlPoints.push_back(stroke->getControlPoint(cp));
1505 }
1506
1507 delete subStroke1;
1508 delete subStroke2;
1509 delete stroke;
1510 subStroke1 = 0;
1511 subStroke2 = 0;
1512 stroke = 0;
1513 }
1514
1515 stroke = new TStroke(controlPoints);
1516 }
1517 }
1518
1519 if (stroke1->isSelfLoop() && stroke2->isSelfLoop()) stroke->setSelfLoop();
1520
1521 stroke->setStyle(stroke1->getStyle());
1522 stroke->outlineOptions() = stroke1->outlineOptions();
1523 VIStroke *vs =
1524 new VIStroke(stroke, m_firstImage->getVIStroke(i)->m_groupId);
1525 vi->m_imp->m_strokes.push_back(vs);
1526
1527 } // end for each stroke
1528
1529 if (m_firstImage->isComputedRegionAlmostOnce()) transferColor(vi);
1530
1531 return vi;
1532 }
1533
1534 //-------------------------------------------------------------------
1535
transferColor(const TVectorImageP & destination) const1536 void TInbetween::Imp::transferColor(const TVectorImageP &destination) const {
1537 const TVectorImageP &original = m_firstImage;
1538 destination->setPalette(original->getPalette());
1539
1540 destination->findRegions();
1541
1542 if (destination->getRegionCount()) {
1543 UINT strokeCount1 = original->getStrokeCount();
1544 UINT strokeCount2 = destination->getStrokeCount();
1545 if (strokeCount1 > strokeCount2) strokeCount1 = strokeCount2;
1546
1547 for (UINT i = 0; i < strokeCount1; i++) {
1548 TVectorImage::transferStrokeColors(original, i, destination, i);
1549 }
1550 }
1551 }
1552
1553 //-------------------------------------------------------------------
1554
tween(double t) const1555 TVectorImageP TInbetween::tween(double t) const { return m_imp->tween(t); }
1556
1557 //-------------------------------------------------------------------
1558
interpolation(double t,enum TweenAlgorithm algorithm)1559 double TInbetween::interpolation(double t, enum TweenAlgorithm algorithm) {
1560 // in tutte le interpolazioni : s(0) = 0, s(1) = 1
1561 switch (algorithm) {
1562 case EaseInInterpolation: // s'(1) = 0
1563 return t * (2 - t);
1564 case EaseOutInterpolation: // s'(0) = 0
1565 return t * t;
1566 case EaseInOutInterpolation: // s'(0) = s'(1) = 0
1567 return t * t * (3 - 2 * t);
1568 case LinearInterpolation:
1569 default:
1570 return t;
1571 }
1572 }
1573
1574 //-------------------------------------------------------------------
1575