Incremental usage of kd-tree and octree

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

Incremental usage of kd-tree and octree

Daniels, Troy (US SSA)

I am looking at using PCL to store data in either a kd-tree or an octree.  My use case is (I believe) somewhat different than the normal usage for the software, and I am trying to figure out if PCL will work well with it.

 

Our data has two spatial dimensions and one time dimension, rather than three spatial dimensions.  We also will be alternately searching the tree and adding data to it.  Occasionally, a large block of data will be removed. 

 

Looking at pcl::KdTree, it seems that the only way to add data to it is to add the data to a PointCloud and then call KdTree::setInputCloud, which seems to process the entire cloud.  Attempting to add 5 points to a KdTree that contains 100,000 points in this manner will be very inefficient.  Does the KdTree notice if I add a point to the cloud and do an incremental update to its data structures?  I also do not see how to delete points from it.

 

pcl::OctreePointCloudSearch looks more encouraging.  addPointToCloud looks like it should allow me to add a single point and is presumably efficient in doing so.  I had found PointCloud::erase, which looked like it would also work for deleting data, but on closer examination, it seems that an OctreePointCloud* is not a PointCloud.  So I am wondering if there is a way to delete a single point from the tree.  (It seems that I can delete the voxel and then add the other data in the voxel, but that is inefficient.)

 

Am I attempting to use this in a way that it is not intended?  Or am I just not seeing the methods that I want to use?

 

Thanks,

Troy

 

 


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

Re: Incremental usage of kd-tree and octree

Radu B. Rusu
Administrator
Troy,

You’re definitely right that a kdtree structure is not what you should be looking for if you want to incrementally add data to it. The PCL octree structures are more appropriate for this kind of task.

Best,
Radu.

On Jan 7, 2014, at 10:57 AM, Daniels, Troy (US SSA) <[hidden email]> wrote:

