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