Основные алгоритмы компьютерной графики. ОТСЕЧЕНИЕ МНОГОУГОЛЬНИКА

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

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

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

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

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

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

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

Простой метод решения проблемы охвата отсекаемым многоугольником вершины окна предлагается в алгоритме Сазерленда-Хогдмана [40], когда весь многоугольник последовательно отсекается каждой границей окна, как это показано на рис. 0.3.23.

При отсечении ребра, соединяющего очередную пару вершин K и L, возможны 4 случая взаимного расположения (рис. 0.3.24):

В случае а) в результат добавляется вершина L. В случае б) в результат заносится S - точка пересечения ребра с границей. В случае в) нет вывода. В случае г) выдаются точка пересечения S и конечная точка ребра L.

Для определения взаимного расположения и направленности используется векторное произведение вектора P₁P₂, проведенного из начальной в конечную точку текущего ребра окна, на вектор P₁S из начальной точки текущего ребра окна в очередную вершину S многоугольника (рис. 0.3.25).

Предложена аппаратная реализация этого алгоритма, состоящая из четырех идентичных ступеней отсечения без промежуточной памяти [28].

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

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

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

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

Возможны 9 различных случаев расположения ребра окна и отсекаемой стороны, показанных на рис. 0.3.26-0.3.28.

На них V₀ и V₁ - начальная и конечная точки отсекаемой стороны многоугольника, соответственно; Nr - нормаль к ребру окна отсечения, направленная внутрь окна.

Из этих рисунков очевидны правила генерации выходных данных, зависящие от варианта взаимного расположения:

2) В выходные данные заносится конечная точка.

3) Рассчитывается пересечение и в выходные данные заносятся точка пересечения и конечная точка.

5) В выходные данные заносится конечная точка.

6) В выходные данные заносится конечная точка.

7) Рассчитывается пересечение и в выходные данные заносится только точка пересечения.

8) В выходные данные заносится конечная точка.

9) В выходные данные заносится конечная точка.

Для определения взаимного расположения, подобно алгоритму отсечения Кируса-Бека, используется скалярное произведение Q вектора нормали на вектор, проведенный из начала ребра в анализируемую точку. Пояснение см. на рис. 8.10.

Таким образом, для определения взаимного расположения начальной V₀ и конечной V₁ точек отсекаемой стороны и ребра отсечения с вектором его начала R, надо вычислить:

Расчет пересечения, если он требуется, производится аналогично алгоритму Кируса-Бека с использованием параметрического представления линии:

Вначале находится значение параметра t для точки пересечения по формуле (см. описание алгоритма Кируса-Бека):

где Qn - скалярное произведение вектора нормали к ребру окна на вектор из начала ребра в начальную точку стороны, уже вычисленное при определении расположения начальной точки, а Pn = (V₁ - V₀)· Nr - скалярное произведение вектора нормали к ребру окна на вектор из начальной в конечную точки отсекаемой стороны.

Легко выразить это произведение через уже вычисленные величины Qn и Qk:

Таким образом, точке пересечения соответствует значение параметра t, равное:

Значения координат пересечения находятся из:

Описанный алгоритм реализован в процедуре V_Plclip, приведенной в Приложении 8.

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

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

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

· входные точки, когда ориентированное ребро отсекаемого многоугольника входит в окно,

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

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

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

· исходная точка пересечения пересечения берется из списка выходных точек,

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

На рис. 0.3.31 иллюстрируется отсечение многоугольника ABCDEFGHI окном PQRS по алгоритму Вейлера-Азертона.

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

Знаете ли Вы, в чем ложность понятия "физический вакуум"?

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

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

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

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

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

Основные алгоритмы компьютерной графики

ОТСЕЧЕНИЕ МНОГОУГОЛЬНИКА

0.7.1 Алгоритм Сазерленда-Ходгмана

0.7.2 Простой алгоритм отсечения многоугольника

0.7.3 Алгоритм отсечения многоугольника Вейлера-Азертона