Open3D (C++ API)  0.17.0
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
17namespace open3d {
18namespace geometry {
19
20class PointCloud;
21class VoxelGrid;
22
29public:
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
51public:
53 Eigen::Vector3d origin_;
55 double size_;
57 size_t depth_;
61};
62
71public:
75 virtual ~OctreeNode() {}
76
78 static std::shared_ptr<OctreeNode> ConstructFromJsonValue(
79 const Json::Value& value);
80};
81
101public:
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>()>
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
125public:
130 std::vector<std::shared_ptr<OctreeNode>> children_;
131};
132
138public:
142
147 static std::function<std::shared_ptr<OctreeInternalNode>()>
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
160public:
162 std::vector<size_t> indices_;
163};
164
169public:
170 virtual bool operator==(const OctreeLeafNode& other) const = 0;
172 virtual std::shared_ptr<OctreeLeafNode> Clone() const = 0;
173};
174
179public:
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
213public:
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
245public:
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
275public:
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
305public:
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
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
404private:
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.
Definition: BoundingVolume.h:159
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
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
static std::function< std::shared_ptr< OctreeLeafNode >()> GetInitFunction()
Get lambda function for initializing OctreeLeafNode.
Definition: Octree.cpp:194
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< 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
static std::function< std::shared_ptr< OctreeInternalNode >()> GetInitFunction()
Get lambda function for initializing OctreeInternalNode.
Definition: Octree.cpp:76
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
static std::function< std::shared_ptr< OctreeInternalNode >()> GetInitFunction()
Get lambda function for initializing OctreeInternalPointNode.
Definition: Octree.cpp:124
bool ConvertFromJsonValue(const Json::Value &value) override
Definition: Octree.cpp:167
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
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< std::shared_ptr< OctreeLeafNode >()> GetInitFunction()
Get lambda function for initializing OctreeLeafNode.
Definition: Octree.cpp:251
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