import {WorldOctree} from 'rabbit-hole'

public class | source

WorldOctree

An octree that subdivides space for fast spatial searches.

The purpose of this linear octree is to efficiently organise volume data. It allows direct access to different LOD layers, octant neighbours and parents.

The world octree is axis-aligned and cannot be rotated.

Static Method Summary

Static Public Methods
public static	calculateOffsetIndex(x: Number, y: Number, z: Number): Number Calculates an offset index from octant key coordinates.

Constructor Summary

Public Constructor
public	constructor(cellSize: Number, levels: Number, keyDesign: KeyDesign) Constructs a new world octree.

Member Summary

Public Members
public get	levels: Number The amount of detail levels.
public get	lodZero: Number The LOD zero octant grid.
public get	max: Vector3 The upper bounds of this world.
public get	min: Vector3 The lower bounds of this world.

Method Summary

Public Methods
public	applyCSG(sdf: SignedDistanceFunction) Applies the given SDF to the affected octants.
public	calculateKeyCoordinates(position: Vector3, lod: Number, target: Vector3): Vector3 Calculates key coordinates based on a given position and LOD.
public	clear() Removes all octants.
public	containsPoint(point: Vector3): Boolean Checks if the given point lies inside this octree's boundaries.
public	findOctantsByLevel(level: Number): Iterable Fetches all octants of the specified LOD.
public	getCellSize(lod: Number): Number Returns the size of the cells in the specified LOD grid.
public	getCenter(target: Vector3): Vector3 Computes the center of this world.
public	getDepth(): Number The world octree depth is constant and corresponds to the amount of detail levels.
public	getDimensions(target: Vector3): Vector3 Computes the size of this world.
public	getGrid(lod: Number): Map Returns a specific LOD grid.
public	getKeyDesign(): KeyDesign Returns the key design.
public	getOctantByPoint(point: Vector3, lod: Number): WorldOctant Retrieves the octant of a specific LOD that contains the given point.
public	octants(lod: Number): WorldOctantIterator Returns a new world octant iterator.
public	raycast(ray: Ray, intersects: Array): WorldOctant[] Finds the octants that intersect with the given ray.
public	removeOctant(key: Number, lod: Number) Removes a specific octant by a given key.
public	setCenter(center: Vector3) Sets the center of this world.

Static Public Methods

public static calculateOffsetIndex(x: Number, y: Number, z: Number): Number source

Calculates an offset index from octant key coordinates.

The index identifies the octant's positional offset relative to its parent:

 0: [0, 0, 0]
 1: [0, 0, 1]
 2: [0, 1, 0]
 3: [0, 1, 1]
 4: [1, 0, 0]
 5: [1, 0, 1]
 6: [1, 1, 0]
 7: [1, 1, 1]

Note: This binary pattern is defined by the external sparse-octree module.

For more information on fast bitwise modulo with power of two divisors see: https://graphics.stanford.edu/~seander/bithacks.html#ModulusDivisionEasy

Params:

Name	Type	Attribute	Description
x	Number		The X-coordinate of the octant key.
y	Number		The Y-coordinate of the octant key.
z	Number		The Z-coordinate of the octant key.

Return:

Number

The index of the relative position offset. Range: [0, 7].

Public Constructors

public constructor(cellSize: Number, levels: Number, keyDesign: KeyDesign) source

Constructs a new world octree.

Each octant can be uniquely identified by a 3D coordinate and a LOD value. The individual values for X, Y and Z are combined into a 53-bit key.

Params:

Name	Type	Attribute	Description
cellSize	Number	optional default: 20	The size of the smallest octants in LOD zero. Must be an integer i such that 0 < i < 2 ** (33 - levels).
levels	Number	optional default: 8	The amount of detail levels. Must be an integer i such that 0 < i < 33.
keyDesign	KeyDesign	optional	The bit allotments for the octant coordinates.

Public Members

public get levels: Number source

The amount of detail levels. This value can not be changed.

public get lodZero: Number source

The LOD zero octant grid.

public get max: Vector3 source

