автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Математическое и алгоритмическое обеспечение для системы визуализации в САПР

11-2 1158

На правах рукописи

Котов Дмитрий Сергеевич

МАТЕМАТИЧЕСКОЕ И АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДЛЯ СИСТЕМЫ ВИЗУАЛИЗАЦИИ

В САПР

Специальность 05.13.12 - Системы автоматизации проектирования (промышленность)

Автореферат диссертации на соискание учёной степени кандидата технических наук

Владимир 2011

Работа выполнена во Владимирском государственном университете.

Научный руководитель: доктор технических наук, профессор

ЛАНЦОВ Владимир Николаевич

Официальные оппоненты: доктор технических наук, профессор

Жигалов Илья Евгеньевич

кандидат технических наук Лобачёв Глеб Александрович

Ведущая организация: Нижегородский государственный

технический университет им. Р.Е.Алексеева 603950, Н.Новгород, ГСП-41, ул.К.Минина, 24. Дирекция ИРИТ.

Защита диссертации состоится "_" апреля 2011г. в_часов

на заседании диссертационного совета Д.212.025.01 при Владимирском государственном университете.

Отзывы в двух экземплярах, заверенных гербовой печатью организации, просьба направлять по адресу: 600000, г.Владимир, ул.Горького, 87, диссертационный совет Д.212.025.01.

С диссертацией можно ознакомиться в научной библиотеке Владимирского государственного университета за месяц до защиты.

Автореферат разослан «_»_2011 г.

Учёный секретарь диссертационного совета /у> д.т.н., профессор

МАКАРОВ Р.И.

ГОСУДАРСТВЕННАЯ БИБЛИОТЕКА

2011 ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

АКТУАЛЬНОСТЬ

Устойчивый рост сложности проектирования инженерных, строительных, архитектурных и конструкторских разработок в системах автоматизированного проектирования (САПР) привел к необходимости повсеместного использования визуальных представлений проектных решений па промежуточных и финальных стадиях выполнения проекта. Применение подсистем получения визуального представления проектных решений позволяет повысить эффективность проектирования. Процедура оценки визуального представления проектного решения является одной из ключевых при выполнении проекта в САПР.

При выполнении конструкторских и инженерных проектов в машиностроении визуализация позволяет представить, как будет выглядеть деталь, разрабатываемое покрытие (лак, краска) или целый механизм до их изготовления. Оценка визуального представления проектного решения на ранних стадиях позволяет внести изменения п проект до начала физического изготовления проектируемого объекта.

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

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

Следует отметить возрастающую актуальность визуализации. Это связано с тем, что всё больше организаций используют визуализацию при выполнении проектов в САПР, а также с ростом требований к качеству и детальности визуального представления проектных решений. Данный рост требований привёл к резкому росту затрат времени, требуемого на получение визуального представления проектного решения. Существующие алгоритмы, методы и подходы, применяемые для финальной визуализации, позволяют решить задачу синтеза реалистичных изображений, однако требуют для решения этой задачи выполнения значительного количества вычислений, что и является основной причиной больших затрат времени, требуемого на получение финальной визуализации проектного решения.

На получение одного кадра финальной визуализации может потребоваться от нескольких десятков минут до 100 часов и более. Количество кадров - от 1 до нескольких тысяч (десятков тысяч). Время, затраченное на получение визуальных представлений проектных решений, может составлять более половины времени выполнения всего проекта.

К числу лиц, внесших значимый вклад в решение задачи повышения эффективности решения уравнения визуализации относятся: Жигалов И.Е., Ланцов В.П.,

Востряков К.А., Галактионов В.А., Dutre P., Jensen W.A., Pharr М., Humphreys G., Whitted Т..

Сложность моделей расчёта освещения, используемых в финальных визуализациях, увеличивается с каждым годом. В частности, усложняются модели расчёта освещения от источников света, взаимодействия света с материалами поверхностей, расчёта распространения света внутри материалов и передающих сред. Увеличивается количество объектов и примитивов в сцене. Это требует выполнения всё большего количества вычислений для получения результата визуализации, что приводит к росту временных затрат, требуемых на визуализацию.

Проблема существенного увеличения времени, требуемого на визуализацию проекта, приводит к увеличению сроков выполнения проекта и снижению эффективности проектирования. Решением данной проблемы являются:

сокращение затрат времени на получение визуального представления проектного решения.

сокращение общего количества процедур создания визуальных представлений проектного решения.

Следуя из вышесказанного можно сделать вывод о том, что применение систем визуализации в САПР востребовано, а задача повышения скорости визуализации в системах финальной визуализации для САПР является актуальной. ЦЕЛЬ И ЗАДАЧИ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

ДЛЯ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЦЕЛИ необходимо решить следующие задачи:

1) Анализ существующих алгоритмов, методов и подходов организации процесса решения уравнения визуализации, ускорения трассировки лучей.

2) Разработка новых, более эффективных алгоритмов, методов и подходов численного решения уравнения визуализации, ускорения трассировки лучей.

3) Разработка информационного, математического и алгоритмического обеспечения системы визуализации для САПР.

НА ЗАЩИТУ ВЫНОСЯТСЯ

1) Алгоритм определения областей проявления ступенчатого эффекта цветовых переходов на создаваемом изображении

2) Метод сохранения и повторного использования информации об освещении сцены источниками света.

3) Подход компактного представления kd-дсрсва для систем трёхмерной визуализации.

4) Метод кластерной трассировки лучей

5) Структура ПО САПР и алгоритмы реализации разработанных методов

НАУЧНАЯ НОВИЗНА

Новые научные результаты, полученные в работе, состоят в следующем:

1) Предложен алгоритм определения областей проявления ступенчатого эффекта цветовых переходов на изображении, позволяющий существенно уменьшить объём данных, подаваемых на вход фильтра устранения ступенчатого эффекта цветовых переходов на создаваемом изображении по сравнению с аналогичными по назначению подходами, применяющимися в современных системах визуализации для САПР.

2) Предложен метод сохранения и повторного использования информации об освещённости трёхмерной сцены от источников света. Применение данного подхода позволяет ускорить процесс визуализации за счёт повторного использования координат пересечения лучей со сценой, полученных в ходе предыдущих визуализаций. Ускорение расчётов достигается благодаря использованию аппроксимации получаемых координат пересечения дополнительных лучей со сценой, что приводит к сокращению количества арифметических онераций при нахождении точки пересечения луча со сценой. Разработанный метод предусматривает вычисление результата визуализации для каждого И С в отдельности, что позволяет управлять вкладом каждого ИС в освещение сцены без необходимости повторного моделирования освещения сцены.

3) Разработан подход компактного представления 1«1-дерсва для систем визуализации, позволяющий сократить затраты памяти на хранение кс1-дерсва.

4) Разработан метод пошаговой трассировки лучей с механизмом классификации, и динамическим объединением лучей в группы - метод кластерной трассировки лучей.

ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ

На основе предложенных алгоритмов, методов и подходов была разработана система визуализации для САПР, обладающая следующими, по сравнению с методами и подходами, применяющимися в существующих решениях, преимуществами:

Меньшее на величину от 14,8 до 20,6% время устранения ступенчатого эффекта цветовых переходов в создаваемом изображении. Расчёт освещения, приходящего от ИС, выполняется быстрее на 15-18% Меньший (до 44%) объем памяти, требуемой для храпения структуры к(1-дерева.

Большая, до 30%, скорость визуализации с использованием предложенного компактного кс1-дерева.

Большая, на величину до 170%, скорость визуализации с использованием метода кластерной трассировки лучей.

Сравнение производительности осуществлялось на одинаковых тестовых сценах и одном и том же аппаратном оборудовании.

Полученные результаты исследований в виде программного обеспечения внедрены в производство на предприятии 000"АС-Студня". АПРОБАЦИЯ РАБОТЫ

Основные положения и результаты работа докладывались и обсуждались на следующих семинарах и конференциях:

VUI Международная научно-техническая конференция "Физика и радиоэлектроника в медицине и экологии ФРЭМЭ'2008", Россия, г.Владимир - г.Суздаль, 2-4 июля 2008г.

IX Международная конференция "Высокопроизводительные Параллельные Вычисления на Кластерных Системах", Россия, г.Владимир, ВлГУ, 2-3 ноября 2009г.

ПУБЛИКАЦИИ

Результаты исследований по теме диссертации опубликованы в 7 работах, из них 3 публикации в изданиях из перечня ВАК.

СТРУКТУРА И ОБЪЁМ РАБОТЫ Диссертационная работа состоит из введения, четырёх глав, заключения и списка использованных источников. Общий объём диссертации 197 страниц, в том числе 178 страниц основного текста, 14 страниц списка литературы, 1 страница приложения. Диссертация содержит 83 рисунка и 14 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность применения систем визуализации для САПР и приведено описание проблемы значительных затрат времени визуализации, определены цели и задачи исследования, а также представлены научная новизна, практическая значимость и основные положения, выносимые на защиту.

В перпон главе диссертации дано введение в системы визуализации для САПР, приведён разбор процесса освещения с физической точки зрения. Показано, что для получения результата моделирования освещения виртуальной сцены проекта одной из наиболее важных величин, значение которой необходимо получить, является светимость. Рассмотрены свойства светимости и процесс взаимодействия света с поверхностями (см. рис. 1). Последовательность лучей света, трассируемых в ходе визуализации, является цепыо Маркова, состоящей из отдельных задач взаимодействия спета с поверхностью сцепы в точке л*.

Приведено уравнение визуализации и описание алгоритма глобального освещения (1.1).

Ь,(х,со) = Le(x,o))+ J/(-v,со,со')Li(x,со')cosQda>' (i j) ii

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

