русс | укр

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

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

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

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


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

Алгоритм Сазерленда-Коэна


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


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

Задача растеризации

● Вход: надпись, шрифт, кодировка, координаты

● Выход: растр

Причины, по которым задача отрисовки важна:

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

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

 

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

 

Параметры отсечения:

● Отсекаемая фигура (примитив, который рисуем)

● Отсекающая фигура (примитив, который задаёт видимую часть; окно видимости)

● Вид отсечения:

Внешнее — оставляем всё, что вне отсекающей фигуры.

 

Внутреннее — оставляем всё, что внутри отсекающей фигуры.

 

 

  Это алгоритм внутреннего отсечения отрезка прямоугольным окном. Продлевая границы окна видимости, получаем девять частей, каждая из которых кодируется четырёхбитным кодом: ● Бит #1 = (область строго левее отсекающего окна) ● Бит #2 = (область строго правее отсекающего окна) ● Бит #3 = (область строго выше отсекающего окна) ● Бит #4 = (область строго ниже отсекающего окна)

 



Пусть A и B — коды, соответствующие концам отрезка. Тогда:

 

Условие Пояснение Вывод
(A OR B) = 0 Коды содержат только нули, то есть оба кода — 0000. Отрезок полностью виден
(A AND B) ≠ 0 Коды содержат единичный бит в одной и той же позиции. Отрезок полностью не виден
(A AND B) = 0 В каждом разряде одного из кодов есть ноль. Отрезок частично видим. Переносим точку, у которой код ≠ 0, в место пересечения отрезка с одной из границ (например, если включен 1й бит, то с левой, если 2й, то с правой и т.д.) и повторяем алгоритм.

 

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

 

Недостатки:

● При вычислении точки пересечения отрезка и прямой используется медленная вещественная арифметика

● В некоторых случаях для получения ответа требуется несколько итераций



<== предыдущая лекция | следующая лекция ==>
Растеризация текста. Шрифты | Алгоритм Лианга-Барски


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


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

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

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


 


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

 
 

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

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