- Aslan
- Забанен
Вот вы опять всё про деревья сразу. Ну вот зачем, объясните мне зачем сразу подтягивать наследование, когда цель не сверх хитрая адресация вокселей а просто их визуализация, то есть растеризация на матрицу экрана. Что мешает также как предполагается делать у меня с тетраэдрами, делать тут волновым алгоритмом с квадратами расположенными вокруг наблюдателя? Проецировать по очереди в порядке дальности от наблюдателя, те воксели которые прозрачные, не растеризовать естественно, а те которые имеют цвет растеризовать в квадрат. Таким образом наблюдатель проходясь по глубине вокселей растеризует всю матрицу экрана, поверхностью построенную из вокселей. Примитивно, и не красиво, зато вполне реально можно заставить работать...
DanielSky
> Зачем вообще указатели на воксель пространство
Чтобы быстро переходить от родителя к детям при трассировке по дереву
В файле оно хранится без указателей
> Например, для октодерева есть/нет вокселя с глубиной три...
Так надо перебрать все узлы на текущем уровне, чтобы добратся до потомков на следующем, не годится
Впрочем указатели как раз мало отнимают, выше я написал как
glukh
Незнаю, как ты хочешь обойтись без деревьев, но очевидно, что видимые воксели несвязное множество
Как уже написали выше, указатели связывают куски геометрии в единый объект, так как использование больших статичных массив чревато 2 большими проблемами:
1)Хранение больших массивов в некоторых случаях невозможно по причине того, что приложение может и не аллоцировать нужный кусок
2)Изменение геометрии влечет за собой изменение данных, хранящихся в структуре. В при хранении всего в статичном массиве приходится переаллоцировать все, что занимает немало времени и дополнительных ресурсов.
С указателями же проблемы решаются,аллоцирование мелких частей проходит в 99% случаев, изменение некоторых участков геометрии не занимает много времени и не требует много ресурсов.
К тому же, хранение в виде дерева (не в полном смысле этого словосочетания) и вправду дает хороший прирост в скорости при нахождении нужных узлов. В том числе, позволяет снизить затраты памяти на геометрию (даже при хранении в виде массива, все равно используется разреженное октодерево).
glukh
> Вот вы опять всё про деревья сразу. Ну вот зачем, объясните мне зачем сразу
> подтягивать наследование, когда цель не сверх хитрая адресация вокселей а
> просто их визуализация, то есть растеризация на матрицу экрана. Что мешает
> также как предполагается делать у меня с тетраэдрами, делать тут волновым
> алгоритмом с квадратами расположенными вокруг наблюдателя? Проецировать по
> очереди в порядке дальности от наблюдателя, те воксели которые прозрачные, не
> растеризовать естественно, а те которые имеют цвет растеризовать в квадрат.
> Таким образом наблюдатель проходясь по глубине вокселей растеризует всю матрицу
> экрана, поверхностью построенную из вокселей. Примитивно, и не красиво, зато
> вполне реально можно заставить работать...
Если ты такой большой любитель традиционной растеризации, то держи ссылку(не знаю,видел ли):
http://www.rsdn.ru/article/alg/03-12-voxel.xml
И могу сказать, что растеризация вокселей дает менее красивый результат, так еще и производительность слабовата,по сравнению с рей кастингом(и рей трейсингом). Но это твое дело, можешь еще почитать исходники Voxlap, если интересно, думаю найдешь, а вот еще форум, где Кен писал об алгоритме рендера:
http://www.jonof.id.au/forum/index.php?topic=30.0
P.S.Если вспоминать переписку с Браниславом(автором Atomontage), то его принцип хранения геометрии так же не является простым октодеревом. По крайней мере, он мне тонко намекнул, что вся архитектура хранения легко переводится в октодерево. Поэтому, дерево нужно в любом случае. Вопрос в другом, как именно ты будешь его использовать.
P.P.S.Могу сделать рандомный вброс и ткнуть пальцем в небо, сказав, что может быть можно реализовать хранение вокселей с помощью графа и использовать всякие клевые алгоритмы(по типу Флойда Уоршела) для поиска нужных частей геометрии.
Aslan
> Чтобы быстро переходить от родителя к детям при трассировке по дереву
Но при трассировке же в начале пути луча очень маленькие стартовые субузлы, а в конце очень большие конечные субузлы (т.к. большая детализация уже не важна). Следоовательно, пробег по дереву будет не большой. А используемые указатели будут использоваться редко, т.к. объекты сбиваются в кучу, заполняя значительную часть узла, а указатели будут оказываться в перекрытой, уже не проверяемой области. Но проверка указателей на каждом шаге луча тоже замедлит алгоритм.
Может Вы проверяли, указатели действительно увеличивают производительность? Или сталкивались с подобными тестами других людей?
Aslan
> Проецировать по очереди в порядке дальности от наблюдателя, те воксели которые
> прозрачные, не растеризовать естественно,
Предположим персонаж смотрит на стену, между ним и стеной огурец. Как Вы растеризуете огурец? Можно перебрать все пустоты меж персом и стеной быстрее, чем октадеревьями?
Vismar
> Как уже написали выше, указатели связывают куски геометрии в единый объект, так
> как использование больших статичных массив чревато 2 большими проблемами:
> 1)Хранение больших массивов в некоторых случаях невозможно по причине того, что
> приложение может и не аллоцировать нужный кусок
> 2)Изменение геометрии влечет за собой изменение данных, хранящихся в структуре.
> В при хранении всего в статичном массиве приходится переаллоцировать все, что
> занимает немало времени и дополнительных ресурсов.
На счет изменения геометрии, почему нельзя изменить маленький кусок массива? Ведь изменения в основном носят характер переноса группы вокселей из одного узла в соседний.
DanielSky
Ну опиши, как ты без указателей будешь находить следующий узел на пути луча
Я ничего пока не проверял, алгоритм трассировки октодерева общеизвестен, предложи свой
> Предположим персонаж смотрит на стену, между ним и стеной огурец
Нахожу самый нижний подуузел, где находится камера, рисую его, пото соседей, задействую HiZ, если огурец пройдет тест, он будет отрисован
> Можно перебрать все пустоты меж персом и стеной быстрее, чем октадеревьями?
По моим расчетам нет, хотя пока не проверил на практике
Dag
> succinct trees.
это что за покемон? похоже на бредятину, о которой вещал делл.
DanielSky
> На счет изменения геометрии, почему нельзя изменить маленький кусок массива?
> Ведь изменения в основном носят характер переноса группы вокселей из одного
> узла в соседний.
Узлы могут удалять в большом количестве, и точно так же добавляться. Поэтому простой перенос не пойдет.Suslik
> это что за покемон? похоже на бредятину, о которой вещал делл.
Это этакий хаффман, только для манюсеньких повторений.
Vismar
> Если ты такой большой любитель традиционной растеризации, то держи ссылку(не знаю,видел ли):
> http://www.rsdn.ru/article/alg/03-12-voxel.xml
Фрустум нарисован на мире! Спасибо за ссылку.
Suslik
> > succinct trees.
> это что за покемон?
Это деревья, размер которых не далëк от теоретического минимума, где-то 2n bits для n узлов. К сожалению, ходить по ним не быстро удается. Но у Делла вроде по другому, только 5-20% .LAS файлов.
Тема что-то резко затихла, поэтому решил ее снова поднять.
Новый воксельштейн, почитать о том, что и как делал автор можно тут:
http://voxelstein3d.blogspot.com
Воксельный движок, рей трейс рендер. Правда разрешение жуткое...
Aslan
Там есть миниган и гранаты для этих целей =)
Aslan
Ну, таким извращением и я занимался, когда играл в воксельштейн =)
Помню, как полтора часа выдалбливал проход прямо из камеры на поверхность, был доволен как слон.
Ну, с тех пор и интересуюсь вокселями =) Правда изучаю их всего пол года
Vismar
> Новый воксельштейн
Кен Силверман написал новый и быстрый 3д-двигатель, который использует октри.
Тема в архиве.