Задание бкс по безье
Безье несколько улучшил способ начального задания контрольныз точет проектируемого сегмента, сократив вектора скоростей в 3 раза и придав им несколько иной смысл.
|
Описание сегмента все равно сводится к восьмерке чисел: СЕГМЕНТ (P1x, P1y, P2x, P2y, P3x, P3y, P4x, P4y).
|
Производя выкладки, аналогичные приведенным выше, можно получить вектор коэффициентов для случая Безье
Или Сх = МБх * GБх.
МБх – матрица Безье,
GБх – геометрический вектор Безье.
Этот метод задания БКС применяется широко.
Сплайны
В проектировании крупных объектов люди давно столкнулись с проблемой отрисовки длинных гладких кривых, например, обводов судов, вычерчиваемых на плазах.
|
|
Технически эта проблема успешно решалась с помощью сплайна – гибкой упругой металлической ленты, получившей название «сплайн».
Как ни удивительно, форма такой кривой описывается через бикубические сегменты.
НЕПРЕРЫВНОЕ СОПРЯЖЕНИЕ СЕГМЕНТОВ
В компьютерной графике различают следующие способы состыковки БКС в состаной кривой:
Если кривая вовтыкована из БКС только гладкими узлами, ее принято называть «сплайн» из сегментов Безье
Бикубические сегменты в формате Безье являются в компьютенрой графике наиболее распространенным универсальным примитивом для векторных изображений.
СТРУКТУРА ВЕКТОРНОГО ПРОИЗВЕДЕНИЯ
Логический уровень
Произведение – множество слоев. Слой - множество бикубических сегментов.
Уровень данных
Произведение – это мультисписок. Верхний уровень – список слоем с их атрибутами. Второй уровень мультисписка – это список БКС.
Визуализация
Показанную выше структуру данных приходится визуализировать с помощью специальных программ, называемых «Векторные графические процессоры». Наиболее известны такие:
Adobe ILLUSTRATOR
Corel DRAW!
Macromedia FreeHands
Harvard Graphics
. . .
ИТОГИ
Векторное представление изображений основано на примитивах. Базовым примитивом является бикубический сегмент Безье в силу его универсальности.
Сегменты описываются параметрически, т.к. при этом нет вырожденных случаев расположения.
Программной моделью векторного произведения является мультисписок. Верхний уровень мультисписка – это список слоёв, нижний уровень – это списки примитивов.
Для визуализации векторного произведения требуется специальная программа – векторный графический процессор.
3 Алгоритмы вычислительной геометрии. Геометрия на плоскости План раздела
Отсечение отрезков по окну. Метод Коэна-Сазерленда.
Классификация точки относительно отрезка.
Пересечение двух отрезков.
Проверка принадлежности точки многоугольнику.
Вычисление площади многоугольника.
Построение выпуклой оболочки.
Отсечение многоугольников. Алгоритм Сазерленда-Ходжмана.
Триангуляция Делоне.
Отсечение отрезков по окну
Истоки проблемы
Задача отсечения возникает при отображении графических примитивов, которые составляют векторный документ, на устройство вывода.
Структура данных может содержать весьма большой ихобъем данных, но показывается чаще всего некоторая часть, ограниченная прямоугольной областью, называемой «окном». Суть в том, что ресурсы компьютера надо тратить на вывод только той части изображения, которая попадает в окно.
Формализация по Коэну-Сазерленду
Примем, что сцена нарисована только отрезками прямых. Коэн и Сазерленд предложили способ, с поомощью которого все отрезки можно быстро разделить на такие группы:
А) те, что находятся вне окна. Они невидимы и при выводе они пропускаются.
Б) те, что полностью попадают в окно. Они выводятся.
В) те, что пересекаются границами окна. С каждым из них нужно провести отсечение и тогда он будет разделен на два подотрезка, которые относятся либо к группе А), либо Б).
Идея способа состоит в том, что каждому концу каждого отрезка сопоставляется четырехбитный код, биты которого отражают положение конца относительно границ окна.
Вычисление кода положения точки
Функция, приведенная ниже, вычисляет код Коэна-Сазерленда для заданной точки.
int outCode(int x, int y, int x1, int y1, int x2, int y2) {
int Code=0;
if( x < x1) // левее
Code |= 0x01;
if( y > y2) // выше
Code |= 0x02;
if( x > x2) // правее
Code |= 0x04;
if( y < y1) // ниже
Code |= 0x08;
return Code;
}
Отсечение отрезка и его вывод
Эта функция отсекает отрезок по границам окна и выводит его видимую часть.
Классификация точки относительно отрезка
Это значит – получить ответ о том, в какой области плоскости относительно заданного отрезка находится точка с изверстными координатами. Таких областей условно различают шесть, они показаны на рисунке.
Справа или слева?
Ответ на ,этот вопрос можно найти по знаку векторного произведения векторов a и b.
Если V<0, то точка слева, иначе справа.
Классификация вдоль длины отрезка
То есть «сзади», «между» или «спереди»? Для этого вспомним, как вычисляется скалярное произведение:
При b*<0 точка «сзади»; при b*>0 и b*< |a| точка «между», »; при b*>0 и b*> |a| точка «спереди».
Расстояние от точки до прямой
Пересечение двух отрезков
Отрезки заданы параметрически, параметры r и s .
При вычислении точки пересечения надо страховаться от случа параллельности отрезков. Тогда точки пересечения нет. Первое из приведенных неравенств определяет непараллельность.
Второе равенство определяет радиус-вектор точки пересечения. Решением этого векторного уравнения является пара значений sx и rx, координирующие точку персечения на линиях – носителях отрезков.
Разные случаи относительного расположения отрезков показаны на рисунках ниже:
Проверка принадлежности точки многоугольнику
Часто даже взглядом человека нельзя сразу определить, вне замкнутого многоугольника или внутри него находится точка:
Формально это определяется по тому, четное или нечетное число пересечений с многоугольником имеет произвольный луч, проведенный из интересующей точки. При четном – точка вне многоугольника, при нечетном – внутри.
Площадь многоугольника
Если имеется произвольный замкнутый многоугольник без самопересечений, то его площадь можно вычислить по приводимой формуле.
Построение выпуклой оболочки
Это задача вычислительной геометрии, котрая часто встречается. Пусть дано произвольное множествоточек на плоскости, не находящихся на одной прямой:
Так может выглядеть выпуклая оболочка такого набора. Для заданного множества точек она единственная.
Метод «заворачивания подарка»
1.Выбираем самую левую из самыхнижних точек множества и проводим лув вправо.
2. Поворачиваем луч против часовой стрелки, пока не встретимся с точкой множества. Первое ребро оболочки определилось.
3. Переходим в найденную точку и повторяем шаг 2.
4. Циклически повторяем шаг 3, пока не прийдем в начальную точку.
Действия напоминают заворачивание коробки в бумагу при упаковке подарка, откуда и название.В алгоритме используется как вспомогательный метод классификации точки относительно отрезка.