@taketwo You have write permission if you want to add commits.

@jpapon Thanks, then let's keep the work in your branch.

I will need some time to prepare my update for AveragePoint. Apart from that, I have several comments:

1. OctreeAdjacencyContainer extends OctreeContainerBase, however does not override getSize(). The default version inherited from OctreeContainerBase always returns zero. I have no clue who/where/how uses this function (if at all), but I think it is a good idea to return the real number of accumulated points.
2. We'll need to update documentation comments in OctreeAdjacencyContainer.
3. Why do you prefer to specialize addPoint()/computeData() for your VoxelData rather than doing accumulation inside of it (like AveragePoint does)?

I have a few new thoughts about our containers:

a) OctreePointCloudVoxelCentroidContainer should have two template parameters:

1. Point type - this is obvious
2. Accumulation policy - this will allow the user to inject his custom behavior for addPoint() and getCentroid(). The default one will be AveragePoint.

b) OctreeAdjacencyContainer is in fact an extension of OctreePointCloudVoxelCentroidContainer, which simply adds neighborhood stuff. Consequently, it could inherit from voxel centroid container and have exactly the same two template parameters.

There is a problem though: supervoxel clustering is designed in a way that also requires us to be able to store some additional piece of data in every leaf. We can account for that by adding a third template parameter, DataT.

template<typename PointT, typename DataT, typename CentroidPolicy = AveragePoint<PointT> >
class OctreeAdjacencyContainer : public OctreePointCloudVoxelCentroidContainer<PointT, CentroidPolicy>

Note the conceptual difference with the DataT parameter that the adjacency container has at the moment. We sort of split into two parts: the one responsible for averaging, the other is for storing "cookies". These are two different axes of variability and it is logical to keep them separate. I bet you already had this idea while thinking about how to make SupervoxelClustering::VoxelData benefit from AveragePoint.

OctreeAdjacencyContainer extends OctreeContainerBase, however does not override getSize(). The default version inherited from OctreeContainerBase always returns zero. I have no clue who/where/how uses this function (if at all), but I think it is a good idea to return the real number of accumulated points.

I don't think it's actually used anywhere. It's basically useless because even OctreePointCloudVoxelCentroidContainer doesn't override it. It also doesn't stick to STL container style.

Why do you prefer to specialize addPoint()/computeData() for your VoxelData rather than doing accumulation inside of it (like AveragePoint does)?

I don't, I just didn't have time to modify it yet.

OctreePointCloudVoxelCentroidContainer should have two template parameters:

I like this, except I find it redundant to call it a centroid container and then have an averaging accumulation policy. I'm just wondering if we can make it just OctreePointCloudVoxelContainer with different accumulation policies. This might be changing too much existing code though.

OctreeAdjacencyContainer is in fact an extension of OctreePointCloudVoxelCentroidContainer, which simply adds neighborhood stuff.

I think it should just extend the VoxelContainer, since one might not want to average, but just use occupancy.

There is a problem though: supervoxel clustering is designed in a way that also requires us to be able to store some additional piece of data in every leaf. We can account for that by adding a third template parameter, DataT.

I think this might be starting to a get a bit over-engineered, there should be a way to simplify it.

The way I'm using DataT is exactly that, a way of storing extra data in the leaves, and you're right it makes sense to keep it completely separate from the averaging behavior. The reason I used the DataT at all is actually historical- if you look back at the original OctreeContainerBase it was designed around a DataT template with getter and setter functions. When I was making the Adjacency Container originally, I had to extend this base class in order to use the OctreeBase, so I didn't have a choice - the PointT and DataT behavior had to be mixed. Then at some point (1d38457) @jkammerl revised all the base classes, and my stuff had to be adapted to work with it.

We really need to get @jkammerl to give some input on this - he may not like what we're talking about doing to the containers at all.

Thanks guys for working on this! I'll look at this over the weekend.. Cheers, Julius

I think it should just extend the VoxelContainer, since one might not want to average, but just use occupancy.

That's reasonable. But how do you see the mechanism for injecting this behavior (occupancy vs. averaging)?

I think this might be starting to a get a bit over-engineered.

