API Docs

Class: Octree

PD. Octree

Implements a simple spatial subdivision method to make the ray tracing of model triangles more efficient.

An octree manages its structure to optimize for spatial searches. Unlike linear data structures such as arrays or dictionaries, an octree will iteratively subdivide itself into eight smaller octants when it contains more than eight triangles, thereby adding an additional level to the spatial tree.

Octrees can be used to very quickly find all the elements/triangles that occupy a specific position or volume of space.

This class is derived and adapted from the THREE.Octree addon.

new Octree( [box])

Create a new Octree.

Parameters:
Name Type Argument Description
box THREE.Box3 <optional>

An optional bounding box for this octree, defaults to undefined.
Author:
  • drajmarsh

Extends

Classes

HitResult

Members

:THREE.Box

bounds

The bounding extents of this octree.

Type
  • THREE.Box
:THREE.Box|null

box

The bounding extents of this spatial node.

Type
  • THREE.Box | null
Inherited From:
Overrides:
:boolean

isOctree <readonly>

A flag identifying this object as a spatial octree.

Type
  • boolean
:Array

subTrees

Stores any subtrees within this spatial node.

Type
  • Array
Inherited From:
Overrides:
:Array

triangles

Stores the triangles at this spatial node.

Type
  • Array
Inherited From:
Overrides:
:number

maxLevel <static>

Store the maximum level the octree will extend to.

Type
  • number

Methods

_getNextPlane()

Retrieves a new or reused plane from the cache.

Returns:

Returns the next plane from the cache.

Type
THREE.Plane

_getNextTriangle(a, b, c [, plane] [, host] [, offsetZ])

Retrieves a new or reused triangle from the cache.

Parameters:
Name Type Argument Description
a THREE.Vector3

The first triangle vertex.
b THREE.Vector3

The second triangle vertex.
c THREE.Vector3

The third triangle vertex.
plane THREE.Plane <optional>

An optional plane to set the triangle to.
host PD.Polygon | PD.BRep.Face | THREE.Mesh <optional>

An optional host object.
offsetZ number <optional>

A vertical offset value (in the Z axis), defaults to zero.
Returns:

Returns the next triangle from the cache.

Type
PD.Triangle

_getNextVertex()

Retrieves a new or reused vertex from the cache.

Returns:

Returns the next vertex from the cache.

Type
THREE.Vector3

addBRep(brep)

Adds triangles from each face of the given BRep to the octree.

NOTE: Once you have added all the geometry you need to the octree, you must call the PD.Octree#build method to actually partition the spatial tree and subdivide the triangles. To reuse an existing octree, call the PD.Octree#reset method before adding new geometry.

Parameters:
Name Type Description
brep PD.BRep

The boundary representation to add to the octree.
Returns:

Returns this octree to support method chaining.

Type
PD.Octree

addBRepFace(face)

Adds triangles from the given BRep face to the octree.

NOTE: Once you have added all the geometry you need to the octree, you must call the PD.Octree#build method to actually partition the spatial tree and subdivide the triangles. To reuse an existing octree, call the PD.Octree#reset method before adding new geometry.

Parameters:
Name Type Description
face PD.BRep.Face

The face of a boundary representation to add to the octree.
Returns:

Returns this octree to support method chaining.

Type
PD.Octree

addBRepFaceWithVerticalOffset(face [, offsetZ])

Adds triangles from the given BRep face to the octree.

NOTE: Once you have added all the geometry you need to the octree, you must call the PD.Octree#build method to actually partition the spatial tree and subdivide the triangles. To reuse an existing octree, call the PD.Octree#reset method before adding new geometry.

Parameters:
Name Type Argument Description
face PD.BRep.Face

The face of a boundary representation to add to the octree.
offsetZ number <optional>

The vertical offset to apply to the face.
Returns:

Returns this octree to support method chaining.

Type
PD.Octree

addMesh(mesh [, zOffset])

Add all triangles within the given mesh.

NOTE: Once you have added all the geometry you need to the octree, you must call the PD.Octree#build method to actually partition the spatial tree and subdivide the triangles. To reuse an existing octree, call the PD.Octree#reset method before adding new geometry.

