egra: added radio button widget; use agg mini to draw buttons (check marks, default...

[iv.d.git] / egra / gfx / aggmini / render.d

/*
 * Simple Framebuffer Gfx/GUI lib
 *
 * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
 * Understanding is not required. Only obedience.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, version 3 of the License ONLY.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 */
/* *****************************************************************************
  Anti-Grain Geometry - Version 2.1 Lite
  Copyright (C) 2002-2003 Maxim Shemanarev (McSeem)
  D port, additional work: Ketmar Dark

  Permission to copy, use, modify, sell and distribute this software
  is granted provided this copyright notice appears in all copies.
  This software is provided "as is" without express or implied
  warranty, and with no claim as to its suitability for any purpose.

  The author gratefully acknowleges the support of David Turner,
  Robert Wilhelm, and Werner Lemberg - the authors of the FreeType
  libray - in producing this work. See http://www.freetype.org for details.

  Initially the rendering algorithm was designed by David Turner and the
  other authors of the FreeType library - see the above notice. I nearly
  created a similar renderer, but still I was far from David's work.
  I completely redesigned the original code and adapted it for Anti-Grain
  ideas. Two functions - renderLine and renderScanLine are the core of
  the algorithm - they calculate the exact coverage of each pixel cell
  of the polygon. I left these functions almost as is, because there's
  no way to improve the perfection - hats off to David and his group!

  All other code is very different from the original.
***************************************************************************** */
module iv.egra.gfx.aggmini.render;
private:
nothrow @safe @nogc:

private import iv.egra.gfx.aggmini : DisableCopyingMixin;
private import iv.egra.gfx.aggmini.enums : FillRule;

import iv.bclamp;
import iv.egra.gfx.base;
import iv.egra.gfx.lowlevel;


// ////////////////////////////////////////////////////////////////////////// //
// a pixel cell
align(1) struct Cell {
align(1):
public:
  //static uint packCoord (in int x, in int y) pure nothrow @safe @nogc { pragma(inline, true); return (y<<16)|(x&0xffff); }

public:
  //uint packedCoord;
  short x, y;
  int cover;
  int area;

  static assert(x.sizeof == 2 && y.sizeof == 2, "oops");
  static assert(y.offsetof == x.offsetof+2, "oops");

public nothrow @trusted @nogc:
  this (in int cx, in int cy, in int c, in int a) pure {
    pragma(inline, true);
    //packedCoord = packCoord(cx, cy);
    x = cast(short)cx; y = cast(short)cy;
    cover = c;
    area = a;
  }

  bool isEqual (in int cx, in int cy) pure const {
    pragma(inline, true);
    //return (x == cx && y == cy);
    return (((cast(short)cx)^x)|((cast(short)cy)^y)) == 0;
  }

  //uint getPackedCoord () const pure nothrow @safe @nogc { pragma(inline, true); return (cast(uint)y<<16)|(cast(uint)cast(ushort)x); }
  uint getPackedCoord () const pure nothrow @trusted @nogc { pragma(inline, true); return *(cast(const uint*)&x); }

  bool isLessThan (in ref Cell other) const pure nothrow @trusted @nogc {
    pragma(inline, true);
    return (y < other.y || (y == other.y && x < other.x));
  }

  //@property int x () const pure { pragma(inline, true); return cast(int)cast(short)(packedCoord&0xffff); }
  //@property int y () const pure { pragma(inline, true); return cast(int)cast(short)(packedCoord>>16); }

  void setCover (in int c, in int a) { pragma(inline, true); cover = c; area = a; }
  void addCover (in int c, in int a) { pragma(inline, true); cover += c; area += a; }

  void setCoord (in int cx, in int cy) {
    pragma(inline, true);
    //packedCoord = packCoord(cx, cy);
    x = cast(short)cx; y = cast(short)cy;
  }

  void set (in int cx, in int cy, in int c, in int a) {
    pragma(inline, true);
    //packedCoord = packCoord(cx, cy);
    x = cast(short)cx; y = cast(short)cy;
    cover = c;
    area = a;
  }
}


// ////////////////////////////////////////////////////////////////////////// //
/* An internal class that implements the main rasterization algorithm.
  Used in the rasterizer. Should not be used direcly.
*/
struct Outline {
private nothrow @trusted @nogc:
  enum : uint {
    CellBlockShift = 12U,
    CellBlockSize = cast(uint)(1<<CellBlockShift),
    CellBlockMask = cast(uint)(CellBlockSize-1),
    CellBlockPool = 256U,
    CellBlockLimit = 1024U,
  }

  enum QSortThreshold = 9;

  enum : uint {
    NotClosed = 1U,
    SortRequired = 2U,
  }

private:
  uint mNumBlocks;
  uint mMaxBlocks;
  uint mCurBlock;
  uint mNumCells;
  Cell** mCells;
  Cell* mCurCellPtr;
  Cell** mSortedCells;
  uint mSortedSize;
  Cell mCurCell = Cell(0x7fff, 0x7fff, 0, 0);
  int mCurX;
  int mCurY;
  int mCloseX;
  int mCloseY;
  int mMinX = 0x7fffffff;
  int mMinY = 0x7fffffff;
  int mMaxX = -0x7fffffff;
  int mMaxY = -0x7fffffff;
  uint mFlags = SortRequired;

private:
  void allocateBlock () {
    import core.stdc.stdlib : realloc;
    if (mCurBlock >= mNumBlocks) {
      import core.stdc.string : memset;
      if (mNumBlocks >= mMaxBlocks) {
        Cell** newCells = cast(Cell**)realloc(mCells, (mMaxBlocks+CellBlockPool)*(Cell*).sizeof);
        if (newCells is null) assert(0, "out of memory");
        mCells = newCells;
        mMaxBlocks += CellBlockPool;
      }
      auto cc = cast(Cell*)realloc(null, Cell.sizeof*CellBlockSize);
      if (cc is null) assert(0, "out of memory");
      memset(cc, 0, Cell.sizeof*CellBlockSize);
      //foreach (ref c; cc[0..CellBlockSize]) c = Cell.init;
      mCells[mNumBlocks++] = cc;
    }
    mCurCellPtr = mCells[mCurBlock++];
  }

public:
  mixin(DisableCopyingMixin);

  ~this () {
    import core.stdc.stdlib : free;
    free(mSortedCells);
    if (mNumBlocks) {
      Cell** ptr = mCells+mNumBlocks-1;
      while (mNumBlocks--) {
        free(*ptr);
        --ptr;
      }
      free(mCells);
    }
  }

  void reset () {
    mNumCells = 0;
    mCurBlock = 0;
    mCurCell.set(0x7fff, 0x7fff, 0, 0);
    mFlags |= SortRequired;
    mFlags &= ~NotClosed;
    mMinX = 0x7fffffff;
    mMinY = 0x7fffffff;
    mMaxX = -0x7fffffff;
    mMaxY = -0x7fffffff;
  }

  void moveTo (in int x, in int y) {
    if ((mFlags&SortRequired) == 0) reset();
    if (mFlags&NotClosed) lineTo(mCloseX, mCloseY);
    setCurCell(x>>PolyBaseShift, y>>PolyBaseShift);
    mCloseX = mCurX = x;
    mCloseY = mCurY = y;
  }

  void lineTo (in int x, in int y) {
    if ((mFlags&SortRequired) && ((mCurX^x)|(mCurY^y))) {
      int c = mCurX>>PolyBaseShift;
      if (c < mMinX) mMinX = c;
      ++c;
      if (c > mMaxX) mMaxX = c;

      c = x>>PolyBaseShift;
      if (c < mMinX) mMinX = c;
      ++c;
      if (c > mMaxX) mMaxX = c;

      renderLine(mCurX, mCurY, x, y);
      mCurX = x;
      mCurY = y;
      mFlags |= NotClosed;
    }
  }

  @property float currX () const pure { pragma(inline, true); return cast(float)mCurX/cast(float)PolyBaseSize; }
  @property float currY () const pure { pragma(inline, true); return cast(float)mCurY/cast(float)PolyBaseSize; }

  @property int minX () const pure { pragma(inline, true); return mMinX; }
  @property int minY () const pure { pragma(inline, true); return mMinY; }
  @property int maxX () const pure { pragma(inline, true); return mMaxX; }
  @property int maxY () const pure { pragma(inline, true); return mMaxY; }

  @property uint numCells () const pure { pragma(inline, true); return mNumCells; }

  const(Cell)** cells () {
    if (mFlags&NotClosed) {
      lineTo(mCloseX, mCloseY);
      mFlags &= ~NotClosed;
    }
    // perform sort only the first time
    if (mFlags&SortRequired) {
      addCurCell();
      if (mNumCells == 0) return null;
      sortCells();
      mFlags &= ~SortRequired;
    }
    return cast(const(Cell)**)mSortedCells;
  }

private:
  void addCurCell () {
    if (mCurCell.area|mCurCell.cover) {
      if ((mNumCells&CellBlockMask) == 0) {
        if (mNumBlocks >= CellBlockLimit) return;
        allocateBlock();
      }
      *mCurCellPtr++ = mCurCell;
      ++mNumCells;
    }
  }

  void setCurCell (in int x, in int y) {
    if (!mCurCell.isEqual(x, y)) {
      addCurCell();
      mCurCell.set(x, y, 0, 0);
    }
  }

  void renderScanLine (in int ey, in int x1, int y1, in int x2, in int y2) {
    immutable int ex2 = x2>>PolyBaseShift;

    // trivial case; happens often
    if (y1 == y2) {
      setCurCell(ex2, ey);
      return;
    }

    int ex1 = x1>>PolyBaseShift;
    immutable int fx1 = x1&PolyBaseMask;
    immutable int fx2 = x2&PolyBaseMask;

    // everything is located in a single cell: that is easy!
    if (ex1 == ex2) {
      immutable int delta = y2-y1;
      mCurCell.addCover(delta, (fx1+fx2)*delta);
      return;
    }

    // ok, we'll have to render a run of adjacent cells on the same scanline...
    int p = (PolyBaseSize-fx1)*(y2-y1);
    int first = PolyBaseSize;
    int incr = 1;

    int dx = x2-x1;

    if (dx < 0) {
      p = fx1*(y2-y1);
      first = 0;
      incr = -1;
      dx = -dx;
    }

    int delta = p/dx;
    int mod = p%dx;
    if (mod < 0) { --delta; mod += dx; }

    mCurCell.addCover(delta, (fx1+first)*delta);

    ex1 += incr;
    setCurCell(ex1, ey);
    y1 += delta;

    if (ex1 != ex2) {
      p = PolyBaseSize*(y2-y1+delta);
      int lift = p/dx;
      int rem = p%dx;
      if (rem < 0) { --lift; rem += dx; }
      mod -= dx;
      while (ex1 != ex2) {
        delta = lift;
        mod += rem;
        if (mod >= 0) { mod -= dx; ++delta; }
        mCurCell.addCover(delta, PolyBaseSize*delta);
        y1 += delta;
        ex1 += incr;
        setCurCell(ex1, ey);
      }
    }

    delta = y2-y1;
    mCurCell.addCover(delta, (fx2+PolyBaseSize-first)*delta);
  }

  void renderLine (in int x1, in int y1, in int x2, in int y2) {
    int ey1 = y1>>PolyBaseShift;
    immutable int ey2 = y2>>PolyBaseShift;

    if (ey1 < mMinY) mMinY = ey1;
    if (ey1+1 > mMaxY) mMaxY = ey1+1;
    if (ey2 < mMinY) mMinY = ey2;
    if (ey2+1 > mMaxY) mMaxY = ey2+1;

    immutable int fy1 = y1&PolyBaseMask;
    immutable int fy2 = y2&PolyBaseMask;

    // everything is on a single scanline
    if (ey1 == ey2) {
      renderScanLine(ey1, x1, fy1, x2, fy2);
      return;
    }

    int dx = x2-x1;
    int dy = y2-y1;

    //int xFrom, xTo;
    //int p, rem, mod, lift, delta, first, incr;

    // vertical line: we have to calculate start and end cells,
    // and then the common values of the area and coverage for
    // all cells of the line. we know exactly there's only one
    // cell, so, we don't have to call renderScanLine().
    int incr = 1;
    if (dx == 0) {
      int ex = x1>>PolyBaseShift;
      int twoFx = (x1-(ex<<PolyBaseShift))<<1;
      int area;

      int first = PolyBaseSize;
      if (dy < 0) { first = 0; incr = -1; }

      immutable int xFrom = x1;

      //renderScanLine(ey1, xFrom, fy1, xFrom, first);
      int delta = first-fy1;
      mCurCell.addCover(delta, twoFx*delta);

      ey1 += incr;
      setCurCell(ex, ey1);

      delta = first+first-PolyBaseSize;
      area = twoFx*delta;
      while (ey1 != ey2) {
        //renderScanLine(ey1, xFrom, PolyBaseSize - first, xFrom, first);
        mCurCell.setCover(delta, area);
        ey1 += incr;
        setCurCell(ex, ey1);
      }
      //renderScanLine(ey1, xFrom, PolyBaseSize - first, xFrom, fy2);
      delta = fy2-PolyBaseSize+first;
      mCurCell.addCover(delta, twoFx*delta);
      return;
    }

    // ok, we have to render several scanlines
    int p = (PolyBaseSize-fy1)*dx;
    int first = PolyBaseSize;

    if (dy < 0) {
      p = fy1*dx;
      first = 0;
      incr = -1;
      dy = -dy;
    }

    int delta = p/dy;
    int mod = p%dy;

    if (mod < 0) { --delta; mod += dy; }

    int xFrom = x1+delta;
    renderScanLine(ey1, x1, fy1, xFrom, first);

    ey1 += incr;
    setCurCell(xFrom>>PolyBaseShift, ey1);

    if (ey1 != ey2) {
      p = PolyBaseSize*dx;
      int lift = p/dy;
      int rem = p%dy;

      if (rem < 0) { --lift; rem += dy; }
      mod -= dy;

      while (ey1 != ey2) {
        delta = lift;
        mod += rem;
        if (mod >= 0) { mod -= dy; ++delta; }

        immutable int xTo = xFrom+delta;
        renderScanLine(ey1, xFrom, PolyBaseSize-first, xTo, first);
        xFrom = xTo;

        ey1 += incr;
        setCurCell(xFrom>>PolyBaseShift, ey1);
      }
    }

    renderScanLine(ey1, xFrom, PolyBaseSize-first, x2, fy2);
  }

private:
  static void qsortCells (Cell** start, uint num) {
    /*
    static void swapCells (Cell** a, Cell** b) nothrow @trusted @nogc {
      pragma(inline, true);
      auto temp = *a;
      *a = *b;
      *b = temp;
    }

    static bool lessThan (in Cell** a, in Cell** b) pure nothrow @trusted @nogc {
      pragma(inline, true);
      version(none) {
        return ((**a).packedCoord < (**b).packedCoord);
      } else {
        return (*a).isLessThan(**b);
      }
    }
    */

    // two macros
    static enum swapCellsMixin(string a, string b) = `
      { auto temp_ = *(`~a~`);
      *(`~a~`) = *(`~b~`);
      *(`~b~`) = temp_; }
    `;

    static enum lessThanMixin(string a, string b) = `(*(`~a~`)).isLessThan(**(`~b~`))`;

    Cell**[80] stack = void;
    Cell*** top;
    Cell** limit;
    Cell** base;

    limit = start+num;
    base = start;
    top = stack.ptr;

    for (;;) {
      immutable int len = cast(int)(limit-base);

      if (len > QSortThreshold) {
        // we use base + len/2 as the pivot
        //auto pivot = base+len/2;
        auto pivot = base+(len>>1);
        mixin(swapCellsMixin!("base", "pivot"));

        auto i = base+1;
        auto j = limit-1;

        // now ensure that *i <= *base <= *j
        if (mixin(lessThanMixin!("j", "i"))) mixin(swapCellsMixin!("i", "j"));
        if (mixin(lessThanMixin!("base", "i"))) mixin(swapCellsMixin!("base", "i"));
        if (mixin(lessThanMixin!("j", "base"))) mixin(swapCellsMixin!("base", "j"));

        for (;;) {
          do { ++i; } while (mixin(lessThanMixin!("i", "base")));
          do { --j; } while (mixin(lessThanMixin!("base", "j")));
          if (i > j) break;
          mixin(swapCellsMixin!("i", "j"));
        }

        mixin(swapCellsMixin!("base", "j"));

        // now, push the largest sub-array
        if (j-base > limit-i) {
          top[0] = base;
          top[1] = j;
          base = i;
        } else {
          top[0] = i;
          top[1] = limit;
          limit = j;
        }
        top += 2;
      } else {
        // the sub-array is small, perform insertion sort
        auto j = base;
        auto i = j+1;
        for (; i < limit; j = i, ++i) {
          for (; mixin(lessThanMixin!("j+1", "j")); --j) {
            mixin(swapCellsMixin!("j+1", "j"));
            if (j == base) break;
          }
        }
        if (top > stack.ptr) {
          top -= 2;
          base = top[0];
          limit = top[1];
        } else {
          break;
        }
      }
    }
  }

  void sortCells () {
    if (mNumCells == 0) return;

    if (mNumCells > mSortedSize) {
      import core.stdc.stdlib: realloc;
      mSortedSize = mNumCells;
      mSortedCells = cast(Cell**)realloc(mSortedCells, (mNumCells+1)*(Cell*).sizeof);
    }

    Cell** sortedPtr = mSortedCells;
    Cell** blockPtr = mCells;
    Cell* cellPtr;

    uint nb = mNumCells>>CellBlockShift;

    while (nb--) {
      cellPtr = *blockPtr++;
      uint i = CellBlockSize;
      while (i--) *sortedPtr++ = cellPtr++;
    }

    cellPtr = *blockPtr++;
    uint i = mNumCells&CellBlockMask;
    while (i--) *sortedPtr++ = cellPtr++;
    mSortedCells[mNumCells] = null;
    qsortCells(mSortedCells, mNumCells);
  }
}


// ////////////////////////////////////////////////////////////////////////// //
/*This class is used to transfer data from class outline (or a similar one)
  to the rendering buffer. It's organized very simple. The class stores
  information of horizontal spans to render it into a pixel-map buffer.
  Each span has initial X, length, and an array of bytes that determine the
  alpha-values for each pixel. So, the restriction of using this class is 256
  levels of Anti-Aliasing, which is quite enough for any practical purpose.
  Before using this class you should know the minimal and maximal pixel
  coordinates of your scanline. The protocol of using is:
  1. reset(minX, maxX)
  2. addCell() / addSpan() - accumulate scanline. You pass Y-coordinate
     into these functions in order to make scanline know the last Y. Before
     calling addCell() / addSpan() you should check with method isReady(y)
     if the last Y has changed. It also checks if the scanline is not empty.
     When forming one scanline the next X coordinate must be always greater
     than the last stored one, i.e. it works only with ordered coordinates.
  3. If the current scanline isReady() you should render it and then call
     resetSpans() before adding new cells/spans.

  4. Rendering:

  Scanline provides an iterator class that allows you to extract
  the spans and the cover values for each pixel. Be aware that clipping
  has not been done yet, so you should perform it yourself.

 -------------------------------------------------------------------------
  int baseX = sl.baseX; // base X. Should be added to the span's X
                        // "sl" is a const reference to the
                        // scanline passed in.

  int y = sl.y; // Y-coordinate of the scanline

  ************************************
  ...Perform vertical clipping here...
  ************************************

  ubyte* row = mRBuf[y]; // the the address of the beginning of the current row

  auto span = scanline.iterator;

  uint spanCount = scanline.spanCount(); // number of spans; it's guaranteed that
                                         // spanCount is always greater than 0

  do {
    int x = span.next+baseX; // the beginning X of the span

    const(ubyte)* covers = span.covers; // the array of the cover values

    int pixelCount = span.pixelCount; // number of pixels of the span;
                                      // always greater than 0, still we
                                      // shoud use "int" instead of "uint"
                                      // because it's more convenient for clipping

    **************************************
    ...Perform horizontal clipping here...
    ...you have x, covers, and pixCount..
    **************************************

    ubyte* dst = row+x; // calculate the start address of the row;
                        // in this case we assume a simple
                        // grayscale image 1-byte per pixel
    do {
      *dst++ = *covers++; // hypotetical rendering
    } while (--pixelCount);
  } while (--spanCount); // spanCount cannot be 0, so this loop is quite safe
 ------------------------------------------------------------------------

  The question is: why should we accumulate the whole scanline when we
  could render just separate spans when they're ready?
  That's because using the scaline is in general faster. When is consists
  of more than one span the conditions for the processor cash system
  are better, because switching between two different areas of memory
  (that can be large ones) occures less frequently.
*/
struct ScanLine {
private:
  int mMinX;
  uint mMaxLen;
  int mDX;
  int mDY;
  int mLastX = 0x7fff;
  int mLastY = 0x7fff;
  ubyte* mCovers;
  ubyte** mStartPtrs;
  ushort* mCounts;
  uint mNumSpans;
  ubyte** mCurStartPtr;
  ushort* mCurCount;

public:
  enum AAShift = 8;

  static struct Iterator {
  private:
    const(ubyte)* mCovers;
    const(ushort)* mCurCount;
    const(ubyte*)* mCurStartPtr;

  public nothrow @trusted @nogc:
    mixin(DisableCopyingMixin);

    this (in ref ScanLine sl) pure {
      pragma(inline, true);
      mCovers = sl.mCovers;
      mCurCount = sl.mCounts;
      mCurStartPtr = sl.mStartPtrs;
    }

    int next () {
      pragma(inline, true);
      ++mCurCount;
      ++mCurStartPtr;
      return cast(int)(*mCurStartPtr-mCovers);
    }

    @property int pixelCount () const pure { pragma(inline, true); return cast(int)(*mCurCount); }
    @property const(ubyte)* covers () const pure { pragma(inline, true); return *mCurStartPtr; }
  }

public nothrow @trusted @nogc:
  mixin(DisableCopyingMixin);

  ~this () {
    import core.stdc.stdlib : free;
    if (mCounts !is null) free(mCounts);
    if (mStartPtrs !is null) free(mStartPtrs);
    if (mCovers !is null) free(mCovers);
  }

  auto iterator () const pure { pragma(inline, true); return Iterator(this); }

  void reset (int minX, int maxX, int dx=0, int dy=0) {
    uint maxLen = maxX-minX+2;
    if (maxLen > mMaxLen) {
      import core.stdc.stdlib : realloc;
      mCovers = cast(ubyte*)realloc(mCovers, maxLen*mCovers[0].sizeof);
      if (mCovers is null) assert(0, "out of memory");
      mStartPtrs = cast(ubyte**)realloc(mStartPtrs, mStartPtrs[0].sizeof*maxLen);
      if (mStartPtrs is null) assert(0, "out of memory");
      mCounts = cast(ushort*)realloc(mCounts, mCounts[0].sizeof*maxLen);
      if (mCounts is null) assert(0, "out of memory");
      mMaxLen = maxLen;
    }
    mDX = dx;
    mDY = dy;
    mLastX = 0x7fff;
    mLastY = 0x7fff;
    mMinX = minX;
    mCurCount = mCounts;
    mCurStartPtr = mStartPtrs;
    mNumSpans = 0;
  }

  void resetSpans () {
    pragma(inline, true);
    mLastX = 0x7fff;
    mLastY = 0x7fff;
    mCurCount = mCounts;
    mCurStartPtr = mStartPtrs;
    mNumSpans = 0;
  }

  void addSpan (int x, int y, uint num, uint cover) {
    import core.stdc.string : memset;
    x -= mMinX;
    memset(mCovers+x, cover, num);
    if (x == mLastX+1) {
      (*mCurCount) += cast(ushort)num;
    } else {
      *++mCurCount = cast(ushort)num;
      *++mCurStartPtr = mCovers+x;
      ++mNumSpans;
    }
    mLastX = x+num-1;
    mLastY = y;
  }

  void addCell (int x, int y, uint cover) {
    x -= mMinX;
    mCovers[x] = cast(ubyte)cover;
    if (x == mLastX+1) {
      ++(*mCurCount);
    } else {
      *++mCurCount = 1;
      *++mCurStartPtr = mCovers+x;
      ++mNumSpans;
    }
    mLastX = x;
    mLastY = y;
  }

  @property bool isReady (int y) const pure { pragma(inline, true); return (mNumSpans && (y^mLastY)); }
  @property int baseX () const pure { pragma(inline, true); return mMinX+mDX; }
  @property int y () const pure { pragma(inline, true); return mLastY+mDY; }
  @property uint spanCount () const pure { pragma(inline, true); return mNumSpans; }
}


// ////////////////////////////////////////////////////////////////////////// //
/* This class template is used basically for rendering scanlines.
  Usage:
    auto ras = Rasterizer();

    // Making polygon
    // ras.moveTo(...);
    // ras.lineTo(...);
    // ...

    // Rendering
    ras.render(ren, Color(255, 127, 0));
*/
public struct Renderer {
public nothrow @trusted @nogc:
  mixin(DisableCopyingMixin);

  static void render (in ref ScanLine sl, in GxColor clr, in ref GxRect clipRect) {
    if (clipRect.size.h < 1 || clipRect.size.w < 1 || sl.y < clipRect.pos.y || sl.y >= clipRect.pos.y+clipRect.size.h) return;
    immutable GxColorU c = GxColorU(clr);
    uint spanCount = sl.spanCount;
    immutable int baseX = sl.baseX;
    uint* row = vglTexBuf+cast(uint)sl.y*cast(uint)VBufWidth;
    auto span = sl.iterator;
    //{ import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "***RENDER: y=%d; spanCount=%u; baseX=%d\n", sl.y, spanCount, baseX); }
    do {
      int x = span.next+baseX;
      int pixelCount = span.pixelCount;
      int leftSkip = void;
      //{ import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "  y=%d; x=%d; pixelCount=%d\n", sl.y, x, pixelCount); }
      if (clipRect.clipHStripe(ref x, sl.y, ref pixelCount, &leftSkip)) {
        //{ import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "    y=%d; x=%d; pixelCount=%d; leftSkip=%d\n", sl.y, x, pixelCount, leftSkip); }
        const(ubyte)* covers = span.covers+leftSkip;
        memBlendColorCoverage(row+x, covers, clr, pixelCount);
      }
    } while (--spanCount);
  }
}


// ////////////////////////////////////////////////////////////////////////// //
/* These constants determine the subpixel accuracy, to be more precise,
  the number of bits of the fractional part of the coordinates.
  The possible coordinate capacity in bits can be calculated by formula:
  sizeof(int) * 8 - PolyBaseShift * 2, i.e, for 32-bit integers and
  8-bits fractional part the capacity is 16 bits or [-32768...32767].
*/
enum : uint {
  PolyBaseShift = 8U,
  PolyBaseSize = cast(uint)(1<<PolyBaseShift),
  PolyBaseMask = cast(uint)(PolyBaseSize-1),
}


int polyCoord (in float c) pure nothrow @safe @nogc { pragma(inline, true); return (cast(int)(c*(PolyBaseSize*2))+1)/2; }

int dbl2fix (in float c) pure nothrow @safe @nogc { pragma(inline, true); return cast(int)(c*PolyBaseSize); }
float fix2dbl (in int c) pure nothrow @safe @nogc { pragma(inline, true); return cast(float)c/cast(float)PolyBaseSize; }


// ////////////////////////////////////////////////////////////////////////// //
/* Polygon rasterizer that is used to render filled polygons with
  high-quality Anti-Aliasing. Internally, by default, the class uses
  integer coordinates in format 24.8, i.e. 24 bits for integer part
  and 8 bits for fractional - see PolyBaseShift. This class can be
  used in the following  way:

  1. fillRule = FillRule.EvenOdd; // optional
  2. gamma() - optional.
  3. reset()
  4. moveTo(x, y) / lineTo(x, y) - make the polygon. One can create
     more than one contour, but each contour must consist of at least 3
     vertices, i.e. moveTo(x1, y1); lineTo(x2, y2); lineTo(x3, y3);
     is the absolute minimum of vertices that define a triangle.
     The algorithm does not check either the number of vertices nor
     coincidence of their coordinates, but in the worst case it just
     won't draw anything.
     The orger of the vertices (clockwise or counterclockwise)
     is important when using the non-zero filling rule (FillNonZero).
     In this case the vertex order of all the contours must be the same
     if you want your intersecting polygons to be without "holes".
     You actually can use different vertices order. If the contours do not
     intersect each other the order is not important anyway. If they do,
     contours with the same vertex order will be rendered without "holes"
     while the intersecting contours with different orders will have "holes".

  fillRule() and gamma() can be called anytime before "sweeping".
*/
public struct Rasterizer {
public nothrow @trusted @nogc:
  enum : uint {
    AAShift = ScanLine.AAShift,
    AANum = 1<<AAShift,
    AAMask = AANum-1,
    AA2Num = AANum*2,
    AA2Mask = AA2Num-1,
  }

private:
  Outline mOutline;
  ScanLine mScanline;
  FillRule mFillingRule = FillRule.NonZero;
  ubyte[256] mGamma = DefaultGamma[];

public:
  bool useGradient;
  uint gradC0;
  uint gradC1;
  float gradMidP = -1.0f;
  uint gradMidC;

public:
  mixin(DisableCopyingMixin);

  void reset () { mOutline.reset(); }

  @property FillRule fillRule () const pure { pragma(inline, true); return mFillingRule; }
  @property void fillRule (FillRule v) { pragma(inline, true); mFillingRule = v; }

  void gamma (in float g) {
    foreach (immutable uint i; 0..256) {
      //import std.math : pow;
      import core.stdc.math : powf;
      mGamma.ptr[i] = cast(ubyte)(powf(cast(float)i/255.0f, g)*255.0f);
    }
  }

  void gamma (const(ubyte)[] g) {
    if (g.length != 256) assert(0, "invalid gamma array");
    mGamma[] = g[0..256];
  }

  @property float currX () const pure { pragma(inline, true); return mOutline.currX; }
  @property float currY () const pure { pragma(inline, true); return mOutline.currY; }

  void moveToFixed (int x, int y) {
    if ((x>>PolyBaseShift) <= short.min+8 || (x>>PolyBaseShift) >= short.max-8 ||
        (y>>PolyBaseShift) <= short.min+8 || (y>>PolyBaseShift) >= short.max-8) assert(0, "coordinates out of bounds");
    mOutline.moveTo(x, y);
  }

  void lineToFixed (int x, int y) {
    if ((x>>PolyBaseShift) <= short.min+8 || (x>>PolyBaseShift) >= short.max-8 ||
        (y>>PolyBaseShift) <= short.min+8 || (y>>PolyBaseShift) >= short.max-8) assert(0, "coordinates out of bounds");
    mOutline.lineTo(x, y);
  }

  void moveTo (in float x, in float y) { mOutline.moveTo(polyCoord(x), polyCoord(y)); }
  void lineTo (in float x, in float y) { mOutline.lineTo(polyCoord(x), polyCoord(y)); }

  @property int minX () const pure { pragma(inline, true); return mOutline.minX; }
  @property int minY () const pure { pragma(inline, true); return mOutline.minY; }
  @property int maxX () const pure { pragma(inline, true); return mOutline.maxX; }
  @property int maxY () const pure { pragma(inline, true); return mOutline.maxY; }

  private uint calculateAlpha (in int area) const pure {
    int cover = area>>(PolyBaseShift*2+1-AAShift);
    if (cover < 0) cover = -cover;
    if (mFillingRule == FillRule.EvenOdd) {
      cover &= AA2Mask;
      if (cover > AANum) cover = AA2Num-cover;
    }
    if (cover > AAMask) cover = AAMask;
    return cover;
  }

  void render (in ref GxRect clipRect, in GxColor c, int dx=0, int dy=0) {
    const(Cell)** cells = mOutline.cells();
    if (mOutline.numCells() == 0) return;

    immutable bool grad = useGradient;
    float gmp = gradMidP;
    bool useMidP = false;
    float gradY0, gradY1, gradTotal;
    uint gC0, gC1, gCM;
    if (grad) {
      gC0 = gradC0;
      gC1 = gradC1;
      gCM = gradMidC;
      gradY0 = minY;
      gradY1 = maxY;
      if (gmp == 0.0f) { gC1 = gCM; gmp = -1.0f; }
      useMidP = (gmp > 0.0f && gmp < 1.0f && minY < maxY);
      gradTotal = 1.0f/(gradY1-gradY0+1.0f);
    } else {
      if (gxIsTransparent(c)) return;
    }

    void flushScanline () {
      if (mScanline.y < clipRect.pos.y || mScanline.y > clipRect.y1) return;
      if (!grad) {
        // no gradient
        Renderer.render(mScanline, c, clipRect);
        return;
      }
      // vertical gradient
      uint clr = void;
      immutable float gt = (cast(float)mScanline.y-gradY0)*gradTotal;
      if (useMidP) {
        if (gt < gmp) {
          clr = gxInterpolateColor(gC0, gCM, gt/gmp);
        } else {
          clr = gxInterpolateColor(gCM, gC1, (gt-gmp)/(1.0f-gmp));
        }
      } else {
        clr = gxInterpolateColor(gC0, gC1, gt);
      }
      Renderer.render(mScanline, clr, clipRect);
    }

    mScanline.reset(mOutline.minX, mOutline.maxX, dx, dy);

    int cover = 0;
    const(Cell)* curCell = *cells++;

    for (;;) {
      const(Cell)* startCell = curCell;

      uint coord = curCell.getPackedCoord;
      int x = curCell.x;
      int y = curCell.y;

      int area = startCell.area;
      cover += startCell.cover;

      // accumulate all start cells
      while ((curCell = *cells++) !is null) {
        if (curCell.getPackedCoord != coord) break;
        area += curCell.area;
        cover += curCell.cover;
      }

      if (area) {
        int alpha = calculateAlpha((cover<<(PolyBaseShift+1))-area);
        if (alpha) {
          if (mScanline.isReady(y)) {
            flushScanline();
            mScanline.resetSpans();
          }
          mScanline.addCell(x, y, mGamma.ptr[alpha]);
        }
        ++x;
      }

      if (!curCell) break;

      if (curCell.x > x) {
        int alpha = calculateAlpha(cover<<(PolyBaseShift+1));
        if (alpha) {
          if (mScanline.isReady(y)) {
            flushScanline();
            mScanline.resetSpans();
          }
          mScanline.addSpan(x, y, curCell.x-x, mGamma.ptr[alpha]);
        }
      }
    }

    if (mScanline.spanCount) flushScanline();
  }

  // returns "gamma alpha" (0 means "no hit")
  ubyte hitTest (int tx, int ty) {
    const(Cell)** cells = mOutline.cells();
    if (mOutline.numCells == 0) return 0;

    int cover = 0;
    const(Cell)* curCell = *cells++;

    for (;;) {
      const(Cell)* startCell = curCell;

      uint coord = curCell.getPackedCoord;
      int x = curCell.x;
      int y = curCell.y;

      if (y > ty) return false;

      int area = startCell.area;
      cover += startCell.cover;

      while ((curCell = *cells++) !is null) {
        if (curCell.getPackedCoord != coord) break;
        area += curCell.area;
        cover += curCell.cover;
      }

      if (area) {
        immutable int alpha = calculateAlpha((cover<<(PolyBaseShift+1))-area);
        if (alpha && mGamma.ptr[alpha]) {
          if (tx == x && ty == y) return mGamma.ptr[alpha];
        }
        ++x;
      }

      if (curCell is null) break;

      if (curCell.x > x) {
        immutable int alpha = calculateAlpha(cover<<(PolyBaseShift+1));
        if (alpha && mGamma.ptr[alpha]) {
          if (ty == y && tx >= x && tx <= curCell.x) return mGamma.ptr[alpha];
        }
      }
    }

    return 0;
  }

private:
  static immutable ubyte[256] DefaultGamma = [
      0,  0,  1,  1,  2,  2,  3,  4,  4,  5,  5,  6,  7,  7,  8,  8,
      9, 10, 10, 11, 11, 12, 13, 13, 14, 14, 15, 16, 16, 17, 18, 18,
     19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28,
     29, 29, 30, 30, 31, 32, 32, 33, 34, 34, 35, 36, 36, 37, 37, 38,
     39, 39, 40, 41, 41, 42, 43, 43, 44, 45, 45, 46, 47, 47, 48, 49,
     49, 50, 51, 51, 52, 53, 53, 54, 55, 55, 56, 57, 57, 58, 59, 60,
     60, 61, 62, 62, 63, 64, 65, 65, 66, 67, 68, 68, 69, 70, 71, 71,
     72, 73, 74, 74, 75, 76, 77, 78, 78, 79, 80, 81, 82, 83, 83, 84,
     85, 86, 87, 88, 89, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99,
    100,101,101,102,103,104,105,106,107,108,109,110,111,112,114,115,
    116,117,118,119,120,121,122,123,124,126,127,128,129,130,131,132,
    134,135,136,137,139,140,141,142,144,145,146,147,149,150,151,153,
    154,155,157,158,159,161,162,164,165,166,168,169,171,172,174,175,
    177,178,180,181,183,184,186,188,189,191,192,194,195,197,199,200,
    202,204,205,207,209,210,212,214,215,217,219,220,222,224,225,227,
    229,230,232,234,236,237,239,241,242,244,246,248,249,251,253,255
  ];
}