2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Сверхбыстрый рендеринг. Что скажет математика?
Сообщение16.11.2014, 22:07 


16/11/14
228
Давно хотелось обсудить тему из области компьютерной графики с упором на математику. На мой взгляд очень фундаментальную тему, касательно вопроса мгновенного вывода фотореалистичного изображения. Давайте сразу поясню в чём суть задачи:

Задача. Имеем миллион лучей и миллион сфер в трехмерном пространстве(сфера задана декартовыми координатами), расположенных хаотично. Требуется найти пересечение каждого конкретного луча со сферой.

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

Собственно, сам вопрос, с изрядной долей философии: "А возможно ли вообще эффективно решить эту задачу?". Возможно ли разработать такой алгоритм, который бы ускорил процесс вычисления в миллионы(да, да не меньше) раз? На практике лучей и сфер может быть в разы больше.

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение16.11.2014, 22:10 


28/11/11
2884
EngineEnergy в сообщении #932042 писал(а):
касательно вопроса мгновенного вывода фотореалистичного изображения

EngineEnergy в сообщении #932042 писал(а):
Требуется найти пересечение каждого конкретного луча со сферой.

Это какие-то разные вещи, всё-таки.

EngineEnergy в сообщении #932042 писал(а):
расположенных хаотично

Конкретно как? Просто неизвестно их расположение, или оно как-то таки генерируется?

-- 16.11.2014, 22:13 --

Так же поясните: что Вы понимаете под пересечением?

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение16.11.2014, 22:29 


16/11/14
228
Нет не разные. Графика - это та же математика. От качественных вычислений зависит очень многое. Выше я не упомянул что имею в виду технику "трассировки лучей".

Хаотично - значит со случайными координатами (x, y и z) в пространстве. Представьте что сферы - это молекулы воздуха, на которые мы направили лазерный луч. Требуется узнать с какими "молекулами" в данный момент времени пересекается лазерный луч.

Пересечение - это столкновение луча со сферой. Вы умеете находить точки пересечения луча со сферой, плоскостью или тором в пространстве?

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение16.11.2014, 22:36 


28/11/11
2884
EngineEnergy в сообщении #932061 писал(а):
Выше я не упомянул что имею в виду технику "трассировки лучей".

Зря я тогда говорить начал. Ничего не знаю на эту тему.

(Оффтоп)

EngineEnergy в сообщении #932061 писал(а):
Хаотично - значит со случайными координатами (x, y и z) в пространстве.

Просто я читал, что иногда удаётся использовать специфику конкретного генератора случайных чисел.

EngineEnergy в сообщении #932061 писал(а):
Пересечение - это столкновение луча со сферой. Вы умеете находить точки пересечения луча со сферой, плоскостью или тором в пространстве?

Мне непонятно: почему Вы в формулировке именно трёхмерные сферы упоминаете? Что ли, лучи направляются под произвольными углами?

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение16.11.2014, 22:53 
Заслуженный участник


27/04/09
28128
EngineEnergy
Ну найдёте вы пересечения (и даже новый луч) — а дальше что? Не факт, что отражённый луч не попадёт в какую-нибудь другую сферу.

EngineEnergy в сообщении #932061 писал(а):
Графика - это та же математика.
Знатная путаница понятий. Если что-то использует математику, это не значит, что это — математика.

EngineEnergy в сообщении #932042 писал(а):
На практике лучей и сфер может быть в разы больше.
Ну и разделите пространство на дерево вложенных кубиков, и рассуйте по ним сферы и лучи.

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение16.11.2014, 22:58 


28/11/11
2884
arseniiv в сообщении #932077 писал(а):
Не факт, что отражённый луч не попадёт в какую-нибудь другую сферу.

Про отражения ничего сказано не было. А вообще интересно откуда задача.

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение16.11.2014, 23:20 


16/11/14
228
arseniiv писал(а):
Ну найдёте вы пересечения (и даже новый луч) — а дальше что? Не факт, что отражённый луч не попадёт в какую-нибудь другую сферу.

