БПФ   к оглавлению   ДМ   ТПОИ   Теория сигналов  

Основные алгоритмы компьютерной графики

(по П.В.Вельтмандеру, НГТУ)

Теория алгоритмов

  1. Координаты и преобразования
  2. Генерация векторов
  3. Генерация окружности
  4. Заполнение многоугольника
  5. Заливка области с затравкой
  6. Отсечение отрезков
  7. Отсечение многоугольника
  8. Структуры данных
  9. Геометрическое моделирование
  10. Удаление скрытых линий и поверхностей
  11. Реалистическое представление сцен

Практика программирования

  1. Процедуры генерации отрезков
  2. Процедуры фильтрации
  3. Процедуры генерации окружности
  4. Процедуры заполнения многоугольника
  5. Процедуры заливки области
  6. Процедуры отсечения отрезка
  7. Процедуры отсечения многоугольника

Дополнительные материалы

  1. Быстрое преобразование Фурье
  2. Преобразование Хартли
  3. Теорема Котельникова
  4. Сплайн-интерполяция
  5. Введение во фракталы
  6. Цифровая фильтрация

Данная, вторая часть курса лекций посвящена рассмотрению основных алгоритмов машинной графики.
В разделе 1 рассматриваются алгоритмы выполнения преобразований в двумерных, трехмерных и однородных координатах; параллельные, перспективные и стереопроекции; плоские преобразования растровых картин.
В разделе 2 рассматриваются три алгоритма генерации векторов - обычного и несимметричного ЦДА и Брезенхема. Там же рассмотрены способы борьбы с лестничным эффектом, вызванным различимыми размерами пикселов на экране. Один из способов основан на модификации алгоритма Брезенхема. Другой, общий способ базируется на использовании низкочастотной фильтрации. Этот способ, естественно, применим для произвольных изображений.
В разделе 3 приводится алгоритм генерации окружностей.
В разделе 4 рассмотрены различные алгоритмы заполнения многоугольника, заданного координатами его вершин. Там же рассмотрен наиболее быстрый алгоритм сортировки - алгоритм распределяющего подсчета.
В разделе 5 рассмотрены алгоритмы заливки с затравкой произвольной области, заданной либо значением граничных пикселов, либо значением пикселов внутренней части области.
Раздел 6 посвящен различным алгоритмам отсечения отрезка (Коэна-Сазерленда, Собкова-Поспишила-Янга, Лианга-Барски и Кируса-Бека) применительно к двух, трех и четырехмерным координатам.
В разделе 7 рассмотрены алгоритмы отсечения многоугольника.
В разделе 8 рассмотрены различные варианты организации данных.
В разделе 9 рассматривается геометрическое моделирование объектов и сцен.
Раздел 10 посвящен рассмотрению алгоритмов удаления скрытых линий и поверхностей.
В разделе 11 рассмотрены методы и алгоритмы реалистичного представления сцен.
В приложениях помещены процедуры на языке С, реализующие большую часть рассмотренные алгоритмы, а также тестовые программы для большинства процедур. Основной целью при написании процедур было достижение наглядности, поэтому есть возможности их оптимизации.

