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, ¤tEdge, &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