2673

Обработка информации, связанная с графическими изображениями на экране

Контрольная

Информатика, кибернетика и программирование

Обработка информации, связанная с графическими изображениями на экране. Обработка информации, связанная с графическими изображениями на экране монитора или на бумаге, подразделяется на 3 основные части: Распознавание образов (изображений) есть совок...

Русский

2012-11-12

382.5 KB

14 чел.

Обработка информации, связанная с графическими изображениями на экране.

Обработка информации, связанная с графическими изображениями на экране монитора или на бумаге, подразделяется на 3 основные части:

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

Символически, распознавание изображений, или система технического зрения COMPUTER VISION, может быть описана так:

• на входе - изображение;

• на выходе – описание этого изображения.

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

Тем самым система обработки изображений IMAGE PROCESSING имеет следующую структуру:

• на входе - изображение;

• на выходе - изображение (преобразование изображений).

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

А еще есть компьютерная живопись, компьютерная анимация и так далее, вплоть до виртуальной реальности.

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

Символически систему компьютерной графики COMPUTER GRAPHICS можно представить следующим образом

• на входе - символьное описание;

• на выходе - изображение (синтез изображений).

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

Направления развития компьютерной графики:

1) иллюстративное,

2) саморазвивающее,

3) исследовательское.

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

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

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

Направления совершенствования компьютерной графики.

  1.  Улучшение динамики изображений.
  2.  Улучшение реалистичности изображений.

Улучшение как 1, так и 2 требует значительных компьютерных ресурсов: быстродействия процессоров и памяти (в первую очередь оперативной и КЭШ-памяти).

Развитие КГ создало новый изобразительный инструмент, который используется художниками, дизайнерами, архитекторами, скульпторами и т. д. Кроме того, существует целый класс профессиональных программных пакетов, которые объединены общей аббревиатурой CADcomputer aidded design (проектирование с помощью компьютера).

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

Растровая и векторная графика.

Все виды графических изображений подразделяются на 2 вида: растровые и векторные.

Растровые изображения связаны с растром. Мозаика пикселов даёт изображение. Каждый из пикселов окрашивается в цвет из палитры. Простейший вид окрашивания – бинарный (всего 2 цвета – чёрный и белый), требует всего одного бита памяти.

True color – 16,7 млн. цветов, 24 бита памяти.

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

  1.  Хранение в памяти изображения, для этого используется видеопамять (память на видеокарте). На каждый пиксел отводится определённое количество бит.
  2.  Регулярный вывод изображения на экран монитора с определённой частотой.

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

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

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

Аффинные преобразования на плоскости.

В компьютерной графике все, что относится к двумерному случаю, принято обозначать символом (2D) (2-dimension).

Допустим, что на плоскости введена прямолинейная координатная система. Тогда каждой точке М ставится в соответствие упорядоченная пара чисел (х, у) ее координат.

Рис. 1

Вводя на плоскости еще одну прямолинейную систему координат, мы ставим в соответствие той же точке М другую пару чисел - (х*,у*).

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

x* = x + y + ,

y* = x + y + ,

где

, , , , - произвольные числа, связанные неравенством

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

(x, y) (x*, y*)

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

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

x* = xcos - ysin,

y* = xsin + ycos.

Рис. 2

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

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

Рис. 3

Б. Растяжение (сжатие) вдоль координатных осей можно задать так:

x* = x,

y* = y,

  0,   0.

Растяжение (сжатие) вдоль оси абсцисс обеспечивается при условии, что > 1 (< 1). На рис. 7.5 =>1.

Рис. 4

В. Отражение (относительно оси абсцисс) (рис. 5) задается при помощи формул

x* = x,

y* = -y.

Рис. 5

Г. На рис. 6 вектор переноса ММ* имеет координаты , и Перенос обеспечивают соотношения

x* = x + ,

y* = y + .

Рис. 6

 Выбор этих четырех частных случаев определяется двумя обстоятельствами.

• каждое из приведенных выше преобразований имеет простой и наглядный геометрический смысл (геометрическим смыслом наделены и постоянные числа, входящие в приведенные формулы);

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

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

, , .

Однородные координаты точки.

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

Пусть М - произвольная точка плоскости с координатами х и у, вычисленными относительно заданной прямолинейной координатной системы. Однородными координатами этой точки называется любая тройка одновременно неравных нулю чисел х1, x2, x3, связанных с заданными числами х и у следующими соотношениями:

= x,  = y.

Рис. 7

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

Заметим, что произвольная точка на прямой, соединяющей начало координат, точку О(0, 0, 0), с точкой М(х, у, /), может быть задана тройкой чисел вида (hx, hy, h). Будем считать, что h  0.

Вектор с координатами (hx, hy, h) является направляющим вектором прямой, соединяющей точки О(0, 0, 0) и М (х, у, 1). Эта прямая пересекает плоскость Z= 1 в точке (х, у, 1), которая однозначно определяет точку (х, у) координатной плоскости ху.

Тем самым между произвольной точкой с координатами (х, у) и множеством троек чисел вида (hx, hy, h), h  0, устанавливается (взаимно однозначное) соответствие, позволяющее считать числа hx, hy, h новыми координатами этой точки.

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

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

х: у: 1, или, более общо, x1,, х2, х3

(напомним, что здесь непременно требуется, чтобы числа x1, х2, х3 одновременно в нуль не обращались).

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

Рассмотрим, например, вопросы, связанные с изменением масштаба. Если устройство отображения работает только с целыми числами (или если необходимо работать только с целыми числами), то для произвольного значения h (например, h = 1) точку с однородными координатами (0.5 0.1 2.5)

представить нельзя. Однако при разумном выборе h можно добиться того, чтобы координаты этой точки были целыми числами. В частности, при h = 10 для рассматриваемого примера имеем (5 1 25).

Возьмем другой случай. Чтобы результаты преобразования не приводили к арифметическому переполнению, для точки с координатами (80000 40000 1000) можно взять, например, h = 0,001. В результате получим (80 40 1).

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

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

В самом деле, считая h = /, сравним две записи: помеченную символом * и нижеследующую матричную:

.

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