На рис. 1 со,со' - векторы входящего и отражённого освещения соответственно, dco - телесный угол видимости сцены из точки поверхности х, N - нормаль поверхности в точке х, 0 - угол между нормалью и входящим направлением.

ствия света с поверхностью

Под решением уравнения визуализации понимают оценку интеграла светимости Ь0 для конечного множества точек в плоскости взгляда наблюдателя. Для решения уравнения визуализации используются методы численного интегрирования. Приведено рассмотрение существующих методов нахождения точки пересечения луча с треугольником. Выполнено исследование существующих методов и подходов выбора точек на плоскости взгляда наблюдателя.

Рассмотрены методы и подходы ускорения трассировки лучей: структуры пространственной сортировки и разбиения, групповая и пакетная трассировка лучей, а также трассировка лучей по Т.Уиттеду (Т.\УЫйес1) и метод распределённой трассировки лучей. Одной из наиболее эффективных структур пространственной сортировки и разбиения является кс!-дерево, где эффективность определена как соотношение скорости трассировки луча к объёму памяти, занимаемой структурой. Метод пакетной трассировки лучей основывается на том наблюдении, что когерентные лучи можно трассировать вместе, выполняя один вызов функции траверса для всего пакета лучей и применяя для вычислений блок БТМЭ, что даёт прирост скорости трассировки первичных лучей в несколько раз. Метод групповой трассировки основан на той же идее, что и метод пакетной трассировки. И в трассировке лучей по Уитттеду и в методе распределённой трассировки лучей для получения результата визуализации требуется осуществить трассировку значительного количества лучей, и трассировка лучей может занимать до 75% времени визуализации.

Ни метод пакетной, ни групповой трассировки не позволяет получить значимый прирост скорости трассировки в силу того, что среди вторичных лучей наблюдается значительный разброс в координатах точек начала отсчёта и в направлениях на Л; нахождения когерентных вторичных лучей за приемлемое время рассмотренные методы не предусматривают. Приведено рассмотрение последних наработок, позволяющих значительно ускорить решение уравнения визуализации в ряде частных случаев. Поставлены и обоснованы цели и задачи исследования.

Во второй главе диссертации приведено обобщённое описание существующих методов, применяющихся при определении областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трёхмерной сцены. Показано, что в предлагаемом алгоритме определения областей проявления ступенчатого эффекта цветовых переходов обращено внимание на тот факт, что ступенчатый эффект проявляется только для некоторых углов се в плоскости взгляда наблюдателя (см. рис. 2 - 3). Для определения областей проявления ступенчатого эффекта используется вектор БО (1.4), время нахождения которого составляет 0( 1). Векторы ре направлены перпендикулярно проекциям рёбер ех, е2,

еу треугольника на плоскость взгляда наблюдателя, наружу треугольника, н определяют направление увеличения количества точек в пределах данного треуголыш-ка(1.2)(1.3).

Рис. 2. Представление объекта сцены в двумерном пространстве плоскости взгляда наблюдателя

1Т

ре,

Рис. 3. Факторы формирования вектора БР

ре2

ех = V, - V, е, = у0 -

(1.2),

ре0=го( 90°(ео) < рё{ = го(90°(е]) ^ = го/90°(е2)

Векторы не нормализованы (соблюдается равенство \ре1

= е.

(1.3)

). Каждому

£ соответствует один ре. Векторы , ре, 51/) лежат в плоскости взгляда наблюдателя.

5О ¡трог/апсе — "I" ре |

л",

со5(4а, -—)

+ ре2

л.

со8(4 а2 —)

+ Рез

/Г

со8(4 а, —)

(1.4)

Модуль косинуса используется в качестве корректирующей скалярной величины с целью пропорционального изменения длин векторов ре, из суммы которых

складывается результирующий Использование модуля косинуса (1.4) позволяет контролировать процесс создания новых точек в плоскости взгляда наблюдателя в зависимости от величины а и от размеров треугольника в плоскости взгляда наблюдателя. Модуль косинуса в (1.4) равен нулю для некоторых величин углов, при которых ступенчатый эффект не проявляется. Для остальных значений сс ступенчатый эффект становится наиболее заметен с ростом количества пикселей, занимаемых ребром в плоскости создаваемого изображения. Таким образом, результирующий вектор Ж направлен в сторону наибольшего проявления ступенчатого эффекта.

С ростом количества примитивов, видимых наблюдателю, количество вычислений, связанное с ростом вычислений векторов £0 растёт, но ограничение на минимально допустимую площадь в 3 пикселя, занимаемую примитивом в плоскости создаваемого изображения, накладывает ограничение на максимальное количество примитивов, для которых производится расчёт.

Получение точек с использованием предложенного алгоритма может быть выполнено в нескольких параллельных во времени потоках.

Описан разработанный метод сохранения и повторного использования информации об освещении сцены от ИС, приведено сравнение с существующими алгоритмами, методами и подходами, использующими повторное использование информации, получаемой в ходе визуализации. Отмечено, что существующие рассмотренные алгоритмы, методы и подходы не предусматривают сохранения информации об освещении сцены от ИС в независимые наборы данных, что не позволяет обновлять результат визуализации для каждого ИС в отдельности.

В рассмотренных методах и подходах используется интерполирование величин светимости во вновь получаемых точках пересечения лучей со сценой. При интерполировании в качестве формы сбора используют окружность или полусферу. В ряде частных случаев интегрирование на полусфере даёт значительные ошибки в значении получаемой величины.

В предложенном методе произведена классификация всех лучен на опорные лучи и дополнительные. Основные лучи трассируются в любом случае, а результат их трассировки используется не только для получения светимости Ь,, но и для проверки номера примитива, с которым найдено пересечение (если найдено). Дополнительные лучи нужны для увеличения точности интегрирования на части направлений П для данного набора лучей.

чает на своём пути один и тот же примитив, либо несколько смежных примитивов, лежащих в одной плоскости. Расчёт точек пересечения для таких лучей может быть сведён к нахождению точек в двумерном (2Э) пространстве, при том условии, что будет гарантирован тот факт, что данные лучи встретят на пути своего распространения именно этот примитив. Данная гарантия обеспечивается трассн-

В ходе оценки интеграла

часть лучей встре-

п

ровкой опорных лучей (см. рис. 4) и проверкой наличия изменений в матрицах трансформации объектов сцены.

Рис. 4. Опорные и дополнительные точки

Основная цель применения опорных точек - подтвердить видимость данного примитива при каждой новой визуализации. Трассировка опорных лучей производится для всего подмножества точек х пересечения лучей с данным примитивом, удовлетворяющего условию распределения по Пуассону.

Предложенный метод предусматривает сохранение только координат точек пересечения лучей со сценой, а для получения значений Ц используются существующие методы и подходы решения уравнения визуализации, что гарантирует отсутствие ошибки аппроксимации значений при сборе окружностями, как в методе фотонной трассировки.

Координаты дополнительных точек находятся как (1.5):

р. и

птах - nmin

(птах - umin) * rand,

\

( птах

'0.5

p.v =

X PtSboJi] v

птах - nmin

+ (vmax - vmin) * rand,

:0.5

(1.5)

где nmin - птах = 3 - номера ближайших опорных точек, по которым производится аппроксимация, ptsbase - последовательность опорных точек, упорядоченная по и координате, rand - псевдослучайная величина из интервала [0..1). В результате математических преобразований (1.5) было получено, что для нахождения координат новой точки p(u,v) потребуется 8 сложений и 6 умножений, что меньше, чем в методе Moller-Trumbore (24 сложения, 26 умножений, 1 деление).

Применение предлагаемого метода производится только для тех участков на спектре направлений П, для которых справедливо (1.б)(1.7):

|<а .....

У¡гиегр I ~

(1.6) ЛШегр\-1' J -¡""1 (1.7)

где Ли«р - среднее значение светимости данной области в плоскости примитива, а направление обхода берётся то же, что и при обходе опорных точек (упорядоченной последовательности 20 распределения по Пуассону).

Для создания новых точек в плоскости примитива необходимо хранить плоскость примитива. Плоскость треугольника сохраняется только для тех примитивов, для которых определена Р^ь^е- Для примитивов, для которых сохранена их плоскость, проверку на пересечение можно производить одним из методов нахождения точки пересечения луча с треугольником с проецированием треугольника в 20 пространство, что, как показали тесты, на ~30-47% быстрее, чем использование методов нахождения точки пересечения в ЗБ.

Сохранение точек пересечения и плоскостей лишь для отдельных примитивов сцены - для тех, которые были найдены лучами освещения, позволяет избежать чрезмерного расхода памяти как в методах нахождения точки пересечения с проецированием треугольника в 2с1, а также позволяет гарантировать, что сохраняются именно те примитивы, которые будут встречены лучами света при последующих визуализациях. Получение аппроксимированных координат внутри треугольника занимает время О(М), где N достаточно мало (в большинстве случаев N = 3).

В результате исследований было отмечено, что среди всех тестовых сцен (в среднем) около 55% точек пересечения лучей со сценой может быть найдено с использованием предлагаемого метода. Доля лучей, подлежащих сохранению, зависит от настроек, установленных пользователем системы (в зависимости от допустимых затрат пространства ОЗУ).

Приведено описание подхода компактного представления кс1-дерева для систем трёхмерной визуализации, метода построения данного дерева, сравнение с уже существующими подходами и оценка получаемой выгоды от использования предложенного подхода. Описан подход построения предложенного кс1-дерева. Учтено, что влияние качества разбиения пространства на скорость визуализации растёт в направлении от корня дерева к его листьям. Для повышения эффективности разбиения пространства стоимость разбиения £Сл/),„ должна расти в направлении от корня дерева к его листьям (см. рис. 5):

