Basic sparse octree implementation which uses linked-list behavior to remain compact in-memory

sparse-octree.rb

# Basic sparse octree implementation which uses linked-list behavior to
# remain compact in-memory.
class Octree

  # The parent of this octree (nil if a root)
  attr_reader :parent

  # Node indices
  NODE_INDICES = { 
    0 => :@u0, 1 => :@u1, 2 => :@u2, 3 => :@u3,
    4 => :@l0, 5 => :@l1, 6 => :@l2, 7 => :@l3
  }
  private_constant :NODE_INDICES
  
  # Create an octree from an array of voxel ID's (length 0..7).  May
  # optionally define a parent node.
  def initialize( *children, parent: nil )
    @parent = parent
    @u0, @u1, @u2, @u3,
      @l0, @l1, @l2, @l3 = children
  end

  # Access a node by index.
  def []( index )
    instance_variable_get( NODE_INDICES[ index ])
  end

  # Set a node by its index.
  def []=( index, value )
    instance_variable_set( NODE_INDICES[ index ], value )
    value.parent = self if value.is_a? Octree
  end

  # Migrate to a new parent node.
  def migrate( parent )
    @parent.detach( self )
    @parent = parent
  end

  # Find and detach a subtree node by instance.
  def detach( node )
    raise TypeError, "Expected Octree but got #{node.class}" unless node.is_a? Octree
    for iv in NODE_INDICES
      next unless node == instance_variable_get( iv )
      instance_variable_set( iv, nil )
      node.send( :instance_variable_set, :@parent, nil ) unless node.parent.nil?
      break
    end
  end

  # Write to IO stream with recursive winding.  May optionall force-flush after.
  def to_io( io, flush: false )
    bitmap = NODE_INDICES.map {|i| instance_variable_get( i ) }
    io.write(  bitmap.map {|n| n.nil ? 0 : 1 }.join('').to_i( 2 ))
    bitmap.compact!.each {|node| 
      if node.is_a? Octree
        io.write("\x80")  # subtree flag
        node.to_io( io )
      else
        io.write( [ node ].pack('n'))
      end
    }
    io.flush if flush # and @parent.nil?
  end
  
  # Reconstitute an octree and all children from a stream (or fragment thereof).
  def self.from_io( io, parent = nil )
    # TODO create new instance and populate ...
  end
end

About the serialization mechanism:

Serialization of an octree (or subtree branch) occurs as a big-endian formatted byte-stream. Octrees do not store volumetric and scalar data by default, as they simply represent arbitrary regions of space subdivided into 8 equal parts.

Each tree is prefixed by a 1-byte "bitmap" (type uint8) which declares which of the 8 subdivisions it defines are populated. As such, each bit is a flag to the corresponding subdivision, in-order, of an octree wound clockwise round the Y-axis, from the top-rear-left (X = -1, Y = 1, Z = 1) to the bottom-fore-left (X = -1, Y = -1, Z = -1).

If a branch is encountered (child octree), it uses the flag 0x80 (128 in decimal, binary 100000000) to indicate its presence, then affixes its own bitmap as the stream recurses through the subtree.

Otherwise, each node is written as a 2-byte "voxel ID" (type uint16, limited to 0x0000 through 0x7FFF, or 32768 possible values), which instruct a downstream system how to render the volume represented.