Тем самым сравниваемые записи можно считать равносильными.

Замечание. Иногда в литературе используется другая запись - запись по столбцам:

Такая запись эквивалентна приведенной выше записи по строкам (и получается

из нее транспонированием).

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

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

Выпишем соответствующие матрицы третьего порядка.

А. Матрица вращения (rotation)

[R] =

Б. Матрица растяжения (сжатия) (dilatation)

[D] =

В. Матрица отражения (reflection)

[M] =

Г. Матрица переноса (translation)

[T] =

Рассмотрим примеры аффинных преобразований плоскости.

Пример 1. Построить матрицу поворота вокруг точки A(a, b) на угол (рис. 8).

1-й шаг. Перенос на вектор А (-а,-b) для совмещения центра поворота с началом координат;

[T-A] =

матрица соответствующего преобразования.

2-й шаг. Поворот на угол .

[R] =

матрица соответствующего преобразования.

Рис. 8

3-й шаг. Перенос на вектор А(а, b) для возвращения центра поворота в прежнее положение;

[TA] =

- матрица соответствующего преобразования.

Перемножим матрицы в том же порядке, как они выписаны:

[T-A] [R][TA]

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

(x* y* 1) = (x y 1)*

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

Пример 2. Построить матрицу растяжения с коэффициентами растяжения

вдоль оси абсцисс и вдоль оси ординат и с центром в точке A(a,b).

1-й шаг. Перенос на вектор - А(-а,-b) для совмещения центра растяжения с началом координат;

[T-A] =

матрица соответствующего преобразования.

2-й шаг. Растяжение вдоль координатных осей с коэффициентами и соответственно; матрица преобразования имеет вид

[D] =

3-й шаг. Перенос на вектор - А(-а,-b) для возвращения центра растяжения в прежнее положение; матрица соответствующего преобразования -

[T-A] =

Перемножив матрицы в том же порядке

[T-A] [D] [T-A]

получим окончательно:

( x* y* 1) = (x y 1)

Замечание. Рассуждая подобным образом, т. е. разбивая предложенное преобразование на этапы, поддерживаемые матрицами

[R], [D], [M], [T],

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

Преобразования в пространстве, проектирование.

Обратимся теперь к трехмерному случаю (3D) (З-dimension) и начнем наше рассмотрение сразу с введения однородных координат.

Поступая аналогично тому, как это было сделано в размерности два, заменим координатную тройку (х, у, z), задающую точку в пространстве, на четверку чисел (х, у, z, 1) или, более общо, на четверку

(hx, hy, hz, h), h  0.

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

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

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

А. Матрицы вращения в пространстве:

  1.  Матрица вращения вокруг оси абсцисс на угол :

[Rx] =

  1.  Матрица вращения вокруг оси ординат на угол :

[Ry] =

  1.  Матрица вращения вокруг оси аппликат на угол :

[Rz] =

Замечание. Полезно обратить внимание на место знака "-" в каждой из трех приведенных матриц.

Б. Матрица растяжения (сжатия) (маштабирования):

где > 0 - коэффициент растяжения (сжатия) вдоль оси абсцисс;

> 0 - коэффициент растяжения (сжатия) вдоль оси ординат;

> 0 - коэффициент растяжения (сжатия) вдоль оси аппликат.

[D] =

В. Матрицы отражения:

  1.  Матрица отражения относительно плоскости xy:

[Mz] =

  1.  Матрица отражения относительно плоскости yz:

[Mx] =

  1.  Матрица отражения относительно плоскости zx:

[My] =

 

Г. Матрица переноса (здесь (, , ) - вектор переноса):

[T] =

Замечание. Как и в двумерном случае, все выписанные матрицы невырожденны.

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

Пример 1. Построить матрицу вращения на угол вокруг прямой L, проходящей через точку А(а, b, с) и имеющую направляющий вектор (I, т, п). Можно считать, что направляющий вектор прямой является единичным:

l2 + m2 + n2 = 1

На рис. 9 схематично показано, матрицу какого преобразования требуется найти.

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

Рис. 9

1-й шаг. Перенос на вектор -А(-а, -b, -с) при помощи матрицы

[T] =

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

2-й шаг. Совмещение оси аппликат с прямой L двумя поворотами вокруг оси абсцисс и

оси ординат.

Первый поворот - вокруг оси абсцисс на угол (подлежащий определению). Чтобы найти этот угол, рассмотрим ортогональную проекцию L' исходной прямой L на плоскость X = 0 (рис. 10).

Направляющий вектор прямой L' определяется просто - он равен (0, т, п). Отсюда сразу же вытекает, что

cos = , sin = ,

где d = .

Рис 10

Соответствующая матрица вращения имеет следующий вид:

[Rx] =

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

( l, m, n, 1) [Rx] = (l, 0, d, 1)

Второй поворот - вокруг оси ординат на угол , определяемый соотношениями

cos = l, sin = -d.

Соответствующая матрица вращения записывается в следующем виде:

[Ry] =

3-й шаг. Вращение вокруг прямой L на заданный угол .

Так как теперь прямая L совпадает с осью аппликат, то соответствующая матрица имеет следующий вид:

[Rz] =

4-й шаг. Поворот вокруг оси ординат на угол -.

5-й шаг. Поворот вокруг оси абсцисс на угол -.

Замечание: Вращение в пространстве некоммутативно. Поэтому порядок, в котором проводятся вращения, является весьма существенным,

6-й шаг. Перенос на вектор А (а, b, с).

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

[T][Rx][Ry][Rz][Ry]-1[Rx]-1[T]-1.

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

.

Рассматривая другие примеры подобного рода, мы будем получать в результате невырожденные матрицы вида

[A] = .

При помощи таких матриц можно преобразовывать любые плоские и пространственные фигуры.

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

многогранник.

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

Vi (xi, yi, zi), i = l, …, n,

строим матрицу

V =

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

Виды проектирования.

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

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

Рис. 11

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

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

вдоль оси X на плоскость YZ имеет вид: ;

[Px] = .

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

[Px]*=.

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

, .

Замечание. Все три полученные матрицы проектирования вырождении.

При аксонометрической проекции проектирующие прямые перпендикулярны картинной плоскости. j