« \

- СогпеИВох

- 51аг^ог(1Виппу НарруВисМЬа

- БГаг^огйОгавоп

- ХУгКСВОгавоп

- Соп(егепсе1*оот -Бропга

. .---

адаптивный $С

Рис. 5. Зависимость времени визуализации от стоимости поиска разбиения £С , ,

В существующих методах построения кё-дерева эта зависимость не учитывается. В предлагаемом подходе предложен новый метод построения кс!-дерева, в котором используется термин стоимости поиска разбиения (максимальное количество секущих плоскостей-кандидатов), что позволяет управлять точностью нахождения секущей позиции и временем построения кс!-дерева. На начальных уровнях построения кс!-дерева используется ограниченное количество плоскостей-кандидатов, разбивающих узел дерева на равные интервалы. На младших уровнях дерева используется выбор позиций секущих плоскостей по границам примитивов, как в методе построения кс1-дерева пгнп/тах. Использование адаптивного параметра $СхрШ позволяет управлять стоимостью разбиения в зависимости от уровня в дереве.

Для уровней дерева с 0 по 16 на представление позиции секущей плоскости можно тратить 8 бит вместо 32-х, где позиций секущей плоскости хранится в процентном соотношении от размера ячейки (см. рис. 6).

Ветвь

|0 1|? 1 и 5 6 7 8 9 10 11 12 13 11 15 16 17 18 19 20 21 22 23|24 25 26 27 28 29 Ш 31|

1 ститдс ц>ла Оси ра>ви*ни> 11 • лист 100.01 101 I потиив I смчшей плоскости

Лмс г

|0 1|2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Э1|

статус узла иийвкс снещсниа списка примитивов

Оси разбиении 100 01 101 11 • лист

Рис. 6. Представление узла кс!-дерева в памяти ЭВМ

Дано описание метода кластерной трассировки лучей, описан принцип формирования кластеров. Приведено рассмолрение метода кластерной трассировки лучей в сравнении с методами пакетной и групповой трассировки лучей. Показано, что наибольшая часть лучей - вторичные лучи - составляет около 75% всего количества лучей - не может быть ускорена методами пакетной и групповой трассировки в силу отсутствия механизмов нахождения когерентных вторичных лучей за приемлемое время. Использование метода кластерной трассировки позволяет локализовать поиск примитивов в структуре пространственной сортировки и разбиения за счёт нахождения когерентных направлений лучей(1.8), а также за счёт

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

\гс( к .х - г с! . .Л'| < £ \п{к.у -гс{ гу\< £ \г(1к.г -п1г2\< £

(1.8)

, где /-«У - вектор направления луча, е- максимально допустимая заранее заданная погрешность различия направлений лучей.

Формирование кластеров занимает время О(Ы), что на практике оказалось приемлемо и позволило ускорить трассировку вторичных лучей. Приведена схема обхода точек при отборе точек направлений и позиций лучей (см. рйс. 7)

X Направление обхода

Ы-дерево

7 ж л -1-!- 1......-: и луч к * 1 к 1

1 1 1 1 1 1 1 1 1 1 /Л 1 » 1 1 1 1 1 .: га, уп 0 1 1 1 1 1 1

Рис. 7. Схема отбора точек лучей в кластеры

В третьей главе приведена диаграмма классов разработанной системы визуализации для САПР, дано описание алгоритмического и информационного обеспечения. Приведена структура системы визуализации для САПР, а также схема организации работы блоков ПО визуализации (см. рис. 8).

-с—

Мит«оф**с САПР

О.

Ии«цмлмм«*м

1 I 1

1-1

М«ам мрши*

—| | ' |

С тру «тур« 11»цтр—«ттиноч

•иауадимци«

(ХЦмбогм ч

Нинр+чк САП»

Рис. 8. Структура разработанного ПС) визуализации (слева), организация работы блоков ПО визуализации (справа)

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

Описание алгоритма трассировки лучей с использованием предложенного метода сохранения и повторного использования информации об освещении от ИС (далее - метод ОМЬ) приведено на рис. 9.

Когерентен «от* 6м с одной группой?

*

(!)

Получгть номер группы когерентности данного луч»

ОЬ Либо М1 _ определен!

IX

Получить новое

ДФОС ■ данной точи

• данной точке

Получить сохраненное

V

■

Рис. 9. Алгоритм трассировки лучей с использованием метода ОМЬ

Алгоритм формирования кластеров в методе кластерной трассировки лучей приведён на рис. 10-11.

)

^___

Для есем Г«»VIк| с к.о по к 1

-I-

ГКЛГ^ ' ыщ\\и\ ШШ ШЛ е ЫЦк ЦП Л Л

Нсидючмть лун и

Рис. 11. Формирование кластеров в предлагаемом методе кластерной трассировки

Приведено описание алгоритма построения компактного кс!-дерева для систем трёхмерной визуализации для САПР.

Рис. 10. Формирование кластеров в предлагаемом методе кластерной трассировки

Рис. 12. Тестовые сцены 15

В четвёртой главе описаны условия тестирования предложенных алгоритмов, методов и подходов, проведено тестирование и внедрение разработанного в рамках выполнения данной диссертационной работы математического и алгоритмического обеспечения в составе разработанной системы визуализации для САПР. Информационным обеспечением разработанной системы визуализации являются: массив геометрических примитивов, массив лучей (сохраняемых в методе кластерной трассировки лучей), массив источников света, массив вершин, массив нормалей, массив результатов расчёта величин светимости. Примеры тестовых сцен приведены на рис. 12. Пример визуализации промышленных изделий см. на рис. 13. __________

Разработанное программное обеспечение внедрено в производство в фирме ООО" АС-студия".

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

1,

N--

лЧ

«к»

О

Рис. 13. Визуализация изделий в промышленности

Сцена СогпеНВох

§ £ 1

640*480

1280*960 размер изображения, пкс

4,915

2560*1920

- С фиксированным шагом

■ С псевдослучайным

Адаптивный

Предлагаемый

Рис. 14. Сравнение количества пикселей, отобранных в область потенциального проявления ступенчатого эффекта цветовых переходов

Меньшее количество пикселей, отобранных в область потенциального проявления ступенчатого эффекта означает, что устранение ступенчатого эффекта с применением предложенного алгоритма будет осуществляться за меньшее время за счёт того, что фильтру устранения ступенчатого эффекта потребуется перебрать меньше пикселей для получения результата.

Рассмотренные методы и подходы выбора точек на плоскости взгляда наблюдателя (кроме метода адаптивной трассировки) не основываются на данных о видимости объектов сцены через соответствующие участки изображения, а метод адаптивной трассировки учитывает получаемые величины светимости ¿0- результат трассировки предыдущих первичных лучей, - но процесс получения точек в плоскости взгляда наблюдателя кусочно-последователен во времени. Проведено исследование скорости работы предложенного алгоритма определения областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трёхмерной сцены. Приведены примеры результатов визуализации.

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

Sponza

ConferenceRoom

§ XYZRGB Dragon о

S Stanford Dragon о

н HappyBuddha 3>

StanfordBunny CornellBox

О 10 20 30 40 50 60 70 80 90 100 % относительно общего количества лучей

□ Метод быстрой излучательности ■ Метод карт светимости □ Предлагаемый метод

Рис. 15. Доля лучей, сохранённых с использованием рассмотренных методов подходов в сравнении с предложенным методом, относительно общего количества

испущенных лучей

Проведено исследование зависимости скорости построения кс!-дерева и скорости трассировки луча от точности позиционирования секущей плоскости на различных уровнях глубины кс!-дерева (см. рис. 16-17).

параметр 5С

—СогпеИВох —■—51апРогйВиппу HappYBuddha —И—Беаг^огсЮгавоп

—Ж—ХУгРСВ_0^оп —•— Сог^егепсеНоот —I—Бропга

Рис. 16. Время построения кс1-дерева в зависимости от значения 5с,

SC=2 SC =4 SC-8 адаптивный SC

параметр SC

—СогпеИВох —■— StanfordBunny HappyBuddha —X—StanfordDragon

—Ш— XYZRGBDragon —•— ConferenceRoom —H— Sponza

Рис. 17. Время визуализации с использованием kd-дерева, построенного по предложенному алгоритму адаптивного SAH, в зависимости от значения SCiplll

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

В результате сравнения качества разбиения пространства с алгоритмом БАИ было выяснено, что при использовании предложенного метода построения кс1-дерева средняя стоимость разбиения пространства сравнима со стоимостью в алгоритме £АН (см. Таблица 1).

Таблица 1 - Средняя стоимость

.....................-........ Тестовая сцена Метод SAH построения Предлагаемый метод построения kd-дсрева (адаптивный SAH), Мб

CornellBox 78,84 76.57

StanfordBunny 76,81 72,41

Happy Buddha 72,45 64,33

StanfordDragon 60,34 62,08 "

XYZRGB Dragon 82,90 65,82

ConferenceRoom 80,57 74,76

Sponza 65,84 72,09

Проведено исследование затрат памяти и скорости трассировки лучей с использованием предложенной структуры компактного кё-дерева. Показано, что при использовании предложенного подхода объём затрат памяти меньше, чем в существующем подходе представления кс!-дерева по 8 байт на узел (см. Таблицу 2). Накладные вычислительные расходы по вычислению размера ячейки в предлагаемом подходе не оказали существенного влияния на падение скорости трассировки, что было достигнуто благодаря их вычислению посредством блока 88П ЦП ЭВМ.

Тестовая сцена Размер kd-дерева (8 байт на узел), Мб Размер kd-дерева (предлагаемый подход), Мб

CornellBox 2,43 2,12

StanfordBunny 0,89 0,51

HappyBuddha 2,32 1,28

StanfordDragon 4,33 3,78

XYZRGB Dragon 489,7 301,2

ConferenceRoom 10,81 7,79

Sponza 14,89 10,17

Дапо сравнение затрат памяти и скорости трассировки с использованием предложенного метода в сравнении существующим подходом представления кс!-дерева.

Проведено исследование алгоритма формирования кластеров в методе кластерной трассировки лучей. Показано, что в существующих алгоритмах, методах и подходах отсутствуют методы и подходы нахождения когерентных вторичных лучей за приемлемое время. Отмечено, что ускорение трассировки вторичных лучей способно даль больший прирост скорости трассировки всего множества трассируемых лучей, чем ускорение трассировки первичных лучей, поскольку доля вторичных лучей достигает 75% от общего количества лучей. Приведены результаты сравнения времени трассировки лучей со временем пакетной трассировки (см. Таблица 3).

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

Основные научные и практические результаты работы заключаются в следующем:

1) Исследованы алгоритмы выбора точек на плоскости взгляда наблюдателя, используемые при определении областей проявления ступенчатого эффекта цветовых переходов, в результате чего был предложен новый алгоритм определения областей проявления ступенчатого эффекта цветовых переходов, с целью возможности создания точек в плоскости взгляда наблюдателя пропорционально величине возможного проявления ступенчатого эффекта цветовых переходов.

2) Исследованы существующие методы сохранения и повторного использования информации об освещении сцены, и в результате их анализа был предложен гибридный метод, использующий интерполяцию координат точек поверхности вместо интерполяции значений светимости, что позволило избавиться от ошибки интегрирования оценки на полусфере, свойственной рассмотренным ме-

