Improving quadrant design?

Question

I have an application that is used to display and modify huge volumes of cloud point data from lidar files (up to several gigabytes each, sometimes downloaded at the same time). In the application, the user can view a 2D image of the loaded points (above) and select a profile for viewing in another window (side). Again, this includes millions of points, and they are displayed using OpenGL.

There is also a quadtri library for data processing, which works, but is very slow. It has been used for some time, but recently the format of the lidar point has changed, and a number of attributes (class members) have been added for the LidarPoint object, which make it grow in size, which in turn affects the performance of an almost unused level (I think 5 minutes to download one file with a capacity of 2 GB).

Currently, quadrants consist of pointers to PointBucket objects, which are simply arrays of LidarPoint objects with a given capacity and defined boundaries (for spatial queries). If the bucket capacity is exceeded, it is divided into four buckets. There is also some kind of caching system that forces point buffers to be unloaded to disk when the point data takes up too much memory. Then they are loaded back into memory, if necessary. Finally, each PointBucket contains swap / resolution levels that store every nth point of the source data and are used when displaying data depending on the zoom level. This is due to the fact that it displays several million points at once, while this level of detail is not needed, it is just very slow.

Hope you can get a picture from this. If not, please ask, and I can provide more information or download additional code. For example, this is the current (and slow) insertion 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: can you come up with a way to improve this design? What are some common strategies for working with huge amounts of data that do not fit into memory? How to make a quadrant more efficient? Is there a way to speed up the rendering of points?

Answer 1

Now my question is: can you come up with a way to improve this design?

Yes. Do not store objects in the quadrant. Put them in a flat structure (array, linked list, etc.) And Quadtree will just keep a pointer to the actual objects. If the quadrants have a certain depth (at all nodes), you can also smooth it.