Implement an Octree to optimize tracing

[ProNoob135]

An octree groups 8 blocks of the same type/same properties into one, then groups 8 groups of the same, recursively. This allows large volumes of air, stone, etc, to be treated as one block, reducing collision checks from O(n) closer to O(log n) (where n is distance), assuming large volumes exist in the world.

[mikenrafter]

This would help with increasing performance surrounding larger cave faces mostly, big (crappy) buildings and chunkerrors. Definitely a good idea.

Reference paper

[ProNoob135]

And air

[mikenrafter]

Leaving this here for future reference and constructive criticism:

An octree step-calculation algorithm in Haskell.

-- the idea is to take 3 vectors, the trajectory, current position, and the target bounds
-- and return a new position, based on which bounding wall will be hit first
-- this is for path tracing using an octree
-- note: this is a haskell representation of an algorithm which will be placed inside minecraft
-- so xyz doesn't follow traditional euler (y is up, not z)

-- takes 3 vectors (and 1 int), returns one
step :: Vec3d -> Vec3d -> Vec3d -> Int -> Vec3d
     -- angle    position bounds   size
     -- where vector is the trajectory...
     -- position is the current position of the ray...
     -- start (u) is the octree segment start pos
     -- size is the octree segment size
step  a p start s =
  -- the smallest vector will prevent overlapping
  min xstep $ min ystep zstep
    where
      -- this step calculates three target coordinates
      -- these coordinates would be along the path of the stepping vector,
      -- branchless way:
      calc base pos angle =
     -- ((  dist  ) + (   size         )) / angle
     -- ((5   -  6) + (16  * 0         )) / -2    = -1/2
     -- ((5   -  7) + (16  * 1         )) /  2    = 14/2
        (base - pos + size * isPos angle) / angle
      xstep = calc (x b) (x p) (x a)
      ystep = calc (y b) (y p) (y a)
      zstep = calc (z b) (z p) (z a)

-- float (is x positive)
isPos :: Float -> Float
-- (-1+1)/2=0 (1+1)/2=1
isPos x = (abs x/x+1)/2