Таблица 3 - Время визуализации с использованием кластерной трассировки Сцена [Трассировка Трассировка Трассировка | Методкла-

22L' Гш"

— ■ • . ^¿а!__ВРСШ,'еК; ЛУЧасеТМЯ1 _ ВРеМЯ,ССК

CornellBox 780 223 1817 121

StanfordBunny

HappyBuddha

StanfordDragon

XYZRGB Dragon

ConferenceRoom

22183

Sponza

12403

Таблица 4 - Размер служебной информации о кластерах

I—r-jvvrv........г...............ПК ...........\...................*..,.........,, . ............1 ■.—

CornellBox

StanfordBunny

HappyBuddha StanfordDragon XYZRGB Dragon

ConferenceRoom

Sponza

тодам и подходам. Для нахождения координат каждой новой точки (не из числа опорных точек) используется нахождение двумерных координат в плоскости треугольника, однако в отличие от существующих методов, сохранение промежуточных величин производится только для примитивов, которые были встречены лучами света (а значит внесли вклад в расчёт итогового значения светимости Ц для одного или нескольких пикселей.

3) Рассмотрены существующие методы и подходы представления и построения kd-дерева. Исследована зависимость скорости трассировки луча от качества разбиения пространства. Показано, что зависимость скорости трассировки луча от точности позиционирования секущей плоскости возрастает в направлении от корня дерева к его листьям. Показано, что при уменьшении точности позиционирования секущей плоскости в узлах начальных уровней приводит к незначительному падению скорости трассировки луча. Предложен подход представления kd-дерева, использующий для представления позиции секущей плоскости менее 32-х бит, где само значение позиции секущей плоскости представлено в виде процентного соотношения относительно размера узла дерева. В алгоритме построения предложенного kd-дерева используется модернизированный вариант алгоритма SAH, где максимальное количество секущих плоскостей-кандидатов ограничено некоторой заранее заданной величиной, а поиск минимальной стоимости разбиения производится среди всех трёх осей XYZ при нахождении позиции секущей плоскости для каждого листа. Сложность построения kd-дерева с использованием предложенного алгоритма составляет 0(N), вместо сложности 0(NlogN) в алгоритме SAH.

4) Исследованы существующие методы организации процесса трассировки лучей, рассмотрены методы пакетной и групповой трассировки лучей, рассмотрены существующие структуры пространственной сортировки и разбиения, применяемые в системах финальной визуализации в САПР. Показано, что в существующих методах и подходах к организации процесса трассировки лучей ускорение трассировки вторичных лучей при помощи пакетной или групповой трассировки не даёт значительного прироста производительности и отсутствуют механизмы поиска когерентных вторичных лучей за приемлемое время. Предложен алгоритм нахождения когерентных вторичных лучей за время 0(N) с дальнейшим выделением кластеров среди данных лучей и выполнением трассировки всего кластера лучей за один вызов функции траверса. Показано, что применение алгоритма кластерной трассировки лучей позволило сократить время визуализации.

ОСНОВНЫЕ ПОЛОЖЕНИЯ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ Публикации в изданиях из перечня, рекомендованного ВАК

1. Котов Д.С. Метод определения областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трехмерной сцены [Текст] / Д.С Котов // САПР и графика. 2009. №8. - С. 111 - 112.

2. Котов Д.С. Кластерная трассировка лучей в системах визуализации [Текст] / Д.С. Котов, В.Н. Ланцов // САПР и графика. 2010. №3. - С.84 - 85.

3. Котов Д.С. Компактное представление KD-дерева в системах трехмерной визуализации [Текст] / Д.С. Котов, В.Н. Ланцов // САПР и графика. 2010. №11. С.73 - 74.

Публикации в остальных изданиях

4. Котов Д.С. Организация интерактивной работы со списком источников света в сцене / Д.С. Котов // Алгоритмы, методы и системы обработки данных: Сб. научных статей / ВлГУ, М, Центр информационных технологий в природопользовании, 2008. №13. С.71 - 77.

5. Котов Д.С. Кластерная трассировка лучей в системах визуализации / Д.С. Котов, В.Н. Ланцов // Высокопроизводительные параллельные вычисления на кластерных системах: Материалы Девятой международной конференции-семинара / ВлГУ, Владимир, 2009. С.245 - 249.

6. Котов Д.С. Многоуровневый подход к построению изображений при визуализации компьютерной графики / Д.С. Котов // VIII Международная научно-техническая конференция "Физика и радиоэлектроника в медицине и экологии": тез. докл. / ВлГУ, Владимир, 2008. №1. С.343 - 345.

