Determining octree traversal order for raycasting

traversalOrder.js

/*
 * Quick and dirty attempt:
 */

// Once per ray cast, determine the full traversal order
function getTraversalOrder(direction: [number, number, number]): Array<number> {
  // Should we test positive side child nodes first?
  const posXFirst: boolean = direction[0] < 0
  const posYFirst: boolean = direction[1] < 0
  const posZFirst: boolean = direction[2] < 0
  
  // This is really ugly, but effective!
  const xs : Array<Array<number>> = posXFirst
    ? [[0, 1], [2, 3], [4, 5], [6, 7]]
    : [[1, 0], [3, 2], [5, 4], [7, 6]]
  const ys : Array<Array<number>> = posYFirst
    ? [xs[0].concat(xs[1]), xs[2].concat(xs[3])]
    : [xs[1].concat(xs[0]), xs[3].concat(xs[2])]
  const zs : Array<number> = posZFirst
    ? ys[0].concat(ys[1])
    : ys[1].concat(ys[0])
  const traversalOrder = zs
}

// Now just loop over traversalOrder, grabbing child[i]

/*
 * Determining full traversal order is often unncessary
 * And the technique above is expensive, ugh!
 *
 * We can do better can't we?
 */
 
// Once per raycast, create a bitmask using direction pos/neg values
function createDirectionMask(direction: [number, number, number]): number {
  const posXFirst: boolean = direction[0] < 0
  const posYFirst: boolean = direction[1] < 0
  const posZFirst: boolean = direction[2] < 0

  let directionMask = 0
  if (posXFirst) directionMask |= 1
  if (posYFirst) directionMask |= 2
  if (posZFirst) directionMask |= 4
  return directionMask
}

// Now, when it's time to test a child node, perform only enough logic to know the next child
function getNextNode(directionMask: number, nodeNumber: number|null): number|null {
  // Node ordering is determined by 7..0 ^ directionMask

  // Max value XOR the direction mask returns the starting value
  if (nodeNumber == null) {
    return 7 ^ directionMask
  }

  // Otherwise, travel down the list
  for (let i = 7; i > 0; i--) {
    if ((i ^ directionMask) == nodeNumber) {
      return (i - 1) ^ directionMask
    }
  }

  // When all other options are exhausted, we've traversed the full set of children
  return null
}

// After implementing, traversal order went from > 25% execution time to ~0.5%