/**
* Provides an octree interface for storing and querying objects in three-dimensional space.
* @interface
* @see syngen.utility.octree.create
* @todo Document private members
*/
syngen.utility.octree = {}
/**
* Instantiates a new octree.
* @param {Object} [options={}]
* @param {Number} [options.depth={@link syngen.const.maxSafeFloat|syngen.const.maxSafeFloat * 2}]
* Range of values along the z-axis.
* Typically this is set programmatically.
* @param {Number} [options.height={@link syngen.const.maxSafeFloat|syngen.const.maxSafeFloat * 2}]
* Range of values along the y-axis.
* Typically this is set programmatically.
* @param {Number} [options.maxItems=12]
* Number of items before the tree branches.
* This value is passed to child nodes.
* @param {Number} [options.width={@link syngen.const.maxSafeFloat|syngen.const.maxSafeFloat * 2}]
* Range of values along the y-axis.
* Typically this is set programmatically.
* @param {Number} [options.x={@link syngen.const.maxSafeFloat|-syngen.const.maxSafeFloat}]
* Lower bound for valeus along the x-axis.
* Typically this is set programmatically.
* @param {Number} [options.y={@link syngen.const.maxSafeFloat|-syngen.const.maxSafeFloat}]
* Lower bound for valeus along the y-axis.
* Typically this is set programmatically.
* @param {Number} [options.z={@link syngen.const.maxSafeFloat|-syngen.const.maxSafeFloat}]
* Lower bound for valeus along the z-axis.
* Typically this is set programmatically.
* @returns {syngen.utility.octree}
* @static
*/
syngen.utility.octree.create = function (options = {}) {
return Object.create(this.prototype).construct(options)
}
/**
* Instantiates a new octree with `items` and `options`.
* @param {Object[]} [items=[]]
* @param {Object} [options={}]
* See {@link syngen.utility.octree.create} for a full reference.
* @returns {syngen.utility.octree}
* @static
*/
syngen.utility.octree.from = function (items = [], options = {}) {
const tree = this.create(options)
for (const item of items) {
tree.insert(item)
}
return tree
}
syngen.utility.octree.prototype = {
/**
* Clears all nodes and items.
* @instance
*/
clear: function () {
this.items.length = 0
this.nodes.length = 0
return this
},
/**
* Initializes the instance with `options`.
* @instance
* @param {Object} [options={}]
* @private
*/
construct: function ({
depth = syngen.const.maxSafeFloat * 2,
height = syngen.const.maxSafeFloat * 2,
maxItems = 12,
width = syngen.const.maxSafeFloat * 2,
x = -syngen.const.maxSafeFloat,
y = -syngen.const.maxSafeFloat,
z = -syngen.const.maxSafeFloat,
} = {}) {
this.depth = depth
this.height = height
this.items = []
this.maxItems = maxItems
this.nodes = []
this.width = width
this.x = x
this.y = y
this.z = z
return this
},
/**
* Prepares the instance for garbage collection.
* @instance
*/
destroy: function () {
return this.clear()
},
/**
* Finds the closest item to `query` within `radius`.
* If `query` is contained within the tree, then the next closest item is returned.
* If no result is found, then `undefined` is returned.
* @instance
* @param {Object} query
* @param {Number} query.x
* @param {Number} query.y
* @param {Number} query.z
* @param {Number} [radius=Infinity]
* @returns {Object|undefined}
*/
find: function (query = {}, radius = Infinity) {
if (!('x' in query && 'y' in query && 'z' in query)) {
return
}
if (
isFinite(radius)
&& !this.intersects({
depth: radius * 2,
height: radius * 2,
width: radius * 2,
x: query.x - radius,
y: query.y - radius,
z: query.z - radius,
})
) {
return
}
const distance = ({x, y, z}) => ((x - query.x) ** 2) + ((y - query.y) ** 2) + ((z - query.z) ** 2),
index = this.getIndex(query),
radius3 = ((radius * (Math.sqrt(3) / 3)) ** 2) * 3
if (index == -1) {
let minDistance = radius3,
result
for (const item of this.items) {
if (item === query) {
continue
}
const d = distance(item)
if (d < minDistance) {
minDistance = d
result = item
}
}
return result
}
let result = this.nodes[index].find(query, radius)
let minDistance = result ? distance(result) : radius3
for (const node of this.nodes) {
if (node === this.nodes[index]) {
continue
}
const item = node.find(query, minDistance)
if (!item || item === query) {
continue
}
const d = distance(item)
if (d < minDistance) {
minDistance = d
result = item
}
}
return result
},
/**
* Returns the node index for `item`.
* @instance
* @param {Object} item
* @private
*/
getIndex: function ({
x = 0,
y = 0,
z = 0,
} = {}) {
if (!this.nodes.length) {
return -1
}
const midX = this.x + (this.width / 2),
midY = this.y + (this.height / 2),
midZ = this.z + (this.depth / 2)
const underMidX = x <= midX,
underMidY = y <= midY
if (z <= midZ) {
if (underMidX && underMidY) {
return 0
}
if (!underMidX && underMidY) {
return 1
}
if (underMidX && !underMidY) {
return 2
}
return 3
}
if (underMidX && underMidY) {
return 4
}
if (!underMidX && underMidY) {
return 5
}
if (underMidX && !underMidY) {
return 6
}
return 7
},
/**
* Inserts `item` into the tree.
* @instance
* @param {Object} item
*/
insert: function (item = {}) {
if (!('x' in item && 'y' in item && 'z' in item)) {
return this
}
const index = this.getIndex(item)
if (index != -1) {
this.nodes[index].insert(item)
return this
}
this.items.push(item)
// TODO: Max depth constant to prevent call stack size exceeded
if (this.items.length > this.maxItems) {
this.split()
}
return this
},
/**
* Returns whether this node intersects the rectanglular prism `prism`.
* @instance
* @param {Object} prism
* @param {Number} [prism.depth=0]
* @param {Number} [prism.height=0]
* @param {Number} [prism.width=0]
* @param {Number} [prism.x=0]
* @param {Number} [prism.y=0]
* @param {Number} [prism.z=0]
* @returns {Boolean}
* @see syngen.utility.intersects
* @todo Define a rectangular prism utility or type
*/
intersects: function (prism) {
return syngen.utility.intersects(this, prism)
},
/**
* Removes `item` from the tree, if it exists.
* @instance
* @param {Object} item
*/
remove: function (item) {
if (this.nodes.length) {
const index = this.getIndex(item)
this.nodes[index].remove(item)
return this
}
const index = this.items.indexOf(item)
if (index != -1) {
this.items.splice(index, 1)
}
return this
},
/**
* Retrieves all items within the rectanglular prism `prism`.
* @instance
* @param {Object} prism
* @param {Number} [prism.depth=0]
* @param {Number} [prism.height=0]
* @param {Number} [prism.width=0]
* @param {Number} [prism.x=0]
* @param {Number} [prism.y=0]
* @param {Number} [prism.z=0]
* @returns {Object[]}
* @todo Define a rectangular prism utility or type
*/
retrieve: function ({
depth = 0,
height = 0,
width = 0,
x = 0,
y = 0,
z = 0,
} = {}) {
const items = []
if (!this.intersects({depth, height, width, x, y, z})) {
return items
}
for (const item of this.items) {
if (
item.x >= x
&& item.x <= x + width
&& item.y >= y
&& item.y <= y + height
&& item.z >= z
&& item.z <= z + depth
) {
items.push(item)
}
}
for (const node of this.nodes) {
items.push(
...node.retrieve({
depth,
height,
width,
x,
y,
z,
})
)
}
return items
},
/**
* Splits this node into eight child nodes.
* @instance
* @private
*/
split: function () {
if (this.nodes.length) {
return this
}
const depth = this.depth / 2,
height = this.height / 2,
width = this.width / 2
this.nodes[0] = syngen.utility.octree.create({
depth,
height,
maxItems: this.maxItems,
width,
x: this.x,
y: this.y,
z: this.z,
})
this.nodes[1] = syngen.utility.octree.create({
depth,
height,
maxItems: this.maxItems,
width,
x: this.x + width,
y: this.y,
z: this.z,
})
this.nodes[2] = syngen.utility.octree.create({
depth,
height,
maxItems: this.maxItems,
width,
x: this.x,
y: this.y + height,
z: this.z,
})
this.nodes[3] = syngen.utility.octree.create({
depth,
height,
maxItems: this.maxItems,
width,
x: this.x + width,
y: this.y + height,
z: this.z,
})
this.nodes[4] = syngen.utility.octree.create({
depth,
height,
maxItems: this.maxItems,
width,
x: this.x,
y: this.y,
z: this.z + depth,
})
this.nodes[5] = syngen.utility.octree.create({
depth,
height,
maxItems: this.maxItems,
width,
x: this.x + width,
y: this.y,
z: this.z + depth,
})
this.nodes[6] = syngen.utility.octree.create({
depth,
height,
maxItems: this.maxItems,
width,
x: this.x,
y: this.y + height,
z: this.z + depth,
})
this.nodes[7] = syngen.utility.octree.create({
depth,
height,
maxItems: this.maxItems,
width,
x: this.x + width,
y: this.y + height,
z: this.z + depth,
})
for (const item of this.items) {
const index = this.getIndex(item)
this.nodes[index].insert(item)
}
this.items.length = 0
return this
},
}