Привет.
В течение последнего месяца я постоянно собирал информацию из различных источников, но без удачи нашел идею, чтоподойдет моей конкретной проблеме.Итак, вот формулировка задачи:
Дана сетка в форме геометрии буфера (32-битные массивы координат вершин и индексов вершин + дополнительные массивы, такие как нормали вершин, uvs или касательные) вычислить функцию расстояния со знаком (SDF) для равномерной сетки точек, окружающих геометрию.
Чтобы быть более точным, я намерен создать нечто похожее на объект MetaBall в 3D-движках, таких как Maxon's Cinema4D илиBlender.Я успешно реализовал функции расстояния для всех геометрических примитивов, но SDF с произвольной сеткой потребовал от меня применения подхода грубой силы - тестирования расстояния для каждого треугольника сетки для каждой точки сетки - что, конечно, становится действительно медленным для сложныхmeshes.
Теперь я вспомнил, что для большинства из этих проблем требуется построение древовидной структуры, такой как Octree, KD-дерево, BSP-дерево или AABB-дерево.Затем я нашел несколько статей о так называемом алгоритме Fast-Sweeping (для решения уравнения Эйконала), который сначала требует заполнения точек сетки, лежащих на границе (в моем случае сетка или ближайшийв сетку) с 0, а остальные с большими значениями (бесконечность), а затем итеративно решить нелинейную гиперболическую краевую задачу (Гаусс-Зейдель).Я также нашел реализацию метода SDF с открытым исходным кодом в библиотеке CGAL .Кроме того, я также подумал об использовании некоторой библиотеки шейдеров (например, GLSL) и, возможно, попытался построить деревья с помощью графического процессора, но я никогда не использовал шейдеры в проекте JS или TS.
Шаг, который я продолжаю застревать на isnЯ просто выбираю лучший вариант, но фактически использую, по крайней мере, один из этих методов эффективно.Например:
Если бы я хотел реализовать метод быстрого марширования , мне пришлось бы перебирать все треугольники, а затем для каждого перебирать всеточки сетки Gijk, и используя нечто похожее на таблицу поиска Marching Cubes для пересечений ячеек сетки (но с еще большим количеством опций), я бы интерполировал значения, близкие к 0, для пересеченных вершин ячеек.У меня такое ощущение, что это займет неоправданно много времени и окажется неподходящим для обновления в реальном времени.
Мне удалось найти несколько примеров Ray Marching SDF вычисление в Unity.Кроме того, поскольку я никогда не пытался вычислять что-либо непосредственно на GPU, я понятия не имею, каковы ограничения, например, для параллельных вычислений на нем, и я не понимаю, как выполняются такие вычисления.Могу ли я распараллелить вычисление расстояния до каждого треугольника, а затем быстро отсортировать все расстояния для каждой точки сетки Gijk?Если да, то как мне включить его в проект TypeScript?
Скажем, я строю AABB-дерево вокруг всех треугольников в сетке (которое должно быть O(n * log (n))), затем с учетом точки сетки Gijk (при условии, что корень дерева представляет собой поле, содержащее как Gijk, так и все треугольники), я бы искал ближайший лист и вычислил евклидово расстояние до треугольника, содержащегося в(или если их больше одного, выберите).(Пожалуйста, поправьте меня, если я ошибся). Поиск должен быть O (log (n)), и если пользователь перемещает сетку, обновление займет O (n), где n - количество треугольников.Так что, если m - размер сетки, тогда все вычисления SDF будут O (m * n * log (n))?Это не похоже на улучшение по сравнению с подходом грубой силы O (n * m), но, возможно, я неправильно понял сложность.
Я думал о комбинировании нескольких подходов, но все это кажется очень трудоемким.Я также подумал об использовании библиотеки CGAL или, возможно, о рефакторинге для целей моего проекта, но я нахожу довольно сложным для понимания кода C ++ из-за всех зависимостей внутри библиотеки.Кто-нибудь из вас делал что-то подобное?Что бы вы порекомендовали?
Спасибо за все идеи.