7. Котов Д.С. Технология упрощения геометрии на ранней стадии подготовки рейдера / Д.С. Котов // Алгоритмы, методы и системы обработки данных: Сб. научных статей / ВлГУ, М, 2008. №13. С.78 - 82.

8. Котов Д.С. Метод групповой трассировки лучей с использованием Streaming SIMD Extensions / Д.С. Котов // VIII Международная научно-техническая конференция "Физика и радиоэлектроника в медицине и экологии": тез. докл. / ВлГУ, Владимир, 2008. №1. С.345 - 347.

Подписано в печать 16.02.2011 Формат 60x84/16 Усл. печ. л. 1,39, Тираж 100 экз. Заказ 2011г Издательство Владимирского государственного университета. 600000, Владимир, ул.Горького, 87 22

SP

2010176983

ВВЕДЕНИЕ.

1 АНАЛИЗ СОСТОЯНИЯ В ОБЛАСТИ АЛГОРИТМОВ И МЕТОДОВ ВИЗУАЛИЗАЦИИ В САПР.

1.1 Введение в системы визуализации для САПР.

1.2 Уравнение визуализации и метод глобального освещения.

1.3 Введение в трассировку лучей.

1.3.1 Радиометрические величины.

1.3.2 Свойства светимости.

1.3.3 Взаимодействие света с поверхностями.

1.3.4 Алгоритмы трассировки лучей.

1.3.5 Алгоритм обратной трассировки лучей.

1.4 Обзор методов и подходов решения уравнения визуализации.

1.4.1 Методы и подходы повышения скорости решения уравнения визуализации и отдельных его частей.

1.5 Обзор методов и подходов нахождения точки пересечения луча с треугольником.

1.5.1 Нахождение точки пересечения в 3(1 пространстве.

1.5.2 Нахождение точки пересечения в 2<1 пространстве.

1.6 Классификация стратегий выбора точек на плоскости создаваемого изображения.

1.6.1 Равномерная трассировка.

1.6.2 Адаптивная трассировка.

1.6.3 Иерархическая трассировка.

1.6.4 Стохастическая трассировка.

1.6.5 Со случайным распределением.

1.6.6 С разделением на ячейки.

1.6.7 Случайное распределение по Пуассону.

1.7 Методы и подходы ускорения трассировки лучей.

1.7.1 Структуры пространственной сортировки и разбиения.

1.7.1.1 Иерархия ограничивающих объёмов.

1.7.1.2 Регулярная сетка.

1.7.1.3 Восьмеричное дерево.

1.7.1.4 КБ-дерево.

1.7.2 Объединение лучей в наборы.

1.7.3 Трассировка лучей по Уиттeдy(T.Whitted) и метод распределённой трассировки лучей.

1.7.4 Обзор последних наработок в области ускорения трассировки лучей

1.8 Цель и постановка задачи исследований.

1.9 Выводы.

2 РАЗРАБОТКА МЕТОДОВ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ И ПРОИЗВОДИТЕЛЬНОСТИ ПРОЦЕССА ВИЗУАЛИЗАЦИИ.

2.1 Обобщённая модель процесса определения областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трёхмерной сцены.

2.1.1 Алгоритм определения областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трёхмерной сцены.

2.2 Метод хранения и повторного использования информации о вкладе ИС в освещение трёхмерной сцены.

2.3 подход компактного представления кб-дерева для систем трёхмерной визуализации.

2.4 Метод кластерной трассировки лучей для систем визуализации, основанных на трассировке лучей.

2.5 Выводы.

3 АЛГОРИТМЫ РЕАЛИЗАЦИИ ПРЕДЛОЖЕННЫХ МЕТОДОВ.

3.1 Алгоритм определения областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трёхмерной сцены.

3.2 Алгоритм реализации подхода хранения и повторного использования информации о вкладе ИС в освещение трёхмерной сцены.

3.3 Алгоритм построения компактного kd-дерева для систем трёхмерной визуализации.

3.4 Алгоритм кластерной трассировки лучей.

3.5 Выводы.

4 ИССЛЕДОВАНИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ.

4.1 Структура и организация взаимодействия блоков разработанной системы визуализации для САПР.

4.2 Условия тестирования.

4.3 Исследование алгоритма определения областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трёхмерной сцены.

4.4 Исследование метода хранения и повторного использования информации о вкладе ИС в освещение трёхмерной сцены.

4.5 Исследование затрат памяти и скорости трассировки лучей с использованием предложенной структуры компактного kd-дерева для систем трёхмерной визуализации.

4.6 Исследование алгоритма кластерной трассировки лучей.

4.7 Сравнение времени визуализации со временем визуализации при использовании существующих подсистем визуализации.

4.8 Выводы.

Устойчивый рост сложности проектирования инженерных, строительных, архитектурных и конструкторских разработок в системах автоматизированного проектирования (САПР) привёл к необходимости повсеместного использования визуальных представлений проектных решений на промежуточных и финальных стадиях выполнения проекта. Применение систем получения визуального представления проектных решений позволяет повысить эффективность проектирования. Процедура оценки визуального представления проектного решения является одной из ключевых при выполнении проекта в САПР.

Визуализация в САПР применяется при выполнении проектов в машиностроении, авиации, автомобилестроении, архитектуре, при производстве дизайнерских проектов в направлениях архитектуры, автомобиле- и машиностроения, в промышленном дизайне, а также в ряде других областей.

От времени получения визуального представления проектного решения зависят сроки выполнения проекта и эффективность применения САПР в целом.

Время, требуемое на получение одного кадра визуального представления проектного решения может занимать от нескольких десятков минут до 100 часов [1] и более. Количество кадров может достигать нескольких тысяч (десятков тысяч).

Увеличить эффективность проектирования можно за счёт сокращения времени выполнения отдельных стадий проектирования, что можно получить путём сокращения вычислительных затрат при условии получения результата, отвечающего предъявляемым требованиям.

Для получения оценки проектных решений используют контроль ключевых характеристик проекта и визуальное представление проектного решения (<визуализация). Визуальное представление проектного решения на различных стадиях проектирования позволяет повысить эффективность оценки проектного решения.

Следует отметить возрастающую актуальность визуализации. Это связано с расширением спектра применения, а также с ростом требований к качеству и детальности визуального представления проектных решений. Данный рост требований привёл к резкому росту затрат времени, требуемого на получение визуального представления проектного решения.

Проблема существенного увеличения времени, требуемого на визуализацию проекта, приводит к увеличению сроков выполнения проекта и снижению эффективности проектирования. Решением данной проблемы являются:

- сокращение затрат времени на получение визуального представления проектного решения.

- сокращение общего количества процедур создания визуальных представлений проектного решения.

Процесс визуализации состоит из следующих стадий:

1) Интерпретация описания сцены1.

2) Оценка цвета каждого пикселя в создаваемом изображении.

3) Обработка совокупности полученных значений цвета пикселей и вывод созданного изображения в выбранном пользователем формате. Интерпретация описания сцены - это процесс преобразования исходного описания сцены проекта из некоторого заранее определённого формата во внутренний формат, определённый для данной системы визуализации. Данная стадия также включает в себя ряд действий по подготовке структур данных, необходимых для стадии оценки цвета пикселей в результирующем изображении.

1 Виртуальное многомерное пространство с настроенными определённым образом параметрами, содержащая описание трёхмерных поверхностей проекта

Оценка цвета пикселя в создаваемом изображении - это процесс, целью которого является получение значения цвета данного пикселя согласно модели распространения света, используемой в данной системе визуализации. Результатом выполнения данной стадии является совокупность значений цвета {светимости ) всех пикселей в создаваемом изображении, являющаяся отображением результата расчёта освещения виртуальной сцены проекта на плоскость взгляда наблюдателя . Цвет пикселя определяется совокупностью оценок светимостей во всех точках сцены, видимых через данный пиксель. В рамках работы над данной диссертацией примем, что цвет представлен в одной из существующих цветовых моделей (в рамках данной диссертации: RGB4).

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

С ростом требований к качеству и детальности визуального представления проектного решения доля времени, требуемого на выполнение стадий 1 и 3 в задаче визуализации стремится к столь ничтожно малой величине, что ею можно пренебречь.

Для решения задачи оценки цвета пикселя в создаваемом изображении необходимо произвести моделирование распространения света по

2 Светимость - отношение светового потока, исходящего от рассматриваемого малого участка поверхности,

1Ф к площади этого участка: М =-, где (1Ф - световой поток, испускаемый участком поверхности Б площадью ¿¡Б.

3 Плоскость изображения, создаваемого в ходе визуализации

4 Аддитивная модель представления цвета виртуальной сцене. Существует две группы методов моделирования распространения света:

1) Трассировка5 элементарных частиц(лучей) [2, 3].

2) Метод сканирования строк (растеризация) [4].

- Метод трассировки элементарных частиц предусматривает распространение элементарных частиц в виртуальной среде с учётом взаимодействия этих частиц с поверхностями трёхмерных моделей сцены проекта. В задаче моделирования распространения света такими

