Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Статьи / Вставка одной поверхности в другую (многопоточный алгоритм)

Вставка одной поверхности в другую (многопоточный алгоритм)

Автор:

В статье рассматривается метод встраивания одной поверхности в другую. Данная статья имеет некоторые «нечеткие» определения, и в ней не гарантируется работа метода на любой геометрии. Она носит скорее исследовательский и теоретический характер, но возможно и это кому-то поможет.

Постановка задачи
Решение
Замечания

Постановка задачи

По условию у нас есть две поверхности, одна исходная, в которую будет вставляться новая поверхность, и соответственно вторая, которая вставляется. Для того чтобы было лучше понятно, можно привести такой пример: песок — изначальная поверхность, след — это вторая поверхность которая «врезалась» в первую. Некое подобие CSG (вычитание). Есть некоторая неконкретность в определении первой поверхности, она должна быть достаточно гладкой и размеры её минимальных элементов должны быть сравнимы с размерами элементов врезаемой поверхности. Врезаемая поверхность представляет из себя некоторую геометрию у которой есть выпуклый замкнутый контур, по которому и будет проходить соединение. Это основное требование к врезаемой геометрии.

Применяться данный метод может как для некоторого подобия вычитания в CSG, так и для уточнения поверхностей при приближении (типа тесселяция).

Вот пример того как это может выглядеть:

2 | Вставка одной поверхности в другую (многопоточный алгоритм) 3 | Вставка одной поверхности в другую (многопоточный алгоритм)

Решение

Для начала сделаем простое решение, которое работает последовательно:

4 | Вставка одной поверхности в другую (многопоточный алгоритм) 5 | Вставка одной поверхности в другую (многопоточный алгоритм)
1. Нужно на исходном меше «начертить» контур врезаемого меша 2. Дальше выкинуть ненужные треугольники, получим два контура (один из которых выпуклый)
7 | Вставка одной поверхности в другую (многопоточный алгоритм) 8 | Вставка одной поверхности в другую (многопоточный алгоритм)
3. Нужно соединить эти два контура (триангулировать) 4. Добавить треугольники и вершины врезаемого меша к основному мешу.
9 | Вставка одной поверхности в другую (многопоточный алгоритм) 10 | Вставка одной поверхности в другую (многопоточный алгоритм)
5. Использование нормалей для восстановления объёма 6. Тоже самое, но нормали инвертированы

Введем некоторые обозначения:
М1 – исходная поверхность
М2 – врезаемая поверхность
К1 – контур образующийся при выкидывании полигонов из М1 для вставки в него М2
К2 – замкнутый выпуклый контур М2

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

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

Соединим сначала только ребра К2 с К1

Для этого будем использовать то, что мы умеем двигаться по поверхности и саму топологию поверхности. Для каждого ребра во врезаемом контуре (К2) идем от точки A к B, по пути собираем информацию о пересекаемых ребрах М1.
Здесь могут быть два случая: пересекаемых ребер нет и они есть (случаи достаточно сильно различаются)
1 для того чтобы построить треугольник, ищем пересечение линии AB c треугольником в котором она лежит; дальше, используя то, что все треугольники ориентированы против часовой стрелки, находим точку C, которая и даст подходящий треугольник.
2 теперь используем ребра, которые пересекаем, чтобы построить новые треугольники. (надеюсь, из рисунка все понятно)


13 | Вставка одной поверхности в другую (многопоточный алгоритм)

Однако теперь могут остаться несоединенными вершины К2 с ребрами К1.
6 | Вставка одной поверхности в другую (многопоточный алгоритм) 7 | Вставка одной поверхности в другую (многопоточный алгоритм)

Здесь опять же возможны три ситуации(0, 1, 2 три новых треугольника), но во всех у нас одна точка лежит внутри треугольника и дотриангулировать не проблематично. Карандашом помечены треугольники, полученные на предыдущей операции.

14 | Вставка одной поверхности в другую (многопоточный алгоритм)

