Компьютерная графика

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

    Некоторые свойства кривой Безье:

• непрерывность заполнения сегмента между начальной и конечной точками;
• кривая всегда располагается внутри фигуры, образованной линиями, соединяющими контрольные точки;
• при наличии только двух контрольных точек сегмент представляет собой прямую линию;
• прямая линия образуется при коллинеарном (на одной прямой) размещении управляющих точек;
• кривая Безье симметрична, то есть обмен местами между начальной и конечной точками (изменение направления траектории) не влияет на форму кривой;
• масштабирование и изменение пропорций кривой Безье не нарушает ее стабильности, так как она с математической точки зрения «аффинно инвариантна»;
• изменение координат хотя бы одной из точек ведет к изменению формы всей кривой Безье;
• степень кривой всегда на одну ступень ниже числа контрольных точек. Например, при трех контрольных точках форма кривой — парабола;
• окружность не может быть описана параметрическим уравнением кривой Безье;
• невозможно создать параллельные кривые Безье, за исключением тривиальных случаев (прямые линии и совпадающие кривые).

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

ІІ.1.4. Сплайны

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

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

     Начало развития теории интерполяции сплайнами и сам термин сплайн насчитывают с 1946 года из статьи Айзека Шонберга. Особенно интенсивное её развитие произошло в 50-70 годы, традиционной прикладной сферой использования интерполяционных сплайнов стали в настоящее время системы автоматизированного проектирования. Однако потенциальные возможности сплайнов значительно шире, чем просто описание некоторых кривых. В реальном мире большое количество физических процессов по самой своей природе являются сплайнами. В механике это деформация гибкой пластины или стержня, зафиксированных в отдельных точках; траектория движения тела, если сила, действующая на него меняется ступенчато (траектория искусственного космического объекта с активными и инерционными отрезками движения, траектория движения самолета при ступенчатой ​​изменении тяги двигателей и изменении профиля крыла и т. д.). В термодинамике это теплообмен в стержне, составленном из фрагментов с различной теплопередачей. В химии — диффузия через слои различных веществ. В электричестве — распространение электромагнитных полей через разнородные среды. То есть, сплайн не надуманная математическая абстракция, а во многих случаях он является решением дифференциальных уравнений, описывающих вполне реальные физические процессы.

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

Сегмент – это часть линии сплайна между двумя соединительными вершинами;

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

Обычно в программах используются четыре типа вершин:

Comer (с изломом) - вершина примыкающие сегменты к которой не имеют кривизны;

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

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

Bezier Comer (Безье с изломом) – вершина которая как и вершина типа Безье снабжена касательным вектором, но у вершин Bezier Comer касательные не связаны друг с другом отрезком, и маркеры можно перемещать независимо.

ІІ.1.5. Алгоритмы заливки плоских фигур

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

 цвет линии;  тип линии (сплошная, пунктирная и пр.); форма концов (со стрелкой, закругленные и пр.).

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

    Существует несколько типов заливок:

 заливка основным цветом, т.е. заполнение внутренней области  выбранным цветом;

 текстурная заливка - заполнение узором с регулярной  структурой;

 заливка изображением-картой (узором) - заполнение готовым растровым  изображением, называемым картой;

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

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

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

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

      Градиентная  заливка. Градиентом называется постепенный переход от одного оттенка или цвета к другому оттенку или цвету. Градиентные заливки в отличие от однородных отображают сложные цветовые переходы между различными цветами. Добавляя в градиент необходимое число промежуточных цветов, можно формировать многоцветные градиентные заливки. В этом случае градиентную заливку можно трактовать как своеобразный узор, образуемый постепенным переходом между двумя или несколькими цветами или оттенками одного итого же цвета. В зависимости от направления перехода цветов существует четыре типа градиентных заливок: линейная, радиальная, коническая и квадратная. Цветовая гамма градиента определяется серией опорных точек, которые обозначаются на шкале цветового перехода специальными маркерами: начальный маркер, конечный маркер цвета и промежуточные маркеры. Опорными точками применительно к градиенту называют точки, в которых тот или иной цвет присутствует в количестве 100% и не смешивается с другими цветами. Маркеры опорных точек можно сдвигать относительно друг друга, настраивая тем самым цветовой рисунок градиента.

ІІ.1.6. Визуализация кривых Безье и шрифтов

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

      Метод разбиения. Построение кривых Безье прямым методом: x=x(t), у=y(t), Подберем шаг dt так, чтобы dx и dy были меньше 1 (т.е. мы не пропустим ни одного пиксела).  и  многочлены, поэтому легко найти их максимумы Мх и Му. Положим M = max(Mx,My). Тогда, взяв, получим, что смещения по х и по у при каждом шаге не превосходят единицу. Недостатком этого метода является то, что при малых смещениях по х и у много итераций рассчитывается впустую.

Построение кривых Безье методом разбиения. Если рассмотреть участок между P0 и , взятых для t=0,5, то он может быть задан как кривая Безье с опорными точками . Аналогичные рассуждения справедливы и для участка между  и P4. Таким образом, можно применить этот алгоритм рекурсивно для левой и правой частей, пока размер участка кривой не станет меньше размера пиксела.

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

ІІ.1.7. Аппроксимация

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

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