+/**
+ * Bresenham's lines
+ */
+void ObjectRenderer::RenderLineOnCPU(int64_t x0, int64_t y0, int64_t x1, int64_t y1, const CPURenderTarget & target, const Colour & colour, bool transpose)
+{
+ int64_t dx = x1 - x0;
+ int64_t dy = y1 - y0;
+ bool neg_m = (dy*dx < 0);
+ dy = abs(dy);
+ dx = abs(dx);
+
+ // If positive slope > 1, just swap x and y
+ if (dy > dx)
+ {
+ RenderLineOnCPU(y0,x0,y1,x1,target,colour,!transpose);
+ return;
+ }
+
+ int64_t two_dy = 2*dy;
+ int64_t p = two_dy - dx;
+ int64_t two_dxdy = 2*(dy-dx);
+ int64_t x; int64_t y; int64_t x_end;
+ int64_t width = (transpose ? target.h : target.w);
+ int64_t height = (transpose ? target.w : target.h);
+
+ if (x0 > x1)
+ {
+ x = x1;
+ y = y1;
+ x_end = x0;
+ }
+ else
+ {
+ x = x0;
+ y = y0;
+ x_end = x1;
+ }
+
+ if (x < 0)
+ {
+ if (x_end < 0) return;
+ y = (neg_m ? y - (dy*-x)/dx : y + (dy*-x)/dx);
+ x = 0;
+ }
+
+ if (x_end > width)
+ {
+ if (x > width) return;
+ x_end = width-1;
+ }
+
+ // TODO: Avoid extra inner conditionals
+ do
+ {
+ if (x >= 0 && x < width && y >= 0 && y < height)
+ {
+ int64_t index = (transpose ? (y + x*target.w)*4 : (x + y*target.w)*4);
+ target.pixels[index+0] = colour.r;
+ target.pixels[index+1] = colour.g;
+ target.pixels[index+2] = colour.b;
+ target.pixels[index+3] = colour.a;
+ }
+ if (p < 0)
+ p += two_dy;
+ else
+ {
+ if (neg_m) --y; else ++y;
+ p += two_dxdy;
+ }
+ } while (++x <= x_end);
+}
+
+
+void ObjectRenderer::FloodFillOnCPU(int64_t x, int64_t y, const PixelBounds & bounds, const CPURenderTarget & target, const Colour & fill, const Colour & stroke)
+{
+ // HACK to prevent overflooding (when the fill points for a path round to the pixel outside the boundary)
+ // (I totally just made that term up...)
+ Colour c = GetColour(target, x+1, y);
+ if (c == fill || c == stroke)
+ return;
+ c = GetColour(target, x-1, y);
+ if (c == fill || c == stroke)
+ return;
+ c = GetColour(target, x, y+1);
+ if (c == fill || c == stroke)
+ return;
+ c = GetColour(target, x, y-1);
+ if (c == fill || c == stroke)
+ return;
+
+ // The hack works but now we get underflooding, or, "droughts".
+
+
+ queue<PixelPoint > traverse;
+ traverse.push(PixelPoint(x,y));
+ // now with 100% less stack overflows!
+ while (traverse.size() > 0)
+ {
+ PixelPoint cur(traverse.front());
+ traverse.pop();
+ if (cur.first < 0 || cur.first < bounds.x || cur.first >= bounds.x+bounds.w || cur.first >= target.w ||
+ cur.second < 0 || cur.second < bounds.y || cur.second >= bounds.y+bounds.h || cur.second >= target.h)
+ continue;
+ c = GetColour(target, cur.first, cur.second);
+ if (c == fill || c == stroke)
+ continue;
+
+ SetColour(target, cur.first, cur.second, fill);
+
+ //Debug("c is {%u,%u,%u,%u} fill is {%u,%u,%u,%u}, stroke is {%u,%u,%u,%u}",
+ // c.r,c.g,c.b,c.a, fill.r,fill.g,fill.b,fill.a, stroke.r,stroke.g,stroke.b,stroke.a);
+
+ traverse.push(PixelPoint(cur.first+1, cur.second));
+ traverse.push(PixelPoint(cur.first-1, cur.second));
+ traverse.push(PixelPoint(cur.first, cur.second-1));
+ traverse.push(PixelPoint(cur.first, cur.second+1));
+ }
+}
+