WWW.PROGRAMMA.X-PDF.RU
БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Учебные и рабочие программы
 

«Программная реализация параллельного алгоритма процедурной генерации геометрических объектов Направление 230100.68 «Информатика и вычислительная техника» Программа «Информационное и прог ...»

Министерство образования и наук

и Российской Федерации

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

«Комсомольский-на-Амуре государственный

технический университет»

На правах рукописи

Юрков Илья Игоревич

Программная реализация параллельного алгоритма

процедурной генерации геометрических объектов

Направление 230100.68 «Информатика и вычислительная техника»

Программа «Информационное и программное обеспечение систем автоматизированного проектирования»

АВТОРЕФЕРАТ

ДИССЕРТАЦИИ

на соискание академической степени магистра

Работа выполнена в ФГБОУ ВПО «Комсомольский-на-Амуре государственный технический университет»

Научный руководитель: доктор физико-математических наук, профессор Хусаинов Ахмет Аксанович Рецензент: кандидат физико-математических наук, доцент Дегтяренко Валентина Альбертовна, проректор по учебной работе ФГБОУ ВПО «Амурский гуманитарнопедагогический государственный университет»

Защита состоится « 30 » июня 2015 года в 14 часов 00 мин. на заседании государственной экзаменационной комиссии по направлению 230100.68 «Информатика и вычислительная техника» в Комсомольском-наАмуре государственном техническом университете по адресу: 681013, г.

Комсомольск-на-Амуре, пр. Ленина, 27, ауд. 321/3

Автореферат разослан 23 июня 2015 г.

Руководитель магистерской программы В.А. Тихомиров

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Построение моделей различных объектов методом процедурной генерации — распространенная задача, которая находит применение во многих сферах, связанных с компьютерной графикой, например, в создании компьютерных игр или мультфильмов. Определение процедурной техники генерации объектов дано в книге Дэвида Эберта «Texturing & Modeling: A Procedural Approach». Она используется тогда, когда нужно получить большое множество моделей с уникальными характеристиками, которое нельзя получить в разумные сроки и при разумных трудозатратах обычным способом, трудом художника.

Например, в литературе рассматривается алгоритм процедурной генерации моделей панельных зданий, в народе именуемых «хрущевками».

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

Параллельные вычисления являются эффективным инструментом повышения производительности вычислений, но только лишь в том случае, если выполняемый алгоритм исходя из своей структуры имеет возможности к параллельному выполнению. Так получилось, что многие алгоритмы процедурной генерации объектов очень хорошо поддаются распараллеливанию, в том числе и рассматриваемый алгоритм процедурной генерации панельных домов.

После анализа научной литературы по этой теме, были сформулированы две основные задачи, решению которых посвящена данная работа:

1. Разработать и реализовать такой многопоточный алгоритм построения здания который позволит получить ускорение от распараллеливания на 2- и 4- ядерных процессорах, широко распространенных в компьютерах.

2. Разработать и реализовать такой алгоритм построения карты города, при котором город составленный из панельных зданий выглядел приемлемо с художественной точки зрения.

Цель исследования. Разработать программное обеспечение для построения модели города с применением техники параллельных вычислений.

Задачи исследования. Для достижения поставленной цели необходимо решить следующие задачи:

1. Проанализировать предметную область.

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

3. Построить и обосновать параллельный алгоритм генерации модели здания и алгоритм генерации модели города.

4. Разработать и протестировать программное обеспечение.

Объектом исследования являются алгоритмы процедурной генерации геометрических объектов.

Предмет исследования – метод процедурной генерации модели панельного здания и модели города.





Методы исследования. В магистерской диссертации используется метод параллельных вычислений. Применяется теория L-систем.

Научная новизна. К новым научным результатам, полученным и представленным автором к защите, относятся следующие:

1. Используя метод параллельных вычислений была повышена скорость работы алгоритма генерации модели панельного здания.

2. На основе принципа L-систем разработан алгоритм генерирующий древовидную структуру улиц города, напоминающую улицы реального города.

Достоверность и обоснованность полученных результатов.

Достоверность и обоснованность результатов магистерской диссертации достигается путем проведения компьютерного эксперимента.

Практическая значимость. Работа имеет теоретическое и практическое значение. Она показала, что скорость выполнения рассмотренного алгоритма можно существенно увеличить. Так же данная работа показала возможность реализации на практике алгоритма генерации модели города на основе принципа L-систем.

