3D Interval KD-Tree

• Download source code - 3.44 KB

Introduction

A C# KD-Tree for storing 3D axis aligned bounding boxes easily. KD-Tree is an efficient method for finding bounding boxes in 3d space compared to iterating through all boxes and evaluating their intersection with the search volume. There are two files in the attached download. One which contains the implementation and another for Unit Test cases. You can directly copy these to your projects. 

Background

There seems to be a lack of simple Open Source KD-Tree implementations for C#. This KD-tree implementation was created to be used in a Metaverse Exchange Protocol (MXP) reference implementation. You may find an improvement version from http://www.bubblecloud.org/ under the Source Code section.

Using the code

The KD-Tree is used in a similar manner as a Dictionary.

IntervalKDTree<string> tree = 
  new IntervalKDTree<string>(100, 10);

IList<TestBox> testBoxes = new List<TestBox>();
for (double i = -100; i < 100; i += 0.3)
{
    TestBox box = new TestBox();
    box.minX = i;
    box.minY = i;
    box.minZ = i;
    box.maxX = i + 1;
    box.maxY = i + 2;
    box.maxZ = i + 3;
    box.value = "test" + i;
    testBoxes.Add(box);
    tree.Put(box.minX, box.minY, box.minZ, box.maxX, 
             box.maxY, box.maxZ, box.value);
}

HashSet<string> foundValues;
foundValues = tree.GetValues(-10, -10, -10, 10, 10, 10, 
              new HashSet<string>());

Points of Interest

It seems a KD-Tree can be implemented with a relatively small amount of code. Please help me improve it further by providing bug fixes and improvement ideas. Patches are welcome as well.

History

Initial version and Unit Test case was implemented end of May 2009.