Click here to Skip to main content
15,867,453 members
Articles / Multimedia / DirectX

3D Interval KD-Tree

Rate me:
Please Sign up or sign in to vote.
3.71/5 (4 votes)
21 May 2009CPOL 40.3K   675   20   5
A KD-Tree which stores axis aligned boxes.

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.

C#
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Architect
Finland Finland
Web and rich client solutions since 2002 with .NET and Java.

Open source contributor to Visual Nunit, OpenSimulator, MXP protocol and IdealistViewer.

Comments and Discussions

 
QuestionHow do you use it? Pin
salasmig9-Feb-11 1:39
salasmig9-Feb-11 1:39 
GeneralBug fixed Pin
Tommi Laukkanen5-Mar-10 10:01
Tommi Laukkanen5-Mar-10 10:01 
General[My vote of 1] My vote of 1 Pin
Johnny J.22-May-09 0:36
professionalJohnny J.22-May-09 0:36 
GeneralNice, clean implementation Pin
jpmik13-May-09 11:29
jpmik13-May-09 11:29 
GeneralRe: Nice, clean implementation Pin
Tommi Laukkanen21-May-09 8:09
Tommi Laukkanen21-May-09 8:09 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.