close

Вход

Забыли?

вход по аккаунту

?

Решение задачи поиска оптимальных алгоритмов компьютерных систем для синтеза трехмерных изображений.

код для вставкиСкачать
Известия ТулГУ. Технические науки. 2016. Вып. 2
Tsudickov Mikhail Borisovich, candidate of technical sciences, docent, tsudickov.mb@yandex.ru, Russia, Tula, Tula State University,
Balyasny Sergei Vicktorovich, candidate of technical sciences, chief of development
departament, sergo120@gmail.com, Russia, Tula, LLC "Alkor",
Chekhovsky Dmitry Valerievich, candidate of technical science , PCS Engineer, dmichekh@gmail.com, Russia, Tula, LLC "Rusautomation"
УДК 621.3
РЕШЕНИЕ ЗАДАЧИ ПОИСКА ОПТИМАЛЬНЫХ АЛГОРИТМОВ
КОМПЬЮТЕРНЫХ СИСТЕМ ДЛЯ СИНТЕЗА ТРЕХМЕРНЫХ
ИЗОБРАЖЕНИЙ
И.Е. Первак
Рассмотрены преимущества использования алгоритмов быстрой визуализации
для снижения временных и вычислительных затрат при одновременном достижении
высокого качества синтезируемого изображения.
Ключевые слова: оптимизация задачи визуализации, трассировка лучей, кубическая интерполяция.
Быстрый прогресс вычислительных средств, расширение их возможностей являются главными факторами все более широкого внедрения
их в различные сферы научной и практической деятельности. Исключительно интенсивное развитие получили в настоящий момент интерфейсы
информационно-измерительных систем, построенные с применением
средств машинной графики [1, 2].
Широкое применение подобных интерфейсов определяется высокой информативностью изображений. Информация, содержащаяся в изображении, представлена в наиболее концентрированной форме, для ее восприятия пользователю достаточно иметь относительно небольшой объем
специальных знаний. Причем стремление визуализировать информацию в
настоящее время наблюдается практически во всех сферах деятельности
человека, и эта информация, как правило, более доступна для анализа. Существует большое число алгоритмов для рендеринга объектов. Поэтому
задача сводится к поиску оптимального алгоритма, удовлетворяющего
временным и качественным характеристикам построения изображения.
Алгоритм визуализации сложных поверхностей, основанный на
трассировке лучей, позволяет напрямую визуализировать объекты, без
разбиения их на кривые или многоугольники. Основной операцией алгоритма является нахождение пересечения луча с поверхностью. Представив
уравнение луча в параметрическом виде
332
Информатика, вычислительная техника и обработка информации
→
→ →
r (t ) = r0 + τ t ,
→
(1)
→
где r0 – начало луча; τ – его направление, уравнение неявной поверхности для всех точек данного луча примет вид
→
→→
F ( r (t )) = f (r0 , τ , t ) = 0
(2)
f ( t ) = 0.
(3)
или просто
Уравнения (2) и (3) должны быть сформулированы и решены для
→→
достаточно большого количества лучей (r0 , τ ) , что приводит к очень вы-
сокой вычислительной нагрузке на систему визуализации. Только несколько функций, используемых в настоящее время при моделировании поверхностей, обеспечивают аналитическое решение уравнения (3), что делает
необходимым применение численных методов.
Алгоритм трассировки лучей предназначен для визуализации поверхностей, описываемых следующим уравнением:
→
n
→
F ( r ) = −T + ∑ Fi ( r ) ,
i =1
(4)
→
где T – величина порогового уровня, и каждая слагаемая функция Fi ( r ) ,
будучи параметризованной вдоль произвольного луча (1) как f (t ) , удовлетворяет следующим условиям:
- f (t ) является C 1 -непрерывной для всех t,
df (t )
- f (t ) и
отличны от нуля только на конечной совокупности
dt
неперекрывающихся отрезков [ t1i , t 2i ] и i=1...,k.
Второе условие подразумевает, что каждый объект, представленный функцией f, может быть ограничен некоторым объемом (не обязательно конечного размера). Например, функция поля бесконечной неявной
плоскости может быть ограничена бесконечной пластиной с гранями, параллельными этой плоскости.
В общем случае алгоритм требует задания как f ( t ) , так и f / ( t ) . В
специальном случае, когда f симметрична относительно средней точки отрезка [ t1 , t 2 ], производная f / ( t ) не требуется.
Поверхность, визуализированная с использованием предложенного
алгоритма, обладает следующими свойствами.
333
Известия ТулГУ. Технические науки. 2016. Вып. 2
1. Гладкость.
Алгоритм визуализирует объекты как С 1 -непрерывные поверхности. Поверхность закрашивается гладко без выпадения пикселов.
2. Мелкие детали.
Алгоритм отображает мелкие детали неявных поверхностей с такой же точностью, как и для обычных примитивов. Алгоритм не сможет
обнаружить поверхность только в том случае, если ее описывающая функ→
ция F ( r ) ограничена настолько малым объемом, что он оказывается между проецирующими лучами. Но это общая проблема всех алгоритмов
трассировки лучей, она достаточно известна и может быть решена на основе стохастических методов или передискретизации.
3. Ограниченная точность.
Изображенная поверхность может слегка сдвигаться от своего истинного местонахождения, заданного уравнением (5). Ошибка индивидуальна для каждой функции и не накапливается.
Сначала кратко опишем этот алгоритм, затем покажем, как он может быть расширен для визуализации поверхностей, удовлетворяющих
сформулированным ранее условиям.
В случае сферического объекта составляющие уравнения изоповерхности являются точечными потенциалами, заданными кусочнонепрерывными многочленами второй степени:
r 2
R

