Учебное пособие: Методические указания по выполнению курсовой работы по дисциплине «машинная графика» Москва 1995

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

С.М.АВДЕЕВА, А.В.КУРОВ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ ПО ДИСЦИПЛИНЕ «МАШИННАЯ ГРАФИКА»

Москва 1995

ОГЛАВЛЕНИЕ

Стр.

1. Содержание курсовой работы

2. Требования к оформлению курсовой работы

3. Пример задания на выполнение курсовой работы .

4. Список рекомендуемых тем курсовых работ

Список литературы, используемой при выполнении

курсовой работы

6. Алгоритмы машинной графики, используемые при вы­
полнении курсовой работы

6.1. Алгоритм Робертса

6.2. Алгоритм Варнока

6.3. Алгоритм Вейлера-Азертона

6.4. Алгоритм, использующий список приоритетов . .

6.5. Алгоритм, использующий 2-буфер

6.6. Алгоритм построчного сканирования

6.7. Алгоритм определения видимых поверхностей
путем трассировки лучей

6.8. Алгоритм создания реалистических изображений.

1. СОДЕРЖАНИЕ КУРСОВОЙ РАБОТЫ

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

Курсовая работа представляет собой комплексную работу и ее выполнение требует использования знаний, полученных не только в одной конкретной дисциплине, но и в ходе предшествующего изуче­ния как фундаментальных и общеинженерных дисциплин («Высшая ма­тематика», «Физика», «Инженерная графика»), так и дисциплин спе­циальности («Основы информатики», «Типы и структуры данных», «Программирование на языке Си», «Системное программирование», «Об»ектно-ориентированное программирование»).

Курсовая работа должна быть посвящена разработке закончен­ного программного продукта, позволяющего моделировать трехмер­ные и/или реалистические изображения на экране дисплея. Такая направленность работы связана с тем, что алгоритмы нижнего уровня студенты достаточно глубоко и всесторонне изучают в ходе теоретических и практических занятий в течение предыдущего се­местра. Алгоритмы верхнего уровня (предназначенные для изобра­жения трехмерных и реалистических об»ектов) достаточно громозд­ки, программы, их реализующие, об»емны, что практически делает невозможным их разработку и отладку в ходе лабораторных работ.

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

-2-

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

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

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

Расчетно-пояснительная записка должна иметь об»ем 30-40 листов рукописного (или машинописного) текста на листах формата А4. Записка должна содержать следующие разделы:

1)Введение

2)Конструкторский

3)Технологический

4)Экспериментально-исследовательский

5)3аключение

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

Во введении дается обзор и анализ существующих программных систем в выбранном направлении, обосновывается необходимость разработки нового комплекса программ. Здесь же проводится ана­лиз и краткое описание с указанием их характеристик известных алгоритмов решения стоящей задачи. Об»ем введения 3-5 листов.

-3-

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

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

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

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

-4-

размерности данных.

Выбор исходных данных и формы их представления должен увя­зываться с такой характеристикой, как их об»ем и удобства поль­зователя при вводе. В частности, ввод большого количества дан­ных утомляет пользователя и увеличивает вероятность ввода ошибочных данных. В данной части записки могут выполняться рас­четы для определения об»емов памяти, необходимой для хранения исходных данных, промежуточных и окончательных результатов, а также расчеты, позволяющие оценить время решения задачи на ЭВМ. Результаты таких расчетов должны использоваться при сравнении альтернативных вариантов алгоритмов, а также оценки возможности практической реализации стоящей задачи на имеющейся технической базе. Об»ем конструкторской части должен составлять 35-55% все­го об»ема записки.

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

Данный раздел должен заканчиваться изложением руководства программиста, в котором излагаются требования к аппаратным средствам и программному обеспечению ЭВМ, а также излагается порядок работы с комплексом программ. Эта часть оформляется в соответствии с ГОСТ 19.504-79 и она должна содержать следующие разделы:

-назначение и условия применения программы;

-характеристики программы;

-обращение к программе;

-входные и выходные данные;

-сообщения.

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

В разделе «Характеристики программы» приводится описание основных характеристик и особенностей программы (временные, режим работы, средства контроля правильности выполнения и са­мовосстановления программы).

В разделе «Обращение к программе» должно быть приведено описание процедур вызова программы (способы передачи управле­ния и параметров данных).

В разделе « Выходные данные» должно быть приведено описа­ние используемой входной и выходной информации.

В разделе «Сообщения» должны быть указаны тексты сообще­ний, выдаваемых программой в ходе ее выполнения, описаны их содержание и действия, которые необходимо предпринять по этим сообщениям.

-6-

В приложениях к руководству программиста могут приводиться дополнительные материалы (примеры, иллюстрации, таблицы, графи­ки).

Технологический раздел должен содержать разработанные тес­ты для проверки правильности работы комплекса программ, резуль­таты тестирования на тестовых примерах. Об»ем этой части работы составляет 35-40%.

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

В этой части работы должны быть представлены примеры ис­пользования комплекса программ с изложением постановки конкрет­ной решаемой задачи, описанием конкретных вводимых исходных данных и полученных результатов с указанием значений характе­ристик требуемых ресурсов ЭВМ (затраты памяти, время счета и т. д.). Об»ем этой части записки составляет 10-15%.

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

-7-

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

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

Материал записки должен излагаться грамотным техническим языком, быть оформлен в соответствии с требованиями ЕСКД, ГОСТ, ЕСПД.

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

Графическая часть данной курсовой работы носит иллюстра­тивный, вспомогательный характер. Об»ем ее должен составлять 2-3 листа формата А1.

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

Графическая часть может выполняться карандашом, тушью или фломастером. При этом все листы должны выполняться однотипно.

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

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

Защита курсовой работы

Защита курсовой работы подводит итог всей работы студента в течение семестра. Защита курсовых работ проходит, как прави­ло, в период зачетной сессии. Предварительно составляется гра­фик работы комиссий по приему курсовых работ. Обязанность сту­дента записаться на защиту в соответствии с предлагаемым графиком и не допускать переноса срока защиты. Защита осущест­вляется публично, кроме членов комиссии (2-3 преподавателя) и защищающегося, могут присутствовать другие преподаватели, сот­рудники и студенты.

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

Доклад должен быть кратким (5-7 минут), четким и ясным. В докладе должны быть выделены основные задачи, стоявшие при вы-

-9-

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

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

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

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