Г *] элементарными частицами могут быть фотоны , либо лучи света. Далее, в рамках данной диссертации, в качестве элементарной частицы примем луч, поскольку в программной реализации фотон - это луч с дополнительными полями, наличие которых зависит от реализуемого метода визуализации. Подход трассировки лучей позволяет обеспечить достаточную степень соответствия физической модели распространения света (корпускулярно-волновая теория света [5]) при наличии такой необходимости, что соответствует целям решения возможной и становящейся всё более актуальной задачи моделирования освещения, присутствующего в физическом мире, окружающем нас.

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

5 Операция нахождения ближайшего пересечения прямой, заданной трёхмерным вектором, с трёхмерной поверхностью сцены проекта

6 Фотон - элементарная частица света (см. Советский Энциклопедический Словарь)

7 Луч - вектор, имеющий координаты начала и направления методе принципиально8 отличается от существующей физической модели распространения света (как частицы и как волны), а поскольку моделирование распространения элементарных частиц по виртуальной сцене является обязательным условием реализации модели распространения света для соответствия корпускулярно-волновой теории, то метод растеризации при моделировании распространения света использовать нецелесообразно. В рамках работы над данной диссертацией метод растеризации рассматриваться не будет.

С ростом требований к качеству результата визуализации трёхмерной сцены всё большую актуальность приобретают методы визуализации, принадлежащие к семейству алгоритмов глобального освещения [6, 7]. Это определено в первую очередь тем, что алгоритмы данного семейства позволяют получить изображение, соответствующее критериям качества, применяемым к результату визуализации на конечных стадиях выполнения проекта при визуализации архитектурных и инженерных строений и сооружений, а также в проектах, создаваемых дизайнерами, инженерами и конструкторами при помощи САПР.

Одной из важнейших проблем финальной визуализации9 является проблема сокращения затрат времени визуализации. В отдельных случаях время, затрачиваемое на визуализацию одного кадра, составляет до 100 часов [1, 8], даже на современном специализированном аппаратном оборудовании. Решение данной проблемы позволит существенно сократить сроки выполнения проектов с использованием САПР.

Таким образом, задача сокращения времени получения визуального представления проектного решения является актуальной проблемой, поскольку её решение позволит повысить эффективность применения САПР

8 Моделирование распространения частиц (лучей) по виртуальной сцене не используется

9 Визуализация проектного решения, производящаяся на завершающих стадиях выполнения проекта в САПР в архитектурных, дизайнерских, инженерных и конструкторских проектах с применением САПР.

Цель работы и задачи исследований.

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

Для достижения поставленной цели необходимо решить следующие задачи:

1) Анализ существующих алгоритмов, методов и подходов организации решения уравнения визуализации, ускорения трассировки лучей.

2) Разработка новых, более эффективных методов численного решения уравнения визуализации, ускорения трассировки лучей.

3) Разработка информационного, математического и алгоритмического обеспечения системы визуализации для САПР.

Научная новизна работы. Новые научные результаты, полученные в работе, состоят в следующем:

1) Предложен алгоритм определения областей проявления ступенчатого эффекта цветовых переходов на изображении, позволяющий существенно уменьшить объём данных, подаваемых на вход фильтра устранения ступенчатого эффекта цветовых переходов на создаваемом изображении по сравнению с аналогичными по назначению подходами, применяющимися в современных системах визуализации для САПР.

2) Предложен метод сохранения и повторного использования информации об освещённости трёхмерной сцены от источников света. Применение данного метода позволяет ускорить процесс визуализации за счёт повторного использования ряда промежуточных величин (величин светимости и точек пересечения лучей со сценой), полученных в ходе предыдущих визуализаций, а также позволяет вычислять результат визуализации для любого ИС10 в отдельности.

3) Разработан подход компактного представления кс!-дерева для систем визуализации, позволяющий сократить затраты памяти на хранение кс1-дерева в ряде случаев.

4) Разработан метод пошаговой трассировки лучей с механизмом классификации, и динамическим объединением лучей в группы - метод кластерной трассировки лучей.

Практическая ценность работы. На основе предложенных алгоритмов, методов и подходов была разработана система визуализации для САПР, обладающая следующими, по сравнению с методами и подходами, применяющимися в существующих решениях, преимуществами:

- Меньшее на величину от 14,8 до 20,6% время устранения ступенчатого эффекта цветовых переходов в создаваемом изображении.

- Расчёт освещения, приходящего от ИС, выполняется быстрее на 1518%

- Меньший (до 44%) объем памяти, требуемой для хранения структуры к<1-дерева.

- Большая, до 30%, скорость визуализации с использованием предложенного компактного кс!-дерева.

- Большая, на величину до 170%, скорость визуализации с использованием метода кластерной трассировки лучей.

Сравнение производительности осуществлялось на одинаковых тестовых сценах и одном и том же аппаратном оборудовании.

В ряде случаев разработанная система уступила в производительности методам и подходам, применяющимся в существующих на рынке решениях, на величину 3 - 20%, однако в большинстве случаев разработанная система оказалась быстрее на величину 15-170%. Также стоит отметить, что

10 ИС - источник света разработанная система имеет потенциал дальнейшего увеличения производительности, и разработанные методы можно использовать совместно с широким кругом существующих методов и подходов, применяемых при расчёте финальной визуализации. Разработанная система визуализации позволяет решать уравнение визуализации [6, 7](1.1), используя метод трассировки путей [9] с выбором направлений луча по алгоритму Monte-Carlo [10], и способна осуществлять устранение ступенчатого эффекта цветовых переходов на получаемом изображении с автоматическим определением областей применения фильтра устранения ступенчатого эффекта цветовых переходов. Описание сцены проекта, включая все необходимые настройки, экспортируется из САПР, с дальнейшим преобразованием во внутренний формат.

Реализация и внедрение результатов работы.

Работа по теме диссертации проводилась в лаборатории ВлГУ, г.Владимир, кафедры ВТ. Полученные результаты исследований в виде программного обеспечения внедрены в производство на предприятии ООО"АС-Студия" (см. Приложение А). На защиту выносятся.

1) Алгоритм определения областей проявления ступенчатого эффекта цветовых переходов на создаваемом изображении.

2) Метод сохранения и повторного использования информации об освещении трёхмерной сцены источниками света.

3) Подход компактного представления kd-дерева для систем трёхмерной визуализации.

4) Метод кластерной трассировки лучей.

5) Программная реализация и алгоритмические решения разработанной системы визуализации.

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на следующих семинарах и конференциях:

- VTII Международная научно-техническая конференция "Физика и радиоэлектроника в медицине и экологии ФРЭМЭ'2008", Россия, г.Владимир - г.Суздаль, 2-4 июля 2008г.

- IX Международная конференция "Высокопроизводительные Параллельные Вычисления на Кластерных Системах", Россия, г.Владимир, ВлГУ, 2-3 ноября 2009г.

Публикации по работе. По теме диссертации опубликовано 7 печатных работ, из них 3 публикации в издании, рекомендованном ВАК (журнал "САПР и графика"), 2 тезиса докладов в сборнике докладов ФРЭМЭ'2008, 2 публикации в сборнике научных статей "Алгоритмы, методы и системы обработки данных" ВлГУ г.Муром.

Структура работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка использованных источников. Общий объём диссертации 197 страниц, в том числе 178 страниц основного текста, 14 страниц списка литературы, 1 страница приложения. Диссертация содержит 83 рисунка и 14 таблиц.

4.8 Выводы

1) Предложен метод определения областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трёхмерной сцены. Метод основывается на результате трассировки лучей в сцену, что гарантирует точность полученных координат пересечения со сценой, соответствующее точности найденных точек пересечения всех первичных лучей со сценой. Используется термин приоритетности направления изменения плотности вновь создаваемых точек в плоскости взгляда наблюдателя, где вектора приоритетности(важности) строятся исходя из данных об участках сцены, видимых через данные области изображения. Достигнуто 20% сокращение количества пикселей, относимых к области потенциального проявления ступенчатого эффекта цветовых переходов в создаваемом изображении.

2) Рассмотрены возможности и область применения предложенного метода сохранения и повторного использования информации об освещении виртуальной сцены проекта от ИС. Показано, что прирост скорости составил 15-18% относительно существующих методов аналогичного назначения.

3) Рассмотрена возможность применения предложенного подхода компактного представления кс1-дерева в архитектурных, инженерных и конструкторских проектах в САПР. Показано, что применение данного подхода позволяет сократить затраты памяти на величину до 44% в сравнении существующими подходами, а прирост скорости визуализации с предложенным подходом составил до 30%.

