OctaIndex3D

A 3D Spatial Indexing and Routing System based on BCC Lattice

Documentation | Whitepaper | Crates.io | Examples

Overview

OctaIndex3D is a high-performance 3D spatial indexing and routing library based on a Body-Centered Cubic (BCC) lattice with truncated octahedral cells.

Key Features

🎮 Interactive 3D Maze Game: Play through procedurally-generated octahedral mazes with BCC lattice pathfinding
Three ID Types: Galactic128 (global), Index64 (Morton), Route64 (local routing)
High Performance: Cross-platform optimizations for modern CPU architectures
14-Neighbor Connectivity: More isotropic than cubic grids (6 neighbors)
Space-Filling Curves: Morton and Hilbert encoding for spatial locality
Hierarchical Refinement: 8:1 parent-child relationships across resolutions
Bech32m Encoding: Human-readable IDs with checksums
Compression: LZ4 (default) and optional Zstd support
Frame Registry: Coordinate reference system management
Streaming Container Format: Append-friendly compressed spatial data storage (v2)
GeoJSON Export: WGS84 coordinate export for GIS integration

Why BCC Lattice?

Our system is built on a Body-Centered Cubic (BCC) lattice, which offers fundamental advantages over traditional grid-based systems for 3D spatial analysis.

1. Superior Efficiency and Fidelity

The BCC lattice is the optimal structure for sampling three-dimensional signals. It achieves the same level of analytical fidelity with approximately 29% fewer data points than a standard cubic grid. This translates to significant reductions in memory usage, storage costs, and processing time for large-scale datasets, without sacrificing precision.

2. Enhanced Isotropy for Realistic Analysis

Spatial relationships in the real world are continuous, not confined to rigid, 90-degree angles. Our system's cells have 14 neighbors, a significant increase from the 6 offered by cubic cells. This near-uniform connectivity in all directions results in:

More realistic pathfinding: Routes are not biased along cardinal axes
Smoother data interpolation: Gradients and fields are represented more naturally
Unbiased neighborhood analysis: Operations like k-rings and spatial statistics are not distorted by grid orientation

3. Consistent and Unambiguous Topology

Every cell in our system is a truncated octahedron, a shape that tiles 3D space perfectly without gaps or overlaps. This guarantees a consistent and unambiguous topology, which is critical for:

Reliable data aggregation: No double-counting or missed regions
Simplified hierarchical models: Parent-child relationships (8:1 refinement) are clear and consistent across all resolutions
Robust algorithms: Eliminates the need for complex edge cases to handle topological inconsistencies found in other tiling systems

🎮 Interactive 3D Maze Game

Experience the power of BCC lattice pathfinding with our interactive 3D octahedral maze game! Navigate through procedurally-generated mazes using 14-neighbor connectivity and compete against optimal A* pathfinding.

Features

Three difficulty levels: Easy (8³), Medium (20³), Hard (40³)
Procedural generation: Randomized Prim's algorithm creates unique mazes every time
Deterministic seeds: Replay specific mazes or share challenges with friends
Competitive stats: Track your performance against optimal A* solutions
Real-time feedback: See your efficiency compared to the theoretical minimum path
BCC lattice navigation: Experience true 3D movement with 14-neighbor connectivity

Quick Start

# Install the CLI (requires 'cli' feature)
cargo install octaindex3d --features cli

# Play on medium difficulty
octaindex3d play --difficulty medium

# Try a specific seed (reproducible maze)
octaindex3d play --seed 42 --size 20

# View your competitive stats
octaindex3d stats

Game Controls

Arrow keys: Navigate in X/Y plane
W/S: Move up/down in Z axis
Q: Quit game
Goal: Reach the target coordinates in as few moves as possible

Example Session

🎮 3D Octahedral Maze Game - BCC Lattice Edition
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Maze: 20×20×20 | Seed: 42
Start: (0, 0, 0) → Goal: (18, 18, 18)
Optimal moves: 18 | Your moves: 19 | Efficiency: 94.7%

Position: (10, 10, 10) | Distance to goal: 13.9
Available moves: 14 (full BCC connectivity)

[Navigate with arrow keys, W/S for Z-axis, Q to quit]

Performance Metrics

The game demonstrates real-world BCC lattice performance:

Maze generation: <200ms for 8,000 cells using Prim's algorithm
A pathfinding*: <5ms for optimal path computation
Memory efficient: <10MB for medium-sized mazes

