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