I also got this feeling. Let's first gather what are the problems we want to address with our re-design. From my viewpoint, the major problem is that leaf containers mix three orthogonal behavior+data at the same time:

1. Data and functions for octree book-keeping (induced by the octree type, e.g. neighborhood sets in adjacency octree);
2. Accumulation of points that fall into the container (density, xyz centroid, single point, averaging, etc.);
3. Additional data that the user might want to save in each leaf for his particular application ("cookies").

If you discovered a bug in "computeNDCentroid", please file a bug report or even better a fix :)

Oh no, it behaves exactly as it should, I just mentioned that for some field types (like RGB) computation of arithmetic mean is pointless.

Would it make more sense to have indices stored in a third "cookie" or "DataT" template parameter?
For voxel centroids that store indices of the points they contain:
VoxelContainer <PointT, IndicesVectorT, AveragingAccumulator>

I think that storing of indices belongs to the second category (see my previous message). Ocree container either stores indices vector, or single point, or computes average, or whatever.

Also, I think that "cookie" (third category) should be left for end-user's exclusive usage.

Thanks @jpapon! I like the suggested interface a lot:

VoxelContainer <PointT, IndicesVectorT, AveragingAccumulator>

This would clearly separate the datatype, storage and functions.

OctreeContainerEmpty and OctreeContainerBase are essentially the same. Is there really a need for a separate abstract base class?

The octree relies on the container to have methods like addPointIndex, getPointIndex, etc. That's why I added the OctreeContainerBase class. I agree that the OctreeContainerEmpty class could be simplified. This problem might still exist in your proposed scheme. How to you define the standard interface of the AveragingAccumulator?

Would it make more sense to have indices stored in a third "cookie" or "DataT" template parameter?

How to you make sure that this DataT parameter has the corresponding getter and setter methods implemented (without a using a base class)?

Thanks guys!

The octree relies on the container to have methods like addPointIndex, getPointIndex, etc.

Yes, this is the problem I'm running into atm. I've defined the base class as:

template<typename PointT, template<class> class AccumulatorPolicy = AveragingAccumulator, typename DataT = EmptyDataT > class OctreeLeafContainer : public AccumulatorPolicy<PointT>

This works fine for most cases, and most of the existing Container types can be replaced with typedefs, ie
typedef OctreeLeafContainer<int, VectorAccumulator> OctreeContainerPointIndices;
typedef OctreeLeafContainer<int, NullAccumulator> OctreeContainerPointIndex;
or template alias':
template <typename PointT> using OctreePointCloudVoxelCentroidContainer = OctreeLeafContainer<PointT, AveragingAccumulator>;

While these typedefs would be nice, lots of existing code uses functions like getPointIndicesVector and getCentroid, which are specific to the individual container types, so I just made some very simple wrapper classes which map these functions to the generic insert and return behavior.

This is all fine, but currently I'm stuck on the internal use of addPointIdx(int) in OctreePointCloud. I need to figure out a way to make this work using one interface, even though some containers store indices and others store the Points.

This is all fine, but currently I'm stuck on the internal use of addPointIdx(int) in OctreePointCloud. I need to figure out a way to make this work using one interface, even though some containers store indices and others store the Points.

What about

void addPoint (int index, const PointT& point);

Octree passes both index and point, and the container decides what it needs to store.

Yeah... why not indeed.

This is going to need some serious checking to make sure it doesn't break anything. I'll push it tomorrow, I'd appreciate your help in reviewing and debugging ;)

@jpapon For sure, I'll assist you with this. Just don't waste too much time updating all the existing containers and octree types. IMHO we haven't arrived at the best possible design yet...

Thanks guys for your great suggestions! It would be awesome to make the containers more flexible to maintain point data and point indices equally well. Please let me know if there is something I can help you with.

Octree passes both index and point, and the container decides what it needs to store.

@taketwo So I remembered why this doesn't help: I was trying to define the interface so you could do this for the point indices containers:
typedef OctreeLeafContainer<int, VectorAccumulator> OctreeContainerPointIndices;