В соответствии с взаимным расположением плоскости проектирования и координатных осей различают три вида проекций:

• триметрию - нормальный вектор картинной плоскости образует с ортами координатных осей попарно различные углы (рис. 9.17);

• диметрию - два угла между нормалью картинной плоскости и координатными осями равны (рис. 9.18);

• изометрию - все три угла между нормалью картинной плоскости и координатными осями равны (рис. 9.19).

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

[M] =

Покажем, как при этом преобразуются единичные орты координатных осей Z, Y, Z;

(1 0 0 1)[M] = (cos sinsin 0 1),

(0 1 0 1)[M] = (0 cos 0 1),

(0 0 1 1)[M] = (sin -sincos 0 1 ).

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

cos2 + sin2sin2 = cos2

Отсюда следует, что

sin2 = tan2

В случае изометрии имеем

cos2 + sin2sin2 = cos2

sin2 + sin2 cos2 = cos2

Из последних двух соотношений вытекает, что

sin2 = 1/3, sin2 = ½.

При триметрии длины проекций попарно различны.

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

При косоугольном проектировании орта оси Z на плоскость XY (рис. 9.20) имеем:

(0 0 1 1) (  0 1).

Матрица соответствующего преобразования имеет следующий вид:

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

В случае свободной проекции

= = cos,

в случае кабинетной -

= = cos.

Перспективные (центральные) проекции строятся более сложно.

Предположим для простоты, что центр проектирования лежит на оси Z в точке С(0, 0, с) и плоскость проектирования совпадает с координатной плоскостью XY (рис. 12). Возьмем в пространстве произвольную точку М(х, у, z), проведем через нее и точку С прямую и запишем соответствующие параметрические уравнения.

Рис. 12

Имеем:

X* = xt, Y* = yt, Z* = c + (z - c)t.

Найдем координаты точки пересечения построенной прямой с плоскостью XY. Из условия Z* = О получаем, что

,

и далее x, y.

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

В самом деле, переходя к однородным координатам, прямым вычислением совсем легко проверить, что

( x y z 1 )  = ( x y 0 1 - ).

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

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

Замечание. Матрица проектирования, разумеется, вырождена.

Матрица соответствующего перспективного преобразования (без проектирования) имеет следующий вид:

[Q] =

Обратим внимание на то, что последняя матрица невырожденна.

Рассмотрим пучок прямых, параллельных оси Z, и попробуем разобраться в том, что с ним происходит под действием матрицы [Q].

Каждая прямая пучка однозначно определяется точкой (скажем, М (х, у, z)) своего пересечения с плоскостью XY и описывается уравнениями X = х, Y = у, Z = t.

Переходя к однородным координатам и используя матрицу [Q], получаем

(x y t 1)[Q] = (x y t 1-), или 

Устремим t в бесконечность.

При переходе к пределу точка (х, у, t, 1) преобразуется в (О, О, 1, 0). Чтобы убедиться в этом, достаточно разделить каждую координату на t:

Точка (0, 0, -с, 1) является пределом (при t, стремящемся к бесконечности) правой части

рассматриваемого равенства.

Тем самым бесконечно удаленный (несобственный) центр (О, О, 1,0) пучка прямых, параллельных оси Z, переходит в точку (О, О, - с, 1) оси Z.

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

X = x + lt, Y = y + mt, Z = z + nt, n 0,

под действием преобразования, задаваемого матрицей [Q], переходит в собственный пучок

(x + lt y + nt nt 1)[Q] = (x + lt y + mt nt 1- )

центр этого пучка

называют точкой схода.

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

Для преобразования с матрицей [Q] существует лишь одна главная точка схода. В общем случае (когда оси координатной системы не параллельны плоскости экрана) таких точек три.

Матрица соответствующего преобразования выглядит следующим образом:

Пучок прямых, параллельных оси

 OX OY

(1 0 0 0) (0 1 0 0)

переходит в пучок прямых с центром.

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

(1 0 0 -) (0 1 0 -), или (-a 0 0 1) (-b 0 0 1)

Точки (-а, 0, 0) и (О, -b, 0) суть главные точки схода.

РАСТРОВЫЕ АЛГОРИТМЫ.

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

• переведение идеального объекта (отрезка, окружности и др.) в их растровые образы;

• обработка растровых изображений.

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

Достаточно важным понятием для растровой сетки является связность - возможность соединения двух пикселов растровой линией, т. е. последовательным набором пикселов. Возникает вопрос, когда пикселы (х1,y1) и (x2,y2) можно считать соседними.

Вводится два понятия связности:

• 4-связность: пикселы считаются соседними, если либо их x-координаты, либо их y-координаты отличаются на единицу:

• 8-связность: пикселы считаются соседними, если их x-координаты и у-координаты отличаются не более чем на единицу:

Понятие 4-связности является более сильным: любые два 4-связных пиксела являются и 8-связными, но не наоборот. На рис. 6.1 изображены 8-связная линия (а) и 4-связная линия (б).

В качестве линии на растровой сетке выступает набор пикселов P1 P2,..., Рn, где любые два пиксела Pi, Pi+1 являются соседними в смысле заданной связности.

Замечание. Так как понятие линии базируется на понятии связности, то естественным образом возникает понятие 4- и 8-связных линий. Поэтому, когда мы говорим о растровом представлении (например, отрезка), следует ясно понимать, о каком именно представлении идет речь. В общем случае растровое представление объекта не является единственным и возможны различные способы его построения.

Растровое представление отрезка. Алгоритм Брезенхейма.

Рассмотрим задачу построения растрового изображения отрезка, соединяющего очки А(ха, уa) и В(хь, yb). Для простоты будем считать, что 0yb - ya xb - xa

Тогда отрезок описывается уравнением

y = ya +  или y = kx + b,

где k = , b = yakxa.

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

Улучшить внешний вид получаемого отрезка можно за счет округления значений y до ближайшего целого. Фактически это означает, что из двух возможных кандидатов (пикселов, расположенных друг над другом так, что прямая проходит между ними) всегда выбирается тот пиксел, который лежит ближе к изображаемой прямой (рис. 6.3). Для этого достаточно сравнить дробную часть y с 1/2.