Try the BCC-14 Demo

For a comprehensive demonstration of the algorithms powering the game:

# Run the BCC-14 Prim's → A* showcase
cargo run --release --example bcc14_prim_astar_demo

# Features:
# - Builds spanning tree on 549K valid BCC nodes in 131ms
# - Solves optimal path with A* in 1ms
# - Comprehensive validation (5/5 checks)
# - Dynamic seeding with reproducible results

Installation

As a Library

Add to your Cargo.toml:

[dependencies]
octaindex3d = "0.4"

# Optional features
octaindex3d = { version = "0.4", features = ["hilbert", "parallel", "container_v2"] }

Available Features

cli: Interactive 3D maze game and command-line utilities
parallel: Multi-threaded batch operations with Rayon (recommended)
simd: SIMD-accelerated operations (BMI2, AVX2, NEON)
hilbert: Hilbert64 space-filling curve with better locality than Morton
container_v2: Append-friendly streaming container format with checkpoints
gis_geojson: GeoJSON export with WGS84 coordinate conversion
zstd_compression: Zstd compression (in addition to default LZ4)

Build from Source

git clone https://github.com/FunKite/OctaIndex3D
cd octaindex3d
cargo build --release

Quick Start

Basic Usage

use octaindex3d::{Galactic128, Index64, Route64, Result};

fn main() -> Result<()> {
    // Create a global ID (128-bit)
    let galactic = Galactic128::new(0, 5, 1, 10, 0, 2, 4, 6)?;
    println!("Galactic ID: {}", galactic.to_bech32m()?);

    // Create a Morton-encoded index (64-bit)
    let index = Index64::new(0, 0, 5, 100, 200, 300)?;
    println!("Morton coordinates: {:?}", index.decode_coords());

    // Create a local routing coordinate (64-bit)
    let route = Route64::new(0, 100, 200, 300)?;
    println!("Route: ({}, {}, {})", route.x(), route.y(), route.z());

    // Get 14 neighbors
    let neighbors = octaindex3d::neighbors::neighbors_route64(route);
    assert_eq!(neighbors.len(), 14);

    Ok(())
}

Working with Hilbert Curves

use octaindex3d::{Hilbert64, Index64};

// Create Hilbert-encoded ID (better spatial locality than Morton)
let hilbert = Hilbert64::new(0, 0, 5, 100, 200, 300)?;

// Hierarchical operations
let parent = hilbert.parent().unwrap();
let children = hilbert.children();

// Convert between Morton and Hilbert
let index: Index64 = hilbert.into();
let hilbert2: Hilbert64 = index.try_into()?;

// Batch encoding
let coords = vec![(0, 0, 0), (1, 1, 1), (2, 2, 2)];
let hilbert_ids = Hilbert64::encode_batch(&coords, 0, 0, 5)?;

Streaming Container Storage

use octaindex3d::container_v2::{ContainerWriterV2, StreamConfig};
use std::fs::File;

// Create streaming container with append support
let file = File::create("data.octa3d")?;
let config = StreamConfig {
    checkpoint_frames: 1000,
    checkpoint_bytes: 64 * 1024 * 1024,
    enable_sha256: false,
};

let mut writer = ContainerWriterV2::new(file, config)?;

// Write spatial data frames
for data in spatial_data {
    writer.write_frame(&data)?;
}

writer.finish()?; // Writes final TOC and footer

GeoJSON Export

use octaindex3d::geojson::{to_geojson_points, write_geojson_linestring, GeoJsonOptions};
use std::path::Path;

// Export points to GeoJSON
let ids = vec![
    Galactic128::new(0, 0, 0, 0, 0, 0, 0, 0)?,
    Galactic128::new(0, 0, 0, 0, 0, 1000, 1000, 0)?,
];

let opts = GeoJsonOptions {
    include_properties: true,
    precision: 7, // ~1cm precision
};

let geojson = to_geojson_points(&ids, &opts);
println!("{}", serde_json::to_string_pretty(&geojson)?);

// Export path as LineString
write_geojson_linestring(Path::new("path.geojson"), &path_ids, &opts)?;

ID System Architecture (v0.3.0+)

Three Interoperable ID Types