2. ТРЕБОВАНИЯ К ОФОРМЛЕНИЮ КУРСОВОЙ РАБОТЫ

Оформление расчетно-пояснительной записки осуществляется в соответствии с ГОСТ 7.32-81 ЕСКД.

Название разделов и их возможное содержание уже рассмотре­ны, возможные названия подразделов, их об»ем приведены в разде-

- 10-

ле 3.

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

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

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

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

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

- 11 -

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

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

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

Сведения об использованных источниках располагаются в том же порядке, что и ссылки на них в тексте записки, список оформляется в соответствии с ГОСТ 7.1-76. В расчетно-поясни-тельной записке ссылки на использованные литературные источни­ки (книги, статьи, стандарты, справочники) даются в местах, где были использованы сведения из этой литературы. Ссылки представляют собой порядковый номер по списку источника, зак­люченный в косые черточки, например, /3,5/.

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

Библиографическое описание состоит из элементов, об»еди-ненных в области, и заголовка. Элементы и области приводятся в

- 12-

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

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

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

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

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

Сведения о документе, в котором помещена составная часть (например, статья из сборника), располагаются после сведений о

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

Примеры оформления пристатейного библиографического списка приведены в списке рекомендуемой литературы.

Каждое приложение следует начинать с нового листа с указа­нием в правом верхнем углу слова «ПРИЛОЖЕНИЕ». Приложение должно иметь содержательный заголовок. Каждое приложение имеет свой порядковый номер, для нумерации используются арабские циф­ры. Нумерация разделов, таблиц, рисунков, формул ведется в пре­делах каждого приложения. Располагаемые в приложениях распечат­ки программ должны быть сложены по формату А4.

Текст расчетно-пояснительной записки располагается на стандартных листах бумаги формата А4 с одной стороны, должны выдерживаться следующие размеры полей: левое - 30 мм, правое -10 мм, верхнее - 15 мм, нижнее - 20 мм. Заголовки разделов рас­полагаются симметрично тексту прописными буквами. Заголовки подразделов располагают с абзацным отступом строчными буквами (кроме первой прописной). Перенос слов в заголовках не допуска­ется, точка в конце не ставится.

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

Иллюстрации обозначают словом «Рис.» и нумеруют последо­вательно арабскими цифрами в пределах раздела, при этом номер рисунка состоит из номера раздела и номера рисунка, например,

- 14-

рис. 2.3. Иллюстрации должны иметь наименование. При необходи­мости их снабжают поясняющими данными. Наименование иллюстра­ции помещают над ней, поясняющую надпись - под ней.Номер ри­сунка помещается ниже поясняющей надписи.

Таблицы нумеруют аналогично, при этом вверху таблицы справа пишут слово «Таблица» и указывают номер. Каждая таблица должна иметь заголовок. Заголовок и слово Таблица начинают с прописной буквы. Заголовки граф пишут с прописных букв, подза­головки - со строчных, если они составляют одно предложение с заголовком. Если подзаголовки имеют самостоятельное значение, то они пишутся с прописных букв. Графы таблиц делить по диаго­нали не допускается.

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

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

При изображении схем следует руководствоваться правилами оформления, изложенными в действующих ГОСТ, ЕСКД, ЕСПД. Часть графического материала должна дублироваться в записке. Это тре­бование является обязательным, так как расчетно-пояснительная записка является самостоятельным документом и ее содержание

- 15-

должно быть понятно и без графической части.

Расчетно-пояснительная записка подписывается студентом, а затем преподавателем - руководителем курсовой работы. Подпись руководителя означает допуск студента к защите курсовой работы.

3. ПРИМЕР ЗАДАНИЯ НА ВЫПОЛНЕНИЕ КУРСОВОЙ РАБОТЫ

ЗАДАНИЕ НА КУРСОВОЕ ПРОЕКТИРОВАНИЕ ПО КУРСУ «МАШИННАЯ ГРАФИКА»

СТУДЕНТА ГРУППЫ ИУ7 - 51 СИДОРОВА С.Н. ТЕМА КУРСОВОЙ РАБОТЫ

«Разработка ППП, моделирующего движение группы динамичес­ких объектов в пространстве и синтезирующего их изображе­ние на экране дисплея.»

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

Промоделировать движение и получить изображение на экране графического дисплея группы объектов (от 1 до 10), совершающих управляемые маневры в пространстве. Объекты описываются коор­динатами вершин (x,y,z), ребрами и гранями. В качестве управля­ющих сигналов задаются значения векторов угловой и линейной скоростей:

W = F(t) , t [tO,tk];

· 16-

V = F(t) , t [tO,tk],

где [tO,tk] -интервал времени моделирования.

Предполагается, что картинная плоскость изображения сов­падает с экраном графического дисплея. Частота смены изображе­ния не менее 25 Гц.

При работе с изображением реализовать процедуру « Быстро­го перемещения изображения объекта».

Требования к процедуре «Быстрого перемещения изображения об»екта»:

1. Изображение объекта задается битовой картой.

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

3. После переноса изображения управление передается вызы­
вающей программе для расчета нового положения объекта.

4. В процедуру передаются следующие параметры:

- координаты центра изображения (хс,ус);

- номер объекта ( номер группы битовой карты);

- номер объекта в группе;

- адреса всех битовых карт;
при необходимости:

- текущие координаты изображения ( проекции (xvi, yvi)
объектов на картинную плоскость);

5. Размер изображения:

- max: 32 * 20 пикселов;

- min: 8*5 пикселов.

6. Интерфейс процедуры должен соответствовать стандарту
языка Паскаль.

- 17-

СОСТАВ КУРСОВОЙ РАБОТЫ Расчетно-пояснительная записка. Графическая часть. Пакет программ. ПРИМЕРНОЕ СОДЕРЖАНИЕ СОСТАВНЫХ ЧАСТЕЙ РАБОТЫ:

1. ВВЕДЕНИЕ

2. КОНСТРУКТОРСКИЙ РАЗДЕЛ

2.1. Обзор и анализ существующих программных систем
и обоснование необходимости разработки.

2.2. Выбор, обоснование и описание метода моделирования и ал­
горитма

3. ТЕХНОЛОГИЧЕСКИЙ РАЗДЕЛ

3.1 Выбор и обоснование языка программирования

3.2. Интерфейс пользователя

3.3. Хранение и обмен данными в системе

3.4. Разработка и отладка текста программы

3.5. Требования к аппаратуре