Верно. Но это можно пока проигнорировать.

arseniiv писал(а):
Знатная путаница понятий. Если что-то использует математику, это не значит, что это — математика.

В данном случае - это почти чистая математика + сложные алгоритмы. Математика используется везде. Вопрос лишь в том насколько глубоко, в каком объеме.

arseniiv писал(а):
Ну и разделите пространство на дерево вложенных кубиков, и рассуйте по ним сферы и лучи.

Не выйдет. Эта техника визуализации является не слишком эффективной.
Вычислять и вычислять. В практическом использовании годится мало.

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение16.11.2014, 23:55 
Заслуженный участник


27/04/09
28128
longstreet в сообщении #932078 писал(а):
Про отражения ничего сказано не было.
Меня смутило вот это:
EngineEnergy в сообщении #932042 писал(а):
фотореалистичного изображения


EngineEnergy в сообщении #932085 писал(а):
Не выйдет. Эта техника визуализации является не слишком эффективной.
Вычислять и вычислять. В практическом использовании годится мало.
Почему не выйдет? Допустим, сферы распределены внутри какого-то куба «хорошо». Разобъём его на $N^3 < S$ кубиков со в среднем $S/N^3$ сферами в каждом, определим каждую сферу в свой(и) кубик(и). Потом для каждого луча найдём кубики, в которые он попадает. Это, если не ошибаюсь, можно сделать за $O(N)$. Кубиков получится тоже $O(N)$. Теперь проверяем $O(N\cdot S/N^3)$ раз проверяем пересечения со сферами в кубиках. Итак, на один луч при проверке с каждой сферой $S$ проверок, а при этом подходе — $c S/N^2$, где [дальше поменял текст] $c$ вряд ли сравнится с правильно выбранным $N^2$. А если сравнится, то распределение сфер должно быть ужасным…

Что не так?

 Профиль  
                  
 
 Posted automatically
Сообщение17.11.2014, 10:13 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Тема перемещена из форума «Дискуссионные темы (М)» в форум «Математика (общие вопросы)»

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение17.11.2014, 10:58 
Аватара пользователя


31/10/08
1244
Это называется квадва-деревья. Стандартная техника рендеринга, применяется во всех движках. Или почти во всех.

EngineEnergy в сообщении #932085 писал(а):
Не выйдет. Эта техника визуализации является не слишком эффективной.
Вычислять и вычислять. В практическом использовании годится мало.

С чего вдруг не эффективной? Дайте оценку и сравните с алгоритмом из сообщения p932042

(Оффтоп)

EngineEnergy в сообщении #932042 писал(а):
На мой взгляд всё просто и понятно. Но вся сложность заключается в том, что обычным перебором (миллион лучей * миллион сфер) проблему не решить. Каждый конкретный луч требуется сопоставить с каждой конкретной сферой

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение17.11.2014, 10:58 


07/08/14
4231
если известны координаты сфер и координаты лучей (кстати, как они задаются?) то в чем может быть проблема?

-- 17.11.2014, 11:05 --

EngineEnergy в сообщении #932042 писал(а):
Имеем миллион лучей и миллион сфер

может это заменить на "Имеем миллион источников света и миллион сфер..." ?

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение17.11.2014, 18:17 


16/11/14
228
Pavia в сообщении #932239 писал(а):
Это называется квадва-деревья. Стандартная техника рендеринга, применяется во всех движках. Или почти во всех.

квадра-октри-деревья, как и бинарное разбиение пространства - отнюдь не сахар. Вы правы, это вполне стандартная техника, которая не решает многих проблем. Но в теме поста я делал немалый акцент на самой возможности существования более продуктивной техники рендеринга как альтернативе упомянутого.

Pavia в сообщении #932239 писал(а):
С чего вдруг не эффективной? Дайте оценку и сравните с алгоритмом из сообщения .