Пусть х0 = ха, у0, ..., хn = хb, yn = уb - последовательность изображаемых пикселов, причем

хi+1 xi= 1. Тогда каждому значению xi соответствует число kxi + b.

Обозначим через сi дробную часть соответствующего значения функции

kxi + bci = {kxi + b}

Тогда, если ci  ½, положим

yi = [kxi + b]

в противном случае – yi = [kxi + b] + 1.

Рассмотрим, как изменяется величина сi при переходе от xi к следующему значению xi+1.

Само значение функции при этом изменяется на k.

Если сi + k  ½, то

ci+1 = ci + k, yi+1 = yi.

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

ci+1 = ci + k – l, yi+1 = yi + l,

так как

kxi + b = yi + ci,

kxi+1 + b = yi+1 + ci+1,

а yi+1 – целочисленная величина

Заметим, что с0 = 0, так как точка (x0 , у0) лежит на прямой

y = kx + b

Замечание. Выбор точки можно трактовать и так: рассматривается середина отрезка между возможными кандидатами и проверяется, где (выше или ниже этой середины) лежит точка пересечения отрезка прямой, после чего выбирается соответствующий пиксел. Это метод срединной точки (midpoint algorithm).

Сравнивать с нулем удобнее, чем с 1/2, поэтому введем новую вспомогательную величину di = 2с - 1, заметив, что, di= 2k - 1 (так как с1 = k).

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

, p  Z

Поэтому если домножить величины di и k на

x = xb - xa

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

ОСНОВНЫЕ АЛГОРИТМЫ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ.

Отсечение отрезка.

Алгоритм Сазерленда – Кохена.

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

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

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

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

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

Рис.13

Рис. 14

бит 0 означает, что точка лежит левее прямоугольника,

бит 1 означает, что точка лежит выше прямоугольника,

бит 2 означает, что точка лежит правее прямоугольника,

бит 3 означает, что точка лежит ниже прямоугольника.

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

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

А

Рис. 15

Для решения этой задачи выпустим из точки А(x, y) произвольный луч и найдём количество точек пересечения этого луча с границей многоугольника. Если отбросить случай, когда луч проходит через вершину многоугольника, то решение задачи тривиально – точка лежит внутри, если общее число количество точек пересечения нечетно, и снаружи, если четно.

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

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

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

Рис.16

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

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

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

Закраска области, заданной цветом границы.

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

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

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

Ясно, что по заданной точке (х, у) отрезок [xl, хr] максимальной длины, проходящий через эту точку и целиком содержащийся в области, построить несложно. После заполнения этого отрезка необходимо проверить точки, лежащие непосредственно над и под ним. Если при этом мы найдем незаполненные пикселы, принадлежащие данной области, то для их обработки рекурсивно вызывается функция.

Этот алгоритм способен работать с областями самой сложной формы.

ЗАКРАШИВАНИЕ.

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

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

Свет точечного источника отражается от идеального рассеивателя по закону косинусов Ламберта:

I = Ilkdcos, 0  /2,

где I интенсивность отраженного света;

Il- интенсивность точечного источника;

kd - коэффициент диффузного отражения (постоянная величина, Okl);

θ - угол между направлением на источник света и (внешней) нормалью к поверхности.

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

     

I = Iaka+ Ilkdcos, 0    /2,

где Ia - интенсивность рассеянного света;

ka - (постоянный) коэффициент диффузного отражения рассеянного света, 0 ≤ ka ≤ 1.

Интенсивность света, естественно, зависит от расстояния d от объекта до источника света. Для того чтобы учесть это, пользуются следующей моделью освещения:

I = Iaka +

где. k произвольная постоянная.

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

 Is = Ilkscospα

где ks - экспериментальная постоянная;

 α - угол между отраженным лучом и вектором наблюдения;

р. - степень, аппроксимирующая пространственное распределение света (рис. 2).

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

I = Iaka +

Функцию закраски, используя единичные векторы внешней нормали n, а также единичные векторы, определяющие направления:

на источник (вектор l), отраженного луча (вектор r) и наблюдения (вектор s), можно записать в следующем виде:

I = Iaka +

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

Если точечных источников света несколько, скажем что модель освещения определяется так

I = Iaka +

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

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

Аiх + Вiу + Сiг + Di = 0, i=l,..., m.

 Можно считать, что нормальные векторы этих плоскостей (Аi, Вi, Сi) i=l,...,m,

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

 V1   n2

 n1

V4  V3  

 V2

(A, B, C) = ; V1V2 × V1V3, V1V3 × V1V4, V1V4 × V1V2.

Замечание

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

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

Замечание

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

Для отыскания направления вектора отражения напомним, что единичные векторы падающего света l, нормали

к поверхности n и отражения г лежат в одной плоскости, причем угол падения равен углу отражения (рис. 7).

Рассмотрим модель освещения с одним точечным источником и предположим, что свет падает вдоль оси Z (рис. 8). Тогда координаты единичного вектора отражения

r = (rx, ry, rz)

определяются по формулам

 rx = 2nxnz,

 ry = 2nynz,

 rz = 2nz2 – 1,

где n = (nx, ny, nz) - единичный вектор нормали к поверхности.

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

rx = -lx, ry = -ly, rz = lz.

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

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

Существуют специальные методы закрашивания, позволяющие создавать иллюзию гладкости.

Опишем два известных метода построения сглаженных изображений.

Закраска методом Гуро.

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

Обратимся к рис. 10, на котором изображена выпуклая четырехугольная грань. Предположим, что интенсивности в ее вершинах V1, V2, V3 и V4 известны и равны соответственно Iv1, Iv2, Iv3, Iv4.

Пусть W - произвольная точка грани. Для определения интенсивности (освещенности) в этой точке проведем через нее горизонтальную прямую. Обозначим через U и V точки пересечения проведенной прямой с границей грани;

Будем считать, что интенсивность на отрезке UV изменяется

   V3

линейно, то есть  

Iw = (1-t)Iu + tIv, V2

  V4  W

Где t = , 0 ≤ u ≤ 1, v =  U V

    V1

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

