Войти
3DTetraWavesФорумОбзор существующих алгоритмов

Воксельная графика

Advanced: Тема повышенной сложности или важная.

Страницы: 1 2 3 4 Следующая »
#0
9:38, 19 окт. 2012

Идея воксельной графики базируется на понятии трёхмерного пикселя - кубического единичного объема из которого составленно всё отображаемое пространство, при этом воксели могут быть прозрачными, залитыми одним цветом или градиентом цвета по цветам вершин куба.
Рассматривать воксельную графику без специально разработанных алгоритмов оптимизации использования памяти, нет смысла, потому как объем воксельного пространства представленный всеми вокселями столь огромный что для небольшой сцены требуются гигабайты памяти. Например, при дискретности пространства 1 сантиметр, и размера сцены 100х100х100 метров, количество вертексов составляет 10000х10000х10000 = 10^12 штук, если в простейшем случае для одного вокселя требуется хранить только один цвет, то есть 24 бита, то получается что такая сцена займёт 3х10^12 байт, или 273 гигабайта.
Для возможности ипользования модели воксельной графики было разработано множество алгоритмов, которые нашли большое применение для работы с двухмерной графикой. Основа этих алгоритмов использование древовидных структур, позволяющих описывать состояние не для одного конкретно вокселя, а для некоторой их совокупности. В простейшем случае воксель представляется состоящим из восьми вокселей меньшего размера, те в свою очередь, также разбиваются на восемь меньших кубов и так далее. При таком подходе, область пространства имеющая одинаковые характеристики всех вокселей из которых она состоит может быть описана одним большим вокселем, уменьшая таким образом объём необходимой памяти для хранения воксельного пространства.


#1
21:04, 19 окт. 2012

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

#2
22:39, 20 окт. 2012

Vismar
> указатели убивают всю экономию
Только при наивной реализации

glukh
Группируем воксели в кубики 2х2х2=8 вокселей, в кубике держим маску 8 бит - воксель заполнен/пуст, маску 8 бит - воксель конечный/делится дальше
Если вторая маска <> 0, то добавляем 32битный указатель на первого кубика-потомка (они идут подряд, их может быть до 8x8=64), иначе кубик получается терминальный
Итого, считая всего N кубиков, нетерминальных будет N/64 (докажи сам) и уйдет байт:
6*N/64+2*N*63/64=132/64*N на N*8 вокселей или 2,1 бит/воксель

#3
23:42, 20 окт. 2012

Ладно,понимаю то, что ты до сих пор сидишь на 32битной системе. Хотя, хоть убей, не понимаю смысла сидеть на 32битной системе при работе с вокселями. Ладно, вижу примитивный способ хранения в виде обычного октодерева разреженного. А вот дальше ты как-то забыл именно про указатели. Когда, пускай и 32битный  указатель, указывает на ноду из 8 вокселей, а таких нод,извини меня,на нормальных уровнях детализации, может быть несколько миллионов(и даже до миллиарда доходит при вменяемых уровнях детализации). Тогда простейшее перемножение покажет, что указатели будут сжирать даже больше,чем сами воксели.
Хранение именно самих вокселей(геометрии без цвета и указателей на ноды) не требует больше 1 бита на воксель. Вопрос состоит именно в том, что чем больше нод, тем тяжелее хранить все данные в памяти. В виде простого массива данных хранение неуместно по понятной причине, через указатели хранить глубокие уровни тяжело по причине количества нод(в частности таких элементарных, как 2х2х2). Поэтому сия реализация не даст хранить больше 7-8 уровней детализации(если полностью забивать все вокселями) в пределах 8 Гб(с учетом 64битных указателей, кои будут присутсвовать в любом случае).
А реализация воксельной геометрии с максимальным уровнем детализации 4-5, никого особо не интересует.

#4
9:43, 21 окт. 2012

Vismar
> Ладно,понимаю то, что ты до сих пор сидишь на 32битной системе
Указатель=индекс в массиве, как нетрудно догадатся, схема выше для файлов размером до 4Гб, если это тебе мало, замени на 64битный указатель
> Когда, пускай и 32битный указатель, указывает на ноду из 8 вокселей, ... Тогда простейшее перемножение покажет, что указатели будут сжирать даже
> больше,чем сами воксели.
Прямо поток сознания какой-то
Перечитай мой пост, или арифметические расчеты тебе не доступны?

#5
9:55, 21 окт. 2012

Ок,индекс в массиве. А ты уверен, что ты сможешь все время выделять по 4Гб+?Одним единым массивом. Я в этом сильно сомневаюсь

#6
10:18, 21 окт. 2012

