1 /*
2  *  Copyright (c) 2004 Boudewijn Rempt <boud@valdyas.org>
3  *  Copyright (c) 2007,2010 Sven Langkamp <sven.langkamp@gmail.com>
4  *
5  *  Outline algorithm based of the limn of fontutils
6  *  Copyright (c) 1992 Karl Berry <karl@cs.umb.edu>
7  *  Copyright (c) 1992 Kathryn Hargreaves <letters@cs.umb.edu>
8  *
9  *  This program is free software; you can redistribute it and/or modify
10  *  it under the terms of the GNU General Public License as published by
11  *  the Free Software Foundation; either version 2 of the License, or
12  *  (at your option) any later version.
13  *
14  *  This program is distributed in the hope that it will be useful,
15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  *  GNU General Public License for more details.
18  *
19  *  You should have received a copy of the GNU General Public License
20  *  along with this program; if not, write to the Free Software
21  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
22  */
23 
24 #include "kis_outline_generator.h"
25 #include <KoColorSpace.h>
26 #include <KoColorSpaceRegistry.h>
27 
28 #include "kis_paint_device.h"
29 #include <kis_iterator_ng.h>
30 #include <kis_random_accessor_ng.h>
31 
32 class LinearStorage
33 {
34 public:
35     typedef quint8* StorageType;
36 public:
LinearStorage(quint8 * buffer,int width,int height,int pixelSize)37     LinearStorage(quint8 *buffer, int width, int height, int pixelSize)
38         : m_buffer(buffer),
39           m_width(width),
40           m_pixelSize(pixelSize)
41     {
42         m_marks.reset(new quint8[width * height]);
43         memset(m_marks.data(), 0, width * height);
44     }
45 
pickPixel(int x,int y)46     quint8* pickPixel(int x, int y) {
47         return m_buffer + (m_width * y + x) * m_pixelSize;
48     }
49 
pickMark(int x,int y)50     quint8* pickMark(int x, int y) {
51         return m_marks.data() + m_width * y + x;
52     }
53 
54 private:
55     QScopedArrayPointer<quint8> m_marks;
56     quint8 *m_buffer;
57     int m_width;
58     int m_pixelSize;
59 };
60 
61 class PaintDeviceStorage
62 {
63 public:
64     typedef const KisPaintDevice* StorageType;
65 public:
PaintDeviceStorage(const KisPaintDevice * device,int,int,int)66     PaintDeviceStorage(const KisPaintDevice *device, int /*width*/, int /*height*/, int /*pixelSize*/)
67         : m_device(device)
68     {
69         m_deviceIt = m_device->createRandomConstAccessorNG();
70 
71         const KoColorSpace *alphaCs = KoColorSpaceRegistry::instance()->alpha8();
72         m_marks = new KisPaintDevice(alphaCs);
73         m_marksIt = m_marks->createRandomAccessorNG();
74     }
75 
pickPixel(int x,int y)76     const quint8* pickPixel(int x, int y) {
77         m_deviceIt->moveTo(x, y);
78         return m_deviceIt->rawDataConst();
79     }
80 
pickMark(int x,int y)81     quint8* pickMark(int x, int y) {
82         m_marksIt->moveTo(x, y);
83         return m_marksIt->rawData();
84     }
85 
86 private:
87     KisPaintDeviceSP m_marks;
88     const KisPaintDevice *m_device;
89     KisRandomConstAccessorSP m_deviceIt;
90     KisRandomAccessorSP m_marksIt;
91 };
92 
93 
94 /******************* class KisOutlineGenerator *******************/
95 
KisOutlineGenerator(const KoColorSpace * cs,quint8 defaultOpacity)96 KisOutlineGenerator::KisOutlineGenerator(const KoColorSpace* cs, quint8 defaultOpacity)
97     : m_cs(cs), m_defaultOpacity(defaultOpacity), m_simple(false)
98 {
99 }
100 
101 template <class StorageStrategy>
outlineImpl(typename StorageStrategy::StorageType buffer,qint32 xOffset,qint32 yOffset,qint32 width,qint32 height)102 QVector<QPolygon> KisOutlineGenerator::outlineImpl(typename StorageStrategy::StorageType buffer,
103                                                    qint32 xOffset, qint32 yOffset,
104                                                    qint32 width, qint32 height)
105 {
106     QVector<QPolygon> paths;
107 
108     try {
109         StorageStrategy storage(buffer, width, height, m_cs->pixelSize());
110 
111         for (qint32 y = 0; y < height; y++) {
112             for (qint32 x = 0; x < width; x++) {
113 
114                 if (m_cs->opacityU8(storage.pickPixel(x, y)) == m_defaultOpacity)
115                     continue;
116 
117                 const EdgeType initialEdge = TopEdge;
118 
119                 EdgeType startEdge = initialEdge;
120                 while (startEdge != NoEdge &&
121                        (*storage.pickMark(x, y) & (1 << startEdge) ||
122                         !isOutlineEdge(storage, startEdge, x, y, width, height))) {
123 
124                     startEdge = nextEdge(startEdge);
125                     if (startEdge == initialEdge)
126                         startEdge = NoEdge;
127                 }
128 
129                 if (startEdge != NoEdge) {
130                     QPolygon path;
131                     const bool clockwise = startEdge == BottomEdge;
132 
133                     qint32 row = y, col = x;
134                     EdgeType currentEdge = startEdge;
135                     EdgeType lastEdge = NoEdge;
136 
137                     if (currentEdge == BottomEdge) {
138                         appendCoordinate(&path, col + xOffset, row + yOffset, currentEdge, lastEdge);
139                         lastEdge = BottomEdge;
140                     }
141 
142                     forever {
143                         //qDebug() << "visit" << xOffset + col << yOffset + row << ppVar(currentEdge) << ppVar(lastEdge);
144 
145                         *storage.pickMark(col, row) |= 1 << currentEdge;
146                         nextOutlineEdge(storage, &currentEdge, &row, &col, width, height);
147 
148                         //While following a straight line no points need to be added
149                         if (lastEdge != currentEdge) {
150                             appendCoordinate(&path, col + xOffset, row + yOffset, currentEdge, lastEdge);
151                             lastEdge = currentEdge;
152                         }
153 
154                         if (row == y && col == x && currentEdge == startEdge) {
155                             if (startEdge != BottomEdge) {
156                                 // add last point of the polygon
157                                 appendCoordinate(&path, col + xOffset, row + yOffset, NoEdge, NoEdge);
158                             }
159                             break;
160                         }
161                     }
162 
163                     if(!m_simple || !clockwise) {
164                         paths.push_back(path);
165                     }
166                 }
167             }
168         }
169     }
170     catch(const std::bad_alloc&) {
171         warnKrita << "KisOutlineGenerator::outline ran out of memory allocating " <<  width << "*" << height << "marks";
172     }
173 
174     return paths;
175 }
176 
outline(quint8 * buffer,qint32 xOffset,qint32 yOffset,qint32 width,qint32 height)177 QVector<QPolygon> KisOutlineGenerator::outline(quint8* buffer, qint32 xOffset, qint32 yOffset, qint32 width, qint32 height)
178 {
179     return outlineImpl<LinearStorage>(buffer, xOffset, yOffset, width, height);
180 }
181 
outline(const KisPaintDevice * buffer,qint32 xOffset,qint32 yOffset,qint32 width,qint32 height)182 QVector<QPolygon> KisOutlineGenerator::outline(const KisPaintDevice *buffer, qint32 xOffset, qint32 yOffset, qint32 width, qint32 height)
183 {
184     return outlineImpl<PaintDeviceStorage>(buffer, xOffset, yOffset, width, height);
185 }
186 
187 template <class StorageStrategy>
isOutlineEdge(StorageStrategy & storage,EdgeType edge,qint32 x,qint32 y,qint32 bufWidth,qint32 bufHeight)188 bool KisOutlineGenerator::isOutlineEdge(StorageStrategy &storage, EdgeType edge, qint32 x, qint32 y, qint32 bufWidth, qint32 bufHeight)
189 {
190     if (m_cs->opacityU8(storage.pickPixel(x, y)) == m_defaultOpacity)
191         return false;
192 
193     switch (edge) {
194     case LeftEdge:
195         return x == 0 || m_cs->opacityU8(storage.pickPixel(x - 1, y)) == m_defaultOpacity;
196     case TopEdge:
197         return y == 0 || m_cs->opacityU8(storage.pickPixel(x, y - 1)) == m_defaultOpacity;
198     case RightEdge:
199         return x == bufWidth - 1 || m_cs->opacityU8(storage.pickPixel(x + 1, y)) == m_defaultOpacity;
200     case BottomEdge:
201         return y == bufHeight - 1 || m_cs->opacityU8(storage.pickPixel(x, y + 1)) == m_defaultOpacity;
202     case NoEdge:
203         return false;
204     }
205     return false;
206 }
207 
208 #define TRY_PIXEL(deltaRow, deltaCol, test_edge)                                                \
209     {                                                                                               \
210         int test_row = *row + deltaRow;                                                             \
211         int test_col = *col + deltaCol;                                                             \
212         if ( (0 <= (test_row) && (test_row) < height && 0 <= (test_col) && (test_col) < width) &&   \
213              isOutlineEdge (storage, test_edge, test_col, test_row, width, height)) \
214         {                                                                                           \
215             *row = test_row;                                                                        \
216             *col = test_col;                                                                        \
217             *edge = test_edge;                                                                      \
218             break;                                                                                  \
219         }                                                                                       \
220     }
221 
222 template <class StorageStrategy>
nextOutlineEdge(StorageStrategy & storage,EdgeType * edge,qint32 * row,qint32 * col,qint32 width,qint32 height)223 void KisOutlineGenerator::nextOutlineEdge(StorageStrategy &storage, EdgeType *edge, qint32 *row, qint32 *col, qint32 width, qint32 height)
224 {
225     int original_row = *row;
226     int original_col = *col;
227 
228     switch (*edge) {
229     case RightEdge:
230         TRY_PIXEL(-1, 0, RightEdge);
231         TRY_PIXEL(-1, 1, BottomEdge);
232         break;
233 
234     case TopEdge:
235         TRY_PIXEL(0, -1, TopEdge);
236         TRY_PIXEL(-1, -1, RightEdge);
237         break;
238 
239     case LeftEdge:
240         TRY_PIXEL(1, 0, LeftEdge);
241         TRY_PIXEL(1, -1, TopEdge);
242         break;
243 
244     case BottomEdge:
245         TRY_PIXEL(0, 1, BottomEdge);
246         TRY_PIXEL(1, 1, LeftEdge);
247         break;
248 
249     default:
250         break;
251 
252     }
253 
254     if (*row == original_row && *col == original_col)
255         *edge = nextEdge(*edge);
256 }
257 
appendCoordinate(QPolygon * path,int x,int y,EdgeType edge,EdgeType prevEdge)258 void KisOutlineGenerator::appendCoordinate(QPolygon * path, int x, int y, EdgeType edge, EdgeType prevEdge)
259 {
260     Q_UNUSED(prevEdge);
261 
262     //const QPoint origPt(x, y);
263 
264     if (edge == TopEdge) {
265         x++;
266     } else if (edge == BottomEdge) {
267         y++;
268     } else if (edge == RightEdge) {
269         x++;
270         y++;
271     }
272 
273     //qDebug() <<"add" << ppVar(origPt) << ppVar(edge) << ppVar(prevEdge) << "-->" << QPoint(x, y);
274 
275     *path << QPoint(x, y);
276 }
277 
setSimpleOutline(bool simple)278 void KisOutlineGenerator::setSimpleOutline(bool simple)
279 {
280     m_simple = simple;
281 }
282