> I am looking at using PCL to store data in either a kd-tree or an octree.  My use case is (I believe) somewhat different than the normal usage for the software, and I am trying to figure out if PCL will work well with it.
>  
> Our data has two spatial dimensions and one time dimension, rather than three spatial dimensions.  We also will be alternately searching the tree and adding data to it.  Occasionally, a large block of data will be removed.
>  
> Looking at pcl::KdTree, it seems that the only way to add data to it is to add the data to a PointCloud and then call KdTree::setInputCloud, which seems to process the entire cloud.  Attempting to add 5 points to a KdTree that contains 100,000 points in this manner will be very inefficient.  Does the KdTree notice if I add a point to the cloud and do an incremental update to its data structures?  I also do not see how to delete points from it.
>  
> pcl::OctreePointCloudSearch looks more encouraging.  addPointToCloud looks like it should allow me to add a single point and is presumably efficient in doing so.  I had found PointCloud::erase, which looked like it would also work for deleting data, but on closer examination, it seems that an OctreePointCloud* is not a PointCloud.  So I am wondering if there is a way to delete a single point from the tree.  (It seems that I can delete the voxel and then add the other data in the voxel, but that is inefficient.)
>  
> Am I attempting to use this in a way that it is not intended?  Or am I just not seeing the methods that I want to use?
>  
> Thanks,
> Troy
>  
>  
> _______________________________________________
> [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: Incremental usage of kd-tree and octree

Julius Kammerl-2
In reply to this post by Daniels, Troy (US SSA)
Hi,

> I am looking at using PCL to store data in either a kd-tree or an octree.
> My use case is (I believe) somewhat different than the normal usage for
> the software, and I am trying to figure out if PCL will work well with it.
>
> Our data has two spatial dimensions and one time dimension, rather than
> three spatial dimensions.  We also will be alternately searching the tree
> and adding data to it.  Occasionally, a large block of data will be
> removed.
>
> Looking at pcl::KdTree, it seems that the only way to add data to it is to
> add the data to a PointCloud and then call KdTree::setInputCloud, which
> seems to process the entire cloud.  Attempting to add 5 points to a KdTree
> that contains 100,000 points in this manner will be very inefficient.
> Does the KdTree notice if I add a point to the cloud and do an incremental
> update to its data structures?  I also do not see how to delete points
> from it.
>
> pcl::OctreePointCloudSearch looks more encouraging.  addPointToCloud looks
> like it should allow me to add a single point and is presumably efficient
> in doing so.  I had found PointCloud::erase, which looked like it would
> also work for deleting data, but on closer examination, it seems that an
> OctreePointCloud* is not a PointCloud.  So I am wondering if there is a
> way to delete a single point from the tree.  (It seems that I can delete
> the voxel and then add the other data in the voxel, but that is
> inefficient.)

I am not sure about the KdTree interface but the octree class allows you
to add single points. Deletion, however, is more tricky. You can only
delete voxels (which might contain more than one point). You could first
analyze the voxel container to check if more than one point exits and only
delete it as soon as it becomes empty.

Julius

>


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

Re: Incremental usage of kd-tree and octree

nizar sallem
In reply to this post by Daniels, Troy (US SSA)
As far as I can remember the FLANN implementation of KdTree doesn't
allow that. And also I am almost sure it would have a negative impact on
performances as it wants to balance data in the tree so whenever you add
a node you would have to rebuild the tree.

Cheers,
--
Nizar

On 07/01/2014 19:57, Daniels, Troy (US SSA) wrote:

> I am looking at using PCL to store data in either a kd-tree or an octree.  My use case is (I believe) somewhat different than the normal usage for the software, and I am trying to figure out if PCL will work well with it.
>
> Our data has two spatial dimensions and one time dimension, rather than three spatial dimensions.  We also will be alternately searching the tree and adding data to it.  Occasionally, a large block of data will be removed.
>
> Looking at pcl::KdTree, it seems that the only way to add data to it is to add the data to a PointCloud and then call KdTree::setInputCloud, which seems to process the entire cloud.  Attempting to add 5 points to a KdTree that contains 100,000 points in this manner will be very inefficient.  Does the KdTree notice if I add a point to the cloud and do an incremental update to its data structures?  I also do not see how to delete points from it.
>
> pcl::OctreePointCloudSearch looks more encouraging.  addPointToCloud looks like it should allow me to add a single point and is presumably efficient in doing so.  I had found PointCloud::erase, which looked like it would also work for deleting data, but on closer examination, it seems that an OctreePointCloud* is not a PointCloud.  So I am wondering if there is a way to delete a single point from the tree.  (It seems that I can delete the voxel and then add the other data in the voxel, but that is inefficient.)
>
> Am I attempting to use this in a way that it is not intended?  Or am I just not seeing the methods that I want to use?
>
> Thanks,
> Troy
>
>
>
>
>
> _______________________________________________
> [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: Incremental usage of kd-tree and octree

Daniels, Troy (US SSA)
Thanks for the advice.  Octree seems to be working well in my experimental code.

I am trying to figure out which class to use for PointT.  I want to include a pointer to external data, but I am not seeing something like that.  Can I just define a struct like

struct MyPoint {
  float x,y,z;
  MyClass *ptr;
};

and the create an OctreePointCloudSearch<MyPoint>?  It seems that I need to instantiate the class, but I'm not certain how to get that to work.  I experimented a bit with PCL_INSTANTIATE(OctreePointCloudSearch, MyPoint) but I was getting compiler errors.

Is there an existing class?  Can I easily use my own class?  If the latter, what are the requirements on it?

Troy



-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Nizar Sallem
Sent: Tuesday, January 07, 2014 2:46 PM
To: Point Cloud Library (PCL) users
Subject: Re: [PCL-users] Incremental usage of kd-tree and octree

As far as I can remember the FLANN implementation of KdTree doesn't allow that. And also I am almost sure it would have a negative impact on performances as it wants to balance data in the tree so whenever you add a node you would have to rebuild the tree.

Cheers,
--
Nizar

On 07/01/2014 19:57, Daniels, Troy (US SSA) wrote:

> I am looking at using PCL to store data in either a kd-tree or an octree.  My use case is (I believe) somewhat different than the normal usage for the software, and I am trying to figure out if PCL will work well with it.
>
> Our data has two spatial dimensions and one time dimension, rather than three spatial dimensions.  We also will be alternately searching the tree and adding data to it.  Occasionally, a large block of data will be removed.
>
> Looking at pcl::KdTree, it seems that the only way to add data to it is to add the data to a PointCloud and then call KdTree::setInputCloud, which seems to process the entire cloud.  Attempting to add 5 points to a KdTree that contains 100,000 points in this manner will be very inefficient.  Does the KdTree notice if I add a point to the cloud and do an incremental update to its data structures?  I also do not see how to delete points from it.
>
> pcl::OctreePointCloudSearch looks more encouraging.  addPointToCloud
> looks like it should allow me to add a single point and is presumably
> efficient in doing so.  I had found PointCloud::erase, which looked
> like it would also work for deleting data, but on closer examination,
> it seems that an OctreePointCloud* is not a PointCloud.  So I am
> wondering if there is a way to delete a single point from the tree.  
> (It seems that I can delete the voxel and then add the other data in
> the voxel, but that is inefficient.)
>
> Am I attempting to use this in a way that it is not intended?  Or am I just not seeing the methods that I want to use?
>
> Thanks,
> Troy
>
>
>
>
>
> _______________________________________________
> [hidden email] / http://pointclouds.org 
> http://pointclouds.org/mailman/listinfo/pcl-users
>
_______________________________________________
[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: Incremental usage of kd-tree and octree

nizar sallem
In reply to this post by Daniels, Troy (US SSA)
Nothing prevents you from doing so.
But could be more efficient to use pcl::PointXYZ as structure and keep
your objects pointers in a separate vector or cloud. It all depends on
what you are planning to do next.

Cheers,
--
Nizar

On 09/01/2014 00:27, Daniels, Troy (US SSA) wrote:

> Thanks for the advice.  Octree seems to be working well in my experimental code.
>
> I am trying to figure out which class to use for PointT.  I want to include a pointer to external data, but I am not seeing something like that.  Can I just define a struct like
>
> struct MyPoint {
>    float x,y,z;
>    MyClass *ptr;
> };
>
> and the create an OctreePointCloudSearch<MyPoint>?  It seems that I need to instantiate the class, but I'm not certain how to get that to work.  I experimented a bit with PCL_INSTANTIATE(OctreePointCloudSearch, MyPoint) but I was getting compiler errors.
>
> Is there an existing class?  Can I easily use my own class?  If the latter, what are the requirements on it?
>
> Troy
>
>
>
> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]] On Behalf Of Nizar Sallem
> Sent: Tuesday, January 07, 2014 2:46 PM
> To: Point Cloud Library (PCL) users
> Subject: Re: [PCL-users] Incremental usage of kd-tree and octree
>
> As far as I can remember the FLANN implementation of KdTree doesn't allow that. And also I am almost sure it would have a negative impact on performances as it wants to balance data in the tree so whenever you add a node you would have to rebuild the tree.
>
> Cheers,
> --
> Nizar
>
> On 07/01/2014 19:57, Daniels, Troy (US SSA) wrote:
>> I am looking at using PCL to store data in either a kd-tree or an octree.  My use case is (I believe) somewhat different than the normal usage for the software, and I am trying to figure out if PCL will work well with it.
>>
>> Our data has two spatial dimensions and one time dimension, rather than three spatial dimensions.  We also will be alternately searching the tree and adding data to it.  Occasionally, a large block of data will be removed.
>>
>> Looking at pcl::KdTree, it seems that the only way to add data to it is to add the data to a PointCloud and then call KdTree::setInputCloud, which seems to process the entire cloud.  Attempting to add 5 points to a KdTree that contains 100,000 points in this manner will be very inefficient.  Does the KdTree notice if I add a point to the cloud and do an incremental update to its data structures?  I also do not see how to delete points from it.
>>
>> pcl::OctreePointCloudSearch looks more encouraging.  addPointToCloud
>> looks like it should allow me to add a single point and is presumably
>> efficient in doing so.  I had found PointCloud::erase, which looked
>> like it would also work for deleting data, but on closer examination,
>> it seems that an OctreePointCloud* is not a PointCloud.  So I am
>> wondering if there is a way to delete a single point from the tree.
>> (It seems that I can delete the voxel and then add the other data in
>> the voxel, but that is inefficient.)
>>
>> Am I attempting to use this in a way that it is not intended?  Or am I just not seeing the methods that I want to use?
>>
>> Thanks,
>> Troy
>>
>>
>>
>>
>>
>> _______________________________________________
>> [hidden email] / http://pointclouds.org
>> http://pointclouds.org/mailman/listinfo/pcl-users
>>
> _______________________________________________
> [hidden email] / http://pointclouds.org http://pointclouds.org/mailman/listinfo/pcl-users
> _______________________________________________
> [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: Incremental usage of kd-tree and octree

Daniels, Troy (US SSA)
I'm missing something here.  PointXYZ just holds the (x,y,z) values.  Once I do the search and find the PointXYZ object, it does not have a pointer or anything to get back to my object.  Are you suggesting that I have a vector, where item N in the cloud has its data as item N in the vector?  That seems like it could easily fall out of sync as I add and delete points in the cloud.

Troy

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Nizar Sallem
Sent: Thursday, January 09, 2014 5:09 AM
To: Point Cloud Library (PCL) users
Subject: Re: [PCL-users] Incremental usage of kd-tree and octree

Nothing prevents you from doing so.
But could be more efficient to use pcl::PointXYZ as structure and keep your objects pointers in a separate vector or cloud. It all depends on what you are planning to do next.

Cheers,
--
Nizar

On 09/01/2014 00:27, Daniels, Troy (US SSA) wrote:

> Thanks for the advice.  Octree seems to be working well in my experimental code.
>
> I am trying to figure out which class to use for PointT.  I want to
> include a pointer to external data, but I am not seeing something like
> that.  Can I just define a struct like
>
> struct MyPoint {
>    float x,y,z;
>    MyClass *ptr;
> };
>
> and the create an OctreePointCloudSearch<MyPoint>?  It seems that I need to instantiate the class, but I'm not certain how to get that to work.  I experimented a bit with PCL_INSTANTIATE(OctreePointCloudSearch, MyPoint) but I was getting compiler errors.
>
> Is there an existing class?  Can I easily use my own class?  If the latter, what are the requirements on it?
>
> Troy
>
>
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of Nizar Sallem
> Sent: Tuesday, January 07, 2014 2:46 PM
> To: Point Cloud Library (PCL) users
> Subject: Re: [PCL-users] Incremental usage of kd-tree and octree
>
> As far as I can remember the FLANN implementation of KdTree doesn't allow that. And also I am almost sure it would have a negative impact on performances as it wants to balance data in the tree so whenever you add a node you would have to rebuild the tree.
>
> Cheers,
> --
> Nizar
>
> On 07/01/2014 19:57, Daniels, Troy (US SSA) wrote:
>> I am looking at using PCL to store data in either a kd-tree or an octree.  My use case is (I believe) somewhat different than the normal usage for the software, and I am trying to figure out if PCL will work well with it.
>>
>> Our data has two spatial dimensions and one time dimension, rather than three spatial dimensions.  We also will be alternately searching the tree and adding data to it.  Occasionally, a large block of data will be removed.
>>
>> Looking at pcl::KdTree, it seems that the only way to add data to it is to add the data to a PointCloud and then call KdTree::setInputCloud, which seems to process the entire cloud.  Attempting to add 5 points to a KdTree that contains 100,000 points in this manner will be very inefficient.  Does the KdTree notice if I add a point to the cloud and do an incremental update to its data structures?  I also do not see how to delete points from it.
>>
>> pcl::OctreePointCloudSearch looks more encouraging.  addPointToCloud
>> looks like it should allow me to add a single point and is presumably
>> efficient in doing so.  I had found PointCloud::erase, which looked
>> like it would also work for deleting data, but on closer examination,
>> it seems that an OctreePointCloud* is not a PointCloud.  So I am
>> wondering if there is a way to delete a single point from the tree.
>> (It seems that I can delete the voxel and then add the other data in
>> the voxel, but that is inefficient.)
>>
>> Am I attempting to use this in a way that it is not intended?  Or am I just not seeing the methods that I want to use?
>>
>> Thanks,
>> Troy
>>
>>
>>
>>
>>
>> _______________________________________________
>> [hidden email] / http://pointclouds.org 
>> http://pointclouds.org/mailman/listinfo/pcl-users
>>
> _______________________________________________
> [hidden email] / http://pointclouds.org 
> http://pointclouds.org/mailman/listinfo/pcl-users
> _______________________________________________
> [hidden email] / http://pointclouds.org 
> http://pointclouds.org/mailman/listinfo/pcl-users
>
_______________________________________________
[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: Incremental usage of kd-tree and octree

nizar sallem
In reply to this post by Daniels, Troy (US SSA)
If you keep both vectors sinked you should be able to prevent data loss.
Anyway as I said before it depends on what your aim is.

Cheers,
--
Nizar

On 09/01/2014 16:25, Daniels, Troy (US SSA) wrote:

> I'm missing something here.  PointXYZ just holds the (x,y,z) values.  Once I do the search and find the PointXYZ object, it does not have a pointer or anything to get back to my object.  Are you suggesting that I have a vector, where item N in the cloud has its data as item N in the vector?  That seems like it could easily fall out of sync as I add and delete points in the cloud.
>
> Troy
>
> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]] On Behalf Of Nizar Sallem
> Sent: Thursday, January 09, 2014 5:09 AM
> To: Point Cloud Library (PCL) users
> Subject: Re: [PCL-users] Incremental usage of kd-tree and octree
>
> Nothing prevents you from doing so.
> But could be more efficient to use pcl::PointXYZ as structure and keep your objects pointers in a separate vector or cloud. It all depends on what you are planning to do next.
>
> Cheers,
> --
> Nizar
>
> On 09/01/2014 00:27, Daniels, Troy (US SSA) wrote:
>> Thanks for the advice.  Octree seems to be working well in my experimental code.
>>
>> I am trying to figure out which class to use for PointT.  I want to
>> include a pointer to external data, but I am not seeing something like
>> that.  Can I just define a struct like
>>
>> struct MyPoint {
>>     float x,y,z;
>>     MyClass *ptr;
>> };
>>
>> and the create an OctreePointCloudSearch<MyPoint>?  It seems that I need to instantiate the class, but I'm not certain how to get that to work.  I experimented a bit with PCL_INSTANTIATE(OctreePointCloudSearch, MyPoint) but I was getting compiler errors.
>>
>> Is there an existing class?  Can I easily use my own class?  If the latter, what are the requirements on it?
>>
>> Troy
>>
>>
>>
>> -----Original Message-----
>> From: [hidden email]
>> [mailto:[hidden email]] On Behalf Of Nizar Sallem
>> Sent: Tuesday, January 07, 2014 2:46 PM
>> To: Point Cloud Library (PCL) users
>> Subject: Re: [PCL-users] Incremental usage of kd-tree and octree
>>
>> As far as I can remember the FLANN implementation of KdTree doesn't allow that. And also I am almost sure it would have a negative impact on performances as it wants to balance data in the tree so whenever you add a node you would have to rebuild the tree.
>>
>> Cheers,
>> --
>> Nizar
>>
>> On 07/01/2014 19:57, Daniels, Troy (US SSA) wrote:
>>> I am looking at using PCL to store data in either a kd-tree or an octree.  My use case is (I believe) somewhat different than the normal usage for the software, and I am trying to figure out if PCL will work well with it.
>>>
>>> Our data has two spatial dimensions and one time dimension, rather than three spatial dimensions.  We also will be alternately searching the tree and adding data to it.  Occasionally, a large block of data will be removed.
>>>
>>> Looking at pcl::KdTree, it seems that the only way to add data to it is to add the data to a PointCloud and then call KdTree::setInputCloud, which seems to process the entire cloud.  Attempting to add 5 points to a KdTree that contains 100,000 points in this manner will be very inefficient.  Does the KdTree notice if I add a point to the cloud and do an incremental update to its data structures?  I also do not see how to delete points from it.
>>>
>>> pcl::OctreePointCloudSearch looks more encouraging.  addPointToCloud
>>> looks like it should allow me to add a single point and is presumably
>>> efficient in doing so.  I had found PointCloud::erase, which looked
>>> like it would also work for deleting data, but on closer examination,
>>> it seems that an OctreePointCloud* is not a PointCloud.  So I am
>>> wondering if there is a way to delete a single point from the tree.
>>> (It seems that I can delete the voxel and then add the other data in
>>> the voxel, but that is inefficient.)
>>>
>>> Am I attempting to use this in a way that it is not intended?  Or am I just not seeing the methods that I want to use?
>>>
>>> Thanks,
>>> Troy
>>>
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> [hidden email] / http://pointclouds.org
>>> http://pointclouds.org/mailman/listinfo/pcl-users
>>>
>> _______________________________________________
>> [hidden email] / http://pointclouds.org
>> http://pointclouds.org/mailman/listinfo/pcl-users
>> _______________________________________________
>> [hidden email] / http://pointclouds.org
>> http://pointclouds.org/mailman/listinfo/pcl-users
>>
> _______________________________________________
> [hidden email] / http://pointclouds.org http://pointclouds.org/mailman/listinfo/pcl-users
> _______________________________________________
> [hidden email] / http://pointclouds.org
> http://pointclouds.org/mailman/listinfo/pcl-users
>
_______________________________________________
[hidden email] / http://pointclouds.org
http://pointclouds.org/mailman/listinfo/pcl-users