KrisLibrary
1.0.0
|
Stores a point set P on an octree grid. Allows for O(d) adding, O(d h) range queries and pseudo-O(d) nearest neighbor queries. More...
#include <Octree.h>
Public Member Functions | |
OctreePointSet (const AABB3D &bbox, int maxPointsPerCell=1, Real minCellSize=0) | |
void | GetPoints (int node, vector< Vector3 > &pts) const |
void | GetPoints (const OctreeNode &node, vector< Vector3 > &pts) const |
void | GetPointIDs (int node, vector< int > &ids) const |
void | GetPointIDs (const OctreeNode &node, vector< int > &ids) const |
void | Add (const Vector3 &pt, int id=-1) |
void | BoxQuery (const Vector3 &bmin, const Vector3 &bmax, vector< Vector3 > &points, vector< int > &ids) const |
void | BoxQuery (const Box3D &b, vector< Vector3 > &points, vector< int > &ids) const |
void | BallQuery (const Vector3 &c, Real r, vector< Vector3 > &points, vector< int > &ids) const |
void | RayQuery (const Ray3D &r, Real radius, vector< Vector3 > &points, vector< int > &ids) const |
int | RayCast (const Ray3D &r, Real radius) const |
bool | NearestNeighbor (const Vector3 &c, Vector3 &closest, int &id) const |
void | KNearestNeighbors (const Vector3 &c, int k, vector< Vector3 > &closest, vector< int > &ids) const |
void | Collapse (int maxSize=0) |
void | FitToPoints () |
const Sphere3D & | Ball (int index) const |
Public Member Functions inherited from Geometry::Octree | |
Octree (const AABB3D &bb) | |
Creates a single-node octree with the given bounding box. | |
int | NumNodes () const |
Returns the number of nodes in the octree. | |
int | Size () const |
Returns the number of nodes in the octree. | |
bool | IsLeaf (const OctreeNode &n) const |
Tests whether a node is a leaf. | |
int | Depth (const OctreeNode &n) const |
Returns the depth of the node in the tree (root is depth 0) | |
int | Index (const OctreeNode &n) const |
Returns the index of the node. | |
const OctreeNode & | Node (int index) const |
Returns the node for a given index. | |
OctreeNode & | Node (int index) |
Returns the node for a given index. | |
int | MaxDepth () const |
Returns the maximum depth of the tree. | |
void | SplitToDepth (int d) |
splits the Octree uniformly to the given depth d | |
void | SplitToDepth (OctreeNode &n, int d) |
OctreeNode * | SplitToDepth (OctreeNode &n, const Vector3 &point, int d) |
void | SplitToResolution (const Vector3 &res) |
splits the Octree uniformly to the given resolution res | |
void | SplitToResolution (OctreeNode &n, const Vector3 &res) |
OctreeNode * | SplitToResolution (OctreeNode &n, const Vector3 &point, const Vector3 &res) |
int | Child (const OctreeNode &n, const Vector3 &pt) const |
Returns the child index in which pt is located (0-7, not the node index) | |
void | Range (const OctreeNode &n, int child, AABB3D &bbchild) const |
Returns the bounding box of a hypothetical child of n. | |
OctreeNode * | Lookup (const Vector3 &point) |
Finds the leaf node containing point or NULL if no such node exists. | |
OctreeNode * | Lookup (OctreeNode &root, const Vector3 &point) |
Same as above, but given a root node for searching. | |
OctreeNode * | Lookup (OctreeNode &root, const Vector3 &point, int depthMax) |
void | BoxLookup (const Vector3 &bmin, const Vector3 &bmax, vector< int > &nodeIndices) const |
void | BoxLookup (const Box3D &b, vector< int > &nodeIndices) const |
Returns the indices of all leaf nodes overlapping the 3D box b. | |
void | BallLookup (const Vector3 &c, Real r, vector< int > &nodeIndices) const |
void | RayLookup (const Ray3D &ray, vector< int > &nodeindices) const |
Returns the sorted list of leaf nodes that intersect the ray. | |
void | FattenedRayLookup (const Ray3D &ray, Real radius, vector< int > &nodeindices) const |
Protected Member Functions | |
Real | _NearestNeighbor (const OctreeNode &n, const Vector3 &c, Vector3 &closest, int &id, Real minDist) const |
int | _KNearestNeighbors (const OctreeNode &n, const Vector3 &c, vector< Vector3 > &closest, vector< int > &ids, vector< Real > &distances, int kmin) const |
virtual int | AddNode (int parent=-1) |
virtual void | DeleteNode (int id) |
virtual void | Split (int nodeindex) |
Splits the given node (once). | |
virtual void | Join (int nodeindex) |
Joins the given node and all descendants. | |
Protected Member Functions inherited from Geometry::Octree | |
void | _RayLookup (int nodeindex, const Ray3D &ray, vector< int > &nodeindices) const |
void | _FattenedRayLookup (int nodeindex, const Ray3D &ray, Real radius, vector< int > &nodeindices) const |
Protected Attributes | |
int | maxPointsPerCell |
Real | minCellSize |
vector< vector< int > > | indexLists |
vector< Vector3 > | points |
vector< int > | ids |
vector< Sphere3D > | balls |
bool | fit |
Protected Attributes inherited from Geometry::Octree | |
vector< OctreeNode > | nodes |
list< int > | freeNodes |
Stores a point set P on an octree grid. Allows for O(d) adding, O(d h) range queries and pseudo-O(d) nearest neighbor queries.
void OctreePointSet::Collapse | ( | int | maxSize = 0 | ) |
Collapses all non-leaf nodes if the collapsed number of points per cell is less than or equal to maxSize
void OctreePointSet::FitToPoints | ( | ) |
Fits AABBs and balls to point sets. May speed up query times. IMPORTANT: can no longer use Lookup, Child, or Add after this is called because the octree subdivision property will no longer hold.
int OctreePointSet::RayCast | ( | const Ray3D & | r, |
Real | radius | ||
) | const |
Returns the ID of the closest point for which r intersects a ball of radius radius around it
References Math::IsInf().
void OctreePointSet::RayQuery | ( | const Ray3D & | r, |
Real | radius, | ||
vector< Vector3 > & | points, | ||
vector< int > & | ids | ||
) | const |
Returns the points p for which r intersects a ball of radius radius around p