СПИСОК ЛИТЕРАТУРЫ

  1. Encarnacao J. Einfurung in die Graphische Datenverarbeiterung // Eurographics '89. Tutorial Notes 1. Hamburg, FRG, September 4-8, 1989. 122 s.
  2. Ньюмен У., Спрулл Р. Основы интерактивной машинной графики. Пер. с англ. М.: Мир, 1976.
  3. Роджерс Д. Алгоритмические основы машинной графики. Пер. с англ. М.: Мир, 1989. 512 c.
  4. Фоли Дж., вэн Дэм А. Основы интерактивной машинной графики: В 2-х книгах. Пер. с англ. М.: Мир, 1985.
  5. Антонофф М., Линдерхолм О. Лазерные принтеры // Компьютер Пресс, сборник N 1, 1989, с. 3-8.
  6. Введение в Автокад 11R: Метод.пособие/ НГТУ; Составители: Р.М.Сидорук, О.А.Соснина, И.М.Моисеенко. Н.Новгород, 1993. 181 с.
  7. Кречко Ю.А., Полищук В.В. Автокад. Курс практической работы. М.: "Диалог-МИФИ", 1994. 256 с.
  8. Вельтмандер П.В., Голубев В.М. Обучение автоматизации проектирования машиностроительного направления// Информатизация образования: Межвуз. сб. науч. тр. / под ред. В.Н.Врагова. Новосибирск: НГУ, 1994. С. 123-131.
  9. Винцюк Т.К. Системы речевого диалога// Материалы пятой школы-семинара "Интерактивные системы" (Кутаиси, 2-10 апреля 1983 г.). Тбилиси: Мецниереба, 1983, с. 16-22.
  10. Печатающие устройства персональных ЭВМ: Справочник // Под редакцией проф. И.М.Витенберга. М.: Радио и связь, 1992.
  11. Гилой В. Интерактивная машинная графика. Пер. с англ. М.: Мир, 1981.
  12. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. Пер. с англ. М.: Мир, 1975. 544 с.
  13. Лисицин Б.Л. Низковольтные индикаторы: Справочник. М.: Радио и связь, 1985.
  14. Справочник по машинной графике в проектировании / В.Е.Михайленко, В.А.Анпилогова, Л.А.Кириевский и др.: Под ред. В.Е.Михайленко. А.А.Лященко. Киев: Будiвельник, 1984. 184 с.
  15. Мячев А.А., Степанов В.Н. Персональные ЭВМ и микроЭВМ. Основы организации: Справочник/ Под ред. А.А.Мячева. М.: Радио и связь, 1991.
  16. Новаковский С.В. Цвет в цветном телевидении. М.: Радио и связь, 1988. 288 с.
  17. Павлидис Т. Алгоритмы машинной графики и обработки изображений. Пер. с англ. М.: Радио и связь, 1986.
  18. Прэтт У. Цифровая обработка изображений: Пер. с англ. в 2-х книгах. М.: Мир, 1982.
  19. Роджерс Д., Адамс Дж. Математические основы машинной графики. Пер. с англ. М.: Машиностроение, 1980.
  20. Сизых В.Г. Растровые дисплеи ряда Гамма. Новосибирск, 1985. 26 с. (Препринт ВЦ СО АН СССР; N 607).
  21. Ткаченко А.П. Цветное телевидение. Минск: Беларусь, 1981. 253 с.
  22. Фролов А.В., Фролов Г.В. Программирование видеоадаптеров CGA, EGA, VGA. M.: Диалог-МИФИ, 1992.
  23. Фостер Дж. Обработка списков. Пер. с англ. М.: Мир, 1974. 71 с.
  24. Холл П. Вычислительные структуры. Ведение в нечисленное программирование. Пер. с англ. М.: Мир, 1978. 214 с.
  25. Bresenham J.E. Algorithm for computer control of a digital plotter// IBM Systems Journal, vol. 4, No. 1, pp. 25-30, 1965.
  26. Bresenham J., A Linear Algoritm for Incremental Didgital Display of Circular Arcs, CACM, vol. 20, pp. 100-106, 1977.
  27. Bui-Tuong Phong. Illumination for Computer-Generated Pictures. Communication of the ASM, 18(6), June 1975, pp. 311-317.
  28. Clark, J.H. A VLSI geometry Processor for Graphics// IEEE Computer, 12(7).
  29. Cyrus M., Beck J. Generalized two- and threedimensional clipping// Computer and Graphics, Vol. 3, pp. 23-28, 1978.
  30. Hans Joseph, Max Mehl. Computer Graphics Hardware: Introduction and State of the Art// Eurographics '91. Tutorial Note 9. Viena, 2.-6. September 1991. Austria, Viena. 29 p.
  31. Fontenier Guy, Pascal Gros Pascal. Architectures of Graphic Processors for Interactive 2D Graphics// Computer Graphics Forum 7 (1988) 78-89.
  32. You-Dong Liang and Brian A. Barsky. A new concept and method for line clipping// ACM Transaction on Graphics, Vol. 3, No. 1, January 1984, pp. 1-22.
  33. Tina M. Nicholl, D.T.Lee and Robin A. Nicholl. An efficient new algoritm for 2-D line clipping: its development and analysis// Computer Graphics, V. 21, N. 4, July 1987, pp. 253-262.
  34. R.Pinkman, M.Novak, K.Guttag. Video-RAM exels at fast graphics// Electronics Design, pp. 161-171 (August 18 1983).
  35. H.-P. Seidel. PC Graphics Hardware // Eurographics '88. Tutorial/Cours 8. Nice, 12.-16. September 1988. France, Nice. 44 p.
  36. Smit A.R., Tint Fill, SIGGRAPH'79 Proceedings // Computer Graphics, Vol.13(2), Aug. 1979, pp. 276-283.
  37. Mark S. Sobkow, Paul Pospisil and Yee-Hong Yang. A Fast Two-Dimensional Line Clipping Algoritm via Line Encoding//Computer & Graphics, Vol. 11, No. 4, pp. 459-467, 1987.
  38. Robert F. Sproull and Ivan E. Sutherland. A Clipping Divider // AFIP Fall Joint Computer Conference. San Francisco, 1968.
  39. Stralunsfreier Flacbildschirm. MC, Die MikrocomputerZeitschrift. N 8, 1989, s. 66.
  40. Sutherland I.E., Hodgman G.W. Reentrant Polygon Clipping//Communications of the ACM, 17(1), pp. 32-42.
  41. Weiler K., Atherton P,. Hidden Surface Removal Using Polygon Area Sorting// SIGGGRAPH'77 Proceedings, Computer Graphics, Vol. 11, N. 2, pp. 214-222, 1977.
  42. Weiler K., Polygon Comparision Using a Graph Representation// SIGGGRAPH'80 Proceedings, Computer Graphics, Vol. 14, pp. 10-18, 1980.
