- •Введение
- •1. Машинная графика и обработка изображения с помощью эвм
- •2. Типы графических устройств
- •2.1. Графические дисплеи на запоминающей трубке
- •2.2. Векторные графические дисплеи с регенерацией изображения
- •2.3. Растровые графические дисплеи с регенерацией изображения
- •2.4. Диалоговые устройства
- •3. Основы растровой графики
- •3.1. Алгоритмы вычерчивания отрезков
- •3.2. Цифровой дифференциальный анализатор
- •3.3. Алгоритм Брезенхема
- •3.4. Целочисленный алгоритм Брезенхема
- •3.5. Общий алгоритм Брезенхема
- •3.6. Алгоритм Брезенхема для генерации окружности
- •4. Растровая развертка изображения
- •4.1. Растровая развертка в реальном времени
- •4.2. Групповое кодирование
- •4.3. Клеточное кодирование
- •4.4. Буферы кадра
- •4.5. Изображение отрезков
- •4.6. Изображение литер
- •4.7. Растровая развертка сплошных областей и заполнение многоугольников
- •1 X 8 – внутри многоугольника;
- •1 Х 4 – внутри многоугольника;
- •6 Х 8 – внутри многоугольника;
- •4.8. Простой алгоритм с упорядоченным списком ребер
- •4.9. Алгоритм заполнения по ребрам
- •4.10. Алгоритм со списком ребер и флагом
- •4.11. Алгоритм заполнения с затравкой
- •4.12. Построчный алгоритм заполнения с затравкой
- •4.13. Основные методы устранения ступенчатости
- •4.14. Аппроксимация полутонами
- •5. Отсечение
- •5.1. Двумерное отсечение
- •5.2. Алгоритм отсечения Сазерленда-Коэна
- •5.3. Алгоритм разбиения средней точкой
- •5.4. Обобщение: отсечение двумерного отрезка выпуклым окном
- •5.5. Алгоритм Кируса–Бека
- •5.6. Внутреннее и внешнее отсечение
- •5.7. Определение факта выпуклости многоугольника
- •5.8. Разбиение невыпуклых многоугольников
- •5.9. Трехмерное отсечение
- •5.10. Определение выпуклости трехмерного тела
- •5.11. Отсечение невыпуклых тел
- •5.12. Отсечение многоугольников
- •5.13. Последовательное отсечение многоугольника – алгоритм Сазерленда – Ходжмена
- •5.14. Невыпуклые отсекающие области – алгоритм
- •5.15. Литеры
- •6. Удаление невидимых линий и поверхностей
- •6.1. Алгоритм плавающего горизонта
- •6.2. Алгоритм Робертса
- •6.3. Алгоритм Варнока
- •6.4. Алгоритм Вейлера–Азертона
- •6.5. Алгоритм, использующий z-буфер
- •6.6. Алгоритмы, использующие список приоритетов
- •6.7. Алгоритм построчного сканирования
- •6.8. Алгоритм построчного сканирования, использующий
- •Библиографический список рекомендуемой литературы
- •Оглавление
- •1. Машинная графика и обработка изображения с помощью эвм….……..3
5.12. Отсечение многоугольников
Предыдущие алгоритмы были связаны с отсечением отрезков. Разумеется, многоугольник можно рассматривать как набор отрезков (рис.16).
Е сли замкнутый многоугольник отсекается, как набор отрезков, то исходная фигура может превратиться в один или более открытых многоугольников или просто стать совокупностью разрозненных отрезков. Однако если многоугольники рассматривается как сплошные области, то необходимо, чтобы замкнутость сохранялась и у результата. Для нашего случая это означает, что отрезки bc, ef, fg, и ha должны быть добавлены к описанию результирующего многоугольника. Добавление отрезков ef и fg представляет особые трудности.
5.13. Последовательное отсечение многоугольника – алгоритм Сазерленда – Ходжмена
Основная идея алгоритма Сазерленда – Ходжмена состоит в том, что отсечь многоугольник относительно одной прямой или плоскости очень легко. В этом алгоритме исходный и каждый из промежуточных многоугольников отсекается последовательно относительно одной прямой. Порядок отсечения многоугольника разными сторонами окна непринципиален.
Результатом работы алгоритма является список вершин многоугольника, у которого все вершины лежат по видимую сторону от очередной отсекающей плоскости. Поскольку каждая сторона многоугольника отсекается независимо от других, то достаточно рассмотреть только возможные ситуации расположения одного отрезка относительно одной отсекающей плоскости. Будем рассматривать каждую точку P из списка вершин многоугольника, за исключением первой, как конечную точку ребра, начальной точкой S которого является вершина, предшествующая P в этом списке. Тогда возможны только четыре ситуации взаимного расположения ребра и отсекающей плоскости (ОП) (рис.17).
Р езультатом каждого сопоставления ребра многоугольника с отсекающей плоскостью будет занесение в список вершин результирующего усеченного многоугольника нуля, одной или двух вершин. Если рассматриваемое ребро полностью видимо, то результатом будет вершина P. Заносить в результат начальную вершину S в этом случае не надо, так как если вершины рассматриваются поочередно, то S уже была конечной точкой предыдущего ребра и поэтому уже попала в результат (рис.17,а). Если же ребро полностью невидимо, то результат не изменяется (рис.17,б).
Если ребро многоугольника видимо неполностью, то оно может или входить или выходить из области видимости отсекающей плоскости. Если ребро выходит из области видимости, то надо определить и занести в результат точку пересечения ребра и отсекающей плоскости (рис.17,в). Если же ребро входит в область видимости (рис.17,г), то следует поступить точно так же. Поскольку в последнем случае конечная вершина P ребра видима, то она также должна попасть в результат.
Для первой вершины многоугольника необходимо определить только факт её видимости. Если вершина видима, то она попадает в результат и становится начальной точкой S. Если же вершина невидима, она тоже становится начальной точкой, но в результат не попадает.
Определение видимости точки эквивалентно определению той стороны границы отсекающей плоскости, по которую лежит эта точка. Можно воспользоваться ранее рассмотренным алгоритмом, который сводится к определению знака скалярного произведения вектора нормали на вектор, начинающийся в произвольной точке на прямой или плоскости и заканчивающийся в пробной точке. Ребро многоугольника будет полностью видимым, если оба его конца видимы, и полностью невидимым, если оба они не видны. Если же один конец ребра видим, а другой невидим, то ребро пересекается с отсекающей плоскостью и нужно вычислять точку пересечения. Для этого можно использовать любые изложенные выше алгоритмы отсечения отрезка, например, Кируса – Бека или разбиение средней точкой.
Сазерленд и Ходжмен показали, как можно избежать порождения и запоминания вершин промежуточных многоугольников. Для этого вместо отсечения каждого ребра (вершины) многоугольника одной плоскостью, ограничивающей окно, надо отсекать каждое такое ребро (вершину) последовательно всеми границами окна. После отсечения очередного ребра (вершины) многоугольника по одной из границ окна, алгоритм рекурсивно обращается к самому себе, чтобы отсечь результат предыдущего обращения по следующей границе окна. Это свойство делает данный алгоритм более удобным для аппаратной реализации. Этот алгоритм можно использовать и для отсечения по выпуклому объёму путём вычисления его пересечений с трёхмерными отсекающими плоскостями при помощи алгоритма Кируса – Бека.