3.6. Требования к программному обеспечению

3.7. Порядок работы

3.8. Обращение к программе

3.9. Входные и выходные данные

3.10.Сообщения системы

4. ЭКСПЕРИМЕНТАЛЬНО-ИССЛЕДОВАТЕЛЬСКИЙ РАЗДЕЛ

4.1. Тестирование программы

4.2. Примеры использования программы

5. СПИСОК ЛИТЕРАТУРЫ

6. ПРИЛОЖЕНИЯ

- 18-

П.1. Листинг программы

П.2. Копии экрана

П.З. Распечатки результатов

ГРАФИЧЕСКАЯ ЧАСТЬ

1. Постановка задачи

2. Математические методы решения задачи

3. Функциональная схема системы

4. Схема алгоритма

5. Сравнительные характеристики аналогов

6. Листинг программы ( фрагмент )

7. Интерфейс пользователя

8. Иллюстрация работы с примером задания исходных данных

На защиту должны быть представлены:

1. Пояснительная записка объемом 25 - 30 страниц.

2. Графическая часть - 3 листа формата А1.

4. СПИСОК РЕКОМЕНДУЕМЫХ ТЕМ КУРСОВЫХ РАБОТ

1. Реализация алгоритма Робертса для об»ектов, описываемых
полигональными моделями.

2. Реализация алгоритма Варнока для об»ектов, описываемых
полигональными моделями.

3. Реализация алгоритма с приоритетами для об»ектов, опи­
сываемых полигональными моделями.

4. Реализация алгоритма Z-буфера для об»ектов, описываемых
полигональными моделями.

- 19-

5. Реализация алгоритма построчного сканирования для
об»ектов, описываемых полигональными моделями.

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

7. Реализация алгоритма трассировки лучей с учетом источ­
ников освещения и специальными эффектами (учет прозрачности,
отражения, преломления).

8. Реализация простого алгоритма закраски.

9. Реализация алгоритма закраски по методу Гуро.

10. Реализация алгоритма закраски по методу Фонга.

11. Реализация и сравнительное исследование алгоритмов зак­
раски - простой, по методу Гуро и по методу Фонга.

12.Построение реалистических изображений с учетом теней.

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

14. Пакет деловой графики (двух- и трехмерный варианты).

15. Пакет для изображения и манипуляции с трехмерным
(об»емным) шрифтом.

16. Пакет для изображения рельефа местности на основе ли­
ний уровня.

17. Обучающий пакет для об»яснения происхождения коничес­
ких и цилиндрических сечений.

18. Пакет для изображения поверхностей вращения по задан­
ной образующей.

19. Графическая библиотека примитивов для построения
трехмерных об»ектов.

5. СПИСОК ЛИТЕРАТУРЫ, ИСПОЛЬЗУЕМЫЙ ПРИ ВЫПОЛНЕНИИ

-20-

КУРСОВОИ РАБОТЫ

1. Аммерал Л. Машинная графика на языке Си.-М.:СолСистем,
1992.

Т. 1 :Принципы программирования в машинной графике.-224 с. Т.2:Машинная графика на персональных компьютерах.-232 с. Т.З.'Интерактивная трехмерная машинная графика.-317 с. Т.4:Программирование графики на Турбо Си.-221 с.

2. Булатов В., Дмитриев В. Увидеть невидимое // Компьютер-
npecc.-1993.-N4.-C.3-10.

3. Булатов В., Дмитриев В. Искусство преображения информации.

4.1 // КомпьютерПресс.-1993.-N4.-C.11-16.

4. Булатов В., Дмитриев В. Искусство преображения информации.

4.2 // КомпьютерПресс.-1993.-N5.-C.20-26.

5. Гардан И., Люка М. Машинная графика и автоматизация конс­
труирования.-М.:Мир.-1987.-272 с.

6. Геометрический процессор синтезирующей системы визуализации
/ В.А.Бурцев, С.В.Власов, С.И.Вяткин и др. // Автомет­
рия.-1986.-N4.-C.3-8.

7. Гилой В. Интерактивная машинная графика.-М.:Мир, 1981.-380 с.

8. Ковалев A.M., Талныкин Э.А. Машинный синтез визуальной
обстановки // Автометрия.-1984.-N4.-С.67-76.

9. Курковский С. Интервальные методы в компьютерной графике //
MoHHTOp.-1993.-N7-8.-C.76-85.

Ю.Ньюмен У., Спрулл Р. Основы интерактивной машинной графики.-М.:Мир,1976.-573с.

11 .Павлидиус Т. Алгоритмы машинной графики и обработки изобра­жений.- М.:Радио и связь, 1986.-400 с.

-21 -

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

-М.:Мир, 1980.-240с. 13.Роджерс Д. Алгоритмические основы машинной графики.-М.:Мир,

1989.-512с. И.Уокер Б.С., Гурд Дж., Дроник Е.А. Интерактивная машинная

графика.-М. :Машиностроение, 1980.-168с. 15.Фоли Дж., вэн Дэм А. Основы интерактивной машинной графики.

-М.:Мир,1985.-Т.1:375 с.,Т.2:368 с. 16.Фролов А.Г., Фролов Г.В. Программирование видеоадаптеров

CGA, EGA и VGA. - М.: Диалог - МИФИ, 1992.-28S с.

17. Хирн Д., Бейкер М. Микрокомпьютерная графика.-М.:Мир, 1987.
-352с.

18. ШикинЕ.В., Боресков А.В., Зайцев А.А. Начала компьютерной
графики.-М.: Диалог-МИФИ, 1993.-138 с.

19. Эгрон Ж. Синтез изображений. Базовые алгоритмы.-М.:Радио и
связь, 1993.-216с.

20. Эйнджел И. Практическое введение в машинную графи-
ку.-М.:Радио и связь, 1984.-135 с.

21. Эндерле Г., Кэнси К., Пфафф Г. Программные средства машинной
графики. Международный стандарт GKS. - М.:Радио и связь,

1988.-479 с.

6. АЛГОРИТМЫ МАШИННОЙ ГРАФИКИ, ИСПОЛЬЗУЕМЫЕ ПРИ ВЫПОЛНЕНИИ

КУРСОВОЙ РАБОТЫ

Алгоритмы машинной графики можно разделить на два уровня: нижний и верхний. Группа алгоритмов нижнего уровня иредназначе-

-22-

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

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

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