4) Рассмотрены целесообразность, особенности, и области применения предложенного метода кластерной трассировки лучей для визуализации в САПР. Показано, что данный метод позволил получить на тестовых сценах прирост производительности на величину до 170%, а время составления кластеров зависит только от количества сортируемых лучей и не зависит (напрямую) от количества примитивов в сцене проекта, что позволяет использовать данный метод при финальных визуализациях.

5) Рассмотрена структура программного обеспечения системы визуализации для САПР. Разработана система визуализации для САПР, реализованная в виде подключаемого модуля к САПР Autodesk 3ds max.

Заключение

Анализ существующих методов, подходов и алгоритмов, применяемых при визуализации трёхмерных сцен позволил определить возможные пути оптимизации каждой из стадий процесса визуализации, а также всего процесса визуализации в общем. Среди рассмотренных методов и подходов выполнения отдельных стадий процесса визуализации была произведена оценка их сильных и слабых сторон, и выделены методы и подходы, наиболее перспективные с точки зрения дальнейшего масштабирования производительности системы визуализации для САПР. Для решения задачи оценки цвета пикселя в создаваемом изображении целесообразно применять метод трассировки элементарных частиц (лучей). Среди структур пространственного разбиения и сортировки одной из лучших является к<1-дерево, т.к. позволяет получить наименьшее время поиска ближайшего пересечения луча с примитивом, при затратах памяти, сравнимых с остальными рассмотренными структурами пространственного разбиения и сортировки. Среди методов поиска пересечения луча с треугольником для системы визуализации для САПР предпочтительными являются методы нахождения пересечения в 3(1 пространстве, т.к. методы нахождения точки пересечения с проецированием в 2(1 пространство имеют слишком большой расход памяти, что значительно снижает количество примитивов сцены, умещающихся в ОЗУ, что в свою очередь является существенным ограничивающим фактором, неприемлемым для систем визуализации для САПР. В ходе исследований рассмотренных алгоритмов, методов и подходов, было также установлено, что в ходе трассировки лучей в сцену ряд промежуточных данных можно сохранить и повторно использовать: в ходе визуализации некоторой последовательности кадров освещённость отдельных участков сцены проекта остаётся неизменной, и отличается от предыдущего кадра лишь трансформацией проекции на плоскость взгляда наблюдателя.

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

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

Сокращение времени трассировки лучей является не единственной возможностью сокращения общего времени визуализации: скорость визуализации значительным образом зависит в том числе и от используемого алгоритма расчёта глобального освещения. Различные алгоритмы расчёта глобального освещения могут давать различный результат визуализации, отличаться в методах получения и обработки получаемых радиометрических величин в ходе визуализации. Для оценки результата визуализации применяется субъективный фактор, а для оценки производительности - время получения конечного результата визуализации.

Исследование существующих алгоритмов, методов и подходов для систем визуализации для САПР показало, что получение результата визуализации, соответствующего критериям качества финальной визуализации, является достижимой задачей для большинства алгоритмов глобального освещения, но требует значительных затрат аппаратных и/или временных ресурсов. Сокращение времени визуализации является одной из наиболее приоритетных задач при построении системы визуализации для САПР.

В диссертационной работе поставлены и решены задачи, направленные на разработку методов, подходов и алгоритмов, позволяющих повысить эффективность средств проектирования в САПР посредством сокращения времени визуализации. Предпочтение отдавалось подходам, не изменяющим результат визуализации.

В работе были получены следующие основные результаты:

1) Исследованы алгоритмы выбора точек на плоскости взгляда наблюдателя, используемые при определении областей проявления ступенчатого эффекта цветовых переходов, в результате чего был предложен новый алгоритм определения областей проявления ступенчатого эффекта цветовых переходов, с целью возможности создания точек в плоскости взгляда наблюдателя пропорционально величине возможного проявления ступенчатого эффекта цветовых переходов.

2) Исследованы существующие методы сохранения и повторного использования информации об освещении сцены, и в результате их анализа был предложен гибридный метод, использующий интерполяцию координат точек поверхности вместо интерполяции значений светимости, что позволило избавиться от ошибки интегрирования оценки Ц на полусфере, свойственной рассмотренным методам и подходам. Для нахождения координат каждой новой точки (не из числа опорных точек) используется нахождение двумерных координат в плоскости треугольника, однако в отличие от существующих методов, сохранение промежуточных величин производится только для примитивов, которые были встречены лучами света (а значит внесли вклад в расчёт итогового значения светимости Li для одного или нескольких пикселей.

3) Рассмотрены существующие методы и подходы представления и построения kd-дерева. Исследована зависимость скорости трассировки луча от качества разбиения пространства. Показано, что зависимость скорости трассировки луча от точности позиционирования секущей плоскости возрастает в направлении от корня дерева к его листьям. Показано, что при уменьшении точности позиционирования секущей плоскости в узлах начальных уровней приводит к незначительному падению скорости трассировки луча. Предложен подход представления kd-дерева, использующий для представления позиции секущей плоскости менее 32-х бит, где само значение позиции секущей плоскости представлено в виде процентного соотношения относительно размера узла дерева. В алгоритме построения предложенного kd-дерева используется модернизированный вариант алгоритма SAH, где максимальное количество секущих плоскостей-кандидатов ограничено некоторой заранее заданной величиной, а поиск минимальной стоимости разбиения производится среди всех трёх осей XYZ при нахождении позиции секущей плоскости для каждого листа. Сложность построения kd-дерева с использованием предложенного алгоритма составляет 0(N), вместо сложности 0(NlogN) в алгоритме SAH.

4) Исследованы существующие методы организации процесса трассировки лучей, рассмотрены методы пакетной и групповой трассировки лучей, рассмотрены существующие структуры пространственной сортировки и разбиения, применяемые в системах финальной визуализации в САПР.

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

181 нахождения когерентных вторичных лучей за время О (К) с дальнейшим выделением кластеров среди данных лучей и выполнением трассировки всего кластера лучей за один вызов функции траверса. Показано, что применение алгоритма кластерной трассировки лучей позволило сократить время визуализации.

1. Grant Rollings, "2,400 hours to make one second of action", The Sun, 07 Dec.2009

2. Cohen, M., and J. Wallace. 1993. Radiosity and Realistic Image Synthesis. Morgan Kaufmann

3. Ward, G. 1994. "The RADIANCE Lighting Simulation and Rendering System." Computer Graphics, pp. 459 472

4. Haeberli, P., and K. Akeley. 1990. "The Accumulation Buffer: Hardware Support for High-Quality Rendering" In Computer Graphics (Proceedings of SIGGRAPH 90) 24(4), pp. 309-318

5. Курс общей физики (Том 3. Оптика. Атомная физика. Физика атомного ядра и элементарных частиц) / Савельев И.В. // М.: 1998, 528 стр.

6. Kajiya, J. 1986, "The rendering equation", Proceedings of SIGGRAPH 1986, pp. 143-150

7. Philip Dutre, 2003, "Global Illuminaiton Comedium" Computer Graphics Department of Computer Science Katholieke Universitet Leuven, 68 pages

8. Дмитриев, К. От Монте-Карло к Квази Монте-Карло / К. Дмитриев // Труды 12-ой международной конференции по компьютерной графике и машинному зрению ГрафиКон'2002, Россия, Нижний Новгород, сентябрь 16-21,2002, с. 53-58.

9. Валиев, И.В. Физически корректная модель солнечного освещения, задаваемая изображением с большим динамическим диапазоном / Валиев И.В., Волобой А.Г., Галактионов В.А. // "Вестник компьютерных и информационных технологий", № 9, 2009, с. 10-17.

10. Волобой, А.Г. Анализ ошибок компьютерного моделирования глобального освещения / А.Г. Волобой, В.А. Галактионов, C.B. Ершов, Д.Д. Жданов, И.С. Потемин, JI.3. Шапиро // Препринт ИПМ им. М.В. Келдыша РАН, № 54, 2009, 23 с.

11. Галактионов В.А. Программные технологии синтеза реалистичных изображений / В.А. Галактионов // Автореферат диссертации на соискание ученой степени доктора физико-математических наук по специальности 05.13.11, Москва, ИПМ им. М.В. Келдыша РАН, 2007.

12. Волобой, А.Г. Моделирование естественного дневного освещения, задаваемого изображением с большим динамическим диапазоном / А.Г. Волобой, В.А. Галактионов, Э.А. Копылов, JI.3. Шапиро // "Программирование", № 5, 2006, с. 62-80.

13. Барладян Б.Х. Моделирование освещенности и синтез фотореалистичных изображений с использованием Интернет технологий / Б.Х. Барладян, А.Г.

14. Волобой, Н.И. Вьюкова, В.А. Галактионов, Н.Б. Дерябин // "Программирование", № 5, 2005, с.66-80.

15. Волобой А.Г. Алгоритмы моделирования и визуализации оптически сложных материалов на примере ткани / А.Г. Волобой, В.А. Галактионов, H.A. Лобалзо // "Программирование", № 4, 2010, с. 68-80.