Тогда интенсивность в точках U и V вычисляется по формулам

Iu = (1- u)Iv4 + uIv1,

Iv = (1 - v)Iv1 + vIv2,

где u = , 0≤ u ≤1, v = , 0≤ v ≤1.

Метод Гуро обеспечивает непрерывное изменение интенсивности при переходе от одной грани к другой без разрывов и скачков.

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

Таким образом, процесс рисования грани слагается из следующих шагов:

1) проектирование вершин грани на экран;

2) отыскание интенсивностей в вершинах по формуле (3);

3) определение координат концов очередного отрезка и значений интенсивности в них линейной интерполяцией;

4) рисование отрезка с линейным изменением интенсивности между его концами.

Закраска методом Фонга.

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

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

I = Iaka + ( kdcosθ + kscospα )

Схема интерполяции при закраске Фонга аналогична интерполяции в закраске Гуро, а именно: для определения вектора нормали в точке W – nw, через эту точку проводят горизонтальную прямую

nw = , где

t = ,

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

nu = (1-u)nv4 + unv1

nv = (1-v)nv4 + vnv2

u = ,

v = .

УДАЛЕНИЕ НЕВИДИМЫХ ЛИНИЙ

И ПОВЕРХНОСТЕЙ.

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

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

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

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

• способу представления объектов;

• способу визуализации сцены;

• пространству, в котором проводится анализ видимости;

• виду получаемого результата (его точности).

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

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

Координаты в исходном трехмерном пространстве будем обозначать через (х, у, z), а координаты в картинной плоскости - через (X, Y). Будем также считать, что на картинной плоскости задана целочисленная растровая решетка - множество точек (i,j), где i и j - целые числа.

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

Х = х, Y=y,

либо является центральным с центром, расположенным на оси Oz, и задается формулами

X =, Y = .

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

Анализ видимости объектов можно производить как в исходном трехмерном пространстве, так и на картинной плоскости. Это приводит к разделению методов на два класса:

• методы, работающие непосредственно в пространстве самих объектов;

• методы, работающие в пространстве картинной плоскости, т. е. работающие с проекциями объектов.

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

Построение графика функции двух переменных. Линии горизонта.

Рассмотрим задачу построения графика функции двух переменных z =f(x, у) в виде сетки координатных линий х = const и у = const .

При параллельном проектировании вдоль оси Oz проекцией вертикальной линии в объектном пространстве будет вертикальная линия на картинной плоскости (экране). Легко убедиться в том, что в этом случае точка р(х, у, z) переходит в точку ((р, е1), (р, e2)) на картинной плоскости, где

e1 = (cos, sin, 0),

e2 = (sinsin, -cossin, cos),

а направление проектирования имеет вид

e3 = (sincos, -coscos, -sin),

где

  [0, 2],   [-].

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

Рассмотрим сначала построение графика функции в виде набора линий, соответствующих постоянным значениям у, считая, что углы φ и ψ подобраны таким образом, что при y1>y2 плоскость у = y1 расположена ближе к картинной плоскости, чем плоскость у = y2.

 Каждая линия семейства z = f(x, yi) лежит в своей плоскости у = yi, причем все эти плоскости параллельны и, следовательно, не могут пересекаться. Из этого следует, что при уj > yt линия z = f(x, yj) не может закрывать собой линию z = f(x, yi) и, значит, каждая линия z =f(x, yj) может быть закрыта только предыдущими линиями z = f(x, yi), I = 1,…,j-1.

Тем самым возможен следующий алгоритм построения графика функции z = f(x, y): линии рисуются в порядке удаления (возрастания у - front-to-back) и при рисовании очередной линии выводится только та ее часть, которая ранее нарисованными линиями не закрывается.

Для определения частей линии z = f(x, уk), которые не закрывают ранее нарисованных линий, вводятся так называемые линии горизонта, или контурные линии.

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

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

Рассмотрим область экрана между верхней и нижней линиями горизонта - она является проекцией части графика функции, заключенной в полосе y1 ≤ yy2, и, очевидно, находится ближе, чем все остальные линии вида z =f(x, уi), i > 2. Поэтому те части линий, которые при проектировании попадают в эту область, указанной частью графика закрываются и при данном способе проектирования не видны.

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

Пусть проекцией линии z = f(x, yk) на картинную плоскость является линия Y = Yk(X), где (X, Y) - координаты на картинной плоскости, причем Y- вертикальная координата. Контурные линии Ykmax(X) и Ykmin(X) определяются следующими соотношениями:

Ykmax(X) = Yi (x),

Ykmin(X) = Yi (x).

На экране рисуются только те части линии

Y = Yk (x)

которые, находятся выше линии

Ykmax(X)

или ниже линии

Ykmin(X)

Такой алгоритм называется методом плавающего горизонта.

Методы оптимизации.

Отсечение нелицевых граней.

Рассмотрим многогранник, для каждой грани которого задан единичный вектор внешней нормали (рис. 17). Несложно заметить, что если вектор нормали грани п составляет с вектором l, задающим направление проектирования, тупой угол (вектор нормали направлен от наблюдателя), то эта грань заведомо не может быть видна (рис. 18). Такие грани называются нелицевыми. Если соответствующий угол является острым, грань называется лицевой.

При параллельном проектировании условие на угол можно записать в виде неравенства (п, l) ≤ 0, поскольку направление проектирования от грани не зависит.

При центральном проектировании с центром в точке с вектор проектирования для точки р будет равен

l = с -р.

Для определения того, является заданная грань лицевой или нет, достаточно взять произвольную точку р этой грани и проверить выполнение условия (п, l) ≤ 0.

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

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

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

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

Рис. 17

Рис. 18

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

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

Рис. 19

Удаление невидимых линий.

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

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

Опишем этот алгоритм.

Сначала отбрасываются все ребра, обе определяющие грани которых являются нелицевыми (ни одно из таких ребер заведомо не видно).

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

• грань ребра не закрывает (рис. 20);

Рис. 20

• грань полностью закрывает ребро (тогда оно удаляется из списка рассматриваемых ребер ) (рис. 20, а);

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

Рассмотрим, как осуществляются эти проверки.