Личный вклад автора состоит в постановке задач исследования, построении математической модели и алгоритмов генерации модели города, разработке многопоточного варианта алгоритма генерации панельных домов, разработке и тестировании программного обеспечения.

Основные положения работы, выносимые на защиту:

1. Разработан многопоточный вариант алгоритма генерации панельных домов, больше известных под названием «хрущевка».

2. Разработан алгоритм генерации модели города на основе принципа L-систем.

3. Разработано и протестировано программное обеспечение.

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих семинарах и научных конференциях:

Научный семинар кафедры «Математическое обеспечение и применение ЭВМ».

45-я научно-техническая конференция аспирантов и студентов Комсомольского-на-Амуре государственного технического университета (г.

Комсомольск-на-Амуре, 2015).

Публикации. Результаты диссертационного исследования опубликованы в 2 научных работах.

Структура и объем работы. Диссертация состоит из введения, общей характеристики работы, трех глав, заключения и списка использованных источников и приложения. Объем диссертации составляет 68 страниц. Текст работы содержит 23 рисунка. Список литературы включает 10 источников.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обозначены цели и задачи работы, обоснована актуальность, новизна и теоретическая значимость работы, сформулированы основные результаты исследования.

В общей характеристике работы определяются: цель исследования;

задачи исследования; объект и предмет исследования; методы исследования;

новизна полученных результатов; достоверность и обоснованность результатов исследования; практическая значимость и ценность работы;

личный вклад автора; основные положения работы, выносимые на защиту;

апробация результатов работы; публикации; структура и объем магистерской диссертации.

Первая глава посвящена обобщению процедурной генерации и техники параллельных вычислений. Дан краткий обзор возможностей процедурной генерации, возможностей и актуальности техники параллельных вычислений.

Процедурная генерация — это группа методов, в которых при помощи особых вычислительных алгоритмов создаются модели, которые изображают различные объекты — дома, растения, ландшафт, текстуры. Техники процедурной генерации – это сегменты программного кода или алгоритмы, которые определяют характеристики модели или эффекта, сгенерированного компьютером. Например, процедурная техника для создания мраморной поверхности не использует изображение, которое отсканировано или сфотографировано, чтобы определять значение цвета. Вместо этого она использует алгоритм и математические функции.

Одна из самых важных особенностей процедурной генерации – это абстракция. В процедурном подходе мы вместо того, чтобы явно задавать и хранить все детали сложной сцены, мы абстрагируем их в функцию или алгоритм (процедуру) и вызываем её, когда потребуется. Таким образом, мы экономим память, так как все детали не заданы теперь явно, а в процедуре, и требования по времени для уточнения деталей смещены от программиста к компьютеру. Это позволяет создавать модели с разным разрешением и текстуры, которые могут быть приведены к необходимому разрешению.

Мы так же можем использовать возможности параметрического управления, что позволяет нам присвоить параметру значимую концепцию (например, число, которое делает горы грубее или гладкой). Параметрическое управление дает богатые возможности для моделирования: несколько параметров предоставляют огромное количество сочетаний деталей.

Параметрический контроль освобождает пользователя от проблем низкоуровневого уточнения и редактирования деталей. Дополнительные возможности также представляют стохастические процедуры.

Процедурные модели предоставляют программисту большие возможности. Дизайнер, используя процедуры, может отразить суть предмета, явления или движения, не ограничиваясь законами физики.

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

Помимо прочего в главе была затронута тема параллельных вычислений. Применение параллельных вычислительных систем (ПВС) является стратегическим направлением развития вычислительной техники.

Это обстоятельство вызвано не только принципиальным ограничением максимально возможного быстродействия обычных последовательных ЭВМ, но и практически постоянным существованием вычислительных задач, для решения которых возможностей существующих средств вычислительной техники всегда оказывается недостаточно.

Такие современные проблемы «большого вызова» возможностям современной науки и техники, как моделирование климата, генная инженерия, проектирование интегральных схем, анализ загрязнения окружающей среды, создание лекарственных препаратов требуют для своего анализа ЭВМ с производительностью более 1000 миллиардов операций с плавающей запятой в секунду (1 террафлопс).

Организация параллельности вычислений, когда в один и тот же момент времени выполняется одновременно несколько операций обработки данных, осуществляется, в основном, введением избыточности функциональных устройств (многопроцессорности). В этом случае можно достичь ускорения процесса решения вычислительной задачи, если осуществить разделение применяемого алгоритма на информационно независимые части и организовать выполнение каждой части вычислений на разных процессорах. Подобный подход позволяет выполнять необходимые вычисления с меньшими затратами времени, и возможность получения максимального ускорения ограничивается только числом имеющихся процессоров и количеством «независимых» частей в выполняемых вычислениях.

Кроме того в главе был дан обзор аналогичных работ по процедурной генерации, а так же был сделан вывод о возможности ускорения алгоритма процедурной генерации геометрических объектов с помощью техники параллельных вычислений.

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

В конце пятидесятых годов для решения остро стоящей жилищной проблемы в Советском Союзе началось массовое строительство панельных или кирпичных двух-пятиэтажных домов. В отличие от архитектурных традиций предыдущих времён, когда каждое здание индивидуально проектировалось архитектором, данные дома строились в массовом порядке, в основе каждого здания лежал один из пары десятков типовых проектов, у таких зданий отсутствовали так называемые «архитектурные излишества» лепнина и другие декоративные элементы.

В народном сознании инициатором строительства этих домов являлся Никита Сергеевич Хрущев, который руководил страной в то время, поэтому за такими зданиями прочно закрепился термин «хрущевка». В данной работе «хрущевкой» будет называться именно панельный дом.

В данной работе ставиться задача алгоритмически описать дом типа «хрущевка», что позволит в дальнейшем быстро генерировать целые улицы таких домов. Такие городские ландшафты в дальнейшем можно будет использовать при разработке компьютерных игр. Таким образом, необходимо выделить примитивы, из которых в дальнейшем может быть составлено здание типа «хрущевка».

Так же в данной главе было дано краткое описание L-систем, в контексте решаемых в работе задач, и описан предложенный алгоритм генерации структуры улиц города на основе L-систем.

В 1968г. Венгерский биолог и ботаник Аристид Линденмайер (Aristid Lindenmayer) предложил математическую модель для изучения развития простых многоклеточных организмов, которая позже была расширена и используется для моделирования сложных ветвящихся структур — разнообразных деревьев и цветов. Эта модель получила название Lindenmayer System, или просто L-System, в данной работе они будут использоваться для генерации улиц города.

Для генерации более реалистичной карты города возьмём за основы фрактал называемый L-системой, который описывает древовидные ветвящиеся структуры. В компьютерной графике его часто применяют, чтобы процедурно генерировать реалистичные растения, деревья, но мы с помощью его принципа сгенерируем ветвящуюся структуру улиц.

Алгоритм генерации структуры рекурсивный, его основная функция работает следующим образом (см. рисунок 2.15). В цикле она создаёт структуру одной дороги из чанков (кусков) так, что чанки расположены один за другим, и каждый из них отклоняется от направления предыдущего на некий случайный угол. Таким образом строится структура отдельной улицы.

Чтобы построить другие улицы в основном цикле после добавления каждого чанка в общую структуру данных описывающую дороги добавляется две новые дороги направленные под углом 90 градусов влево и вправо по отношению к текущему чанку, и делаются рекурсивные вызовы основной функции для проработки дочерних дорог.

В рекурсивно вызываемую функцию передаётся информация о текущей глубине рекурсии, в соответствии с чем заполняется информация о размере текущей дороги, и принимается решение о добавлении и обсчете правых дочерних дорог у текущей дороги (у дорог уровня рекурсии ниже начального не добавляются правые дороги, для более качественного результата). Так же стоит упомянуть о наличии в данном алгоритме проверки добавляемого чанка на пересечения с уже сгенерированной структурой — при пересечении длинна чанка обрезается до точки пересечения и основной цикл функции строящей текущую дорогу завершается. Таким образом дороги не смешиваются в беспорядочную структуру, а соединяются в структуру более гармоничного характера.

Рисунок 1 – Схема работы рекурсивной функции второго уровня вложенности. а - в основной функции строится первый чанк дороги; б - та же функция вызывается рекурсивно и строит тем же алгоритмом дочерние дороги; в - строится следующий чанк и алгоритм повторяется Кроме того были описаны используемые для решения данной задачи некоторые приёмы работы с библиотекой OpenGL.

В третьей главе рассматриваются практически достигнутые результаты, полученные при проведении компьютерного эксперимента.

