1// Aseprite Document Library
2// Copyright (c) 2019-2020 Igara Studio S.A.
3// Copyright (c) 2001-2014 David Capello
4//
5// This file is released under the terms of the MIT license.
6// Read LICENSE.txt for more information.
7
8#ifdef HAVE_CONFIG_H
9#include "config.h"
10#endif
11
12#include "base/debug.h"
13#include "doc/algo.h"
14#include "doc/algorithm/polygon.h"
15
16#include "gfx/point.h"
17
18#include <algorithm>
19#include <vector>
20
21namespace doc {
22
23static void addPointsWithoutDuplicatingLastOne(int x, int y, std::vector<gfx::Point>* pts)
24{
25 const gfx::Point newPoint(x, y);
26 if (pts->empty() ||
27 *(pts->end()-1) != newPoint) {
28 pts->push_back(newPoint);
29 }
30}
31
32// createUnion() joins a single scan point "x" (a pixel in other words)
33// to the input vector "pairs".
34// Each pair "pairs[i], pairs[i+1]" is a representation
35// of a horizontal scan segment "i".
36// An added scan point "x" to the "pairs" vector is represented
37// by two consecutive values of "x" if it is an insolated point.
38// If "x" is between or next to a scan segment, this function creates an
39// union, making a fusion between "x" <-> "pairs[i], pairs[i+1]".
40// Additionally, after the union step, this function handles
41// overlapped situations respect to the nexts scan segments "i+2",
42// "i+4", etc.
43// Note: "pairs" must be sorted prior execution of this function.
44bool algorithm::createUnion(std::vector<int>& pairs,
45 const int x,
46 int& ints)
47{
48 if (ints == 0) {
49 pairs.insert(pairs.begin(), 2, x);
50 ints = 2;
51 return true;
52 }
53 else if (pairs.size() < ints || ints == 1) {
54 // Error
55 return false;
56 }
57 else if (ints%2 == 1)
58 ints--;
59
60 for (int i=0; i < ints; i+=2) {
61 // Case: pairs[i] pairs[i+1]
62 // O --------- O
63 // -x-
64 if (x == pairs[i] - 1) {
65 pairs[i] = x;
66 return true;
67 }
68 // Case: pairs[i] pairs[i+1]
69 // O --------- O
70 // -x-
71 else if (x < pairs[i] - 1) {
72 pairs.insert(pairs.begin() + i, 2, x);
73 ints += 2;
74 return true;
75 }
76 // Case: pairs[i] pairs[i+1]
77 // O --------- O
78 // -x-
79 // or -x-
80 else if (x == pairs[i+1] + 1 || x == pairs[i+1]) {
81 pairs[i+1] = x;
82 while (ints > i+2 && pairs[i+2] <= x+1) {
83 pairs.erase(pairs.begin() + (i+1));
84 pairs.erase(pairs.begin() + (i+1));
85 ints -= 2;
86 if (i+2 >= pairs.size())
87 break;
88 }
89 return true;
90 }
91 // Case: pairs[i] pairs[i+1]
92 // O --------- O
93 // -x-
94 else if (x >= pairs[i] && x < pairs[i+1])
95 return true;
96 }
97 // Case: pairs[i] pairs[i+1]
98 // O --------- O
99 // -x-
100 if (x > pairs[ints-1]) {
101 pairs.insert(pairs.begin() + ints, 2, x);
102 ints += 2;
103 return true;
104 }
105 return false;
106}
107
108void algorithm::polygon(int vertices, const int* points, void* data, AlgoHLine proc)
109{
110 if (!vertices)
111 return;
112
113 // We load locally the points to "verts" and remove the duplicate points
114 // to manage easily the input vector, by the way, we find
115 // "ymin" and "ymax" to use them later like vertical scan limits
116 // on the scan line loop.
117 int ymin = *(points+1);
118 int ymax = *(points+1);
119 std::vector<gfx::Point> verts(1);
120 verts[0].x = *points;
121 verts[0].y = *(points+1);
122 int verticesAux = vertices;
123 for (int i=2; i < vertices*2; i+=2) {
124 int last = verts.size() - 1;
125 if (verts[last].x == *(points+i) && verts[last].y == *(points + (i+1))) {
126 verticesAux--;
127 continue;
128 }
129 verts.push_back(gfx::Point(*(points + i), *(points + (i+1))));
130 ASSERT(last + 1 == verts.size() - 1);
131 if (verts[last+1].y < ymin)
132 ymin = verts[last+1].y;
133 if (verts[last+1].y > ymax)
134 ymax = verts[last+1].y;
135 }
136 vertices = verticesAux;
137
138 std::vector<gfx::Point> pts;
139 for (int c=0; c < verts.size(); ++c) {
140 if (c == verts.size() - 1) {
141 algo_line_continuous(verts[verts.size()-1].x,
142 verts[verts.size()-1].y,
143 verts[0].x,
144 verts[0].y,
145 (void*)&pts,
146 (AlgoPixel)&addPointsWithoutDuplicatingLastOne);
147 // Consideration when we want to draw a simple pixel with contour tool
148 // dragging the cursor inside of a pixel (in this case pts contains
149 // just one element, which want to preserve).
150 if (pts.size() > 1)
151 // We remove the last point which is a duplicate point of
152 // the "pts" first element.
153 pts.pop_back();
154 }
155 else {
156 algo_line_continuous(verts[c].x,
157 verts[c].y,
158 verts[c+1].x,
159 verts[c+1].y,
160 (void*)&pts,
161 (AlgoPixel)&addPointsWithoutDuplicatingLastOne);
162 }
163 }
164
165 // Scan Line Loop:
166 int y;
167 int x1, y1;
168 int x2, y2;
169 int ind1, ind2;
170 int ints;
171 std::vector<int> polyInts(pts.size());
172 for (y = ymin; y <= ymax; y++) {
173 ints = 0;
174 for (int i=0; i < pts.size(); i++) {
175 if (!i) {
176 ind1 = pts.size() - 1;
177 ind2 = 0;
178 }
179 else {
180 ind1 = i - 1;
181 ind2 = i;
182 }
183 y1 = pts[ind1].y;
184 y2 = pts[ind2].y;
185 if (y1 < y2) {
186 x1 = pts[ind1].x;
187 x2 = pts[ind2].x;
188 }
189 else if (y1 > y2) {
190 y2 = pts[ind1].y;
191 y1 = pts[ind2].y;
192 x2 = pts[ind1].x;
193 x1 = pts[ind2].x;
194 }
195 else
196 continue;
197
198 if ((y >= y1 && y < y2) ||
199 (y == ymax && y > y1 && y <= y2)) {
200 polyInts[ints] = (int) ((float)((y - y1)*(x2 - x1)) / (float)(y2 - y1) + 0.5f + (float)x1);
201 ints++;
202 }
203 }
204
205 std::sort(polyInts.begin(), polyInts.begin() + ints);
206
207 for (int i=0; i < pts.size(); i++) {
208 if (pts[i].y == y)
209 createUnion(polyInts, pts[i].x, ints);
210 }
211
212 for (int i=0; i < ints; i+=2)
213 proc(polyInts[i], y, polyInts[i+1], data);
214 }
215}
216
217} // namespace doc
218