PointOctree

PointOctree Class

Namespace: Unity_Tools.Collections

Represents a collection of items that have a position in space, the item type is generic.

public class PointOctree<T> : 
    Unity_Tools.Collections.IPoint3DCollection<T>
    System.Collections.Generic.ICollection<T>

Type parameters

T
The type of the items in the PointOctree .

Examples

The following code example creates a new PointOctree with int items.
Then it adds random points using the Add method.
It creates a sphere shape and does a shape cast on the PointOctree using ShapeCast.
For every item that is inside the sphere, it prints out its key.

// Create a new point octree with center set to zero, size set to 100 and allow duplicate keys (as we know we won't have any)
PointOctree<int> points = new PointOctree<int>(Vector3.zero, new Vector3(100, 100, 100), true);

// Create 1000 example entries
for (int index = 0; index < 1000; index++)
{
    // Create a position that is somewhere inside the bounds of the point octree
    var position = UnityEngine.Random.insideUnitSphere * 100f;

    // Add a new item with the index as key and the position as position
    points.Add(index, position);
}

// Create a new sphere located at zero with a radius of 10.
Sphere sphere = new Sphere(Vector3.zero, 10);

// Do a shape cast with the sphere and print out the results.
foreach (var index in points.ShapeCast(sphere))
{
    Debug.Log(index);
}

Remarks

Duplicate entries

The PointOctree takes a boolean flag "allowDuplicates" that determines whether the code should check for duplicates when modifying the collection.
If duplicates are allowed, expensive duplicate checks can be avoided, and duplicate entries can exist.
If duplicates aren't allowed, the duplicate check is performed and it is ensured that no duplicate entries exist.

Two entries are considered duplicates, if and only if they have the same key and position.
For position equality, the UnityEngine.Vector3 == operator is used.

Performance

The PointOctree uses a highly optimized octree implementation for storage and lookup.
For most tasks, it is about 30-50% faster than the Spatial3DTree implementation.
Generally, you should prefer this data structure over Spatial3DTree.

However, the PointOctree has a fixed boundary, whereas the Spatial3DTree has a dynamic boundary.
For that reason, if you need an adaptive or moving boundary, consider using Spatial3DTree instead.

Constructors

• PointOctree<T>(Vector3, Vector3, bool (default: false))
  Creates a new instance of the PointOctree type with default capacity.
• PointOctree<T>(Vector3, Vector3, int, bool (default: false))
  Creates a new instance of the PointOctree type with the specified capacity.

Properties

• AllowsDuplicates : bool
  Gets a value indicating whether duplicate elements are detected and duplicate entries are prevented when adding or moving items.
• Count : int
  Gets the amount of items stored in this collection.

Methods

• Add(T, UnityEngine.Vector3) : void
  Adds the item at the given position.
• Clear() : void
  Clears all items.
• Contains(T, UnityEngine.Vector3) : bool
  Evaluates whether the given item is at the given position.
• GetEnumerator() : System.Collections.Generic.IEnumerator<T>
  Returns an enumerator that iterates through the collection.
• MoveItem(T, Vector3, Vector3) : bool
  Moves the item from the old position to the new position
• ShapeCast<TShape>(TShape) : System.Collections.Generic.IEnumerator<T>
  Returns an enumerator that iterates through all items that are inside the given shape.
• Remove(T, Vector3) : bool
  Removes the item at the given position from the collection.
• [Conditional("UNITY_EDITOR")]TestIntegrity() : void
  Editor only functionality to verify implementation.

Thread safety

The Contains method and enumeration (GetEnumerator) support concurrent reads.
The ShapeCast method does not support concurrent readers.
When the PointOctree is being used in a multi threaded read and write environment, proper locking must be applied.

The ShapeCast method uses pooling to reduce GC pressure, this is not thread safe.
To make ShapeCast support concurrent reads, replace the CastPathCache field with an thread safe alternative.