This makes sense, since the point indices leaves don't need to know about the point type, they just need to store indices. Unfortunately, since they need to have a common interface with leaf containers that store points, you either need to pass both (which means passing indices to containers which do nothing with them), or do what @jkammerl did, which is have the trees implement their own addPointIdx function which passes points instead of indices to the container if the container they use should store points rather than indices. That is, unless there's some clever trick that I don't know about.

typedef OctreeLeafContainer<int, VectorAccumulator> OctreeContainerPointIndices;
This makes sense, since the point indices leaves don't need to know about the point type, they just need to store indices.

Still, there is no harm in actually letting them know about point type. Anyway this int template argument looks weird, since indices are always integers.

That is, unless there's some clever trick that I don't know about.

Oh yes, there is a way to resolve this with some meta-programming. For each accumulator we define traits that indicate whether it needs points, indices, or both. Then at compilation time octree checks these traits and selects appropriate addIndex() function to be used at run-time. But honestly, I do not see any benefit in going through all of this instead of just passing both to every container.

@taketwo I've pushed the changes... let me know what you think. It compiles, but right now some of the unit tests fail. I'm not sure why, I'll have to look into it some more. I tried to keep all existing interfaces.

SupervoxelClustering compiles, but it's completely broken right now because it's not using the Accumulator to average the points, it's still using the VoxelData parameter.

Hmm clang 3.5.0 refuses to compile with multiple errors like

octree_container.h:253:40: error: template argument for template template parameter must be a class template
        using OctreeLeafContainer<int, IndexVectorAccumulator>::getPointIndices;

In fact, the same holds for clang 3.3 that we have on Travis.

I do not quite understand how gcc handles these constructs, because indeed IndexVectorAccumulator is not a valid class name until you specify its template argument like so:

using OctreeLeafContainer<int, IndexVectorAccumulator<PointT>>::getPointIndices;

Looking at the code it seems like the idea with passing both index and point was not that good. Also I do not like that OctreeLeafContainer derives from the accumulator policy. Finally, all these getSize(), size() freak me out because they have no "general" meaning. Adjacency container would return the number of neighbors as its size, whereas some "normal" container would output the number of points accumulated.

Thinking more about all of these I am coming back to the three separate "axes" that I noted before:

1. Data and functions for octree book-keeping (induced by the octree type, e.g. neighborhood sets in adjacency octree);
2. Accumulation of points that fall into the container (density, xyz centroid, single point, averaging, etc.);
3. Additional data that the user might want to save in each leaf for his particular application ("cookies").

Now I am even more convinced it makes sense to turn these into three template parameters, leading to the following definition (observe how it does not depend on PointT):

template <typename OctreeDataT = EmptyData,
          typename LeafDataT = NullAccumulator,
          typename UserDataT = EmptyData>
class OctreeLeafContainer
{
  // almost nothing, just store instances of all datas
  LeafDataT leaf_data_;
  ...
  // and provide accessors, reset, and comparison
  // plus all the deprecated functions
}

For example, here is how OctreeContainerPointIndex specialization would look like:

template <typename OctreeDataT = EmptyData,
          typename UserDataT = EmptyData>
class OctreeContainerPointIndex
  : public OctreeLeafContainer<OctreeDataT, LastAccumulator, UserDataT>
{
  // function to insert a point
  // this container only stores an index
  void insert (int index_arg)
  {
    lead_data_.insert (index_arg);
  }
}

Observe how it allows OctreeDataT template parameter. If someone wants adjacency octree with point index accumulation he will just need to substitute default EmptyData for OctreeAdjacencyData (that will contain neighbors and stuff).

What do you think? I have a feeling that this will lead to a much more flexible and simple code. Do you have any ideas what problems this would give us? If not then I can sketch the proposed changes.

Finally, all these getSize(), size() freak me out because they have no "general" meaning.

I agree, but unfortunately I'm not sure we can really eliminate them, since it would break existing code. The frustrating thing is often they don't actually do anything - they just return 0. The same is true of getPointIndices - it's called, but the result isn't actually used for anything.

The above proposed changes are going to require some trait checking in OctreePointCloud to decide whether to insert the index or the point. I guess we need a check like isPointType.

