dunyazad / cuda-tree

CUDA-based Tree builder

CUDA based Tree builder (QuadTree, Octree)

Octree	QuadTree

Functionality

• CUDA tree builder
• CPU kNN, Radius Search
• 2d, 3d visualization (controls: WSAD R F, Mouse). Additional functionality for QuadTree - click on a Tree for kNN and RadiusSearch
• Random Points Generator
• Configuration file
• An obj file loader

Some implementation details: Medium

---

Usage

• ./cuda_tree_app ./app/config/AppConfig.json
• memory check: compute-sanitizer --tool memcheck ./cuda_tree_app ./app/config/AppConfig.json

Config

• AppConfig.json - contains general information (points count, pathes to Tree and Render config files)
• TreeConfig.json:
  • type - 'Quad' or 'Oct'
  • size - width, height, depth (if Octree)
  • threadsPerBlock - min 128 for QuadTree and 256 for Octree (1 warp for each leaf)
• RenderConfig.json - all about rendering

Requirements

• CUDA 11.8+
• C++ 17+
• OpenGL, GLFW
• nlohmann (included)

Limitations

• Tested on up to 150 mln points
• Max stable depth: QuadTree = 7, Octree = 6
• I recommend to disable rendering (AppConfig.json) if more than 50 mln points are used

Further development

1. CUDA based kNN, Radius Search
2. Refactoring, CPU, GPU optimization
3. OpenGL interop for faster visualization
4. Raycasting
5. KDTree

---

Disclaimer

• Tested on Linux: Ubuntu 20.02, CUDA: 12.2, GPU: 3060 (laptop)
• Approach based on Nvidia's QuadTree sample (cdpQuadtree)