Пусть задано ребро АВ, где точка А имеет координаты (xa, ya ), а точка В - (хь, уь).

Прямая, проходящая через отрезок АВ, задается уравнениями

x = xa + t(xb - xa),

y = ya + t(yb - ya).

причем сам отрезок соответствует значениям параметра

0  t  1.

Данную прямую можно задать неявным образом как F(x, у) = 0, где

F(x, y) = (yb – ya)(x – xa) – (yb – xa)(y – ya).

Предположим, что проекция грани задается набором проекций вершин Р1, ..., Pk с координатами i,,уi), i = 1, ..., п. Обозначим через Fi значение функции F в точке Pi и рассмотрим i-й отрезок проекции грани Рi Рi+1 Этот отрезок пересекает прямую АВ тогда и только тогда, когда функция F принимает значения разных знаков на концах этого отрезка, а именно при

FiFi+1 0.

Случай, когда

Fi+1 = 0

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

Fi0, Fi+10,

Fi0, Fi+10.

Точка пересечения определяется соотношениями

x = xi + s(xi+1 - xi),

y = yi +s(yi+1 - yi),

где s = .

Отсюда легко находится значение параметра t:

t =

.

Возможны следующие случаи:

  1.  Отрезок не имеет пересечения с проекцией грани, кроме, быть может, одной точки. Это может иметь место, когда

• прямая АВ не пересекает ребра проекции (рис. 20, а);

• прямая АВ пересекает ребра в двух точках t1 и t2 ,но либо t1< О, t2 < 0, либо t1 > 1, t2 > 1 (рис. 20, б);

• прямая АВ проходит через одну вершину, не задевая внутренности треугольника (рис. 20, в).

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

2. Проекция ребра полностью содержится внутри проекции грани (рис. 21, а). Тогда есть две точки пересечения прямой АВ и границы грани и t1< 0 < 1 < t2 Если грань, лежит ближе к картинной плоскости, чем ребро, то ребро полностью невидимо и удаляется.

3. Прямая АВ пересекает ребра проекции грани в двух точках и либо

t1 0  t2 1, либо 0  t1 1  t2 (рис. 21 б и в).

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

Рис. 21

4. Прямая АВ пересекает ребра проекции грани в двух точках, причем

0  t1  t2 1 (рис. 21 г).

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

Для определения того, что лежит ближе к картинной плоскости - отрезок АВ (проекция которого лежит в проекции грани) или сама грань, через эту грань проводится плоскость

(n, p) + c = 0

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

Если общее количество граней равно п, то временные затраты для данного алгоритма составляют О(п2).

Количество проверок можно заметно сократить, если воспользоваться разбиением картинной плоскости.

Разобьем видимую часть картинной плоскости (экран) на N1 x N2 равных частей (клеток) и для каждой клетки Аij построим список всех лицевых граней, чьи проекции имеют с данной клеткой непустое пересечение.

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

В качестве шага разбиения обычно выбирается О(1), где l-характерный размер ребра в сцене. Для любого ребра количество проверяемых граней практически не зависит от общего числа граней и совокупные временные затраты алгоритма на проверку пересечений составляют О(п), где п - количество ребер в сцене.

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

Количественная невидимость. Алгоритм Аппеля.

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

У точек, для которых (п, l)=0, подобной окрестности (состоящей только из лицевых или только нелицевых точек) может не существовать. Такие точки, в отличие от (регулярных) точек называются нерегулярными (особыми) точками проектирования (рис. 10.21).

В общем случае множество всех нерегулярных точек

(п,1) = 0

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

Попытаемся обобщить этот подход на случай одного или нескольких невыпуклых тел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так, для многогранника на рис. 22 контурной линией является ломаная ABCIJDEKLGA.

Рассмотрим, как меняется количественная невидимость вдоль ребра.

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

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

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

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

Рис. 22

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

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

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

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

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

Удаление невидимых граней.

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

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

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

Одним из преимуществ этого метода является простота, универсальность (он может легко работать не только с полигональными моделями; возможно использование Constructive Solid Geometry) и возможность совмещения определения видимости с расчетом цвета пиксела.

Еще одним несомненным плюсом метода является большое количество методов , оптимизации, позволяющих работать с сотнями тысяч граней и обеспечивающих временные затраты порядка O(Clogn), где С - общее количество пикселов па экране, a n- общее количество объектов в сцене. Более того, существуют методы, обеспечивающие практическую независимость временных затрат от количества объектов.

Метод z-буфера.

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

Поставим в соответствие каждому пикселу (х, у) картинной плоскости кроме , цвета с(х, у), хранящегося в видеопамяти, его расстояние до картинной плоскости вдоль направления проектирования z(x, у) (его глубину).

Массив глубин инициализируется +∞.

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

Метод z-буфера работает исключительно в пространстве картинной плоскости и не требует никакой предварительной обработки данных. Порядок, в котором грани выводятся на экран, не играет никакой роли.

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

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

Алгоритмы упорядочения.

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

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

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

Упорядочим все лицевые грани таким образом, чтобы при их выводе в этом порядке получалось корректное изображение сцены. Для этого необходимо, чтобы для любых двух граней Р и Q та из них, которая при выводе может закрывать другую, выводилась позже. Такое упорядочение обычно называется back-to-front, поскольку сначала выводятся более далекие грани, а затем более близкие.

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

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

Рис. 23

Метод сортировки по глубине. Алгоритм художника.

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

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

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

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

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

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

Приведенная ниже программа осуществляет построение изображения тора на основе этого метода. Тор, описываемый уравнениями

x = (R + rcos)cos,

y = (R + rsin)cos,

z = rsin,

представляется в виде набора треугольных граней. После этого для сортировки граней по расстоянию до наблюдателя используется стандартная процедура qsort.

Расстояние от точки р до наблюдателя, расположенного в начале координат, при параллельном проектировании вдоль единичного l задается следующей формулой: d = (р, l).

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

Предлагается следующий алгоритм этой проверки. Для простоты будем считать, что рассматривается параллельное проектирование вдоль оси Oz.

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

Ниже приведены 4 теста в порядке возрастания сложности проверки:

1. Пересекаются ли проекции этих граней на ось Ох?

2. Пересекаются ли проекции этих граней на ось Оу?

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

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

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

3. Находятся ли грань Р и наблюдатель по разные стороны от плоскости, проходящей через грань Q (рис. 25)?

4. Находятся ли грань Q и наблюдатель по одну сторону от плоскости, проходящей через грань Р, (рис. 26)?

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

В случае, если ни один из тестов не подтвердил правильность упорядочения граней Р и Q, проверяем, не следует ли поменять эти грани местами. Для этого проводятся тесты, являющиеся аналогами тестов 3 и 4 (очевидно, что снова проводить гесты 1 и 2 не имеет смысла):

  •  3'. Находятся ли грань Q и наблюдатель по разные стороны от плоскости, проходящей через грань Р?
  •  4'. Находятся ли грань Р и наблюдатель по одну сторону от плоскости, проходящей через грань Q?

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

Возможны ситуации, когда несмотря на го, что грани Р и Q упорядочены верно, их разбиение все же будет произведено (алгоритм создает избыточные разбиения). Подобный случай изображен на рис. 27, где для каждой вершины указана ее глубина.

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

Методу упорядочения присущ тот же недостаток, что и методу z-буфера, а именно необходимость вывода всех лицевых граней. Чтобы избежать этого, можно его модифицировать следующим образом: грани выводятся в обратном порядке - начиная с самых близких и заканчивая самыми далекими (front-to-back). При выводе очередной грани рисуются только те пикселы, которые еще не были выведены. Как только весь экран будет заполнен, вывод граней можно прекратить.

Рис.27

Метод двоичного разбиения пространства.

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

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

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

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

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

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

Получаем в результате двоичное дерево (Binary Space Partitioning Tree). Узлами этого дерева являются плоскости, производящие разбиение. Пусть плоскость, производящая разбиение, задается уравнением

(p, n) = d

Рис.28

Метод построчного сканирования.

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

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

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

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

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

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

Рис.29

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

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

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

Возможны 4 различных случая:

1. Проекция грани полностью накрывает область (рис. 30, а);

2. Проекция грани пересекает область, но не содержится в ней полностью (рис. 30, б);

3. Проекция грани целиком содержится внутри области (рис. 30, в);

4. Проекция грани не имеет общих внутренних точек с рассматриваемой областью (рис. 30, г).

Рис. 30

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

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

• проекция ни одной грани не попадает в область;

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

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

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

 Рис.31

Естественно возникает вопрос о критерии, на основании которого прекращать разбиение (иначе оно может продолжаться до бесконечности).

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

ГЕОМЕТРИЧЕСКИЕ СПЛАЙНЫ.

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

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

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

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

Достаточно типичной является следующая задача: по заданному массиву точек на плоскости (2D) или в пространстве (3D) построить кривую либо проходящую через все эти точки (задача интерполяции), либо проходящую вблизи от этих точек (задача сглаживания).

Совершенно естественно возникают вопросы:

1) в каком классе кривых искать решение поставленной задачи? и

2) как искать?

Сплайн-функции.

Случай одной переменной.

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

А) решение было единственным

Б) построенная кривая изменялась плавно.

Пусть на плоскости задан набор точек (xi, yi) i = 0, … m, таких, что они упорядочены следующим образом:

x0x xm, т. е. точки пронумерованы в порядке возрастания вдоль оси OX, это позволяет искать кривую в классе графиков функций.

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

Lm(x) = , где

.

График этого полинома (многочлена) проходит через все заданные точки. Многочлен однозначно определяется набором своих коэффициентов, число которых совпадает с количеством точек в заданном наборе (m+1).

Недостатки:

1. Степень многочлена Лагранжа = m, если заданных точек (m+1), поэтому чем больше точек, тем больше степень полинома Лагранжа, и хотя он гарантированно пройдет через все заданные точки, но если его порядок велик, то отклонение от ожидаемых значений всегда может быть существенным.

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

Самый простой способ построения искомой кривой – соединение точек набора прямолинейными отрезками, но получается ломаная. При такой кусочно – линейной интерполяции нужно найти всего 2m чисел, но при этом мы не получаем необходимой гладкости кривой (математически – нахождение производных).

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

y = S (x).

Сплайн – функция обладает следующими свойствами:

1. С довольно большой точностью часть графика функции между двумя любыми соседними опорами (точками) можно приблизить к многочленам 3-ей степени и на всём промежутке от x0 до xm эта функция дважды непрерывно дифференцируема. Такая функция относится к интерполяционным кубическим сплайнам.

Интерполяционный кубический сплайн – это функция S(x), обладающая следующими свойствами:

  •  График функции проходит через каждую точку заданного массива

S(xi) = yi, i = 0…m

  •  На каждом из отрезков [xi, xi+1], i = 0…m-1, функция является многочленом 3 степени

S(x) =

  •  На всём отрезке от х0 до хm функция S(x) имеет непрерывную производную.

  1.  На каждом отрезке сплайн S(x) определяется четырьмя коэффициентами, поэтому для полного построения сплайна на всём большом отрезке надо найти 4m чисел.

 

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

xi (i = 1, 2, … m-1)

это даёт m-1 условие на коэффициент. Ещё m-1 условие даёт требование непрерывности первой производной во внутренних узлах и ещё m-1 – второй.

Всего 4m – 2 условий на коэффициенты.

Недостающие 2 условия для полного определения коэффициентов получают, например, задавая значение 1-ых производных на концах отрезков.

S’(x0) = l0 ,S’(xm) = lm- граничные условия.

Бывают граничные условия и других типов.


Сплайновые кривые.

Будет пользоваться параметрическими уравнениями кривой. Параметрически заданной кривой называется множество у точек М (х, у, z), координаты х, у, z которых определяются соотношениями:

x=x(t), y=y(t), z=z(t), (1)

где x(t), y(t), z(t) функции, непрерывные на заданном интервале.

Соотношения (I) называются параметрическими уравнениями кривой у.

Если представить, что мы вводим новую переменную u = , то можно представить, что a=0, b=1, т. е. осуществить нормализацию параметров функции.

