toxi.geom
Class PointOctree

java.lang.Object
  toxi.geom.Vec3D
      toxi.geom.AABB
          toxi.geom.PointOctree

All Implemented Interfaces:

java.lang.Comparable<ReadonlyVec3D>, ReadonlyVec3D, Shape3D

public class PointOctree
extends AABB
implements Shape3D

Implements a spatial subdivision tree to work efficiently with large numbers of 3D particles. This octree can only be used for particle type objects and does NOT support 3D mesh geometry as other forms of Octrees do. For further reference also see the OctreeDemo in the /examples folder.

Nested Class Summary

Nested classes/interfaces inherited from class toxi.geom.Vec3D

Vec3D.Axis

Field Summary

Fields inherited from class toxi.geom.Vec3D

MAX_VALUE, MIN_VALUE, x, X_AXIS, y, Y_AXIS, z, Z_AXIS, ZERO

Constructor Summary

PointOctree(Vec3D o, float size)
Constructs a new PointOctree node within the AABB cube volume: {o.x, o.y, o.z} ...

Method Summary

boolean	addAll(java.util.Collection<Vec3D> points) Adds all points of the collection to the octree.
boolean	addPoint(Vec3D p) Adds a new point/particle to the tree structure.
boolean	containsPoint(ReadonlyVec3D p) Checks if the point is within the given shape/volume.
void	empty()
PointOctree[]	getChildren()
int	getDepth()
PointOctree	getLeafForPoint(ReadonlyVec3D p) Finds the leaf node which spatially relates to the given point
float	getMinNodeSize() Returns the minimum size of nodes (in world units).
float	getNodeSize()
int	getNumChildren()
ReadonlyVec3D	getOffset()
PointOctree	getParent()
java.util.List<Vec3D>	getPoints()
java.util.ArrayList<Vec3D>	getPointsWithinBox(AABB b) Selects all stored points within the given axis-aligned bounding box.
java.util.ArrayList<Vec3D>	getPointsWithinSphere(Sphere s) Selects all stored points within the given sphere volume
java.util.ArrayList<Vec3D>	getPointsWithinSphere(Vec3D sphereOrigin, float clipRadius) Selects all stored points within the given sphere volume
float	getSize()
boolean	remove(ReadonlyVec3D p) Removes a point from the tree and (optionally) tries to release memory by reducing now empty sub-branches.
void	removeAll(java.util.Collection<Vec3D> points)
void	setMinNodeSize(float minNodeSize)
void	setTreeAutoReduction(boolean state) Enables/disables auto reduction of branches after points have been deleted from the tree.
java.lang.String	toString()

Methods inherited from class toxi.geom.AABB

copy, fromMinMax, getExtent, getMax, getMin, getNormalForPoint, includePoint, intersectsBox, intersectsRay, intersectsSphere, intersectsSphere, intersectsTriangle, set, set, set, setExtent, toMesh, toMesh, updateBounds

Methods inherited from class toxi.geom.Vec3D

abs, add, add, add, addSelf, addSelf, angleBetween, angleBetween, clear, compareTo, constrain, constrain, cross, cross, crossInto, crossSelf, distanceTo, distanceToSquared, dot, dot, equals, equalsWithTolerance, floor, frac, fromXYTheta, fromXZTheta, fromYZTheta, getAbs, getComponent, getComponent, getConstrained, getFloored, getFrac, getInverted, getLimited, getNormalized, getNormalizedTo, getReciprocal, getReflected, getRotatedAroundAxis, getRotatedX, getRotatedY, getRotatedZ, getSignum, hashCode, headingXY, headingXZ, headingYZ, immutable, interpolateTo, interpolateTo, interpolateTo, interpolateTo, interpolateToSelf, interpolateToSelf, invert, isInAABB, isInAABB, isMajorAxis, isZeroVector, jitter, jitter, jitter, jitter, jitter, jitter, limit, magnitude, magSquared, max, maxSelf, min, minSelf, modSelf, modSelf, normalize, normalizeTo, randomVector, randomVector, reciprocal, reflect, rotateAroundAxis, rotateX, rotateY, rotateZ, roundToAxis, scale, scale, scale, scale, scaleSelf, scaleSelf, scaleSelf, set, setComponent, setComponent, setXY, shuffle, signum, sub, sub, sub, subSelf, subSelf, to2DXY, to2DXZ, to2DYZ, toArray, toArray4, toCartesian, toSpherical, x, y, z

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

