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

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

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

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

  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.
БПФ   к оглавлению   ДМ   ТПОИ   Теория сигналов  

Знаете ли Вы, почему "черные дыры" - фикция?
Согласно релятивистской мифологии, "чёрная дыра - это область в пространстве-времени, гравитационное притяжение которой настолько велико, что покинуть её не могут даже объекты, движущиеся со скоростью света (в том числе и кванты самого света). Граница этой области называется горизонтом событий, а её характерный размер - гравитационным радиусом. В простейшем случае сферически симметричной чёрной дыры он равен радиусу Шварцшильда".
На самом деле миф о черных дырах есть порождение мифа о фотоне - пушечном ядре. Этот миф родился еще в античные времена. Математическое развитие он получил в трудах Исаака Ньютона в виде корпускулярной теории света. Корпускуле света приписывалась масса. Из этого следовало, что при высоких ускорениях свободного падения возможен поворот траектории луча света вспять, по параболе, как это происходит с пушечным ядром в гравитационном поле Земли.
Отсюда родились сказки о "радиусе Шварцшильда", "черных дырах Хокинга" и прочих безудержных фантазиях пропагандистов релятивизма.
Впрочем, эти сказки несколько древнее. В 1795 году математик Пьер Симон Лаплас писал:
"Если бы диаметр светящейся звезды с той же плотностью, что и Земля, в 250 раз превосходил бы диаметр Солнца, то вследствие притяжения звезды ни один из испущенных ею лучей не смог бы дойти до нас; следовательно, не исключено, что самые большие из светящихся тел по этой причине являются невидимыми." [цитата по Брагинский В.Б., Полнарёв А. Г. Удивительная гравитация. - М., Наука, 1985]
Однако, как выяснилось в 20-м веке, фотон не обладает массой и не может взаимодействовать с гравитационным полем как весомое вещество. Фотон - это квантованная электромагнитная волна, то есть даже не объект, а процесс. А процессы не могут иметь веса, так как они не являются вещественными объектами. Это всего-лишь движение некоторой среды. (сравните с аналогами: движение воды, движение воздуха, колебания почвы). Подробнее читайте в FAQ по эфирной физике.

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

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


Рыцари теории эфира
 01.03.2021 - 06:31: ПЕРСОНАЛИИ - Personalias -> WHO IS WHO - КТО ЕСТЬ КТО - Карим_Хайдаров.
28.02.2021 - 21:33: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Андрея Фурсова - Карим_Хайдаров.
28.02.2021 - 18:56: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ЗА НАМИ БЛЮДЯТ - Карим_Хайдаров.
28.02.2021 - 18:55: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Пламена Паскова - Карим_Хайдаров.
28.02.2021 - 18:55: ТЕОРЕТИЗИРОВАНИЕ И МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ - Theorizing and Mathematical Design -> ФУТУРОЛОГИЯ - прогнозы на будущее - Карим_Хайдаров.
28.02.2021 - 18:54: СОВЕСТЬ - Conscience -> РУССКИЙ МИР - Карим_Хайдаров.
28.02.2021 - 18:54: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> Проблема государственного терроризма - Карим_Хайдаров.
27.02.2021 - 19:35: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Амары Ельской - Карим_Хайдаров.
27.02.2021 - 18:43: ЭКОНОМИКА И ФИНАНСЫ - Economy and Finances -> КОЛЛАПС МИРОВОЙ ФИНАНСОВОЙ СИСТЕМЫ - Карим_Хайдаров.
27.02.2021 - 18:42: ЭКОЛОГИЯ - Ecology -> ЭКОЛОГИЯ ДЛЯ ВСЕХ - Карим_Хайдаров.
27.02.2021 - 18:42: СОВЕСТЬ - Conscience -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров.
27.02.2021 - 18:41: ЭКОНОМИКА И ФИНАНСЫ - Economy and Finances -> ПРОБЛЕМА КРИМИНАЛИЗАЦИИ ЭКОНОМИКИ - Карим_Хайдаров.
Bourabai Research - Технологии XXI века Bourabai Research Institution