Hi, recently we want to contribute anoctree class to thenext branch. We read some implementations in open source projects, such as Open3D, PCL, Octomap. They all contain octrees, but their implementation is different.

In the current PR, we have only implemented some very basic functions.
Before improving it, we have the following doubts:

Which functions of the octree in thenext branch should be implemented?
What is the role of theoctree in the3d module in the future?

Looking forward to your opinion, thank you.

The`viz`-based visualization examples can be found athere.

Pull Request Readiness Checklist

See details athttps://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request

I agree to contribute to the project under Apache 2 License.
To the best of my knowledge, the proposed patch is not based on a code under GPL or other license that is incompatible with OpenCV
The PR is proposed to proper branch
There is reference to original bug report and related work
There is accuracy test, performance test and test data in opencv_extra repository, if applicable
Patch to opencv_extra has the same branch name.
The feature is well documented and sample code can be built with the project CMake

vpisarev self-assigned this

Mar 26, 2021

Copy link

Contributor

vpisarev commentedMar 26, 2021

@zihaomu, thank you for the contribution and sorry for delay with the review.
More detailed review will follow, but please do the following things first of all:

expose this functionality from public OpenCV header. Since the API is rather compact, for now it can be put right intohttps://github.com/opencv/opencv/blob/next/modules/3d/include/opencv2/3d.hpp.
please, hide all the details from the header file. No class members, no private methods. Just the interface. The two possible approaches are: 1.https://github.com/opencv/opencv/wiki/Coding_Style_Guide#high-level-c-interface-algorithms, 2. "pimpl" trick (http://oliora.github.io/2015/12/29/pimpl-and-rule-of-zero.html). In OpenCV we usecv::Ptr<Impl> impl instead of a raw pointer.
please, provide some regression test. The test should read some point cloud or generate artificial one, put the points into octree, access them and check some properties (e.g. that the nearest point is found correctly etc.).

Copy link

MemberAuthor

zihaomu commentedMar 29, 2021

@zihaomu, thank you for the contribution and sorry for delay with the review.
More detailed review will follow, but please do the following things first of all:
expose this functionality from public OpenCV header. Since the API is rather compact, for now it can be put right intohttps://github.com/opencv/opencv/blob/next/modules/3d/include/opencv2/3d.hpp.
please, hide all the details from the header file. No class members, no private methods. Just the interface. The two possible approaches are: 1.https://github.com/opencv/opencv/wiki/Coding_Style_Guide#high-level-c-interface-algorithms, 2. "pimpl" trick (http://oliora.github.io/2015/12/29/pimpl-and-rule-of-zero.html). In OpenCV we usecv::Ptr<Impl> impl instead of a raw pointer.
please, provide some regression test. The test should read some point cloud or generate artificial one, put the points into octree, access them and check some properties (e.g. that the nearest point is found correctly etc.).

@vpisarev Thank you for your suggestion, I will continue to work on it.

Copy link

Contributor

asenyaev commentedApr 8, 2021

jenkins cn please retry a build

Copy link

MemberAuthor

zihaomu commentedApr 8, 2021

jenkins cn please retry a build

Hi@asenyaev. Thank you for your reminder, how to retry a build?

Copy link

Contributor

asenyaev commentedApr 8, 2021

Hi@zihaomu. The command is the same as my latest comment.

zihaomu force-pushed theoctree_in_3d branch froma0e6073 todc0acceCompare

April 29, 2021 14:47

zihaomu force-pushed theoctree_in_3d branch from100cb3d to47c510bCompare

May 7, 2021 09:18

Copy link

MemberAuthor

zihaomu commentedMay 16, 2021

@alalek @vpisarev Hi, I have added a test program and some basic neighborhood search algorithms in the new version.

alalek reviewed

May 16, 2021

View reviewed changes

Copy link

Member

alalek left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Thank you for updates!

Please take a look on the comments below.

