Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Задачи и ссылки на полезные материалы

Версия задач от 02.09.05 (возможно изменение задачи №5)

ДопМатериалы по курсу можно найти локально студгородке Долгопрудного на \\194.85.83.110\!Public\Study\!!Institute\CG, а также в студгородке Зюзино.

Некоторые задачи по курсу "Базовые алгоритмы машинной графики"

 

1.1        Аппроксимация полутонов.

Вход: растровый файл в любом удобном формате.

Наиболее простым для чтения и записи, a также для наших целей являются файлы в формате pgm (portable gray map ).

Выход: растровый файл в любом удобном формате но с меньшим цветовым разрешением.

Для данного эксперимента можно ограничится двухцветным выходным файлом. Чтобы не мучится можно использовать тот же (входной) формат, но пикселы должно быть только двух цветов (черного и белого).

Алгоритмы: Интересно сравнить результаты работы 4 алгоритмов

·         Округление до ближайшего (Round to nearest or fixed threshold dithering).

·         Случайное возбуждение (Random threshold dithering).

·         Упорядоченное возбуждение (ordered dithering)

·         Диффузия ошибки (error diffusion by Floyd Steinberg algorithm)

 

Другие интересные алгоритмы

·         диффузия ошибки только в следующий по строке пиксел.

·         другие разновидноности диффузии ошибки (с другими весами, с чередованием направлений, вдоль кривой

·         dot diffusion

 

Литература

1.  Роджерс Д., Алгоритмические основы машинной графики.
М.: Мир, 1989, 512 с.

2.  Хилл Ф., Open GL. Программирование компьютерной графики. Для профессионалов. — СПб.: Питер, 2002. — 1088 с. ISBN 5-318-00219-6

3.  Foley J. D., A. van Dam, Feiner S. K., Hughes J. H., Computer graphics: principles and practice. 2nd ed. in C. Addison-Wesley, 1996, 1175 p., ISBN 0-201-84840-6

4.  http://www.cg.tuwien.ac.at/courses/CG2/SS2002/RasterGraphics.pdf

5.  http://www.crl.hpl.hp.com/who/people/ulichney/bib/papers/1999-encyclopedia.pdf

6.  Ulichney, R. 1987. Digital halftoning. Cambridge, MA: MIT Press

Необходимое программное обеспечение.

Бесплатная программа для просмотра и манипуляций растровыми изображениями.(http://www.xnview.com/)

 

1.2        Поворот растра на заданный угол с помощью комбинации трех сдвигов

Вход: растровый файл в любом удобном формате. Значение угла поворота (в градусах).

Выход: повернутый растровый файл в любом удобном формате.

Внимание! ширина и высота повернутого файла отличаются от ширины и высоты входного файла. Пустые пикселы надо закрасить цветом фона (например черным)

Алгоритм: Преобразование поворота заменяется на последовательность из трех сдвигов (=shear не перепутайте с translation=параллельным переносом)

Литература

1.        Хилл Ф., Open GL. Программирование компьютерной графики. Для профессионалов. — СПб.: Питер, 2002. — 1088 с. ISBN 5-318-00219-6

2.        Foley J. D., A. van Dam, Feiner S. K., Hughes J. H., Computer graphics: principles and practice. 2nd ed. in C. Addison-Wesley, 1996, 1175 p., ISBN 0-201-84840-6

3.        http://www.cg.tuwien.ac.at/courses/CG2/SS2002/RasterGraphics.pdf

 

2         Postscript

В рамках данного курса студенты должны познакомится с языком PostScript.

Вот список наиболее интересных (важных) книг о Postscript:

A manual of mathematical illustration PostScript language tutorial and cookbook (the `blue book') PostScript language design (the `green book') PostScript language reference language manuals (originally the `red book'). Thinking in PostScript

Для практических экспериментов с PostScript можно воспользоваться программами ghostscript и ghostview (ghostview использует внутри ghostscript, но предоставляет более удобный пользовательский интерфейс. Скачать надо обе). Эти программы можно скачать здесь

 

Для того чтобы изучение было более интересным предлагается выполнить следующие упражнения:

·         Нарисовать 7 сфер равного радиуса, касающихся друг друга (одна в центре и шесть вокруг)

·         Нарисовать кривую Гильберта 1-го или 2-го типа в виде рекурсивной процедуры на языке Postscript.

·         Нарисовать проекцию 3D аналога кривой Гильберта.

·         Написать программу (на любом языке программирования), которая выводит растровое изображение с помощью Postscript (Вход: растровый файл в удобном формате; Выход: файл Postscript)

3         Кривые Безье и B-сплайны

Литература

1.     http://www.cg.tuwien.ac.at/courses/CG2/SS2002/CAGD.pdf

2.     On-Line Geometric Modeling Notes. Computer Science Department, University of California, Davis. (http://graphics.cs.ucdavis.edu/CAGDNotes/CAGD-Notes.html)

3.     Farin G. Curves and surfaces for computer aided geometric design: a practical guide. 4th ed. ACADEMIC PRESS 1997, 429 p., ISBN 0-12-249054-1

4.     Шикин Е.В., Плис А.И., Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. — М.: ДИАЛОГ-МИФИ, 1996. – 240 с.

 

3.1        Адаптивное рекурсивное разбиение кривой Безье

Программа должна позволить пользователю задать набор котрольных точек (с помощью мыши). Программа рисует кривую Безье n -ой степени по n+1 контрольной точке.

Алгоритм: рекурсивный алгоритм разбиения кривой (algorithm de Casteljau). Рекурсия прекращается когда кусочек кривой становиться достаточно плоским

Дополнительные задачи:

·         интерактивное редактирование кривой

·         анимация (контрольные точки движутся и отражаются от границ окна, кривая перерисовывается вместе с ними)

·         нарисовать B-spline, используя тот же набор контрольных точек.

·         задать дополнительный прямоугольник отсечения и рисовать части кривой вне и внутри него разным цветом

4         OpenGL и GLUT

Библиотека GLUT может быть скачена здесь (GLUT for Win32)

Здесь расположен набор обучающих программ для изучения OpenGL

4.1        Растровая аппроксимация диаграмм Вороного для ломанных

Здесь имеется программа для растровой аппроксимации диаграмм Вороного для точек с помощью OpenGL. Вы должны модифицировать эту программу так, чтобы она рисовала диаграммы Вороного для ломанных

 

5         Аналитическое построение диаграмм Вороного.

5.1        Диаграммы Вороного для отрезков являющихся сторонами выпуклого многоугольника.

Придумать и реализовать алгоритм, строящий диаграммы Вороного для набора отрезков образующих выпуклый многоугольник (N.B.: это гораздо проще чем в общем случае!)

Дополнительные задачи:

Обобщить исходный алгоритм для пары выпуклых непересекающихся многоугольников Подумать, как решить эту задачу для n – выпуклых многоугольников. Подумать, что необходимо, для того чтобы обобщить исходный алгоритм для одного невыпуклого многоугольника.
Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика