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

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

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

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

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

Знаете ли Вы, что такое мысленный эксперимент, gedanken experiment?
Это несуществующая практика, потусторонний опыт, воображение того, чего нет на самом деле. Мысленные эксперименты подобны снам наяву. Они рождают чудовищ. В отличие от физического эксперимента, который является опытной проверкой гипотез, "мысленный эксперимент" фокуснически подменяет экспериментальную проверку желаемыми, не проверенными на практике выводами, манипулируя логикообразными построениями, реально нарушающими саму логику путем использования недоказанных посылок в качестве доказанных, то есть путем подмены. Таким образом, основной задачей заявителей "мысленных экспериментов" является обман слушателя или читателя путем замены настоящего физического эксперимента его "куклой" - фиктивными рассуждениями под честное слово без самой физической проверки.
Заполнение физики воображаемыми, "мысленными экспериментами" привело к возникновению абсурдной сюрреалистической, спутанно-запутанной картины мира. Настоящий исследователь должен отличать такие "фантики" от настоящих ценностей.

Релятивисты и позитивисты утверждают, что "мысленный эксперимент" весьма полезный интрумент для проверки теорий (также возникающих в нашем уме) на непротиворечивость. В этом они обманывают людей, так как любая проверка может осуществляться только независимым от объекта проверки источником. Сам заявитель гипотезы не может быть проверкой своего же заявления, так как причина самого этого заявления есть отсутствие видимых для заявителя противоречий в заявлении.

Это мы видим на примере СТО и ОТО, превратившихся в своеобразный вид религии, управляющей наукой и общественным мнением. Никакое количество фактов, противоречащих им, не может преодолеть формулу Эйнштейна: "Если факт не соответствует теории - измените факт" (В другом варианте " - Факт не соответствует теории? - Тем хуже для факта").

Максимально, на что может претендовать "мысленный эксперимент" - это только на внутреннюю непротиворечивость гипотезы в рамках собственной, часто отнюдь не истинной логики заявителя. Соответсвие практике это не проверяет. Настоящая проверка может состояться только в действительном физическом эксперименте.

Эксперимент на то и эксперимент, что он есть не изощрение мысли, а проверка мысли. Непротиворечивая внутри себя мысль не может сама себя проверить. Это доказано Куртом Гёделем.

Понятие "мысленный эксперимент" придумано специально спекулянтами - релятивистами для шулерской подмены реальной проверки мысли на практике (эксперимента) своим "честным словом". Подробнее читайте в 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