OctTree Implementation for overlap detection in C#

• Download source - 180.9 KB
• Download Ball_Packing_With_Octa_Tree_App.rar - 17.4 KB

Introduction

a Octa Tree is a 3D spatial partitioning strategy used to make queries on relationships between 3D spatial data such as coordinates in a Geographic Information System. Most usage of this algorithm is to put 3D object  in a 3D space. and this algorithm can check overlaping with Log_{n .}

Background

if you are Beginner and dont now how space partitioning algorithm work it is recomended that first you read this article about quad tree algorithm for 2D space. that is a good article and i use that quad tree in past. after that when i Need to find an octa tree algorithm i begin search but i dont find a good algorithm in c# for my jop. i find onr octa tree algorithm but that was not suitable for overlap detection. so i try to write my own algorithm my self. i need this algorithm because i was working on a project that i shuold fill a 3D tumor with sphere. sphere was in 4 different size. In the general case this problem is known as Ball packing problem and is a NP problem. attached code is my early work on this problem that use octa tree for space partitioning. octa Tree library itself dont need any thig else c#. but for showing 3D sphere in 3D space i use XNA fremework so you need to have XNA Framework Redistributable 4.0. and for runing project on visual studio you need visual studio 2010  and XNA Game Studio 4.0.

Using the code

this code is Extended version of the quad tree project that i introduce in Background and is as simple as that.you can add any object too this octa tree.also you need to Inheritance from ihas3DLocation interface. i implement cube and sphere shape and you can add other shape yourself. because all query on octa Tree is cube if you want to check overlap of other object you should get the object in smallest cube and check object overlaping with more accuracy yourself.

To initilize new octa Tree. theonly thing you need is size of octa tree.

myOctaTree = new OctTree(0, 0, 0, 100, 100, 100);

Inset object is as simple as you can see below : you can add any object that Inheritance from Ihas3DLocation.

myOctaTree.Insert(currentSphere);

You can use query function to find all object that has overlap with given cube.

overlapList = myOctaTree.Query(new Cube(10, 10, 10, 20, 20, 20));

I dont implement removing object from octa Tree because i dont need this future in my project but you can add this future in some minute or i will do that for you if you need.

Points of Interest

• performance : for more flexibility i use float Instead int because in my search this is not very difference in performance ( in new The current CPU generation).

History

• First version of octa Tree with simple inserting and Query operation useful for overlap cheking.with ball packing problem application
• fix some bug in query.