Octree Search

• Download source - 66.31 KB

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:

• Octree
• Quadtree
• Background and Theory: What are quadtrees?

History

This is release 1.0.

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