vox_data.d

   1 module vox_data;
   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 static import iv.timer;
  12
  13 import vox_3dbmp;
  14
  15
  16 // ////////////////////////////////////////////////////////////////////////// //
  17 static align(1) struct VoxXYZ16 {
  18 align(1):
  19   ushort x = void, y = void, z = void;
  20 }
  21
  22
  23 // ////////////////////////////////////////////////////////////////////////// //
  24 /*
  25   this is a struct that keeps info about an individual voxel.
  26   it keeps voxel color, and face visibility info.
  27  */
  28 align(1) struct VoxPix {
  29 align(1):
  30   ubyte b, g, r;
  31   ubyte cull;
  32   uint nextz; // voxel with the next z; 0 means "no more"
  33   ushort z; // z of the current voxel
  34
  35   uint rgb () const pure nothrow @safe @nogc {
  36     pragma(inline, true);
  37     return 0xff000000U|b|(cast(uint)g<<8)|(cast(uint)r<<16);
  38   }
  39
  40   uint rgbcull () const pure nothrow @safe @nogc {
  41     pragma(inline, true);
  42     return b|(cast(uint)g<<8)|(cast(uint)r<<16)|(cast(uint)cull<<24);
  43   }
  44 }
  45
  46
  47 // ////////////////////////////////////////////////////////////////////////// //
  48 /*
  49   this keeps voxel "voxmap" (it's like a pixmap, but with voxels instead
  50   of pixels). the representation is slightly optimised, tho: it keeps only
  51   actually used voxels, in vertical "slabs". as most voxel models have only
  52   contour voxels stored, this greatly reduces memory consumption. quering
  53   the individial voxel data is slightly slower, tho, but for our case it is
  54   not really important.
  55
  56   there are some methods to "optimise" the voxmap. for example, to fix voxel
  57   face visibility info, and to remove "internal" voxels (it is called "hollow fill").
  58
  59   also note that some optimisation methods may leave empty voxels in the voxmap.
  60   they have `cull` field equal to zero.
  61
  62   to build a voxmap you simply call `addVoxel()` method, optionally providing
  63   the face visibility info. but you can use `0x3f` as a visibility, and then ask
  64   `VoxelData` object to calculate the proprer "cull" values for you. you can also
  65   add "internal" voxels, and then ask the object to fix the vixmap for you, removing
  66   all the unnecessary data.
  67  */
  68 struct VoxelData {
  69 public:
  70   uint xsize = 0, ysize = 0, zsize = 0;
  71   float cx = 0.0f, cy = 0.0f, cz = 0.0f;
  72
  73   VoxPix[] data; // [0] is never used
  74   // xsize*ysize array, offsets in `data`; 0 means "no data here"
  75   // slabs are sorted from bottom to top, and never intersects
  76   uint[] xyofs;
  77   uint freelist = 0;
  78   uint voxpixtotal = 0;
  79
  80 private:
  81   uint allocVox () nothrow @safe {
  82     assert(data.length);
  83     ++voxpixtotal;
  84     if (!freelist) {
  85       if (data.length >= 0x3fffffffU) assert(0, "too many voxels");
  86       const uint lastel = cast(uint)data.length;
  87       data.length += 1024;
  88       freelist = cast(uint)data.length-1;
  89       while (freelist >= lastel) {
  90         data[freelist].nextz = freelist+1;
  91         --freelist;
  92       }
  93       freelist = lastel;
  94       data[$-1].nextz = 0;
  95     }
  96     const uint res = freelist;
  97     freelist = data[res].nextz;
  98     return res;
  99   }
 100
 101 public:
 102   void clear () {
 103     delete data;
 104     data = null;
 105     delete xyofs;
 106     xyofs = null;
 107     xsize = ysize = zsize = 0;
 108     cx = cy = cz = 0.0f;
 109     freelist = 0;
 110     voxpixtotal = 0;
 111   }
 112
 113   void setSize (uint xs, uint ys, uint zs) {
 114     clear();
 115     if (!xs || !ys || !zs) return;
 116     xsize = xs;
 117     ysize = ys;
 118     zsize = zs;
 119     xyofs = new uint[xsize*ysize];
 120     xyofs[] = 0;
 121     data.length = 1; // data[0] is never used
 122   }
 123
 124   uint getDOfs (int x, int y) const nothrow @trusted @nogc {
 125     pragma(inline, true);
 126     if (x < 0 || y < 0) return 0;
 127     if (cast(uint)x >= xsize || cast(uint)y >= ysize) return 0;
 128     return xyofs.ptr[cast(uint)y*xsize+cast(uint)x];
 129   }
 130
 131   // high byte is cull info
 132   // returns 0 if there is no such voxel
 133   uint voxofs (int x, int y, int z) const nothrow @safe @nogc {
 134     uint dofs = getDOfs(x, y);
 135     while (dofs) {
 136       if (data[dofs].z == cast(ushort)z) return dofs;
 137       if (data[dofs].z > cast(ushort)z) return 0;
 138       dofs = data[dofs].nextz;
 139     }
 140     return 0;
 141   }
 142
 143   // high byte is cull info
 144   // returns 0 if there is no such voxel
 145   uint query (int x, int y, int z) const nothrow @safe @nogc {
 146     immutable uint dofs = voxofs(x, y, z);
 147     if (!dofs) return 0;
 148     if (!data[dofs].cull) return 0;
 149     return data[dofs].rgbcull();
 150   }
 151
 152   VoxPix *queryVP (int x, int y, int z) nothrow @trusted @nogc {
 153     pragma(inline, true);
 154     immutable uint dofs = voxofs(x, y, z);
 155     return (dofs ? &data[dofs] : null);
 156   }
 157
 158   // high byte is cull info
 159   // returns 0 if there is no such voxel
 160   ubyte queryCull (int x, int y, int z) const nothrow @safe @nogc {
 161     immutable uint dofs = voxofs(x, y, z);
 162     return (dofs ? data[dofs].cull : 0);
 163   }
 164
 165   void removeVoxel (int x, int y, int z) nothrow @safe @nogc {
 166     uint dofs = getDOfs(x, y);
 167     uint prevdofs = 0;
 168     while (dofs) {
 169       if (data[dofs].z == cast(ushort)z) {
 170         // remove this voxel
 171         if (prevdofs) {
 172           data[prevdofs].nextz = data[dofs].nextz;
 173         } else {
 174           xyofs[cast(uint)y*xsize+cast(uint)x] = data[dofs].nextz;
 175         }
 176         data[dofs].nextz = freelist;
 177         freelist = dofs;
 178         --voxpixtotal;
 179         return;
 180       }
 181       if (data[dofs].z > cast(ushort)z) return;
 182       prevdofs = dofs;
 183       dofs = data[dofs].nextz;
 184     }
 185   }
 186
 187   void addVoxel (int x, int y, int z, uint rgb, ubyte cull) nothrow @safe {
 188     cull &= 0x3f;
 189     if (!cull) { removeVoxel(x, y, z); return; }
 190     if (x < 0 || y < 0 || z < 0) return;
 191     if (cast(uint)x >= xsize || cast(uint)y >= ysize || cast(uint)z >= zsize) return;
 192     uint dofs = getDOfs(x, y);
 193     uint prevdofs = 0;
 194     while (dofs) {
 195       if (data[dofs].z == cast(ushort)z) {
 196         // replace this voxel
 197         data[dofs].b = rgb&0xff;
 198         data[dofs].g = (rgb>>8)&0xff;
 199         data[dofs].r = (rgb>>16)&0xff;
 200         data[dofs].cull = cull;
 201         return;
 202       }
 203       if (data[dofs].z > cast(ushort)z) break;
 204       prevdofs = dofs;
 205       dofs = data[dofs].nextz;
 206     }
 207     // insert before dofs
 208     immutable uint vidx = allocVox();
 209     data[vidx].b = rgb&0xff;
 210     data[vidx].g = (rgb>>8)&0xff;
 211     data[vidx].r = (rgb>>16)&0xff;
 212     data[vidx].cull = cull;
 213     data[vidx].z = cast(ushort)z;
 214     data[vidx].nextz = dofs;
 215     if (prevdofs) {
 216       assert(data[prevdofs].nextz == dofs);
 217       data[prevdofs].nextz = vidx;
 218     } else {
 219       xyofs[cast(uint)y*xsize+cast(uint)x] = vidx;
 220     }
 221   }
 222
 223   // only for existing voxels; won't remove empty voxels
 224   void setVoxelCull (int x, int y, int z, ubyte cull) nothrow @safe @nogc {
 225     VoxPix *vp = queryVP(x, y, z);
 226     if (vp) vp.cull = cast(ubyte)(cull&0x3f);
 227   }
 228
 229   version(vox_check_invariants)
 230   void checkInvariants () const nothrow /*@safe*/ @trusted /*@nogc*/ {
 231     version(voxdata_debug) conwriteln("checking invariants...");
 232     uint voxcount = 0;
 233     foreach (uint y; 0..ysize) {
 234       foreach (uint x; 0..xsize) {
 235         uint dofs = getDOfs(x, y);
 236         if (!dofs) continue;
 237         ++voxcount;
 238         ushort prevz = data[dofs].z;
 239         dofs = data[dofs].nextz;
 240         while (dofs) {
 241           ++voxcount;
 242           assert(prevz < data[dofs].z, "broken voxel data Z invariant");
 243           prevz = data[dofs].z;
 244           dofs = data[dofs].nextz;
 245         }
 246       }
 247     }
 248     assert(voxcount == voxpixtotal, "invalid number of voxels");
 249   }
 250
 251   void removeEmptyVoxels () nothrow /*@safe*/ @trusted /*@nogc*/ {
 252     version(voxdata_debug) conwriteln("removing empty voxels...");
 253     uint count = 0;
 254     foreach (uint y; 0..ysize) {
 255       foreach (uint x; 0..xsize) {
 256         uint dofs = getDOfs(x, y);
 257         if (!dofs) continue;
 258         uint prevdofs = 0;
 259         while (dofs) {
 260           if (!data[dofs].cull) {
 261             // remove it
 262             const uint ndofs = data[dofs].nextz;
 263             if (prevdofs) {
 264               data[prevdofs].nextz = ndofs;
 265             } else {
 266               xyofs[cast(uint)y*xsize+cast(uint)x] = ndofs;
 267             }
 268             data[dofs].nextz = freelist;
 269             freelist = dofs;
 270             --voxpixtotal;
 271             dofs = ndofs;
 272             ++count;
 273           } else {
 274             prevdofs = dofs;
 275             dofs = data[dofs].nextz;
 276           }
 277         }
 278       }
 279     }
 280     if (count) conwriteln("removed ", count, " empty voxel", (count != 1 ? "s" : ""));
 281   }
 282
 283   static immutable int[3][6] cullofs = [
 284     [ 1, 0, 0], // left
 285     [-1, 0, 0], // right
 286     [ 0,-1, 0], // near
 287     [ 0, 1, 0], // far
 288     [ 0, 0, 1], // top
 289     [ 0, 0,-1], // bottom
 290   ];
 291
 292   static ubyte cullmask (uint cidx) pure nothrow @safe @nogc {
 293     pragma(inline, true);
 294     return cast(ubyte)(1U<<cidx);
 295   }
 296
 297   // opposite mask
 298   static ubyte cullopmask (uint cidx) pure nothrow @safe @nogc {
 299     pragma(inline, true);
 300     return cast(ubyte)(1U<<(cidx^1));
 301   }
 302
 303   // remove inside voxels, leaving only contour
 304   void removeInsideFaces () nothrow /*@safe*/ @trusted {
 305     version(voxdata_debug) conwriteln("removing inside voxels...");
 306     foreach (int y; 0..ysize) {
 307       foreach (int x; 0..xsize) {
 308         for (uint dofs = getDOfs(x, y); dofs; dofs = data[dofs].nextz) {
 309           if (!data[dofs].cull) continue;
 310           // check
 311           const int z = cast(int)data[dofs].z;
 312           foreach (uint cidx; 0..6) {
 313             // go in this dir, removing the corresponding voxel side
 314             immutable ubyte cmask = cullmask(cidx);
 315             immutable ubyte opmask = cullopmask(cidx);
 316             immutable ubyte checkmask = cmask|opmask;
 317             immutable int dx = cullofs[cidx][0];
 318             immutable int dy = cullofs[cidx][1];
 319             immutable int dz = cullofs[cidx][2];
 320             int vx = x, vy = y, vz = z;
 321             uint myofs = dofs;
 322             while (myofs && (data[myofs].cull&cmask)) {
 323               immutable int sx = vx+dx;
 324               immutable int sy = vy+dy;
 325               immutable int sz = vz+dz;
 326               immutable uint sofs = voxofs(sx, sy, sz);
 327               if (!sofs) break;
 328               if (!(data[sofs].cull&checkmask)) break;
 329               // fix culls
 330               data[myofs].cull ^= cmask;
 331               data[sofs].cull &= cast(ubyte)(~cast(uint)opmask);
 332               vx = sx;
 333               vy = sy;
 334               vz = sz;
 335               myofs = sofs;
 336             }
 337           }
 338         }
 339       }
 340     }
 341   }
 342
 343   // if we have ANY voxel at the corresponding side, don't render that face
 344   // return number of fixed voxels
 345   uint fixFaceVisibility () nothrow @safe @nogc {
 346     uint count = 0;
 347     foreach (int y; 0..ysize) {
 348       foreach (int x; 0..xsize) {
 349         for (uint dofs = getDOfs(x, y); dofs; dofs = data[dofs].nextz) {
 350           const ubyte ocull = data[dofs].cull;
 351           if (!ocull) continue;
 352           const int z = cast(int)data[dofs].z;
 353           // if we have ANY voxel at the corresponding side, don't render that face
 354           foreach (uint cidx; 0..6) {
 355             const ubyte cmask = cullmask(cidx);
 356             if (data[dofs].cull&cmask) {
 357               if (queryCull(x+cullofs[cidx][0], y+cullofs[cidx][1], z+cullofs[cidx][2])) {
 358                 data[dofs].cull ^= cmask; // reset bit
 359               }
 360             }
 361           }
 362           count += (data[dofs].cull != ocull);
 363         }
 364       }
 365     }
 366     return count;
 367   }
 368
 369   void create3DBitmap (ref Vox3DBitmap bmp) {
 370     bmp.setSize(xsize, ysize, zsize);
 371     foreach (int y; 0..ysize) {
 372       foreach (int x; 0..xsize) {
 373         for (uint dofs = getDOfs(x, y); dofs; dofs = data[dofs].nextz) {
 374           if (data[dofs].cull) bmp.setPixel(x, y, cast(int)data[dofs].z);
 375         }
 376       }
 377     }
 378   }
 379
 380   // this fills everything outside of the voxel, and
 381   // then resets culling bits for all invisible faces
 382   // i don't care about memory yet
 383   uint hollowFill () @trusted {
 384     Vox3DBitmap bmp;
 385     scope(exit) { bmp.clear(); }
 386     bmp.setSize(xsize+2, ysize+2, zsize+2);
 387
 388     VoxXYZ16[] stack;
 389     scope(exit) delete stack;
 390     uint stackpos;
 391
 392     stack.length = 32768;
 393     stack.assumeSafeAppend;
 394     stackpos = 0;
 395     assert(xsize <= cast(uint)stack.length);
 396
 397     // this is definitely empty
 398     VoxXYZ16 xyz;
 399     xyz.x = xyz.y = xyz.z = 0;
 400     bmp.setPixel(cast(int)xyz.x, cast(int)xyz.y, cast(int)xyz.z);
 401     stack[stackpos++] = xyz;
 402
 403     immutable int[3][6] deltas = [
 404       [-1, 0, 0],
 405       [ 1, 0, 0],
 406       [ 0,-1, 0],
 407       [ 0, 1, 0],
 408       [ 0, 0,-1],
 409       [ 0, 0, 1],
 410     ];
 411
 412     auto tm = iv.timer.Timer(true);
 413     while (stackpos) {
 414       xyz = stack[--stackpos];
 415       for (uint dd = 0; dd < 6; ++dd) {
 416         const int nx = cast(int)xyz.x+deltas[dd][0];
 417         const int ny = cast(int)xyz.y+deltas[dd][1];
 418         const int nz = cast(int)xyz.z+deltas[dd][2];
 419         if (bmp.setPixel(nx, ny, nz)) continue;
 420         if (queryCull(nx-1, ny-1, nz-1)) continue;
 421         if (stackpos == cast(uint)stack.length) {
 422           stack.length += 32768;
 423           stack.assumeSafeAppend;
 424         }
 425         stack[stackpos++] = VoxXYZ16(cast(ushort)nx, cast(ushort)ny, cast(ushort)nz);
 426       }
 427     }
 428     tm.stop();
 429     version(voxdata_debug) conwriteln("*** flooded in ", tm.toString(), " ", stack.length, " stack items used.");
 430
 431     // unmark contour voxels
 432     // this is required for proper face removing
 433     foreach (int y; 0..ysize) {
 434       foreach (int x; 0..xsize) {
 435         for (uint dofs = getDOfs(x, y); dofs; dofs = data[dofs].nextz) {
 436           if (!data[dofs].cull) continue;
 437           const int z = cast(int)data[dofs].z;
 438           bmp.resetPixel(x+1, y+1, z+1);
 439         }
 440       }
 441     }
 442
 443     // now check it
 444     uint changed = 0;
 445     foreach (int y; 0..ysize) {
 446       foreach (int x; 0..xsize) {
 447         for (uint dofs = getDOfs(x, y); dofs; dofs = data[dofs].nextz) {
 448           immutable ubyte omask = data[dofs].cull;
 449           if (!omask) continue;
 450           data[dofs].cull = 0x3f;
 451           // check
 452           const int z = cast(int)data[dofs].z;
 453           foreach (uint cidx; 0..6) {
 454             immutable ubyte cmask = cullmask(cidx);
 455             if (!(data[dofs].cull&cmask)) continue;
 456             const int nx = x+cullofs[cidx][0];
 457             const int ny = y+cullofs[cidx][1];
 458             const int nz = z+cullofs[cidx][2];
 459             if (bmp.getPixel(nx+1, ny+1, nz+1)) continue;
 460             // reset this cull bit
 461             data[dofs].cull ^= cmask;
 462           }
 463           changed += (omask != data[dofs].cull);
 464         }
 465       }
 466     }
 467     return changed;
 468   }
 469
 470   void optimise (bool doHollowFill) @trusted {
 471     version(vox_check_invariants) checkInvariants();
 472     version(voxdata_debug) conwriteln("optimising mesh with ", voxpixtotal, " individual voxels...");
 473     if (doHollowFill) {
 474       version(voxdata_debug) conwriteln("optimising voxel culling...");
 475       uint count = hollowFill();
 476       if (count) conwriteln("fixed ", count, " voxel", (count != 1 ? "s" : ""));
 477       //count = fixFaceVisibility();
 478       //if (count) conwriteln("fixed ", count, " voxel", (count != 1 ? "s" : ""));
 479     } else {
 480       removeInsideFaces();
 481       version(voxdata_debug) conwriteln("optimising voxel culling...");
 482       uint count = fixFaceVisibility();
 483       if (count) conwriteln("fixed ", count, " voxel", (count != 1 ? "s" : ""));
 484     }
 485     removeEmptyVoxels();
 486     version(vox_check_invariants) checkInvariants();
 487     version(voxdata_debug) conwriteln("final optimised mesh contains ", voxpixtotal, " individual voxels...");
 488   }
 489 }