К третьей группе следует отнести алгоритмы, которые могут быть без больших затруднений реализованы аппаратно (допускающие распараллеливание, рекурсивные, реализуемые в простейших коман­дах). В эту группу могут попасть и алгоритмы, представленные в первых двух группах.

Наконец, к четвертой группе можно отнести алгоритмы со специальными эффектами, например, с устранением лестничного эф­фекта.

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

-23-

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

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

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

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

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

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

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

-24-

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

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

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

Различны и объемы вычислений для различного рода алгорит­мов. Так объем вычислений для алгоритмов, работающих в объектом

-25-

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

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

6.1. АЛГОРИТМ РОБЕРТСА

Алгоритм Робертса представляет собой первый из известных алгоритмов удаления невидимых линий. Этот математически эле­гантный метод работает в объектном пространстве. Модификации алгоритма, использующие предварительную пространственную сорти­ровку вдоль оси z и простые габаритные или минимаксные тесты, позволяют добиться почти линейной зависимости роста объема вы­числений от роста числа объектов.

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

-26-

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

Таким образом, для реализации алгоритма необходимо вначале
представить объекты визуализации в виде наборов многогранников,
каждый из которых задан уравнениями плоскостей своих граней.
Каждая плоскость многогранника описывается уравнением:
aX + bY + cZ+d = 0, (6.1)

где X,Y и Z - мировые координаты.

В матричной форме это уравнение запишется в виде: [XYZ1][P] = 0,где

р 2= о

L -

Любой выпуклый объект можно описать матрицей объекта, сос­тоящей из коэффицентов уравнений плоскостей:

где каждый столбец содержит коэффициенты одной плоскости.

Известно, что любая точка на плоскости однозначно определя-

ется двумя координатами; точка в пространстве в однородных коор-

динатах описывается вектором [S] = [X Y Z 1]. Известно также, ес­ли точка лежит на плоскости, то скалярное произведение [S][P] равно 0; если же точка не лежит на плоскости, то знак этого ска­лярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точ­ки, лежащие внутри тела дают положительное скалярное произведе­ние.

Сформировать матрицу объекта, состоящую из коэффициентов уравнений плоскостей можно несколькими методами. Один из них ис­пользует общеизвестный из аналитической геометрии принцип, что плоскость можно определить по трем неколлинеарным точкам ( хотя уравнение плоскости содержит четыре неизвестных коэффициента, его можно нормировать так, чтобы в = 1 ). Другой метод используется, если известен вектор нормали к плоскости , то есть :

2п 0 = a 2i + b Oj 2 + 0 с 2k 0 ,

где 2 i,j,k 0 - единичные векторы осей X, Y, Z соответственно. Урав­нение плоскости описывается формулой (6.1). Коэффицеш^ вычисля­ется с помощью произвольной точки на плоскости. Например, если эта точка с координатами (xl, yl, zl), то в = - (axl + byl + czl).

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

а = (yi - yJ)(^zi + ^Z J)

-28-

b - (zi - zj)(xi + xj)

с = (xi - xj)(yi + у)),где ]=1+1,если i=3,To j=l, а коэффициент в вычисляется с помощью любой точки на плоскости.

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

Предположим, что [В] - матрица однородных координат, задаю­щая исходные вершины объекта, [Т] - матрица видового преобразова­ния размером 4*4. Тогда координаты преобразованных вершин опи-шуться с помощью соотношения:

[ВТ] = [В][Т]; а уравнения исходных плоскостей, ограничивающих объект:

где [D] - ненулевая матрица. Аналогично, уравнения преобразован­ных плоскосстей задаются следующим образом:

[BT][VT] = [D],

где [VT] - преобразованная матрица объекта. Приравнивая левые части двух последних соотношений, получаем:

[BT][VT] = [B][V]. Затем преобразовываем к виду:

[VT] = [Т] [V].

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

-30-

плоскостей (рис. ).

После удаления нелицевых граней и ребер для каждого объекта выполняется самая трудоемкая часть алгоритма : проверка каждого оставщегося ребра на закрытие другими объектами. При этом исполь­зование Z - сортировки и простого минимаксного или габаритного с прямоугольной объемлющей оболочкой тестов позволяет удалить целые группы ребер и объектов. Например, все тела в сцене упорядочива­ются в некоторый преоритетный список по значениям Z ближайших вершин и расстояния до наблюдателя. Тогда никакой объект из этого списка, у которого ближайшая точка находится дальше от наблюдате­ля, чем самая удаленная из концевых точек ребра, не может закры­вать это ребро. Более того, ни одно из оставшихся тел, прямоу­гольная оболочка которого расположена полностью справа, слева, над или под ребром, не может экранировать это ребро. Использова­ние этих приемов значительно сокращает число тел, с которыми нуж­но сравнивать каждый отрезок или ребро.

Для сравнения отрезка (R1,R2) с объектом используется пара­метрическое представление этого отрезка:

R(t) = Rl +(R2 -Rl)t , 0<=t<=l (6.2)

или

V = S + dt,

где V - вектор точки на отрезке, S - начальная точка, a в - направление отрезка.

Необходимо определить: существуют ли значения t, при ко­торых данный отрезок или ребро невидимы. Для этого формируется другой отрезок от точки R(t) до точки наблюдения g :

Q(f,t) = U = V + gf = S + dt + gf , 0<=t<=l , f>=0. Значение t указывает точку на отрезке R(t) , a f указывает точ-

-31 -

ку на отрезке, проведенном от точки R(t) до точки наблюдения. Фактически Q(f,t) представляет собой плоскость в трехмерном пространстве, a (f,t) определяет точку на этой плоскости. Зна­чение f всегда положительно, ибо объекты, экранирующие R(t), могут находиться только в той части данной плоскости, которая заключена между исследуемым отрезком R(t) и точкой наблюдения.

Скалярное произведение любой точки, расположенной внутри объекта, на матрицу тела положительно. Если точка лежит внутри тела, то она невидима. Следовательно, для определения невидимой части ребра, которая экранируется объектом, достаточно определить те значения f и t, для которых скалярное произведение Q(f,t) = U на матрицу объекта положительно:

Н = U [VT] = S[VT] + dt[VT] + gf[VT] > 0. (6.3)

Те значения t и f, для которых все значения компоненты Н положительны соответствуют невидимой части ребра.

Обозначим: p = S[VT] , q = d[VT] , w = g[VT].

