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

Question

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

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

Answer 1

Звучит так, будто ты хочешь октри .

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

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

Answer 2

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

 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 3

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