PointOctree

public PointOctree(Vec3D o,
                   float size)

Constructs a new PointOctree node within the AABB cube volume: {o.x, o.y, o.z} ... {o.x+size, o.y+size, o.z+size}

Parameters:

o - tree origin

size - size of the tree volume along a single axis

Method Detail

addAll

public boolean addAll(java.util.Collection<Vec3D> points)

Adds all points of the collection to the octree. IMPORTANT: Points need be of type Vec3D or have subclassed it.

Parameters:

points - point collection

Returns:

true, if all points have been added successfully.

addPoint

public boolean addPoint(Vec3D p)

Adds a new point/particle to the tree structure. All points are stored within leaf nodes only. The tree implementation is using lazy instantiation for all intermediate tree levels.

Parameters:

p -

Returns:

true, if point has been added successfully

containsPoint

public boolean containsPoint(ReadonlyVec3D p)

Description copied from interface: Shape3D

Checks if the point is within the given shape/volume.

Specified by:

containsPoint in interface Shape3D

Overrides:

containsPoint in class AABB

Returns:

true, if inside

empty

public void empty()

getChildren

public PointOctree[] getChildren()

Returns:

a copy of the child nodes array

getDepth

public int getDepth()

Returns:

the depth

getLeafForPoint

public PointOctree getLeafForPoint(ReadonlyVec3D p)

Finds the leaf node which spatially relates to the given point

Parameters:

p - point to check

Returns:

leaf node or null if point is outside the tree dimensions

getMinNodeSize

public float getMinNodeSize()

Returns the minimum size of nodes (in world units). This value acts as tree recursion limit since nodes smaller than this size are not subdivided further. Leaf node are always smaller or equal to this size.

Returns:

the minimum size of tree nodes

getNodeSize

public float getNodeSize()

getNumChildren

public int getNumChildren()

Returns:

the number of child nodes (max. 8)

getOffset

public ReadonlyVec3D getOffset()

Returns:

the offset

getParent

public PointOctree getParent()

Returns:

the parent

getPoints

public java.util.List<Vec3D> getPoints()

Returns:

the points

getPointsWithinBox

public java.util.ArrayList<Vec3D> getPointsWithinBox(AABB b)

Selects all stored points within the given axis-aligned bounding box.

Parameters:

b - AABB

Returns:

all points with the box volume

getPointsWithinSphere

public java.util.ArrayList<Vec3D> getPointsWithinSphere(Sphere s)

Selects all stored points within the given sphere volume

Parameters:

s - sphere

Returns:

selected points

getPointsWithinSphere

public java.util.ArrayList<Vec3D> getPointsWithinSphere(Vec3D sphereOrigin,
                                                        float clipRadius)

Selects all stored points within the given sphere volume

Parameters:

sphereOrigin -

clipRadius -

Returns:

selected points

getSize

public float getSize()

Returns:

the size

remove

public boolean remove(ReadonlyVec3D p)

Removes a point from the tree and (optionally) tries to release memory by reducing now empty sub-branches.

Parameters:

p - point to delete

Returns:

true, if the point was found & removed

removeAll

public void removeAll(java.util.Collection<Vec3D> points)

setMinNodeSize

public void setMinNodeSize(float minNodeSize)

Parameters:

minNodeSize -

setTreeAutoReduction

public void setTreeAutoReduction(boolean state)

Enables/disables auto reduction of branches after points have been deleted from the tree. Turned off by default.

Parameters:

state - true, to enable feature

toString

public java.lang.String toString()

Overrides:

toString in class AABB