Еще нам нужно сохранить/построить соседей у новых треугольников. Во время прохода по ребрам соседи очевидным образом строятся используя текущую топологию. Во время прохода триангуляции по вершинам мы используем информацию из прилежащих ребер (туда мы ее записываем во время прохода по ребрам, каждое ребро запоминает свой первый треугольник и последний).

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


15 | Вставка одной поверхности в другую (многопоточный алгоритм)

Теперь как все это дело распараллелить. Видно, что операция пробегания одной вершины по поверхности не зависит от остальных, поэтому мы можем всеми вершинами бежать параллельно. Операция триангуляции при проходе по ребрам также не зависит от других ребер, однако при проходе по вершинам мы должны знать информацию, хранящуюся в соседних ребрах, поэтому необходимо дождаться, пока все ребра обработаются. Теперь вершины также обрабатываются независимо. Последний шаг с заливкой также легко реализуется многопоточно (в каждом потоке идет заливка используя только еще не обработанные треугольник), используя атомарные операции. Таким образом видно, что количество потоков удобно сделать равным числу граничных ребер(вершин) у врезаемого контура. Остальные вершины (не контурные) и треугольники удобно распределить примерно одинаково по потокам.

Псевдокод выглядит так:

foreach (граничная вершина / ребро)
{
  каждая вершина находит свою позицию; //строим контур на поверхности;
  присоединяем новые вершины и треугольники относящиеся к данной граничной вершине;
 
  barrier(); //синхронизация

  проход триангуляции по ребрам;

  barrier();

  проход триангуляции по вершинам;

  barrier();
 
  заливка ненужных треугольников;
}

Многопоточная реализация использует OpenGL 4.3, compute shaders и ssbo для записи из шейдера в видеопамять, плюс еще, конечно, атомарные счетчики и атомарные операции над ssbo. Ниже даны приблизительные графики (как версия алгоритма для CPU, так и GPU, не оптимизированы, кроме того версия для GPU оказалась очень "тяжелой", там много длинных условных веток и тд). Тестирование проводилось на ноуте с CPU - Intel Core i5-4258U (2.4ггц), GPU - Intel IRIS 5100.
Первая строка:
  35 - количество граничных ребер(вершин) = кол-ву потоков на GPU;
  246 - общее число вершин в М2;
  455 - общее число треугольников в М2;
Время указано в микросекундах, для загрузки на GPU использовалась функции glMapBuffer.

35 - 246 - 455 70 - 1401 - 2730 140 - 5531 - 10920 280 - 21981 - 43680
300 1298 4056 28345 CPU
30512 52395 120853 402540 CPU(+ загрузка на GPU)
696 1409 2163 4504 GPU

14 | Вставка одной поверхности в другую (многопоточный алгоритм) 15 | Вставка одной поверхности в другую (многопоточный алгоритм)

Замечания

  • Данный метод имеет некоторые значимые недостатки. Наиболее важно то, что прирост в производительности замечен только на достаточно больших значениях. Это значит, что метод не подходит для игр, где все-таки используются модели с меньшей полигональностью. С другой стороны, он не является точным и не подойдет для чего-то другого.
  • Для улучшения алгоритма нужно придумать, как эффективно делать непрерывный переход между поверхностями.
    В качестве направления движения точки по поверхности можно использовать не плоскость, а uv-координаты. По идее, должно все работать, и будет более управляемо и красиво.
  • Исходная поверхность может быть легко восстановлена используя выкинутые треугольники. В них осталась информация о соседях и они могут «рассказать» им: я твой новый сосед.
  • Процедура соединения ребер К2 с К1 может быть изменена. Я делал вариант точного совпадения К2 с М1(но получалось много треугольников).
  • Очень помог геометрический шейдер для проверки правильности построения новых соседей(маленькие треугольники показывают соседство).

16 | Вставка одной поверхности в другую (многопоточный алгоритм)

Вот небольшое демо:


9 сентября 2015

#geometry modification, #OpenGL


Обновление: 11 сентября 2015

2001—2017 © GameDev.ru — Разработка игр