- О. Федор
- Постоялец
Добрый день, встречал на форуме несколько статей по теме.
Хочу предложить описание ещё одного алгоритма.
UPD:
В алгоритме рассматривается специальный тип сеток, используемый при гидродинамических расчетах. Статья рассчитана на тех, кто занимается визуализацией результатов расчета гидродинамических симуляторов.
Прочитав статью, я понял, как оптимайзить кубики, но совершенно не понял, как оптимайзить случайные меши :)
Altair
Ты невкурил, за кубиками будущее, скоро и ты сам их них будешь состоять ) И сиськи тоже будут квадратные
romank
Если честно, и вправду не понятно, как смотреть назад... ))))))))) Хотя может и вправду что-то есть...
А можно на примере Сферы объяснить? или хотябы на примере предположительно бесконечной поверхности ( ландшафт ).
Всеобщий Универсальный Алгоритм удаления дублирующихся вершин и полигонов
1. Координаты всех вершин записываются с заданным огрублением, пропорциональным возможной поргрешности положения вершин, как числа Моргана в общий массив int vMorgan.
2. Массив vMorgan сортируется.
3. В результате простого прохода все повторяющиеся элементы vMorgan считаются одной вершиной, соответственно перенумирируются вершины в полигонах.
4. Номера всех вершин полигонов в возрастающем порядке записываются как числа Моргана в общий массив int pMorgan.
5. Массив pMorgan сортируется.
6. В результате простого прохода все повторяющиеся элементы pMorgan считаются одним полигоном, лишние выбрасываются.
О. Федор
Зачем тъ все ето понаписъвал?
На память. Между прочим алгоритм роботоспособный.
Z
Ты его не понял?
О. Федор
Там непонятно ничего.
Z
Там основная фишка в использовании чисел Моргана. Дело в том, что хотя эти числа скалярны, они позволяют представить векторы (3 и 2D), причем близкие в отсортированной последовательности числа Моргана отображают близкие в пространстве вектора.
Да, и еще. Я считаю, разумеется приближенно, что две вершины v1 и v2 совпадают если |v1 - v2 | < eps.
О. Федор
Ето лиш weld-инг, которъй принципно не так уж и важен - как часто художник производит меш, где много близких < eps вертексов?
Суть в другом там.
romank
а если не кубик, а произвольный меш?
я сделал примерно так:
сортирую вершины (сравниваю x,если равно сравниваю y,если равно сравниваю z)-сортировка слиянием O(N*log(N))
повторяющиеся удаляю за один проход
на самом деле несколько сложнее:
вершины не переставляю, сортирую их индексы
проход по отсортированному массиву
для каждой вершины вычисляю флаг, надо ли ее удалить
для всех оставляемых вершин вычисляю новый индекс (после удаления повторяющихся)
проход по отсортированному массиву
каждой удаляемой вершине сопоставляю индекс оставляемой
переиндексирую грани
при сравнении вершин я учитываю нормаль,колор,текс.координаты-в результате массив готовый для VBO
Да, можно и сферу и ландшафт.
Я начинал с "взять вершину" "просмотреть все вершины" "заменить дубликаты" простая реализация и очень медленный код.
Описываемый алгоритм напоминает А* алгоритм, точнее его модификация. Характерен отсутствием различных перестановок и сортировок. Как расчитывается скорость алгоритма я не помню, но время зависит линейно от X-Y-Z.
Внимание : Текущая реализация работает только с вершинами и индексами.
Что делать с текстурами я честное слово пока ещё не придумал, в интернете ничего не нашел, на канале #gamedev полное игнорирование. Проблема такая: на одну грань теперь может приходится менее четырех уникальных вершин. Как сохранить текстурные координаты и сохранить возможность использования VBO?
Если нужен конкретный пример, пришлите мне исходные координаты, чтобы я написал обрезанный пример. Моя реализация кода занимает 400 строк и тащит в себе много лишнего (связанное со спецификой работы). Ещё раз напомню, только вершины, только индексы. Без нормалей, без текстурных координат.
romank
мой код работает за O(N*log(N)) - очень быстро, за вычетом сортировки за ЛИНЕЙНОЕ время
нормали и текстуры-просто добавляешь их к координатам вершины и рассматриваешь 3+3+2-мерные вектора
Aslan у меня больше технический вопрос по VBO, я рад что кто-то может понять вопрос.
Я получил уникальное количество вершин и заполнил буфер VBO
glBufferData(GL_ARRAY_BUFFER, 3 * vertexCount * sizeof(GLfloat), NULL, GL_STATIC_DRAW);
Далее я получил индексированный массив с учетом уникальных вершин
glBufferData(GL_ELEMENT_ARRAY_BUFFER, quadeCount * 4 * sizeof(GLuint), NULL, GL_STATIC_DRAW);
И дальше стопор. Если я дополню GL_ARRAY_BUFFER текстурными координатами, то только для уникальных вершин.
Может сможете показать свой код?
Рассмотреный мной алгоритм работает так : просматриваются все вершины куба и метятся как уникальные или нет.
Далее в цикле закидываются уникальные вершины в VBO. Никаких сортировок, даже перстановок никаких.
Тема в архиве.