Documentation / scene / Octree

Class: Octree

Defined in: libs/scene/src/scene/octree.ts:646

Spatial acceleration structure for scene graph nodes using an octree hierarchy.

Remarks

• Organizes GraphNode instances into a multi-level grid of OctreeNodeChunks.
• Supports dynamic resizing to accommodate large scenes while maintaining a minimum leaf size.
• Placement is driven by world-space AABBs; nodes are mapped to an appropriate level by size.
• Maintains a weak map from GraphNode to the current OctreeNode for efficient updates.

Performance:

• Nodes and chunks are created lazily.
• Resizing re-inserts existing nodes; use sparingly and prefer reasonable initial sizes.

Invariants:

• rootSize and leafSize are powers of two; rootSize >= leafSize.
• Level 0 chunk exists after initialization.

Constructors

Constructor

new Octree(scene, rootSize?, leafSize?, maxRootSize?): Octree

Defined in: libs/scene/src/scene/octree.ts:674

Create an octree.

Parameters

scene

Scene

Owning scene instance.

rootSize?

number = 8

Initial root world size (edge length), power of two. Defaults to 8.

leafSize?

number = 8

Minimum leaf cell size (edge length), power of two. Defaults to 8.

maxRootSize?

number = 65536

Hard cap for dynamic growth. Defaults to 65536.

Returns

Octree

Remarks

The octree is initialized on construction; use finalize() to clear all data.

Methods

initialize()

initialize(rootSize, leafSize): void

Defined in: libs/scene/src/scene/octree.ts:695

Initialize the octree with specified root and leaf sizes.

Parameters

rootSize

number

Root world size (edge length).

leafSize

number

Leaf cell size (edge length).

Returns

void

Remarks

• Clears any existing data.
• Builds chunk hierarchy from coarse to fine granularity.

---

finalize()

finalize(): void

Defined in: libs/scene/src/scene/octree.ts:721

Free all nodes and chunks owned by this octree.

Returns

void

Remarks

Resets sizes, root node, and placement maps.

---

getScene()

getScene(): Scene

Defined in: libs/scene/src/scene/octree.ts:734

Owning scene.

Returns

Scene

The Scene that owns this octree.

---

getRootSize()

getRootSize(): number

Defined in: libs/scene/src/scene/octree.ts:742

Root world size (edge length).

Returns

number

The current root world size.

---

getLeafSize()

getLeafSize(): number

Defined in: libs/scene/src/scene/octree.ts:750

Minimum leaf cell size (edge length).

Returns

number

The current leaf cell size.

---

locateNodeChain()

locateNodeChain(candidate, center, radius): OctreeNode

Defined in: libs/scene/src/scene/octree.ts:767

Locate the best-fit node chain for a sphere.

Parameters

candidate

OctreeNode

Optional current node containing the object (hint for reuse).

center

Vector3

Sphere center in world coordinates.

radius

number

Sphere radius in world units.

Returns

OctreeNode

The head OctreeNode of the located chain, or null if out of bounds.

Remarks

• Chooses the finest level where node size is at least (4 \times) radius.
• Returns null if the sphere lies outside the current octree bounds.
• If candidate already matches, it is returned directly.

---

getRootNode()

getRootNode(): OctreeNode

Defined in: libs/scene/src/scene/octree.ts:794

Get the root node (level 0, index 0), creating it if necessary.

Returns

OctreeNode

The root OctreeNode.

---

getNumChunks()

getNumChunks(): number

Defined in: libs/scene/src/scene/octree.ts:805

Number of chunks (levels) in the octree hierarchy.

Returns

number

The total number of chunk levels.

---

getChunk()

getChunk(level): OctreeNodeChunk

Defined in: libs/scene/src/scene/octree.ts:815

Get a chunk by level index.

Parameters

level

number

Chunk level (0 is root).

Returns

OctreeNodeChunk

The OctreeNodeChunk at the given level.

---

placeNode()

placeNode(node): void

Defined in: libs/scene/src/scene/octree.ts:829

Place or update a scene node in the octree.

Parameters

node

GraphNode

Scene graph node to place.

Returns

void

Remarks

• Uses the node's world-space AABB to determine size and best-fit level.
• If the node does not fit within current bounds and growth is allowed, the octree resizes (up to maxRootSize) and reinserts nodes.
• Nodes without valid bounds or with clip tests disabled fall back to the root.

---

removeNode()

removeNode(node): void

Defined in: libs/scene/src/scene/octree.ts:873

Remove a scene node from the octree.

Parameters

node

GraphNode

Scene graph node to remove.

Returns

void

---

prune()

prune(): void

Defined in: libs/scene/src/scene/octree.ts:889

Shrink the octree to the minimum size if the first finer level is empty.

Returns

void

Remarks

Useful after many removals; preserves leafSize.

---

resize()

resize(size): void

Defined in: libs/scene/src/scene/octree.ts:909

Resize the octree root size and rebuild chunks.

Parameters

size

number

New root world size (edge length). Rounded up to the next power of two and clamped to leafSize.

Returns

void

Remarks

• Reinitializes chunks and reinserts previously placed nodes.
• No-op if the size does not change.