Компьютерная геометрия и графика

  • 01 окт. 2012 г.
  • 10621 Слова
Кафедра Систем Искусственного Интеллекта










Компьютерная геометрия и графика








Методические указания для выполнения лабораторных работ
















































Лабораторная работа №1.
Исследование алгоритмов генерации отрезков
Цель: анализ различных алгоритмов генерации отрезков на прямоугольном растре.
Задача: Ознакомиться с работойалгоритма несимметричный ЦДА и алгоритма Брезенхема, реализовав их на языке программирования, и разработать на их базе программу рисования заданных плоских фигур на прямоугольном растре.
Результат: программа рисования заданных плоских фигур на прямоугольном растре. Отчет в печатном виде, оформленный в соответствии с приложением 1.


Генерация изображений отрезков на прямоугольном растре
Одним изграфических примитивов в двумерной графике является отрезок прямой линии, задаваемый координатами своих концевых точек. Отображение таких отрезков в растровой графике отнюдь не просто. Связано это с тем, что изображение отрезка на прямоугольном растре является совокупностью горизонтальных, либо вертикальных отрезков и отдельных точек рис. 1.1.
Задачей алгоритма генерации отрезков прямыхлиний является определение координат пикселей, которые необходимо подсветить для получения изображения заданного отрезка. Существует несколько алгоритмов генерации отрезков. Эти алгоритмы выбирают пиксели так, чтобы их координаты были наиболее близки к координатам точек, принадлежащих реальному отрезку. Наибольшее распространение в компьютерной графике получили инкрементные алгоритмы генерации отрезков.В этих алгоритмах, отрезок рисуется последовательно пиксель за пикселем. Координаты следующего пикселя определяются исходя из координат текущего, и некоторой дополнительной информации. Рассмотрим два инкрементных алгоритма.


[pic]
Рис. 1.1. Растровое представление отрезков прямых линий.


Алгоритм №1. Несимметричный цифровой дифференциальный анализатор (несимметричный ЦДА)
Воснову работы этого алгоритма положен тот факт, что производная функции, представляющей прямую линию на плоскости, является величиной постоянной, т.е. [pic]. Если у нас имеется отрезок прямой, заданный координатами своих концевых точек [pic]и ([pic]), то величину этой производной можно рассчитать следующим образом: [pic] .
Алгоритм «несимметричный ЦДА» использует эту величину, чтобы рассчитатьзначение смещения по одной из координат, при смещении по другой на 1. Этот алгоритм можно описать следующей последовательностью действий (подразумевается, что хотя бы одно из значений [pic]или [pic] не равно нулю).
1. Рассчитаем величину [pic] и определим, ось, вдоль которой будем продвигаться, следующим образом:
Если [pic], то наш отрезок является вертикальным, тогда [pic], продвигаться будемвдоль оси [pic].
Если [pic], то наш отрезок является горизонтальным, тогда [pic], и продвигаться будем вдоль оси [pic].
Если [pic], тогда, [pic]продвигаться будем вдоль оси [pic].
В противном случае, [pic], и продвигаться будем вдоль оси [pic].
2. Подсветим пиксель с координатами [pic].[pic]
3. Увеличим координату, соответствующую оси, вдоль которойпродвигаемся, на 1 (-1), а другую на [pic], и подсветим пиксель, соответствующий этим координатам.
4. Повторять пункт 3, до тех пор, пока не нарисуем весь отрезок.
Рассмотрим работу алгоритма на следующих примерах рис. 1.2.
[pic]
Рис. 1.2. Генерация отрезков несимметричным ЦДА.
Отрезок а): [pic]
1. Поскольку [pic], то [pic], продвигаться будем
вдоль оси y.
2. Подсветим пиксель скоординатами (3, 1).
3. Увеличим [pic]на 1, а [pic]на [pic]. Получим [pic]. Подсветим пиксель с координатами (3 ([pic]), 2).
4. Далее повторяем пункт 3, пока не нарисуем весь отрезок.
На следующем шаге получим [pic]. Подсветим пиксель (3, 2). Далее получим [pic]. Подсветим пиксель (4, 2) и т.д.
Отрезок б): [pic]
1. Поскольку...