У меня есть приложение, которое используется для отображения и изменения огромных объемов данных облака точек из лидарных файлов (до нескольких гигабайт каждый, иногда загружаемых одновременно). В приложении пользователь может просмотреть 2D-изображение загруженных точек (сверху) и выбрать профиль для просмотра в другом окне (сбоку). Опять же, это включает в себя миллионы точек, и они отображаются с использованием OpenGL.
Для обработки данных также есть библиотека quadtree, которая работает, но очень медленно. Он использовался в течение некоторого времени, но недавно формат лидарной точки изменился, и объекту LidarPoint потребовалось добавить ряд атрибутов (членов класса), что привело к его увеличению в размере, что, в свою очередь, повлияло на производительность до почти непригодного уровня (подумайте 5 минут). для загрузки одного файла размером 2 ГБ).
В настоящее время дерево квадрантов состоит из указателей на объекты PointBucket, которые представляют собой просто массивы объектов LidarPoint с заданной емкостью и определенными границами (для пространственных запросов). Если емкость ведра превышена, оно разбивается на четыре ведра. Существует также своего рода система кэширования, которая заставляет сегменты точек сбрасываться на диск, когда данные точек занимают слишком много памяти. Затем они загружаются обратно в память, если это необходимо. Наконец, каждый PointBucket содержит вложенные сегменты/уровни разрешения, которые содержат каждую n-ю точку исходных данных и используются при отображении данных в зависимости от уровня масштабирования. Это связано с тем, что одновременное отображение нескольких миллионов точек, хотя такой уровень детализации не требуется, просто очень медленно.
Я надеюсь, что вы можете получить картину из этого. Если нет, пожалуйста, спросите, и я могу предоставить более подробную информацию или загрузить больше кода. Например, вот текущий (и медленный) метод вставки:
// 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]++;
}
}
}
Теперь мой вопрос: можете ли вы придумать способ улучшить этот дизайн? Каковы некоторые общие стратегии при работе с огромными объемами данных, которые не помещаются в память? Как сделать дерево квадрантов более эффективным? Есть ли способ ускорить отрисовку точек?
