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>
28 lines
897 B
CMake
28 lines
897 B
CMake
cmake_minimum_required(VERSION 3.10)
|
|
project(sorted_hash_grid)
|
|
|
|
set(CMAKE_CXX_STANDARD 17)
|
|
set(CMAKE_CXX_STANDARD_REQUIRED ON)
|
|
|
|
add_executable(test_sorted_hash_grid
|
|
test_sorted_hash_grid.cc
|
|
)
|
|
|
|
add_executable(test_city_distribution
|
|
test_city_distribution.cc
|
|
)
|
|
|
|
target_include_directories(test_sorted_hash_grid PRIVATE ${CMAKE_CURRENT_SOURCE_DIR})
|
|
target_include_directories(test_city_distribution PRIVATE ${CMAKE_CURRENT_SOURCE_DIR})
|
|
|
|
if(MSVC)
|
|
target_compile_options(test_sorted_hash_grid PRIVATE /W4)
|
|
target_compile_options(test_city_distribution PRIVATE /W4)
|
|
else()
|
|
target_compile_options(test_sorted_hash_grid PRIVATE -Wall -Wextra -O2)
|
|
target_compile_options(test_city_distribution PRIVATE -Wall -Wextra -O2)
|
|
endif()
|
|
|
|
enable_testing()
|
|
add_test(NAME sorted_hash_grid_test COMMAND test_sorted_hash_grid)
|
|
add_test(NAME city_distribution_test COMMAND test_city_distribution) |