Also, I don't see how you're going to accumulate PointT if you don't template the Accumulator on it (or int for index) - doesn't the policy need to be a template template parameter?

Also I do not like that OctreeLeafContainer derives from the accumulator policy.

This was only done to simplify syntax.

If someone wants adjacency octree with point index accumulation he will just need to substitute default EmptyData for OctreeAdjacencyData (that will contain neighbors and stuff).

Also, I'm not exactly sure how this would work. Do you want to store an OctreeDataT member in the OctreeLeafContainer? As far as I can tell that would mean basically removing OctreePointCloudAdjacency, and moving the neighbor calculation behavior into the OctreeDataT parameter. Was that your intention?

I agree, but unfortunately I'm not sure we can really eliminate them, since it would break existing code. The frustrating thing is often they don't actually do anything - they just return 0.

Then let's clearly mark them all as deprecated and consistently return 0 or whatever (that is, do not return anything sensible even when it is possible).

The above proposed changes are going to require some trait checking in OctreePointCloud to decide whether to insert the index or the point. I guess we need a check like isPointType.

Yep, I have an idea that is pretty close. We may have an adapter traits structure AccumulatorTraits with specializations for different accumulator types. It will provide a universal insert function to be used from OctreePointCloud. Something like this:

template <typename AccumulatorT>
struct AccumulatorTraits
{
  // generic version, useless unless specialized
};

template<>
structure AccumulatorTraits<LastAccumulator>
{
  // specialization for LastAccumulator, which does not care/know about
  // point types, thus insert function is templated on point type
  template <typename PointT>
  void insert (AccumulatorT& acc, int idx, const PointT& point) const
  {
    acc.insert (idx);
  }
}

template <typename PointT>
struct AccumulatorTraits<AveragingAccumulator<PointT> >
{
  // specialization for AveragingAccumulator<PointT>
  static void insert (AveragingAccumulator<PointT>& acc, int idx, PointT& point)
  {
    acc.insert (point);
  }
};

// Usage as follows:
// Some accumulator types
typedef LastAccumulator A1;
typedef AveragingAccumulator<pcl::PointXYZ> A2;
A1 a1;
A2 a2;
// Now we insert points in them using uniform interface
AccumulatorTraits<A1>::insert (a1, 1, point);
AccumulatorTraits<A2>::insert (a2, 1, point);

Also, I don't see how you're going to accumulate PointT if you don't template the Accumulator on it (or int for index) - doesn't the policy need to be a template template parameter?

No no, I will, but when it comes to the definition of OctreeLeafContainer it does not have to know whether accumulator type is itself templated or not.

Also, I'm not exactly sure how this would work. Do you want to store an OctreeDataT member in the OctreeLeafContainer?

Yes, along with LeafDataT (accumulator) and UserDataT (user cookie).

As far as I can tell that would mean basically removing OctreePointCloudAdjacency, and moving the neighbor calculation behavior into the OctreeDataT parameter. Was that your intention?

No, the neighbor calculation behavior stays where it is, i.e. in OctreePointCloudAdjacency. OctreeDataT will only contain data which is needed to support that calculation. That is, NeighborSetT neighbors_.

Anything else? I am quite happy I have been able to answer your questions so far, that is a good indication that the conceived design actually fits together :)

// specialization for LastAccumulator, which does not care/know about point types, thus insert function is templated on point type

Wouldn't this mean you need a separate Accumulator type for storing Last Index vs Last Point? This is fine I guess, it just means you need a LastIndexAccumulator and LastPointAccumulator.

Also, what are the access functions? Do you have separate index and value getters or is that templated too?

Maybe it would be easier to get on the PCL IRC channel.

Wouldn't this mean you need a separate Accumulator type for storing Last Index vs Last Point? This is fine I guess, it just means you need a LastIndexAccumulator and LastPointAccumulator.

This was intended as an example only to show how accumulators that don't care about points look like. Perhaps I should better chose IndexVectorAccumulator for that purpose. Actually LastAccumulator should be templated on point type and store last point instead of last index. Or, as you said, we may have two versions.

