Open3D (C++ API)  0.18.0+3975044
Octree.h
Go to the documentation of this file.
1 // ----------------------------------------------------------------------------
2 // - Open3D: www.open3d.org -
3 // ----------------------------------------------------------------------------
4 // Copyright (c) 2018-2023 www.open3d.org
5 // SPDX-License-Identifier: MIT
6 // ----------------------------------------------------------------------------
7 
8 #pragma once
9 
10 #include <cstddef>
11 #include <memory>
12 #include <vector>
13 
16 
17 namespace open3d {
18 namespace geometry {
19 
20 class PointCloud;
21 class VoxelGrid;
22 
29 public:
33  OctreeNodeInfo() : origin_(0, 0, 0), size_(0), depth_(0), child_index_(0) {}
34 
41  OctreeNodeInfo(const Eigen::Vector3d& origin,
42  const double& size,
43  const size_t& depth,
44  const size_t& child_index)
45  : origin_(origin),
46  size_(size),
47  depth_(depth),
48  child_index_(child_index) {}
50 
51 public:
53  Eigen::Vector3d origin_;
55  double size_;
57  size_t depth_;
60  size_t child_index_;
61 };
62 
71 public:
75  virtual ~OctreeNode() {}
76 
78  static std::shared_ptr<OctreeNode> ConstructFromJsonValue(
79  const Json::Value& value);
80 };
81 
101 public:
105  static std::shared_ptr<OctreeNodeInfo> GetInsertionNodeInfo(
106  const std::shared_ptr<OctreeNodeInfo>& node_info,
107  const Eigen::Vector3d& point);
108 
113  static std::function<std::shared_ptr<OctreeInternalNode>()>
114  GetInitFunction();
115 
119  static std::function<void(std::shared_ptr<OctreeInternalNode>)>
121 
122  bool ConvertToJsonValue(Json::Value& value) const override;
123  bool ConvertFromJsonValue(const Json::Value& value) override;
124 
125 public:
130  std::vector<std::shared_ptr<OctreeNode>> children_;
131 };
132 
138 public:
142 
147  static std::function<std::shared_ptr<OctreeInternalNode>()>
148  GetInitFunction();
149 
154  static std::function<void(std::shared_ptr<OctreeInternalNode>)>
155  GetUpdateFunction(size_t idx);
156 
157  bool ConvertToJsonValue(Json::Value& value) const override;
158  bool ConvertFromJsonValue(const Json::Value& value) override;
159 
160 public:
162  std::vector<size_t> indices_;
163 };
164 
168 class OctreeLeafNode : public OctreeNode {
169 public:
170  virtual bool operator==(const OctreeLeafNode& other) const = 0;
172  virtual std::shared_ptr<OctreeLeafNode> Clone() const = 0;
173 };
174 
179 public:
180  bool operator==(const OctreeLeafNode& other) const override;
181 
183  std::shared_ptr<OctreeLeafNode> Clone() const override;
184 
189  static std::function<std::shared_ptr<OctreeLeafNode>()> GetInitFunction();
190 
197  static std::function<void(std::shared_ptr<OctreeLeafNode>)>
198  GetUpdateFunction(const Eigen::Vector3d& color);
199 
200  bool ConvertToJsonValue(Json::Value& value) const override;
201  bool ConvertFromJsonValue(const Json::Value& value) override;
204  Eigen::Vector3d color_ = Eigen::Vector3d(0, 0, 0);
205 };
206 
213 public:
214  bool operator==(const OctreeLeafNode& other) const override;
216  std::shared_ptr<OctreeLeafNode> Clone() const override;
217 
222  static std::function<std::shared_ptr<OctreeLeafNode>()> GetInitFunction();
223 
231  static std::function<void(std::shared_ptr<OctreeLeafNode>)>
232  GetUpdateFunction(size_t index, const Eigen::Vector3d& color);
233 
234  bool ConvertToJsonValue(Json::Value& value) const override;
235  bool ConvertFromJsonValue(const Json::Value& value) override;
236 
238  std::vector<size_t> indices_;
239 };
240 
245 public:
249  origin_(0, 0, 0),
250  size_(0),
251  max_depth_(0) {}
255  Octree(const size_t& max_depth)
257  origin_(0, 0, 0),
258  size_(0),
259  max_depth_(max_depth) {}
265  Octree(const size_t& max_depth,
266  const Eigen::Vector3d& origin,
267  const double& size)
269  origin_(origin),
270  size_(size),
271  max_depth_(max_depth) {}
272  Octree(const Octree& src_octree);
273  ~Octree() override {}
274 
275 public:
276  Octree& Clear() override;
277  bool IsEmpty() const override;
278  Eigen::Vector3d GetMinBound() const override;
279  Eigen::Vector3d GetMaxBound() const override;
280  Eigen::Vector3d GetCenter() const override;
281 
285 
289  bool robust = false) const override;
290 
294  bool robust = false) const override;
295 
296  Octree& Transform(const Eigen::Matrix4d& transformation) override;
297  Octree& Translate(const Eigen::Vector3d& translation,
298  bool relative = true) override;
299  Octree& Scale(const double scale, const Eigen::Vector3d& center) override;
300  Octree& Rotate(const Eigen::Matrix3d& R,
301  const Eigen::Vector3d& center) override;
302  bool ConvertToJsonValue(Json::Value& value) const override;
303  bool ConvertFromJsonValue(const Json::Value& value) override;
304 
305 public:
312  void ConvertFromPointCloud(const geometry::PointCloud& point_cloud,
313  double size_expand = 0.01);
314 
316  std::shared_ptr<OctreeNode> root_node_ = nullptr;
317 
320  Eigen::Vector3d origin_;
321 
324  double size_;
325 
328  size_t max_depth_;
329 
343  void InsertPoint(
344  const Eigen::Vector3d& point,
345  const std::function<std::shared_ptr<OctreeLeafNode>()>& fl_init,
346  const std::function<void(std::shared_ptr<OctreeLeafNode>)>&
347  fl_update,
348  const std::function<std::shared_ptr<OctreeInternalNode>()>&
349  fi_init = nullptr,
350  const std::function<void(std::shared_ptr<OctreeInternalNode>)>&
351  fi_update = nullptr);
352 
360  void Traverse(
361  const std::function<bool(const std::shared_ptr<OctreeNode>&,
362  const std::shared_ptr<OctreeNodeInfo>&)>&
363  f);
364 
372  void Traverse(
373  const std::function<bool(const std::shared_ptr<OctreeNode>&,
374  const std::shared_ptr<OctreeNodeInfo>&)>&
375  f) const;
376 
377  std::pair<std::shared_ptr<OctreeLeafNode>, std::shared_ptr<OctreeNodeInfo>>
378 
383  LocateLeafNode(const Eigen::Vector3d& point) const;
384 
391  static bool IsPointInBound(const Eigen::Vector3d& point,
392  const Eigen::Vector3d& origin,
393  const double& size);
394 
396  bool operator==(const Octree& other) const;
397 
399  std::shared_ptr<geometry::VoxelGrid> ToVoxelGrid() const;
400 
402  void CreateFromVoxelGrid(const geometry::VoxelGrid& voxel_grid);
403 
404 private:
405  static void TraverseRecurse(
406  const std::shared_ptr<OctreeNode>& node,
407  const std::shared_ptr<OctreeNodeInfo>& node_info,
408  const std::function<bool(const std::shared_ptr<OctreeNode>&,
409  const std::shared_ptr<OctreeNodeInfo>&)>&
410  f);
411 
412  void InsertPointRecurse(
413  const std::shared_ptr<OctreeNode>& node,
414  const std::shared_ptr<OctreeNodeInfo>& node_info,
415  const Eigen::Vector3d& point,
416  const std::function<std::shared_ptr<OctreeLeafNode>()>& f_l_init,
417  const std::function<void(std::shared_ptr<OctreeLeafNode>)>&
418  f_l_update,
419  const std::function<std::shared_ptr<OctreeInternalNode>()>&
420  f_i_init,
421  const std::function<void(std::shared_ptr<OctreeInternalNode>)>&
422  f_i_update);
423 };
424 
425 } // namespace geometry
426 } // namespace open3d
math::float4 color
Definition: LineSetBuffers.cpp:45
A bounding box that is aligned along the coordinate axes and defined by the min_bound and max_bound.
Definition: BoundingVolume.h:160
The base geometry class for 3D geometries.
Definition: Geometry3D.h:28
The base geometry class.
Definition: Geometry.h:18
GeometryType
Specifies possible geometry types.
Definition: Geometry.h:23
OctreeColorLeafNode class is an OctreeLeafNode containing color.
Definition: Octree.h:178
bool ConvertToJsonValue(Json::Value &value) const override
Definition: Octree.cpp:232
Eigen::Vector3d color_
Definition: Octree.h:204
bool operator==(const OctreeLeafNode &other) const override
Definition: Octree.cpp:222
std::shared_ptr< OctreeLeafNode > Clone() const override
Clone this OctreeLeafNode.
Definition: Octree.cpp:216
static std::function< std::shared_ptr< OctreeLeafNode >)> GetInitFunction()
Get lambda function for initializing OctreeLeafNode.
Definition: Octree.cpp:194
bool ConvertFromJsonValue(const Json::Value &value) override
Definition: Octree.cpp:237
static std::function< void(std::shared_ptr< OctreeLeafNode >)> GetUpdateFunction(const Eigen::Vector3d &color)
Get lambda function for updating OctreeLeafNode.
Definition: Octree.cpp:201
Octree datastructure.
Definition: Octree.h:244
void ConvertFromPointCloud(const geometry::PointCloud &point_cloud, double size_expand=0.01)
Convert octree from point cloud.
Definition: Octree.cpp:544
std::shared_ptr< OctreeNode > root_node_
Root of the octree.
Definition: Octree.h:316
Eigen::Vector3d GetCenter() const override
Returns the center of the geometry coordinates.
Definition: Octree.cpp:502
bool IsEmpty() const override
Returns true iff the geometry is empty.
Definition: Octree.cpp:484
bool ConvertToJsonValue(Json::Value &value) const override
Definition: Octree.cpp:754
Octree & Clear() override
Clear all elements in the geometry.
Definition: Octree.cpp:476
bool operator==(const Octree &other) const
Returns true if the Octree is completely the same, used for testing.
Definition: Octree.cpp:381
Eigen::Vector3d origin_
Definition: Octree.h:320
std::pair< std::shared_ptr< OctreeLeafNode >, std::shared_ptr< OctreeNodeInfo > > LocateLeafNode(const Eigen::Vector3d &point) const
Returns leaf OctreeNode and OctreeNodeInfo where the querypoint should reside.
Definition: Octree.cpp:725
OrientedBoundingBox GetMinimalOrientedBoundingBox(bool robust=false) const override
Definition: Octree.cpp:518
Eigen::Vector3d GetMinBound() const override
Returns min bounds for geometry coordinates.
Definition: Octree.cpp:486
bool ConvertFromJsonValue(const Json::Value &value) override
Definition: Octree.cpp:768
Octree & Rotate(const Eigen::Matrix3d &R, const Eigen::Vector3d &center) override
Apply rotation to the geometry coordinates and normals. Given a rotation matrix , and center ,...
Definition: Octree.cpp:538
double size_
Definition: Octree.h:324
AxisAlignedBoundingBox GetAxisAlignedBoundingBox() const override
Definition: Octree.cpp:506
void CreateFromVoxelGrid(const geometry::VoxelGrid &voxel_grid)
Convert from voxel grid.
Definition: Octree.cpp:789
Octree & Transform(const Eigen::Matrix4d &transformation) override
Apply transformation (4x4 matrix) to the geometry coordinates.
Definition: Octree.cpp:523
Octree & Translate(const Eigen::Vector3d &translation, bool relative=true) override
Apply translation to the geometry coordinates.
Definition: Octree.cpp:528
std::shared_ptr< geometry::VoxelGrid > ToVoxelGrid() const
Convert to VoxelGrid.
Definition: Octree.cpp:748
OrientedBoundingBox GetOrientedBoundingBox(bool robust=false) const override
Definition: Octree.cpp:513
static bool IsPointInBound(const Eigen::Vector3d &point, const Eigen::Vector3d &origin, const double &size)
Return true if point within bound, that is, origin <= point < origin + size.
Definition: Octree.cpp:661
void Traverse(const std::function< bool(const std::shared_ptr< OctreeNode > &, const std::shared_ptr< OctreeNodeInfo > &)> &f)
DFS traversal of Octree from the root, with callback function called for each node.
Definition: Octree.cpp:669
size_t max_depth_
Definition: Octree.h:328
Octree(const size_t &max_depth)
Parameterized Constructor.
Definition: Octree.h:255
Octree(const size_t &max_depth, const Eigen::Vector3d &origin, const double &size)
Parameterized Constructor.
Definition: Octree.h:265
~Octree() override
Definition: Octree.h:273
Octree()
Default Constructor.
Definition: Octree.h:247
void InsertPoint(const Eigen::Vector3d &point, const std::function< std::shared_ptr< OctreeLeafNode >()> &fl_init, const std::function< void(std::shared_ptr< OctreeLeafNode >)> &fl_update, const std::function< std::shared_ptr< OctreeInternalNode >()> &fi_init=nullptr, const std::function< void(std::shared_ptr< OctreeInternalNode >)> &fi_update=nullptr)
Insert a point to the octree.
Definition: Octree.cpp:577
Octree & Scale(const double scale, const Eigen::Vector3d &center) override
Apply scaling to the geometry coordinates. Given a scaling factor , and center , a given point is tr...
Definition: Octree.cpp:533
Eigen::Vector3d GetMaxBound() const override
Returns max bounds for geometry coordinates.
Definition: Octree.cpp:494
OctreeInternalNode class, containing OctreeNode children.
Definition: Octree.h:100
std::vector< std::shared_ptr< OctreeNode > > children_
Definition: Octree.h:130
static std::shared_ptr< OctreeNodeInfo > GetInsertionNodeInfo(const std::shared_ptr< OctreeNodeInfo > &node_info, const Eigen::Vector3d &point)
Definition: Octree.cpp:52
static std::function< std::shared_ptr< OctreeInternalNode >)> GetInitFunction()
Get lambda function for initializing OctreeInternalNode.
Definition: Octree.cpp:76
static std::function< void(std::shared_ptr< OctreeInternalNode >)> GetUpdateFunction()
Get lambda function for updating OctreeInternalNode.
Definition: Octree.cpp:83
bool ConvertFromJsonValue(const Json::Value &value) override
Definition: Octree.cpp:103
bool ConvertToJsonValue(Json::Value &value) const override
Definition: Octree.cpp:87
OctreeInternalNode()
Default Constructor.
Definition: Octree.h:104
OctreeInternalPointNode class is an OctreeInternalNode containing a list of indices which is the unio...
Definition: Octree.h:137
OctreeInternalPointNode()
Default Constructor.
Definition: Octree.h:141
std::vector< size_t > indices_
Indices of points associated with any children of this node.
Definition: Octree.h:162
bool ConvertFromJsonValue(const Json::Value &value) override
Definition: Octree.cpp:167
static std::function< std::shared_ptr< OctreeInternalNode >)> GetInitFunction()
Get lambda function for initializing OctreeInternalPointNode.
Definition: Octree.cpp:124
bool ConvertToJsonValue(Json::Value &value) const override
Definition: Octree.cpp:146
OctreeLeafNode base class.
Definition: Octree.h:168
virtual bool operator==(const OctreeLeafNode &other) const =0
virtual std::shared_ptr< OctreeLeafNode > Clone() const =0
Clone this OctreeLeafNode.
The base class for octree node.
Definition: Octree.h:70
OctreeNode()
Default Constructor.
Definition: Octree.h:74
static std::shared_ptr< OctreeNode > ConstructFromJsonValue(const Json::Value &value)
Factory function to construct an OctreeNode by parsing the json value.
Definition: Octree.cpp:24
virtual ~OctreeNode()
Definition: Octree.h:75
OctreeNode's information.
Definition: Octree.h:28
size_t child_index_
Definition: Octree.h:60
~OctreeNodeInfo()
Definition: Octree.h:49
OctreeNodeInfo(const Eigen::Vector3d &origin, const double &size, const size_t &depth, const size_t &child_index)
Parameterized Constructor.
Definition: Octree.h:41
double size_
Size of the node.
Definition: Octree.h:55
OctreeNodeInfo()
Default Constructor.
Definition: Octree.h:33
Eigen::Vector3d origin_
Origin coordinate of the node.
Definition: Octree.h:53
size_t depth_
Depth of the node to the root. The root is of depth 0.
Definition: Octree.h:57
OctreePointColorLeafNode class is an OctreeColorLeafNode containing a list of indices corresponding t...
Definition: Octree.h:212
static std::function< std::shared_ptr< OctreeLeafNode >)> GetInitFunction()
Get lambda function for initializing OctreeLeafNode.
Definition: Octree.cpp:251
bool ConvertToJsonValue(Json::Value &value) const override
Definition: Octree.cpp:297
std::vector< size_t > indices_
Associated point indices with this node.
Definition: Octree.h:238
static std::function< void(std::shared_ptr< OctreeLeafNode >)> GetUpdateFunction(size_t index, const Eigen::Vector3d &color)
Get lambda function for updating OctreeLeafNode.
Definition: Octree.cpp:258
bool operator==(const OctreeLeafNode &other) const override
Definition: Octree.cpp:284
bool ConvertFromJsonValue(const Json::Value &value) override
Definition: Octree.cpp:307
std::shared_ptr< OctreeLeafNode > Clone() const override
Clone this OctreeLeafNode.
Definition: Octree.cpp:277
A bounding box oriented along an arbitrary frame of reference.
Definition: BoundingVolume.h:25
A point cloud consists of point coordinates, and optionally point colors and point normals.
Definition: PointCloud.h:36
VoxelGrid is a collection of voxels which are aligned in grid.
Definition: VoxelGrid.h:61
Definition: IJsonConvertible.h:40
int size
Definition: FilePCD.cpp:40
const char const char value recording_handle imu_sample void
Definition: K4aPlugin.cpp:250
Definition: PinholeCameraIntrinsic.cpp:16