BTW,cv::Ptr-based implementation is not efficient from time or memory consumption metrics. RGB-D cameras may provide 1M points for each frame.

Are there plans to support points "metadata" in some form?

/cc@savuor

modules/3d/include/opencv2/3d.hpp Outdated

		children[6]: origin == (0, 1, 1), size == 1, in Y-Z plane
		children[7]: origin == (1, 1, 1), size == 1, furthest from child 0
		*/
		classOctree {

Copy link

Member

alalekMay 16, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

CV_EXPORTS

Copy link

MemberAuthor

zihaomuMay 26, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Thank you for your code review. Currently, Octree to Python has not been completed, so "CV_EXPORTS" is not used.

Copy link

Member

alalekMay 27, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

CV_EXPORTS
is not the same as
CV_EXPORTS_W

This change is required. Also this would allow to remove hacks from the tests.

Copy link

MemberAuthor

zihaomuMay 28, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

@alalek Thank you for your reminder, I have added the "CV_EXPORT" flag in the new version.

modules/3d/include/opencv2/3d.hpp Outdated

		voidclear();
		voidstep();
		enum { DONE=0, STARTED=1, CALC_J=2, CHECK_ERR=3 };

Copy link

Member

alalekMay 16, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

remove unnecessary changes from the patch.

Copy link

MemberAuthor

zihaomuMay 26, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

fixed

modules/3d/include/opencv2/3d.hpp Outdated

Comment on lines 2372 to 2375

		/** @overload
		* @brief Create an empty Octree and set the maximum depth.
		* @param _maxDepth The max depth of the Octree. The _maxDepth > -1.
		*/

Copy link

Member

alalekMay 16, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Something is wrong with indentation

modules/3d/include/opencv2/3d.hpp Outdated

		* @brief Create an empty Octree and set the maximum depth.
		* @param _maxDepth The max depth of the Octree. The _maxDepth > -1.
		*/
		Octree(int _maxDepth);

Copy link

Member

alalekMay 16, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Avoid using underscore prefixes in public headers.
We don't need them in the public API.

BTW, C++ allows to use any name for parameters in .cpp file (but it should correlate with name in .hpp to keep code readable).

Copy link

MemberAuthor

zihaomuMay 26, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Thanks, this will be fixed in the new version.

modules/3d/include/opencv2/3d.hpp Outdated

		boolempty();

		/** @brief
		* Reset all octree parameterDeleting a point from the octree actually deletes the corresponding element

Copy link

Member

alalekMay 16, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

parameterDeleting

what is that?

Please re-read documentation.

Copy link

MemberAuthor

zihaomuMay 26, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

fixed

modules/3d/src/octree.hpp Outdated

Comment on lines 36 to 44

		namespacecv {
		//! @addtogroup 3d
		//! @{

		/** @brief OctreeNode for Octree.

		The class OctreeNode represents the node of the octree. Each node contains 8 children, which are used to divide the
		space cube into eight parts. Each octree node represents a cube.
		And these eight children will have a fixed order, the order is described as follows:

Copy link

Member

alalekMay 16, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Avoid indentation in namespaces.

modules/3d/test/test_octree.cpp Outdated

Comment on lines 60 to 58

		TEST_F(OctreeTest, BasicFunctionTest)
		{

Copy link

Member

alalekMay 16, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

unnecessary indentation

modules/3d/test/test_octree.cpp Outdated

Comment on lines 97 to 100

		{
		int K =4;
		std::vector<Point3f> outputPoints;
		std::vector<float> outputSquareDist;

Copy link

Member

alalekMay 16, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

missing indentation

modules/3d/test/test_octree.cpp Outdated

		{
		float _x = rng_Point.uniform(pmin.x, pmax.x);
		float _y = rng_Point.uniform(pmin.y, pmax.y);
		float _z = rng_Point.uniform(pmin.z, pmax.z);

Copy link

Member

alalekMay 16, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

BTW, floating-point random numbers are not bit-exact between platforms.

modules/3d/test/test_octree.cpp Outdated

		pmin =Point3f(-1.0f, -1.0f, -1.0f);
		pmax =Point3f(1.0f,1.0f,1.0f);

		RNGrng_Point(12345);// set random seed for fixing output 3D point.

Copy link

Member

alalekMay 16, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

OpenCV testing infrastructure should "fix"theRNG() state.

Copy link

Contributor

vpisarevMay 25, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

@zihaomu, please, removerng_Point from the class.
Before the point cloud initialization loop simply put

RNG& rng_Point = theRNG();

vpisarev reviewed

May 25, 2021

View reviewed changes

modules/3d/test/test_octree.cpp Outdated

		// Generate 3D PointCloud
		for (int i =0; i < pointCloudSize; i++)
		{
		float _x = rng_Point.uniform(pmin.x, pmax.x);

Copy link

Contributor

vpisarevMay 25, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

@zihaomu, I suggest to use integer pmin & pmax and then inside the loop scale it by a power-of-two, then we can guarantee bit-exactness between platforms:

int scale;Point3i pmin, pmax;....scale = 1<<20;pmin = Point3i(-scale, -scale, -scale);pmax = Point3i(scale, scale, scale);...RNG rng_Point(12345);

for(int i = 0; i , pointCloudSize; i++){     float _x = (float)rng_Point.uniform(pmin.x, pmax.x)/scale;     float _y = (float)rng_Point.uniform(pmin.y, pmax.y)/scale;     float _z = (float)rng_Point.uniform(pmin.z, pmax.z)/scale;     pointcloud.push_back(Point3f(_x, _y, _z));}

zihaomu force-pushed theoctree_in_3d branch fromccb057a to53b29efCompare

May 27, 2021 09:23

vpisarev self-requested a review

May 27, 2021 14:41

vpisarev approved these changes

May 27, 2021

View reviewed changes

vpisarev requested a review fromalalek

May 27, 2021 14:42

alalek reviewed

May 31, 2021

View reviewed changes

modules/3d/src/octree.hpp Outdated

		//
		// License Agreement
		// For Open Source Computer Vision Library
		//

Copy link

Member

alalekMay 31, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Please align license headers in both files fromsrc/ directory (they should have the same content).
Consider using this form:

// This file is part of OpenCV project.// It is subject to the license terms in the LICENSE file found in the top-level directory// of this distribution and at http://opencv.org/license.html.

then add this if required:

//// Copyright (C) 2021, Huawei Technologies Co., Ltd. All rights reserved.// Third party copyrights are property of their respective owners.

And optionally add this:

//// Author: Zihao Mu <zihaomu6@gmail.com>//         Liangqian Kong <chargerKong@126.com>//         Longbu Wang <riskiest@gmail.com>

modules/3d/src/octree.hpp Outdated

		// Longbu Wang <riskiest@gmail.com>

		#ifndef OPENCV_OCTREE_OCTREE_H
		#defineOPENCV_OCTREE_OCTREE_H

Copy link

Member

alalekMay 31, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

OPENCV_OCTREE_OCTREE_H

OPENCV_3D_SRC_OCTREE_HPP (OPENCV_<module_name>_<file_path_name>_HPP)

modules/3d/src/octree.hpp Outdated

Comment on lines 115 to 116


		constfloat epsilon = std::numeric_limits<float>::epsilon();// For precision of floating point

Copy link

Member

alalekMay 31, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

used?

If so, then replace withstd::numeric_limits<float>::epsilon() directly.

modules/3d/src/octree.hpp Outdated

Comment on lines 113 to 114


		conststaticint octreeChildNum =8;// Each OctreeNode contains up to 8 children.

Copy link

Member

alalekMay 31, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Put global constant intoOctreeNode class (probably as enum value).

modules/3d/src/octree.cpp

Comment on lines +6 to +7

		#include"octree.hpp"

Copy link

Member

alalekMay 31, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

octree.hpp

Do we need dedicatedsrc/octree.hpp file? (it makes sense to put all details in this .cpp file)

modules/3d/test/test_octree.cpp Outdated


		usingnamespacecv;

		classOctreeTest:public::testing::Test

Copy link

Member

alalekMay 31, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

public<space>

modules/3d/test/test_octree.cpp Outdated

		std::vector<float> outputSquareDist;
		EXPECT_NO_THROW(octreeRadiusNNSearch(treeTest, restPoint, radius, outputPoints, outputSquareDist));

		EXPECT_NEAR(outputPoints[0].x, -0.888461112976f, std::numeric_limits<float>::epsilon());

Copy link

Member

alalekMay 31, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

EXPECT_FLOAT_EQ()?

modules/3d/test/test_octree.cpp Outdated

		{
		// Check if the point in Bound.
		EXPECT_EQ(treeTest.isPointInBound(restPoint),true);
		EXPECT_EQ(treeTest.isPointInBound(restPoint +Point3f(2,2,2)),false);

Copy link

Member

alalekMay 31, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

EXPECT_TRUE()
EXPECT_FALSE()

here and below with true/false

modules/3d/src/octree.cpp Outdated

Comment on lines 167 to 226

		Ptr<OctreeNode>index(const Point3f& point, Ptr<OctreeNode>& node)
		{
		if(node ==nullptr)
		{
		returnnullptr;
		}

Copy link

Member

alalekMay 31, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

node == nullptr comparison is not efficient. Useoperator bool instead.
return nullptr; is not efficient.
reduce amount ofnode-> dereferences.

Ptr<OctreeNode> index(const Point3f& point, Ptr<OctreeNode>& node_){    if (!node_)    {        return Ptr<OctreeNode>();    }    OctreeNode& node = *node_;    ...}

Probably you don't needPtr<> in this implementation.

Ptr<OctreeNode> index(const Point3f& point, const OctreeNode& node)

modules/3d/include/opencv2/3d.hpp Outdated



		/** @brief Octree for 3D vision.
		In 3D vision filed, the Octree is used to process and accelerate the pointcloud data. The class Octree represents

Copy link

Member

alalekMay 31, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

empty line after@brief note:http://pullrequest.opencv.org/buildbot/export/pr/19684/docs/d3/da6/classcv_1_1Octree.html

zihaomu requested a review fromalalek

June 4, 2021 02:20

alalek reviewed

Jun 5, 2021

View reviewed changes

Copy link

Member

alalek left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Thank you for update!

modules/3d/src/octree.hpp Outdated

		#ifndef OPENCV_3D_SRC_OCTREE_HPP
		#defineOPENCV_3D_SRC_OCTREE_HPP

		#include"precomp.hpp"

Copy link

Member

alalekJun 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

precomp.hpp

should be used by .cpp files only (as first include)

modules/3d/include/opencv2/3d.hpp Outdated

		* @param maxDepth The max depth of the Octree.
		* @return Returns whether the creation is successful.
		*/
		boolcreat(const std::vector<Point3f> &pointCloud,int maxDepth = -1);

Copy link

Member

alalekJun 4, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

creat

create

modules/3d/src/octree.cpp Outdated

Comment on lines 12 to 24

		// Locate the OctreeNode corresponding to the input point from the given OctreeNode.
		Ptr<OctreeNode>index(const Point3f& point, Ptr<OctreeNode>& node);

		bool_isPointInBound(const Point3f& _point,const Point3f& _origin,double _size);
		voidinsertPointRecurse( Ptr<OctreeNode>& node,const Point3f& point,int maxDepth);
		booldeletePointRecurse( Ptr<OctreeNode>& node);

		// For Nearest neighbor search.
		floatSquaredDistance(const Point3f& query,const Point3f& origin);
		booloverlap(const OctreeNode& node,const Point3f& query,float squareRadius);
		template<typename T>structPQueueElem;// Priority queue
		voidradiusNNSearchRecurse(const Ptr<OctreeNode>& node,const Point3f& query,float squareRadius,
		std::vector<PQueueElem<Point3f>>& candidatePoint);
		voidKNNSearchRecurse(const Ptr<OctreeNode>& node,const Point3f& query,constint K,
		float& smallestDist, std::vector<PQueueElem<Point3f>>& candidatePoint);

Copy link

Member

alalekJun 5, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

These declarations should be local - usestatic for that.
Also some declaration can be removed (used after declaration) - addstatic to definition only.

Copy link

MemberAuthor

zihaomuJun 7, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Thank you for your carefully reviewing. I have addedstatic prefix in these functions.

zihaomu force-pushed theoctree_in_3d branch 2 times, most recently from9fc54fd toae07a9eCompare

June 7, 2021 15:41

zihaomu requested a review fromalalek

June 8, 2021 01:09

Copy link

Contributor

vpisarev commentedJun 8, 2021

@zihaomu, thank you! Could you, please, squash the commits into 1?

cd <opencv_root>git status # make sure you are on the proper branchgit reset --soft HEAD~8 # the number of commits so fargit commitgit push --force origin

zihaomu force-pushed theoctree_in_3d branch fromae07a9e to23cd8c2Compare

June 8, 2021 01:35

Copy link

Contributor

vpisarev commentedJun 8, 2021

@zihaomu, for some reason, there is merge conflict after squash

zihaomu force-pushed theoctree_in_3d branch from22f9fba to1026286Compare

June 8, 2021 01:59

Copy link

Contributor

vpisarev commentedJun 8, 2021

@zihaomu, check the PR more carefully. Now it shows that 1297 files are changed. There is something wrong

Copy link

MemberAuthor

zihaomu commentedJun 8, 2021

@zihaomu, check the PR more carefully. Now it shows that 1297 files are changed. There is something wrong

Thank you, I'm checking it now.

add Octree to 3d module of next branch.

5c0ac37

zihaomu force-pushed theoctree_in_3d branch from1026286 to5c0ac37Compare

June 8, 2021 03:19

opencv-pushbot merged commit4dc8119 intoopencv:next

Jun 8, 2021

Copy link

Member

alalek commentedJun 19, 2021

Valgrind builder reports about memory leaks from octree code:http://pullrequest.opencv.org/buildbot/builders/5_x_valgrind-lin64-debug/builds/10
Please take a look

Copy link

MemberAuthor

zihaomu commentedJun 19, 2021

Valgrind builder reports about memory leaks from octree code:http://pullrequest.opencv.org/buildbot/builders/5_x_valgrind-lin64-debug/builds/10
Please take a look

Thank you for pointing out this. I will keep work on it.

zihaomu mentioned this pull request

Oct 22, 2022

3D: Handle cases where the depth of Octree setting is too large#22682

Merged

6 tasks

Labels

category: 3d module feature test

Movatterモバイル変換

Uh oh!

Add Octree to 3D module in next branch - in progress#19684

Add Octree to 3D module in next branch - in progress#19684

Uh oh!

Conversation

zihaomu commentedMar 6, 2021• editedLoading Uh oh!There was an error while loading.Please reload this page.

Uh oh!

Add Octree to 3D module in next branch - in progress

Theviz-based visualization examples can be found athere.

Pull Request Readiness Checklist

Uh oh!

vpisarev commentedMar 26, 2021

Uh oh!

zihaomu commentedMar 29, 2021

Uh oh!

asenyaev commentedApr 8, 2021

Uh oh!

zihaomu commentedApr 8, 2021

Uh oh!

asenyaev commentedApr 8, 2021

Uh oh!

zihaomu commentedMay 16, 2021

Uh oh!

alalek left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

zihaomu commentedMar 6, 2021•
edited
Loading

The`viz`-based visualization examples can be found athere.