Parameters:
Name Type Argument Description
mesh THREE.Mesh

The mesh tpo add to the octree.
zOffset number <optional>

An optional z-axis offset in world coordinates, defaults to zero.
Returns:

Returns this octree to support method chaining.

Type
PD.Octree

addPolygon(poly)

Adds triangles from the given polygon to the octree.

NOTE: Once you have added all the geometry you need to the octree, you must call the PD.Octree#build method to actually partition the spatial tree and subdivide the triangles. To reuse an existing octree, call the PD.Octree#reset method before adding new geometry.

Parameters:
Name Type Description
poly PD.Polygon

The polygon to add to the octree.
Returns:

Returns this octree to support method chaining.

Type
PD.Octree

addShell(shell)

Adds triangles from each polygon in the given shell to the octree.

NOTE: Once you have added all the geometry you need to the octree, you must call the PD.Octree#build method to actually partition the spatial tree and subdivide the triangles. To reuse an existing octree, call the PD.Octree#reset method before adding new geometry.

Parameters:
Name Type Description
shell PD.Shell

The model shell to add to the octree.
Returns:

Returns this octree to support method chaining.

Type
PD.Octree

build()

Builds the spatial octree once all triangles have been added.

This method should only really be called on the top node of the tree as it will iterate down to 16 levels of subdivision. Invoking this method on subtrees will result in a further 16 subdivisions from that level.

Returns:

Returns this octree to support method chaining.

Type
PD.Octree

capsuleIntersect(capsule)

Determines if the given capsule intersect triangles in the spatial octree.

If an intersection is found, the returned object has the following fields:

  • normal: The normal vector at the intersection point.
  • depth: Depth of the intersection.
Parameters:
Name Type Description
capsule PD.Capsule

The capsule to intersect the octree with.
Returns:

Return a data object if intersected, otherwise null.

Type
object | null

clear()

Resets the spatial octree and frees all cached data.

You will rarely need to call this method directly as all memory will be released anyway if you no longer reference the octree. However, you can call it if you wish to keep the octree but clear all cached data within it from memory.

Returns:

Returns this octree to support method chaining.

Type
PD.Octree

fromGroup(group)

Recursively adds all triangles in each of the geometries within the group.

NOTE: This method first calls PD.Octree#reset and then, once all the geometries have been added, calls PD.Octree#build to partition the spatial tree and subdivide the triangles.

Parameters:
Name Type Description
group THREE.Group

The model group to create the octree from.
Returns:

Returns this octree to support method chaining.

Type
PD.Octree

getCapsuleTriangles(capsule, triangles)

Collects all the triangles from the subtrees intersected by the given capsule.

The aim of this method is to reduce the number of triangle intersection tests to only those that the capsule has any possibility of intersecting. Thus, you only need to test those that are added to the triangles array.

Parameters:
Name Type Description
capsule PD.Capsule

The capsule to intersect the octree with.
triangles Array

The array to add test triangles to.
Inherited From:
Overrides:
Returns:

Returns the triangles array.

Type
Array

getIntersectedNodes(ray, nodes)

Collects all nodes from the subtrees intersected by the given ray.

The aim of this method is to reduce the number of node/triangle intersection tests to only those that the ray has any possibility of intersecting. Thus, you only need to test the triangles within the nodes added to the array.

Parameters:
Name Type Description
ray THREE.Ray

The ray to intersect the octree with.
nodes Array

An array to add intersected tree nodes to.
Inherited From:
Overrides:
Returns:

Returns the triangles array.

Type
Array

getRayTriangles(ray, triangles)

Collects all the triangles from the subtrees intersected by the given ray.

The aim of this method is to reduce the number of triangle intersection tests to only those that the ray has any possibility of intersecting. Thus, you only need to test those that are added to the triangles array.

Parameters:
Name Type Description
ray THREE.Ray

The ray to intersect the octree with.
triangles Array

An array to add test triangles to.
Inherited From:
Overrides:
Returns:

Returns the triangles array.