Vismar
> А ты уверен, что ты сможешь все время выделять по 4Гб
А это уж технические детали. Можно одним блоком выделить, можно кусками, индекс легко дешифровать, к примеру старшие биты=номер куска, остальные-смещение
Да и гигабайты - это жирно, ведь хранятся по большому счету только поверхностные воксели

#7
11:20, 21 окт. 2012

Выделение одного жирнющего блока в гигабайт и больше, вполне вероятно может не произойти по понятным причинам. Ну и да, разделение на куски вполне правильная мысль.
Однако,гигабайты на 1 объект вполне могут уйти,если он достаточно большой. К примеру,можно взять тот же ландшафт со сложной поверхностной геометрией. Поэтому,разделение его на части необходимо.
Однако, не стоит забывать и про главную плюшку воксельной геометрии, ее можно изменять на лету. Но если хранить ее статичными блоками, то возникает трудность с переаллоцированием памяти, ведь переаллокация больших кусков памяти занимает немало времени. Да и требует дополнительных трат памяти на момент аллокации.
Лично в моей реализации,я добился того, что ~134,5*10^6 вокселей занимает у меня ~128Мб, что вполне терпимо. Но это чистая геометрия, без цвета. Вот с цветом состоит наибольшая проблема, так как каждый воксель требует 3 байта на цвет (если без альфа канала). Хоть и есть вариант с хранением урезанной цветовой палитры на объект(тогда хранение индекса цвета занимает меньше памяти(в зависимости от разрешения палитры), а хранение палитры в виде 3д текстуры еще позволяет сжимать ее саму. Но все равно получается слишком много. Хотя Йон Олик предлагал на сиграфе некий хитры способ сжатия цветов для нод, но я по его презентации не понял алгоритма... Возможно есть другие идеи?

#8
11:55, 21 окт. 2012

Vismar
Посмотрел твой сайт, вижу ты спец по вокселям
Меня больше интересует удаление перекрытых объектов, SVO только как средство, в теме про UD я набросал идею использования SVO+HiZ
Сами "воксели" могут быть и кубами со скошенными краями, как в Marching Cube

> Однако,гигабайты на 1 объект вполне могут уйти,если он достаточно большой. К примеру,можно взять тот же ландшафт со сложной поверхностной геометрией
Мне понравилось как сделано в Voxelshtein 3D, та явно не гигабайт, но если добавить Marching Cube, смотрелось бы вообще отлично...

> Лично в моей реализации,я добился того, что ~134,5*10^6 вокселей занимает у меня ~128Мб, что вполне терпимо.
Около байта на воксель? У людей вообще чуть ли не один бит, это вместе с указателями/индексами
> Вот с цветом состоит наибольшая проблема, так как каждый воксель требует 3 байта на цвет (если без альфа канала)
Может не надо хранить для каждого вокселя? Сравни с текстурами, в играх они тоже не размером с уровень, условно говоря на каждую точку по текселю, либо тайлятся, либо растягиваются
Или както хранить разницу с родителем/соседями, ее проще сжать

#9
19:31, 21 окт. 2012

Aslan
> Меня больше интересует удаление перекрытых объектов, SVO только как средство, в
> теме про UD я набросал идею использования SVO+HiZ
> Сами "воксели" могут быть и кубами со скошенными краями, как в Marching Cube
То есть ты хочешь реализовать полигонизацию вокселей?Или ты при рендере преобразуешь их в поверхности? Просто второе как-то интереснее.Aslan
> Мне понравилось как сделано в Voxelshtein 3D, та явно не гигабайт, но если
> добавить Marching Cube, смотрелось бы вообще отлично...
Ну,у Кена там вся карта имеет разрешение 2048*2048*128 вокселей. Что немного. И при том каждый из вокселей имеет свой цвет. Ну и рендерится там в неком смысле волновым алгоритмом(правда,как сам Кен сознался на форуме, когда он писал алгоритм, даже не знал о волновом рендере), хоть и жутко переделанным.
Aslan
> Около байта на воксель? У людей вообще чуть ли не один бит, это вместе с
> указателями/индексами
Ну, я не считаю свою реализацию идеальной,но пока написал о том, чего достиг. По сути, могу избавиться еще от кучи указателей, но прошу заметить, что при своем допустимом максимальном разрешении дерева, я использую 8^7 указателей, а это всего-то 2 Мб, в то время,как вокселей в дереве будет аж 8 589 934 592, и занимать они будут ровно 1 Гб.
Поэтому я считаю, что количество указателей даже можно и не уменьшать, так как  это не даст особого выигрыша.
Aslan
> Может не надо хранить для каждого вокселя? Сравни с текстурами, в играх они
> тоже не размером с уровень, условно говоря на каждую точку по текселю, либо
> тайлятся, либо растягиваются
> Или както хранить разницу с родителем/соседями, ее проще сжать
Как таковое, хранить именно цвет у каждого вокселя и вправду глупо, а идея с хранением разницы очень мне нравится и я пытаюсь с ней что-то сделать,но все равно я вечно натыкаюсь на то, что соседние воксели могут иметь достаточно большую разницу в цвете, что в итоге не даст сжать объем. Но и идея некой 3д текстуры(ну или просто ограниченной палитрой цветов для каждого объекта) меня прельщает,так как действительно позволяет уменьшить размер индекса цвета, но этого все равно не достаточно.

#10
20:31, 21 окт. 2012

Vismar
> То есть ты хочешь реализовать полигонизацию вокселей?Или ты при рендере преобразуешь их в поверхности? Просто второе как-то интереснее.
Нет, просто октодерево, про воксели забудь. Можно сделать кубики со скошенными краями, во что интересно, но это потом
Пока хочу выработать алгоритм удаления перекрытых кубиков

> я использую 8^7 указателей, а это всего-то 2 Мб, в то время,как вокселей в дереве будет аж 8 589 934 592, и занимать они будут ровно 1 Гб
Вот это я не понял, на каждые 8 вокселей надо 1 указатель или как?

> идея с хранением разницы
Надо чтото вроде JPEG-сжатия. Потом цвет родителя пригодится и при трассировке, сильно удаленные воксели не трассировать "вглубь", получается как мипмап уровни для текстуры

#11
20:34, 21 окт. 2012

Vismar
succinct trees.

#12
20:38, 21 окт. 2012

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

#13
22:19, 21 окт. 2012

Aslan
> Вот это я не понял, на каждые 8 вокселей надо 1 указатель или как?
Я использую разрешение нод 16*16*16. То есть использую указатель на этот кубик. Меньшее разрешение нод не использую, позволяет снизить затраты на указатели(pointers). Идейку сию прихватил от гигавокселей из их документации.
Aslan
> Нет, просто октодерево, про воксели забудь. Можно сделать кубики со скошенными
> краями, во что интересно, но это потом
> Пока хочу выработать алгоритм удаления перекрытых кубиков
Хм, сложность возникает пропорционально количеству возможных вариантов скосов. Но,все же я думаю, не столь сложно это сделать, скорее отладка займет времени много.
Aslan
> Надо чтото вроде JPEG-сжатия. Потом цвет родителя пригодится и при трассировке,
> сильно удаленные воксели не трассировать "вглубь", получается как мипмап уровни
> для текстуры
> Такая мыслишка, разницу (с родителем) можно хранить подобно float, т.е. с
> фиксированной относительной точностью. Мантисса, порядок (степень двойки). Абс.
> ошибка нас не колышет, главное чтобы глазом не было заметно. Тогда можно сжать
> до нескольких бит. Можно даже наращивать яркость не линейно, а более крутым
> графиком, скажем экспоненциально, хранить собст-во не y, а x графика и сверять
> с таблицей
> В родителе держим среднее арифмет непосредственных потомков
Порылся снова в презентации Йона, более менее разобрался с его принципом,но надо посидеть за листком с ручкой и посчитать выигрыш в памяти да и в сложности доступа и сжатия этого чуда...
Там группирование по разнице с определенной разницей и хранение именно разницы...И даже хранение разницы разниц..Запутанно довольно. Надо все посчитать...

#14
14:13, 22 окт. 2012


Я не интересовался ранее этой темой, и прошу пояснить пару моментов:
Vismar
> указатели убивают всю экономию
Зачем вообще указатели на воксель пространство? Почему бы не хранить данные изначально в структуре с известной иерархией.
Например, для октодерева есть/нет вокселя с глубиной три, просто записываем данные в порядке маска первого узла, маска второго 1, маска третьего 1...8, маска второго 2... итд. И в циклах перебора вокселей шаг 73 байта для узлов первого уровня (1+8+64), 65 для узлов второго уровня (1+64) итд.

Vismar
> я вечно натыкаюсь на то, что соседние воксели могут иметь достаточно большую
> разницу в цвете
Почему нельзя сначала плавно передать цвет по октодереву, а потом в отдельной структуре описать воксели с резко отличающимся цветом (их гораздо меньше?).

Страницы: 1 2 3 4 Следующая »
3DTetraWavesФорумОбзор существующих алгоритмов

Тема в архиве.