OctreeNode.h
Go to the documentation of this file.
1 // This file is a part of the OpenSurgSim project.
2 // Copyright 2013, SimQuest Solutions Inc.
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 // http://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 
16 #ifndef SURGSIM_DATASTRUCTURES_OCTREENODE_H
17 #define SURGSIM_DATASTRUCTURES_OCTREENODE_H
18 
19 #include <array>
20 #include <memory>
21 #include <functional>
22 
25 #include "SurgSim/Math/Vector.h"
26 #include "SurgSim/Math/Aabb.h"
27 
28 
29 namespace SurgSim
30 {
31 
32 namespace Math
33 {
34 class OctreeShape;
35 }
36 
37 namespace DataStructures
38 {
39 
43 typedef std::vector<size_t> OctreePath;
44 
49 {
50 public:
51  size_t operator()(const OctreePath& path) const
52  {
53  size_t result = 0;
54  for (auto i : path)
55  {
56  result = (result << 3) | i;
57  }
58 
59  return m_hasher(result);
60  }
61 private:
62  std::hash<size_t> m_hasher;
63 };
64 
67 {
72  NEIGHBORHOOD_ALL = 0x1 | 0x2 | 0x4
73 };
74 
76 enum Symbol
77 {
80  SYMBOL_UP = 1,
84  SYMBOL_FRONT = 5
85 };
86 
103 OctreePath getNeighbor(const OctreePath& origin, const std::array<Symbol, 3>& direction);
104 
110 std::vector<OctreePath> getNeighbors(const OctreePath& origin, int type);
111 
112 template <typename Data>
113 class OctreeNodePlyReaderDelegate;
114 
130 template<class Data>
132  public std::enable_shared_from_this<OctreeNode<Data>>
133 {
136 
137 public:
138 
140  typedef Eigen::AlignedBox<double, 3> AxisAlignedBoundingBox;
141 
143  OctreeNode();
144 
147  OctreeNode(const OctreeNode& other);
148 
153  template <class T>
154  OctreeNode(const OctreeNode<T>& other);
155 
156  std::string getClassName() const override;
157 
160  explicit OctreeNode(const SurgSim::Math::Aabbd& boundingBox);
161 
163  virtual ~OctreeNode();
164 
167  const SurgSim::Math::Aabbd& getBoundingBox() const;
168 
171  bool isActive() const;
172 
175  void setIsActive(bool isActive);
176 
179  bool hasChildren() const;
180 
184  void subdivide();
185 
193  bool addData(const SurgSim::Math::Vector3d& position, const int level, const Data& nodeData = Data());
194 
197  std::array<std::shared_ptr<OctreeNode<Data>>, 8>& getChildren();
198 
201  const std::array<std::shared_ptr<OctreeNode<Data>>, 8>& getChildren() const;
202 
207  std::shared_ptr<OctreeNode<Data>> getChild(size_t index);
208 
213  const std::shared_ptr<OctreeNode<Data>> getChild(size_t index) const;
214 
219  // the last node on a given path, otherwise it will throw.
221  virtual std::shared_ptr<OctreeNode<Data>> getNode(const OctreePath& path, bool returnLastValid = false);
222 
224  Data data;
225 
226 protected:
233  bool doAddData(const SurgSim::Math::Vector3d& position, const Data& nodeData, const int level,
234  const int currentLevel);
235 
236  bool doLoad(const std::string& filePath) override;
237 
240 
243 
246 
248  std::array<std::shared_ptr<OctreeNode<Data>>, 8> m_children;
249 
250 private:
252 };
253 
254 }; // namespace DataStructures
255 }; // namespace SurgSim
256 
258 
259 #endif // SURGSIM_DATASTRUCTURES_OCTREENODE_H
SurgSim::Math::OctreeShape
Octree Shape A defined by an octree data structure.
Definition: OctreeShape.h:35
SurgSim::DataStructures::NEIGHBORHOOD_EDGE
@ NEIGHBORHOOD_EDGE
Definition: OctreeNode.h:70
SurgSim::DataStructures::NEIGHBORHOOD_ALL
@ NEIGHBORHOOD_ALL
Definition: OctreeNode.h:72
SurgSim::DataStructures::OctreeNode::m_children
std::array< std::shared_ptr< OctreeNode< Data > >, 8 > m_children
The children of this node.
Definition: OctreeNode.h:248
Vector.h
Definitions of small fixed-size vector types.
SurgSim::DataStructures::Symbol
Symbol
Direction code for the neighborhood search.
Definition: OctreeNode.h:77
SurgSim::DataStructures::OctreeNode::getNode
virtual std::shared_ptr< OctreeNode< Data > > getNode(const OctreePath &path, bool returnLastValid=false)
Get the node at the supplied path.
Definition: OctreeNode-inl.h:216
SurgSim::DataStructures::OctreeNode::~OctreeNode
virtual ~OctreeNode()
Destructor.
Definition: OctreeNode-inl.h:97
SurgSim::DataStructures::SYMBOL_RIGHT
@ SYMBOL_RIGHT
Definition: OctreeNode.h:81
SurgSim::DataStructures::OctreeNode::doLoad
bool doLoad(const std::string &filePath) override
Derived classes will overwrite this method to do actual loading.
Definition: OctreeNode-inl.h:241
Asset.h
SurgSim::DataStructures::OctreeNode::getChildren
std::array< std::shared_ptr< OctreeNode< Data > >, 8 > & getChildren()
Get the children of this node (non const version)
Definition: OctreeNode-inl.h:192
SurgSim::DataStructures::SYMBOL_BACK
@ SYMBOL_BACK
Definition: OctreeNode.h:83
EmptyData.h
SurgSim::DataStructures::OctreeNode::OctreeNode
OctreeNode()
Constructor.
Definition: OctreeNode-inl.h:36
SurgSim::Math::Vector3d
Eigen::Matrix< double, 3, 1 > Vector3d
A 3D vector of doubles.
Definition: Vector.h:57
SurgSim::DataStructures::OctreeNode::isActive
bool isActive() const
Is this node active.
Definition: OctreeNode-inl.h:114
SurgSim
Definition: CompoundShapeToGraphics.cpp:30
SurgSim::DataStructures::OctreePath
std::vector< size_t > OctreePath
Typedef of octree path The path is a vector of children indexes (each within 0 to 7) that lead to the...
Definition: OctreeNode.h:43
SurgSim::DataStructures::SYMBOL_FRONT
@ SYMBOL_FRONT
Definition: OctreeNode.h:84
SurgSim::DataStructures::getNeighbor
SurgSim::DataStructures::OctreePath getNeighbor(const OctreePath &origin, const std::array< Symbol, 3 > &direction)
Calculate the neighbor of an node in the octree by traversing a state machine, see http://ww1....
Definition: OctreeNode.cpp:155
SurgSim::DataStructures::OctreePathHash::operator()
size_t operator()(const OctreePath &path) const
Definition: OctreeNode.h:51
SurgSim::DataStructures::OctreeNode::getClassName
std::string getClassName() const override
Support serialization with a classname.
Definition: OctreeNode-inl.h:102
SurgSim::DataStructures::SYMBOL_LEFT
@ SYMBOL_LEFT
Definition: OctreeNode.h:82
SurgSim::DataStructures::OctreeNode::m_boundingBox
SurgSim::Math::Aabbd m_boundingBox
The bounding box of the current OctreeNode.
Definition: OctreeNode.h:239
SurgSim::Math::Aabbd
Eigen::AlignedBox< double, 3 > Aabbd
Wrapper around the Eigen type.
Definition: Aabb.h:30
SurgSim::DataStructures::OctreeNode::getChild
std::shared_ptr< OctreeNode< Data > > getChild(size_t index)
Get a child of this node (non const version)
Definition: OctreeNode-inl.h:204
SurgSim::DataStructures::OctreeNodePlyReaderDelegate
Subclass the OctreeNodePLyReaderDelegateBase class to enable processing of the templated data,...
Definition: OctreeNodePlyReaderDelegate.h:135
SurgSim::DataStructures::OctreePathHash::m_hasher
std::hash< size_t > m_hasher
Definition: OctreeNode.h:62
SurgSim::DataStructures::OctreeNode::addData
bool addData(const SurgSim::Math::Vector3d &position, const int level, const Data &nodeData=Data())
Add data to a node in this octree The octree will build the octree as necessary to add the node at th...
Definition: OctreeNode-inl.h:155
SurgSim::DataStructures::OctreeNode::subdivide
void subdivide()
Subdivide the node into 8 equal regions.
Definition: OctreeNode-inl.h:132
SurgSim::DataStructures::NEIGHBORHOOD_NONE
@ NEIGHBORHOOD_NONE
Definition: OctreeNode.h:68
SurgSim::DataStructures::Neighborhood
Neighborhood
Indicates what neighbors to grab.
Definition: OctreeNode.h:67
SurgSim::DataStructures::SYMBOL_HALT
@ SYMBOL_HALT
Definition: OctreeNode.h:78
SurgSim::DataStructures::getNeighbors
std::vector< OctreePath > getNeighbors(const OctreePath &origin, int type)
Fetch a list of neighbors, indicated by the type, Face, Edge and Vertex are possible types and can be...
Definition: OctreeNode.cpp:216
Aabb.h
SurgSim::DataStructures::OctreeNode
Octree data structure.
Definition: OctreeNode.h:133
SurgSim::DataStructures::NEIGHBORHOOD_VERTEX
@ NEIGHBORHOOD_VERTEX
Definition: OctreeNode.h:71
SurgSim::DataStructures::SYMBOL_DOWN
@ SYMBOL_DOWN
Definition: OctreeNode.h:79
SurgSim::DataStructures::OctreeNode::hasChildren
bool hasChildren() const
Does this node have children.
Definition: OctreeNode-inl.h:126
SurgSim::DataStructures::OctreeNode::m_hasChildren
bool m_hasChildren
True if the node has children.
Definition: OctreeNode.h:245
SurgSim::DataStructures::OctreePathHash
Enable the OctreePath to be used as a key in an unordered map, if the int range is exceeded this will...
Definition: OctreeNode.h:49
SurgSim::DataStructures::OctreeNode::doAddData
bool doAddData(const SurgSim::Math::Vector3d &position, const Data &nodeData, const int level, const int currentLevel)
Recursive function that does the adding of the data to the octree.
Definition: OctreeNode-inl.h:161
SurgSim::DataStructures::OctreeNode::AxisAlignedBoundingBox
Eigen::AlignedBox< double, 3 > AxisAlignedBoundingBox
Bounding box type for convenience.
Definition: OctreeNode.h:140
SurgSim::DataStructures::OctreeNode::setIsActive
void setIsActive(bool isActive)
Set active flag for this octree node.
Definition: OctreeNode-inl.h:120
SurgSim::Framework::Asset
This class is used to facilitate file loading.
Definition: Asset.h:40
SurgSim::DataStructures::SYMBOL_UP
@ SYMBOL_UP
Definition: OctreeNode.h:80
SurgSim::DataStructures::OctreeNode::m_isActive
bool m_isActive
True if there is any data inside this node, including data held by children, children's children,...
Definition: OctreeNode.h:242
string
string(TOUPPER ${DEVICE} DEVICE_UPPER_CASE) option(BUILD_DEVICE_$
Definition: CMakeLists.txt:38
SurgSim::DataStructures::OctreeNode::data
Data data
Extra node data.
Definition: OctreeNode.h:224
SurgSim::DataStructures::OctreeNode::getBoundingBox
const SurgSim::Math::Aabbd & getBoundingBox() const
Get the bounding box for this octree node.
Definition: OctreeNode-inl.h:108
SurgSim::DataStructures::NEIGHBORHOOD_FACE
@ NEIGHBORHOOD_FACE
Definition: OctreeNode.h:69
SurgSim::DataStructures::OctreeNode::m_className
static std::string m_className
Definition: OctreeNode.h:251
OctreeNode-inl.h