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

Octree Search

, 27 Aug 2008 CPOL
Rate this:
Please Sign up or sign in to vote.
An Octree Search Algorithm in C#

Introduction

A data structure is an approach of storing data in a computer in a way that it can be accessed efficiently. A clever data structure allows a variety of vital operations to be achieved, using as few resources, both execution time and memory space, as possible. A tree is a widely-used data structure that emulates a tree structure with a set of linked nodes. An Octree is a tree data structure in which each inner node has up to eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees.

Octree data structures are useful in many scenarios. Imagine you have a huge data set of strings, and you need to find a string. You have no idea where it is located in that data set, then an Octree search (or quadtree in 2D) is probably the most efficient and fastest method to find your requested string. In my specific project, I have a huge number of fluid elements (in 3D and each element is represented by another data structure), usually in the order of a few million, and I need to find out which element is hosting a solid particle (a 3D point in space). Obviously, searching each element one by one would take forever, and binary searches require sorting of the data set which is not efficient as well. In this case, an Octree search works great.

The code posted here is a conversion/upgrade of couple 2D quadtree codes taken from open source packages but has extended to 3D and added many new tools such as searching in rings and squares. In this article, I give a quick instruction on the code usage. Hope this code comes in handy for you.

Using the Code

The demo project attached shows how to use the octree module. The first step is to instantiate the Octree class:

Octree octreeDataset = new Octree();   

There are several constructors that you can use. I highly recommend to specify the initial range of your dataset (min, max, maximum number of nodes) which are usually known. This will speed up the search process. To do so, call Octree as follows:

Octree octreeDataset = Octree(
       float xMax, 
       float xMin, 
       float yMax, 
       float yMin, 
       float zMax, 
       float zMin, 
       int maxItems) 

The next step is to fill this data set with a bunch of nodes. This is very easy as well, simply write:

octreeDataset.AddNode(x, y, z, obj);

This will add a node to the octree data structure at location x, y, z and the stored value at this point is object obj. This module has 32 overloads, so use it accordingly. Here are the current overloads:

/// <summary> Add an object into the organizer at a location.</summary>
/// <param name="x">up-down location    x</param>
/// <param name="y">left-right location y</param>
/// <param name="z">front-back location z</param>
/// <returns> true if the insertion worked. </returns>
bool AddNode(float x, float y, float z, object obj);
bool AddNode(float x, float y, float z, int obj);
bool AddNode(float x, float y, float z, uint obj);
bool AddNode(float x, float y, float z, short obj);
bool AddNode(float x, float y, float z, long obj);
bool AddNode(float x, float y, float z, float obj);
bool AddNode(float x, float y, float z, double obj);
bool AddNode(float x, float y, float z, bool obj);

bool AddNode(Vector3f vector, object obj);
bool AddNode(Vector3f vector, int obj);
bool AddNode(Vector3f vector, uint obj);
bool AddNode(Vector3f vector, short obj);
bool AddNode(Vector3f vector, long obj);
bool AddNode(Vector3f vector, float obj);
bool AddNode(Vector3f vector, double obj);
bool AddNode(Vector3f vector, bool obj);

bool AddNode(double x, double y, double z, object obj);
bool AddNode(double x, double y, double z, int obj);
bool AddNode(double x, double y, double z, uint obj);
bool AddNode(double x, double y, double z, short obj);
bool AddNode(double x, double y, double z, long obj);
bool AddNode(double x, double y, double z, float obj);
bool AddNode(double x, double y, double z, double obj);
bool AddNode(double x, double y, double z, bool obj);

bool AddNode(Vector3d vector, object obj);
bool AddNode(Vector3d vector, int obj);
bool AddNode(Vector3d vector, uint obj);
bool AddNode(Vector3d vector, short obj);
bool AddNode(Vector3d vector, long obj);
bool AddNode(Vector3d vector, float obj);
bool AddNode(Vector3d vector, double obj);
bool AddNode(Vector3d vector, bool obj);

To remove a node:

octreeDataset.RemoveNode(x, y, z, obj); 

This method has several overloads as well.

Now the data set is ready, let's see how to search for an item. This step is easy too, simply try GetNode or GetNodes methods. The following command looks up for the object located at x, y, z location.

(object)octreeDataset.GetNode(x, y, z); 

There are several methods to find a node:

// Find an object closest to point x/y/z.
object GetNode(float x, float y, float z);
object GetNode(Vector3f vector);
object GetNode(double x, double y, double z);
object GetNode(Vector3d vector);

//Find an object closest to point x/y/z within a distance.
object GetNode(float x, float y, float z, double withinDistance);
object GetNode(Vector3f vector, double withinDistance);
object GetNode(double x, double y, double z, double withinDistance);
object GetNode(Vector3d vector, double withinDistance);

// Find a set of objects closest to point x/y/z within a given radius.
ArrayList GetNodes(float x, float y, float z, double radius);
ArrayList GetNodes(Vector3f vector, double radius);
ArrayList GetNodes(double x, double y, double z, double radius);
ArrayList GetNodes(Vector3d vector, double radius);

ArrayList GetNodes(float x, float y, float z, double MinRadius, double MaxRadius);
ArrayList GetNodes(Vector3f vector, double MinRadius, double MaxRadius);
ArrayList GetNodes(double x, double y, double z, double MinRadius, double MaxRadius);
ArrayList GetNodes(Vector3d vector, double MinRadius, double MaxRadius);

// Find an object closest to point x/y/z, within a cube.
ArrayList GetNode
    (float xMax, float xMin, float yMax, float yMin, float zMax, float zMin);

And that's it! Please let me know if you have new ideas to improve the code.

Points of Interest

To get more information on Octree search algorithm, check out the following pages:

History

This is release 1.0.

Please let me know if you find bugs or have suggestions to improve the code.

License

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

Share

About the Author

Kam
Engineer
United States United States
No Biography provided

Comments and Discussions

 
Question2D quadtree codes Pinmembergdindrawan22-Dec-11 12:58 
GeneralI think your code has some significant bugs [modified] PinmemberAdeMiller27-Sep-08 15:18 
GeneralRe: I think your code has some significant bugs PinmemberKam17-Oct-08 20:04 
GeneralRe: I think your code has some significant bugs Pinmemberscosta_FST20-Oct-08 3:57 
GeneralRe: I think your code has some significant bugs PinmemberKam23-Oct-08 7:51 
GeneralRe: I think your code has some significant bugs Pinmemberscosta_FST23-Oct-08 20:09 
GeneralRe: I think your code has some significant bugs [modified] Pinmembergdindrawan23-Dec-11 13:04 
Generalwhoops :D Pinmembersk8er_boy28728-Aug-08 2:25 
RantRe: whoops :D PinmemberRoberto Collina28-Aug-08 2:59 
GeneralRe: whoops :D Pinmembersk8er_boy28728-Aug-08 3:34 
GeneralRe: whoops :D PinmemberKam28-Aug-08 11:09 
JokeRe: whoops :D Pinmembersk8er_boy28729-Aug-08 5:19 

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
Web04 | 2.8.141030.1 | Last Updated 27 Aug 2008
Article Copyright 2008 by Kam
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid