Привет, вот возник вопрос, имеется 3d массив (достаточно большой 300*300*300 хотя бы), со значениями - цвет вокселей. нужно его отобразить в 3D (OpenGL) Можно ли как-нибудь сделать это быстро ? Ну или хотябы так: Выбрать только те точки которые принадлежат контуру (в 3D !) и "полигонизировать" их (по 3 точки на грань) так вот, как найти этот самый контур ? Наверное какой-нибудь замутный клеточный автомат для этого надо ? П.С. Нужно это для написания интры, типа "oldschool meet's newschool" где старые oldsCOOL'ные эффекты (огонь, вода и пр.) реализованы в 3D массиве (а не в 2D) и "вокселизированы"
300^3 = 27'000'000. Эффект-то oldschool, вот только тачка далеко не oldschool-льная понадобится. Полностью "честно" сполигонизировать (а это придется делать каждый кадр как я понимаю) такой массивчик на компах простых смертных не получится. Даже самые модные алгоритмы типа триангуляции Делоне в совокупности с квиксортом дадут сложность порядка (n^3)*log((n^3),2), что в данном случае означает 666'534'313 итераций. Если каждая итерация займет 10 тактов (что в принципе не реально), это уже 6.7GHz для 1 FPS при условии что коэффициент временной сложности C из выражения C*(n^3)*log((n^3),2) равен 1, что в принципе тоже не реально. С другой стороны, можно попробовать заюзать RayTracing, проткнув массив лучами из камеры. Если постараться, то в принципе, можно прийти к алгоритмической сложности порядка (n^2)*f(n), где f(n) по идее можно свести к log(n,2), а это уже 740'593 итераций, что почти в 1000 раз быстрее, чем прошлый алгоритм. Но напомню, в данном случае RayTracing, в отличие от прошлого способа, будет приближенным решением.
О сложности (n^2)*log(n,2) я похоже поторопился. Это далеко не тривиальная математическая задача, по сути являющаяся численным решением нелинейного уравнения одной переменной. Мысли такие: 1. 3D массив по сути является кубом. Проецируем вершины на экран, определяем видимые грани и растеризуем их. Через полученные пиксели и поведем лучи. В итоге понадобится перебрать меньше пикселей, чем k*n^2, и чем дальше объект, тем меньше, где k - количество видимых граней. 1 <= k <= 3. 2. Хорошей идеей будет построить mip-map ряд из кубов. Это так же снизит количество обрабатываемых данных + практически нахаляву даст mip-map фильтрацию. 3. С ходом луча до соприкосновения с кубом все ясно. Далее, ход луча внутри куба. Если количество пересечений луча с поверхностью внутри куба заранее известно, то можно заюзать дихотомию (нам нужно первое пересечение) и свести общую сложность к (n^2)*log(n,2). Иначе, боюсь что придется использовать последовательное приближение с постоянным шагом. Это дает общую сложность порядка n^3. Но если камера находится от куба на расстоянии нескольких размеров самого куба, то временные затраты заметно снизятся и производительность будет приемлемой. PS: Воду предлагаю хранить двумерным бампом. Это существенно облегчит жизнь.
Забыл уточнить. Растеризовать можно прямо на экран. Тут вобще будет достаточно DirectDraw и простого тыкания пикселей в память видяхи и никакие треугольники не нужны. Но так придется забыть о расчете освещения и прочих прелестях средствами GPU. Если же мы хотим полигонизацию, то растеризовать надо на какой-то массив в оперативе. Соответственно масштаб, или размер, нашего виртуального экрана будет определять качество полигонизации. Точки этого виртуального экрана будут являться координатами треугольников. Надеюсь ясно как построить разбиение. Т.к. точки будут 3D, то и от видяхи можно будет получить и освещение и все остальное. Вот меня пробило
Это чет слишком мутно А что если сделать клеточный автомат ? Если количество соседних "кубиков" равно 8 то текущий "кубик" дохнет, иначе оставляем его ?
tylerdurden Ну, хорошо, а дальше-то что? Всеравно ведь либо триангулировать, либо RayTracing. Или есть еще идеи?
Даже если сделать вокселями: Сначала прогоняем клеточным автоматом, убивая все внутренние точки, затем на месте каждой точки рисуем кубик - воксель, все ! Т.к. это массив, то в кубиках не будет разрывов (не знаю как выразиться, но это и так понятно) А можно ваще полигонизироватьесли вместо кубиков рисовать какюто замутную хрень к соседним... а вот еще есть метод полизонизации "марширующими кубами"...
tylerdurden Называется с чего начали, тем, извиняюсь за выражение, и кончили. Один хрен сложность O(n^3) получается.
Всем привет. Давно здесь не был. Рад всех видеть. Кубик со стороной в 300 элементов - это дофига. До визуализации дело может вообще не дойти, просто потому, что не получится обновлять такое количество данных с приемлемым фпс-ом. Нужно учитывать то, что в 3д те же растровые эффекты больше действий требуют: если плоский блюр - это усреднение, скажем, 9 точек, то объёмный - уже 27. А 300^3 * 4 байта на цвет, это уже 103 мега. А вот сократив сторону хотя бы до 128, можно оперировать вполне приемлемым объёмом в 8 мегов. Визуализировать его можно, загнав в 3д текстуру и отображая стопкой параллельных экрану секущих плоскостей. А на свежих видяхах ещё более хитрые способы есть, подробностей не помню, но в нвидёвом сдк был эффект с произвольно вращающимся кубиком с 3д текстурой внутри, который рисовался за один проход. А вся трассировка лучей по текстуре делалась в шейдере. Назывался volume, если мне память не изменяет. А сама идея с олдскульными эффектами в 3д отнюдь не нова. Во всяком случае, трёхмерный растровый огонь, полигонизированый по сетке бегущими кубиками, уже точно был. Смотрелось, кстати, некрасиво ни разу.
