Алгоритмы вычерчивания отрезков.

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

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

Алгоритм Брезенхема для генерации окружностей. Вначале необходимо сгенерировать только одну восьмую часть окружности. Остальные ее части могут быть получены последовательными отражениями. Если сгенерирован первый октант (от 0° до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = О для завершения построения.

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

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

Растровая развертка многоугольников. Можно разработать эффективный метод растровой развертки многоугольников, если воспользоваться тем фактом, что соседние пиксели, вероятно, имеют одинаковые характеристики (кроме пикселей граничных ребер). Это свойство называется пространственной когерентностью.

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

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

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

Более подробно математическая реализация вопросов визуализации графических объектов приведена в [7].

Вопросы для самопроверки.

1. Что такое САПР?

2. Назовите подходы к конструированию.

3. Что понимают под геометрическим моделированием?

4. Перечислите основные средства трехмерной графики.

5. Что такое рабочее трехмерное пространство?

6. Какие существуют алгоритмы вычерчивания отрезков?

7. Назовите основные графические редакторы трехмерной графики.

8. Что такое параметрическое черчение?

9. Чем отличается параметрическое черчение от традиционного черчения?

10. Назовите логические операции, применяемые в трехмерной графике.

11. Какие типы пространственных моделей применяются в трехмерной графике?