Class

GKOctree

A data structure for organizing objects based on their locations in a three-dimensional space.

Declaration

@interface GKOctree<__covariant ElementType> : NSObject

Overview

An octree manages its structure to optimize for spatial searches—unlike a basic data structure such as an array or dictionary, an octree can find all elements occupying a specific position or volume very quickly. The octree partitioning strategy divides space into eight octants at each level, as illustrated in Figure 1. When an octant contains more than one object, the tree subdivides that region into eight smaller octants, adding a level to the tree.

Figure 1

Spatial and logical arrangement of an example octree

Octrees can be useful for many tasks in game design. For example:

  • Deciding which game characters are close enough to each other for interaction

  • Deciding which portions of a large game world need to be processed at a given time

The GKOctree class is one of three spatial partitioning data structures that GameplayKit provides, and the only one suited to three-dimensional data. See the GKQuadTree class for the two-dimensional analogue of an octree, and the GKRTree class for different ways to organize two-dimensional data.

Topics

Creating an Octree

- initWithBoundingBox:minimumCellSize:

Initializes an octree with the specified dimensions.

+ octreeWithBoundingBox:minimumCellSize:

Creates an octree with the specified dimensions.

Adding and Removing Elements

- addElement:withPoint:

Adds an object to the tree corresponding to the specified point in 3D space.

- addElement:withBox:

Adds an object to the tree corresponding to the specified volume of 3D space.

- removeElement:withNode:

Removes the specified object from the tree, using a reference to its containing node.

- removeElement:

Searches for the specified object and removes it from the tree.

Searching for Elements

- elementsAtPoint:

Returns all objects whose corresponding locations overlap the specified point.

- elementsInBox:

Returns all objects whose corresponding locations overlap the specified volume.

Constants

GKBox

The definition of an axis-aligned rectangular bounding volume addressed by the tree.

Relationships

Inherits From

See Also

Spatial Partitioning

GKQuadtree

A data structure for organizing objects based on their locations in a two-dimensional space.

GKQuadtreeNode

A helper class for managing the objects you organize in a quadtree.

GKOctreeNode

A helper class for managing the objects you organize in an octree.

GKRTree

A data structure that adaptively organizes objects based on their locations in a two-dimensional space.

Beta Software

This documentation contains preliminary information about an API or technology in development. This information is subject to change, and software implemented according to this documentation should be tested with final operating system software.

Learn more about using Apple's beta software