summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorNiels Martin Hansen <nielsm@indvikleren.dk>2020-01-05 15:19:32 +0100
committerNiels Martin Hansen <nielsm@indvikleren.dk>2020-01-07 18:13:58 +0100
commit35c55dfe70767204597aeada2b3676825ce2bacc (patch)
tree934d087e7e320419d01f30f50bebe238c748f1a1
parentfa71375ec24e4bd8b324352581f7662cd46b82cb (diff)
downloadopenttd-35c55dfe70767204597aeada2b3676825ce2bacc.tar.xz
Add: Filled polygon drawing function
-rw-r--r--src/gfx.cpp138
-rw-r--r--src/gfx_func.h1
2 files changed, 139 insertions, 0 deletions
diff --git a/src/gfx.cpp b/src/gfx.cpp
index db024c9c7..076837341 100644
--- a/src/gfx.cpp
+++ b/src/gfx.cpp
@@ -154,6 +154,144 @@ void GfxFillRect(int left, int top, int right, int bottom, int colour, FillRectM
}
}
+typedef std::pair<Point, Point> LineSegment;
+
+/**
+ * Make line segments from a polygon defined by points, translated by an offset.
+ * Entirely horizontal lines (start and end at same Y coordinate) are skipped, as they are irrelevant to scanline conversion algorithms.
+ * Generated line segments always have the lowest Y coordinate point first, i.e. original direction is lost.
+ * @param shape The polygon to convert.
+ * @param offset Offset vector subtracted from all coordinates in the shape.
+ * @return Vector of undirected line segments.
+ */
+static std::vector<LineSegment> MakePolygonSegments(const std::vector<Point> &shape, Point offset)
+{
+ std::vector<LineSegment> segments;
+ if (shape.size() < 3) return segments; // fewer than 3 will always result in an empty polygon
+ segments.reserve(shape.size());
+
+ /* Connect first and last point by having initial previous point be the last */
+ Point prev = shape.back();
+ prev.x -= offset.x;
+ prev.y -= offset.y;
+ for (Point pt : shape) {
+ pt.x -= offset.x;
+ pt.y -= offset.y;
+ /* Create segments for all non-horizontal lines in the polygon.
+ * The segments always have lowest Y coordinate first. */
+ if (prev.y > pt.y) {
+ segments.emplace_back(pt, prev);
+ } else if (prev.y < pt.y) {
+ segments.emplace_back(prev, pt);
+ }
+ prev = pt;
+ }
+
+ return segments;
+}
+
+/**
+ * Fill a polygon with colour.
+ * The odd-even winding rule is used, i.e. self-intersecting polygons will have holes in them.
+ * Left and top edges are inclusive, right and bottom edges are exclusive.
+ * @note For rectangles the GfxFillRect function will be faster.
+ * @pre dpi->zoom == ZOOM_LVL_NORMAL
+ * @param shape List of points on the polygon.
+ * @param colour An 8 bit palette index (FILLRECT_OPAQUE and FILLRECT_CHECKER) or a recolour spritenumber (FILLRECT_RECOLOUR).
+ * @param mode
+ * FILLRECT_OPAQUE: Fill the polygon with the specified colour.
+ * FILLRECT_CHECKER: Fill every other pixel with the specified colour, in a checkerboard pattern.
+ * FILLRECT_RECOLOUR: Apply a recolour sprite to every pixel in the polygon.
+ */
+void GfxFillPolygon(const std::vector<Point> &shape, int colour, FillRectMode mode)
+{
+ Blitter *blitter = BlitterFactory::GetCurrentBlitter();
+ const DrawPixelInfo *dpi = _cur_dpi;
+ if (dpi->zoom != ZOOM_LVL_NORMAL) return;
+
+ std::vector<LineSegment> segments = MakePolygonSegments(shape, Point{ dpi->left, dpi->top });
+
+ /* Remove segments appearing entirely above or below the clipping area. */
+ segments.erase(std::remove_if(segments.begin(), segments.end(), [dpi](const LineSegment &s) { return s.second.y <= 0 || s.first.y >= dpi->height; }), segments.end());
+
+ /* Check that this wasn't an empty shape (all points on a horizontal line or outside clipping.) */
+ if (segments.empty()) return;
+
+ /* Sort the segments by first point Y coordinate. */
+ std::sort(segments.begin(), segments.end(), [](const LineSegment &a, const LineSegment &b) { return a.first.y < b.first.y; });
+
+ /* Segments intersecting current scanline. */
+ std::vector<LineSegment> active;
+ /* Intersection points with a scanline.
+ * Kept outside loop to avoid repeated re-allocations. */
+ std::vector<int> intersections;
+ /* Normal, reasonable polygons don't have many intersections per scanline. */
+ active.reserve(4);
+ intersections.reserve(4);
+
+ /* Scan through the segments and paint each scanline. */
+ int y = segments.front().first.y;
+ std::vector<LineSegment>::iterator nextseg = segments.begin();
+ while (!active.empty() || nextseg != segments.end()) {
+ /* Clean up segments that have ended. */
+ active.erase(std::remove_if(active.begin(), active.end(), [y](const LineSegment &s) { return s.second.y == y; }), active.end());
+
+ /* Activate all segments starting on this scanline. */
+ while (nextseg != segments.end() && nextseg->first.y == y) {
+ active.push_back(*nextseg);
+ ++nextseg;
+ }
+
+ /* Check clipping. */
+ if (y < 0) {
+ ++y;
+ continue;
+ }
+ if (y >= dpi->height) return;
+
+ /* Intersect scanline with all active segments. */
+ intersections.clear();
+ for (const LineSegment &s : active) {
+ const int sdx = s.second.x - s.first.x;
+ const int sdy = s.second.y - s.first.y;
+ const int ldy = y - s.first.y;
+ const int x = s.first.x + sdx * ldy / sdy;
+ intersections.push_back(x);
+ }
+
+ /* Fill between pairs of intersections. */
+ std::sort(intersections.begin(), intersections.end());
+ for (size_t i = 1; i < intersections.size(); i += 2) {
+ /* Check clipping. */
+ const int x1 = max(0, intersections[i - 1]);
+ const int x2 = min(intersections[i], dpi->width);
+ if (x2 < 0) continue;
+ if (x1 >= dpi->width) continue;
+
+ /* Fill line y from x1 to x2. */
+ void *dst = blitter->MoveTo(dpi->dst_ptr, x1, y);
+ switch (mode) {
+ default: // FILLRECT_OPAQUE
+ blitter->DrawRect(dst, x2 - x1, 1, (uint8)colour);
+ break;
+ case FILLRECT_RECOLOUR:
+ blitter->DrawColourMappingRect(dst, x2 - x1, 1, GB(colour, 0, PALETTE_WIDTH));
+ break;
+ case FILLRECT_CHECKER:
+ /* Fill every other pixel, offset such that the sum of filled pixels' X and Y coordinates is odd.
+ * This creates a checkerboard effect. */
+ for (int x = (x1 + y) & 1; x < x2 - x1; x += 2) {
+ blitter->SetPixel(dst, x, 0, (uint8)colour);
+ }
+ break;
+ }
+ }
+
+ /* Next line */
+ ++y;
+ }
+}
+
/**
* Check line clipping by using a linear equation and draw the visible part of
* the line given by x/y and x2/y2.
diff --git a/src/gfx_func.h b/src/gfx_func.h
index ea133acfc..3def1c85a 100644
--- a/src/gfx_func.h
+++ b/src/gfx_func.h
@@ -115,6 +115,7 @@ int DrawStringMultiLine(int left, int right, int top, int bottom, StringID str,
void DrawCharCentered(uint32 c, int x, int y, TextColour colour);
void GfxFillRect(int left, int top, int right, int bottom, int colour, FillRectMode mode = FILLRECT_OPAQUE);
+void GfxFillPolygon(const std::vector<Point> &shape, int colour, FillRectMode mode = FILLRECT_OPAQUE);
void GfxDrawLine(int left, int top, int right, int bottom, int colour, int width = 1, int dash = 0);
void DrawBox(int x, int y, int dx1, int dy1, int dx2, int dy2, int dx3, int dy3);