Под понятием "эффективность" можно понимать очень широкий спектр конечного результата. В данной задаче за критерий эффективности следует понимать количество шагов для получения конкретного результата. А именно найти пересечение одного луча и миллион сфер за 30 тактов/шагов. То есть с помощью обычного перебора - где каждая проверка является шагом - это будет невозможно сделать. Мы проверим всего лишь 30 сфер из миллиона. В алгоритмах приведенных выше ситуация обстоит значительно лучше, но в критерий 30 шагов отнюдь не укладывается и, следовательно, вопрос эффективности можно уже опустить касательно данных алгоритмов.


upgrade в сообщении #932240 писал(а):
если известны координаты сфер и координаты лучей (кстати, как они задаются?) то в чем может быть проблема?

Проблема в её сложности, не в качестве самого решения, а его эффективности, когда дело идёт о работе с очень большим массивом данных.


upgrade в сообщении #932240 писал(а):
может это заменить на "Имеем миллион источников света и миллион сфер..." ?

Напомните, из чего состоит каждый источник света? Из лучей. Любой источник света испускает собой лучи. В задаче был дан источник света, испускающий один миллион лучей.

Для каждого луча можно определить свои варианты:

1. Луч не пересекается ни с одной из сфер.
2. Луч пересекается с какой-либо сферой.
3. Луч пересекается одновременно с двумя или большим количеством сфер.

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение17.11.2014, 19:32 
Аватара пользователя


01/04/14
227
Санкт-Петербург
EngineEnergy в сообщении #932502 писал(а):
Напомните, из чего состоит каждый источник света? Из лучей. Любой источник света испускает собой лучи.

Источник света, состоящий из лучей и испускающий лучи - это нонсенс.

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение17.11.2014, 19:45 
Аватара пользователя


31/10/08
1244
EngineEnergy
$N=1000000$ - число лучей
$M=1000000$ - число шаров.
1) Тривиальный алгоритм
$T_1(N\cdot M)$
2) Алгоритм на основе kd-дерева
$T_2(M\cdot Log_2(M))+T_1(N\cdot Log_2(M))$
3) Очевидно, что оптимальный случай - это перебрать всех лучей ровно 1 раз.
$T_1(N)$

Так вот 2) меньше 1) он более оптимален.
Если приравнять $T_1=T_2$ и подставить числа получим
40 шагов на луч, что больше дополнительного условия.
Думаю достаточно для следующего луча проверку по дереву начинать с узла предыдущего луча. Тогда в худшем случае нам понадобится 40 проверок на луч. А в лучшем 1.

-- Пн ноя 17, 2014 21:15:06 --

PS. Думаю что можно придумать алгоритм близкий к оптимальному. Дерево можно представить массивом. Тем самым свести поиск элемента можно вести по аналогии, как это делается при поиске K-статистики. А для неё известен алгоритм поиска O(N) в не отсортированном массиве.

 Профиль  
                  
 
 Re: Сверхбыстрый рендеринг. Что скажет математика?
Сообщение17.11.2014, 23:47 


16/11/14
228
Pavia в сообщении #932548 писал(а):
EngineEnergy
40 шагов на луч, что больше дополнительного условия.
Думаю достаточно для следующего луча проверку по дереву начинать с узла предыдущего луча. Тогда в худшем случае нам понадобится 40 проверок на луч. А в лучшем 1

Довольно интересно. Уже ближе к цели. Правда, 40 проверок это весьма не мало, если помножить на миллион. В хаотичной сцене худший сценарий будет часто преобладать. Идеалом является осуществление всего одной проверки на каждый луч вне зависимости от роста числа сфер в пространстве. Такой подход практически малоосуществим.

Поэтому чтобы уложиться в заданные выше 30 или меньшее количество шагов - стоит подумать об отсечение "неправильных" сфер ровно в два раза на каждом последующем шаге.
Привести алгоритм к: 2^(количество проверок) = (количество сфер).

По такому принципу задача может быть относительно эффективно решена.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 32 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group