Тогда условие (6.3) запишется в виде:
Hj = pj + tqj + fwj > 0 , (6.4)

где j - номер столбца в матрице объекта.

Условия (6.4) должны выполняться для всех плоскостей, огра­ничивающих объект, то есть для всех j.

Случай, когда Hj = 0, является граничным между видимой и не-видомой частями ребра. Полагая Hj = 0 для всех плоскостей, полу­чают систему уравнений относительно t и f, которые должны удов­летворяться одновременно. Решая эту систему уравнений, находят все значения t и f, при которых изменяется значение видимости ребра или части ребра (число возможных возможных решений при j

-32-

плоскостях равно j(j - 1)/2). Затем каждое решение в интервалах 0<=t<=l , f>=0, подставляется во все остальные неравенства системы (6.3) для проверки того, что условие Hj >= 0 выполнено. Поиск корректных решений производится для того, чтобы найти мини­мальное среди максимальных значений параметра t (t minmax) и мак­симальное среди минимальных значений t (t maxmin). Подставляя эти значения в уравнение (6.2) определяют видимые участки ребра на интервалах [0,t maxmin] и [t mimmax,!]. Условие экранирования ре­бер или отрезков ребер является простым следствием из классичес­кой задачи линейного программирования:

t maxmin < t, t minmax.

Решения, удовлетворяющие неравенствам Hj > 0, могут су­ществовать и за пределами области, ограниченной условиями:

0<=t<=l и f>=0.

Поэтому к системе (6.4) необходимо добавить три уравнения, описы­вающие эти границы:

t = 0, t-1 =0 и f=0. Тогда число решений будет равно (j + 2)(j + 3)/2.

Для ускорения работы алгоритма перед определением t maxmin и t minmax удаляются не только нелицевые ребра, но и полностью ви­димые ребра. Видимые ребра определяются на основании того, что оба конца такого ребра должны лежать между точкой наблюдения и какой-либо видимой плоскостью. При f = 0 значение U задает сам отрезок. Далее, если f = 0, то при t = 0 и t = 1 получаются кон­цевые точки отрезка. Из соотношений (6.4) видно, что при t = 0 pj является скалярным произведением концевой точки отрезка и j - ой плоскости. Аналогично, pj + qj является скалярным произведением другой концевой точки отрезка и j-ой плоскости. В свою очередь,

-33-

j-я плоскость, ограничивающая объект видима, если wj <= 0. Следо­вательно, если wj <=0 , pj <= 0 и pj + qj <=0, то отрезок пол­ностью видим , а оба его конца лежат либо на видимой плоскости, либо между этой плоскостью и точкой наблюдения.

Для полностью невидимых ребер объекта отсутствуют простые тесты из-за бесконечности плоскостей. Поэтому полностью невидимые ребра определяют также как и частично невидимые ( в этом случае невидимый участок будет простираться от t = 0 до t = 1).

После определения частично видимых или полностью невидимых ребер определяются пары объектов, связанных отношениями протыка­ния, (в случае протыкания объектов сцены возникают решения на границе f = 0) и вычисляются отрезки, которые образуются при про­тыкании объектами друг друга. Эти отрезки проверяются на экрани­рование всеми прочими объектами сцены. Видимые отрезки образуют структуру протыкания.

Таким образом, реализация алгоритма Робертса подразделяет­ся на следующие этапы (рис. ):

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

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

3. Определение нелицевых граней, удаление их из списка гра­
ней и соответствующих ребер - из списка ребер.

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

5. Формирование списка протыканий также на основании сравне-

-34-

ний охватывающих оболочек объектов.

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

7.Формирования списка возможных ребер, соединяющих точки протыкания, для пар объектов, связанных отношением протыкания.

8.Проверка видимости полученных ребер по отношению ко всем объектам сцены в соответствии с действиями этапов 3 и 6.

9.Визуализация изображения.

6.2. АЛГОРИТМ ВАРНОКА

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

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

-35-

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

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

1) многоугольник внешний (целиком находится за пределами об­
ласти);

2) многоугольник внутренний (целиком лежит внутри области);

3) пересекающий многоугольник (пересекает область, т. е. одна
часть его лежит внутри области, другая - за пределами об­
ласти);

4) охватывающий многоугольник (область целиком лежит внутри
многоугольника).

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

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

1. Все многоугольники являются внешними по отношению к окну;
область можно закрасить цветом фона.

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

-36-

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

3. Имеется единственный охватывающий многоугольник и нет ни­
каких других многоугольников. Область закрашивается цве­
том этого охватывающего многоугольника.

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

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

Если исследуемая ситуация не приводится ни к одному из этих четырех случаев, то проводится разбиение области. При этом

-37-

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

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

Для вычисления глубины плоскости в точке с известными ко­ординатами (xl,yl) можно воспользоваться уравнением плоскости Ax+By+Cz+D=0, откуда получить Axl+Byl+D

С

Если же С=0, то плоскость параллельна оси Z. В этом слу­чае глубина находится из уравнений ребер многоугольника, кото­рые могут пересекать прямую, параллельную оси Z и проходящую через точку (xl,yl). В качестве глубины берется глубина той точки пересечения, у которой координата Z оказалась максималь­ной.

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

-38-

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

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

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

Более сложные варианты алгоритма используют перечисленные тесты. При этом целесообразно иметь три списка многоугольников: 1)охватывающих; 2)внешних; 3)пересекающих и внутренних. При построении этих списков запоминается уровень (шаг разбиения), на котором многоугольник попал в тот или иной список.

Рассмотрим тесты, позволяющие распознать тип многоугольни­ка. Простой габаритный тест выявляет факт внешности многоуголь­ника по отношению к прямоугольному окну на основе сравнения ко­ординат окна с координатами прямоугольной оболочки многоугольника. Если Хл, Хп - абсциссы левой и правой границ, а yh, yb - ординаты нижней и верхней границ области, a Xmin, Xmax, Ymin, Ymax - координаты аналогичных границ оболочки, то многоу­гольник внешний, если истинно следующее выражение:

-39-

(Xmin>Xn) (Хтах<Хл) (Утт>Ув) (Утах<Ун)

Многоугольник будет внутренним, если его об»емлющая обо­лочка лежит внутри области, т.е. должно быть истинным выражение

(Xmin> Хл)&(Хтах< Xn)&(Ymin> Ун)&(Утах< yb).

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

f=Ax+By+C,

где А, В, С - коэффициенты уравнения прямой.

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

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

