Как пройти по вершинам сетки в зависимости от их местоположения?

Question

Я использую Point Cloud Free Viewer для визуализации облаков точек в Unity. У него есть скрипт, который анализирует файлы.off и создает сетки без триангуляции. Однако код создает несколько ячеек, поскольку его индексный формат 16-битный. Я изменил код для использования 32-битного формата, и у меня есть сетка с 2 миллионами точек:

Я хочу создать сетку, подобную геометрии, и покрасить это облако точек на основе плотности точек. Я хочу найти приблизительный объем этого облака точек, умножив разницу между значениями max и min x,y,z и разделив этот объем на равные блоки. Каждое из этих полей будет окрашено в зависимости от количества точек, которые они содержат. Я был бы счастлив, если бы кто-то мог предложить мне лидерство. Я попробовал подход KDTree, но он немного медленный, так как у меня 2 миллиона очков. Я также пробовал сортировать точки перед созданием меша, но это также занимает слишком много времени. Есть ли способ прохождения вершин сетки на основе местоположения без посещения всех вершин, учитывая, что они проиндексированы случайным образом? Я считаю, что я ищу решение, подобное mesh.bounds.contains() но я не знаю, существует ли такой метод, как пространственный поиск.

Answer 1

Для тех, кто может посетить этот вопрос позже, я нашел действительно быстрое решение, основанное на комментарии Нико. Я обхожу целые точки, анализируя мой файл сканирования с помощью этого сценария

 for (int i = 0; i < numPoints; i++)
    {
        buffer = sr.ReadLine().Split();

        points[i] = new Vector3(float.Parse(buffer[0]) , float.Parse(buffer[1]) , -float.Parse(buffer[2]) );

        //Finding minX, minY, minZ
        if (points[i].x < minX)
            minX = points[i].x;
        if (points[i].y < minY)
            minY = points[i].y;
        if (points[i].z < minZ)
            minZ = points[i].z;
        //Finding maxX, maxY, maxZ
        if (points[i].x > maxX)
            maxX = points[i].x;
        if (points[i].y > maxY)
            maxY = points[i].y;
        if (points[i].z > maxZ)
            maxZ = points[i].z;

    }

Вот мои и переменные я использую с нимFindPointIndex функция.

    deltaX = maxX - minX;
    deltaY = maxY - minY;
    deltaZ = maxZ - minZ;
    gridCountX = Mathf.CeilToInt(deltaX / gridSize);
    gridCountY = Mathf.CeilToInt(deltaY / gridSize);
    gridCountZ = Mathf.CeilToInt(deltaZ / gridSize);
    Resolution = gridCountX * gridCountY * gridCountZ;
    Histogram = new int[Resolution];

 int FindPointIndex(Vector3 point)
{
    //Finds the grid index of the point 
    int index = Mathf.FloorToInt((point.x - minX) / gridSize) + ((Mathf.FloorToInt((point.z - minZ) / gridSize)) * gridCountX)
           + Mathf.FloorToInt((point.y - minY) / gridSize) * gridCountX * gridCountZ;
    if (index < 0)
    {
        index = 0;
    }
    return index;
}

Затем я могу снова пересечь точки, чтобы увеличить индекс для каждой из них, чтобы увидеть, сколько точек каждая сетка содержит следующим образом:

 for (int i = 0; i < numPoints; i++)
    {
        Histogram[FindPointIndex(points[i])]++;                                      
    }

В конце, используя эту гистограмму, я могу закрасить облако точек другим циклом.

Answer 2

Не совсем, полное решение, скорее подсказка в направлении, которое я бы выбрал: сначала разделите ваш пул вершин на более мелкие группы, т. Е. На кубы (возможно, отдельные сетки), просчитайте это, тогда вам нужно искать только в гораздо меньшей области, после начального поиска набора кубов, которые соседствуют (или касаются) вашего региона.

Answer 3

Для меня это звучит так, будто ты хочешь октри.

Во-первых, загрузите все точки в память (2 миллиона точек на самом деле не так много - при условии удвоения, это 2 000 000 * 3 * 8 байт ~= 45 МБ). Пока вы анализируете файл и загружаете точки в память, запишите минимальные и максимальные координаты x, y и z. Затем вы можете построить свое октодерево, которое ограничивает этот объем в N*LogN. Затем для каждого из ваших объемов сетки вы можете очень быстро запросить дерево, чтобы получить только точки в этом регионе. Я уверен, что это самый эффективный способ сделать то, что вы хотите.

Я бы предложил проверить статью quadtree для ее реализации queryRange чтобы увидеть, как это будет сделано. Октри - это просто трехмерная реализация квадродерева, поэтому базовый код более или менее одинаков (каждый узел содержит 8 дочерних элементов вместо 4).