16. Волобой, А.Г. Физически обоснованная модель распространения света в ткани и ее валидация / А.Г. Волобой, В.А. Галактионов, H.A. Лобалзо // Препринт ИПМ им. М.В. Келдыша РАН, № 63, 2008, 18 с.

17. Востряков, К.А. Высокочастотный кэш излучения / К.А. Востряков // Труды 19-ой международной конференции по компьютерной графике и зрению ГРАФИКОН-2009, Москва, МГУ, 5-9 октября, 2009, с. 360-363.

18. Востряков, К.А. Когерентные алгоритмы синтеза реалистичных изображений / Автореферат диссертации на соискание ученой степени кандидата физико-математических наук по специальности 05.13.11, Москва, ИПМ им.М.В. Келдыша РАН, 2009.

19. Барладян, Б.Х. Применение когерентной трассировки лучей в задачах физически аккуратной визуализации / Б.Х. Барладян, А.Г. Волобой, К.А. Востряков, В.А. Галактионов, JI.3. Шапиро // "Программирование", № 5, 2008, с. 67-80.

20. Волобой, А.Г. Средства визуализации распространения световых лучей в задачах проектирования оптических систем / А.Г. Волобой, В.А. Галактионов, А.Д. Жданов, Д.Д. Жданов // "Информационные технологии и вычислительные системы", № 4, 2009, с. 28-39.

21. Востряков К.А. Новый иерархический базис для освещения на полусфере // Труды 18-ой международной конференции по компьютерной графике и зрению, Россия, Московский Государственный Университет, июнь 23-27, 2008, с. 262-269.

22. Барладян, Б.Х. Алгоритм двухуровневой трассировки лучей и его развитие в Оптических элементах / Б.Х. Барладян, А.Г. Волобой, В.А. Галактионов, JI.3. Шапиро // Препринт ИПМ им. М.В. Келдыша РАН, № 46, 2008,21 с.

23. Волобой, А.Г. Визуализация результатов моделирования освещения в тонком красящем слое / А.Г. Волобой, С.В. Ершов, С.Г. Поздняков // Препринт ИПМ им. М.В. Келдыша РАН, № 66, 2010, 21 с.

24. Котов Д.С. Метод определения областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трехмерной сцены Текст. / Д.С. Котов // САПР и графика 8'2009, стр.111112

25. Котов Д.С. Организация интерактивной работы со списком источников света в сцене Текст. / Д.С. Котов // Алгоритмы, методы и системы обработки данных: сборник научных статей, выпуск 13, 2008, ВлГУ, г.Муром, стр.71-77

26. Ward, Gregory J.; Francis M. Rubinstein and Robert D.Clear: "A Ray Tracing Solution for Diffuse Interreflection". Coputer Graphics 22 (4), pp.85-92, 1988

27. Ward, Gregory J., Paul S. Heckbert, "Irradiance Gradients". In Proceedings of the Third Eurographics Workshop on Rendering, pp.85-98, Bristol 1992

28. Ingo Wald, Heiko Friedrich, Gerd Marmitt, Philipp Slusallek and Hans-Peter Seidel "Faster Isosurface Ray Tracing using Implicit KD-Trees" IEEE Transactions on Visualization and Computer Graphics (2005), Vol.11(5), pp.562-572

29. Maxim Shevtsov, Alexei Soupikov and Alexander Reshetov Intel Corporation "Efficient acceleration structures layout for rendering on 32- and 64-bit many-core architectures" proceedings of GraphiCon'2009, 2 pages

30. Котов Д.С. Компактное представление KD-дерева в системах трехмерной визуализации Текст. / Д.С. Котов, В.Н. Ланцов // САПР и графика 1Г2010, стр.73-74

31. Н. Samet, "The Design and Analysis of Spatial Data Structures" Addison-Wesley, Reading, MA, 1990

32. Matthias Groß, Carsten Lojewski, Martin Bertram and Hans Hagen "Fast Implicit kd-Trees: Accelerated Isosurface Ray Tracing and Maximum Intensity Projection for Large Scalar Fields" CGIM07: Proceedings of Computer Graphics and Imaging (2007) 67-74

33. Котов Д.С. Технология упрощения геометрии на ранней стадии подготовки рендера Текст. / Д.С. Котов // Алгоритмы, методы и системы обработки данных: Сб. научных статей / ВлГУ, М, 2008. №13. С.78-82

34. Realtime Ray Tracing on current CPU architectures Carsten Benthin PhD, Computer Graphics Group, Saarland University, Germany, 2006

35. Котов Д.С. Кластерная трассировка лучей в системах визуализации Текст. / Д.С. Котов, В.Н. Ланцов // САПР и графика 3'2010, стр.84-85

36. Kirill Garanzha and Charles Loop "Fast Ray Sorting and Breadth-First Packet Traversal for GPU Ray Tracing" // EUROGRAPHICS 2010, Volume 29 (2010), Number 2

37. Теоретические основы САПР / Корячко В.П., Курейчик В.М., Норенков И.П. // М.: Энергоатомиздат, 1987, 400с.

38. Основы САПР (CAD,САМ,CAE) / Кунву Ли // 2004, 560 е., Питер, ISBN: 5-94723-770-9

39. Введение в современные САПР / Малюх В. // ДМК Пресс, 2010, 192с., ISBN: 978-5-94074-551-8

40. Инженерное проектирование и САПР электрических машин (1-е изд.) / Гольдберг О.Д. // Академия, 2008, 560с., ISBN: 978-5-7695-4088-2194

41. Основы автоматизированного проектирования / Норенков И.П. // М., Изд. МГТУ им. Баумана, 2002., 336с.

42. Моделирование и алгоритмизация в САПР / Судзиловский В. // Клуб 36 и 6, 2009, 267с., ISBN: 978-5-98697-139-1

43. Численные методы / Самарский A.A., Гулин A.B. // М.: Научный мир, 1989, 432с.

44. Введение в математическое моделирование / Семененко М.Г. // М.: Солон-Р, 2002, 112с.

45. Введение в математические основы САПР / Ушаков Д. // Новосибирск: Ледас, 2008, 180с.

46. Математическое моделирование в технике / Зарубин B.C. // М.: МГТУ им. Н.Э. Баумана, 2001, 496с.

47. Математические основы машинной графики / Роджерс Д. // Адаме Дж., М.: Мир, 2001, 606с.

48. SolidWorks Компьютерное моделирование в инженерной практике / Алямовский A.A. // М: БХВ, 2005, 800 с.

49. Инженерная и компьютерная графика / Романычева Э. Т., Соколова Т. Ю. // ДМК Пресс, 2001, 592 с.

50. САПР технологических процессов / Кондаков А. И. // ISBN 978-57695-3338-9, 272с., 2008г.

51. САПР в машиностроении / Берлинер Э.М., Таратынов О.В. // Форум-Инфра-М, 2010, 448с., ISBN: 978-5-91134-117-6.

52. Каталог САПР. Программы и производители. 2008-2009 2-изд. / Латышев П. // Солон-Пресс, 2008, 704с., ISBN: 978-5-91359-032-9.

53. Проектирование в системе КОМПАС-ЗБ VII / Ганин Н. // ДМК Пресс, 010, 776с., ISBN: 978-5-94074-543-3.

54. Эффективная работа: SolidWorks 2005 / Тику Ш. // Питер, 2006, 816 е., ISBN: 5469010236.

55. САПР на базе AutoCAD как это делается / Зуев С.А. // BHV-Санкт-Петербург, 2008, 1168 е., ISBN: 5-94157-344-8.

56. AutoCAD 2004. Разработка приложений и адаптация / Полещук H.H. // БХВ-Петербург, 2004, 624 е., ISBN:5-94157-424-Х.

57. Основы компьютерной графики: Autocad 2000-2006 / Ивашинников А.П. // Солон-пресс, 2005, 175с., ISBN: 5-98003-228-2.

58. ArchiCAD 8.О. Самоучитель. Архитектурно-строительное проектирование / Васильев П. // ТехБук, 2004, 338с.

59. Волобой, А.Г. Расчет освещенности и генерация реалистичных изображений для архитектурных моделей, разработанных в AutoCAD / А.Г. Волобой, В.А. Галактионов, JI.3. Шапиро // Учебно-методическое руководство, ИПМ им. М.В. Келдыша РАН, 2009, 20 с.

60. Autodesk AutoCAD 2007 и AutoCAD LT 2007. Библия пользователя / Финкелыптейн Э. // Диалектика, 2007, 1312 е., ISBN 978-5-8459-1000-4.

61. AutoCAD 2010. Полный курс для профессионалов / Климачева Т. Н. // Диалектика, 2009, 1088 е., ISBN 978-5-8459-1599-3.

62. AutoCad для конструкторов / Уваров A.C. // Горячая линия Телеком, 2006, 399с., ISBN: 5-93517-275-5.