русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Алгоритмы рисования закрашенного многоугольника


Дата добавления: 2013-12-23; просмотров: 2016; Нарушение авторских прав


Алгоритм де Костельжо

Кривые Безье. Алгоритм де Костельжо

Кривые Безье — это универсальный способ задания произвольных кривых на плоскости или в пространстве. Задаются многочленом Берштейна:

 

где

n — степень кривой

P0 .. Pn — опорные точки, их как минимум две

t ∈ [0,1]

Свойства:

● Гладкость и непрерывность

● Количество изгибов зависит от количества опорных точек

● Степень многочлена Берштейна на один меньше количества опорных точек

● Легко выполнить сложные преобразования (поворот, перенос,..., либо их комбинация)

● Кривая лежит в оболочке опорных точек, которая является многоугольником.

● Кривая всегда проходит через P0 и Pn, и в этих точках касательные к кривой параллельны отрезкам P0P1 и Pn-1Pn.

● Если рассматривать точки в обратном порядке, то форма кривой не изменится.

● Если кривую Безье разбить точкой P(t*), то мы получим две кривые Безье: t ∈ [0,t*] и t ∈ [t*,1]. Таким образом, кривую Безье высшего порядка порядка можно представить в виде набора кривых Безье низшего порядка.

Недостатки:

● Очень много вещественных вычислений

● Трудно подобрать Δt:

○ если взять слишком большим, будут разрывы,

○ если взять слишком маленьким, прорисовка будет повторяться несколько раз.

 

Задача: построить кривую P(t) по ломаной P0 … Pn.

Сначала берем t* = ⅓ и делим в таком отношении каждое звено ломаной. Полученные точки соединяем и получаем новую ломаную, степень которой меньше степени исходной ломаной на 1. Повторяем процесс, пока степень не станет равной единице, то есть пока ломаная не выродится в точку. Эта точка будет принадлежать кривой Безье.

Дальше берем t* = ½ и повторяем алгоритм, и так далее, пока t* не сольётся с P0 (с заданной точностью)



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

NURBS— рациональные кривые Безье. Для каждой точки вводится ещё и вес (может быть и отрицательным). Он показывает, насколько точка “притягивает” к себе кривую. В этом случае кривая задается: — многочлен Берштейна.

В обычной кривой Безье все w = 1.

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

1 Алгоритм с упорядоченным списком рёбер (для закраски многоугольников)

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

1 Вычисляются координаты охватывающего прямоугольника: ymin, ymax, xmin, xmax.

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

3 Массив с этими координатами сортируется, причем сначала сравниваются координаты y, а потом — х.

4 В полученном массиве первая точка соединяется со второй, …, i-я c (i + 1)-ой. Таким образом получаются горизонтальные отрезки, находящиеся внутри многоугольника, которые называются сканирующими строками.

Недостаток:

○ при большом количестве точек на сортировку уйдёт много времени.

Решение недостатка: Разделим массив точек на несколько маленьких. Можно разделить так, чтобы в каждом массиве были точки с одинаковой координатой у. Тогда не надо будет внутри них хранить у - он же у всех одинаковый. Маленькие массивы легко и быстро сортировать, + используется меньше памяти, потому что после того, как нарисованы все прямые с точками из некоторого массива, его можно удалить из памяти и создать новый — это называется “отрисовка по мере необходимости”.

2 Алгоритм со списком активных рёбер.

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

 

 



<== предыдущая лекция | следующая лекция ==>
Алгоритм Брезенхема для рисования окружностей | Немонотонная закраска


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.006 сек.