- •153000 Г. Иваново, пр. Ф.Энгельса, 21
- •Лекция №1 Предмет и область применения компьютерной графики
- •1. Отображение информации
- •2. Проектирование
- •3. Моделирование
- •4. Графический пользовательский интерфейс
- •Краткая история
- •Технические средства поддержки компьютерной графики
- •Вопросы и упражнения
- •Лекция №2 о природе света и цвета
- •Цветовой график мко
- •Цветовые модели rgb и cmy
- •Цветовые модели hsv и hls
- •Пространство cie Luv
- •Вопросы и упражнения
- •Лекция №3 Геометрические преобразования Системы координат и векторы
- •Уравнения прямой и плоскости
- •Аналитическое представление кривых и поверхностей
- •Пересечение луча с плоскостью и сферой
- •Лекция №3 (продолжение) Интерполяция функций одной и двух переменных
- •Матрицы
- •Геометрические преобразования (перенос, масштабирование, вращение)
- •Переход в другую систему координат
- •Задача вращения относительно произвольной оси
- •Вопросы и упражнения
- •Лекция №4 Введение в растеризацию кривых
- •Изображение отрезка с целочисленными координатами концов
- •Цифровой дифференциальный анализатор
- •Алгоритм Брезенхема
- •Алгоритм Кастла-Питвея
- •Изображение отрезка с нецелочисленными координатами концов
- •Изображение окружностей
- •Алгоритм Брезенхема
- •Изображение эллипсов
- •Построение по неявной функции
- •Построение путем сжатия окружности
- •Лекция №5 Представление геометрической информации Геометрические примитивы
- •Полигональные модели
- •Воксельные модели
- •Поверхности свободных форм (функциональные модели)
- •Системы координат: мировая, объектная, наблюдателя и экранная
- •Однородные координаты. Задание геометрических преобразований в однородных координатах с помощью матриц
- •Вопросы и упражнения
- •Лекция №6 Отсечение (клиппирование) геометрических примитивов
- •Алгоритм Сазерленда-Коэна отсечения прямоугольной областью
- •Отсечение выпуклым многоугольником
- •Клиппирование многоугольников
- •Вопросы и упражнения
- •Лекция №7 Удаление невидимых поверхностей и линий
- •Удаление нелицевых граней многогранника Алгоритм Робертса
- •Алгоритм Варнока
- •Алгоритм Вейлера-Азертона
- •Метод z-буфера
- •Методы приоритетов (художника, плавающего горизонта)
- •Алгоритмы построчного сканирования для криволинейных поверхностей
- •Метод двоичного разбиения пространства
- •Метод трассировки лучей
- •Вопросы и упражнения
- •Лекция №8 Проецирование пространственных сцен Основные типы проекций
- •Параллельные проекции
- •Центральные проекции
- •Математический аппарат
- •Ортогональные проекции
- •Косоугольные проекции
- •Центральные проекции
- •Специальные картографические проекции. Экзотические проекции земной сферы
- •Стереографическая проекция
- •Гномоническая проекция
- •Ортографическая проекция
- •Проекции на цилиндр
- •Проекция Меркатора
- •Проекции на многогранник
- •Необычные проекции
- •Вопросы и упражнения
- •Лекция 9 Растровое преобразование графических примитивов
- •Алгоритм Брезенхема растровой дискретизации отрезка
- •Алгоритмы Брезенхема растровой дискретизации окружности и эллипса
- •Алгоритмы заполнения областей
- •Вопросы и упражнения
- •Лекция 10 Закрашивание. Рендеринг полигональных моделей
- •Простая модель освещения
- •Закраска граней Плоское закрашивание
- •Закраска методом Гуро
- •Закраска методом Фонга
- •Более сложные модели освещения
- •Устранение ступенчатости (антиэлайзинг)
- •Вопросы и упражнения
- •Лекция 11 Визуализация пространственных реалистических сцен Свето-теневой анализ
- •Метод излучательности
- •Глобальная модель освещения с трассировкой лучей
- •Текстуры
- •Вопросы и упражнения
- •Учебники к курсу
- •Список литературы
Алгоритмы построчного сканирования для криволинейных поверхностей
Идея построчного сканирования, предложенная в 1967 г. Уайли, Ромни, Эвансом и Эрдалом, заключалась в том, что сцена обрабатывается в порядке прохождения сканирующей прямой. В объектном пространстве это соответствует проведению секущей плоскости, перпендикулярной пространству изображения. Строго говоря, алгоритм работает именно в пространстве изображения, отыскивая точки пересечения сканирующей прямой с ребрами многоугольников, составляющих картину (для случая изображения многогранников). Но при пересечении очередного элемента рисунка выполняется анализ глубины полученной точки и сравнение ее с глубиной других точек на сканирующей плоскости. В некоторых случаях можно построить список ребер, упорядоченный по глубине, но зачастую это невозможно выполнить корректно. Поэтому сканирование сочетают с другими методами.
Один из таких методов мы уже рассматривали - метод Z–буфера, в котором буфер инициализируется заново для каждой сканирующей строки. Другой метод называют интервальным алгоритмом построчного сканирования. В нем сканирующая строка разбивается проекциями точек пересечения ребер многоугольников на интервалы, затем в каждом из интервалов выбираются видимые отрезки. В этой ситуации их уже можно отсортировать по глубине. Мы остановимся чуть подробнее на методе построчного сканирования для криволинейных поверхностей.
В описании метода приоритетов поверхность задавалась в виде функции двух переменных, здесь мы будем задавать поверхность параметрическими уравнениями:
Пересечение сканирующей плоскости с поверхностью дает нам так называемую линию уровня, или изолинию. Эта кривая может быть неодносвязной, т. е. состоять из нескольких отдельных кривых. Чтобы получить эту кривую, мы должны решить уравнение
и, определив значения параметров , найти точки кривой. Для получения решения можно воспользоваться численными итерационными методами, но это вносит дополнительные проблемы (например, при плохом выборе начального приближения итерационный процесс может не сойтись). Выбор подходящего метода решения лежит вне задач нашего курса, поэтому перейдем к описанию алгоритма, считая, что он уже выбран и надежно работает.
Второй шаг этого алгоритма предполагает, что решение отыскивается только для тех элементов поверхности (или группы поверхностей, если речь идет о более сложной сцене, содержащей составные объекты), которые при данном значении ординаты пересекают сканирующую плоскость. Предварительный анализ в некоторых случаях позволяет оптимизировать алгоритм.
Метод двоичного разбиения пространства
Теперь разберем один способ использования метода художника при изображении пространственных сцен, содержащих несколько объектов или составные объекты. Это так называемый метод двоичного разбиения пространства плоскостями. Плоскости, как обычно, будут задаваться с помощью вектора нормали и расстояния до начала координат (с точностью до знака). Пусть изображаемая сцена состоит из набора непересекающихся граней (они могут иметь общие прямолинейные участки границы). Проведем плоскость , разбивающую все пространство на два полупространства, в одном из которых находится наблюдатель. Предположим, что плоскость при этом не пересекает ни одну из граней (но может содержать участок ее границы). Тогда грани, находящиеся в одном полупространстве с наблюдателем, могут заслонять от него часть граней из второго полупространства, но не наоборот. Это означает, что они должны изображаться позже. Разобьем плоскостью второе полупространство и снова определим, какая группа граней из него должна изображаться раньше. Продолжая этот процесс до того уровня, когда все пространство будет разбито плоскостями на секции, в каждой из которых будет находиться только одна грань, мы получим упорядоченный набор граней. Этот порядок можно изобразить в виде двоичного дерева. В контексте рассматриваемого алгоритма это дерево представляет собой структуру данных , элементами которой являются указатель на грань изображаемой сцены, плоскость, отделяющая эту грань, указатели на левое и правое поддерево и . Такой элемент называется узлом дерева.
В каждом узле дерева левое поддерево будет содержать грани, отделенные плоскостью, а правое - не отделенные. Рисование сцены осуществляется с помощью рекурсивного алгоритма следующего вида:
Рис. 7.6. Разбиение пространства и соответствующее ему дерево
Построение плоскостей и дерева в данном случае осуществляется "вручную". Для эффективности работы алгоритма надо стремиться к тому, чтобы дерево было сбалансированным. Если какие-то грани не удается отделить, то их пересекают плоскостями и рисуют как два объекта. Способ определения, по какую сторону плоскости находится наблюдатель, а по какую - грань, очень прост. Параметр плоскости для каждой грани будем задавать так, чтобы грань находилась в положительной полуплоскости. Тогда если при подстановке координат наблюдателя в это уравнение получаем положительное значение, то он находится в одной полуплоскости с гранью, если нет, то в разных.
Алгоритм может применяться не только к многогранникам, но и вообще к любой сцене при условии, что имеется алгоритм изображения составляющих ее объектов. На рис. 7.6 изображена проекция сцены, разбитой вертикальными плоскостями, и соответствующее ей дерево. Положение наблюдателя отмечено кружком с буквой Н. При этой точке зрения объекты будут изображаться в последовательности 5, 6, 1, 2, 3, 4.