Донецкий национальный технический университет

Пауков Дмитрий Петрович

Исследование алгоритмов трехмерной визуализации в реальном времени конструкций и механических узлов

Автореферат

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

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

Компьютерная графика (computer graphics) - это область информатики (науки о компьютерах - computer sciences), которая изучает все вопросы, связанные с обработкой и синтезом изображения с помощью ЭВМ.

Эта область начала развиваться около 40 лет назад. В те годы удавалось добиться отображения нескольких десятков отрезков на экране электронно-лучевой трубки (ЭЛТ), а современные системы машинной графики позволяют создавать изображения, практически, не отличимые по качеству от фотографических снимков реальных объектов. Общепринятой практикой стало сейчас обучение пилотов с помощью систем моделирования реальной ситуации, как она видится из кабины самолета во время пилотирования, создание изображения виртуального динамического мира во всем его многообразии в реальном масштабе времени. На экран выводят полнометражные кинофильмы, в которых нет ни одного кадра, снятого "на натуре" или в павильоне киностудии, а все действия разворачиваются в памяти компьютера.

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

В области программного обеспечения также произошли большие изменения, особенно за последние годы. Появилось много различных графических библиотек API, среди которых наиболее популярные Direct3D и OpenGL.

Библиотека OpenGL стала своего рода стандартным интерфейсом для программистов, как при написании прикладных программ, так и при разработке программных продуктов высокого класса - от интерактивных игр до систем визуализации результатов научных исследований. Для решения этих же задач можно применять также и Direct3D.

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

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

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

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

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

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

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

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

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

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

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

Виртуальные миры, но пока другого рода, приникли и в Internet - появился язык VRML (Virtual Reality Modeling Language), который позволяет создавать в сети виртуальные динамические миры. Технология VRML предназначена для создания с помощью языка VRML в Internet (WWW) управляемых трехмерных пространств с гиперсвязями, называемых Moving Worlds (движущимися мирами). Основной задачей VRML является реалистичное отображение образов окружающего мира и расширение возможностей Internet в сфере человеческого общения.

Человек не может взаимодействовать с вычислительной машиной на "её языке" машинных команд - необходим интерфейс пользователя. В различные времена использовались различные подходы для решения этой проблемы, но в последнее время парадигма графического интерфейса стала доминирующей в сфере взаимодействия пользователя с компьютером. Графический интерфейс предполагает использование различного рода окон, пиктограмм, меню, кнопок, устройств указания, таких как мышь для осуществления взаимодействия человека с машиной. Такой подход наиболее прост и понятен для человека, чем, например, интерфейс командной строки. Поэтому большинство современных операционных систем и прикладных программ используют графический интерфейс. При чем с точки зрения пользователя эти интерфейсы различаются только деталями, например, графические интерфейсы систем X Window, Microsoft Windows и MacOS в достаточной степени похожи, что позволяет пользователю легко переходить от одной системы к другой.

Сейчас уже миллионы людей пользуются услугами сети Internet, доступ к которой немыслим без графических программ-броузеров, таких как Netscape или Internet Explorer, которые используют одни и те же средства графического интерфейса. Мы настолько к ним привыкли, что часто и не задумываемся, что эти средства также относятся к инструментам компьютерной графики.

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

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

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

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

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

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

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

Таким образом, исследование алгоритмов визуализации является актуальной современной задачей.

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

Исследование алгоритмов осуществляется путем определения основных его характеристик:

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

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

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

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

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

Растровое преобразование отрезков можно реализовать по алгоритму Брезенхема (Bresenham) [1]. Этот алгоритм был предложен в 1965 году, и с тех пор используется практически во всех графических системах. Главное его достоинство заключается в том, что для растеризации отрезка нужно выполнять только целочисленные вычисления, что существенно ускоряет и упрощает процесс растеризации по сравнению с алгоритмами, использующими действительные числа. Поэтому алгоритм Брезенхема просто реализовать аппаратно.

Растровое преобразование многоугольников сопряжено с тонированием и закраской.

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

Отсортируем вершины так, чтобы вершина A была верхней, C - нижней, тогда

Необходимо пройтись по всем линиям от min_y до max_y. Рассмотрим какую-нибудь линию, соответствующую значению sy на экране,

Если sy меньше B.y, то она пересекает стороны AB и AC; если sy больше или равно B.y, то стороны BC и AC.

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

Остановимся более подробно на нахождении пересечения прямой y = sy (текущей строки) и стороны треугольника, например AB. Запишем уравнение прямой AB:

Подставляем сюда известное для текущей прямой значение y = sy:

Для других сторон пересечение ищется аналогично. Пример реализации на Си-подобном языке.

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

При расчете освещенности для любой поверхности должны учитываться следующие факторы:

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

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

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

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

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