Also, what are the access functions? Do you have separate index and value getters or is that templated too?

These are functions that the octree itself could use to reach these different datas inside leaf containers. For example, somewhere deep inside some octree function we may find:

LeafContainerT* container = this->createLeaf (key);
container->getLeafData().insert (index_arg, point);

or in adjacency octree

LeafContainerT *neighbor = this->findLeaf (neighbor_key);
if (neighbor)
{
  leaf_container->getOctreeData ().addNeighbor (neighbor);
}

Of course, we may just make these fields public.

Maybe it would be easier to get on the PCL IRC channel.

Sure, we may do this, though I will be available only in the late evening.

Alright, well go ahead then, I'm interested to see how much nicer this version comes out =p

I have pushed some changes on top of your commits. (I did not push to your repo in order not to interfere with your work. So you could access it in the very same branch, but on my fork here. Also, you could cherry-pick this commit to your fork if you like).

At the moment this is compilable (at least with make test_octree), and the tests pass, though I suspect the actual test coverage is very poor.

My idea with having OctreeDataT as a template parameter needs more thinking. At least I was not able to plug everything together so that adjacency octree work (so it is commented out in 'octree_test.cpp').

Summarizing, I am mostly satisfied with the current state, but I need more time to think through a clean way to mix "adjacency" behavior with different "accumulator" behaviors.

Great discussion guys! Thanks a lot for working on this. Traits in general are a powerful tool, but in this case they might be just used to distinguish between the different applications and not addressing the need for a common interface.

Maybe we should not add any logic to the containers and keep the logic within the octree pointcloud classes. Distributing the logic across multiple entities that all relate to the same functionality does not sound right and this leads to all the special cases we are currently facing. What do you guys thinks of adding/modifying the virtual methods in the octreepointcloud class to interface with the containers in a more comprehensive way. This way the octree could be easily specialized, logic would stay within the OctreePointcloudClass and data stays within the containers?

Maybe we should not add any logic to the containers and keep the logic within the octree pointcloud classes.

I totally agree. In fact, this how the things are shaping out now. Just have a look at 'octree_container.h', there is no real business logic involved.

What do you guys thinks of adding/modifying the virtual methods in the octreepointcloud class to interface with the containers in a more comprehensive way.

As far as I understand it, the interaction between OctreePointCloud and containers basically boils down to point insertion.

Ok, so I merged @taketwo 's changes, and had to make some little tweaks in order to get it to compile, mainly removing the template parameters from all the previously existing container types (e.g. OctreeContainerPointIndex) and changing them into typedefs. I don't know how the templated version compiled for you @taketwo, maybe clang doesn't require the blank template arguments <> in some cases? gcc couldn't handle them missing in octree_inst.cpp for me.

Anyway, I think it's better to leave them untemplated because it won't break existing code and it allows us to avoid the ugly wrapper classes and just use typedefs.

Now as for the OctreeAdjacency problems... it is kind of troubling, since the whole idea was that leaves point to eachother, and I don't see how you can do that if the OctreeDataT is a template parameter of the leaf.

Hmm you are right regarding the octree tutorial. Though it does not mention the "centroid" octree at all.

@jkammerl @jspricke @rbrusu I think we are done with this PR. There are a lot of commits and changes here, some of them first introduce stuff and then remove it, so the commit history is not too clean. Unfortunately, I see no way how it could be rectified other than squashing everything into one big commit. I feel this will be extremely hard to review, but perhaps you suggest something we can do to simplify the process?

Thanks for your hard work! This week, I am quite busy but I'll reserve some time next weekend. I am not sure how to proceed with this huge commit. How much of the new/revised functionality is covered by unit tests in your opinion?

@jkammerl This pull request is largely concerned with a change in how octree interacts with its leaves and does not introduce new functionality or touch existing. The existing tests do check that insertion of points / retrieval of data still works for all kinds of octrees. The only new functionality is the improved centroid container. However, it relies on the CentroidPoint class, which is covered with unit tests pretty well. The rest of this pull request is about changes (simplifications) in adjacency octree, container, and supervoxel clustering. I do not think that these have a good coverage in terms of unit tests, however Jeremie is the original author, so I assume he knows what he was doing :)

