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>
Inheritance diagram for Geometry::OctreePointSet:
Public Member Functions | |
| OctreePointSet (const AABB3D &bbox, int maxPointsPerCell=1, Real minCellSize=0) | |
| size_t | NumPoints (int node) const |
| size_t | NumPoints (const OctreeNode &node) const |
| 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 | AddSphere (const Vector3 &pt, Real radius, 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, Real upperBound=Inf) 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< Real > | radii |
| vector< int > | ids |
| vector< Sphere3D > | balls |
| bool | fit |
| Protected Attributes inherited from Geometry::Octree | |
| vector< OctreeNode > | nodes |
| list< int > | freeNodes |
Detailed Description
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.
Can also associate a nonnegative radius to each point using AddSphere. If so, the queries treat the points as solid spheres. For this to work properly, FitToPoints must be called before queries are made.
Member Function Documentation
| 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
The documentation for this class was generated from the following files:
- Octree.h
- Octree.cpp
