1
2
3 #include "texception.h"
4 #include "toonz/autoclose.h"
5 #include "trastercm.h"
6 #include "skeletonlut.h"
7
8 #define AUT_SPOT_SAMPLES 10
9
10 using namespace SkeletonLut;
11
12 class TAutocloser::Imp {
13 public:
14 struct Seed {
15 UCHAR *m_ptr;
16 UCHAR m_preseed;
SeedTAutocloser::Imp::Seed17 Seed(UCHAR *ptr, UCHAR preseed) : m_ptr(ptr), m_preseed(preseed) {}
18 };
19
20 int m_closingDistance;
21 double m_spotAngle;
22 int m_inkIndex;
23 int m_opacity;
24 TRasterP m_raster;
25 TRasterGR8P m_bRaster;
26 UCHAR *m_br;
27
28 int m_bWrap;
29
30 int m_displaceVector[8];
31 TPointD m_displAverage;
32 int m_visited;
33
34 double m_csp, m_snp, m_csm, m_snm, m_csa, m_sna, m_csb, m_snb;
35
Imp(const TRasterP & r,int distance=10,double angle=M_PI_2,int index=0,int opacity=0)36 Imp(const TRasterP &r, int distance = 10, double angle = M_PI_2,
37 int index = 0, int opacity = 0)
38 : m_raster(r)
39 , m_spotAngle(angle)
40 , m_closingDistance(distance)
41 , m_inkIndex(index)
42 , m_opacity(opacity) {}
43
~Imp()44 ~Imp() {}
45
isInk(UCHAR * br)46 bool inline isInk(UCHAR *br) { return (*br) & 0x1; }
eraseInk(UCHAR * br)47 inline void eraseInk(UCHAR *br) { *(br) &= 0xfe; }
48
ePix(UCHAR * br)49 UCHAR inline ePix(UCHAR *br) { return (*(br + 1)); }
wPix(UCHAR * br)50 UCHAR inline wPix(UCHAR *br) { return (*(br - 1)); }
nPix(UCHAR * br)51 UCHAR inline nPix(UCHAR *br) { return (*(br + m_bWrap)); }
sPix(UCHAR * br)52 UCHAR inline sPix(UCHAR *br) { return (*(br - m_bWrap)); }
swPix(UCHAR * br)53 UCHAR inline swPix(UCHAR *br) { return (*(br - m_bWrap - 1)); }
nwPix(UCHAR * br)54 UCHAR inline nwPix(UCHAR *br) { return (*(br + m_bWrap - 1)); }
nePix(UCHAR * br)55 UCHAR inline nePix(UCHAR *br) { return (*(br + m_bWrap + 1)); }
sePix(UCHAR * br)56 UCHAR inline sePix(UCHAR *br) { return (*(br - m_bWrap + 1)); }
neighboursCode(UCHAR * seed)57 UCHAR inline neighboursCode(UCHAR *seed) {
58 return ((swPix(seed) & 0x1) | ((sPix(seed) & 0x1) << 1) |
59 ((sePix(seed) & 0x1) << 2) | ((wPix(seed) & 0x1) << 3) |
60 ((ePix(seed) & 0x1) << 4) | ((nwPix(seed) & 0x1) << 5) |
61 ((nPix(seed) & 0x1) << 6) | ((nePix(seed) & 0x1) << 7));
62 }
63
64 //.......................
65
notMarkedBorderInk(UCHAR * br)66 inline bool notMarkedBorderInk(UCHAR *br) {
67 return ((((*br) & 0x5) == 1) &&
68 (ePix(br) == 0 || wPix(br) == 0 || nPix(br) == 0 || sPix(br) == 0));
69 }
70
71 //.......................
getPtr(int x,int y)72 UCHAR *getPtr(int x, int y) { return m_br + m_bWrap * y + x; }
getPtr(const TPoint & p)73 UCHAR *getPtr(const TPoint &p) { return m_br + m_bWrap * p.y + p.x; }
74
getCoordinates(UCHAR * br)75 TPoint getCoordinates(UCHAR *br) {
76 TPoint p;
77 int pixelCount = br - m_bRaster->getRawData();
78 p.y = pixelCount / m_bWrap;
79 p.x = pixelCount - p.y * m_bWrap;
80 return p;
81 }
82
83 //.......................
84 void compute(std::vector<Segment> &closingSegmentArray);
85 void draw(const std::vector<Segment> &closingSegmentArray);
86 void skeletonize(std::vector<TPoint> &endpoints);
87 void findSeeds(std::vector<Seed> &seeds, std::vector<TPoint> &endpoints);
88 void erase(std::vector<Seed> &seeds, std::vector<TPoint> &endpoints);
89 void circuitAndMark(UCHAR *seed, UCHAR preseed);
90 bool circuitAndCancel(UCHAR *seed, UCHAR preseed,
91 std::vector<TPoint> &endpoints);
92 void findMeetingPoints(std::vector<TPoint> &endpoints,
93 std::vector<Segment> &closingSegments);
94 void calculateWeightAndDirection(std::vector<Segment> &orientedEndpoints);
95 bool spotResearchTwoPoints(std::vector<Segment> &endpoints,
96 std::vector<Segment> &closingSegments);
97 bool spotResearchOnePoint(std::vector<Segment> &endpoints,
98 std::vector<Segment> &closingSegments);
99
100 void copy(const TRasterGR8P &braux, TRaster32P &raux);
101 int exploreTwoSpots(const TAutocloser::Segment &s0,
102 const TAutocloser::Segment &s1);
103 int notInsidePath(const TPoint &p, const TPoint &q);
104 void drawInByteRaster(const TPoint &p0, const TPoint &p1);
105 TPoint visitEndpoint(UCHAR *br);
106 bool exploreSpot(const Segment &s, TPoint &p);
107 bool exploreRay(UCHAR *br, Segment s, TPoint &p);
108 void visitPix(UCHAR *br, int toVisit, const TPoint &dis);
109 void cancelMarks(UCHAR *br);
110 void cancelFromArray(std::vector<Segment> &array, TPoint p, int &count);
111 };
112
113 /*------------------------------------------------------------------------*/
114
115 /*------------------------------------------------------------------------*/
116
117 #define DRAW_SEGMENT(a, b, da, db, istr1, istr2, block) \
118 { \
119 d = 2 * db - da; \
120 incr_1 = 2 * db; \
121 incr_2 = 2 * (db - da); \
122 while (a < da) { \
123 if (d <= 0) { \
124 d += incr_1; \
125 a++; \
126 istr1; \
127 } else { \
128 d += incr_2; \
129 a++; \
130 b++; \
131 istr2; \
132 } \
133 block; \
134 } \
135 }
136
137 /*------------------------------------------------------------------------*/
138
139 #define EXPLORE_RAY_ISTR(istr) \
140 if (!inside_ink) { \
141 if (((*br) & 0x1) && !((*br) & 0x80)) { \
142 p.x = istr; \
143 p.y = (s.first.y < s.second.y) ? s.first.y + y : s.first.y - y; \
144 return true; \
145 } \
146 } else if (inside_ink && !((*br) & 0x1)) \
147 inside_ink = 0;
148
149 /*------------------------------------------------------------------------*/
150
151 //-------------------------------------------------
152
153 namespace {
154
isInk(const TPixel32 & pix)155 inline bool isInk(const TPixel32 &pix) { return pix.r < 80; }
156
157 /*------------------------------------------------------------------------*/
158
fillByteRaster(const TRasterCM32P & r,TRasterGR8P & bRaster)159 TRasterGR8P fillByteRaster(const TRasterCM32P &r, TRasterGR8P &bRaster) {
160 int i, j;
161 int lx = r->getLx();
162 int ly = r->getLy();
163 // bRaster->create(lx+4, ly+4);
164 UCHAR *br = bRaster->getRawData();
165
166 for (i = 0; i < lx + 4; i++) *(br++) = 0;
167
168 for (i = 0; i < lx + 4; i++) *(br++) = 131;
169
170 for (i = 0; i < ly; i++) {
171 *(br++) = 0;
172 *(br++) = 131;
173 TPixelCM32 *pix = r->pixels(i);
174 for (j = 0; j < lx; j++, pix++) {
175 if (pix->getTone() != pix->getMaxTone())
176 *(br++) = 3;
177 else
178 *(br++) = 0;
179 }
180 *(br++) = 131;
181 *(br++) = 0;
182 }
183
184 for (i = 0; i < lx + 4; i++) *(br++) = 131;
185
186 for (i = 0; i < lx + 4; i++) *(br++) = 0;
187
188 return bRaster;
189 }
190
191 /*------------------------------------------------------------------------*/
192
193 #define SET_INK \
194 if (buf->getTone() == buf->getMaxTone()) \
195 *buf = TPixelCM32(inkIndex, 0, 255 - opacity);
196
drawSegment(TRasterCM32P & r,const TAutocloser::Segment & s,USHORT inkIndex,USHORT opacity)197 void drawSegment(TRasterCM32P &r, const TAutocloser::Segment &s,
198 USHORT inkIndex, USHORT opacity) {
199 int wrap = r->getWrap();
200 TPixelCM32 *buf = r->pixels();
201 /*
202 int i, j;
203 for (i=0; i<r->getLy();i++)
204 {
205 for (j=0; j<r->getLx();j++, buf++)
206 *buf = (1<<4)|0xf;
207 buf += wrap-r->getLx();
208 }
209 return;
210 */
211
212 int x, y, dx, dy, d, incr_1, incr_2;
213
214 int x1 = s.first.x;
215 int y1 = s.first.y;
216 int x2 = s.second.x;
217 int y2 = s.second.y;
218
219 if (x1 > x2) {
220 std::swap(x1, x2);
221 std::swap(y1, y2);
222 }
223
224 buf += y1 * wrap + x1;
225
226 dx = x2 - x1;
227 dy = y2 - y1;
228
229 x = y = 0;
230
231 if (dy >= 0) {
232 if (dy <= dx)
233 DRAW_SEGMENT(x, y, dx, dy, (buf++), (buf += wrap + 1), SET_INK)
234 else
235 DRAW_SEGMENT(y, x, dy, dx, (buf += wrap), (buf += wrap + 1), SET_INK)
236 } else {
237 dy = -dy;
238 if (dy <= dx)
239 DRAW_SEGMENT(x, y, dx, dy, (buf++), (buf -= (wrap - 1)), SET_INK)
240 else
241 DRAW_SEGMENT(y, x, dy, dx, (buf -= wrap), (buf -= (wrap - 1)), SET_INK)
242 }
243 }
244
245 /*------------------------------------------------------------------------*/
246
247 } // namespace
248 /*------------------------------------------------------------------------*/
249
compute(std::vector<Segment> & closingSegmentArray)250 void TAutocloser::Imp::compute(std::vector<Segment> &closingSegmentArray) {
251 std::vector<TPoint> endpoints;
252 try {
253 assert(closingSegmentArray.empty());
254
255 TRasterCM32P raux;
256
257 if (!(raux = (TRasterCM32P)m_raster))
258 throw TException("Unable to autoclose a not CM32 image.");
259
260 if (m_raster->getLx() == 0 || m_raster->getLy() == 0)
261 throw TException("Autoclose error: bad image size");
262
263 // Lx = r->lx;
264 // Ly = r->ly;
265
266 TRasterGR8P braux(raux->getLx() + 4, raux->getLy() + 4);
267 braux->lock();
268 fillByteRaster(raux, braux);
269
270 TRect r(2, 2, braux->getLx() - 3, braux->getLy() - 3);
271 m_bRaster = braux->extract(r);
272 m_br = m_bRaster->getRawData();
273 m_bWrap = m_bRaster->getWrap();
274
275 m_displaceVector[0] = -m_bWrap - 1;
276 m_displaceVector[1] = -m_bWrap;
277 m_displaceVector[2] = -m_bWrap + 1;
278 m_displaceVector[3] = -1;
279 m_displaceVector[4] = +1;
280 m_displaceVector[5] = m_bWrap - 1;
281 m_displaceVector[6] = m_bWrap;
282 m_displaceVector[7] = m_bWrap + 1;
283
284 skeletonize(endpoints);
285
286 findMeetingPoints(endpoints, closingSegmentArray);
287 // copy(m_bRaster, raux);
288 braux->unlock();
289
290 }
291
292 catch (TException &e) {
293 throw e;
294 }
295 }
296
297 /*------------------------------------------------------------------------*/
298
draw(const std::vector<Segment> & closingSegmentArray)299 void TAutocloser::Imp::draw(const std::vector<Segment> &closingSegmentArray) {
300 TRasterCM32P raux;
301
302 if (!(raux = (TRasterCM32P)m_raster))
303 throw TException("Unable to autoclose a not CM32 image.");
304
305 if (m_raster->getLx() == 0 || m_raster->getLy() == 0)
306 throw TException("Autoclose error: bad image size");
307
308 for (int i = 0; i < (int)closingSegmentArray.size(); i++)
309 drawSegment(raux, closingSegmentArray[i], m_inkIndex, m_opacity);
310 }
311
312 /*------------------------------------------------------------------------*/
313
copy(const TRasterGR8P & br,TRaster32P & r)314 void TAutocloser::Imp::copy(const TRasterGR8P &br, TRaster32P &r) {
315 assert(r->getLx() == br->getLx() && r->getLy() == br->getLy());
316 int i, j;
317
318 int lx = r->getLx();
319 int ly = r->getLy();
320
321 UCHAR *bbuf = br->getRawData();
322 TPixel *buf = (TPixel *)r->getRawData();
323
324 for (i = 0; i < ly; i++) {
325 for (j = 0; j < lx; j++, buf++, bbuf++) {
326 buf->m = 255;
327 if ((*bbuf) & 0x40)
328 buf->r = 255, buf->g = buf->b = 0;
329 else if (isInk(bbuf))
330 buf->r = buf->g = buf->b = 0;
331 else
332 buf->r = buf->g = buf->b = 255;
333 }
334 buf += r->getWrap() - lx;
335 bbuf += br->getWrap() - lx;
336 }
337 }
338
339 /*=============================================================================*/
340
341 namespace {
342
intersect_segment(int x1,int y1,int x2,int y2,int i,double * ris)343 int intersect_segment(int x1, int y1, int x2, int y2, int i, double *ris) {
344 if ((i < std::min(y1, y2)) || (i > std::max(y1, y2)) || (y1 == y2)) return 0;
345
346 *ris = ((double)((x1 - x2) * (i - y2)) / (double)(y1 - y2) + x2);
347
348 return 1;
349 }
350
351 /*=============================================================================*/
352
distance2(const TPoint p0,const TPoint p1)353 inline int distance2(const TPoint p0, const TPoint p1) {
354 return (p0.x - p1.x) * (p0.x - p1.x) + (p0.y - p1.y) * (p0.y - p1.y);
355 }
356
357 /*=============================================================================*/
358
closerPoint(const std::vector<TAutocloser::Segment> & points,std::vector<bool> & marks,int index)359 int closerPoint(const std::vector<TAutocloser::Segment> &points,
360 std::vector<bool> &marks, int index) {
361 assert(points.size() == marks.size());
362
363 int min, curr;
364 int minval = (std::numeric_limits<int>::max)();
365
366 min = index + 1;
367
368 for (curr = index + 1; curr < (int)points.size(); curr++)
369 if (!(marks[curr])) {
370 int distance = distance2(points[index].first, points[curr].first);
371
372 if (distance < minval) {
373 minval = distance;
374 min = curr;
375 }
376 }
377
378 marks[min] = true;
379 return min;
380 }
381
382 /*------------------------------------------------------------------------*/
383
intersect_triangle(int x1a,int y1a,int x2a,int y2a,int x3a,int y3a,int x1b,int y1b,int x2b,int y2b,int x3b,int y3b)384 int intersect_triangle(int x1a, int y1a, int x2a, int y2a, int x3a, int y3a,
385 int x1b, int y1b, int x2b, int y2b, int x3b, int y3b) {
386 int minx, maxx, miny, maxy, i;
387 double xamin, xamax, xbmin, xbmax, val;
388
389 miny = std::max(std::min({y1a, y2a, y3a}), std::min({y1b, y2b, y3b}));
390 maxy = std::min(std::max({y1a, y2a, y3a}), std::max({y1b, y2b, y3b}));
391 if (maxy < miny) return 0;
392
393 minx = std::max(std::min({x1a, x2a, x3a}), std::min({x1b, x2b, x3b}));
394 maxx = std::min(std::max({x1a, x2a, x3a}), std::max({x1b, x2b, x3b}));
395 if (maxx < minx) return 0;
396
397 for (i = miny; i <= maxy; i++) {
398 xamin = xamax = xbmin = xbmax = 0.0;
399
400 intersect_segment(x1a, y1a, x2a, y2a, i, &xamin);
401
402 if (intersect_segment(x1a, y1a, x3a, y3a, i, &val)) {
403 if (xamin) {
404 xamax = val;
405 } else {
406 xamin = val;
407 }
408 }
409
410 if (!xamax) intersect_segment(x2a, y2a, x3a, y3a, i, &xamax);
411
412 if (xamax < xamin) {
413 val = xamin, xamin = xamax, xamax = val;
414 }
415
416 intersect_segment(x1b, y1b, x2b, y2b, i, &xbmin);
417
418 if (intersect_segment(x1b, y1b, x3b, y3b, i, &val)) {
419 if (xbmin) {
420 xbmax = val;
421 } else {
422 xbmin = val;
423 }
424 }
425
426 if (!xbmax) intersect_segment(x2b, y2b, x3b, y3b, i, &xbmax);
427
428 if (xbmax < xbmin) {
429 val = xbmin, xbmin = xbmax, xbmax = val;
430 }
431
432 if (!((tceil(xamax) < tfloor(xbmin)) || (tceil(xbmax) < tfloor(xamin))))
433 return 1;
434 }
435 return 0;
436 }
437
438 /*------------------------------------------------------------------------*/
439
440 } // namespace
441
442 /*------------------------------------------------------------------------*/
443
notInsidePath(const TPoint & p,const TPoint & q)444 int TAutocloser::Imp::notInsidePath(const TPoint &p, const TPoint &q) {
445 int tmp, x, y, dx, dy, d, incr_1, incr_2;
446 int x1, y1, x2, y2;
447
448 x1 = p.x;
449 y1 = p.y;
450 x2 = q.x;
451 y2 = q.y;
452
453 if (x1 > x2) {
454 tmp = x1, x1 = x2, x2 = tmp;
455 tmp = y1, y1 = y2, y2 = tmp;
456 }
457 UCHAR *br = getPtr(x1, y1);
458
459 dx = x2 - x1;
460 dy = y2 - y1;
461 x = y = 0;
462
463 if (dy >= 0) {
464 if (dy <= dx)
465 DRAW_SEGMENT(x, y, dx, dy, (br++), (br += m_bWrap + 1),
466 if (!((*br) & 0x2)) return true)
467 else
468 DRAW_SEGMENT(y, x, dy, dx, (br += m_bWrap), (br += m_bWrap + 1),
469 if (!((*br) & 0x2)) return true)
470 } else {
471 dy = -dy;
472 if (dy <= dx)
473 DRAW_SEGMENT(x, y, dx, dy, (br++), (br -= m_bWrap - 1),
474 if (!((*br) & 0x2)) return true)
475 else
476 DRAW_SEGMENT(y, x, dy, dx, (br -= m_bWrap), (br -= m_bWrap - 1),
477 if (!((*br) & 0x2)) return true)
478 }
479
480 return 0;
481 }
482
483 /*------------------------------------------------------------------------*/
484
exploreTwoSpots(const TAutocloser::Segment & s0,const TAutocloser::Segment & s1)485 int TAutocloser::Imp::exploreTwoSpots(const TAutocloser::Segment &s0,
486 const TAutocloser::Segment &s1) {
487 int x1a, y1a, x2a, y2a, x3a, y3a, x1b, y1b, x2b, y2b, x3b, y3b;
488
489 x1a = s0.first.x;
490 y1a = s0.first.y;
491 x1b = s1.first.x;
492 y1b = s1.first.y;
493
494 TPoint p0aux = s0.second;
495 TPoint p1aux = s1.second;
496
497 if (x1a == p0aux.x && y1a == p0aux.y) return 0;
498 if (x1b == p1aux.x && y1b == p1aux.y) return 0;
499
500 x2a = tround(x1a + (p0aux.x - x1a) * m_csp - (p0aux.y - y1a) * m_snp);
501 y2a = tround(y1a + (p0aux.x - x1a) * m_snp + (p0aux.y - y1a) * m_csp);
502 x3a = tround(x1a + (p0aux.x - x1a) * m_csm - (p0aux.y - y1a) * m_snm);
503 y3a = tround(y1a + (p0aux.x - x1a) * m_snm + (p0aux.y - y1a) * m_csm);
504
505 x2b = tround(x1b + (p1aux.x - x1b) * m_csp - (p1aux.y - y1b) * m_snp);
506 y2b = tround(y1b + (p1aux.x - x1b) * m_snp + (p1aux.y - y1b) * m_csp);
507 x3b = tround(x1b + (p1aux.x - x1b) * m_csm - (p1aux.y - y1b) * m_snm);
508 y3b = tround(y1b + (p1aux.x - x1b) * m_snm + (p1aux.y - y1b) * m_csm);
509
510 return (intersect_triangle(x1a, y1a, p0aux.x, p0aux.y, x2a, y2a, x1b, y1b,
511 p1aux.x, p1aux.y, x2b, y2b) ||
512 intersect_triangle(x1a, y1a, p0aux.x, p0aux.y, x3a, y3a, x1b, y1b,
513 p1aux.x, p1aux.y, x2b, y2b) ||
514 intersect_triangle(x1a, y1a, p0aux.x, p0aux.y, x2a, y2a, x1b, y1b,
515 p1aux.x, p1aux.y, x3b, y3b) ||
516 intersect_triangle(x1a, y1a, p0aux.x, p0aux.y, x3a, y3a, x1b, y1b,
517 p1aux.x, p1aux.y, x3b, y3b));
518 }
519
520 /*------------------------------------------------------------------------*/
521
findMeetingPoints(std::vector<TPoint> & endpoints,std::vector<Segment> & closingSegments)522 void TAutocloser::Imp::findMeetingPoints(
523 std::vector<TPoint> &endpoints, std::vector<Segment> &closingSegments) {
524 int i;
525 double alfa;
526 alfa = m_spotAngle / AUT_SPOT_SAMPLES;
527 m_csp = cos(m_spotAngle / 5);
528 m_snp = sin(m_spotAngle / 5);
529 m_csm = cos(-m_spotAngle / 5);
530 m_snm = sin(-m_spotAngle / 5);
531 m_csa = cos(alfa);
532 m_sna = sin(alfa);
533 m_csb = cos(-alfa);
534 m_snb = sin(-alfa);
535
536 std::vector<Segment> orientedEndpoints(endpoints.size());
537 for (i = 0; i < (int)endpoints.size(); i++)
538 orientedEndpoints[i].first = endpoints[i];
539
540 int size = -1;
541
542 while ((int)closingSegments.size() > size && !orientedEndpoints.empty()) {
543 size = closingSegments.size();
544 do
545 calculateWeightAndDirection(orientedEndpoints);
546 while (spotResearchTwoPoints(orientedEndpoints, closingSegments));
547
548 do
549 calculateWeightAndDirection(orientedEndpoints);
550 while (spotResearchOnePoint(orientedEndpoints, closingSegments));
551 }
552 }
553
554 /*------------------------------------------------------------------------*/
555
allMarked(const std::vector<bool> & marks,int index)556 static bool allMarked(const std::vector<bool> &marks, int index) {
557 int i;
558
559 for (i = index + 1; i < (int)marks.size(); i++)
560 if (!marks[i]) return false;
561 return true;
562 }
563
564 /*------------------------------------------------------------------------*/
565
spotResearchTwoPoints(std::vector<Segment> & endpoints,std::vector<Segment> & closingSegments)566 bool TAutocloser::Imp::spotResearchTwoPoints(
567 std::vector<Segment> &endpoints, std::vector<Segment> &closingSegments) {
568 int i, distance, current = 0, closerIndex;
569 int sqrDistance = m_closingDistance * m_closingDistance;
570 bool found = 0;
571 std::vector<bool> marks(endpoints.size());
572
573 while (current < (int)endpoints.size() - 1) {
574 found = 0;
575 for (i = current + 1; i < (int)marks.size(); i++) marks[i] = false;
576 distance = 0;
577
578 while (!found && (distance <= sqrDistance) && !allMarked(marks, current)) {
579 closerIndex = closerPoint(endpoints, marks, current);
580 if (exploreTwoSpots(endpoints[current], endpoints[closerIndex]) &&
581 notInsidePath(endpoints[current].first,
582 endpoints[closerIndex].first)) {
583 drawInByteRaster(endpoints[current].first,
584 endpoints[closerIndex].first);
585 closingSegments.push_back(
586 Segment(endpoints[current].first, endpoints[closerIndex].first));
587
588 if (!EndpointTable[neighboursCode(
589 getPtr(endpoints[closerIndex].first))]) {
590 std::vector<Segment>::iterator it = endpoints.begin();
591 std::advance(it, closerIndex);
592 endpoints.erase(it);
593 std::vector<bool>::iterator it1 = marks.begin();
594 std::advance(it1, closerIndex);
595 marks.erase(it1);
596 }
597 found = true;
598 }
599 }
600
601 if (found) {
602 std::vector<Segment>::iterator it = endpoints.begin();
603 std::advance(it, current);
604 endpoints.erase(it);
605 std::vector<bool>::iterator it1 = marks.begin();
606 std::advance(it1, current);
607 marks.erase(it1);
608 } else
609 current++;
610 }
611 return found;
612 }
613
614 /*------------------------------------------------------------------------*/
615 /*
616 static void clear_marks(POINT *p)
617 {
618 while (p)
619 {
620 p->mark = 0;
621 p = p->next;
622 }
623 }
624
625
626 static int there_are_unmarked(POINT *p)
627 {
628 while (p)
629 {
630 if (!p->mark) return 1;
631 p = p->next;
632 }
633 return 0;
634 }
635 */
636
637 /*------------------------------------------------------------------------*/
638
calculateWeightAndDirection(std::vector<Segment> & orientedEndpoints)639 void TAutocloser::Imp::calculateWeightAndDirection(
640 std::vector<Segment> &orientedEndpoints) {
641 // UCHAR *br;
642 int lx = m_raster->getLx();
643 int ly = m_raster->getLy();
644
645 std::vector<Segment>::iterator it = orientedEndpoints.begin();
646
647 while (it != orientedEndpoints.end()) {
648 TPoint p0 = it->first;
649 TPoint &p1 = it->second;
650
651 // br = (UCHAR *)m_bRaster->pixels(p0.y)+p0.x;
652 // code = neighboursCode(br);
653 /*if (!EndpointTable[code])
654 {
655 it = orientedEndpoints.erase(it);
656 continue;
657 }*/
658 TPoint displAverage = visitEndpoint(getPtr(p0));
659
660 p1 = p0 - displAverage;
661
662 /*if ((point->x2<0 && point->y2<0) || (point->x2>Lx && point->y2>Ly))
663 * printf("che palle!!!!!!\n");*/
664
665 if (p1.x < 0) {
666 p1.y = tround(p0.y - (float)((p0.y - p1.y) * p0.x) / (p0.x - p1.x));
667 p1.x = 0;
668 } else if (p1.x > lx) {
669 p1.y =
670 tround(p0.y - (float)((p0.y - p1.y) * (p0.x - lx)) / (p0.x - p1.x));
671 p1.x = lx;
672 }
673
674 if (p1.y < 0) {
675 p1.x = tround(p0.x - (float)((p0.x - p1.x) * p0.y) / (p0.y - p1.y));
676 p1.y = 0;
677 } else if (p1.y > ly) {
678 p1.x =
679 tround(p0.x - (float)((p0.x - p1.x) * (p0.y - ly)) / (p0.y - p1.y));
680 p1.y = ly;
681 }
682 it++;
683 }
684 }
685
686 /*------------------------------------------------------------------------*/
687
spotResearchOnePoint(std::vector<Segment> & endpoints,std::vector<Segment> & closingSegments)688 bool TAutocloser::Imp::spotResearchOnePoint(
689 std::vector<Segment> &endpoints, std::vector<Segment> &closingSegments) {
690 int count = 0;
691 bool ret = false;
692
693 while (count < (int)endpoints.size()) {
694 TPoint p;
695
696 if (exploreSpot(endpoints[count], p)) {
697 Segment segment(endpoints[count].first, p);
698 std::vector<Segment>::iterator it =
699 std::find(closingSegments.begin(), closingSegments.end(), segment);
700 if (it == closingSegments.end()) {
701 ret = true;
702 drawInByteRaster(endpoints[count].first, p);
703 closingSegments.push_back(Segment(endpoints[count].first, p));
704 cancelFromArray(endpoints, p, count);
705 if (!EndpointTable[neighboursCode(getPtr(endpoints[count].first))]) {
706 std::vector<Segment>::iterator it = endpoints.begin();
707 std::advance(it, count);
708 endpoints.erase(it);
709 continue;
710 }
711 }
712 }
713 count++;
714 }
715
716 return ret;
717 }
718
719 /*------------------------------------------------------------------------*/
720
exploreSpot(const Segment & s,TPoint & p)721 bool TAutocloser::Imp::exploreSpot(const Segment &s, TPoint &p) {
722 int x1, y1, x2, y2, x3, y3, i;
723 double x2a, y2a, x2b, y2b, xnewa, ynewa, xnewb, ynewb;
724 int lx = m_raster->getLx();
725 int ly = m_raster->getLy();
726
727 x1 = s.first.x;
728 y1 = s.first.y;
729 x2 = s.second.x;
730 y2 = s.second.y;
731
732 if (x1 == x2 && y1 == y2) return 0;
733
734 if (exploreRay(getPtr(x1, y1), s, p)) return true;
735
736 x2a = x2b = (double)x2;
737 y2a = y2b = (double)y2;
738
739 for (i = 0; i < AUT_SPOT_SAMPLES; i++) {
740 xnewa = x1 + (x2a - x1) * m_csa - (y2a - y1) * m_sna;
741 ynewa = y1 + (y2a - y1) * m_csa + (x2a - x1) * m_sna;
742 x3 = tround(xnewa);
743 y3 = tround(ynewa);
744 if ((x3 != tround(x2a) || y3 != tround(y2a)) && x3 > 0 && x3 < lx &&
745 y3 > 0 && y3 < ly &&
746 exploreRay(
747 getPtr(x1, y1),
748 Segment(TPoint(x1, y1), TPoint(tround(xnewa), tround(ynewa))), p))
749 return true;
750
751 x2a = xnewa;
752 y2a = ynewa;
753
754 xnewb = x1 + (x2b - x1) * m_csb - (y2b - y1) * m_snb;
755 ynewb = y1 + (y2b - y1) * m_csb + (x2b - x1) * m_snb;
756 x3 = tround(xnewb);
757 y3 = tround(ynewb);
758 if ((x3 != tround(x2b) || y3 != tround(y2b)) && x3 > 0 && x3 < lx &&
759 y3 > 0 && y3 < ly &&
760 exploreRay(
761 getPtr(x1, y1),
762 Segment(TPoint(x1, y1), TPoint(tround(xnewb), tround(ynewb))), p))
763 return true;
764
765 x2b = xnewb;
766 y2b = ynewb;
767 }
768 return false;
769 }
770
771 /*------------------------------------------------------------------------*/
772
exploreRay(UCHAR * br,Segment s,TPoint & p)773 bool TAutocloser::Imp::exploreRay(UCHAR *br, Segment s, TPoint &p) {
774 int x, y, dx, dy, d, incr_1, incr_2, inside_ink;
775
776 inside_ink = 1;
777
778 x = 0;
779 y = 0;
780
781 if (s.first.x < s.second.x) {
782 dx = s.second.x - s.first.x;
783 dy = s.second.y - s.first.y;
784 if (dy >= 0)
785 if (dy <= dx)
786 DRAW_SEGMENT(x, y, dx, dy, (br++), (br += m_bWrap + 1),
787 EXPLORE_RAY_ISTR((s.first.x + x)))
788 else
789 DRAW_SEGMENT(y, x, dy, dx, (br += m_bWrap), (br += m_bWrap + 1),
790 EXPLORE_RAY_ISTR((s.first.x + x)))
791 else {
792 dy = -dy;
793 if (dy <= dx)
794 DRAW_SEGMENT(x, y, dx, dy, (br++), (br -= m_bWrap - 1),
795 EXPLORE_RAY_ISTR((s.first.x + x)))
796 else
797 DRAW_SEGMENT(y, x, dy, dx, (br -= m_bWrap), (br -= m_bWrap - 1),
798 EXPLORE_RAY_ISTR((s.first.x + x)))
799 }
800 } else {
801 dx = s.first.x - s.second.x;
802 dy = s.second.y - s.first.y;
803 if (dy >= 0)
804 if (dy <= dx)
805 DRAW_SEGMENT(x, y, dx, dy, (br--), (br += m_bWrap - 1),
806 EXPLORE_RAY_ISTR((s.first.x - x)))
807 else
808 DRAW_SEGMENT(y, x, dy, dx, (br += m_bWrap), (br += m_bWrap - 1),
809 EXPLORE_RAY_ISTR((s.first.x - x)))
810 else {
811 dy = -dy;
812 if (dy <= dx)
813 DRAW_SEGMENT(x, y, dx, dy, (br--), (br -= m_bWrap + 1),
814 EXPLORE_RAY_ISTR((s.first.x - x)))
815 else
816 DRAW_SEGMENT(y, x, dy, dx, (br -= m_bWrap), (br -= m_bWrap + 1),
817 EXPLORE_RAY_ISTR((s.first.x - x)))
818 }
819 }
820 return false;
821 }
822
823 /*------------------------------------------------------------------------*/
824
drawInByteRaster(const TPoint & p0,const TPoint & p1)825 void TAutocloser::Imp::drawInByteRaster(const TPoint &p0, const TPoint &p1) {
826 int x, y, dx, dy, d, incr_1, incr_2;
827 UCHAR *br;
828
829 if (p0.x > p1.x) {
830 br = getPtr(p1);
831 dx = p0.x - p1.x;
832 dy = p0.y - p1.y;
833 } else {
834 br = getPtr(p0);
835 dx = p1.x - p0.x;
836 dy = p1.y - p0.y;
837 }
838
839 x = y = 0;
840
841 if (dy >= 0) {
842 if (dy <= dx)
843 DRAW_SEGMENT(x, y, dx, dy, (br++), (br += m_bWrap + 1), ((*br) |= 0x41))
844 else
845 DRAW_SEGMENT(y, x, dy, dx, (br += m_bWrap), (br += m_bWrap + 1),
846 ((*br) |= 0x41))
847 } else {
848 dy = -dy;
849 if (dy <= dx)
850 DRAW_SEGMENT(x, y, dx, dy, (br++), (br -= m_bWrap - 1), ((*br) |= 0x41))
851 else
852 DRAW_SEGMENT(y, x, dy, dx, (br -= m_bWrap), (br -= m_bWrap - 1),
853 ((*br) |= 0x41))
854 }
855 }
856
857 /*------------------------------------------------------------------------*/
858
visitEndpoint(UCHAR * br)859 TPoint TAutocloser::Imp::visitEndpoint(UCHAR *br)
860
861 {
862 m_displAverage = TPointD();
863
864 m_visited = 0;
865
866 visitPix(br, m_closingDistance, TPoint());
867 cancelMarks(br);
868
869 return TPoint(convert((1.0 / m_visited) * m_displAverage));
870 }
871
872 /*------------------------------------------------------------------------*/
873
visitPix(UCHAR * br,int toVisit,const TPoint & dis)874 void TAutocloser::Imp::visitPix(UCHAR *br, int toVisit, const TPoint &dis) {
875 UCHAR b = 0;
876 int i, pixToVisit = 0;
877
878 *br |= 0x10;
879 m_visited++;
880 m_displAverage.x += dis.x;
881 m_displAverage.y += dis.y;
882
883 toVisit--;
884 if (toVisit == 0) return;
885
886 for (i = 0; i < 8; i++) {
887 UCHAR *v = br + m_displaceVector[i];
888 if (isInk(v) && !((*v) & 0x10)) {
889 b |= (1 << i);
890 pixToVisit++;
891 }
892 }
893
894 if (pixToVisit == 0) return;
895
896 if (pixToVisit <= 4) toVisit = troundp(toVisit / (double)pixToVisit);
897
898 if (toVisit == 0) return;
899
900 int x[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
901 int y[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
902
903 for (i = 0; i < 8; i++)
904 if (b & (1 << i))
905 visitPix(br + m_displaceVector[i], toVisit, dis + TPoint(x[i], y[i]));
906 }
907
908 /*------------------------------------------------------------------------*/
909
cancelMarks(UCHAR * br)910 void TAutocloser::Imp::cancelMarks(UCHAR *br) {
911 *br &= 0xef;
912 int i;
913
914 for (i = 0; i < 8; i++) {
915 UCHAR *v = br + m_displaceVector[i];
916
917 if (isInk(v) && (*v) & 0x10) cancelMarks(v);
918 }
919 }
920
921 /*=============================================================================*/
922
923 /*=============================================================================*/
924 /*=============================================================================*/
925 /*=============================================================================*/
926 /*=============================================================================*/
927 /*=============================================================================*/
928 /*=============================================================================*/
929 /*=============================================================================*/
930 /*=============================================================================*/
931 /*=============================================================================*/
932 /*=============================================================================*/
933
934 /*=============================================================================*/
935
skeletonize(std::vector<TPoint> & endpoints)936 void TAutocloser::Imp::skeletonize(std::vector<TPoint> &endpoints) {
937 std::vector<Seed> seeds;
938
939 findSeeds(seeds, endpoints);
940
941 erase(seeds, endpoints);
942 }
943
944 /*------------------------------------------------------------------------*/
945
findSeeds(std::vector<Seed> & seeds,std::vector<TPoint> & endpoints)946 void TAutocloser::Imp::findSeeds(std::vector<Seed> &seeds,
947 std::vector<TPoint> &endpoints) {
948 int i, j;
949 UCHAR preseed;
950
951 UCHAR *br = m_br;
952
953 for (i = 0; i < m_bRaster->getLy(); i++) {
954 for (j = 0; j < m_bRaster->getLx(); j++, br++) {
955 if (notMarkedBorderInk(br)) {
956 preseed = FirstPreseedTable[neighboursCode(br)];
957
958 if (preseed != 8) /*non e' un pixel isolato*/
959 {
960 seeds.push_back(Seed(br, preseed));
961 circuitAndMark(br, preseed);
962 } else {
963 (*br) |= 0x8;
964 endpoints.push_back(getCoordinates(br));
965 }
966 }
967 }
968 br += m_bWrap - m_bRaster->getLx();
969 }
970 }
971
972 /*------------------------------------------------------------------------*/
973
circuitAndMark(UCHAR * seed,UCHAR preseed)974 void TAutocloser::Imp::circuitAndMark(UCHAR *seed, UCHAR preseed) {
975 UCHAR *walker;
976 UCHAR displ, prewalker;
977
978 *seed |= 0x4;
979
980 displ = NextPointTable[(neighboursCode(seed) << 3) | preseed];
981 // assert(displ>=0 && displ<8);
982
983 walker = seed + m_displaceVector[displ];
984 prewalker = displ ^ 0x7;
985
986 while ((walker != seed) || (preseed != prewalker)) {
987 *walker |= 0x4; /* metto la marca di passaggio */
988
989 displ = NextPointTable[(neighboursCode(walker) << 3) | prewalker];
990 // assert(displ>=0 && displ<8);
991 walker += m_displaceVector[displ];
992 prewalker = displ ^ 0x7;
993 }
994
995 return;
996 }
997
998 /*------------------------------------------------------------------------*/
999
erase(std::vector<Seed> & seeds,std::vector<TPoint> & endpoints)1000 void TAutocloser::Imp::erase(std::vector<Seed> &seeds,
1001 std::vector<TPoint> &endpoints) {
1002 int i, size = 0, oldSize;
1003 UCHAR *seed, preseed, code, displ;
1004 oldSize = seeds.size();
1005
1006 while (oldSize != size) {
1007 oldSize = size;
1008 size = seeds.size();
1009
1010 for (i = oldSize; i < size; i++) {
1011 seed = seeds[i].m_ptr;
1012 preseed = seeds[i].m_preseed;
1013
1014 if (!isInk(seed)) {
1015 code = NextSeedTable[neighboursCode(seed)];
1016 seed += m_displaceVector[code & 0x7];
1017 preseed = (code & 0x38) >> 3;
1018 }
1019
1020 if (circuitAndCancel(seed, preseed, endpoints)) {
1021 if (isInk(seed)) {
1022 displ = NextPointTable[(neighboursCode(seed) << 3) | preseed];
1023 // assert(displ>=0 && displ<8);
1024 seeds.push_back(Seed(seed + m_displaceVector[displ], displ ^ 0x7));
1025
1026 } else /* il seed e' stato cancellato */
1027 {
1028 code = NextSeedTable[neighboursCode(seed)];
1029 seeds.push_back(
1030 Seed(seed + m_displaceVector[code & 0x7], (code & 0x38) >> 3));
1031 }
1032 }
1033 }
1034 }
1035 }
1036
1037 /*------------------------------------------------------------------------*/
1038
circuitAndCancel(UCHAR * seed,UCHAR preseed,std::vector<TPoint> & endpoints)1039 bool TAutocloser::Imp::circuitAndCancel(UCHAR *seed, UCHAR preseed,
1040 std::vector<TPoint> &endpoints) {
1041 UCHAR *walker, *previous;
1042 UCHAR displ, prewalker;
1043 bool ret = false;
1044
1045 displ = NextPointTable[(neighboursCode(seed) << 3) | preseed];
1046 // assert(displ>=0 && displ<8);
1047
1048 if ((displ == preseed) && !((*seed) & 0x8)) {
1049 endpoints.push_back(getCoordinates(seed));
1050 *seed |= 0x8;
1051 }
1052
1053 walker = seed + m_displaceVector[displ];
1054 prewalker = displ ^ 0x7;
1055
1056 while ((walker != seed) || (preseed != prewalker)) {
1057 // assert(prewalker>=0 && prewalker<8);
1058 displ = NextPointTable[(neighboursCode(walker) << 3) | prewalker];
1059 // assert(displ>=0 && displ<8);
1060
1061 if ((displ == prewalker) && !((*walker) & 0x8)) {
1062 endpoints.push_back(getCoordinates(walker));
1063 *walker |= 0x8;
1064 }
1065 previous = walker + m_displaceVector[prewalker];
1066 if (ConnectionTable[neighboursCode(previous)]) {
1067 ret = true;
1068 if (previous != seed) eraseInk(previous);
1069 }
1070 walker += m_displaceVector[displ];
1071 prewalker = displ ^ 0x7;
1072 }
1073
1074 displ = NextPointTable[(neighboursCode(walker) << 3) | prewalker];
1075
1076 if ((displ == preseed) && !((*seed) & 0x8)) {
1077 endpoints.push_back(getCoordinates(seed));
1078 *seed |= 0x8;
1079 }
1080
1081 if (ConnectionTable[neighboursCode(seed + m_displaceVector[preseed])]) {
1082 ret = true;
1083 eraseInk(seed + m_displaceVector[preseed]);
1084 }
1085
1086 if (ConnectionTable[neighboursCode(seed)]) {
1087 ret = true;
1088 eraseInk(seed);
1089 }
1090
1091 return ret;
1092 }
1093
1094 /*=============================================================================*/
1095
cancelFromArray(std::vector<Segment> & array,TPoint p,int & count)1096 void TAutocloser::Imp::cancelFromArray(std::vector<Segment> &array, TPoint p,
1097 int &count) {
1098 std::vector<Segment>::iterator it = array.begin();
1099 int i = 0;
1100
1101 for (; it != array.end(); ++it, i++)
1102 if (it->first == p) {
1103 if (!EndpointTable[neighboursCode(getPtr(p))]) {
1104 assert(i != count);
1105 if (i < count) count--;
1106 array.erase(it);
1107 }
1108 return;
1109 }
1110 }
1111
1112 /*------------------------------------------------------------------------*/
1113 /*
1114 int is_in_list(LIST list, UCHAR *br)
1115 {
1116 POINT *aux;
1117 aux = list.head;
1118
1119 while(aux)
1120 {
1121 if (aux->p == br) return 1;
1122 aux = aux->next;
1123 }
1124 return 0;
1125 }
1126 */
1127
1128 /*=============================================================================*/
1129
TAutocloser(const TRasterP & r,int distance,double angle,int index,int opacity)1130 TAutocloser::TAutocloser(const TRasterP &r, int distance, double angle,
1131 int index, int opacity)
1132 : m_imp(new Imp(r, distance, angle, index, opacity)) {}
1133
1134 //...............................
1135
exec()1136 void TAutocloser::exec() {
1137 std::vector<TAutocloser::Segment> segments;
1138 compute(segments);
1139 draw(segments);
1140 }
1141
1142 //...............................
1143
~TAutocloser()1144 TAutocloser::~TAutocloser() {}
1145
1146 //-------------------------------------------------
1147
compute(std::vector<Segment> & closingSegmentArray)1148 void TAutocloser::compute(std::vector<Segment> &closingSegmentArray) {
1149 m_imp->compute(closingSegmentArray);
1150 }
1151 //-------------------------------------------------
1152
draw(const std::vector<Segment> & closingSegmentArray)1153 void TAutocloser::draw(const std::vector<Segment> &closingSegmentArray) {
1154 m_imp->draw(closingSegmentArray);
1155 }
1156