Type
Array

getSphereTriangles(sphere, triangles)

Collects all the triangles from the subtrees intersected by the given sphere.

The aim of this method is to reduce the number of triangle intersection tests to only those that the sphere has any possibility of intersecting. Thus, you only need to test those that are added to the triangles array.

Parameters:
Name Type Description
sphere THREE.Sphere

The sphere to intersect the octree with.
triangles Array

The array to add test triangles to.
Inherited From:
Overrides:
Returns:

Returns the triangles array.

Type
Array

rayIntersect(ray, result)

Checks for the closest triangle that the given ray intersects within the octree.

This method finds the intersected triangle that is closest to the ray origin and sets the intersection and triangle properties of the result argument. This method does NOT set the transmittance, reflectance or color properties as this must be done by the caller function based on the returned triangle.

If no triangle was hit, the method will return false after setting the distance property to Infinity, the triangle property to null.

Parameters:
Name Type Description
ray THREE.Ray

The ray defining the origin and direction of the light ray.
result PD.Octree.HitResult

An object for receiving the information about the light ray.
Returns:

Returns true if the light ray hit an opaque surface and updated the result argument.

Type
boolean

rayIntersectAll(ray, result)

Checks for all triangle intersections along the given ray within the octree.

This method compiles a list of all triangles hit by the given ray and returns a sorted array of intersection info, where each entry is a [distance,triangle] array. It also sets the distance, intersection and triangle properties of the result argument to those of the closest intersected triangle.

If no triangle is hit, the method will return an empty array after setting the distance property to Infinity and the triangle property to null.

Parameters:
Name Type Description
ray THREE.Ray

The ray defining the origin and direction of the light ray.
result PD.Octree.HitResult

An object for receiving the information about the light ray.
Returns:

Returns an array of [distance, triangle] arrays for each intersected triangle, ordered by ascending distance from the ray origin.

Type
Array.<Array.<number, PD.Triangle>>

rayIntersectsAny(ray)

Checks if any triangle in the octree was intersected.

If any triangle in the octree is hit, the method returns true. This method exits on the first intersection, regardless of its order along the ray. Thus, you can use this method as a quick boolean obstruction test where the actual intersection result does not really matter.

Parameters:
Name Type Description
ray THREE.Ray

The ray defining the origin and direction of the light ray.
Returns:

Returns true if the light ray hit any triangle.

Type
boolean

reset()

Resets the spatial octree to begin accepting new triangles.

You must call this method before attempting to rebuild the octree with new or updated geometry. Its job is to initialise the cache ready to be reused. If you keep adding geometry without calling this method, the cache and the octree will just keep getting bigger until available memory is exceeded.

Returns:

Returns this octree to support method chaining.

Type
PD.Octree

sphereIntersect(sphere)

Determines if the given sphere intersect triangles in the spatial octree.

If an intersection is found, the returned object has the following fields:

  • normal: The normal vector at the intersection point.
  • depth: Depth of the intersection.
Parameters:
Name Type Description
sphere THREE.Sphere

The sphere to intersect the octree with.
Returns:

Return a data object if intersected, otherwise null.

Type
object | null

triangleCapsuleIntersect(capsule, triangle)

Checks if the given capsule and triangle intersect.

If an intersection is found, the returned object has the following fields:

  • normal: The normal vector at the intersection point.
  • point: The actual intersection point.
  • depth: The depth of the intersection.
Parameters:
Name Type Description
capsule PD.Capsule

The capsule to test.
triangle PD.Triangle

The triangle to test.
Returns:

Return a data object if intersected, otherwise null.

Type
object | null

triangleSphereIntersect(sphere, triangle)

Checks if the given sphere and triangle intersect.

If an intersection is found, the returned object has the following fields:

  • normal: The normal vector at the intersection point.
  • point: The actual intersection point.
  • depth: The depth of the intersection.
Parameters:
Name Type Description
sphere THREE.Sphere

The sphere to test.
triangle PD.Triangle

The triangle to test.
Returns:

Return a data object if intersected, otherwise null.

Type
object | null