-40-

выявления внешних и охватывающих многоугольников (рис.).

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

При прохождении луча через вершину многоугольника возника­ет неопределенность. Ее можно устранить, если считать касание за два пересечения, а протыкание - за одно.

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

ALFAi=0 - многоугольник внешний по отношению к окну.

(ALFAi - угол, образованный лучами, проведенными в конец 1-го ребра).

ALFAi=360m - многоугольник охватывает окно m раз (мно­гоугольник без самопересечений может охватить точку только один раз).

Процесс вычисления суммы можно упростить, так как нет нуж­ды подсчитывать углы с высокой точностью (достаточно ограни­читься приращениями по 45 , т.е. считать целые октанты, покры­тые отдельными углами). Октанты нумеруются от 0 до 7. Они получаются, если считать стороны окна бесконечными прямыми). Число целых октантов, покрытых углом, равно разности между но-

-41 -

мерами октантов, в которых лежат концы его ребер. При этом ALFA= ALFA-8, если ALFA>4 ALFA= ALFA +8, если ALFA<-4

Если ALFA=+4, то сторона окна расщепляет ребро многоуголь­ника, поэтому ребро в этом случае надо разбить на два стороной окна (в противном случае получаются одинаковые результаты для внешнего и охватывающего многоугольника).

На основе суммирования вкладов отдельных ребер получим О - многоугольник внешний по отно­шению к окну S= ALFAi =

+8m - многоугольник охватывает ок­но

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

6.3. АЛГОРИТМ ВЕЙЛЕРА-АЗЕРТОНА

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

Алгоритм удаления невидимых поверхностей состоит из четы­рех шагов:

-42-

1. Предварительная сортировка по глубине.

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

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

2. Отсечение по границе ближайшего к наблюдателю много­угольника (сортировка многоугольников на плоскости).

В качестве отсекателя используется копия самого приори­тетного многоугольника из списка, полученного на первом шаге. Отсекаются все остающиеся в приоритетном списке многоугольники (в том числе и первый). С помощью алгоритма отсечения Вейлера-Азертона [1, с.315] проводится отсечение по границам отсекате­ля, в результате чего формируются два списка - внутренних и внешних многоугольников.

Фактически отсечение проводится с проекциями на плоскость XOY отсекателя и отсекаемого многоугольника (двумерная операция отсечения). Часть отсекаемого многоугольника (если она есть), попавшая внутрь отсекателя, добавляется к списку внутренних

-43-

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

Этот шаг представляет собой сортировку на плоскости или XY -сортировку.

3. Удаление многоульников, экранированных многоульником,
ближайшим к точке наблюдения.

На этом шаге алгоритма сравниваются глубины каждого много­угольника из внутреннего списка с глубиной отсекающего многоу­гольника. Сначала для каждого многоугольника определяются коэф­фициенты уравнения несущей плоскости. Для каждой вершины каждого многоугольника с помощью полученных уравнений плоскос­тей вычисляются глубины (значения координаты Z). Полученные значения сравниваются с минимальным значением координаты Z (ZoTc.min) отсекающего многоугольника. Если глубина ни одной из вершин многоугольников из внутреннего списка не больше ZoTc.min, то все эти многоугольники экранируются отсекающим многоугольни­ком. И в итоге должен быть изображен отсекающий многоугольник.

Затем аналогично рассматривается внешний список многоу­гольников.

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

4. Рекурсивное подразбиение и окончательная сортировка для
устранения неопределенностей.

Если координата Z какого-либо отсекаемого многоугольника окажется больше, чем ZoTc.min, то такой многоугольник частично экранирует отсекающий многоугольник. В таком случае результат предварительной сортировки ошибочен, и алгоритм рекурсивно под-

-44-

разделяет плоскость (X,Y), используя многоугольник, нарушивший порядок, в качестве нового отсекающего многоугольника. Отсече­нию подвергаются многоугольники из внутреннего списка, причем старый отсекающий многоугольник сам подвергается отсечению.

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

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

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

6.4. АЛГОРИТМ, ИСПОЛЬЗУЮЩИЙ СПИСОК ПРИОРИТЕТОВ

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

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

-45-

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

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

1. Упорядочение всех многоугольников в соответствии с их
наибольшим (или наименьшим) значением Z координаты.

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

2. Разрешение неопределенностей, вызванных перекрытием
Z-оболочек.

Будем считать для определенности, что плоскости упорядо­чены по возрастанию минимального значения координаты Z. Обоз­начим через Р плоскость, стоящую в приоритетном списке на пер­вом месте (она имеет min Zmini), а через Q - плоскость, стоящую на втором месте.

Тогда возможна ситуация, при которой плоскость Р пол­ностью или частично экранирует Q. Неопределенность возникает при циклическом перекрывании плоскостей, например, Р находится

-46-

впереди Q, причем Q лежит впереди R, a R в свою очередь нахо­дится перед Р. Неопределенность возникает также и при проты­кании многоугольников.

В отмеченных случаях окончательный список приоритетов не удается установить сразу. Для проверки правильности сформиро­ванного списка следует для каждого многоугольника Р проверить его отношение с Q. Многоугольник Р не может экранировать мно­гоугольник Q, если его ближайшая к наблюдателю вершина (Pzmax) лежит дальше, чем самая удаленная вершина Q(Qzmin), т.е. Qzmin>Pzmax.

Если же Qzmin<Pzmax, то многоугольник Р потенциально мо­жет экранировать многоугольник Q и любой другой многоугольник, подобный Q, для которого выполняется приведенное соотношение. Если же Р фактически не экранирует Q, то Р можно заносить в буфер кадра.

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

Пятью тестами являются следующие:

1. Х-оболочки многоугольников не перекрываются, поэтому
сами многоугольники также не перекрываются, положительный от­
вет здесь получается, если истинно следующее выражение:

(Pxmax<Qxmin) (Qxmax<Pxmin).

2. Y-оболочки многоугольников не перекрываются, поэтому

-47-

сами многоугольники также не перекрываются. Положительный от­вет в этом тесте получается, если истинно соотношение (Pymax<Qymin) (Qymax<Pymin)

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

Q:

Ax+By+Cz+D=0

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

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

5. Проекции многоугольников на плоскость XOY (экран) не

-48-

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

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

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

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

