14,981,383 members
Articles / Multimedia / DirectX
Article
Posted 13 May 2009

36.9K views
630 downloads
20 bookmarked

# 3D Interval KD-Tree

Rate me:
3.71/5 (4 votes)
21 May 2009CPOL
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)

## About the Author

 Architect 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

 First Prev Next
 How do you use it? salasmig9-Feb-11 1:39 salasmig 9-Feb-11 1:39
 Bug fixed Tommi Laukkanen5-Mar-10 10:01 Tommi Laukkanen 5-Mar-10 10:01
 [My vote of 1] My vote of 1 Johnny J.22-May-09 0:36 Johnny J. 22-May-09 0:36
 Nice, clean implementation jpmik13-May-09 11:29 jpmik 13-May-09 11:29
 Re: Nice, clean implementation Tommi Laukkanen21-May-09 8:09 Tommi Laukkanen 21-May-09 8:09
 Last Visit: 31-Dec-99 18:00     Last Update: 3-Aug-21 7:39 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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