Hello,
I'm reading the source code of octree in pcl, but I have some problem. I don't know how to understand the procedure of building an octree, is there any thesis introducing the procedure of building an octree in pcl?And what's the purpose of using depth_mask_? -- Sent from: http://www.pcl-users.org/ _______________________________________________ [hidden email] / http://pointclouds.org http://pointclouds.org/mailman/listinfo/pcl-users |
Hi, The construction of the octree is tricky (for me). But you can understand it with a good debugger. If you want to discuss efficiently by mail, please give us the name of one method you are looking at, or copy/paste the code in your body mail, it would be better. General feeling about depth_mask_, is used to get the key of a node at a given depth level of the octree. Best regards, frozar 2018-01-18 14:57 GMT+01:00 JamesRayen <[hidden email]>: Hello, _______________________________________________ [hidden email] / http://pointclouds.org http://pointclouds.org/mailman/listinfo/pcl-users |
Fabien Rozar wrote
> Hi, > > The construction of the octree is tricky (for me). But you can > understand it with a good debugger. > > If you want to discuss efficiently by mail, please give us the > name of one method you are looking at, or copy/paste the > code in your body mail, it would be better. > > General feeling about depth_mask_, is used to get the key > of a node at a given depth level of the octree. > > Best regards, > frozar > > 2018-01-18 14:57 GMT+01:00 JamesRayen < > zc_mail163@ > >: > >> Hello, >> I'm reading the source code of octree in pcl, but I have some problem. I >> don't know how to understand the procedure of building an octree, is >> there >> any thesis introducing the procedure of building an octree in pcl?And >> what's >> the purpose of using depth_mask_? >> >> >> >> -- >> Sent from: http://www.pcl-users.org/ >> _______________________________________________ >> > PCL-users@ > / http://pointclouds.org >> http://pointclouds.org/mailman/listinfo/pcl-users >> > > _______________________________________________ > PCL-users@ > / http://pointclouds.org > http://pointclouds.org/mailman/listinfo/pcl-users Hi, thanks for your kindly reply. I was not sure that if I pasted the source code there would be someone who would like to read. Here, I paste some source code, would you help me ? OctreeBase<LeafContainerT, BranchContainerT>::setTreeDepth (unsigned int depth_arg) { assert(depth_arg>0); // set octree depth octree_depth_ = depth_arg; // define depthMask_ by setting a single bit to 1 at bit position == tree depth depth_mask_ = (1 << (depth_arg - 1)); // define max. keys max_key_.x = max_key_.y = max_key_.z = (1 << depth_arg) - 1; } inline unsigned char getChildIdxWithDepthMask (unsigned int depthMask) const { return static_cast<unsigned char> (((!!(this->x & depthMask)) << 2) | ((!!(this->y & depthMask)) << 1) | (!!(this->z & depthMask))); } 'setTreeDepth' is a funtion in octree_base.hpp, and 'getChildIdxWithDepthMask' is a funtion in octree_key.h, I don't know why depth_mask_ is set to (1 << (depth_arg - 1)) and the reason of using depthMask to get child index. Also, I don't understand the reason of using double '!', and there are some fuctions using double '!' such as function 'getBranchBitPattern' in octree_base.h and function 'pushBranch' in octree_key.h. Could you help me with these questions? Thank you very much! Best Wishes! JamesRayen -- Sent from: http://www.pcl-users.org/ _______________________________________________ [hidden email] / http://pointclouds.org http://pointclouds.org/mailman/listinfo/pcl-users |
On 21-01-2018 00:16, JamesRayen wrote:
Hi, thanks for your kindly reply. I was not sure that if I pasted the sourceThis one is kind of involved to explain and I'm not sure I fully understand the entire process, but the answer to this question lies in the way the unique ids are generated, so let me start with a simple example.code there would be someone who would like to read. Here, I paste some source code, would you help me ? OctreeBase<LeafContainerT, BranchContainerT>::setTreeDepth (unsigned int depth_arg) { assert(depth_arg>0); // set octree depth octree_depth_ = depth_arg; // define depthMask_ by setting a single bit to 1 at bit position == tree depth depth_mask_ = (1 << (depth_arg - 1)); // define max. keys max_key_.x = max_key_.y = max_key_.z = (1 << depth_arg) - 1; } inline unsigned char getChildIdxWithDepthMask (unsigned int depthMask) const { return static_cast<unsigned char> (((!!(this->x & depthMask)) << 2) | ((!!(this->y & depthMask)) << 1) | (!!(this->z & depthMask))); } 'setTreeDepth' is a funtion in octree_base.hpp, and 'getChildIdxWithDepthMask' is a funtion in octree_key.h, I don't know why depth_mask_ is set to (1 << (depth_arg - 1)) and the reason of using depthMask to get child index. Also, I don't understand the reason of using double '!', and there are some fuctions using double '!' such as function 'getBranchBitPattern' in octree_base.h and function 'pushBranch' in octree_key.h. Could you help me with these questions? Thank you very much! - Assume we're dealing with a 1D case, a spatial coordinate represented by 'x', which ranges at most from the coordinates 0 to 1 - Now lets add the requirement that octree (in this case binary tree because it's 1D only) nodes need to have a unique key. I'm gonna refer to these keys in binary format Understanding the ID construction As a first step let's assume the binary tree only has depth 1, which implies two leaf nodes - leaf node id: 0 - represents the interval from [0, 0.5] - leaf node id: 1 - represents the interval from [0.5, 1] If the depth was 2, we would have two branch nodes and 4 leaf nodes (Disclaimer: the bit ordering might be reversed from the actual PCL implementation but same principles apply) - branch node id: 0x - represents the interval from [0, 0.5] - branch node id: 1x - represents the interval from [0.5, 1] - leaf node id: 00 - represents the interval from [0, 0.25] - leaf node id: 01 - represents the interval from [0.25, 0.5] - leaf node id: 10 - represents the interval from [0.5, 0.75] - leaf node id: 11 - represents the interval from [0.75, 1] So on and so forth as you increase the depth... Extending this to 3D is simply concatenating three of these binary ids for each dimension. Max Key If you look closely there's a close relationship between the tree depth and the maximum number of bits which can be used as an id. - depth = 1 -> only one bit was used and enough to represent everything - depth = 2 -> two bits were required to represent everything Now lets decompose the following expression assuming depth_arg is 2: (1 << depth_arg) - 1 (1 << 2) = 100 (1 << 2) - 1 = 011 11 is exactly the maximum id which a lead node could have in our previous example This is all I have time to explain for now, but it should be enough to help you decode the particular functions you posted. Cheers _______________________________________________ [hidden email] / http://pointclouds.org http://pointclouds.org/mailman/listinfo/pcl-users signature.asc (836 bytes) Download Attachment |
Thanks for your detailed answer, it's really helpful to me. Now I know the
relationship between depth and max_key. However, I'm still puzzled about the meaning of 'depth_mask_' and the reason of using 'depthMask' in function getChildIdxWithDepthMask. In function setTreeDepth: ////////////////////////////////////////////////////////////////////////////////////////////// template<typename LeafContainerT, typename BranchContainerT> void OctreeBase<LeafContainerT, BranchContainerT>::setTreeDepth (unsigned int depth_arg) { assert(depth_arg>0); // set octree depth octree_depth_ = depth_arg; // define depthMask_ by setting a single bit to 1 at bit position == tree depth depth_mask_ = (1 << (depth_arg - 1)); // define max. keys max_key_.x = max_key_.y = max_key_.z = (1 << depth_arg) - 1; } if depth_arg is set to 3(011 in binary format), then octree_depth_ is 3 too, and depth_mask_ is 100 in binary format(equals to 4 in decimal format, not equals to 3). What's more, in function getChildIdxWithDepthMask, inline unsigned char getChildIdxWithDepthMask (unsigned int depthMask) const { return static_cast<unsigned char> (((!!(this->x & depthMask)) << 2) | ((!!(this->y & depthMask)) << 1) | (!!(this->z & depthMask))); } 'depthMask' is used to operate 'and' with key components(i.e. x,y,z) to get child index, then double '!' are used, and the results shift left with 2, 1, 0 bits, so why should it be this way? Thanks for your reading. Please help me! Sérgio Agostinho wrote > On 21-01-2018 00:16, JamesRayen wrote: >> Hi, thanks for your kindly reply. I was not sure that if I pasted the >> source >> code there would be someone who would like to read. Here, I paste some >> source code, would you help me ? >> OctreeBase<LeafContainerT, BranchContainerT>::setTreeDepth >> (unsigned int >> depth_arg) >> { >> assert(depth_arg>0); >> // set octree depth >> octree_depth_ = depth_arg; >> // define depthMask_ by setting a single bit to 1 at bit position >> == >> tree depth >> depth_mask_ = (1 << (depth_arg - 1)); >> // define max. keys >> max_key_.x = max_key_.y = max_key_.z = (1 << depth_arg) - 1; >> } >> inline unsigned char >> getChildIdxWithDepthMask (unsigned int depthMask) const >> { >> return static_cast > <unsigned char> > (((!!(this->x & depthMask)) << 2) >> | ((!!(this->y & depthMask)) << >> 1) >> | (!!(this->z & depthMask))); >> } >> 'setTreeDepth' is a funtion in octree_base.hpp, and >> 'getChildIdxWithDepthMask' is a funtion in octree_key.h, I don't know why >> depth_mask_ is set to (1 << (depth_arg - 1)) and the reason of using >> depthMask to get child index. Also, I don't understand the reason of >> using >> double '!', and there are some fuctions using double '!' such as function >> 'getBranchBitPattern' in octree_base.h and function 'pushBranch' in >> octree_key.h. Could you help me with these questions? Thank you very >> much! >> > This one is kind of involved to explain and I'm not sure I fully > understand the entire process, but the answer to this question lies in > the way the unique ids are generated, so let me start with a simple > example. > > - Assume we're dealing with a 1D case, a spatial coordinate represented > by 'x', which ranges at most from the coordinates 0 to 1 > - Now lets add the requirement that octree (in this case binary tree > because it's 1D only) nodes need to have a unique key. I'm gonna refer > to these keys in binary format > > *Understanding the ID construction* > > As a first step let's assume the binary tree only has depth 1, which > implies two leaf nodes > > - leaf node id: 0 - represents the interval from [0, 0.5] > - leaf node id: 1 - represents the interval from [0.5, 1] > > If the depth was 2, we would have two branch nodes and 4 leaf nodes > (Disclaimer: the bit ordering might be reversed from the actual PCL > implementation but same principles apply) > > - branch node id: 0x - represents the interval from [0, 0.5] > - branch node id: 1x - represents the interval from [0.5, 1] > > - leaf node id: 00 - represents the interval from [0, 0.25] > - leaf node id: 01 - represents the interval from [0.25, 0.5] > - leaf node id: 10 - represents the interval from [0.5, 0.75] > - leaf node id: 11 - represents the interval from [0.75, 1] > > So on and so forth as you increase the depth... Extending this to 3D is > simply concatenating three of these binary ids for each dimension. > > *Max Key* > > If you look closely there's a close relationship between the tree depth > and the maximum number of bits which can be used as an id. > > - depth = 1 -> only one bit was used and enough to represent everything > - depth = 2 -> two bits were required to represent everything > > Now lets decompose the following expression assuming depth_arg is 2: (1 > << depth_arg) - 1 > > (1 << 2) = 100 > (1 << 2) - 1 = 011 > > 11 is exactly the maximum id which a lead node could have in our > previous example > > > This is all I have time to explain for now, but it should be enough to > help you decode the particular functions you posted. > > Cheers > > > _______________________________________________ > PCL-users@ > / http://pointclouds.org > http://pointclouds.org/mailman/listinfo/pcl-users > > > signature.asc (836 bytes) > <http://www.pcl-users.org/attachment/4045480/0/signature.asc> -- Sent from: http://www.pcl-users.org/ _______________________________________________ [hidden email] / http://pointclouds.org http://pointclouds.org/mailman/listinfo/pcl-users |
It feels like you lack the fundamental understanding of what a bitmask
is, therefore here's some additional reading https://stackoverflow.com/questions/10493411/what-is-bit-masking#10493604 We provide a depth mask the getIdWithDepthMask method in order to allow the user to specify which bit's of the node key/id he wants. Cheers _______________________________________________ [hidden email] / http://pointclouds.org http://pointclouds.org/mailman/listinfo/pcl-users signature.asc (836 bytes) Download Attachment |
Free forum by Nabble | Edit this page |