@jpapon Do you think we can get rid of this now?

I looked over your huge commit :) Thanks for all the efforts and time!
Regarding the template traits, to be honest, I have a few concerns. Particularly, they add a lot of complexity to the code and will make debugging harder. Boost magic is great, but I would prefer to use it as little magic as possible. It is still not clear to me why we absolutely need them. I am aware that this has been already discussed intensively, but please help me to understand this again.

Rather than specializing the insert method in every container with this relatively complex wrappers:

    /** LeafContainerTraits specialization for OctreeIndicesContainer. */
    template<typename LeafContainerT>
    struct LeafContainerTraits<LeafContainerT,
                               typename boost::enable_if<
                                 boost::is_base_of<
                                   OctreeIndicesContainer<typename LeafContainerT::data_type>
                                 , LeafContainerT
                                 >
                               >::type>
    {
      template <typename PointT>
      static void insert (LeafContainerT& container, int idx, const PointT&)
      {
        container.insertPointIndex (idx);
      }
    };

.. why don't we design a single insert method that takes all information into account, that could be needed within the container. Something like this:
void insert (LeafContainerT&, int, const PointT&, UserDataT* optional_user_data = nullptr)

Thanks,
Julius

Hi Julius, thanks for reviewing.

why don't we design a single insert method that takes all information into account, that could be needed within the container

That is exactly the idea with which we started 3 months ago :)

The problem is that this would require each and every leaf container (even EmptyContainer) to be templated on the point type, though only one of them actually needs points (the centroid container).

Ok, makes sense. And what if we consider the PointT to be user data in the centroid container. This would result in a insert method like this:

void insert (LeafContainerT& container, int index, UserDataT* optional_user_data = nullptr)

Not possible, UserDataT was designed specifically to allow the user to store some application-dependent piece of data in addition to points/indices. For example, SupervoxelClustering uses it to store some distances and owner pointers (see VoxelData struct).

(By the way, seems like Jeremie forgot to update the documentation comment for VoxelData.)

Wouldn't storing the PointT for the purpose of calculating the centroid be also quite application dependent (for the OctreePointcloudCentroid class)? I don't see a general difference here.

Calculation of centroid point in octree leaves is a common operation, that is why we have it among the "standard" containers. UserDataT provides a facility to extend it (specialize for a concrete application at hand) easily, without the need for creating a new class.

This sounds to me more like a semantic question what is considered to be a common operation. I see the octree as a data structure that stores indices within each node and additional data could be considered as UserDataT. Such UserDataT element could be also a PointT if needed.

Anyways, if only considering the PointT to be UserDataT in the centroid calculation helps us to avoid all the template specialization, I think we would gain a lot in terms of code readability, and reduced code complexity.

I see the octree as a data structure that stores indices within each node and additional data could be considered as UserDataT. Such UserDataT element could be also a PointT if needed.

I thought there was a distinction to be made between the UserDataT and the internal storage of the LeafContainerT. The LeafContainer's data is set internally by the Octree, whether that be indices, a centroid, or neighbor information. These get set when addPointsFromInputCloud is called and the Octree is built. UserDataT is intended to be used for post processing by the user - say, for maintaining labels when using the tree for a segmentation algorithm.

Anyways, if only considering the PointT to be UserDataT in the centroid calculation helps us to avoid all the template specialization, I think we would gain a lot in terms of code readability, and reduced code complexity.

But wouldn't that mean modifying the UserDataT element from inside the Octree? That isn't the point of it at all.

If we want to avoid the boost magic, then maybe the simplest solution would be to go back to what was there previously - give the centroid octree class its own virtual 'addPointIdx' implementation. I think the only reason we changed from doing it that way was that it means any Octree class which works with points needs to reimplement the 'addPointIdx' function.

But wouldn't that mean modifying the UserDataT element from inside the Octree? That isn't the point of it at all.

The octree should not modify any UserDataT from within the Octree. All it does is looking up OctreeNode containers which are passed to the application/super class. In my opinion the containers should not contain any logic. Even averaging points should ideally happen outside of the container (which is not the case in OctreePointcloudCentroid right now). This would be the cleanest design, I think. The boost magic enables the containers to become smart by design. That's my biggest concern. To me the PR adds more complexity to the octree due to the boost magic happening here without making the design much cleaner.

Even averaging points should ideally happen outside of the container (which is not the case in OctreePointcloudCentroid right now). This would be the cleanest design, I think.

This was never the case. The only way I see this as being possible would be to use the indices vector octree and then only compute centroids when the user requests it. This might give a simpler design, but it would be slower (worst case a non-reserved push_back for every point in the cloud) and would generally use more memory.

From what I gather, @jkammerl you prefer to keep points out of the octree: octrees should only store, at the most, indices into a cloud. Is there a particular reason for that?

Yes, it is important in my opinion that each leaf should store as little information as possible. Storing points instead of indices would not only significantly increase the memory requirements but also adds a lot of redundant data due to the copying of the incoming point cloud leading to other implications.

However, there are many application scenarios where the octree does not organize a pointcloud but data associated with it (such as the centroid calculation). In this case, each cell would not store indices but for instance a calculated centroid. Hence, there should not be any application specific logic in the Octree class as well as in the container classes. Here's an example how an application could should use the octree interface.

OctreePointcloud<PointT, OctreeContainerT>
for (PointT& point: pointcloud) {
    OctreeKey key;
    octree.genOctreeKeyForPoint(point, key)
    OctreeContainerT container = octree.createLeaf(key) // This returns an existing container if it already exists
    // update centroid estimate in container with "point" data.
}

The OctreePointCloudPointVector class would use vector as OctreeContainerT, the OctreePointCloudCentroid calls can use PointT as OctreeContainerT, etc. If you need to store points and indices, would create your own struct and update it accordingly. Please let me know your opinion here. Would this work with the super voxel class?

Hi guys, I'm sorry I am not participating in the discussion, though I would like. I have a few important deadlines approaching, and will rejoin you in a few days once they are over.

Storing points instead of indices would not only significantly increase the memory requirements

This is not true. The amount of memory used by storing a centroid in the leaves can actually be significantly less than storing indices - it's dependant on the amount of points within each leaf.

Hence, there should not be any application specific logic in the Octree class as well as in the container classes. Here's an example how an application could should use the octree interface.

I'm a little confused now. All this functionality is currently inside OctreePointCloud, are you saying it should be moved out of it?

The OctreePointCloudPointVector class would use vector as OctreeContainerT, the OctreePointCloudCentroid calls can use PointT as OctreeContainerT, etc.

This could be done, but I think it would require changing quite a bit of the Octree code, and I don't really see any advantage of doing it this way over the current system of leaf containers.

Storing points instead of indices would not only significantly increase the memory requirements

This is not true. The amount of memory used by storing a centroid in the leaves can actually be significantly less than storing indices - it's dependant on the amount of points within each leaf.

Agreed. See my previous comment: ... there are many application scenarios where the octree does not organize a pointcloud but data associated with it (such as the centroid calculation). In this case, each cell would not store indices but for instance a calculated centroid.

Hence, there should not be any application specific logic in the Octree class as well as in the container classes. Here's an example how an application could should use the octree interface.

I'm a little confused now. All this functionality is currently inside OctreePointCloud, are you saying it should be moved out of it?

Exactly. The octree iterators expose already some of the functionality, but I think that it would be a much nicer interface to use the octree independently from the application.

The OctreePointCloudPointVector class would use vector as OctreeContainerT, the OctreePointCloudCentroid calls can use PointT as OctreeContainerT, etc.

This could be done, but I think it would require changing quite a bit of the Octree code, and I don't really see any advantage of doing it this way over the current system of leaf containers.

Well, the advantage would be that we don't run into this template madness using traits and template specialization. And design-wise, it would results in an improved separation between program logic and data containers.

In my opinion, the changes needed would not be very comprehensive but would touch the octree interface. If we agree on this, then I would write a patch for discussion.

In my opinion, the changes needed would not be very comprehensive but would touch the octree interface. If we agree on this, then I would write a patch for discussion.

