// TODO: consider replacing with something like: http://www.cse.chalmers.se/edu/year/2010/course/TDA361/grid.pdf
module.exports = findOccupiedCell;

function sign(a) {
  return typeof a === 'number' ? a ? a < 0 ? -1 : 1 : a === a ? 0 : 0 : 0
}

function diff(s, ds) {
  var is = s|0;

  s -= (s < 0) ? -1 + is : is
  return ds > 0 ? (1-s) / ds : s/-ds;
}

function findOccupiedCell(ubx, uby, ubz, isect, rd, pixels, out) {
  var rdx = rd[0];
  var rdy = rd[1];
  var rdz = rd[2];

  var sx = sign(rdx);
  var sy = sign(rdy);
  var sz = sign(rdz);

  var x = isect[0] - rd[0];
  var y = isect[1] - rd[1];
  var z = isect[2] - rd[2];

  var mx = diff(x, rdx);
  var my = diff(y, rdy);
  var mz = diff(z, rdz);

  var dx = sx/rdx;
  var dy = sy/rdy;
  var dz = sz/rdz;

  // TODO: handle NaN

  while (
    x >= -1 && y >= -1 && z >= -1 &&
    x <= ubx && y <= uby && z <= ubz
  ) {

    var ix = x|0;
    var iy = y|0;
    var iz = z|0;

    if (pixels.get(ix, iy, iz)) {
      out[0] = ix;
      out[1] = iy;
      out[2] = iz;
      return out;
    }

    if(mx < my) {
      if(mx < mz) {
        x+=sx;
        mx += dx;
      } else {
        z+=sz;
        mz+=dz;
      }
    } else {
      if(my < mz) {
        y+=sy;
        my+=dy;
      } else {
        z+=sz;
        mz += dz;
      }
    }
  }
  return false;
}

@@ -257,24 +257,61 @@
 ff(s, ds) %7B%0A
+  s = typeof s === 'number' ? s : 0;%0A
   var is = s
@@ -314,16 +314,16 @@
  = s%7C0;%0A
-
 %0A  s -= 
@@ -465,21 +465,24 @@
 r rdx = 
++(
 rd%5B0%5D
+)
 ;%0A  var 
@@ -487,21 +487,24 @@
 r rdy = 
++(
 rd%5B1%5D
+)
 ;%0A  var 
@@ -509,21 +509,24 @@
 r rdz = 
++(
 rd%5B2%5D
+)
 ;%0A%0A  var
@@ -601,16 +601,18 @@
 x = 
++(
 isect%5B0%5D
  - r
@@ -611,16 +611,20 @@
 t%5B0%5D
+)
  - 
++(
 rd%5B0%5D
+)
 ;%0A  
@@ -635,16 +635,18 @@
 y = 
++(
 isect%5B1%5D
  - r
@@ -645,16 +645,20 @@
 t%5B1%5D
+)
  - 
++(
 rd%5B1%5D
+)
 ;%0A  
@@ -669,16 +669,18 @@
 z = 
++(
 isect%5B2%5D
  - r
@@ -679,16 +679,20 @@
 t%5B2%5D
+)
  - 
++(
 rd%5B2%5D
+)
 ;%0A%0A 
@@ -781,14 +781,17 @@
 x = 
++(
 sx/rdx
+)
 ;%0A  
@@ -803,14 +803,17 @@
 y = 
++(
 sy/rdy
+)
 ;%0A  
@@ -825,14 +825,17 @@
 z = 
++(
 sz/rdz
+)
 ;%0A%0A 
@@ -1165,18 +1165,20 @@
        x
+ 
 +=
+ 
 sx;%0A    
@@ -1207,34 +1207,36 @@
 else %7B%0A        z
+ 
 +=
+ 
 sz;%0A        mz+=
@@ -1233,18 +1233,20 @@
       mz
+ 
 +=
+ 
 dz;%0A    
@@ -1291,18 +1291,20 @@
        y
+ 
 +=
+ 
 sy;%0A    
@@ -1309,18 +1309,20 @@
       my
+ 
 +=
+ 
 dy;%0A    
@@ -1341,18 +1341,20 @@
        z
+ 
 +=
+ 
 sz;%0A    

improve typeinfo analysis, no real bump in perf