Алгоритм удаления дублирующихся вершин и граней (2 стр)

Я не программист, но если смотреть алгоритмически время работы моего алгоритма растет прямо пропорционально количеству вершин, то есть O(N)?

работает как написал в посте 10

перечитал еще раз твою статью
как я понял ты разбиваешь Bounding Box на кубики, округляешь координаты вершин до ближайшего угла кубика и
приписываешь каждой вершине индекс угла

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

romank

>> Я не программист, но если смотреть алгоритмически время работы моего алгоритма растет прямо пропорционально количеству вершин, то есть O(N)?

да верно, но есть проблемы - огрубление координат (потеря точности)
лечится уменьшением шага, но растет кол-во кубиков (кубично:), пропорционально время и потребная память

у твоего алгоритма еще один плюс - убирает ВНУТРЕННИЕ вершины, это можно где-то применить

мне в голову еще пришло сделать неравномерную сетку - т.е. 3 секущие плоскости через КАЖДУЮ вершину параллельно Oxy,Oyz,Oxz, - но там уже нужна сортировка, полезен лиш для убирания внутренних вершин, полюбому памяти много кушает

что касается текстур и нормалей, твой алгоритм легко обобщить, добавь дополнительные измерения в пространство, но вышесказанные проблемы усилятся многократно

что у тебя за задача с миллионами вершин? инженерная проблема?

ну если кубики с самого начала заданы - другое дело, я думал у тебя типичная для gamedev задача - загрузка меша

Всё понятно. Рассматриваются разные области, у меня видимо очень специальный случай.
В моей ситуации я имею сетку (grid) размером X,Y,Z состоящую из примыкающих друг к другу кубиков.

Да инженерная задача.
Мой алгоритм убирает все потроха объемной фигуры, остается только пустая оболочка.

то есть есть равномерная сетка в 3D и фигура, заданная изначально как? традиционно вершинами и гранями?
я уже видел похожую тему, это ты писал?

Кубики могут и не иметь общих граней :)
Сначала делал так :
glBegin(GL_QUADS) glColor3f(цвет кубика) собственно кубик glEnd();
Очень медленный рендер.

Теперь же, я имею отличную скорость, но не знаю как кубик в цвет один закрасить, чёрт его дери, по массиву цветов каждого кубика. Нашел выход в 1D текстурах, да можно окрасить каждый кубик в свой цвет, только я теряю выйгрыш в дублировании вершин. Приходится иметь на каждую грань обязательно четыре координаты.

Хотелось быть самым быстрым парнем на этом побережье. Видимо придется отказатся от первого алгоритма.

ответь на 23 пост

Мы как то асинхронно пишем. Да, я писал в теме Solid&Wire, приводил пример рисунка.
Фигура задана так: восемь раз по (x, y, z) - первый куб и так далее.

не нашел ту тему, опиши проблему нормально, забрось сюда рисунок или ссылку дай

т.е. фигура ИЗНАЧАЛЬНО задана кубиками. Они все одного размера или необязательно? Походу чтоб задать куб хватает (x,y,z) + размер

Может стоит перейти в IRC на #gamedev?

Solid Wireframe