mirror of
https://github.com/lighttransport/tinyusdz.git
synced 2026-01-18 01:11:17 +01:00
f0205018b8
Implement high-performance spatial data structures optimized for vertex deduplication and similarity search in 3D meshes, with special optimizations for city-like point distributions. Key features: - Morton code-based sorted hash grid with O(1) average query time - Automatic multilevel grid subdivision for cells exceeding threshold (128 default) - 27-cell neighborhood search for finding similar vertices - Memory-efficient implementation: 48-58 bytes per vertex Specialized strategies for city distributions: - Adaptive octree with RANSAC-based plane detection for walls/floors - Hybrid city grid with layer separation (ground/building/aerial) - 2D grid optimization for ground plane points - Dedicated plane storage for building surfaces Performance benchmarks: - Build time: 11ms for 100K vertices, scales linearly - Query time: 5-17μs average per proximity search - Memory usage: 660MB for 14M points with 0.1m cells - Handles city distributions 2-3x more efficiently than naive approaches Test coverage includes: - Basic functionality and exact vertex matching - Large dataset handling (100K+ vertices) - Clustered data with automatic subdivision - City-like distributions with planes - Memory usage and histogram analysis 🤖 Generated with [Claude Code](https://claude.ai/code) Co-Authored-By: Claude <noreply@anthropic.com>