vox_texatlas.d

   1 module vox_texatlas;
   2
   3 import iv.bclamp;
   4 import iv.glbinds.utils;
   5 import iv.cmdcongl;
   6 import iv.strex;
   7 import iv.vfs;
   8 import iv.vfs.io;
   9 import iv.vmath;
  10
  11
  12 // ////////////////////////////////////////////////////////////////////////// //
  13 public __gshared bool vox_reuse_colors = false;
  14
  15
  16 // ////////////////////////////////////////////////////////////////////////// //
  17 struct VoxTexAtlas {
  18 public:
  19   static struct Rect {
  20     int x, y, w, h;
  21     alias x0 = x;
  22     alias y0 = y;
  23     pure nothrow @safe @nogc {
  24       static Rect Invalid () { pragma(inline, true); return Rect.init; }
  25       bool isValid () const { pragma(inline, true); return (x >= 0 && y >= 0 && w > 0 && h > 0); }
  26       int getArea () const { pragma(inline, true); return w*h; }
  27       int getX1 () const { pragma(inline, true); return x+w; }
  28       int getY1 () const { pragma(inline, true); return y+h; }
  29     }
  30   }
  31
  32   // texture coords in atlas
  33   static struct FRect {
  34     float x0, y0, x1, y1;
  35   }
  36
  37 private:
  38   int imgWidth, imgHeight;
  39   Rect[] rects;
  40
  41   enum BadRect = uint.max;
  42
  43 public:
  44   void clear () {
  45     delete rects; rects = null;
  46     imgWidth = imgHeight = 0;
  47   }
  48
  49   void setSize (int awdt, int ahgt) {
  50     clear();
  51     assert(awdt > 0 && ahgt > 0);
  52     imgWidth = awdt;
  53     imgHeight = ahgt;
  54     rects ~= Rect(0, 0, awdt, ahgt); // one big rect
  55     rects.assumeSafeAppend;
  56   }
  57
  58   @property const pure nothrow @safe @nogc {
  59     int width () { pragma(inline, true); return imgWidth; }
  60     int height () { pragma(inline, true); return imgHeight; }
  61   }
  62
  63   FRect texCoords (in Rect rc) const pure nothrow @safe @nogc {
  64     FRect res;
  65     res.x0 = (cast(float)rc.x+0.5f)/cast(float)imgWidth;
  66     res.y0 = (cast(float)rc.y+0.5f)/cast(float)imgHeight;
  67     res.x1 = (cast(float)(rc.x+rc.w)+0.5f)/cast(float)imgWidth;
  68     res.y1 = (cast(float)(rc.y+rc.h)+0.5f)/cast(float)imgHeight;
  69     return res;
  70   }
  71
  72   // node id or BadRect
  73   private uint findBestFit (int w, int h) nothrow @trusted @nogc {
  74     uint fitW = BadRect, fitH = BadRect, biggest = BadRect;
  75
  76     foreach (immutable idx, const ref r; rects) {
  77       if (r.w < w || r.h < h) continue; // absolutely can't fit
  78       if (r.w == w && r.h == h) return cast(uint)idx; // perfect fit
  79       if (r.w == w) {
  80         // width fit
  81         if (fitW == BadRect || rects.ptr[fitW].h < r.h) fitW = cast(uint)idx;
  82       } else if (r.h == h) {
  83         // height fit
  84         if (fitH == BadRect || rects.ptr[fitH].w < r.w) fitH = cast(uint)idx;
  85       } else {
  86         // get biggest rect
  87         if (biggest == BadRect || rects.ptr[biggest].getArea() > r.getArea()) biggest = cast(uint)idx;
  88       }
  89     }
  90     // both?
  91     if (fitW != BadRect && fitH != BadRect) return (rects.ptr[fitW].getArea() > rects.ptr[fitH].getArea() ? fitW : fitH);
  92     if (fitW != BadRect) return fitW;
  93     if (fitH != BadRect) return fitH;
  94     return biggest;
  95   }
  96
  97   // returns invalid rect if there's no room
  98   Rect insert (int cwdt, int chgt/*, const(uint)[] colors*/) {
  99     assert(cwdt > 0 && chgt > 0);
 100     auto ri = findBestFit(cwdt, chgt);
 101     if (ri == BadRect) return Rect.Invalid;
 102     auto rc = rects.ptr[ri];
 103     auto res = Rect(rc.x, rc.y, cwdt, chgt);
 104     // split this rect
 105     if (rc.w == res.w && rc.h == res.h) {
 106       // best fit, simply remove this rect
 107       foreach (immutable cidx; ri+1..rects.length) rects.ptr[cidx-1] = rects.ptr[cidx];
 108       rects.length -= 1;
 109       rects.assumeSafeAppend; // for future; we probably won't have alot of best-fitting nodes initially
 110     } else {
 111       if (rc.w == res.w) {
 112         // split vertically
 113         rc.y += res.h;
 114         rc.h -= res.h;
 115       } else if (rc.h == res.h) {
 116         // split horizontally
 117         rc.x += res.w;
 118         rc.w -= res.w;
 119       } else {
 120         Rect nr = rc;
 121         // split in both directions (by longer edge)
 122         if (rc.w-res.w > rc.h-res.h) {
 123           // cut the right part
 124           nr.x += res.w;
 125           nr.w -= res.w;
 126           // cut the bottom part
 127           rc.y += res.h;
 128           rc.h -= res.h;
 129           rc.w = res.w;
 130         } else {
 131           // cut the bottom part
 132           nr.y += res.h;
 133           nr.h -= res.h;
 134           // cut the right part
 135           rc.x += res.w;
 136           rc.w -= res.w;
 137           rc.h = res.h;
 138         }
 139         rects ~= nr;
 140         rects.assumeSafeAppend;
 141       }
 142       rects.ptr[ri] = rc;
 143     }
 144     return res;
 145   }
 146 }
 147
 148
 149 // ////////////////////////////////////////////////////////////////////////// //
 150 // just a compact representation of a rectange
 151 align(1) struct VoxRect16 {
 152 align(1):
 153   uint xy = 0; // low word: x; high word: y
 154   uint wh = 0; // low word: w; high word: h
 155
 156   nothrow @safe @nogc {
 157     uint getX () const pure { pragma(inline, true); return (xy&0xffffU); }
 158     uint getY () const pure { pragma(inline, true); return (xy>>16); }
 159     void setX (uint x) { pragma(inline, true); xy = (xy&0xffff0000U)|(x&0xffffU); }
 160     void setY (uint y) { pragma(inline, true); xy = (xy&0x0000ffffU)|(y<<16); }
 161
 162     uint getW () const pure { pragma(inline, true); return (wh&0xffffU); }
 163     uint getH () const pure { pragma(inline, true); return (wh>>16); }
 164     void setW (uint w) { pragma(inline, true); wh = (wh&0xffff0000U)|(w&0xffffU); }
 165     void setH (uint h) { pragma(inline, true); wh = (wh&0x0000ffffU)|(h<<16); }
 166
 167     bool isValid () const pure { pragma(inline, true); return (wh != 0); }
 168
 169     static VoxRect16 Zero () pure { pragma(inline, true); return VoxRect16(0, 0); }
 170   }
 171 }
 172
 173
 174 // ////////////////////////////////////////////////////////////////////////// //
 175 // color atlas, ready to be uploaded to the GPU
 176 struct VoxColorPack {
 177 public:
 178   static struct ColorItem {
 179     VoxRect16 rc; // start position; (relative to parent, or to (0,0)
 180     uint newxy; // used in relayouter
 181     int parent; // topmost parent color item, or -1
 182     int next; // -1: no more
 183
 184     bool isRelative () const pure nothrow @safe @nogc { pragma(inline, true); return (parent >= 0); }
 185   }
 186
 187 public:
 188   uint clrwdt, clrhgt;
 189   uint[] colors; // clrwdt by clrhgt
 190
 191   ColorItem[] citems;
 192   int[uint] citemhash; // key: color index; value: index in `citems`
 193
 194   VoxTexAtlas atlas;
 195
 196 public:
 197   uint getWidth () const pure nothrow @safe @nogc { pragma(inline, true); return clrwdt; }
 198   uint getHeight () const pure nothrow @safe @nogc { pragma(inline, true); return clrhgt; }
 199
 200   uint getTexX (uint cidx, ref in VoxRect16 rc) const pure nothrow @safe @nogc {
 201     pragma(inline, true);
 202     return citems[cidx].rc.getX()+rc.getX();
 203   }
 204
 205   uint getTexY (uint cidx, ref in VoxRect16 rc) const pure nothrow @safe @nogc {
 206     pragma(inline, true);
 207     return citems[cidx].rc.getY()+rc.getY();
 208   }
 209
 210
 211   void clear () {
 212     delete colors; colors = null;
 213     delete citems; citems = null;
 214     citemhash.clear();
 215     atlas.clear();
 216   }
 217
 218
 219   // prepare for new run
 220   void reset () {
 221     clear();
 222   }
 223
 224
 225   // grow image, and relayout everything
 226   void growImage (uint inswdt, uint inshgt) {
 227     uint neww = clrwdt, newh = clrhgt;
 228     while (neww < inswdt) neww <<= 1;
 229     while (newh < inshgt) newh <<= 1;
 230     for (;;) {
 231       if (neww < newh) neww <<= 1; else newh <<= 1;
 232       // relayout data
 233       bool again = false;
 234       atlas.setSize(neww, newh);
 235       for (int f = 0; f < cast(int)citems.length; ++f) {
 236         ColorItem *ci = &citems[f];
 237         if (ci.isRelative()) continue;
 238         auto rc = atlas.insert(cast(int)ci.rc.getW(), cast(int)ci.rc.getH());
 239         if (!rc.isValid()) {
 240           // alas, no room
 241           again = true;
 242           break;
 243         }
 244         // record new coords
 245         ci.newxy = ((cast(uint)rc.y)<<16)|((cast(uint)rc.x)&0xffffU);
 246       }
 247       if (!again) break; // done
 248     }
 249
 250     // allocate new image, copy old data
 251     conwriteln("ATLAS: resized from ", clrwdt, "x", clrhgt, " to ", neww, "x", newh);
 252     uint[] newclr = new uint[neww*newh];
 253     newclr[] = 0;
 254     for (int f = 0; f < cast(int)citems.length; ++f) {
 255       ColorItem *ci = &citems[f];
 256       if (ci.isRelative()) continue;
 257       const uint newx = ci.newxy&0xffffU;
 258       const uint newy = ci.newxy>>16;
 259       const uint rcw = ci.rc.getW();
 260       uint oaddr = ci.rc.getY()*clrwdt+ci.rc.getX();
 261       uint naddr = newy*neww+newx;
 262       uint dy = ci.rc.getH();
 263       /*
 264       conwriteln(": : : oldpos=(", ci.rc.getX(), ",", ci.rc.getY(), "); newpos=(", newx, ",",
 265                  newy, "); size=(", rcw, "x", ci.rc.getH(), "); oaddr=", oaddr, "; naddr=", naddr);
 266       */
 267       while (dy--) {
 268         newclr[naddr..naddr+rcw] = colors[oaddr..oaddr+rcw];
 269         oaddr += clrwdt;
 270         naddr += neww;
 271       }
 272       ci.rc.setX(newx);
 273       ci.rc.setY(newy);
 274     }
 275     delete colors;
 276     colors = newclr;
 277     clrwdt = neww;
 278     clrhgt = newh;
 279     newclr = null;
 280   }
 281
 282
 283   // returns true if found, and sets `*cidxp` and `*xyofsp`
 284   // `*xyofsp` is offset inside `cidxp`
 285   bool findRectEx (const(uint)[] clrs, uint cwdt, uint chgt, uint cxofs, uint cyofs,
 286                    uint wdt, uint hgt, uint *cidxp, VoxRect16 *xyofsp)
 287   {
 288     assert(wdt > 0 && hgt > 0);
 289     assert(cwdt >= wdt && chgt >= hgt);
 290
 291     const uint saddrOrig = cyofs*cwdt+cxofs;
 292     auto cp = clrs[saddrOrig] in citemhash;
 293     if (!cp) return false;
 294
 295     for (int cidx = *cp; cidx >= 0; cidx = citems[cidx].next) {
 296       const ColorItem *ci = &citems[cidx];
 297       if (wdt > ci.rc.getW() || hgt > ci.rc.getH()) continue; // impossibiru
 298       // compare colors
 299       bool ok = true;
 300       uint saddr = saddrOrig;
 301       uint caddr = void;
 302       if (ci.isRelative()) {
 303         const ColorItem *cip = &citems[ci.parent];
 304         caddr = (cip.rc.getY()+ci.rc.getY())*clrwdt+(cip.rc.getX()+ci.rc.getX());
 305       } else {
 306         caddr = ci.rc.getY()*clrwdt+ci.rc.getX();
 307       }
 308       for (uint dy = 0; dy < hgt; ++dy) {
 309         if (colors[caddr..caddr+wdt] != clrs[saddr..saddr+wdt]) {
 310           ok = false;
 311           break;
 312         }
 313         saddr += cwdt;
 314         caddr += clrwdt;
 315       }
 316       if (ok) {
 317         // i found her!
 318         if (ci.isRelative()) {
 319           // subrect
 320           if (cidxp !is null) *cidxp = cast(uint)ci.parent;
 321           if (xyofsp !is null) *xyofsp = ci.rc;
 322         } else {
 323           // topmost
 324           if (cidxp !is null) *cidxp = cast(uint)cidx;
 325           if (xyofsp !is null) *xyofsp = VoxRect16.Zero();
 326         }
 327         if (xyofsp !is null) {
 328           (*xyofsp).setW(wdt);
 329           (*xyofsp).setH(hgt);
 330         }
 331         return true;
 332       }
 333     }
 334
 335     return false;
 336   }
 337
 338
 339   bool findRect (const(uint)[] clrs, uint wdt, uint hgt, uint *cidxp, VoxRect16 *xyofsp) {
 340     return findRectEx(clrs, wdt, hgt, 0, 0, wdt, hgt, cidxp, xyofsp);
 341   }
 342
 343
 344   // returns index in `citems`
 345   uint addNewRect (const(uint)[] clrs, uint wdt, uint hgt) {
 346     assert(wdt > 0 && hgt > 0);
 347     VoxRect16 coord;
 348
 349     if (clrwdt == 0) {
 350       // no rects yet
 351       assert(clrhgt == 0);
 352       clrwdt = 1;
 353       while (clrwdt < wdt) clrwdt <<= 1;
 354       clrhgt = 1;
 355       while (clrhgt < hgt) clrhgt <<= 1;
 356       if (clrhgt < clrwdt) clrhgt = clrwdt; //!!
 357       atlas.setSize(clrwdt, clrhgt);
 358       coord.setX(0);
 359       coord.setY(0);
 360       colors.length = clrwdt*clrhgt;
 361       colors[] = 0;
 362     } else {
 363       // insert into atlas; grow texture if cannot insert
 364       for (;;) {
 365         auto rc = atlas.insert(cast(int)wdt, cast(int)hgt);
 366         if (rc.isValid()) {
 367           coord.setX(rc.x);
 368           coord.setY(rc.y);
 369           break;
 370         }
 371         // no room, grow the texture, and relayout everything
 372         growImage(wdt, hgt);
 373       }
 374     }
 375     coord.setW(wdt);
 376     coord.setH(hgt);
 377
 378     // copy source colors into the atlas image
 379     uint saddr = 0;
 380     uint daddr = coord.getY()*clrwdt+coord.getX();
 381     for (uint dy = 0; dy < hgt; ++dy) {
 382       colors[daddr..daddr+wdt] = clrs[saddr..saddr+wdt];
 383       saddr += wdt;
 384       daddr += clrwdt;
 385     }
 386
 387     // hash main rect
 388     ColorItem ci;
 389     ci.rc = coord;
 390     ci.parent = -1;
 391     const int parentIdx = cast(int)citems.length;
 392     auto cpp = clrs[0] in citemhash;
 393     if (cpp) {
 394       ci.next = *cpp;
 395       *cpp = parentIdx;
 396     } else {
 397       ci.next = -1;
 398       citemhash[clrs[0]] = parentIdx;
 399     }
 400     citems ~= ci;
 401     citems.assumeSafeAppend;
 402
 403     // hash all subrects
 404     //uint xxci;
 405     //VoxRect16 xxrc;
 406     if (vox_reuse_colors) {
 407       for (uint dy = 0; dy < hgt; ++dy) {
 408         for (uint dx = 0; dx < wdt; ++dx) {
 409           if ((dx+dy) == 0) continue;
 410           version(none) {
 411             if (findRectEx(clrs, wdt, hgt, dx, dy, wdt-dx, hgt-dy, null, null)) {
 412               /*
 413               conwriteln("    dup subrect of (", coord.getX(), ",", coord.getY(), ")-(",
 414                          wdt, "x", hgt, "): (", dx, ",", dy, ")-(", wdt-dx, "x", hgt-dy, ")",
 415                          " : xxci=", xxci, "; xxrc=(", xxrc.getX(), ",", xxrc.getY(), ")-(",
 416                          xxrc.getW(), "x", xxrc.getH(), ")");
 417               */
 418               continue;
 419             }
 420           }
 421           // new subrect, append it
 422           /*
 423           conwriteln("    new subrect of (", coord.getX(), ",", coord.getY(), ")-(",
 424                      wdt, "x", hgt, "): (", dx, ",", dy, ")-(", wdt-dx, "x", hgt-dy, ")");
 425           */
 426           ci.rc.setX(dx);
 427           ci.rc.setY(dy);
 428           ci.rc.setW(wdt-dx);
 429           ci.rc.setH(hgt-dy);
 430           ci.parent = cast(uint)parentIdx;
 431           const uint cc = clrs[dy*wdt+dx];
 432           cpp = cc in citemhash;
 433           if (cpp) {
 434             ci.next = *cpp;
 435             *cpp = cast(int)citems.length;
 436           } else {
 437             ci.next = -1;
 438             citemhash[cc] = cast(int)citems.length;
 439           }
 440           citems ~= ci;
 441           citems.assumeSafeAppend;
 442         }
 443       }
 444     }
 445
 446     return cast(uint)parentIdx;
 447   }
 448 }