Часто используют векторную форму записи параметрических уравнений:

r(t) = , 0 t 1

Параметр t задает ориентацию параметризованной кривой r(t) (порядок прохождения точек при монотонном возрастании параметра).

Дальше можно задавать первую производную кривой и если r’(t) = 0 в каждой точке, то кривая называется регулярной, т. е. в каждой точке кривой существует касательная.

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

K(t) = .

Кривая Безье.

Кривой Безье, определяемой массивом V, называется кривая, определяемая векторным уравнением

r(t) = ,

t  [0, 1],

где Сim =  - биномиальный коэффициент, Cim – число сочетаний из m элементов по i.

Кривая Безье обладает замечательными свойствами:

• она является гладкой;

• начинается в точке v0 и заканчивается в точке Vm , касаясь при этом отрезков V0 V1, и Vm-1Vm контрольной ломаной;

• функциональные коэффициенты Cimti(1-t)m-i при вершинах Vi, i=0, I, .... m, представляет собой универсальные многочлены (многочлены Бернштейна); они неотрицательны, и их сумма равна единицы:

  V1 V2 V3

V0    V6 V3 V4

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

При m = 3 получаем (элементарную) кубическую кривую Безье, определяемую четверкой точек V0, V1, V2, V3 и описываемую векторным параметрическим уравнением:

r(t) = (((1-t)3V0 + 3tV1)(1-t)2 + 3t2V2)(1-t) + t3V3,

t[0, 1].

Порядок точек в заданном наборе влияет на вид кривой Безье.

   3 4

2 3

14 12

  4 2

13


 

А также другие работы, которые могут Вас заинтересовать

65531. СИСТЕМНІ ТА ФІЗИКО-МЕХАНІЧНІ ОСНОВИ ПРОЕКТУВАННЯ РОЗПУШУВАЧІВ ҐРУНТУ 411.5 KB
  Розробка комплексу нових знарядь можлива при системному підході тобто при розгляді обробітку ґрунту як доповнення до природних ґрунтоутворюючих процесів на основі більш повного урахування механічних фізичних і біологічних властивостей ґрунту.
65532. Створення адаптивних засобів обліку і аналізу якості електроенергії 391 KB
  Обсяг спожитої електричної енергії фіксується електролічильниками а її якість контролюється приладами для вимірювання показників якості. Подана робота присвячена питанням розробки адаптивних засобів обліку електроенергії вимірювання показників її якості та відтворення...
65533. МЕТОДИ, МОДЕЛІ ТА ЗАСОБИ ПРОЕКТУВАННЯ І УПРАВЛІННЯ БІЗНЕС-ПРОЦЕСАМИ ДЛЯ ОРГАНІЗАЦІЙНО-ТЕХНІЧНИХ ОБ’ЄКТІВ УПРАВЛІННЯ 721 KB
  Сучасне процесне управління підприємствами і організаціями включає в себе управління гнучкими бізнеспроцесами орієнтованими на користувача і мінливими під впливом внутрішніх і зовнішніх чинників.
65534. МАЛЕ ПІДПРИЄМНИЦТВО В СИСТЕМІ РЕГІОНАЛЬНОГО РОЗВИТКУ 322 KB
  Хоч протягом усього пeрiоду ринкових рeформ в eкономiчнiй лiтeртурi бгто увги придiлялося проблeмм розвитку в Укрїнi млого бiзнeсу лe його стн всe щe злишється нeздовiльним. Проблeм полягє нвiть нe в кiлькiсних прмeтрх функцiонувння цiєї сфeри якi поступово полiпшуються нсмпeрeд – у структурi вiтчизняного...
65535. Інформаційна технологія синтезу моделей систем управління автоматизованими процесами 1.05 MB
  При створенні нових інформаційних технологій ІТ сучасні комп’ютери та різні спеціалізовані математичні моделі слугують фундаментом побудови нових методів перетворення інформації для складних систем управління ССУ.
65536. РЕФРАКЦІЙНА КЕРАТОПЛАСТИКА АМЕТРОПІЙ (ВДОСКОНАЛЕННЯ ТЕХНОЛОГІЇ, ПРОГНОЗУВАННЯ РЕЗУЛЬТАТІВ, ПОПЕРЕДЖЕННЯ РОЗВИТКУ УСКЛАДНЕНЬ) 389.5 KB
  Тенденції світової офтальмохірургії за останні роки переконливо свідчать про бурхливий розвиток керато-рефракційної хірургії заснованої на моделюванні передньої поверхні рогівки шляхом пошарового її зрізання методом кератомільозу.
65537. АВТОМАТИЧНИЙ КОНТРОЛЬ СТУПЕНЯ ЗДРІБНЕННЯ РУДИ В ТЕХНОЛОГІЧНИХ КОМПЛЕКСАХ ФЛОТАЦІЙНОГО ТА МАГНІТНОГО ЗБАГАЧЕННЯ 272.5 KB
  Завданням автоматизації здрібнення перед флотаційним або магнітним збагаченням є розкриття руд зі змінними фізикомеханічними властивостями тобто здрібнення їх до такої оптимальної крупності при якій частки корисного мінералу дезінтегруються з порожньою породою...
65538. Етіопатогенетичне обґрунтування способу лікування карієсу у дітей молодшого шкільного віку 156 KB
  Карієс зубів обумовлений прогресуючою демінералізацією зубних тканин викликаною кислотоутворюючими автохтонними бактеріями ротової порожнини серед яких найбільший карієсогенний потенціал мають стрептококи.
65539. МІЦНІСТЬ ТА ДЕФОРМАЦІЇ ЗАЛІЗОБЕТОННИХ ЕЛЕМЕНТІВ З ВИСОКОМІЦНОГО БЕТОНУ З УРАХУВАННЯМ ТРИВАЛОСТІ НАВАНТАЖЕННЯ І НЕРІВНОМІРНОГО НАГРІВАННЯ ДО +200 С 5.05 MB
  Для даного часу характерна характерною тенденціэю тенденцією в будівельній галузі є інтенсивний розвиток висотного будівництва з монолітного залізобетону із застосуванням сучасних високоякісних бетонів які мають високі характеристики міцності...