What's the meaning of depth_mask_ in octree_base.h?

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

What's the meaning of depth_mask_ in octree_base.h?

JamesRayen
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
Reply | Threaded
Open this post in threaded view
|

Re: What's the meaning of depth_mask_ in octree_base.h?

Fabien Rozar
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,
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


_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the meaning of depth_mask_ in octree_base.h?

JamesRayen
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 &lt;

> zc_mail163@

> &gt;:
>
>> 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
Reply | Threaded
Open this post in threaded view
|

Re: What's the meaning of depth_mask_ in octree_base.h?

Sérgio Agostinho



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


_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: What's the meaning of depth_mask_ in octree_base.h?

JamesRayen
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&lt;LeafContainerT, BranchContainerT&gt;::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)
> &lt;http://www.pcl-users.org/attachment/4045480/0/signature.asc&gt;





--
Sent from: http://www.pcl-users.org/
_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users
Reply | Threaded
Open this post in threaded view
|

Re: What's the meaning of depth_mask_ in octree_base.h?

Sérgio Agostinho
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