Please help me improve my quadtree design

Question

I have an application which is used for displaying and modifying huge volumes of point cloud data from lidar files (up to few gigabytes each, sometimes loaded in simultaneously). In the app the user is able to view a 2D image of loaded points (from the top) and select a profile to view in another window (from the side). Again this involves millions of points and they are displayed using OpenGL.

To handle the data there is also a quadtree library, which works, but is extremely slow. It has been used for some time, but recently the lidar point format changed and the LidarPoint object needed a number of attributes (class members) added, which cause it to grow in size in turn affecting the performance to almost unusable level (think 5 minutes to load a single 2GB file).

The quadtree currently consist of pointers to PointBucket objects which are simply arrays of LidarPoint objects with specified capacity and defined boundaries (for spatial queries). If the bucket capacity is exceeded it splits into four buckets. There is also kind of a caching system in place which causes point buckets to get dumped to disk when the point data is taking too much memory. These are then loaded back into memory if needed. Finally every PointBucket contains subbuckets/resolution levels which hold every n-th point of the original data and are used when displaying the data depending on the zoom level. That is because displaying few million points at once, while that level of detail is not necessary, is just extremely slow.

I hope you can get a picture from this. If not please ask and I can provide some more details or upload more code. For example here is the current (and slow) insert method:

// Insert in QuadTree
bool QuadtreeNode::insert(LidarPoint newPoint)
{
   // if the point dosen't belong in this subset of the tree return false
   if (newPoint.getX() < minX_ || newPoint.getX() > maxX_ || 
       newPoint.getY() < minY_ || newPoint.getY() > maxY_)
   {
      return false;
   }
   else
   {
      // if the node has overflowed and is a leaf
      if ((numberOfPoints_ + 1) > capacity_ && leaf_ == true)
      {
         splitNode();

         // insert the new point that caused the overflow
         if (a_->insert(newPoint))
         {
            return true;
         }
         if (b_->insert(newPoint))
         {
            return true;
         }
         if (c_->insert(newPoint))
         {
            return true;
         }
         if (d_->insert(newPoint))
         {
            return true;
         }
         throw OutOfBoundsException("failed to insert new point into any \
                                     of the four child nodes, big problem");
      }

      // if the node falls within the boundary but this node not a leaf
      if (leaf_ == false)
      {
         return false;
      }
      // if the node falls within the boundary and will not cause an overflow
      else
      {
         // insert new point
         if (bucket_ == NULL)
         {
            bucket_ = new PointBucket(capacity_, minX_, minY_, maxX_, maxY_, 
                                      MCP_, instanceDirectory_, resolutionBase_, 
                                      numberOfResolutionLevels_);
         }
         bucket_->setPoint(newPoint);         
         numberOfPoints_++;
         return true;
      }
   }
}

// Insert in PointBucket (quadtree holds pointers to PointBuckets which hold the points)
void PointBucket::setPoint(LidarPoint& newPoint)
{    
   //for each sub bucket
   for (int k = 0; k < numberOfResolutionLevels_; ++k)
   {
      // check if the point falls into this subbucket (always falls into the big one)
      if (((numberOfPoints_[0] + 1) % int(pow(resolutionBase_, k)) == 0))
      {
         if (!incache_[k])
            cache(true, k);

         // Update max/min intensity/Z values for the bucket.
         if (newPoint.getIntensity() > maxIntensity_)
            maxIntensity_ = newPoint.getIntensity();
         else if (newPoint.getIntensity() < minIntensity_)
            minIntensity_ = newPoint.getIntensity();

         if (newPoint.getZ() > maxZ_)
            maxZ_ = newPoint.getZ();
         else if (newPoint.getZ() < minZ_)
            minZ_ = newPoint.getZ();

         points_[k][numberOfPoints_[k]] = newPoint;
         numberOfPoints_[k]++;
      }
   }
}

Now my question is if you can think of a way to improve this design? What are some general strategies when dealing with huge amounts of data that doesn't fit into memory? How can I make the quadtree more efficient? Is there a way to speed up rendering of points?

Answer 1

Profiling is always good to locate bottlenecks.

If quadtree construction is a bottleneck, it might help to use multiple passes. A first pass might only store the x/y values which are all that is needed to determine the structure of the quadtree. For a second pass, the buckets can be pre-allocated to the correct size (most less than capacity_) and each point goes directly to the right bucket.

For the resulting quadtree, do you really need to store the point values (multiple times, at that)? Maybe just the summary info is enough (min/max z, min/max intensity). Or if you need the points only rarely, store an index to each point and do a more expensive look-up to find the point specifics when needed.

Lastly, if your coordinates are used at display resolution, you can store them with floats instead of doubles.

Answer 2

You may find this article gives you some ideas...

http://queue.acm.org/detail.cfm?id=1814327

You mention a caching scheme. What this argues is that rather than having a caching scheme, you let virtual memory do the work for you on that, and manage things so that data fits into memory pages in a way which matches how the data tends to be used.

The article doesn't talk about quadtrees - rather it's talking about b-heaps, and the usage is quite different - they are looking at locating single data-points as fast as possible on a heavily used server, whereas it seems you're looking at pulling in large amounts on data on a single workstation. So it's something to be inspired by, more than something which solves your problem directly, but it may give you thoughts about how you can structure your data to make best use of disk accesses. The resulting data structure might end up being much more complex, but I would be surprised if the issue was CPU rather than disk so the tradeoff should work in your favour.

Hope it gives you some ideas!