У меня есть приложение, которое используется для отображения и изменения огромных объемов данных облака точек из лидарных файлов (до нескольких гигабайт каждый, иногда загружаемых одновременно). В приложении пользователь может просмотреть 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]++;
}
}
}
Теперь мой вопрос: можете ли вы придумать, как улучшить этот дизайн? Каковы некоторые общие стратегии при работе с огромными объемами данных, которые не помещаются в память? Как я могу сделать квадри более эффективным? Есть ли способ ускорить рендеринг очков?