Click here to Skip to main content
Click here to Skip to main content

OctTree Implementation for overlap detection in C#

, 28 Jul 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
Octa Tree is a 3D space partitioning algorithm

 

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 Logn .

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.

 

License

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

Share

About the Author

sajjad kardani moghadam
Student Phoenix Game group
Iran (Islamic Republic Of) Iran (Islamic Republic Of)
Information Technology Graduate student.Programer. Game designer
Follow on   Twitter

Comments and Discussions

 
QuestionMy vote of 5 PinmemberloPetS29-Jul-14 1:02 

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

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

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150224.1 | Last Updated 28 Jul 2014
Article Copyright 2014 by sajjad kardani moghadam
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid