Merging leaves in an octree

I have a very large point cloud (> 100000 points) that I'd like to detect planar arrangements in. I decided to use an octree to break the points into very small planar clusters and then merge neighboring clusters that are coplanar. I have written code in C++ that quickly splits the point cloud into the small planar clusters, but how to effectively merge them is eluding me...

My Octree implementation uses a pointer structure: there are Oct开发者_StackOverflow中文版reeNodes with arrays OctreeNode* children[8] containing pointers to their child nodes, or all NULL pointers if it is a leaf node.

My first thought was to, in each OctreeNode object, keep a pointer to a Plane object. After splitting the points the first time, each leaf in the octree will get a Plane that represents the least-squares fit to all the points contained in the leaf. I then iterate over every leaf node in the tree. For each leaf node, I check each one of its neighbor leaf nodes: if the neighbor's plane should be merged with the current leaf's plane, I call Plane* newPlane = Plane::mergePlanes(this->plane, neighbor->plane); to create a new plane that represents the points in both nodes.

This is where I've run into trouble... I first thought I could simply replace both planes with the new plane, i.e. plane = newPlane; neighbor->plane = newPlane; and be done (memory leaks aside; I handled them in the real code). Unfortunately, this doesn't work in practice. After merging several planes, there may be several different OctreeNodes pointing to a single Plane, and simply replacing the pointers in this->plane and neighbor->plane doesn't replace EVERY pointer that is pointing to their old planes.

The solution seemed hackish even when I first came up with it, and now its flaws are even more clear. Can anyone think of a way to fix the merging method I came up with, or think of a better one?

Thank you

The standard fix is to lazily fix nodes. Have an access method that looks at the plane you're pointing to, and then sees whether it has been pointed elsewhere. If it has, recursively search until you find where it is, and fix up all of the objects back to the current one, and then hand back the right plane.

This is a lot more expensive than following a pointer, but in practice this isn't nearly as expensive as you would think since most of the time the final object is in the first or second place that you look.

VTK has a similar point handle class vtkIncrementalOctreePointLocator. I think the ideal point to merge the insert point.

E.g.:

double xyz[3];    // location
id_type point_id; // we get back the point id

// bool InsertUniquePoint( double xyz[3], id_type &point_id );
// return value is true, if new point inserted
bool value = inserter->InsertUniquePoint( xyz, point_id );

So my opinion: if the class too big, it is easier to rebuild it.