БПФ   к оглавлению   ДМ   ТПОИ   Теория сигналов  

Знаете ли Вы, что релятивизм (СТО и ОТО) не является истинной наукой? - Истинная наука обязательно опирается на причинность и законы природы, данные нам в физических явлениях (фактах). В отличие от этого СТО и ОТО построены на аксиоматических постулатах, то есть принципиально недоказуемых догматах, в которые обязаны верить последователи этих учений. То есть релятивизм есть форма религии, культа, раздуваемого политической машиной мифического авторитета Эйнштейна и верных его последователей, возводимых в ранг святых от релятивистской физики. Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМА

Форум Рыцари теории эфира

Рыцари теории эфира
 10.11.2021 - 12:37: ПЕРСОНАЛИИ - Personalias -> WHO IS WHO - КТО ЕСТЬ КТО - Карим_Хайдаров.
10.11.2021 - 12:36: СОВЕСТЬ - Conscience -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров.
10.11.2021 - 12:36: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от д.м.н. Александра Алексеевича Редько - Карим_Хайдаров.
10.11.2021 - 12:35: ЭКОЛОГИЯ - Ecology -> Биологическая безопасность населения - Карим_Хайдаров.
10.11.2021 - 12:34: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> Проблема государственного терроризма - Карим_Хайдаров.
10.11.2021 - 12:34: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ПРАВОСУДИЯ.НЕТ - Карим_Хайдаров.
10.11.2021 - 12:34: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вадима Глогера, США - Карим_Хайдаров.
10.11.2021 - 09:18: НОВЫЕ ТЕХНОЛОГИИ - New Technologies -> Волновая генетика Петра Гаряева, 5G-контроль и управление - Карим_Хайдаров.
10.11.2021 - 09:18: ЭКОЛОГИЯ - Ecology -> ЭКОЛОГИЯ ДЛЯ ВСЕХ - Карим_Хайдаров.
10.11.2021 - 09:16: ЭКОЛОГИЯ - Ecology -> ПРОБЛЕМЫ МЕДИЦИНЫ - Карим_Хайдаров.
10.11.2021 - 09:15: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Екатерины Коваленко - Карим_Хайдаров.
10.11.2021 - 09:13: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вильгельма Варкентина - Карим_Хайдаров.
Bourabai Research - Технологии XXI века Bourabai Research Institution