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

• 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

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

• 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

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

• Robotics: 3D occupancy grids, UAV path planning, obstacle avoidance
• Geospatial: Volumetric environmental data, atmospheric modeling, ocean data
• Gaming: 3D spatial partitioning, NPC navigation, voxel worlds
• 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.

Copyright (c) 2025 Michael A. McLarney

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

• Wikipedia - "Body-centered cubic"
• Wikipedia - "Truncated octahedron"
• Bech32m Specification
• Morton Encoding
• Hilbert Curve

---

Made with ❤️ and Rust

Report Bug · Request Feature