1 #ifndef GEOMETRY_OCTREE_H 2 #define GEOMETRY_OCTREE_H 4 #include <KrisLibrary/math3d/AABB3D.h> 5 #include <KrisLibrary/math3d/Box3D.h> 6 #include <KrisLibrary/math3d/Ray3D.h> 18 enum {LLL,LLU,LUL,LUU,ULL,ULU,UUL,UUU};
32 int NumNodes()
const {
return (
int)nodes.size()-(int)freeNodes.size(); }
34 int Size()
const {
return NumNodes(); }
38 int Depth(
const OctreeNode& n)
const {
if(n.parentIndex<0)
return 0;
return 1+
Depth(nodes[n.parentIndex]); }
48 void SplitToDepth(
int d);
57 void SplitToResolution(
const Vector3& res);
78 void BoxLookup(
const Vector3& bmin,
const Vector3& bmax,vector<int>& nodeIndices)
const;
80 void BoxLookup(
const Box3D& b,vector<int>& nodeIndices)
const;
83 void BallLookup(
const Vector3& c,Real r,vector<int>& nodeIndices)
const;
85 void RayLookup(
const Ray3D& ray,vector<int>& nodeindices)
const;
88 void FattenedRayLookup(
const Ray3D& ray,Real radius,vector<int>& nodeindices)
const;
90 virtual void Split(
int nodeindex);
92 virtual void Join(
int nodeindex);
95 virtual int AddNode(
int parent=-1);
96 virtual void DeleteNode(
int);
97 void _RayLookup(
int nodeindex,
const Ray3D& ray,vector<int>& nodeindices)
const;
98 void _FattenedRayLookup(
int nodeindex,
const Ray3D& ray,Real radius,vector<int>& nodeindices)
const;
100 vector<OctreeNode> nodes;
116 size_t NumPoints(
int node)
const;
117 size_t NumPoints(
const OctreeNode& node)
const {
return NumPoints(
Index(node)); }
118 void GetPoints(
int node,vector<Vector3>& pts)
const;
119 void GetPoints(
const OctreeNode& node,vector<Vector3>& pts)
const { GetPoints(
Index(node),pts); }
120 void GetPointIDs(
int node,vector<int>& ids)
const;
121 void GetPointIDs(
const OctreeNode& node,vector<int>& ids)
const { GetPointIDs(
Index(node),ids); }
122 void Add(
const Vector3& pt,
int id=-1);
123 void AddSphere(
const Vector3& pt,Real radius,
int id=-1);
124 void BoxQuery(
const Vector3& bmin,
const Vector3& bmax,vector<Vector3>& points,vector<int>& ids)
const;
125 void BoxQuery(
const Box3D& b,vector<Vector3>& points,vector<int>& ids)
const;
126 void BallQuery(
const Vector3& c,Real r,vector<Vector3>& points,vector<int>& ids)
const;
129 void RayQuery(
const Ray3D& r,Real radius,vector<Vector3>& points,vector<int>& ids)
const;
133 bool NearestNeighbor(
const Vector3& c,
Vector3& closest,
int&
id,Real upperBound=Inf)
const;
134 void KNearestNeighbors(
const Vector3& c,
int k,vector<Vector3>& closest,vector<int>& ids)
const;
137 void Collapse(
int maxSize=0);
142 const Sphere3D& Ball(
int index)
const {
return balls[index]; }
146 int _KNearestNeighbors(
const OctreeNode& n,
const Vector3& c,vector<Vector3>& closest,vector<int>& ids,vector<Real>& distances,
int kmin)
const;
147 virtual int AddNode(
int parent=-1);
148 virtual void DeleteNode(
int id);
149 virtual void Split(
int nodeindex);
150 virtual void Join(
int nodeindex);
152 int maxPointsPerCell;
154 vector<vector<int> > indexLists;
155 vector<Vector3> points;
158 vector<Sphere3D> balls;
175 void Set(
const Vector3& pt,Real value,
int id=-1);
177 Real Value(
const Vector3& pt)
const;
180 bool ValueIn(
const Vector3& pt,Real valueMin,Real valueMax)
const;
183 bool ValueGreater(
const Vector3& pt,Real bound)
const;
185 bool ValueLess(
const Vector3& pt,Real bound)
const;
189 void BoxLookupRange(
const Vector3& bmin,
const Vector3& bmax,Real valueMin,Real valueMax,vector<int>& nodeIndices,
bool inclusive=
true)
const;
192 void BoxLookupGreater(
const Vector3& bmin,
const Vector3& bmax,Real bound,vector<int>& nodeIndices)
const;
195 void BoxLookupLess(
const Vector3& bmin,
const Vector3& bmax,Real bound,vector<int>& nodeIndices)
const;
198 void Collapse(Real tolerance=0);
210 virtual int AddNode(
int parent=-1);
211 virtual void DeleteNode(
int id);
212 virtual void Split(
int nodeindex);
213 virtual void Join(
int nodeindex);
int NumNodes() const
Returns the number of nodes in the octree.
Definition: Octree.h:32
A 3D vector class.
Definition: math3d/primitives.h:136
int Depth(const OctreeNode &n) const
Returns the depth of the node in the tree (root is depth 0)
Definition: Octree.h:38
int id
An ID.
Definition: Octree.h:207
Definition: rayprimitives.h:132
A 3D axis-aligned bounding box.
Definition: AABB3D.h:13
int Index(const OctreeNode &n) const
Returns the index of the node.
Definition: Octree.h:40
OctreeNode & Node(int index)
Returns the node for a given index.
Definition: Octree.h:44
An integer tuple class.
Definition: IntTuple.h:14
bool IsLeaf(const OctreeNode &n) const
Tests whether a node is a leaf.
Definition: Octree.h:36
Stores a function f(x) on an octree grid. Allows for O(d) setting, sub O(d) testing of f(x) in range ...
Definition: Octree.h:167
A 3D sphere class.
Definition: Sphere3D.h:21
Real valueMin
The min / max value.
Definition: Octree.h:205
Contains all the definitions in the Math3D package.
Definition: AnyGeometry.h:13
int Size() const
Returns the number of nodes in the octree.
Definition: Octree.h:34
Real RayCast(const Meshing::VolumeGrid &grid, const Ray3D &ray, Real levelSet, Real tmax)
Definition: CollisionImplicitSurface.cpp:527
Real value
The value, at a leaf, or the average value of leaves, if it's non-leaf.
Definition: Octree.h:203
Stores a point set P on an octree grid. Allows for O(d) adding, O(d h) range queries and pseudo-O(d) ...
Definition: Octree.h:111
A 3D boxThe box is the unit cube [0,1]^3 set in the scaled local coordinate system. That is, one corner is at the origin, and it has dimensions [dims.x,dims.y,dims.z] in the coordinates given by {xbasis,ybasis,zbasis}.
Definition: Box3D.h:21
Contains all definitions in the Geometry package.
Definition: AnyGeometry.cpp:26
const OctreeNode & Node(int index) const
Returns the node for a given index.
Definition: Octree.h:42