The upper bounds of this world.

public get min: Vector3 source

The lower bounds of this world.

Public Methods

public applyCSG(sdf: SignedDistanceFunction) source

Applies the given SDF to the affected octants.

Params:

Name	Type	Attribute	Description
sdf	SignedDistanceFunction		An SDF.

public calculateKeyCoordinates(position: Vector3, lod: Number, target: Vector3): Vector3 source

Calculates key coordinates based on a given position and LOD.

Params:

Name	Type	Attribute	Description
position	Vector3		A position.
lod	Number		The target LOD.
target	Vector3	optional	A vector to store the result in. If none is provided, a new one will be created.

Return:

Vector3

The key coordinates.

public clear() source

Removes all octants.

public containsPoint(point: Vector3): Boolean source

Checks if the given point lies inside this octree's boundaries.

Params:

Name	Type	Attribute	Description
point	Vector3		A point.

Return:

Boolean

Whether the given point lies inside this octree.

public findOctantsByLevel(level: Number): Iterable source

Fetches all octants of the specified LOD.

Params:

Name	Type	Attribute	Description
level	Number		The LOD.

Return:

Iterable

A collection that contains the octants of the specified LOD.

public getCellSize(lod: Number): Number source

Returns the size of the cells in the specified LOD grid.

Params:

Name	Type	Attribute	Description
lod	Number	optional default: 0	The LOD. Must be an integer; fractions will be truncated.

Return:

Number

The cell size.

public getCenter(target: Vector3): Vector3 source

Computes the center of this world.

Params:

Name	Type	Attribute	Description
target	Vector3	optional	A target vector. If none is provided, a new one will be created.

Return:

Vector3

A vector that describes the center of this world.

public getDepth(): Number source

The world octree depth is constant and corresponds to the amount of detail levels.

Return:

Number

The octree depth.

public getDimensions(target: Vector3): Vector3 source

Computes the size of this world.

Params:

Name	Type	Attribute	Description
target	Vector3	optional	A target vector. If none is provided, a new one will be created.

Return:

Vector3

A vector that describes the size of this world.

public getGrid(lod: Number): Map source

Returns a specific LOD grid.

Params:

Name	Type	Attribute	Description
lod	Number		The LOD of the grid.

Return:

Map	The requested LOD grid or undefined if the given LOD is out of bounds.

public getKeyDesign(): KeyDesign source

Returns the key design.

Return:

KeyDesign

The key design.

public getOctantByPoint(point: Vector3, lod: Number): WorldOctant source

Retrieves the octant of a specific LOD that contains the given point.

Params:

Name	Type	Attribute	Description
point	Vector3		A point.
lod	Number	optional default: 0	A LOD value.

Return:

WorldOctant

The octant that contains the point or undefined if it doesn't exist.

public octants(lod: Number): WorldOctantIterator source

Returns a new world octant iterator.

The octants returned by this iterator are augmented with explicit positional information. See WorldOctantWrapper for more details.

Params:

Name	Type	Attribute	Description
lod	Number	optional default: 0	The LOD grid to consider.

Return:

WorldOctantIterator

An iterator.

public raycast(ray: Ray, intersects: Array): WorldOctant[] source

Finds the octants that intersect with the given ray. The intersecting octants are sorted by distance, closest first. Empty octants will not be included in the result.

Params:

Name	Type	Attribute	Description
ray	Ray		A ray.
intersects	Array	optional	An optional target list to be filled with the intersecting octants.

Return:

WorldOctant[]

The intersecting octants.

public removeOctant(key: Number, lod: Number) source

Removes a specific octant by a given key.

Children and empty parent nodes will be removed as well.

Params:

Name	Type	Attribute	Description
key	Number		The key of the octant that should be removed.
lod	Number	optional default: 0	The LOD of the octant.

public setCenter(center: Vector3) source

Sets the center of this world.

Keeping the center at (0, 0, 0) is recommended because a large offset can lead to floating point coordinate imprecisions.

Params:

Name	Type	Attribute	Description
center	Vector3		The new center.