egra/gfx/aggmini/render.d

   1 /*
   2  * Simple Framebuffer Gfx/GUI lib
   3  *
   4  * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   5  * Understanding is not required. Only obedience.
   6  *
   7  * This program is free software: you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation, version 3 of the License ONLY.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  18  */
  19 /* *****************************************************************************
  20   Anti-Grain Geometry - Version 2.1 Lite
  21   Copyright (C) 2002-2003 Maxim Shemanarev (McSeem)
  22   D port, additional work: Ketmar Dark
  23
  24   Permission to copy, use, modify, sell and distribute this software
  25   is granted provided this copyright notice appears in all copies.
  26   This software is provided "as is" without express or implied
  27   warranty, and with no claim as to its suitability for any purpose.
  28
  29   The author gratefully acknowleges the support of David Turner,
  30   Robert Wilhelm, and Werner Lemberg - the authors of the FreeType
  31   libray - in producing this work. See http://www.freetype.org for details.
  32
  33   Initially the rendering algorithm was designed by David Turner and the
  34   other authors of the FreeType library - see the above notice. I nearly
  35   created a similar renderer, but still I was far from David's work.
  36   I completely redesigned the original code and adapted it for Anti-Grain
  37   ideas. Two functions - renderLine and renderScanLine are the core of
  38   the algorithm - they calculate the exact coverage of each pixel cell
  39   of the polygon. I left these functions almost as is, because there's
  40   no way to improve the perfection - hats off to David and his group!
  41
  42   All other code is very different from the original.
  43 ***************************************************************************** */
  44 module iv.egra.gfx.aggmini.render;
  45 private:
  46 nothrow @safe @nogc:
  47
  48 private import iv.egra.gfx.aggmini : DisableCopyingMixin;
  49 private import iv.egra.gfx.aggmini.enums;
  50
  51 import iv.bclamp;
  52 import iv.egra.gfx.base;
  53 import iv.egra.gfx.lowlevel;
  54
  55
  56 // ////////////////////////////////////////////////////////////////////////// //
  57 /* These constants determine the subpixel accuracy, to be more precise,
  58   the number of bits of the fractional part of the coordinates.
  59   The possible coordinate capacity in bits can be calculated by formula:
  60   sizeof(int) * 8 - PolyBaseShift * 2, i.e, for 32-bit integers and
  61   8-bits fractional part the capacity is 16 bits or [-32768...32767].
  62 */
  63 enum : uint {
  64   PolyBaseShift = 8U,
  65   PolyBaseSize = cast(uint)(1<<PolyBaseShift),
  66   PolyBaseMask = cast(uint)(PolyBaseSize-1),
  67 }
  68
  69
  70 int polyCoord (in float c) pure nothrow @safe @nogc { pragma(inline, true); return (cast(int)(c*(PolyBaseSize*2.0f))+1)/2; }
  71
  72 //int dbl2fix (in float c) pure nothrow @safe @nogc { pragma(inline, true); return cast(int)(c*PolyBaseSize); }
  73 //float fix2dbl (in int c) pure nothrow @safe @nogc { pragma(inline, true); return cast(float)c/cast(float)PolyBaseSize; }
  74
  75
  76 // ////////////////////////////////////////////////////////////////////////// //
  77 // a pixel cell
  78 align(1) struct Cell {
  79 align(1):
  80 public:
  81   short x, y;
  82   int cover;
  83   int area;
  84
  85   static assert(x.sizeof == 2 && y.sizeof == 2, "oops");
  86   static assert(y.offsetof == x.offsetof+2, "oops");
  87
  88 public nothrow @trusted @nogc:
  89   this (in int cx, in int cy, in int c, in int a) pure {
  90     pragma(inline, true);
  91     x = cast(short)cx;
  92     y = cast(short)cy;
  93     cover = c;
  94     area = a;
  95   }
  96
  97   /*
  98   bool isEqual (in int cx, in int cy) pure const {
  99     pragma(inline, true);
 100     return (((cast(short)cx)^x)|((cast(short)cy)^y)) == 0;
 101   }
 102   */
 103
 104   uint getPackedCoord () const pure { pragma(inline, true); return *(cast(const uint*)&x); }
 105
 106   bool isLessThan (in ref Cell other) const pure {
 107     pragma(inline, true);
 108     return (y < other.y || (y == other.y && x < other.x));
 109   }
 110
 111   void setCover (in int c, in int a) { pragma(inline, true); cover = c; area = a; }
 112   void addCover (in int c, in int a) { pragma(inline, true); cover += c; area += a; }
 113
 114   void set (in int cx, in int cy, in int c, in int a) {
 115     pragma(inline, true);
 116     x = cast(short)cx;
 117     if (cast(int)x != cx) { x = (cx < 0 ? short.min+2 : short.max-2); }
 118     y = cast(short)cy;
 119     if (cast(int)y != cy) { y = (cy < 0 ? short.min+2 : short.max-2); }
 120     cover = c;
 121     area = a;
 122   }
 123 }
 124
 125
 126 // ////////////////////////////////////////////////////////////////////////// //
 127 // an internal class that implements the main rasterization algorithm.
 128 // used in the rasterizer. should not be used direcly.
 129 // this clips by vertical framebuffer extents.
 130 // we are rendering scanline by scanline, so this is safe.
 131 // k8: alas, clipping by horizontal extents is harder due to polygon filling.
 132 // k8: i can limit coords in `addCurCell()`, but the cells still should be kept.
 133 // k8: this is because i don't fully understand how the whole thing works.
 134 struct Outline {
 135 private nothrow @trusted @nogc:
 136   enum : uint {
 137     CellBlockShift = 12U,
 138     CellBlockSize = cast(uint)(1<<CellBlockShift),
 139     CellBlockMask = cast(uint)(CellBlockSize-1),
 140     CellBlockPool = 256U,
 141     CellBlockLimit = 1024U,
 142   }
 143
 144   enum QSortThreshold = 9;
 145
 146   enum : uint {
 147     NotClosed = 1U,
 148     SortRequired = 2U,
 149   }
 150
 151 private:
 152   uint mNumBlocks;
 153   uint mMaxBlocks;
 154   uint mCurBlock;
 155   uint mNumCells;
 156   Cell** mCells;
 157   Cell* mCurCellPtr;
 158   Cell** mSortedCells;
 159   uint mSortedSize;
 160   Cell mCurCell = Cell(0x7fff, 0x7fff, 0, 0);
 161   int mCurX;
 162   int mCurY;
 163   int mCloseX;
 164   int mCloseY;
 165   int mMinX = 0x7fffffff;
 166   int mMinY = 0x7fffffff;
 167   int mMaxX = -0x7fffffff;
 168   int mMaxY = -0x7fffffff;
 169   int mLimitY;
 170   uint mFlags = SortRequired;
 171
 172   static struct SortedY {
 173     uint start;
 174     uint num;
 175   }
 176
 177   SortedY* mSortedY = null;
 178   uint mSortedYAlloted = 0;
 179
 180 private:
 181   void allocateBlock () {
 182     import core.stdc.stdlib : realloc;
 183     if (mCurBlock >= mNumBlocks) {
 184       import core.stdc.string : memset;
 185       if (mNumBlocks >= mMaxBlocks) {
 186         Cell** newCells = cast(Cell**)realloc(mCells, (mMaxBlocks+CellBlockPool)*(Cell*).sizeof);
 187         if (newCells is null) assert(0, "out of memory");
 188         mCells = newCells;
 189         mMaxBlocks += CellBlockPool;
 190       }
 191       auto cc = cast(Cell*)realloc(null, Cell.sizeof*CellBlockSize);
 192       if (cc is null) assert(0, "out of memory");
 193       memset(cc, 0, Cell.sizeof*CellBlockSize);
 194       mCells[mNumBlocks++] = cc;
 195     }
 196     mCurCellPtr = mCells[mCurBlock++];
 197   }
 198
 199 public:
 200   mixin(DisableCopyingMixin);
 201
 202   ~this () {
 203     import core.stdc.stdlib : free;
 204     if (mSortedCells !is null) free(mSortedCells);
 205     if (mSortedY !is null) free(mSortedY);
 206     if (mNumBlocks) {
 207       Cell** ptr = mCells+mNumBlocks-1;
 208       while (mNumBlocks--) {
 209         free(*ptr);
 210         --ptr;
 211       }
 212       free(mCells);
 213     }
 214   }
 215
 216   void reset () {
 217     mNumCells = mCurBlock = 0;
 218     mCurCell.set(0x7fff, 0x7fff, 0, 0);
 219     //mFlags |= SortRequired;
 220     //mFlags &= ~NotClosed;
 221     mFlags = SortRequired;
 222     mMinX = mMinY = +0x7fffffff;
 223     mMaxX = mMaxY = -0x7fffffff;
 224     mLimitY = VBufHeight;
 225   }
 226
 227   // fixed point
 228   void moveTo (in int x, in int y) {
 229     if ((mFlags&SortRequired) == 0) reset();
 230     if (mFlags&NotClosed) lineTo(mCloseX, mCloseY);
 231     setCurCell(x>>PolyBaseShift, y>>PolyBaseShift);
 232     mCloseX = mCurX = x;
 233     mCloseY = mCurY = y;
 234   }
 235
 236   // fixed point
 237   void lineTo (in int x, in int y) {
 238     if ((mFlags&SortRequired) && ((mCurX^x)|(mCurY^y))) {
 239       renderLine(mCurX, mCurY, x, y);
 240       mCurX = x;
 241       mCurY = y;
 242       mFlags |= NotClosed;
 243     }
 244   }
 245
 246   @property float currX () const pure { pragma(inline, true); return cast(float)mCurX/cast(float)PolyBaseSize; }
 247   @property float currY () const pure { pragma(inline, true); return cast(float)mCurY/cast(float)PolyBaseSize; }
 248
 249   @property int minX () const pure { pragma(inline, true); return (mMinX <= mMaxX ? mMinX : 0); }
 250   @property int minY () const pure { pragma(inline, true); return (mMinY <= mMaxY ? mMinY : 0); }
 251   @property int maxX () const pure { pragma(inline, true); return (mMinX <= mMaxX ? mMaxX : 0); }
 252   @property int maxY () const pure { pragma(inline, true); return (mMinY <= mMaxY ? mMaxY : 0); }
 253
 254   @property uint numCells () const pure { pragma(inline, true); return mNumCells; }
 255
 256   void prepareCells () {
 257     if (mFlags&NotClosed) {
 258       lineTo(mCloseX, mCloseY);
 259       mFlags &= ~NotClosed;
 260     }
 261     // perform sort only the first time
 262     if (mFlags&SortRequired) {
 263       addCurCell();
 264       if (mNumCells != 0) sortCells();
 265       mFlags &= ~SortRequired;
 266     }
 267   }
 268
 269   const(Cell)** cells () {
 270     prepareCells();
 271     return cast(const(Cell)**)mSortedCells;
 272   }
 273
 274   // should be called after `prepareCells()`!
 275   const(Cell)** getCellsForY (in int y) {
 276     prepareCells();
 277     if (mNumCells == 0) return null;
 278     if (y < mMinY || y > mMaxY) return null;
 279     const(SortedY)* cy = &mSortedY[y-mMinY];
 280     if (cy.num == 0) return null;
 281     return cast(const(Cell)**)(mSortedCells+cy.start);
 282   }
 283
 284   // should be called after `prepareCells()`!
 285   // returns first cell where `cell.y >= y`
 286   const(Cell)** getCellsForYOrMore (int y) {
 287     prepareCells();
 288     if (mNumCells == 0) return null;
 289     if (y > mSortedCells[mNumCells-1].y) return null;
 290     if (y <= mSortedCells[0].y) return cast(const(Cell)**)mSortedCells;
 291     assert(y >= mMinY);
 292     const(SortedY)* cy = &mSortedY[y-mMinY];
 293     while (y++ <= mMaxY) {
 294       if (cy.num) return cast(const(Cell)**)(mSortedCells+cy.start);
 295       ++cy;
 296     }
 297     return null;
 298   }
 299
 300 private:
 301   void fixMinMaxX (int x) {
 302     pragma(inline, true);
 303     //if (x < 0) x = 0; else if (x >= VBufWidth) x = VBufWidth-1;
 304     if (x < mMinX) mMinX = x;
 305     if (x+1 > mMaxX) mMaxX = x+1;
 306   }
 307
 308   void fixMinMaxY (int y) {
 309     pragma(inline, true);
 310     if (y < 0) y = 0; else if (y >= mLimitY) y = mLimitY-1;
 311     if (y < mMinY) mMinY = y;
 312     if (y+1 > mMaxY) mMaxY = y+1;
 313   }
 314
 315   // this clips by vertical framebuffer extents
 316   // we are rendering scanline by scanline, so this is safe
 317   // just don't forget that `fixMinMaxY()` should perform clipping too
 318   void addCurCell () {
 319     if (mCurCell.area|mCurCell.cover) {
 320       if (mCurCell.y >= 0 && mCurCell.y < mLimitY) {
 321         if ((mNumCells&CellBlockMask) == 0) {
 322           if (mNumBlocks >= CellBlockLimit) return;
 323           allocateBlock();
 324         }
 325         *mCurCellPtr++ = mCurCell;
 326         ++mNumCells;
 327       }
 328       mCurCell.area = mCurCell.cover = 0;
 329     }
 330   }
 331
 332   void setCurCell (in int x, in int y) {
 333     if (/*!mCurCell.isEqual(x, y)*/(((cast(short)mCurCell.x)^x)|((cast(short)mCurCell.y)^y))) {
 334       addCurCell();
 335       mCurCell.set(x, y, 0, 0);
 336     }
 337   }
 338
 339   // `iy`: integral; other: fixed point
 340   void renderHorizLine (in int iy, in int x1, int y1, in int x2, in int y2) {
 341     immutable int ix2 = x2>>PolyBaseShift;
 342
 343     // trivial case; happens often
 344     if (y1 == y2) {
 345       setCurCell(ix2, iy);
 346       return;
 347     }
 348
 349     int ix1 = x1>>PolyBaseShift;
 350     immutable int fx1 = x1&PolyBaseMask;
 351     immutable int fx2 = x2&PolyBaseMask;
 352
 353     // everything is located in a single cell: that is easy!
 354     if (ix1 == ix2) {
 355       immutable int delta = y2-y1;
 356       mCurCell.addCover(delta, (fx1+fx2)*delta);
 357       return;
 358     }
 359
 360     // ok, we'll have to render a run of adjacent cells on the same scanline...
 361     int p = (PolyBaseSize-fx1)*(y2-y1);
 362     int first = PolyBaseSize;
 363     int incr = 1;
 364
 365     int dx = x2-x1;
 366
 367     if (dx < 0) {
 368       p = fx1*(y2-y1);
 369       first = 0;
 370       incr = -1;
 371       dx = -dx;
 372     }
 373
 374     int delta = p/dx;
 375     int mod = p%dx;
 376     if (mod < 0) { --delta; mod += dx; }
 377
 378     mCurCell.addCover(delta, (fx1+first)*delta);
 379
 380     ix1 += incr;
 381     setCurCell(ix1, iy);
 382     y1 += delta;
 383
 384     if (ix1 != ix2) {
 385       p = PolyBaseSize*(y2-y1+delta);
 386       int lift = p/dx;
 387       int rem = p%dx;
 388       if (rem < 0) { --lift; rem += dx; }
 389       mod -= dx;
 390       while (ix1 != ix2) {
 391         delta = lift;
 392         mod += rem;
 393         if (mod >= 0) { mod -= dx; ++delta; }
 394         mCurCell.addCover(delta, PolyBaseSize*delta);
 395         y1 += delta;
 396         ix1 += incr;
 397         setCurCell(ix1, iy);
 398       }
 399     }
 400
 401     delta = y2-y1;
 402     mCurCell.addCover(delta, (fx2+PolyBaseSize-first)*delta);
 403   }
 404
 405   // fixed point
 406   void renderLine (in int x1, in int y1, in int x2, in int y2) {
 407     int iy1 = y1>>PolyBaseShift;
 408     immutable int iy2 = y2>>PolyBaseShift;
 409
 410     fixMinMaxX(x1>>PolyBaseShift);
 411     fixMinMaxX(x2>>PolyBaseShift);
 412
 413     fixMinMaxY(iy1);
 414     fixMinMaxY(iy2);
 415
 416     immutable int fy1 = y1&PolyBaseMask;
 417     immutable int fy2 = y2&PolyBaseMask;
 418
 419     // everything is on a single scanline
 420     if (iy1 == iy2) {
 421       renderHorizLine(iy1, x1, fy1, x2, fy2);
 422       return;
 423     }
 424
 425     int dx = x2-x1;
 426     int dy = y2-y1;
 427
 428     // vertical line: we have to calculate start and end cells,
 429     // and then the common values of the area and coverage for
 430     // all cells of the line. we know exactly there's only one
 431     // cell, so, we don't have to call renderHorizLine().
 432     int incr = 1;
 433     if (dx == 0) {
 434       int ix = x1>>PolyBaseShift;
 435       int twoFx = (x1-(ix<<PolyBaseShift))<<1;
 436       int area;
 437
 438       int first = PolyBaseSize;
 439       if (dy < 0) { first = 0; incr = -1; }
 440
 441       immutable int xFrom = x1;
 442
 443       //renderHorizLine(ey1, xFrom, fy1, xFrom, first);
 444       int delta = first-fy1;
 445       mCurCell.addCover(delta, twoFx*delta);
 446
 447       iy1 += incr;
 448       setCurCell(ix, iy1);
 449
 450       delta = first+first-PolyBaseSize;
 451       area = twoFx*delta;
 452       while (iy1 != iy2) {
 453         //renderHorizLine(ey1, xFrom, PolyBaseSize-first, xFrom, first);
 454         mCurCell.setCover(delta, area);
 455         iy1 += incr;
 456         setCurCell(ix, iy1);
 457       }
 458       //renderHorizLine(ey1, xFrom, PolyBaseSize-first, xFrom, fy2);
 459       delta = fy2-PolyBaseSize+first;
 460       mCurCell.addCover(delta, twoFx*delta);
 461       return;
 462     }
 463
 464     // ok, we have to render several scanlines
 465     int p = (PolyBaseSize-fy1)*dx;
 466     int first = PolyBaseSize;
 467
 468     if (dy < 0) {
 469       p = fy1*dx;
 470       first = 0;
 471       incr = -1;
 472       dy = -dy;
 473     }
 474
 475     int delta = p/dy;
 476     int mod = p%dy;
 477
 478     if (mod < 0) { --delta; mod += dy; }
 479
 480     int xFrom = x1+delta;
 481     renderHorizLine(iy1, x1, fy1, xFrom, first);
 482
 483     iy1 += incr;
 484     setCurCell(xFrom>>PolyBaseShift, iy1);
 485
 486     if (iy1 != iy2) {
 487       p = PolyBaseSize*dx;
 488       int lift = p/dy;
 489       int rem = p%dy;
 490
 491       if (rem < 0) { --lift; rem += dy; }
 492       mod -= dy;
 493
 494       while (iy1 != iy2) {
 495         delta = lift;
 496         mod += rem;
 497         if (mod >= 0) { mod -= dy; ++delta; }
 498
 499         immutable int xTo = xFrom+delta;
 500         renderHorizLine(iy1, xFrom, PolyBaseSize-first, xTo, first);
 501         xFrom = xTo;
 502
 503         iy1 += incr;
 504         setCurCell(xFrom>>PolyBaseShift, iy1);
 505       }
 506     }
 507
 508     renderHorizLine(iy1, xFrom, PolyBaseSize-first, x2, fy2);
 509   }
 510
 511 private:
 512   static void qsortCells (Cell** start, uint num) {
 513     // two macros
 514     static enum swapCellsMixin(string a, string b) = `
 515       { auto temp_ = *(`~a~`);
 516       *(`~a~`) = *(`~b~`);
 517       *(`~b~`) = temp_; }
 518     `;
 519
 520     //static enum lessThanMixin(string a, string b) = `(*(`~a~`)).isLessThan(**(`~b~`))`;
 521     // y is guaranteed to be the same
 522     static enum lessThanMixin(string a, string b) = `((*(`~a~`)).x < (*(`~b~`)).x)`;
 523
 524     Cell**[80] stack = void;
 525     Cell*** top;
 526     Cell** limit;
 527     Cell** base;
 528
 529     limit = start+num;
 530     base = start;
 531     top = stack.ptr;
 532
 533     for (;;) {
 534       immutable int len = cast(int)(limit-base);
 535
 536       if (len > QSortThreshold) {
 537         // we use base + len/2 as the pivot
 538         //auto pivot = base+len/2;
 539         auto pivot = base+(len>>1);
 540         mixin(swapCellsMixin!("base", "pivot"));
 541
 542         auto i = base+1;
 543         auto j = limit-1;
 544
 545         // now ensure that *i <= *base <= *j
 546         if (mixin(lessThanMixin!("j", "i"))) mixin(swapCellsMixin!("i", "j"));
 547         if (mixin(lessThanMixin!("base", "i"))) mixin(swapCellsMixin!("base", "i"));
 548         if (mixin(lessThanMixin!("j", "base"))) mixin(swapCellsMixin!("base", "j"));
 549
 550         for (;;) {
 551           do { ++i; } while (mixin(lessThanMixin!("i", "base")));
 552           do { --j; } while (mixin(lessThanMixin!("base", "j")));
 553           if (i > j) break;
 554           mixin(swapCellsMixin!("i", "j"));
 555         }
 556
 557         mixin(swapCellsMixin!("base", "j"));
 558
 559         // now, push the largest sub-array
 560         if (j-base > limit-i) {
 561           top[0] = base;
 562           top[1] = j;
 563           base = i;
 564         } else {
 565           top[0] = i;
 566           top[1] = limit;
 567           limit = j;
 568         }
 569         top += 2;
 570       } else {
 571         // the sub-array is small, perform insertion sort
 572         auto j = base;
 573         auto i = j+1;
 574         for (; i < limit; j = i, ++i) {
 575           for (; mixin(lessThanMixin!("j+1", "j")); --j) {
 576             mixin(swapCellsMixin!("j+1", "j"));
 577             if (j == base) break;
 578           }
 579         }
 580         if (top > stack.ptr) {
 581           top -= 2;
 582           base = top[0];
 583           limit = top[1];
 584         } else {
 585           break;
 586         }
 587       }
 588     }
 589   }
 590
 591   void sortCells () {
 592     if (mNumCells == 0) return;
 593
 594     if (mNumCells >= mSortedSize) {
 595       import core.stdc.stdlib: realloc;
 596       mSortedSize = (mNumCells|0x3ff)+1;
 597       mSortedCells = cast(Cell**)realloc(mSortedCells, mSortedSize*(Cell*).sizeof);
 598       if (mSortedCells is null) assert(0, "out of memory");
 599     }
 600
 601     // allocate and zero the Y array
 602     immutable uint mSortedYSize = mMaxY-mMinY+1;
 603     assert(mSortedYSize > 0);
 604     if (mSortedYSize >= mSortedYAlloted) {
 605       import core.stdc.stdlib: realloc;
 606       mSortedYAlloted = (mSortedYSize|0xff)+1;
 607       mSortedY = cast(SortedY*)realloc(mSortedY, mSortedYAlloted*SortedY.sizeof);
 608       if (mSortedY is null) assert(0, "out of memory");
 609     }
 610     {
 611       import core.stdc.string : memset;
 612       memset(mSortedY, 0, mSortedYSize*SortedY.sizeof);
 613     }
 614
 615     // create the Y-histogram (count the numbers of cells for each Y)
 616     Cell** blockPtr = mCells;
 617     Cell* cellPtr = void;
 618     uint i = void;
 619
 620     uint nb = mNumCells>>CellBlockShift;
 621     while (nb--) {
 622       cellPtr = *blockPtr++;
 623       i = CellBlockSize;
 624       while (i--) {
 625         mSortedY[cellPtr.y-mMinY].start++;
 626         ++cellPtr;
 627       }
 628     }
 629
 630     cellPtr = *blockPtr++;
 631     i = mNumCells&CellBlockMask;
 632     while (i--) {
 633       mSortedY[cellPtr.y-mMinY].start++;
 634       ++cellPtr;
 635     }
 636
 637     // convert the Y-histogram into the array of starting indexes
 638     uint start = 0;
 639     for (i = 0; i < mSortedYSize; ++i) {
 640       immutable uint v = mSortedY[i].start;
 641       mSortedY[i].start = start;
 642       start += v;
 643     }
 644
 645     // fill the cell pointer array sorted by Y
 646     blockPtr = mCells;
 647     nb = mNumCells>>CellBlockShift;
 648     while (nb--) {
 649       cellPtr = *blockPtr++;
 650       i = CellBlockSize;
 651       while (i--) {
 652         assert(cellPtr.y-mMinY >= 0 && cellPtr.y-mMinY < mSortedYSize);
 653         SortedY* cy = &mSortedY[cellPtr.y-mMinY];
 654         mSortedCells[cy.start+(cy.num++)] = cellPtr++;
 655       }
 656     }
 657
 658     cellPtr = *blockPtr++;
 659     i = mNumCells&CellBlockMask;
 660     while (i--) {
 661       assert(cellPtr.y-mMinY >= 0 && cellPtr.y-mMinY < mSortedYSize);
 662       SortedY* cy = &mSortedY[cellPtr.y-mMinY];
 663       mSortedCells[cy.start+(cy.num++)] = cellPtr++;
 664     }
 665     mSortedCells[mNumCells] = null; // we need this
 666
 667     // finally arrange the X-arrays
 668     for (i = 0; i < mSortedYSize; ++i) {
 669       const(SortedY)* cy = &mSortedY[i];
 670       if (cy.num) qsortCells(mSortedCells+cy.start, cy.num);
 671     }
 672   }
 673 }
 674
 675
 676 // ////////////////////////////////////////////////////////////////////////// //
 677 // this also clips to horizontal framebuffer extents
 678 struct ScanLine {
 679 private:
 680   //int mMinX;
 681   int mMaxX; // working area is [0..mMaxX) (i.e. `mMaxX` is not included)
 682   uint mMaxLen;
 683   int mLastX = /*0x7fff*/-666;
 684   ubyte* mCovers;
 685   ubyte** mStartPtrs;
 686   ushort* mCounts;
 687   uint mNumSpans;
 688   ubyte** mCurStartPtr;
 689   ushort* mCurCount;
 690
 691 public:
 692   static struct Iterator {
 693   private:
 694     const(ubyte)* mCovers;
 695     const(ushort)* mCurCount;
 696     const(ubyte*)* mCurStartPtr;
 697
 698   public nothrow @trusted @nogc:
 699     mixin(DisableCopyingMixin);
 700
 701     this (in ref ScanLine sl) pure {
 702       pragma(inline, true);
 703       mCovers = sl.mCovers;
 704       mCurCount = sl.mCounts;
 705       mCurStartPtr = sl.mStartPtrs;
 706     }
 707
 708     int next () {
 709       pragma(inline, true);
 710       ++mCurCount;
 711       ++mCurStartPtr;
 712       return cast(int)(*mCurStartPtr-mCovers);
 713     }
 714
 715     @property int pixelCount () const pure { pragma(inline, true); return cast(int)(*mCurCount); }
 716     @property const(ubyte)* covers () const pure { pragma(inline, true); return *mCurStartPtr; }
 717   }
 718
 719 public nothrow @trusted @nogc:
 720   mixin(DisableCopyingMixin);
 721
 722   ~this () {
 723     import core.stdc.stdlib : free;
 724     if (mCounts !is null) free(mCounts);
 725     if (mStartPtrs !is null) free(mStartPtrs);
 726     if (mCovers !is null) free(mCovers);
 727   }
 728
 729   auto iterator () const pure { pragma(inline, true); return Iterator(this); }
 730
 731   void reset (/*int minX, int maxX*/) {
 732     //immutable uint maxLen = ((minX <= maxX ? maxX-minX+2 : 2)|0x7ff)+1;
 733     mMaxX = VBufWidth;
 734     if (mMaxX < 0) mMaxX = 0;
 735     immutable uint maxLen = (mMaxX|0xff)+1;
 736     if (maxLen > mMaxLen) {
 737       import core.stdc.stdlib : realloc;
 738       mCovers = cast(ubyte*)realloc(mCovers, maxLen*mCovers[0].sizeof);
 739       if (mCovers is null) assert(0, "out of memory");
 740       mStartPtrs = cast(ubyte**)realloc(mStartPtrs, mStartPtrs[0].sizeof*maxLen);
 741       if (mStartPtrs is null) assert(0, "out of memory");
 742       mCounts = cast(ushort*)realloc(mCounts, mCounts[0].sizeof*maxLen);
 743       if (mCounts is null) assert(0, "out of memory");
 744       mMaxLen = maxLen;
 745     }
 746     resetSpans();
 747     //mMinX = minX;
 748   }
 749
 750   void resetSpans () {
 751     pragma(inline, true);
 752     mLastX = /*0x7fff*/-666;
 753     mCurCount = mCounts;
 754     mCurStartPtr = mStartPtrs;
 755     mNumSpans = 0;
 756   }
 757
 758   // WARNING! it really works only with [-32768..32767] range!
 759   // luckily, that's the max range of the canvas.
 760   // `num` should be positive! (zeroes are not allowed)
 761   void addSpan (int x, int num, ubyte cover) {
 762     import core.stdc.string : memset;
 763     if (x >= mMaxX) return; // out of bounds
 764     if (x < 0) {
 765       if ((num += x) <= 0) return; // out of bounds
 766       x = 0;
 767     } else if (x+num > mMaxX) {
 768       num = mMaxX-x;
 769     }
 770     //x -= mMinX;
 771     memset(mCovers+x, cover, cast(ushort)num);
 772     if (x == mLastX+1) {
 773       (*mCurCount) += cast(ushort)num;
 774     } else {
 775       *++mCurCount = cast(ushort)num;
 776       *++mCurStartPtr = mCovers+x;
 777       ++mNumSpans;
 778     }
 779     mLastX = x+num-1;
 780   }
 781
 782   void addCell (int x, ubyte cover) {
 783     if (x < 0 || x >= mMaxX) return; // out of bounds
 784     //x -= mMinX;
 785     mCovers[x] = cast(ubyte)cover;
 786     if (x == mLastX+1) {
 787       ++(*mCurCount);
 788     } else {
 789       *++mCurCount = 1;
 790       *++mCurStartPtr = mCovers+x;
 791       ++mNumSpans;
 792     }
 793     mLastX = x;
 794   }
 795
 796   //@property int baseX () const pure { pragma(inline, true); return mMinX; }
 797   enum baseX = 0;
 798   @property uint spanCount () const pure { pragma(inline, true); return mNumSpans; }
 799 }
 800
 801
 802 // ////////////////////////////////////////////////////////////////////////// //
 803 /* Polygon rasterizer that is used to render filled polygons with
 804   high-quality Anti-Aliasing. Internally, by default, the class uses
 805   integer coordinates in format 24.8, i.e. 24 bits for integer part
 806   and 8 bits for fractional - see PolyBaseShift. This class can be
 807   used in the following  way:
 808
 809   1. fillRule = FillRule.EvenOdd; // optional
 810   2. gamma() - optional.
 811   3. reset()
 812   4. moveTo(x, y) / lineTo(x, y) - make the polygon. One can create
 813      more than one contour, but each contour must consist of at least 3
 814      vertices, i.e. moveTo(x1, y1); lineTo(x2, y2); lineTo(x3, y3);
 815      is the absolute minimum of vertices that define a triangle.
 816      The algorithm does not check either the number of vertices nor
 817      coincidence of their coordinates, but in the worst case it just
 818      won't draw anything.
 819      The orger of the vertices (clockwise or counterclockwise)
 820      is important when using the non-zero filling rule (FillNonZero).
 821      In this case the vertex order of all the contours must be the same
 822      if you want your intersecting polygons to be without "holes".
 823      You actually can use different vertices order. If the contours do not
 824      intersect each other the order is not important anyway. If they do,
 825      contours with the same vertex order will be rendered without "holes"
 826      while the intersecting contours with different orders will have "holes".
 827
 828   fillRule() and gamma() can be called anytime before "sweeping".
 829 */
 830 public struct Rasterizer {
 831 public nothrow @trusted @nogc:
 832   enum {
 833     AAShift = 8,
 834     AANum = 1<<AAShift,
 835     AAMask = AANum-1,
 836     AA2Num = AANum<<1,
 837     AA2Mask = AA2Num-1,
 838   }
 839
 840 private:
 841   Outline mOutline;
 842   ScanLine mScanline;
 843   FillRule mFillingRule = FillRule.NonZero;
 844   ubyte[256] mGamma = DefaultGamma[];
 845
 846   // for gradient spans
 847   GxColor* xsg = null;
 848   uint xsgAllot = 0;
 849
 850 private:
 851   void ensureXSG (uint size) {
 852     if (!size) return;
 853     if (size > 0x00ff_ffffU) assert(0, "out of memory");
 854     size = (size|0xffU)+1U;
 855     if (xsgAllot < size) {
 856       import core.stdc.stdlib : realloc;
 857       GxColor* nc = cast(GxColor*)realloc(xsg, size*GxColor.sizeof);
 858       if (nc is null) assert(0, "out of memory");
 859       xsg = nc;
 860       xsgAllot = size;
 861     }
 862   }
 863
 864 public:
 865   static void renderSL (in ref ScanLine sl, in int y, in GxColor clr, in ref GxRect clipRect) {
 866     uint spanCount = sl.spanCount;
 867     immutable int baseX = sl.baseX;
 868     uint* row = vglTexBuf+cast(uint)y*cast(uint)VBufWidth;
 869     auto span = sl.iterator;
 870     do {
 871       int x = span.next+baseX;
 872       int pixelCount = span.pixelCount;
 873       int leftSkip = void;
 874       if (clipRect.clipHStripe(ref x, y, ref pixelCount, &leftSkip)) {
 875         const(ubyte)* covers = span.covers+leftSkip;
 876         memBlendColorCoverage(row+x, covers, clr, pixelCount);
 877       }
 878     } while (--spanCount);
 879   }
 880
 881   //FIXME: this is SLOW!
 882   void renderSLGrad(SG) (in ref ScanLine sl, in int y, auto ref SG spangen, in ref GxRect clipRect) if (AGGIsGoodGradient!SG) {
 883     uint spanCount = sl.spanCount;
 884     immutable int baseX = sl.baseX;
 885     uint* row = vglTexBuf+cast(uint)y*cast(uint)VBufWidth;
 886     auto span = sl.iterator;
 887     do {
 888       int x = span.next+baseX;
 889       int pixelCount = span.pixelCount;
 890       int leftSkip = void;
 891       if (clipRect.clipHStripe(ref x, y, ref pixelCount, &leftSkip)) {
 892         const(ubyte)* covers = span.covers+leftSkip;
 893         ensureXSG(cast(uint)pixelCount);
 894         spangen.colorSpanAtXY(x, y, xsg[0..cast(uint)pixelCount]);
 895         //memBlendColorCoverage(row+x, covers, clr, pixelCount);
 896         version(all) {
 897           // this is slightly faster than the naive code below
 898           uint* dp = row+x;
 899           foreach (GxColor clr; xsg[0..cast(uint)pixelCount]) {
 900             immutable uint cvr = *covers++;
 901             if (!cvr || !(clr&gxAlphaMask)) { ++dp; continue; } // nothing to do
 902             if (cvr == 255 && (clr&gxAlphaMask) == gxAlphaMask) { *dp++ = clr; continue; } // opaque
 903             // need to mix
 904             immutable uint a_ = (((clr>>24)*(cvr+1U))>>8)+1u; // to not loose bits
 905             uint rb_ = (*dp)&0xff00ffu;
 906             uint g_  = (*dp)&0x00ff00u;
 907             rb_ += (((clr&0xff00ffu)-rb_)*a_)>>8;
 908             g_  += (((clr&0x00ff00u)-g_)*a_)>>8;
 909             *dp++ = (rb_&0xff00ffu)|(g_&0xff_00ff00u)|gxAlphaMask;
 910           }
 911         } else {
 912           ubyte* p = cast(ubyte*)(row+x);
 913           foreach (GxColor clr; xsg[0..cast(uint)pixelCount]) {
 914             immutable uint cb = clr&0xff;
 915             immutable uint cg = (clr>>8)&0xff;
 916             immutable uint cr = (clr>>16)&0xff;
 917             immutable uint ca = clr>>24;
 918             immutable uint cvr = *covers++;
 919             if (!cvr) { p += 4; continue; }
 920             immutable uint alpha = ca*(cvr+1); // to not loose bits
 921             uint v = *p; *p++ = cast(ubyte)((((cb-v)*alpha)>>16)+v);
 922                  v = *p; *p++ = cast(ubyte)((((cg-v)*alpha)>>16)+v);
 923                  v = *p; *p++ = cast(ubyte)((((cr-v)*alpha)>>16)+v);
 924             *p++ = 0xff;
 925           }
 926         }
 927       }
 928     } while (--spanCount);
 929   }
 930
 931 private:
 932   ubyte calculateAlpha (in int area) const pure {
 933     int cover = area>>(PolyBaseShift*2+1-AAShift);
 934     if (cover < 0) cover = -cover;
 935     if (mFillingRule == FillRule.EvenOdd) {
 936       cover &= AA2Mask;
 937       if (cover > AANum) cover = AA2Num-cover;
 938     }
 939     //if (cover > AAMask) cover = AAMask;
 940     //return cover;
 941     return (cover < AAMask ? cast(ubyte)cover : cast(ubyte)AAMask);
 942   }
 943
 944 public:
 945   mixin(DisableCopyingMixin);
 946
 947   ~this () {
 948     if (xsg !is null) {
 949       import core.stdc.stdlib : free;
 950       free(xsg);
 951       xsg = null;
 952       xsgAllot = 0;
 953     }
 954   }
 955
 956   void reset () { mOutline.reset(); }
 957
 958   @property FillRule fillRule () const pure { pragma(inline, true); return mFillingRule; }
 959   @property void fillRule (in FillRule v) { pragma(inline, true); mFillingRule = v; }
 960
 961   void gamma (in float g) {
 962     foreach (immutable uint i; 0..256) {
 963       //import std.math : pow;
 964       import core.stdc.math : powf;
 965       mGamma.ptr[i] = cast(ubyte)(powf(cast(float)i/255.0f, g)*255.0f);
 966     }
 967   }
 968
 969   void gamma (const(ubyte)[] g) {
 970     if (g.length != 256) assert(0, "invalid gamma array");
 971     mGamma[] = g[0..256];
 972   }
 973
 974   @property float currX () const pure { pragma(inline, true); return mOutline.currX; }
 975   @property float currY () const pure { pragma(inline, true); return mOutline.currY; }
 976
 977   void moveToFixed (int x, int y) {
 978     if ((x>>PolyBaseShift) <= short.min+8 || (x>>PolyBaseShift) >= short.max-8 ||
 979         (y>>PolyBaseShift) <= short.min+8 || (y>>PolyBaseShift) >= short.max-8) assert(0, "coordinates out of bounds");
 980     mOutline.moveTo(x, y);
 981   }
 982
 983   void lineToFixed (int x, int y) {
 984     if ((x>>PolyBaseShift) <= short.min+8 || (x>>PolyBaseShift) >= short.max-8 ||
 985         (y>>PolyBaseShift) <= short.min+8 || (y>>PolyBaseShift) >= short.max-8) assert(0, "coordinates out of bounds");
 986     mOutline.lineTo(x, y);
 987   }
 988
 989   void moveTo (in float x, in float y) { mOutline.moveTo(polyCoord(x), polyCoord(y)); }
 990   void lineTo (in float x, in float y) { mOutline.lineTo(polyCoord(x), polyCoord(y)); }
 991
 992   @property int minX () const pure { pragma(inline, true); return mOutline.minX; }
 993   @property int minY () const pure { pragma(inline, true); return mOutline.minY; }
 994   @property int maxX () const pure { pragma(inline, true); return mOutline.maxX; }
 995   @property int maxY () const pure { pragma(inline, true); return mOutline.maxY; }
 996
 997
 998   //WARNING! `clipRect` should never go out of framebuffer bounds!
 999   void render(SG) (in ref GxRect clipRect, auto ref SG spangen) if (AGGIsGoodSpanGen!SG) {
1000     if (clipRect.empty) return;
1001
1002     immutable int y0 = clipRect.y0;
1003     immutable int y1 = clipRect.y1;
1004     immutable int x1 = clipRect.x1;
1005
1006     //const(Cell)** cells = mOutline.cells();
1007     //if (mOutline.numCells() == 0) return;
1008     const(Cell)** cells = mOutline.getCellsForYOrMore(y0);
1009     if (cells is null || *cells is null) return;
1010     if ((*cells).y > y1) return;
1011
1012     if (!clipRect.overlaps(GxRect(mOutline.minX, mOutline.minY, mOutline.maxX-mOutline.minX+1, mOutline.maxY-mOutline.minY+1))) return;
1013
1014     static if (AGGIsGoodSingleColor!SG) {
1015       immutable GxColor sc = spangen;
1016     }
1017
1018     mScanline.reset(/*mOutline.minX, mOutline.maxX*/);
1019
1020     /*
1021       k8: this code resets `cover` on each new scanline. this is what AGG does.
1022       the original code accumulated `cover` through the whole cell array. why?
1023      */
1024     const(Cell)* currCell = *cells++;
1025
1026     while (currCell !is null) {
1027       immutable int currY = currCell.y;
1028       if (currY > y1) break; // no more
1029       assert(currCell.y >= y0);
1030
1031       int cover = 0;
1032       for (;;) {
1033         const(Cell)* startCell = currCell;
1034         immutable uint coord = currCell.getPackedCoord;
1035         int x = currCell.x;
1036         if (x > x1) break; // there's nothing to render on this line anymore
1037
1038         int area = startCell.area;
1039         cover += startCell.cover;
1040
1041         // accumulate all start cells
1042         while ((currCell = *cells++) !is null) {
1043           if (currCell.getPackedCoord != coord) break;
1044           area += currCell.area;
1045           cover += currCell.cover;
1046         }
1047
1048         if (area) {
1049           immutable ubyte alpha = calculateAlpha((cover<<(PolyBaseShift+1))-area);
1050           if (alpha && mGamma.ptr[alpha]) mScanline.addCell(x, mGamma.ptr[alpha]);
1051           ++x;
1052         }
1053
1054         if (currCell is null || currCell.y != currY) break;
1055
1056         if (currCell.x > x) {
1057           immutable ubyte alpha = calculateAlpha(cover<<(PolyBaseShift+1));
1058           if (alpha && mGamma.ptr[alpha]) mScanline.addSpan(x, currCell.x-x, mGamma.ptr[alpha]);
1059         }
1060       }
1061
1062       // flush scanline
1063       if (mScanline.spanCount) {
1064         static if (AGGIsGoodSingleColor!SG) {
1065           renderSL(mScanline, cast(uint)currY, sc, clipRect);
1066         } else static if (AGGIsGoodVerticalGradient!SG) {
1067           renderSL(mScanline, cast(uint)currY, spangen.colorAtY(currY), clipRect);
1068         } else static if (AGGIsGoodGradient!SG) {
1069           renderSLGrad(mScanline, cast(uint)currY, spangen, clipRect);
1070         } else {
1071           static assert(0, "unknown span color generator type");
1072         }
1073         mScanline.resetSpans();
1074       }
1075
1076       // skip clipped part
1077       if (currCell !is null && currCell.y == currY) {
1078         cells = mOutline.getCellsForYOrMore(currY+1);
1079         if (cells is null) break;
1080         currCell = *cells++;
1081       }
1082     }
1083   }
1084
1085
1086   // returns "gamma alpha" (0 means "no hit")
1087   ubyte hitTest (in int tx, in int ty) {
1088     // clip by framebuffer
1089     if (tx < 0 || ty < 0 || tx >= VBufWidth || ty >= VBufHeight) return 0;
1090
1091     const(Cell)** cells = mOutline.getCellsForY(ty);
1092     if (cells is null) return 0;
1093
1094     int cover = 0;
1095     const(Cell)* currCell = *cells++;
1096     assert(currCell.y == ty);
1097
1098     while (currCell !is null) {
1099       const(Cell)* startCell = currCell;
1100       immutable uint coord = currCell.getPackedCoord;
1101       int x = currCell.x;
1102       if (tx < x) return 0;
1103
1104       int area = startCell.area;
1105       cover += startCell.cover;
1106
1107       while ((currCell = *cells++) !is null) {
1108         if (currCell.getPackedCoord != coord) break;
1109         area += currCell.area;
1110         cover += currCell.cover;
1111       }
1112
1113       if (area) {
1114         if (tx == x) {
1115           immutable ubyte alpha = calculateAlpha((cover<<(PolyBaseShift+1))-area);
1116           return (alpha ? mGamma.ptr[alpha] : 0);
1117         }
1118         ++x;
1119       }
1120
1121       if (currCell is null || currCell.y != ty) break;
1122
1123       if (currCell.x > x && tx >= x && tx < currCell.x) {
1124         immutable ubyte alpha = calculateAlpha(cover<<(PolyBaseShift+1));
1125         return (alpha ? mGamma.ptr[alpha] : 0);
1126       }
1127     }
1128
1129     return 0;
1130   }
1131
1132 private:
1133   static immutable ubyte[256] DefaultGamma = [
1134       0,  0,  1,  1,  2,  2,  3,  4,  4,  5,  5,  6,  7,  7,  8,  8,
1135       9, 10, 10, 11, 11, 12, 13, 13, 14, 14, 15, 16, 16, 17, 18, 18,
1136      19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28,
1137      29, 29, 30, 30, 31, 32, 32, 33, 34, 34, 35, 36, 36, 37, 37, 38,
1138      39, 39, 40, 41, 41, 42, 43, 43, 44, 45, 45, 46, 47, 47, 48, 49,
1139      49, 50, 51, 51, 52, 53, 53, 54, 55, 55, 56, 57, 57, 58, 59, 60,
1140      60, 61, 62, 62, 63, 64, 65, 65, 66, 67, 68, 68, 69, 70, 71, 71,
1141      72, 73, 74, 74, 75, 76, 77, 78, 78, 79, 80, 81, 82, 83, 83, 84,
1142      85, 86, 87, 88, 89, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99,
1143     100,101,101,102,103,104,105,106,107,108,109,110,111,112,114,115,
1144     116,117,118,119,120,121,122,123,124,126,127,128,129,130,131,132,
1145     134,135,136,137,139,140,141,142,144,145,146,147,149,150,151,153,
1146     154,155,157,158,159,161,162,164,165,166,168,169,171,172,174,175,
1147     177,178,180,181,183,184,186,188,189,191,192,194,195,197,199,200,
1148     202,204,205,207,209,210,212,214,215,217,219,220,222,224,225,227,
1149     229,230,232,234,236,237,239,241,242,244,246,248,249,251,253,255
1150   ];
1151 }