Войти
ПрограммированиеФорумГрафика

Ray casting, SVO и отбраковка невидимых вокселей

Страницы: 1 2 Следующая »
#0
12:26, 16 ноя. 2011

Как мне скастить луч с логарифмической сложностью? Везде пишут о том, что такой способ есть, но алгоритм никто не даёт. Цитата из википедии:

Выделив неинтересные для отображения части пространства еще до рендеринга, можно значительно уменьшить количество вычислений при рейкастинге или смешивании текстур. В зависимости от используемого алгоритма, вычислительная сложность уменьшится от O(n) до O(log n)

http://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%8A%D1%91%D0%BC%D0%BD… 8%D0%BD%D0%B3

Где можно прочитать про такой алгоритм? Желательно, с картинками и на русском языке.


#1
12:42, 16 ноя. 2011

Antilegent
нигде не почитаешь, предполагаю, без препроцесса не обойтись.

#2
13:10, 16 ноя. 2011

рейкастинг тоже не нужен.

#3
14:36, 16 ноя. 2011

Antilegent
обычный Oct-tree дает логарифмическое число проверок

#4
14:56, 16 ноя. 2011

Aslan
это да, первое что идет в голову, но мысль дальше:
обычно воксели используются для высокой детализации, и модели такие весят очень много, если я не ошибаюсь, то воксельная модель собра из демки инвидии весила около 1,7г, а теперь представим сколько будет весить дерево? наверно очень очень много и врятли это жизнеспособно, но автору попробовать можно, и даже употребить, чуть чуть

#5
15:27, 16 ноя. 2011

На картинке изображено дерево, высота которого равна четырём. Серые кубики - это воксели, а белые - пустое пространство.

Рейкастинг для SVO | Ray casting, SVO и отбраковка невидимых вокселей

Как я могу за 4 итерации вычислить самый первый воксель, с которым пересекается красный луч?

Aslan

> обычный Oct-tree дает логарифмическое число проверок

Да. Для того, чтобы вычислить воксель с известными координатами. А как за логарифмическое число проверок вычислить коксель, чьи координаты неизвестны?

#6
18:09, 16 ноя. 2011

Antilegent
А чего воксели то, полигоны не устраивают?
Или просто нужна реалистичная картинка?

#7
19:03, 16 ноя. 2011

Antilegent
> А как за логарифмическое число проверок вычислить коксель, чьи координаты
> неизвестны?
Это как вообще? Что это за воксель без координат?

#8
19:20, 16 ноя. 2011

VirT

> Это как вообще? Что это за воксель без координат?

Координаты то у него есть, но как узнать, что это именно тот воксель, с которым пересекается луч? Ведь на пути между началом луча и вокселем лежит очень много пустых клеток.

nes

> А чего воксели то, полигоны не устраивают?

Полигоны во Флеше хреново выглядят. Картинка получается на уровне первой Кваки.

#9
19:31, 16 ноя. 2011

Antilegent
> На картинке изображено дерево
Неправда, на картинке изображен квадрат.

Не надо делить пространство на равные части, используй адаптивное деление, дели на зоны с данными и зоны без данных.

#10
19:51, 16 ноя. 2011

Antilegent
>Полигоны во Флеше хреново выглядят. Картинка получается на уровне первой Кваки.
Ну так возьми С++ + OGL или С# + D3D и в перед )
По вопросам С++ помогу чем смогу )

#11
1:01, 17 ноя. 2011

Antilegent
> до O(log n)
Полагаю, это лучший возможный (частный) случай. А на картинке представлен худший случай, часто придётся спускаться на самые нижние уровни дерева, чтоб определить, есть ли воксель. Могу ошибаться, сам ещё не придумал.

#12
11:00, 17 ноя. 2011

Antilegent
Ты прав, сложность нифига не логарифмическая, в общем случае степенная (с показателем < 1)
Для 3Д луч, пересекающий куб, может пересечь максимум 4 его подкуба (каждый переход - это пересечение одной из 3х плоскостей XY,YZ,XZ,  луч пересекает кажд.плоскость не более 1 раза)
Считая дерево везде равной глубины d, кол-во узлов - N=8^d, макс.кол-во проверок - 4^d=N^(1/2)

Есть надежда на ЛОД - если тебе рейкаст нужен именно для отображения
Когда размер подкубика с учетом удаления от глаза становится меньше пиксела - выходишь из рекурсии, вроде должно помощь для протяженных моделей

Еще можно использовать схожесть трассы для соседних лучей, я сам еще не продумал эту идею

Бить не обязательно на Oct-tree, даже не нужно
Плоскостями (BSP), параллельными любым двум осям координат
Можно проводить так чтобы дерево стремилось к сбалансированному
max(left,right) -> min
left,right - число граней или вокселей слева и справа при разбиении, считая и пересеченные разделяющей плоскостью

ПРАВКА
Гугл дал кучу ссылок по Sparse Voxel Octtree
http://www.tml.tkk.fi/~samuli/publications/laine2010i3d_paper.pdf

#13
11:15, 17 ноя. 2011

не знаю в тему будет ли или нет, но когда делал модификацию POM'a,  т.е рейкастинг тот же самый, но доваил туда  квадтри, то за log почти никогда не желались выборки, - это самый самый лучший случай, потому что между нодами приходилось прыгать, т.е шел внутри нода, а тут фигак и в соседний нод, и так еще много чего + на более верхние уровни подниматься надо, так что тут хз как за логирфм что-то трассировать.

#14
14:12, 17 ноя. 2011

Antilegent
> Как я могу за 4 итерации вычислить самый первый воксель, с которым пересекается красный луч?
во-первых, логарифмическая сложность обеспечивается в average case, worst case по-прежнему будет O(n). во-вторых даже если сложность логарифмическая, при ней будет какая-то константа.

Страницы: 1 2 Следующая »
ПрограммированиеФорумГрафика

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