3d_dda.js

// NOTE: Although this uses javascript syntax highlighting, it is not javascript.

// start: Vec3
// direction: Vec3

function traverse(start, direction) {
  // TODO: Make sure direction is not 0, this will result in infinite loop!
  
  // Floor the position to get current voxel.
  var pos = floor(start);
  
  // vector_signs returns a 3d vector of either -1, 0, 1
  var step = vector_signs(direction);
  
  // Calls voxel_bound_element for every element.
  var max = voxel_bound(start, direction);
  
  // Delta will always be positive, sign does not matter when used in combination
  // with voxel bound without sign. Result will be the same.
  var delta = step / direction;
  
  var last_face = null;
  
  while (true) {
    // TODO: Make sure you do a range check or something, if not
    // this will keep marching on into infinity.
    
    // Report block hit here (pos, last_face)
    
    if (max.x < max.y) {
      if (max.x < max.z) {
        pos.x += step.x;
        max.x += delta.x;
        last_face = (-step.x, 0, 0);
      } else {
        pos.z += step.z;
        max.z += delta.z;
        last_face = (0, 0, -step.z);
      }
    } else {
      if (max.y < max.z) {
        pos.y += step.y;
        max.y += delta.y;
        last_face = (0, -step.y, 0);
      } else {
        pos.z += step.z;
        max.z += delta.z;
        last_face = (0, 0, -step.z);
      }
    }
  }
}

function voxel_bound_element(pos, dir) {
  if (dir < 0) {
    // Sign does not matter for us, we only care about grid intersections.
    return voxel_bound_element(-pos, -dir);
  } else {
    // Mod function is modulo where RESULT IS DIVISOR SIGNED
    // See http://stackoverflow.com/questions/353224/how-do-you-do-modulo-or-remainder-in-erlang
    // for implementation for languages where modulus is dividend signed.
    // Useful implementation in comment of first answer.
    // (Why the fuck does every goddamn language have a different modulo variant...)
    return (1-mod(pos, 1)) / dir;
  }
}