Блог

Главная - Вопросы по программированию - Разделяющая сетка

Разделяющая сетка

#algorithm #3d #geometry

#алгоритм #3D #геометрия

Вопрос:

У меня проблема с разделением сеток. Существует комбинированная сетка, которая имеет 1 вершинный буфер и 1 индексный буфер для треугольников. Но в сетке есть как минимум 2 отдельных объекта. Например, есть 2 квадрата без общей вершины (и, конечно, без общего индекса), и их геометрия находится в 1 одиночной сетке (1 буфер вершин, 1 буфер индексов). Итак, как я могу создать из них 2 сетки. Существует ли какой-либо алгоритм для этого.

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

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

Разделение сетки

Комментарии:

1. какое 3D-приложение вы используете, если это так.

2. Я работаю с Unity, но для меня это не важно

3. Это было бы простой задачей для выполнения в Maya, например, никогда не работало с unity. Я не уверен, можете ли вы редактировать сетку или она сгенерирована процедурно (?)

4. Что вы собираетесь делать с сетками? Если вы хотите их нарисовать, я бы посоветовал оставить вершинный буфер нетронутым и просто создать два отдельных индексных буфера. Если вам все равно нужны данные о вершинах на графическом процессоре, нет причин хранить их в двух отдельных буферах. Разделение может быть выполнено с помощью структуры данных union-find.

5. Это должно быть сделано не только для рисования.

Ответ №1:

Во-первых, инициализируйте объединение-найдите структуру данных с количеством вершин. Затем найдите все связанные компоненты следующим образом:

 for each triangle index i1, i2, i3 in indices
    union-find.union(i1, i2)
    union-find.union(i1, i3)

Затем инициализируйте пустую карту (или словарь), которая сопоставит старые индексы вершин с новыми:

 Dictionary<int, int> indexMap;

Кроме того, нам понадобятся новые списки для вершин:

 Dictionary<int, List<Vertex>> vertices;
Dictionary<int, List<int>> indices;

Затем распределите вершины по правильным спискам следующим образом:

 for i from 0 to vertex count -1
    componentRepresentative := union-find.find(i)
    if(!vertices.ContainsKey(componentRepresentative))
        vertices.Add(new List<Vertex>());
        indices.Add(new List<int>());
    var list = vertices[componentRepresentative];
    list.Add(vertexBuffer[i]);
    indexMap.Add(i, list.Count - 1)

На этом этапе мы разделили буферы вершин. Нам все еще нужно аналогичным образом разделить индексные буферы.

 for i from 0 to index count - 1
    componentRepresentative := union-find.find(indexbuffer[i])
    var list = indices[componentRepresentative]
    list.Add(indexMap[indexBuffer[i]])

Общая временная сложность составляет почти O (n) (для идеальной структуры объединения-поиска).