Согласно описанной математической модели было разработано программное обеспечение, выполняющее построение модели города на основе L-систем и алгоритма процедурной генерации панельных зданий. Были приведены результаты ускорения работы алгоритма на доступных процессорах.

Тестирование приложения проводилось несколько раз с разным числом потоков. Максимально возможное число потоков выбрано 5, по результатам компьютерного эксперимента это число является оптимальным.

Разработанное приложение было протестировано на 2-х и 4-ядерных процессорах и Опытным путём установлено, что многопоточный алгоритм работает быстрее однопоточного в 1,8 раз на 4-х ядерном и в 1,5 раз на 2ядерном процессорах, как показано на рисунке 2.

0,08 0,06

–  –  –

Так же, опытным путём установлено что после 5 потоков увеличение их количества не даёт существенного прироста производительности на 2-х и 4-х ядерных процессорах Intel.

В заключении перечислены основные результаты работы.

ЗАКЛЮЧЕНИЕ

1. Был предложен алгоритм процедурной генерации структуры улиц города используя принцип L-систем. Данный алгоритм позволил программе строить модель города, в определённой степени напоминающую реальный город, и применимую в художественных целях.

2. Предложена модификация алгоритма генерации модели панельных зданий, ориентированная на использование параллельных вычислений.

Данный алгоритм был использован в алгоритме генерации модели города, что позволило сократить временные издержки.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ИССЛЕДОВАНИЯ

1 Юрков, И.И. Разработка и программная реализация параллельного алгоритма процедурной генерации зданий и города / И.И. Юрков // журнал «Аспирант и соискатель», Москва, Спутник+, выпуск №3, 2015 г. (в печати).

2 Юрков, И.И. Программная реализация параллельного алгоритма процедурной генерации геометрических объектов / И.И Юрков, А.А.

Хусаинов // Научно-техническое творчество аспирантов и студентов:

материалы 45-й научно-технической конференции аспирантов и студентов КнАГТУ (в печати).



 


Похожие работы:

«1. Цели освоения дисциплины В дисциплине «Детали мехатронных модулей, роботов и их конструирование» излагается материал, относящийся к вопросам инженерной деятельности в области разработки и проектирования деталей, узлов мехатронных модулей. Полученные знания по данной дисциплине используются при изучении специальных дисциплин и выполнении выпускной квалификационной работы.Цели дисциплины в соответствии с целями ООП: Подготовка выпускников к проектно-конструкторской деятельности в области...»

«Утвержден на заседании Ученого совета института 02 апреля 2014 года, протокол № 7 ОТЧЕТ о результатах самообследования негосударственного образовательного учреждения высшего профессионального образования Вологодский институт бизнеса Вологда, 2014 СОДЕРЖАНИЕ I. Аналитическая часть Общие сведения об образовательной организации 1. Образовательная деятельность 2. Научно-исследовательская деятельность 3. Международная деятельность 4. Внеучебная работа 5. Материально-техническое обеспечение 6. II....»

«Разработан Политехническое отделение «ММРК им. И.И. Месяцева» ФГБОУ ВПО «МГТУ» ММРК Программа подготовки специалистов среднего звена по Страница 2 из 33 специальности 21.02.03 Сооружение и эксплуатация газонефтепроводов и газонефтехранилищ Лист ознакомления Должность Ф.И.О. Дата, подпись Разработан Политехническое отделение «ММРК им. И.И. Месяцева» ФГБОУ ВПО «МГТУ» ММРК Программа подготовки специалистов среднего звена по Страница 3 из 33 специальности 21.02.03 Сооружение и эксплуатация...»

«ПЕРВОЕ ВЫСШЕЕ ТЕХНИЧЕСКОЕ УЧЕБНОЕ ЗАВЕДЕНИЕ РОССИИ МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «НАЦИОНАЛЬНЫЙ МИНЕРАЛЬНО-СЫРЬЕВОЙ УНИВЕРСИТЕТ «ГОРНЫЙ» Согласовано Утверждаю Руководитель ООП по Зав. кафедрой направлению 15.04.01 машиностроения профессор Максаров В.В. профессор Максаров В.В. «» _ 2015 г. «» _ 2015 г. РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ «НАУЧНЫЕ ОСНОВЫ ТЕХНОЛОГИИ...»

«САНКТ-ПЕТЕРБУРГСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ПЕТРА ВЕЛИКОГО УТВЕРЖДАЮ Директор ИЭиТС Н.А. Забелин 20_ г. РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭЛЕМЕНТОВ ЭЛЕКТРОЭНЕРГЕТИЧЕСКИХ СИСТЕМ Наименование дисциплины Кафедра-разработчик Электрические системы и сети Наименование кафедры Направление (специальность) подготовки: 13.06.01 Электрои теплотехника Код и наименование Наименование ООП: 13.06.01_06 Электрические станции и электроэнергетические системы Код и наименование...»

«ПЕРВОЕ ВЫСШЕЕ ТЕХНИЧЕСКОЕ УЧЕБНОЕ ЗАВЕДЕНИЕ РОССИИ МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «НАЦИОНАЛЬНЫЙ МИНЕРАЛЬНО-СЫРЬЕВОЙ УНИВЕРСИТЕТ «ГОРНЫЙ» Согласовано Утверждаю Руководитель ООП Зав. кафедрой МКП по специальности 21.05.02 проф. М.А. Иванов проф. Ю.Б. Марин «» 2015 г. «» 2015 г. РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ «ОБЩАЯ ГЕОХИМИЯ» Направление подготовки (специальность):...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФГБОУ ВПО «УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ЛЕСОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» УРАЛЬСКОЕ ОТДЕЛЕНИЕ СЕКЦИИ НАУК О ЛЕСЕ РАЕН УРАЛЬСКИЙ ЛЕСНОЙ ТЕХНОПАРК НАУЧНОЕ ТВОРЧЕСТВО МОЛОДЕЖИ – ЛЕСНОМУ КОМПЛЕКСУ РОССИИ МАТЕРИАЛЫ IX ВСЕРОССИЙСКОЙ НАУЧНО-ТЕХНИЧЕСКОЙ КОНФЕРЕНЦИИ СТУДЕНТОВ И АСПИРАНТОВ И КОНКУРСА ПО ПРОГРАММЕ «УМНИК» Часть 2 Екатеринбург УДК 630:66\67 (042.2) ББК 43:72я43 Н 34 Научное творчество молодежи – лесному комплексу России: матер. IХ Всерос....»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО РЫБОЛОВСТВУ Дальневосточный государственный технический рыбохозяйственный университет Международная научно-техническая конференция студентов, аспирантов и молодых ученых, посвященная 85-летию ФГБОУ ВПО «Дальрыбвтуз» (Владивосток, 22-24 апреля 2015 г.) ПРОГРАММА Владивосток Дальрыбвтуз Цель конференции – установление новых и дальнейшее развитие творческих связей между студентами, углубление интеграционных процессов между вузами, направленных на изучение современных...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ТЕХНИЧЕСКОМУ РЕГУЛИРОВАНИЮ И МЕТРОЛОГИИ ГОСТ Р 22.10.05НАЦИОНАЛЬНЫЙ 201 СТАНДАРТ РОССИЙСКОЙ ФЕДЕРАЦИИ Проект, редакция первая Безопасность в чрезвычайных ситуациях БЕЗОПАСНОСТЬ ЖИЗНЕДЕЯТЕЛЬНОСТИ НАСЕЛЕНИЯ НА РАДИОАКТИВНО ЗАГРЯЗНЕННЫХ ТЕРРИТОРИЯХ Безопасное использование земель сельскохозяйственного назначения Основные положения Safety in emergency. Human life safety of population on radioactive nuclide contaminated areas. Safe use of agricultural lands. Basic principles...»

«ПЕРВОЕ ВЫСШЕЕ ТЕХНИЧЕСКОЕ УЧЕБНОЕ ЗАВЕДЕНИЕ РОССИИ МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «НАЦИОНАЛЬНЫЙ МИНЕРАЛЬНО-СЫРЬЕВОЙ УНИВЕРСИТЕТ «ГОРНЫЙ» Согласовано Утверждаю _ Руководитель ООП Зав. кафедрой АТПП по направлению 15.03.02 д.т.н. проф. В.Ю. Бажин д.т.н. проф. В.Ю. Бажин ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ «МЕХАНИКА ЖИДКОСТИ И ГАЗА» Направление подготовки: 15.03.02...»







 
2016 www.programma.x-pdf.ru - «Бесплатная электронная библиотека - Учебные, рабочие программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.