1
−
3
(
)
,
0
≤
r
≤
;

3
R
 3
r
R
f (r ) =  (1 − ) 2 ,
< r ≤ R;
(5)
2
3
R

0,
r > R,


где R – радиус влияния сферического компонента; r – расстояние от его
центра до рассматриваемой точки пространства.
Для нахождения пересечения луча с поверхностью уравнение луча
(1) подставляется в формулу для потенциала (5), образуя, по крайней мере,
три кусочно-непрерывных многочлена второй степени для каждого сферического объекта, описывающих его поле вдоль луча. После того, как все
сферические объекты обработаны описанным выше способом, часть луча,
расположенная внутри их общего поля, оказывается разделенной на ряд
отрезков с соответствующими многочленами, полученными из уравнения
(5). Алгоритм проходит через все эти отрезки, формируя и решая уравнение изоповерхности (4). Так как все компоненты представлены многочленами второй степени, то общее уравнение изоповерхности также имеет
вторую степень, и все его корни (следовательно, точки пересечения) могут
быть найдены аналитически.
334
Известия ТулГУ. Технические науки. 2016. Вып. 2
Для граничных точек первого подынтервала [t1 , t mid ] условие (7)
запишется в виде
(8)
f1 = 0, f / 1 = 0, f mid = f (t mid ), f / mid = f / (t mid ),
потому что функция f имеет нулевое значение и нулевую первую производную на границе ее зоны влияния. Если функция f симметрична относительно средней точки t mid , то четвертое условие примет вид
(9)
f / mid = 0.
Уравнения (8), решенные для подынтервалов [t1 , t mid ] и [t mid , t 2 ] ,
дают в итоге кусочно-непрерывное представление функции f на отрезке
[t1 , t 2 ] , удовлетворяющее сформулированным выше требованиям: низкая
степень; C 1 -непрерывность, вычислительная эффективность.
Так же, как и для любого случая, где используется аппроксимация,
важно получить границы для возникающих при этом ошибок. В случае интерполяции Эрмита в n узлах x1 , x 2 ,... x n ошибка
ε(t ) =
f
(ξ)
[ Ln (t )]2 ,
( 2n )!
( 2n )
(10)
n
где Ln (t ) = ∏ (t − xi ) , точка ξ принадлежит интервалу, содержащему все
i =1
x i и текущую координату t.
Здесь x i обозначает положение узлов интерполяции, его не следует путать
с граничными точками первоначального отрезка [t1 , t 2 ] .
Как видно из формулы (10), ошибка может быть уменьшена за счет
увеличения числа узловых точек n в пределах первоначального интервала
[t1 , t 2 ] (см. рисунок). С другой стороны, можно зафиксировать число узловых точек n и разбить первоначальный интервал [t1 , t 2 ] на меньшие подынтервалы, тем самым снижая величину множителя Ln . Оба метода
очень эффективно уменьшают ошибку. Однако увеличение числа узловых
точек до n приводит к тому, что степень интерполяционного многочлена
становится равной (2n-1), что делает невозможным аналитическое нахождение корней при n >2.
Таким образом, было решено использовать кубическую интерполяцию (n=2) и увеличивать число подынтервалов. На каждом подынтервале
[ x1 , x 2 ] ошибка
f 4 (ξ )
[(t − x1 )(t − x2 )] 2 .
24
Так как ошибка зависит от величины x1 − x 2 , возведенной в четвертую степень, удвоение числа подынтервалов на первоначальном отрезке уменьшает ошибку в 16 раз.
ε (t ) =
336
Информатика, вычислительная техника и обработка информации
Алгоритм может быть оптимизирован для решения некоторых частных задач визуализации.
1. Вычисление аппроксимирующих полиномов только в случае необходимости.
Если при формировании объекта не используются операции булевой алгебры, то не требуется расчет всех полиномов вдоль луча, достаточно подготовить лишь список подинтервалов i1 ,...i n . Соответствующий интерполяционный многочлен p i рассчитывается лишь при необходимости в
процессе обработки алгоритмом списка подинтервалов. Процесс останавливается после нахождения первой точки пересечения. Это может значительно уменьшить число вызовов подпрограммы построения интерполяционных многочленов.
2. Быстрая проверка условия пересечения луча и поверхности.
Прежде чем вычислять точку пересечения, некоторое предварительное исследование описывающей функции поверхности может ускорить проверку существования такого пересечения. Например, если сумма
максимальных значений всех слагаемых функции f i меньше величины
n
порогового уровня Т, то уравнение неявной поверхности
∑ fi
i =1
= Т не име-
ет корней и не на одном из подынтервалов i1 ,...i n не существует точки пересечения. Такая проверка особенно эффективна, если функции f i симметричны относительно середины их интервалов, где поле достигает максимального значения (это справедливо для неявных точек, прямых, торов и
плоскостей).
Аналогичная проверка на наличие корней может использоваться на
некотором интервале i j = [ x1 , x 2 ] , на котором заранее известно, что функция f является монотонной. Если Т не содержится между f ( x1 ) и f ( x 2 ) ,
то на отрезке i j пересечений не существует, и алгоритм может переходить
к следующему отрезку i j +1 , минуя процесс интерполяции и вычисления
n
корней. Для того, чтобы функция f = ∑ f i была монотонной, необходимо
i =1
проверить, что все ее слагаемые f i одновременно не убывают (не возрастают) на этом интервале.
Уменьшение временных и вычислительных затрат при одновременном достижении высокого качества синтезируемого изображения достигается за счет использования в методе трассировки лучей аппроксимации
значений скалярного поля вдоль луча многочленами Эрмита.
337
Известия ТулГУ. Технические науки. 2016. Вып. 2
Список литературы
1. Роджерс Д. Алгоритмические основы машинной графики. М.:
Мир, 2009. 504 с.
2. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика.
М.: Радио и связь, 2013. 224 с.
Первак Ирина Евгеньевна, канд. техн. наук, доц., irapervak@mail.ru, Россия,
Тула, Тульский государственный университет
SOLUTION TASK OF FINDING THE OPTIMAL ALGORITHM COMPUTER SYSTEMS
FOR SYNTHESIS OF THREE-DIMENSIONAL IMAGES
I.E. Pervak
The advantages of using fast imaging algorithms to reduce time and computational
cost while achieving the high quality of the synthesized image.
Key words: optimization of imaging tasks, ray tracing, cubic interpolation.
Pervak Irina Evgenevna, сandidate of
irapervak@mail.ru, Russia, Tula, Tula State University
338
technical
sciences,
docent,
Документ
Категория
Без категории
Просмотров
4
Размер файла
349 Кб
Теги
оптимальное, решение, алгоритм, синтез, трехмерная, система, компьютерные, изображение, задачи, поиск
1/--страниц
Пожаловаться на содержимое документа