vox_2dbmp.d

   1 module vox_2dbmp;
   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 /*
  14   just a 2d bitmap that keeps rgb colors.
  15   there is also the code to find the biggest non-empty rectangle on the bitmap.
  16   empty pixels are represented with zeroes.
  17
  18   the algorithm was taken from this SO topic: https://stackoverflow.com/questions/7245/
  19  */
  20 struct Vox2DBitmap {
  21   static struct Pair {
  22     int one;
  23     int two;
  24   };
  25
  26   int[] cache; // cache
  27   Pair[] stack; // stack
  28   int top; // top of stack
  29
  30   void push (int a, int b) nothrow @safe @nogc {
  31     pragma(inline, true);
  32     stack[top].one = a;
  33     stack[top].two = b;
  34     ++top;
  35   }
  36
  37   void pop (int *a, int *b) nothrow @safe @nogc {
  38     pragma(inline, true);
  39     --top;
  40     *a = stack[top].one;
  41     *b = stack[top].two;
  42   }
  43
  44
  45   int wdt, hgt; // dimension of input
  46   uint[] grid;
  47   uint[] ydotCount; // for each y coord
  48   int dotCount;
  49
  50
  51   void clear () {
  52     delete cache; cache = null;
  53     delete stack; stack = null;
  54     delete grid; grid = null;
  55     delete ydotCount; ydotCount = null;
  56     wdt = hgt = dotCount = 0;
  57   }
  58
  59
  60   void setSize (int awdt, int ahgt) {
  61     if (awdt < 1) awdt = 0;
  62     if (ahgt < 1) ahgt = 0;
  63     wdt = awdt;
  64     hgt = ahgt;
  65     if (grid.length < awdt*ahgt) grid.length = awdt*ahgt;
  66     grid[0..awdt*ahgt] = 0;
  67     if (ydotCount.length < ahgt) ydotCount.length = ahgt;
  68     ydotCount[0..hgt] = 0;
  69     dotCount = 0;
  70   }
  71
  72
  73   void clearBmp () {
  74     grid[0..wdt*hgt] = 0;
  75     ydotCount[0..hgt] = 0;
  76     dotCount = 0;
  77   }
  78
  79
  80   void setPixel (int x, int y, uint rgb) nothrow @trusted @nogc {
  81     pragma(inline, true);
  82     if (x < 0 || y < 0 || x >= wdt || y >= hgt) return;
  83     uint *cp = grid.ptr+cast(uint)y*cast(uint)wdt+cast(uint)x;
  84     if (!*cp) {
  85       ++dotCount;
  86       ++ydotCount.ptr[y];
  87     }
  88     *cp = rgb;
  89   }
  90
  91   uint resetPixel (int x, int y) nothrow @trusted @nogc {
  92     pragma(inline, true);
  93     if (x < 0 || y < 0 || x >= wdt || y >= hgt) return 0;
  94     uint *cp = grid.ptr+cast(uint)y*cast(uint)wdt+cast(uint)x;
  95     const uint res = *cp;
  96     if (res) {
  97       *cp = 0;
  98       --dotCount;
  99       --ydotCount.ptr[y];
 100     }
 101     return res;
 102   }
 103
 104
 105   void updateCache (int currY) nothrow @trusted @nogc {
 106     /*
 107     for (int m = 0; m < wdt; ++m, ++cp) {
 108       if (!grid[currY*wdt+m]) cache[m] = 0; else ++cache[m];
 109     }
 110     */
 111     const(uint) *lp = grid.ptr+cast(uint)currY*cast(uint)wdt;
 112     int *cp = cache.ptr;
 113     for (int m = wdt; m--; ++cp) {
 114       if (*lp++) ++(*cp); else *cp = 0;
 115     }
 116   }
 117
 118
 119   /*
 120     this is the slowest part of the conversion code.
 121    */
 122   bool doOne (int *rx0, int *ry0, int *rx1, int *ry1) nothrow @trusted {
 123     if (dotCount == 0) return false;
 124
 125     if (cache.length < wdt+1) cache.length = wdt+1;
 126     if (stack.length < wdt+1) stack.length = wdt+1;
 127
 128     Pair best_ll;
 129     Pair best_ur;
 130     int best_area;
 131
 132     best_ll.one = best_ll.two = 0;
 133     best_ur.one = best_ur.two = -1;
 134     best_area = 0;
 135     top = 0;
 136     bool cacheCleared = true;
 137
 138     for (int m = 0; m <= wdt; ++m) cache[m] = stack[m].one = stack[m].two = 0;
 139
 140     // main algorithm
 141     for (int n = 0; n < hgt; ++n) {
 142       // there is no need to scan empty lines
 143       // (and we usually have quite a lot of them)
 144       if (ydotCount[n] == 0) {
 145         if (!cacheCleared) {
 146           cacheCleared = true;
 147           cache[0..wdt] = 0;
 148         }
 149         continue;
 150       }
 151       int openWidth = 0;
 152       updateCache(n);
 153       cacheCleared = false;
 154       const(int) *cp = cache.ptr;
 155       for (int m = 0; m <= wdt; ++m) {
 156         const int cvl = *cp++;
 157         if (cvl > openWidth) {
 158           // open new rectangle
 159           push(m, openWidth);
 160           openWidth = cvl;
 161         } else if (cvl < openWidth) {
 162           // close rectangle(s)
 163           int m0 = void, w0 = void;
 164           do {
 165             pop(&m0, &w0);
 166             const int area = openWidth*(m-m0);
 167             if (area > best_area) {
 168               best_area = area;
 169               best_ll.one = m0; best_ll.two = n;
 170               best_ur.one = m-1; best_ur.two = n-openWidth+1;
 171             }
 172             openWidth = w0;
 173           } while (cvl < openWidth);
 174           openWidth = cvl;
 175           if (openWidth != 0) push(m0, w0);
 176         }
 177       }
 178     }
 179
 180     *rx0 = (best_ll.one < best_ur.one ? best_ll.one : best_ur.one);
 181     *ry0 = (best_ll.two < best_ur.two ? best_ll.two : best_ur.two);
 182     *rx1 = (best_ll.one > best_ur.one ? best_ll.one : best_ur.one);
 183     *ry1 = (best_ll.two > best_ur.two ? best_ll.two : best_ur.two);
 184
 185     // remove dots
 186     /*
 187     for (int y = *ry0; y <= *ry1; ++y) {
 188       for (int x = *rx0; x <= *rx1; ++x) {
 189         resetPixel(x, y);
 190       }
 191     }
 192     */
 193
 194     return true;
 195   }
 196 };