Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Один метод построения полигональных изображений

Название: Один метод построения полигональных изображений
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 08:37:07 19 марта 2007 Похожие работы
Просмотров: 158 Комментариев: 22 Оценило: 4 человек Средний балл: 4.3 Оценка: неизвестно     Скачать

Василий Терешков

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

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

Терминология

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

Мировая система координат – в нашем случае пространственная прямоугольная система координат (СК), две оси которой (X и Y) направлены по сторонам экрана монитора, а третья – от наблюдателя.

Экранная система координат – СК в плоскости экрана, ее оси совпадают с осями X и Y мировой СК.

Система координат модели – СК, относительно которой в файле заданы координаты всех вершин модели, изображение которой строится.

Вектор – направленный отрезок, его положение будем задавать либо координатами начала и конца, либо их разностями (собственно координатами вектора). Длина (модуль) вектора рассчитывается как квадратный корень из суммы квадратов его координат – это следствие теоремы Пифагора. Скалярное произведение векторов – число p, определяемое следующим образом: или, где |A| и |B| - длины векторов A и B, x, y, z – их координаты, t – угол между ними. Коллинеарные векторы – два или более вектора, лежащие на одной прямой или параллельных прямых. Компланарные векторы – три или более вектора, которые при отложении из одной точки оказываются лежащими в одной плоскости. Если векторы A, B, C компланарны, то вектор C можно разложить по векторам A и B, то есть C=aA+bB, где a и b – некоторые коэффициенты. Нормаль к вектору – вектор единичной длины, перпендикулярный данному. На плоскости координаты нормали к вектору P(x; y) определяются по формулам:

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

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

Используемые данные и их представление

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

В файле с информацией о модели должны быть каким-либо образом заданы координаты всех вершин (их число может достигать нескольких тысяч) и порядок их соединения. Если предполагается наложение текстур, то каждой вершине должны быть приписаны еще два числа – текстурные координаты u, v. Их смысл в следующем. Текстура представляет собой плоское растровое изображение, которое должно быть наложено на пространственную модель без разрывов. Это предполагает неравномерную деформацию текстуры – ее сжатие и растяжение. Но одновременно требуется, чтобы текстура не «сползла», то есть во всех вершинах модели оказались строго определенные точки растра. Эти точки и задаются координатами u, v в системе координат, связанной с текстурой. Хорошей механической аналогией может послужить кусок резины, натягиваемый на каркас и прикрепляемый булавками в вершинах каркаса.

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

//Информация о вершинах

struct TVertex

{

float x; //координаты в СК модели

float y;

float z;

} Vertices[NUM_VERTICES];

//Информация о гранях

struct Ttriangle

{

int i1; //номера вершин, составляющих грань, в массиве Vertices

int i2;

int i3;

float u1; //текстурные координаты вершин

float v1;

float u2;

float v2;

float u3;

float v3;

} Triangles[NUM_TRIANGLES];

//Текстура (256 цветов)

unsigned char Texture[TEXTURE_SIZE];

Отдельно требуется указать ракурс, под которым будет видна модель. Наиболее удобным для пользователя было бы задание оси вращения в виде вектора и угла поворота вокруг нее. Однако значительно проще реализовать последовательные повороты по трем углам: вокруг оси X, вокруг оси Y’, в которую перешла ось Y при первом повороте, вокруг оси Z’’, в которую перешла ось Z’ при втором повороте.

Алгоритм построения изображения

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

Первым этапом построения изображения треугольной грани будет определение координат ее вершин в мировой СК и, в частности, их положения на экране, для чего требуется повернуть СК модели на заранее заданные углы (см. выше). Наиболее изящно такой поворот осуществляется умножением радиуса-вектора вершины на матрицу поворота. Мы же опишем его в терминах обычной координатной геометрии с применением формул поворота «плоской» (!) СК. Пусть x, y, z – начальные, а x’, y’, z’ - конечные координаты вершины, ТАУ – угол поворота, тогда эти формулы приобретают вид:

вокруг оси X:

вокруг оси Y:

вокруг оси Z:

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

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

Например, на приведенном рисунке точка P лежит внутри треугольника, поскольку выполняются соотношения (здесь и далее заглавными латинскими буквами будем обозначать точки и векторы, а строчными – координаты):

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

float ZBuffer[SCREEN_WIDTH][SCREEN_HEIGHT];

Каждой точке на экране (пикселю) соответствует один элемент массива, а его значение трактуется как «глубина» этой точки, иными словами, ее координата z в мировой СК. Перед выводом точки ее «глубина» сравнивается с текущим значением в массиве и, если оказывается меньше его, записывается на его место и точка выводится на экран. Таким образом, видимой среди всех точек с одинаковыми координатами x и y оказывается та, у которой координата z минимальна.

Внимательный читатель заметит, что на предыдущем этапе задачу о взаимном расположении точки и треугольника мы решали в плоскости экрана и ни для одной из проверяемых точек координата z вообще неизвестна. Зато известны координаты z вершин треугольной грани, а кроме того, тот очевидный факт, что любая из точек (пусть это будет все та же точка P на рисунке вверху) лежит в плоскости грани. Следовательно, векторы A, C, XP (можно выбрать и другие тройки) компланарны и

Эта система с неизвестными a, b, Zxp легко решается методом подстановки. Сложив Zx и Zxp, мы получим координату z точки P.

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

x’ = ax + by + c;

y’ = dx + ey + f.

Приведенные уравнения справедливы для координат любой точки, в том числе и для вершин, а значит, если мы, например, хотим найти координату u точки P, то должны сначала определить a, b, c, решив систему уравнений

Для решения таких систем часто применяют так называемое правило Крамера. Пусть F11 - определитель, полученный выписыванием коэффициентов перед неизвестными в правой части так, как они расположены в системе, а F12 - определитель, полученный из F11 заменой i-го столбца на столбец свободных членов (левая часть системы). Тогда i-е неизвестное рассчитывается по формуле

Так находятся числа a, b, c и, аналогично, d, e, f, которые затем применяются для расчета текстурных координат точки P. Далее цвет точки текстуры с этими координатами переносится в точку P на экране. Построение точки завершено.

Недостатки концепции

Рассмотренный нами метод работоспособен и вполне надежен. Но у него есть и существенные недостатки, относящиеся, в первую очередь, к скорости построения изображения. Так, изображение модели, состоящей из 1250 граней, на компьютере с процессором Celeron с тактовой частотой 1,3 ГГц строится за 1,5 секунды. Ясно, что для применения в практических задачах метод требуется оптимизировать, прежде всего, уменьшением количества операций умножения и деления чисел.

Настораживают также и требования к объему оперативной памяти: один только z-буфер, являющийся, по сути, вспомогательной структурой, в графическом режиме 640х480 точек потребует 1,2 Мб.

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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Хватит париться. На сайте FAST-REFERAT.RU вам сделают любой реферат, курсовую или дипломную. Сам пользуюсь, и вам советую!
Никита05:45:37 02 ноября 2021
.
.05:45:35 02 ноября 2021
.
.05:45:35 02 ноября 2021
.
.05:45:34 02 ноября 2021
.
.05:45:34 02 ноября 2021

Смотреть все комментарии (22)
Работы, похожие на Реферат: Один метод построения полигональных изображений

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(294402)
Комментарии (4230)
Copyright © 2005 - 2024 BestReferat.ru / реклама на сайте