Для разбиения многоугольника вдоль линии пересечения не­сущих эти многоугольники плоскостей можно использовать алго­ритм Сазерленда-Ходжмена (если отсекатель выпуклый) или алгоритм Вейлера-Азертона в общем случае. Многоугольник Q ис­пользуется как отсекатель. Многоугольник Р разбивается на два новых. Для нахождения точек пересечения ребер многоугольника Р с отсекателем Q можно использовать алгоритм Кируса-Бека [ ].

Алгоритм, использующий список приоритетов, может работать

-49-

как в об»ектном пространстве, так и в пространстве изображе­ния. Формирование списка приоритетов ведется в об»ектном пространстве, а результат заносится в буфер кадра в терминах пространства изображения. При этом необходимо произвести масш­табирование (переход из пространства мировых координат в пространство экранных координат).

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

6.5. АЛГОРИТМ, ИСПОЛЬЗУЮЩИЙ Z-БУФЕР Данный алгоритм удаления невидимых поверхностей является одним из простейших. Этот алгоритм работает в пространстве изображения. Здесь обобщается идея о буфере кадра. Буфер кадра используется для заполнения атрибутов (интенсивности) каждого пиксела в пространстве изображения. Наряду с буфером кадра вводится Z-буфер, представляющий собой специальный буфер глу­бины, в котором запоминаются координаты Z (глубина) каждого видимого пиксела в пространстве изображения.

В процессе работы глубина (значение координаты Z) каждого нового пиксела, который надо занести в буфер кадра, сравнивает­ся с глубиной того пиксела, который уже занесен в Z-буфер. Если

-50-

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

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

Главный недостаток алгоритма - большой об»ем требуемой памяти. Буфер кадра совместно с Z-буфером требует около 1,5 мегабайт памяти (при разрешающей способности 640*480 пикселов, 8 битах для хранения цвета пиксела и 32 битах для хранения глубины).

Один из путей решения этой проблемы - использование внешней памяти, но это может существенно замедлить работу. Другой путь экономии памяти - использование Z-буфера размером в одну стро­ку (алгоритм построчного сканирования).

Еще два недостатка данного алгоритма - трудоемкость устра­нения лестничного эффекта и невозможность реализации эффектов

-51 -

прозрачности.

Формально описать алгоритм можно следующим образом:

1. Заполнение буфера кадра фоновым значением интенсивности
(цвета).

2. Заполнение Z-буфера минимальным значением Z.

3. Преобразование каждого многоугольника в растровую форму
в произвольном порядке.

4. Вычисление для каждого пиксела с координатами (х,у),
принадлежащего многоугольнику, его глубины Z(x,y).

5. Сравнение глубины Z(x,y) со значением Zбyф(x,y), храня­
щимся в Z-буфере для пиксела с теми же координатами (х,у):

если Z(x,y)>Zбyф(x,y), то записать атрибут очередного мно­гоугольника в буфер кадра и гбуф(х,у) заменить на значение Z(x,

У).

Предварительно для выпуклых многогранников целесообразно удалить нелицевые грани (выполнить первый этап алгоритма Ро-бертса).

Для вычисления глубины каждого пиксела на сканирующей строке можно поступить следующим образом: уравнение плоскости, несущей многоугольник, имет вид Ax+By+Cz+D=0.

Отсюда при С<>0 Z=-(Ax+By+D)/C. Для сканирующей строки y=const, глубина пиксела, для которого xl=x+ х, равна: Ax+By+D Ax A

zl=............................ = z- - х

С С С

Поскольку х=1, Tozl=z-A/C. Если же О=0, то плоскость многоугльника параллельна оси Z. (Для наблюдателя такой много-

-52-

угольник вырождается в линию). Глубина пиксела, являющегося пе­ресечением сканирующей строки с ребром многоугольника, вычисля­ется следующим образом. Сначала определяются ребра грани, вер­шины которых лежат по разные стороны от сканирующей строки (одна из вершин ребра может в крайнем случае лежать на скани­рующей строке), так как только в этом случае сканирующая стро­ка пересекает ребро. Затем из найденных точек пересечения вы­бирается ближайшая к наблюдателю. Глубина точки пересечения определяется из соотношения _У 3-у2

z3=z2 + (z2-zl)

y2-yl где (yl,zl) и (y2,z2) - координаты вершин проекции ребра

на плоскость YOZ; (y3,z3) - координаты проекции точки пересечения на ту же

плоскость. Уравнение проекции ребра

z-z2 y-y2

z2-zl y2-yl

Уравнение проекции плоскости y=const (у-уЗ).

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

где Zpasp - глубина искомого разреза. В этом случае оста-

-53-

ются только элементы поверхности, которые лежат на плоскости разреза или позади нее.

Для построения прозрачных поверхностей может применяться модифицированный вариант Z-буфера - ALFA-буфер. Если рассматри­ваются монохромные почти прозрачные поверхности, то в этом слу­чае достаточно наряду с Z-буфером иметь еще один буфер с инфор­мацией о текущей интенсивности пиксела. При построении непрозрачной поверхности (как и в Z-буфере) используется Z-бу-фер, при этом обновляется информация и в ALFA-буфере. При пост­роении прозрачной поверхности расстояние до очередного пиксела изображения сравнивается с элементом Z-буфера, и он строится, если находится ближе к наблюдателю, при этом элемент Z-буфера не модифицируется, а в элемент ALFA-буфера заносится информация о новом цвете пиксела по правилу:

1=Т*1о

Т=( 1 -(4piD+M))exp(-S * 1),

где I - интенсивность пиксела, Т - коэффициент прозрачности,

D,M - коэффициенты диффузного и зеркального отражения, S - коэффициент поглощения, 1 - путь луча в рассматриваемом слое, 1о - текущее содержимое ALFA-буфера. (коэффициент прозрачности должен быть близок к 1).

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

В заключение можно отметить, что эксплуатационные характе-

-54-

ристики алгоритма с Z-буфером остаются практически постоянными, т.к. с ростом числа многоугольников в видимом об»еме уменьшает­ся число пикселов, покрываемых одним многоугольником.

6.6. АЛГОРИТМ ПОСТРОЧНОГО СКАНИРОВАНИЯ

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

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

Основная идея алгоритма достаточна проста. Как и в преды­дущем алгоритме, создается Z-буфер, но меньший по об»ему. Об»ем буфера соответствует количеству пикселов одной строки экрана. Первоначально этот буфер заполняется минимальным зна­чением Z, а в буфер кадра заносится фоновое значение интенсив­ности.