┌─────────────────────────────────────────────────────────────┐
│                       Galactic128                           │
│  128-bit global ID with frame, tier, LOD, and coordinates   │
│  ┌────────┬──────┬─────┬──────┬──────────────────────────┐  │
│  │ Frame  │ Tier │ LOD │ Attr │    Coordinates (90b)     │  │
│  │ 8 bits │ 2b   │ 4b  │ 24b  │    X, Y, Z (30b each)    │  │
│  └────────┴──────┴─────┴──────┴──────────────────────────┘  │
│  HRP: g3d1                                                  │
└─────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────┐
│                        Index64                              │
│  64-bit Morton-encoded spatial index (Z-order curve)        │
│  ┌────┬────────┬──────┬─────┬──────────────────────────┐    │
│  │ Hdr│ Frame  │ Tier │ LOD │  Morton Code (48 bits )  │    │
│  │ 2b │ 8 bits │ 2b   │ 4b  │  16b/axis interleaved    │    │
│  └────┴────────┴──────┴─────┴──────────────────────────┘    │
│  HRP: i3d1  |  BMI2 PDEP/PEXT optimized                     │
└─────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────┐
│                        Route64                              │
│  64-bit signed local routing coordinates                    │
│  ┌────┬────────┬──────────────────────────────────────┐     │
│  │ Hdr│ Parity │    X, Y, Z (20 bits each, signed)    │     │
│  │ 2b │  2b    │    ±524k range per axis              │     │
│  └────┴────────┴──────────────────────────────────────┘     │
│  HRP: r3d1  |  Fast neighbor lookup                         │
└─────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────┐
│                       Hilbert64                             │
│  64-bit Hilbert curve spatial index (Gray code)             │
│  ┌────┬────────┬──────┬─────┬──────────────────────────┐    │
│  │ Hdr│ Frame  │ Tier │ LOD │  Hilbert Code (48 bits)  │    │
│  │ 2b │ 8 bits │ 2b   │ 4b  │  Better locality         │    │
│  └────┴────────┴──────┴─────┴──────────────────────────┘    │
│  HRP: h3d1  |  Requires 'hilbert' feature                   │
└─────────────────────────────────────────────────────────────┘

BCC Lattice Properties

Parity Constraint: (x + y + z) % 2 == 0 for all lattice points
14 Neighbors: 8 opposite-parity (distance √3) + 6 same-parity (distance 2)
Hierarchical: 8:1 refinement, each parent has 8 children
Voronoi Cell: Truncated octahedron (14 faces: 6 squares + 8 hexagons)

Examples

🎮 Interactive Maze Game

The fastest way to experience BCC lattice pathfinding:

# Play the interactive 3D maze game
cargo run --release --features cli --bin octaindex3d -- play --difficulty medium

# Try specific challenges
cargo run --release --features cli --bin octaindex3d -- play --seed 42 --size 30

# View your stats
cargo run --release --features cli --bin octaindex3d -- stats

🚀 BCC-14 Prim's Algorithm → A* Demo

Run the comprehensive showcase example demonstrating the algorithms behind the game:

cargo run --release --example bcc14_prim_astar_demo

What it demonstrates:

Prim's Algorithm: Generate spanning tree on 549,450 valid BCC nodes
14-Neighbor Connectivity: All edges preserve BCC lattice parity
A Pathfinding*: Heuristic-guided search with Euclidean distance
Performance: 131ms tree generation, 1ms pathfinding on Apple M1 Max
Validation: 5 comprehensive checks ensuring correctness

Sample output:

🚀 BCC-14 3D Graph: Randomized Prim's Algorithm → A* Pathfinding
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Configuration
  Extent: 130×130×130 (2,197,000 total, 549,450 valid BCC)
  Seed: 42 🍀
  Start: (0, 0, 0) → Goal: (128, 128, 128)

BUILD: Prim's Algorithm
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
  ✓ Carved 549,450 nodes (100.0% coverage) in 131 ms
  Performance: 4,194,656 nodes/sec | 11 MB memory
  Validation: ✓ Tree structure valid (E = N-1)

SOLVE: A* Pathfinding
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
  ✓ Found path: 129 hops in 1 ms
  Performance: 200,000 nodes/sec
  Validation: ✓ All edges verified on spanning tree

Pathfinding with A*

use octaindex3d::{Route64, path::{astar, EuclideanCost}};

let start = Route64::new(0, 0, 0, 0)?;
let goal = Route64::new(0, 10, 10, 10)?;

