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) {
  31     stack[top].one = a;
  32     stack[top].two = b;
  33     ++top;
  34   }
  35
  36   void pop (int *a, int *b) {
  37     --top;
  38     *a = stack[top].one;
  39     *b = stack[top].two;
  40   }
  41
  42
  43   int wdt, hgt; // dimension of input
  44   uint[] grid;
  45   int dotCount;
  46
  47
  48   void updateCache (int currY) {
  49     for (int m = 0; m < wdt; ++m) {
  50       if (!grid[currY*wdt+m]) cache[m] = 0; else ++cache[m];
  51     }
  52   }
  53
  54
  55   void clear () {
  56     delete cache; cache = null;
  57     delete stack; stack = null;
  58     delete grid; grid = null;
  59     wdt = hgt = dotCount = 0;
  60   }
  61
  62
  63   void setSize (int awdt, int ahgt) {
  64     if (awdt < 1) awdt = 0;
  65     if (ahgt < 1) ahgt = 0;
  66     wdt = awdt;
  67     hgt = ahgt;
  68     if (grid.length < awdt*ahgt) grid.length = awdt*ahgt;
  69     grid[0..awdt*ahgt] = 0;
  70     dotCount = 0;
  71   }
  72
  73
  74   void clearBmp () {
  75     grid[] = 0;
  76     dotCount = 0;
  77   }
  78
  79
  80   void setPixel (int x, int y, uint rgb) nothrow @safe @nogc {
  81     if (x < 0 || y < 0 || x >= wdt || y >= hgt) return;
  82     if (!grid[y*wdt+x]) {
  83       grid[y*wdt+x] = rgb;
  84       ++dotCount;
  85     }
  86   }
  87
  88   uint resetPixel (int x, int y) nothrow @trusted @nogc {
  89     if (x < 0 || y < 0 || x >= wdt || y >= hgt) return 0;
  90     const uint addr = y*wdt+x;
  91     const uint res = grid[addr];
  92     if (res) {
  93       grid[addr] = 0;
  94       --dotCount;
  95     }
  96     return res;
  97   }
  98
  99
 100   bool isDone () const nothrow @safe @nogc { pragma(inline, true); return (dotCount == 0); }
 101
 102
 103   bool doOne (int *rx0, int *ry0, int *rx1, int *ry1) {
 104     if (dotCount == 0) return false;
 105
 106     if (cache.length < wdt+1) cache.length = wdt+1;
 107     if (stack.length < wdt+1) stack.length = wdt+1;
 108
 109     Pair best_ll;
 110     Pair best_ur;
 111     int best_area;
 112
 113     best_ll.one = best_ll.two = 0;
 114     best_ur.one = best_ur.two = -1;
 115     best_area = 0;
 116     //clearStack();
 117     top = 0;
 118
 119     for (int m = 0; m <= wdt; ++m) cache[m] = stack[m].one = stack[m].two = 0;
 120
 121     // main algorithm
 122     for (int n = 0; n < hgt; ++n) {
 123       int openWidth = 0;
 124       updateCache(n);
 125       for (int m = 0; m <= wdt; ++m) {
 126         if (cache[m] > openWidth) {
 127           // open new rectangle
 128           push(m, openWidth);
 129           openWidth = cache[m];
 130         } else if (cache[m] < openWidth) {
 131           // close rectangle(s)
 132           int m0, w0, area;
 133           do {
 134             pop(&m0, &w0);
 135             area = openWidth*(m-m0);
 136             if (area > best_area) {
 137               best_area = area;
 138               best_ll.one = m0; best_ll.two = n;
 139               best_ur.one = m-1; best_ur.two = n-openWidth+1;
 140             }
 141             openWidth = w0;
 142           } while (cache[m] < openWidth);
 143           openWidth = cache[m];
 144           if (openWidth != 0) push(m0, w0);
 145         }
 146       }
 147     }
 148
 149     *rx0 = (best_ll.one < best_ur.one ? best_ll.one : best_ur.one);
 150     *ry0 = (best_ll.two < best_ur.two ? best_ll.two : best_ur.two);
 151     *rx1 = (best_ll.one > best_ur.one ? best_ll.one : best_ur.one);
 152     *ry1 = (best_ll.two > best_ur.two ? best_ll.two : best_ur.two);
 153
 154     // remove dots
 155     /*
 156     for (int y = *ry0; y <= *ry1; ++y) {
 157       for (int x = *rx0; x <= *rx1; ++x) {
 158         resetPixel(x, y);
 159       }
 160     }
 161     */
 162
 163     return true;
 164   }
 165 };