Maybe I'm naive (or perhaps crazy) but I I envision having OctreePointcloud as an entirely separate data structure from Pointcloud- one that uses an octree rather than a vector. This would mean providing an STL like interface for adding new points, but I don't think that would be so bad, really.

I guess this is why storing indices in leaves is such a problem for me - if you store indices it's not really a separate structure, since the leaves the indices fall in is dependent on the external pointcloud. When you store points, the structure is entirely self contained and can serve as an actual container - a tree alternative to the vector Pointcloud.

In my mind an OctreePointcloud<int> doesn't even really make sense - why would you make an octree in one dimension? What you're really making is an OctreePointcloud<PointT*> that dereferences the points when building the tree - and that's not really how containers should work imo.

It seems the question here is whether OctreePointcloud should be an actual tree-based container, or a tree which stores references to a separate Pointcloud (ie vector) container. We're trying to make it both here, and I think it's leading to these problems that require the "boost magic" to resolve the discrepancy.

Maybe I'm naive (or perhaps crazy) but I I envision having OctreePointcloud as an entirely separate data structure from Pointcloud- one that uses an octree rather than a vector. This would mean providing an STL like interface for adding new points, but I don't think that would be so bad, really.

That's not crazy :) That's exactly what I envision as well. To this end, I designed the OctreeBase class to be completely independent from any notion of point clouds. They implement the octree behavior by just taking octree keys into account independent from points, etc. They also don't store indices but an octree container that is templated against a user type.

The OctreePointCloud class extends the octree to work with pointclouds. And here storing indices makes sense, since in most pointcloud-related applications (nearest neighbor, etc.), this is the most efficient way of organizing the point set. In other applications, like the centroid calculation per voxel a separate class that does not store indices is needed.

In my mind an OctreePointcloud<int> doesn't even really make sense - why would you make an octree in one dimension? What you're really making is an OctreePointcloud<PointT*> that dereferences the points when building the tree - and that's not really how containers should work imo.

Well, I am not sure what you mean by "one dimensions". The template parameter specifies what is stored in the containers. I agree, you can argue if storing PointT* has advantages over indices.

It seems the question here is whether OctreePointcloud should be an actual tree-based container, or a tree which stores references to a separate Pointcloud (ie vector) container. We're trying to make it both here, and I think it's leading to these problems that require the "boost magic" to resolve the discrepancy.

Absolutely, I agree with you. This is what we should aim for. In other words, the OctreePointcloud class should use OctreeBase as a member. Does that make sense? Please let me know your opinion.

The OctreePointCloud class extends the octree to work with pointclouds. And here storing indices makes sense, since in most pointcloud-related applications (nearest neighbor, etc.), this is the most efficient way of organizing the point set. In other applications, like the centroid calculation per voxel a separate class that does not store indices is needed.

Yeah, sorry. I suppose I've gotten so used to working with points in the containers that I completely forget that people use the indices.

The template parameter specifies what is stored in the containers. I agree, you can argue if storing PointT* has advantages over indices.

I agree, and I think this the current problem - it specifies what is stored in the containers, but not how it should be added to the container.

Absolutely, I agree with you. This is what we should aim for. In other words, the OctreePointcloud class should use OctreeBase as a member. Does that make sense? Please let me know your opinion.

You mean remove the inheritance? I think that would certainly make the code cleaner, but I don't see how it would solve this problem of containers needing to know how points should be inserted into them.

You mean remove the inheritance? I think that would certainly make the code cleaner, but I don't see how it would solve this problem of containers needing to know how points should be inserted into them.

Well, each point cloud class would have its own container. The octree class becomes a member of the OctreePointcloud classes and does not need to know anything about the container itself. The OctreePointcloud classes then would work with the actual containers, inserting, manipulating data, etc. Hence the octree class implements the octree logic, voxel lookup etc. The OctreePointcloud class works with the containers. Does this make sense?

OctreePointcloud classes then would work with the actual containers, inserting, manipulating data, etc. Hence the octree class implements the octree logic, voxel lookup etc

Yeah, this seems like a sensible way of doing it. It will take a bunch of code refactoring though.