// Use legacy pathfinding (from v0.2.0)
use octaindex3d::CellID;
let start_cell = CellID::from_coords(0, 5, 0, 0, 0)?;
let goal_cell = CellID::from_coords(0, 5, 10, 10, 10)?;
let path = astar(start_cell, goal_cell, &EuclideanCost)?;

println!("Path length: {} cells", path.len());

Data Layers and Aggregation

use octaindex3d::layer::{Layer, Aggregation};

// Create data layer (legacy API from v0.2.0)
let mut layer = Layer::new("temperature");

for cell in cells {
    layer.set(cell, temperature_value);
}

// Aggregate over region
let mean_temp = layer.aggregate(&region_cells, Aggregation::Mean)?;

// Roll up to coarser resolution
let coarse_layer = layer.rollup(Aggregation::Mean)?;

Frame Registry

use octaindex3d::frame::{FrameDescriptor, register_frame};

// Register custom coordinate system
let frame = FrameDescriptor {
    id: 1,
    name: "LocalENU".to_string(),
    description: "East-North-Up local frame".to_string(),
    base_unit: 1.0, // meters
    origin: [0.0, 0.0, 0.0],
    srid: None,
};

register_frame(frame)?;

Streaming Container Format

The container format provides efficient storage for spatial data with streaming support:

[Header] [Frame 1] [Frame 2] ... [TOC] [Footer]

Features:

Append-friendly: Add data without full rewrite
Fast loading: Footer + TOC enables <50ms open time for 100k frames
Crash recovery: Checkpoint-based resilience
Compression: LZ4 (default) or Zstd per-frame compression
Integrity: Optional SHA-256 checksums
Configurable: Adjust checkpoint intervals (frames/bytes)

Use Cases:

Real-time sensor data streaming
Incremental dataset updates
Long-running data collection

Performance

OctaIndex3D is optimized for modern CPU architectures with support for:

BMI2 hardware acceleration (x86_64 Intel/AMD)
NEON SIMD (Apple Silicon, ARM)
AVX2 vectorization (x86_64)
Adaptive batch processing with automatic threshold selection

For detailed performance analysis and benchmarks, see:

Performance Guide - Usage examples and optimization tips
CPU Comparison - Cross-platform performance analysis
Benchmark Suite - Criterion benchmarks and profiling tools

Use Cases

🎮 Gaming & Interactive: 3D maze games, spatial partitioning, NPC navigation with 14-neighbor pathfinding, procedural generation, voxel worlds
Robotics: 3D occupancy grids, UAV path planning, obstacle avoidance
Geospatial: Volumetric environmental data, atmospheric modeling, ocean data
Scientific: Crystallography, molecular modeling, particle simulations
Urban Planning: 3D city models, airspace management, building information
GIS Integration: Export to WGS84 for visualization in QGIS, ArcGIS, etc.

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

License

Licensed under the MIT License. See LICENSE for details.

Research and Citation

For an in-depth technical analysis, see the OctaIndex3D Whitepaper, which covers:

Mathematical foundations of BCC lattice geometry
Detailed architecture and implementation
Performance benchmarks and analysis
Applications across multiple domains
Future research directions

If you use OctaIndex3D in academic work, please cite:

@techreport{mclarney2025octaindex3d,
  title={OctaIndex3D: A High-Performance 3D Spatial Indexing System Based on Body-Centered Cubic Lattice},
  author={McLarney, Michael A. and Claude},
  year={2025},
  institution={GitHub},
  url={https://github.com/FunKite/OctaIndex3D}
}

References

Made with ❤️ and Rust

Report Bug · Request Feature

octaindex3d 0.4.3

OctaIndex3D

Overview

Key Features

Why BCC Lattice?

1. Superior Efficiency and Fidelity

2. Enhanced Isotropy for Realistic Analysis

3. Consistent and Unambiguous Topology

🎮 Interactive 3D Maze Game

Features

Quick Start

Game Controls

Example Session

Performance Metrics

Try the BCC-14 Demo

Installation

As a Library

Available Features

Build from Source

Quick Start

Basic Usage

Working with Hilbert Curves

Streaming Container Storage

GeoJSON Export

ID System Architecture (v0.3.0+)

Three Interoperable ID Types

BCC Lattice Properties

Examples

🎮 Interactive Maze Game

🚀 BCC-14 Prim's Algorithm → A* Demo

Pathfinding with A*

Data Layers and Aggregation

Frame Registry

Streaming Container Format

Performance

Use Cases

Contributing

License

Research and Citation

References