Новосибирский Государственный Технический Университет. Факультет автоматики и вычислительной техники Кафедра вычислительной техники (специальность 220100). учебное пособие
| Вид материала | Учебное пособие |
| 0.1 координаты и преобразования 0.1.1 Двумерные преобразования P = [X Y] - вектор-строка исходных координат, Pn Преобразование поворота |
- Новосибирский Государственный Технический Университет. Факультет автоматики и вычислительной, 1650.9kb.
- Рабочая программа для специальности: 220400 Программное обеспечение вычислительной, 133.96kb.
- Государственный Технический Университет. Факультет: Автоматики и Вычислительной Техники., 32.46kb.
- Образования Республики Молдова Колледж Микроэлектроники и Вычислительной Техники Кафедра, 113.64kb.
- Постоянное развитие и углубление профессиональных навыков в области информационных, 54.56kb.
- «Программное обеспечение вычислительной техники и автоматизированных систем», 1790.14kb.
- Задачи дисциплины: -изучение основ вычислительной техники; -изучение принципов построения, 37.44kb.
- Лекция №2 «История развития вычислительной техники», 78.1kb.
- Система контроля и анализа технических свойств интегральных элементов и устройств вычислительной, 582.84kb.
- Московский государственный инженерно-физический институт (технический университет), 947.05kb.
ВВЕДЕНИЕ
Данная, вторая часть курса лекций посвящена рассмотрению основных алгоритмов машинной графики.
В разделе 1 рассматриваются алгоритмы выполнения преобразований в двумерных, трехмерных и однородных координатах; параллельные, перспективные и стереопроекции; плоские преобразования растровых картин.
В разделе 2 рассматриваются три алгоритма генерации векторов - обычного и несимметричного ЦДА и Брезенхема. Там же рассмотрены способы борьбы с лестничным эффектом, вызванным различимыми размерами пикселов на экране. Один из способов основан на модификации алгоритма Брезенхема. Другой, общий способ базируется на использовании низкочастотной фильтрации. Этот способ, естественно, применим для произвольных изображений.
В разделе 3 приводится алгоритм генерации окружностей.
В разделе 4 рассмотрены различные алгоритмы заполнения многоугольника, заданного координатами его вершин. Там же рассмотрен наиболее быстрый алгоритм сортировки - алгоритм распределяющего подсчета.
В разделе 5 рассмотрены алгоритмы заливки с затравкой произвольной области, заданной либо значением граничных пикселов, либо значением пикселов внутренней части области.
Раздел 6 посвящен различным алгоритмам отсечения отрезка (Коэна-Сазерленда, Собкова-Поспишила-Янга, Лианга-Барски и Кируса-Бека) применительно к двух, трех и четырехмерным координатам.
В разделе 7 рассмотрены алгоритмы отсечения многоугольника.
В разделе 8 рассмотрены различные варианты организации данных.
В разделе 9 рассматривается геометрическое моделирование объектов и сцен.
Раздел 10 посвящен рассмотрению алгоритмов удаления скрытых линий и поверхностей.
В разделе 11 рассмотрены методы и алгоритмы реалистичного представления сцен.
В приложениях помещены процедуры на языке С, реализующие большую часть рассмотренные алгоритмы, а также тестовые программы для большинства процедур. Основной целью при написании процедур было достижение наглядности, поэтому есть возможности их оптимизации.
0.1 КООРДИНАТЫ И ПРЕОБРАЗОВАНИЯ
Описание, конструирование, манипулирование и представление геометрических объектов являются центральными работами в графических системах. Их поддержка в требуемом объеме за счет соответствующих математических методов, алгоритмов и программ оказывают существенное влияние на возможности и эффективность графической системы. В данном разделе будут рассмотрены математические методы для описания геометрических преобразований координат в двух, трех и четырехмерном случае, будут обсуждены некоторые вопросы эффективности, рассмотрены геометрические преобразования растровых картин.
Далее большими буквами X, Y, Z будут обозначаться обычные декартовые координаты, а маленькие буквы x, y, z будут использоваться для обозначения т.н. однородных координат.
0.1.1 Двумерные преобразования
Преобразование сдвига в плоском случае имеет вид:
| (0.1.1) |
или в векторной форме:
| (0.1.2) |
где ¯ Pn = [Xn Yn] ¯ - ¯ вектор-строка преобразованных координат, где X,Y - исходные координаты точки,
Tx,Ty - величина сдвига по осям,
Xn,Yn - преобразованные координаты.
P = [X Y] - вектор-строка исходных координат,
Pn = [Xn Yn] - вектор-строка преобразованных координат,
T = [Tx Ty] - вектор-строка сдвига.
Преобразование масштабирования относительно начала координат имеет вид:
| (0.1.3) |
или в матричной форме:
| (0.1.4) |
где Sx, Sy - коэффициенты масштабирования по осям, а
S = [
|
| ||
|
|
Преобразование поворота относительно начала координат имеет вид:
| (0.1.5) |
или в матричной форме:
| (0.1.6) |
где - угол поворота, а
R = [
|
| ||
|
|
Столбцы и строки матрицы поворота представляют собой взаимно ортогональные единичные векторы. В самом деле квадраты длин векторов-строк равны единице:
|
|
а скалярное произведение векторов-строк есть
|
Так как скалярное произведение векторов A ·B = A ·B ·cos, где A - длина вектора A, B - длина вектора B, а - наименьший положительный угол между ними, то из равенства 0 скалярного произведения двух векторов-строк длины 1 следует, что угол между ними равен 90.
Аналогичное можно показать и для векторов-столбцов. Кроме того вектора-столбцы представляют собой такие единичные векторы, которые после выполнения преобразования, заданного этой матрицей, совпадут с осями. В самом деле, произведение первого столбца на матрицу есть
| (0.1.7) |
т.е. это единичный вектор вдоль оси X. Аналогично, произведение второго столбца на матрицу даст вектор [ 0 1 ]. Это позволяет сформировать матрицу, если известны результаты преобразования (см. пример в п. ).