Gorgon Game Engine
Polygon.h
Go to the documentation of this file.
1 #pragma once
2 
3 #include "../Types.h"
4 #include "../Graphics/Bitmap.h"
5 #include "../Graphics/Color.h"
6 #include "../Containers/Image.h"
7 #include "../CGI.h"
8 #include "../Geometry/PointList.h"
9 #include "../Geometry/Line.h"
10 #include "../Containers/Collection.h"
11 
12 #include <cmath>
13 
14 
15 namespace Gorgon { namespace CGI {
16 
18  namespace internal {
19  struct vertexinfo {
20  vertexinfo() = default;
21 
22  vertexinfo (Float first, Float second, int list) :
23  first(first), second(second), list(list)
24  { }
25 
26  Float first, second;
27  int list;
28  bool skip = false;
29  int wind = false;
30  };
31 
32  template<class PL_, class F_, class T_>
33  void findpolylinestofill(const PL_ &pointlist, T_ ymin, T_ ymax, F_ fn, T_ step = 1, T_ cover = 1) {
34  using std::swap;
35 
36  for(T_ y = ymin; y<ymax; y += step) {
37  T_ nexty = y + cover;
38 
39  std::vector<vertexinfo> xpoints;
40 
41  int listind = 0;
42  for(const auto &points : pointlist) {
43  int N = (int)points.GetSize();
44 
45  if(N <= 1) continue;
46 
47  int off = 0;
48  //trackback until the line that is not touching this scanline
49  while(off > -N) {
50  auto line = points.GetLine(off);
51 
52  if(line.End.Y < nexty && line.End.Y > y) {
53  off--;
54  }
55  if(line.Start.Y < nexty && line.Start.Y > y) {
56  off--;
57  }
58  else
59  break;
60  }
61 
62  if(off == -N)
63  continue;
64 
65 
66  bool connected = false, wasconnected = false;
67  int firstdir = 0, lastdir = 0;
68  for(int i=off; i<N+off; i++) {
69  auto line = points.GetLine(i);
70 
71  if(line.MinY() < nexty && line.MaxY() > y) {
72  auto line = points.GetLine(i);
73 
74  auto slope = line.SlopeInv();
75  auto offset= line.OffsetInv();
76 
77  Float x1, x2;
78 
79  if(std::isinf(slope)) {
80  x1 = line.Start.X;
81  x2 = line.End.X;
82  }
83  else {
84  x1 = slope * y + offset;
85  x2 = slope * nexty + offset;
86  }
87 
88  if(x1 > x2)
89  swap(x1, x2);
90 
91  if(x1 < line.MinX())
92  x1 = line.MinX();
93 
94  if(x2 > line.MaxX())
95  x2 = line.MaxX();
96 
97  if(connected) {
98  auto &f = xpoints.back().first;
99  f = f > x1 ? x1 : f;
100 
101  auto &s = xpoints.back().second;
102  s = s < x2 ? x2 : s;
103  }
104  else {
105  if(wasconnected && lastdir != firstdir) { //change in direction
106  xpoints.back().skip= true;
107  }
108 
109  firstdir = line.YDirection();
110  xpoints.push_back({x1, x2, listind});
111  xpoints.back().wind = firstdir;
112  }
113 
114  lastdir = line.YDirection();
115 
116  wasconnected = connected;
117  connected = line.End.Y <= nexty && line.End.Y >= y;
118  }
119  else {
120  if(wasconnected && lastdir != firstdir) { //change in direction
121  xpoints.back().skip= true;
122  //xpoints.back().wind = 0;
123  }
124  connected = false;
125  }
126  }
127 
128  if(wasconnected && lastdir != firstdir) { //change in direction
129  xpoints.back().skip= true;
130  //xpoints.back().wind = 0;
131  }
132 
133  listind++;
134  }
135 
136  std::sort(xpoints.begin(), xpoints.end(), [](auto l, auto r) { return l.second < r.second; });
137 
138  //join overlapping x sections
139  /*for(int i=0; i<(int)xpoints.size()-1; i++) {
140  if(xpoints[i].second >= xpoints[i+1].first) {
141  //join
142  xpoints[i+1].first = xpoints[i].first; //sorted
143  xpoints[i].second = xpoints[i].second > xpoints[i+1].second ? xpoints[i].second : xpoints[i+1].second;
144  xpoints[i+1].second= xpoints[i].second;
145  }
146  }*/
147 
148  //fill
149  fn((Float)y, xpoints);
150  }
151  }
152  }
154 
163  template<int S_ = 8, int W_ = 1, class P_= Geometry::Pointf, class F_ = SolidFill<>>
164  void Polyfill(Containers::Image &target, const std::vector<Geometry::PointList<P_>> &p, F_ fill = SolidFill<>{Graphics::Color::Black}) {
165  if(p.size() < 1) return;
166 
167  std::vector<Geometry::PointList<P_>> p2;
168  const std::vector<Geometry::PointList<P_>> *pp;
169 
170  if(S_ > 1) {
171  for(auto &pl : p) {
172  p2.push_back(pl.Duplicate());
173  }
174  pp = &p2;
175  }
176  else {
177  pp = &p;
178  }
179 
180  const std::vector<Geometry::PointList<P_>> &points = *pp;
181 
182 
183  Float ymin = (Float)int(target.GetHeight()*S_ - 1);
184  Float ymax = 0;
185  int xmin = int(target.GetWidth()*S_ - 1);
186  int xmax = 0;
187  bool found = false;
188 
189  for(const auto &p : points) {
190  if(p.GetSize() <= 0) continue;
191 
192  auto yrange = std::minmax_element(p.begin(), p.end(), [](auto l, auto r) { return l.Y < r.Y; });
193 
194  if(ymin > yrange.first->Y)
195  ymin = yrange.first->Y;
196 
197  if(ymax < yrange.second->Y)
198  ymax = yrange.second->Y;
199 
200  auto xrange = std::minmax_element(p.begin(), p.end(), [](auto l, auto r) { return l.X < r.X; });
201 
202  if(xmin > xrange.first->X)
203  xmin = (int)xrange.first->X;
204 
205  if(xmax < xrange.second->X)
206  xmax = (int)xrange.second->X;
207 
208  found = true;
209  }
210 
211  if(!found) return;
212 
213  ymax++; //ensuring the last line is not skipped due to <
214 
215  Gorgon::FitInto<Float>(ymin, 0.f, (Float)target.GetHeight()-1);
216  Gorgon::FitInto<Float>(ymax, 0.f, (Float)target.GetHeight());
217 
218 
219  Gorgon::FitInto(xmin, 0, target.GetWidth()-1);
220  Gorgon::FitInto(xmax, 0, target.GetWidth()-1);
221 
222  if(ceil(ymin) > floor(ymax)) return;
223 
224  if(S_ > 1) { //subpixel
225  for(auto &pl : p2)
226  pl *= S_;
227 
228  Float cy = -1;
229 
230  int ew = xmax-xmin+1; //effective width
231  std::vector<int> cnts(ew); //line buffer for counting
232  int yminint = (int)floor(ymin*S_);
233 
234  float a = 1.f / (S_ * S_);
235 
236  internal::findpolylinestofill(points, yminint, (int)ceil(ymax*S_)+1, [&](float y, auto &xpoints) {
237  if(int(cy) != int(y/S_)) {
238  if(y != yminint) { //transfer
239  for(int x=0; x<ew; x++) {
240  if(cnts[x]) {
241  Graphics::RGBA prevcol = target.GetRGBAAt(int(x+xmin), (int)cy);
242 
243  auto col = fill({(Float)x, (Float)floor(cy-yminint)}, {x + xmin, (int)cy}, prevcol, a * cnts[x]);
244 
245  target.SetRGBAAt(int(x + xmin), int(cy), col);
246  }
247  }
248  }
249 
250  //reset
251  memset(&cnts[0], 0, cnts.size()*sizeof(int));
252 
253  cy = (Float)int(y/S_);
254  }
255 
256  int wind = 0;
257  for(int i=0; i<(int)xpoints.size()-1; i++) {
258  if(xpoints[i].skip)
259  continue;
260 
261  wind += xpoints[i].wind;
262 
263  if(wind == 0) continue;
264 
265  Float s = ceil(xpoints[i].second)/S_;
266  std::sort(xpoints.begin() + i + 1, xpoints.end(), [](auto l, auto r) { return l.first < r.first; });
267 
268  while(true) {
269  i++;
270 
271  if(i >= xpoints.size())
272  break;
273 
274  wind += xpoints[i].wind;
275 
276  if(W_ == 0 ? (wind == 0) : (wind%2==0)) {
277  Float e = floor(xpoints[i].first)/S_;
278 
279  FitInto<Float>(s, (Float)xmin, (Float)xmax+1);
280  FitInto<Float>(e, (Float)xmin, (Float)xmax+1);
281  if(s < e) {
282  for(Float x=s; x<e; x+=1.f/S_) {
283  cnts[(int)x-xmin]++;
284  }
285  }
286 
287  if(xpoints[i].skip) {
288  xpoints[i].skip = false;
289  xpoints[i].wind *= -1;
290  i--;
291  }
292 
293  break;
294  }
295 
296  if(xpoints[i].skip) {
297  xpoints[i].skip = false;
298  xpoints[i].wind *= -1;
299  i--;
300  }
301  }
302 
303  if(xpoints.begin() + i == xpoints.end()) continue;
304 
305  std::sort(xpoints.begin() + i + 1, xpoints.end(), [](auto l, auto r) { return l.second < r.second; });
306  }
307  });
308  }
309  else { //integer
310  internal::findpolylinestofill(points, (int)floor(ymin), (int)ceil(ymax), [&](float y, auto &xpoints) {
311  int wind = 0;
312  for(int i=0; i<(int)xpoints.size()-1; i++) {
313  if(xpoints[i].skip)
314  continue;
315 
316  wind += xpoints[i].wind;
317 
318  if(wind == 0) continue;
319 
320  int s = (int)ceil(xpoints[i].second);
321  std::sort(xpoints.begin() + i + 1, xpoints.end(), [](auto l, auto r) { return l.first < r.first; });
322 
323  while(true) {
324  i++;
325 
326  if(i >= xpoints.size())
327  break;
328 
329  wind += xpoints[i].wind;
330 
331  if(W_ == 0 ? (wind == 0) : (wind%2 == 0)) {
332  int e = (int)floor(xpoints[i].first);
333 
334  FitInto(s, 0, target.GetWidth());
335  FitInto(e, 0, target.GetWidth());
336  if(s < e) {
337  for(int x=s; x<e; x++) {
338  target.SetRGBAAt(x, (int)y, fill({float(x-xmin), float(y-ymin)}, {(int)x, (int)y}, target.GetRGBAAt(x, (int)y), 1.f));
339  }
340  }
341 
342  if(xpoints[i].skip) {
343  xpoints[i].skip = false;
344  xpoints[i].wind *= -1;
345  i--;
346  }
347 
348  break;
349  }
350 
351  if(xpoints[i].skip) {
352  xpoints[i].skip = false;
353  xpoints[i].wind *= -1;
354  i--;
355  }
356  }
357 
358  if(xpoints.begin() + i == xpoints.end()) continue;
359 
360  std::sort(xpoints.begin() + i + 1, xpoints.end(), [](auto l, auto r) { return l.second < r.second; });
361  }
362  });
363  }
364  }
365 
370  template<int S_ = 8, int W_ = 1, class P_, class F_ = SolidFill<>>
371  void Polyfill(Graphics::Bitmap &target, const std::vector<Geometry::PointList<P_>> &points, F_ fill = SolidFill<>{Graphics::Color::Black}) {
372  if(target.HasData())
373  Polyfill<S_, W_, P_, F_>(target.GetData(), points, fill);
374  }
375 
381  template<int S_ = 8, int W_ = 1, class P_= Geometry::Pointf, class F_ = SolidFill<>>
382  void Polyfill(Containers::Image &target, const Geometry::PointList<P_> &p, F_ fill = SolidFill<>{Graphics::Color::Black}) {
383  if(p.GetSize() <= 1) return;
384 
385  Geometry::PointList<P_> p2;
386  const Geometry::PointList<P_> *pp;
387 
388  if(S_ > 1) {
389  p2 = p.Duplicate();
390  pp = &p2;
391  }
392  else {
393  pp = &p;
394  }
395  const Geometry::PointList<P_> &points = *pp;
396 
397  auto yrange = std::minmax_element(points.begin(), points.end(), [](auto l, auto r) { return l.Y < r.Y; });
398 
399  Float ymin = yrange.first->Y;
400  Float ymax = yrange.second->Y;
401 
402  ymax++;
403 
404  Gorgon::FitInto<Float>(ymin, 0, (Float)target.GetHeight()-1);
405  Gorgon::FitInto<Float>(ymax, 0, (Float)target.GetHeight());
406 
407  auto xrange = std::minmax_element(points.begin(), points.end(), [](auto l, auto r) { return l.X < r.X; });
408 
409  int xmin = (int)xrange.first->X;
410  int xmax = (int)ceil(xrange.second->X);
411 
412  Gorgon::FitInto(xmin, 0, target.GetWidth()-1);
413  Gorgon::FitInto(xmax, 0, target.GetWidth()-1);
414 
415  if(ceil(ymin) > floor(ymax)) return;
416 
417  if(S_ > 1) { //subpixel
418  p2 *= S_;
419 
420  Float cy = -1;
421 
422  int ew = xmax-xmin+1; //effective width
423  std::vector<int> cnts(ew); //line buffer for counting
424  int yminint = (int)floor(ymin*S_);
425 
426  float a = 1.f / (S_ * S_);
427 
428  internal::findpolylinestofill(Containers::Collection<const Geometry::PointList<P_>>({points}), yminint, (int)ceil(ymax*S_)+1, [&](Float y, auto &xpoints) {
429  if(int(cy) != int(y/S_)) {
430  if(y != yminint) { //transfer
431  for(int x=0; x<ew; x++) {
432  if(cnts[x]) {
433  Graphics::RGBA prevcol = target.GetRGBAAt(int(x+xmin), (int)cy);
434 
435  auto col = fill({floorf((float)x), floorf((float)cy-yminint)}, {int(x + xmin), (int)cy}, prevcol, a * cnts[x]);
436 
437  target.SetRGBAAt(x + xmin, (int)cy, col);
438  }
439  }
440  }
441 
442  //reset
443  memset(&cnts[0], 0, cnts.size()*sizeof(int));
444 
445  cy = (Float)int(y/S_);
446  }
447 
448 
449  int wind = 0;
450  for(int i=0; i<(int)xpoints.size()-1; i++) {
451  if(xpoints[i].skip)
452  continue;
453 
454  wind += xpoints[i].wind;
455 
456  if(wind == 0) continue;
457 
458  Float s = ceil(xpoints[i].second)/S_;
459  std::sort(xpoints.begin() + i + 1, xpoints.end(), [](auto l, auto r) { return l.first < r.first; });
460 
461  while(true) {
462  i++;
463 
464  if(i >= xpoints.size())
465  break;
466 
467  wind += xpoints[i].wind;
468 
469  if(W_ == 0 ? (wind == 0) : (wind%2==0)) {
470  Float e = floor(xpoints[i].first)/S_;
471 
472  FitInto<Float>(s, (Float)xmin, (Float)xmax+1);
473  FitInto<Float>(e, (Float)xmin, (Float)xmax+1);
474  if(s < e) {
475  for(Float x=s; x<e; x+=1.f/S_) {
476  cnts[(int)x-xmin]++;
477  }
478  }
479 
480  if(xpoints[i].skip) {
481  xpoints[i].skip = false;
482  xpoints[i].wind *= -1;
483  i--;
484  }
485 
486  break;
487  }
488 
489  if(xpoints[i].skip) {
490  xpoints[i].skip = false;
491  xpoints[i].wind *= -1;
492  i--;
493  }
494  }
495 
496  if(xpoints.begin() + i == xpoints.end()) continue;
497 
498  std::sort(xpoints.begin() + i + 1, xpoints.end(), [](auto l, auto r) { return l.second < r.second; });
499  }
500  });
501  }
502  else {
503  internal::findpolylinestofill(Containers::Collection<const Geometry::PointList<P_>>({points}), ymin, ymax, [&](float y, auto &xpoints) {
504  int wind = 0;
505  for(int i=0; i<(int)xpoints.size()-1; i++) {
506  if(xpoints[i].skip)
507  continue;
508 
509  wind += xpoints[i].wind;
510 
511  if(wind == 0) continue;
512 
513  int s = (int)ceil(xpoints[i].second);
514  std::sort(xpoints.begin() + i + 1, xpoints.end(), [](auto l, auto r) { return l.first < r.first; });
515 
516  while(true) {
517  i++;
518 
519  if(i >= xpoints.size())
520  break;
521 
522  wind += xpoints[i].wind;
523 
524  if(W_ == 0 ? (wind == 0) : (wind%2 == 0)) {
525  int e = (int)floor(xpoints[i].first);
526 
527  FitInto(s, 0, target.GetWidth());
528  FitInto(e, 0, target.GetWidth());
529  if(s < e) {
530  for(int x=s; x<e; x++) {
531  target.SetRGBAAt(x, (int)y, fill({float(x-xmin), float(y-ymin)}, {(int)x, (int)y}, target.GetRGBAAt(x, (int)y), 1.f));
532  }
533  }
534 
535  if(xpoints[i].skip) {
536  xpoints[i].skip = false;
537  xpoints[i].wind *= -1;
538  i--;
539  }
540 
541  break;
542  }
543 
544  if(xpoints[i].skip) {
545  xpoints[i].skip = false;
546  xpoints[i].wind *= -1;
547  i--;
548  }
549  }
550 
551  if(xpoints.begin() + i == xpoints.end()) continue;
552 
553  std::sort(xpoints.begin() + i + 1, xpoints.end(), [](auto l, auto r) { return l.second < r.second; });
554  }
555  });
556  }
557  }
558 
563  template<int S_ = 8, class P_, class F_ = SolidFill<>>
564  void Polyfill(Graphics::Bitmap &target, const Geometry::PointList<P_> &points, F_ fill = SolidFill<>{Graphics::Color::Black}) {
565  if(target.HasData())
566  Polyfill<S_>(target.GetData(), points, fill);
567  }
568 
569 } }
Gorgon::swap
void swap(Event< Source_, Args_... > &l, Event< Source_, Args_... > &r)
Swaps two events.
Definition: Event.h:351
Gorgon::CGI::SolidFill
Fills a drawing with a solid color.
Definition: CGI.h:11
Gorgon::Graphics::Color::Black
constexpr RGBA Black
Definition: Color.h:653
Gorgon::Float
float Float
Represents floating point data type.
Definition: Types.h:16
Gorgon::Containers::basic_Image::GetWidth
int GetWidth() const
Returns the width of the image.
Definition: Image.h:1296
Gorgon::Input::Keyboard::Keycodes::N
constexpr Key N
Definition: Keyboard.h:93
Gorgon::Input::Keyboard::Keycodes::X
constexpr Key X
Definition: Keyboard.h:103
Gorgon
Root namespace for Gorgon Game Engine.
Definition: Any.h:19
Gorgon::Graphics::Bitmap::HasData
bool HasData() const
Checks if this image resource has a data attached to it.
Definition: Bitmap.h:163
Gorgon::Geometry::PointList::GetSize
auto GetSize() const
Returns the number of elements in the list.
Definition: PointList.h:70
Gorgon::Graphics::Bitmap
This object contains an bitmap image.
Definition: Bitmap.h:25
Gorgon::FitInto
void FitInto(T_ &v, T_ min, T_ max)
Performs clamping on the given value.
Definition: Types.h:91
Gorgon::Geometry::PointList::Duplicate
PointList Duplicate() const
Duplicates this PointList.
Definition: PointList.h:38
Gorgon::Containers::basic_Image::SetRGBAAt
void SetRGBAAt(int x, int y, Graphics::RGBA color)
Sets the color at the given location to the specified RGBA value.
Definition: Image.h:1241
Gorgon::Containers::basic_Image
This class is a container for image data.
Definition: Image.h:19
Gorgon::Containers::basic_Image::GetHeight
int GetHeight() const
Returns the height of the image.
Definition: Image.h:1301
Gorgon::CGI::Polyfill
void Polyfill(Containers::Image &target, const std::vector< Geometry::PointList< P_ >> &p, F_ fill=SolidFill<>{Graphics::Color::Black})
This function fills the given point list as a polygon.
Definition: Polygon.h:164
Gorgon::Graphics::Bitmap::GetData
Containers::Image & GetData() const
Returns the data attached to this bitmap. If no data is present, this function throws.
Definition: Bitmap.h:168
Gorgon::Input::Keyboard::Keycodes::Y
constexpr Key Y
Definition: Keyboard.h:104
Gorgon::Geometry::PointList
This class represents a set of points.
Definition: PointList.h:17
Gorgon::Containers::basic_Image::GetRGBAAt
Graphics::RGBA GetRGBAAt(int x, int y) const
Returns the alpha at the given location.
Definition: Image.h:1207