Затем определяется пересечение сканирующей строки с про-

-55-

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

Однако сравнение каждого многоугольника с каждой сканиру­ющей строкой является неэффективным. Целесообразнее использо­вать список активных ребер [1, с.99]. Но в отличие от растровой развертки одного многоугольника здесь осуществляется работа со всеми многоугольниками об»екта.

Алгоритм может быть сформулирован следующим образом:

1. Подготовка исходных данных.

а) Создание списка активных многоугольников. Для этого определяется самая верхняя сканирующая строка, которую пересе­кает многоугольник, и заносится многоугольник в группу Y, со­ответствующую этой сканирующей строке. Для каждого многоуголь­ника создается таблица (список), содержащая следующую информацию: коэффициенты А, В, С, в уравнения плоскости много­угольника; ymh - число сканирующих строк, пересекаемых многоу­гольником; атрибуты (цвет, интенсивность) многоугольника; Zn - глубину многоугольника для пиксела, соответствующего левому

-56-

ребру; Zx - приращение по Z вдоль сканирующей строки ( Z=-A/C, С<>0); Zy - приращение по Z между сканирующими строками ( Zy=-В /С, С<>0).

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

б) Создание списка активных ребер для всех негоризонтальных
ребер. Элементы списка должны быть отсортированы по группам на
основе меньшей Y-координаты (если считать, что верхней строке
экрана соответствует минимальное значение Y-координаты).

в) Запоминание по каждому ребру в виде таблицы (списка)
следующей информации: Х-координаты вершины с наименьшей Y-ко-
ординатой; X -приращения координаты X ребра при переходе к со­
седней сканирующей строке; Y - количества сканирующих строк,
пересекаемых ребром; идентификатора многоугольника, показываю­
щего принадлежность ребра многоугольнику.

2. Удаление невидимых поверхностей.

а) Инициализация буфера кадра размером с одну сканирующую
строку дисплея для всех пикселов цветом фона.

б) Инициализация Z-буфера размером с одну сканирующую строку
путем занесения в него значения Zmin.

в) Проверка для очередной сканирующей строки появления новых
многоугольников (соответствующая Y-группа должна быть не пус­
та). Добавление новых многоугольников к списку активных много­
угольников.

-57-

г) Проверка появления новых многоугольников в списке актив­
ных многоугольников. Добавление всех пар ребер новых
многоугольников к списку активных ребер.

д) Проверка удаления ребра из списка активных ребер. Провер­
ка сохранения многоугольника в списке активных многоугольни­
ков. Укомплектование пары активных ребер многоугольника в
списке активных ребер при сохранении многоугольника в списке
активных многоугольников.

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

ж) Выполнение для каждой пары ребер многоугольника из спис­
ка активных ребер следующих действий:

- извлечение пары ребер многоугольника из списка активных
ребер;

- инициализация Z со значением Zn;

- вычисление глубины для каждого пиксела, лежащего в ин­
тервале Хл<Х<Хп (Хл, Хп -абсциссы точек пересечения левого и
правого ребер пары со сканирующей строкой): для очередной точ­
ки текущей сканирующей строки Zx+ x=Zx- Zx;

- сравнение глубины Z(x) с величиной Z6y<|)(x) для те­
кущей строки. При Z(x)>Z6y<|)(x) занесение атрибутов многоуголь­
ника в буфер кадра для сканирующей строки и замена Z6y4>(x) на
Z(x);

- запись буфера кадра для сканирующей строки в буфер кад­
ра дисплея.

- коррекция списка активных ребер:

-58-

¥л=¥л-1; Yn= Yn-1. При ¥л<0 или Yn<0 удаление соот­ветствующего ребра из списка; индикация обоих ребер и соот­ветствующего многоугольника;

- вычисление новых абсцисс точек пересечения:
Хл=Хл+ Хл; Хп=Хп+ Хп;

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

Zn= Zn- Zx* Х- Zy;

- удаление многоугольника из списка активных многоуголь­
ников при Умн<0.

Перед началом работы алгоритма целесообразно удалить не­лицевые грани.

6.7.АЛГОРИТМ ОПРЕДЕЛЕНИЯ ВИДИМЫХ ПОВЕРХНОСТЕЙ ПУТЕМ ТРАССИРОВКИ ЛУЧЕЙ

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

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

Если наблюдать лучи, выпущенные источником, то можно убе­диться, что лишь малое их количество дойдет до наблюдателя, поэтому такой подход в вычислительном плане весьма неэффекти-

-59-

вен. Более эффективным является подход, при котором лучи отс­леживаются (трассируются) в обратном направлении, т.е. от наб­людателя к об»екту.

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

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

Лучи, идущие от наблюдателя, параллельны в этом случае оси Z. Необходимо проследить траекторию луча, чтобы определить об»екты сцены, с которыми этот луч пересекается, и вычислить глубину пересечения с каждым об»ектом для каждого пиксела (лу­чей будет столько, сколько пикселей на экране). Из всех об»ек-тов, с которыми пересекается луч, видимым для данного пиксела будет тот, пересечение с которым имеет наибольшую глубину (максимальное значение координаты Z). И данный пиксел надо закрасить цветом об»екта с этой максимальной глубиной.

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

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

-60-

оказывает самое большое влияние на эффективность всего алго­ритма, так как более 75% всего времени затрачивается на опре­деление пересечений.

Для исключения ненужного поиска пересечений в алгоритме предлагается искать сначала пересечение луча с об»емлющей обо­лочкой об»екта. Если луч не пересекает оболочку, то он не пе­ресекает и сам об»ект.

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

Использование сферы может оказаться неэффективным, так как об»ем описанной сферы может существенно превышать об»ем об»екта. Но тест со сферической оболочкой чрезвычайно прост: достаточно определить расстояние от центра сферы до луча. При использовании параметрического представления прямой, проходя­щей через точки Pl(xl,yl,zl) и P2(x2,y2,z2), получим P(t)=Pl+(P2-Pl)t

или x=xl+(x2-xl)t=xl+at у=у 1 +(у2-у 1 )t=y I +bt z=zl+(z2-zl)t=zl+ct

Если центр сферы лежит в точке с координатами Po(Xo,Yo,Zo), то квадрат расстояния от него до прямой:

d =(Xl+at-Xo) + (Yl+bt-Yo) + (Zl+ct-Zo). Значение параметра t, при котором это расстояние мини­мально, находится из условия

dd(t)

-=0