Метод Франка-Вульфа и решение матричных игр

Введение

1. Теоретическая часть

• 1.1 Мегатекстура
• 1.2 Текстура (трёхмерная графика)
• 1.3 Примитивы трёхмерной графики
• 1.4 Методы текстурирования

2. Порядок выполнения работы

• 2.1 Описание физической модели
• 2.2 Описание математической модели
• 2.3 Программирование модели
• 2.4 Ключевые фрагменты программы с комментариями

3. Результат выполнения приложения

Заключение

Cписок использованных источников

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

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

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

С появлением аппаратных ускорителей трехмерная графика стала развиваться очень быстрыми темпами. Вместе с повышением производительности видеокарт разработчики уделяли немало внимания расширению их возможностей, предназначенных в первую очередь для реализации новых способов повышения реалистичности изображений. Речь о наиболее популярных на данный момент методах пойдет далее. Все методы из рассмотренных ниже в той или иной мере используют дополнительные (ставшие, впрочем, стандартом de facto на сегодняшний день) возможности видеокарт. Ни один из методов не изменяет полигональную модель, то есть все методы работает в двухмерном пространстве текстуры.

мегатекстура полигональный фильтрация

1. Теоретическая часть

1.1 Мегатекстура

Мегатекстура — (англ. MegaTexture) — это графическая технология, разработанная Джоном Кармаком, техническим директором id Software. Его технология повторяет технологию Clipmaps (ClipTextures), которая разработана компанией SGI и уже достаточно давно применяется для текстурирования больших ландшафтов. Отличие мегатекстуры от clipmaps состоит в том, что мегатекстура содержит маску для добавочных текстур повышенной детализации и информацию о типе материала (трава, камень и т. п.). Технология «Мегатекстура» реализована в последней версии движка id Tech 4 и используется пока что лишь в одной игре — Enemy Territory: Quake Wars — которая разработана фирмой Splash Damage, а также будет использоваться в Prey 2. Независимыми разработчиками были созданы модификации, позволяющие использовать технологию мегатекстуры в ранее вышедших играх, например Doom 3.

Рисунок 1.1 — Расположение текстур Технология «Мегатекстура» относится к методике распределения текстур. Весь ландшафт игрового уровня покрывается одной большой текстурой вместо множества мелких текстур.

На рисунке 1 показаны белые и цветные квадраты — тексели; тонкими линиями обозначены границы отдельных текстур. Круги — области высокой (средней, низкой) детализации. Загружено по 9 квадратов каждого уровня детализации.

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

Существует несколько версий мегатекстуры в разных уровнях детализации; в каждом уровне она разбита на квадраты одинакового (в пикселях) размера. Например: мегатекстура 32 768?32768 пикселей, покрывающая участок в 640?640 метров, в максимальной (нулевой) детализации разбивается на 32?32 квадрата размером 1024?1024 пикселя (20?20 м). Первый уровень детализации состоит из 16?16 квадратов того же размера (1024?1024 px), но вдвое меньшего пространственного разрешения (то есть, размер каждого квадрата — 40?40 метров), второй — из 8?8 квадратов по 80 м каждый, и т. д.

Ближайшие к камере пиксели рендерятся с текстурой максимального качества, содержащей только небольшой участок мегатекстуры. Следующие пиксели рендерятся с текстурой меньшего качества, и маленьким разрешением. Самые дальние пиксели рендерятся с основной текстурой в уменьшенном разрешении. В игре Enemy Territory: Quake Wars разрешение мегатекстуры составляет 32 768?32 768 пикселей.

В следующем движке компании id Software — id Tech 5 — используется улучшенная версия мегатекстуры размерностью 128 000?128 000 пикселей.

1.2 Текстура (трёхмерная графика) Текстура — растровое изображение, накладываемое на поверхность полигона, из которых состоят 3D-модели, для придания ей цвета, окраски или иллюзии рельефа. Понятие «текстура» является одним из столпов 3D-моделирования, поскольку позволяет воспроизвести малые объекты поверхности, создание которых полигонами оказалось бы чрезмерно ресурсоёмким. Например, шрамы на коже, складки на одежде, мелкие камни и прочие предметы на поверхности стен и почвы.

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

Существует технология parallax mapping, для создания трёхмерного описания текстурированной поверхности с использованием карт смещения.

Тексел (сокращение от англ. Texture element) — минимальная единица текстуры трёхмерного объекта. Пиксел текстуры.

Обычно создание объекта в 3D-графике оканчивается облечением его в текстуру: камень должен выглядеть как камень, табурет — как табурет. Текстура представляет собой плоское изображение соответствующего содержания: поверхность камня собирается из фотографии камня, сиденье табурета собирается из фотографии табурета. И чем качественней будет изображение, налагаемое на объект, тем лучше он будет выглядеть.

Рисунок 1.2 — Пример использования текстурирования 1 — 3D-модель без текстурирования; 2 -с текстурированием

1.3 Примитивы трёхмерной графики Проще всего будет объяснить значение термина «тексел» на примере трёхмерных игр. Если подойти вплотную к стене в какой-нибудь старой 3D-игре — (Wolfenstein или Duke), то можно наблюдать, как текстура стены распадается на одинаково закрашенные квадраты. Те увеличиваются при приближении и собираются обратно в осмысленный рисунок при отдалении. Эти квадраты и называются текселами, и чем крупнее исходный рисунок текстуры, тем меньше становятся текселы. Для идеального отображения текстуры количество текселов должно совпадать с количеством пикселов, но из-за возрастающей ресурсоёмкости такое возможно только в случае рендера статичных картинок.

С появлением более совершенных 3D-видеокарт, стал применяться метод интерполяции (например, бикубическая интерполяция). Количество попадающих в поле зрения текселов уменьшалось без сильной потери качества изображения. Это достигалось благодаря тому, что изменение цвета при переходе между текселами делается плавно, без резких границ.

Понятие «минимальной видимой единицы текстуры» осталось основным при проработке 3D-графики. Даже несмотря на современные достижения в программных и аппаратных средствах при рендеринге. Так, например, кроме кубической и бикубической интерполяции, которая сглаживает и размывает (она применялась в первых видеоускорителях вроде 3dfx), существует интерполяция 2xSAI, сглаживающая пикселы погруппно, ориентируясь на цвет и близость к краю текстуры. Также применяется подтекстурное наложение: под сильно размытую текстуру накладывается ещё одна, чёткая и с большим количеством контрастирующих пиксельных точек, что создаёт эффект шероховатости.

Для увеличения производительности, при удалении на большое расстояние от поверхности, большая текстура постепенно заменяется на уменьшенную версию этой же текстуры (MIP-текстурирование), обычно в 2 раза меньше по каждому измерению.

Шейдер (англ. Shader; схема затенения, программа построения теней) — это программа для одной из ступеней графического конвейера, используемая в трёхмерной графике для определения окончательных параметров объекта или изображения. Она может включать в себя произвольной сложности описание поглощения и рассеяния света, наложения текстуры, отражение и преломление, затенение, смещение поверхности и эффекты пост-обработки.

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

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

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

Предшественниками шейдеров были процедурная генерация текстур (широко применявшаяся в Unreal для создания анимированных текстур воды и огня) и мультитекстурирование (на нём был основан язык шейдеров, применявшийся в Quake 3). Но и эти механизмы не обеспечивают такой гибкости, как шейдеры.

Полигональная сетка (англ. polygon mesh) или неструктурированная сетка это совокупность вершин, рёбер и граней, которые определяют форму многогранного объекта втрехмерной компьютерной графике и объемном моделировании. Гранями обычно являются треугольники, четырехугольники или другие простые выпуклые многоугольники (полигоны), так как это упрощает рендеринг, но так же может состоять из наиболее общих вогнутых многоугольников, или многоугольников с дырками. Учение о полигональных сетках это большой подраздел компьютерной графики и геометрического моделирования. Разные представления полигональных сеток используются для разных целей и приложений. Множество операций проводимых над сетками могут включать Булевую алгебру, сглаживание, упрощение и многие другие. Сетевые представления, такие как «потоковые» и «прогрессивные» сетки, используются для передачи полигональных сеток по сети. Объемные сетки отличаются от полигональных тем, что они явно представляют и поверхность и объём структуры, тогда как полигональные сетки явно представляют лишь поверхность (объём неявный). Так как полигональные сетки широко используются в компьютерной графике, также существуют алгоритмы трассировки лучей, обнаружения столкновений и динамики твердых тел для полигональных сеток.

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

Рисунок 1.4 — Элементы моделирования сетки Вершина — это позиция вместе с другой информацией, такой как цвет, нормальный вектор и координаты текстуры. Ребро это соединение между двумя вершинами. Грань это замкнутое множество ребер, в котором треугольная грань имеет три ребра и четырехугольное — четыре. Полигон это множество граней. В системах, которые поддерживают многосторонние грани, полигоны и грани равнозначны. Однако, большинство аппаратного обеспечения для рендеринга поддерживает лишь грани с тремя или четырьмя сторонам, так что полигоны представлены как множество граней. Математически, полигональная сетка может быть представлена в виде неструктурированной сетки, или неориентированного графа, с добавлением свойств геометрии, формы и топологии.

Поверхности, чаще называемые группами сглаживания, полезны, но не обязательны для группирования гладких областей. Представьте себе цилиндр с крышками, такой как жестяная банка. Для гладкого затенения сторон, все нормали должны указывать горизонтально от центра, тогда как нормали крышек должны указывать в +/-(0,0,1) направлениях. Если рендерить как единую, затененную по Фонгу поверхность, вершины складок имели бы неправильные нормали. Поэтому, нужен способ определения, где прекращать сглаживание для того, чтобы группировать гладкие части сетки, также, как полигоны группируют трехсторонние грани. Как альтернатива предоставлению поверхностей/групп сглаживания, сетка может содержать другую информацию для расчета тех же данных, такая как разделяющий угол (полигоны с нормалями выше этого предела либо автоматически рассматриваются как отдельные группы сглаживания, либо по отношению к ребру между ними применяется какая-либо техника, как например разделение или скашивание). Также, полигональные сетки с очень высоким разрешением менее подвержены проблемам, для решения которых требуются группы сглаживания, так как их полигоны настолько малы, что нужда в них пропадает. Кроме того, другая альтернатива существует в возможности просто отсоединения самих поверхностей от оставшейся части сетки. Рендереры не пытаются сглаживать ребра между несмежными полигонами.

Формат полигональной сетки может определять и другие полезные данные. Могут быть определены группы, которые задают отдельные элементы сетки и полезны для установления отдельных подобъектов для скелетной анимации или отдельных субъектов нескелетной анимации. Обычно определяются материалы, позволяя разным частям сетки использовать разные шейдеры при рендере. Большинство форматов сетки также предполагают UV координаты, которые являются отдельным двухмерным представлением полигональной сетки, «развернутым» чтобы показать, какая часть двумерной текстуры применяется к разным полигонам сетки.

Полигональные сетки могут быть представлены множеством способов, используя разные способы хранения вершин, ребер и граней. В них входят:

· Список граней: описание граней происходит с помощью указателей в список вершин.

· «Крылатое» представление: в нём каждая точка ребра указывает на две вершины, две грани и четыре (по часовой стрелке и против часовой) ребра, которые её касаются. Крылатое представление позволяет обойти поверхность за постоянное время, но у него большие требования по памяти хранения.

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

· Четырехреберные сетки[неизвестный термин], которые хранят ребра, полуребра и вершины без какого-либо указания полигонов. Полигоны прямо не выражены в представлении, и могут быть найдены обходом структуры. Требования по памяти аналогичны полуреберным сеткам.

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

· Вершинное представление: представлены лишь вершины, указывающие на другие вершины. Информация о гранях и ребрах выражена неявно в этом представлении. Однако, простота представления позволяет проводить над сеткой множество эффективных операций.

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

1.4 Методы текстурирования

Анизотропная фильтрация (англ. Anisotropic Filtering, AF) — в трёхмерной графике метод улучшения качества изображения текстур на поверхностях, сильно наклонённых относительно камеры. Как билинейная и трилинейная фильтрация, анизотропная фильтрация позволяет устранять эффект ступенчатости на различных поверхностях, но при этом вносит меньше размытия и поэтому позволяет сохранить большую детальность изображения. Анизотропная фильтрация требует относительно сложного вычисления, и поэтому только около 2004 года она стала «бесплатной» (не снижающей общей кадровой частоты, либо снижающей её незначительно) в графических платах потребительского уровня.

Выбирается MIP-текстура, соответствующая разрешению поперёк направления обзора. Берут несколько текселей вдоль направления обзора (в фильтрации 2x — до двух, в 4x — до четырёх, и т. д.) и усредняют их цвета. Так как пикселей на экране может быть 1 миллион и даже больше, а каждый тексел — это не менее 32 бит, анизотропная фильтрация требует огромной пропускной способности видеопамяти (десятки гигабайт в секунду). Столь большие требования к памяти уменьшают за счёт сжатия текстур и кэширования.

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

Трилинейная фильтрация — усовершенствованный вариант билинейной фильтрации.

MIP-текстурирование, повышая чёткость изображения и процент попаданий в кэш на дальних расстояниях, имеет серьёзный недостаток: ясно видны границы раздела между MIP-уровнями. Трилинейная фильтрация позволяет исправить этот недостаток ценой некоторого снижения резкости текстур. Для этого цвет пикселя высчитывается как средневзвешенное восьми текселей: по четыре на двух соседних MIP-текстурах. В случае, если формулы MIP-текстурирования дают самую крупную или самую маленькую из MIP-текстур, трилинейная фильтрация вырождается в билинейную. С недостаточной резкостью борются, устанавливая отрицательный mip bias — то есть, текстуры берутся более детальные, чем нужно было бы без трилинейной фильтрации.

Рельефное текстурирование — метод в компьютерной графике для придания более реалистичного и насыщенного вида поверхности объектов.

Рисунок 1.5 — Сфера без и с применением рельефного текстурирования Техника заключается в том, что отклонение каждого пикселя от нормали к поверхности просчитываемого объекта смотрится в карте высот (поле высот) и применяется перед обсчётом освещения (затенение по Фонгу).

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

Normal mapping — Технология аналогична Bump mapping, но для хранения информации о рельефе используются текстуры, в которых кодируются данные не о высоте точек поверхности, а об отклонении нормалей поверхности. Для создания таких текстур обычно используются высокополигональная модель, на основе которых и генерируется текстура нормалей, и низкополигональная, на которую она накладывается.

Parallax mapping — Данная технология также использует карты нормалей, но, в отличие от normal mapping, она реализует не только освещение с учётом рельефа, но и сдвигает координаты диффузной текстуры. Этим достигается наиболее полный эффект рельефа, особенно при взгляде на поверхность под углом.

2. Порядок выполнения работы

2.1 Описание физической модели

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

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

2.2 Описание математической модели

Математическая модель — приближенное описание объекта моделирования, выраженное с помощью математической символики.

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

2.3 Программирование модели В качестве среды программирования была выбрана IDE Borland Delphi 7.0. Анализ требований показывает, что разрабатываемое приложение должно вести активное взаимодействие с пользователем и, следовательно, должно обладать мощным графическим интерфейсом. Для существенного облегчения создания такого графического приложения необходимо использовать визуальную среду программирования.

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

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

2.4 Ключевые фрагменты программы с комментариями

program a;

uses

Windows,

SysUtils,

Messages,

OpenGL,

mplayer,

vfw,

NeHeGL in 'NeHeGL.pas';

procedure glGenTextures (n: GLsizei; var textures: GLuint); stdcall; external opengl32;

procedure glBindTexture (target: GLenum; texture: GLuint); stdcall; external opengl32;

procedure glDeleteTextures (n: GLsizei; textures: PGLuint); stdcall; external 'opengl32';

procedure glCopyTexImage2D (target: GLenum; level: GLint; internalFormat: GLenum; x, y: GLint; width, height: GLsizei; border: GLint); stdcall; external 'opengl32';

procedure glTexSubImage2D (target: GLenum; level, xoffset, yoffset: GLint; width, height: GLsizei; format, atype: GLenum; const pixels: Pointer); stdcall; external 'opengl32';

var

g_window: PGL_Window;

g_keys: PKeys;

angle: GLfloat;

next: integer;

frame: integer = 0;

effect: integer;

env: boolean = true;

bg: boolean = true;

sp: boolean;

ep: boolean;

bp: boolean;

psi: TAVIStreamInfo;

pavi: IAVIStream;

pgf: IGetFrame;

bmih: BITMAPINFOHEADER;

lastframe: integer;

width: integer;

height: integer;

pdata: PGLubyte;

mpf: integer;

quadratic: GLUquadricObj;

hdd: HDRAWDIB;

h_bitmap: HBITMAP;

h_dc: HDC;

data: Pointer = nil;

begin

for i:= 0 to 256 * 256 — 1 do %%Prochбzн data obrбzku

begin

B:= Pointer (Integer (buffer) + i * 3); %%Ukazatel na B

R:= Pointer (Integer (buffer) + i * 3+2); %%Ukazatel na R

temp:= B^; %%B uloћнme do pomocnй promмnnй

B^:= R^; %%R je na sprбvnйm mнstм

R^:= temp; %%B je na sprбvnйm mнstм

end;

end;

procedure OpenAVI (szFile: LPCSTR);

var

title: PAnsiChar;

bmi: BITMAPINFO;

begin

AVIFileInit;

if AVIStreamOpenFromFile (pavi, szFile, streamtypeVIDEO, 0, OF_READ, nil) <> 0 then

MessageBox (HWND_DESKTOP,'Failed To Open The AVI Stream','Error', MB_OK or MB_ICONEXCLAMATION);

AVIStreamInfo (pavi, psi, sizeof (psi));

width:= psi.rcFrame.Right — psi.rcFrame.Left;

height:= psi.rcFrame.Bottom — psi.rcFrame.Top;

lastframe:= AVIStreamLength (pavi);

mpf:= AVIStreamSampleToTime (pavi, lastframe) div lastframe;

with bmih do

begin

biSize:= sizeof (BITMAPINFOHEADER);

biPlanes:= 1;

biBitCount:= 24;

biWidth:= 256;

biHeight:= 256;

biCompression:= BI_RGB;

end;

bmi.bmiHeader:= bmih;

h_bitmap:= CreateDIBSection (h_dc, bmi, DIB_RGB_COLORS, data, 0,0);

SelectObject (h_dc, h_bitmap);

pgf:= AVIStreamGetFrameOpen (pavi, nil);

if pgf = nil then

MessageBox (HWND_DESKTOP,'Failed To Open The AVI Frame','Error', MB_OK or MB_ICONEXCLAMATION);

title:= PAnsiChar (Format ('NeHe''s AVI Player: Width: %d, Height: %d, Frames: %d',[width, height, lastframe]));

SetWindowText (g_window.hWnd, title);

end;

procedure GrabAVIFrame (frame: integer);

lpbi: PBitmapInfoHeader;

begin

lpbi:= AVIStreamGetFrame (pgf, frame);

pdata:= Pointer (Integer (lpbi) + lpbi. biSize + lpbi. biClrUsed * sizeof (RGBQUAD));

DrawDibDraw (hdd, h_dc, 0,0,256,256,lpbi, pdata, 0,0,width, height, 0);

flipIt (data);

glTexSubImage2D (GL_TEXTURE_2D, 0, 0, 0, 256, 256, GL_RGB, GL_UNSIGNED_BYTE, data);

end;

function Initialize (window: PGL_Window; key: PKeys): boolean;

begin

g_window:= window;

g_keys:= key;

h_dc:= CreateCompatibleDC (0);

angle:= 0.0;

hdd:= DrawDibOpen;

glClearColor (0.0, 0.0, 0.0, 0.5);

glClearDepth (1.0);

glDepthFunc (GL_LEQUAL);

glEnable (GL_DEPTH_TEST);

glShadeModel (GL_SMOOTH);

glBegin (GL_QUADS);

glTexCoord2f (1.0,1.0); glVertex3f (11.0, 8.3,-20.0);

glTexCoord2f (0.0,1.0); glVertex3f (-11.0, 8.3,-20.0);

glTexCoord2f (0.0,0.0); glVertex3f (-11.0,-8.3,-20.0);

glTexCoord2f (1.0,0.0); glVertex3f (11.0,-8.3,-20.0);

glEnd;

end;

glLoadIdentity;

glTranslatef (0.0,0.0,-10.0);

if env then

begin

glEnable (GL_TEXTURE_GEN_S);

glEnable (GL_TEXTURE_GEN_T);

end;

glRotatef (angle*2.3,1.0,0.0,0.0);

glRotatef (angle*1.8,0.0,1.0,0.0);

glTranslatef (0.0,0.0,2.0);

case effect of

0: begin

glRotatef (angle*1.3,1.0,0.0,0.0);

glRotatef (angle*1.1,0.0,1.0,0.0);

glRotatef (angle*1.2,0.0,0.0,1.0);

glBegin (GL_QUADS);

glNormal3f (0.0,0.0,0.5);

glTexCoord2f (0.0,0.0); glVertex3f (-1.0,-1.0,1.0);

glTexCoord2f (1.0,0.0); glVertex3f (1.0,-1.0,1.0);

glTexCoord2f (1.0,1.0); glVertex3f (1.0, 1.0,1.0);

glTexCoord2f (0.0,1.0); glVertex3f (-1.0, 1.0,1.0);

glNormal3f (0.0,0.0,-0.5);

glTexCoord2f (1.0,0.0); glVertex3f (-1.0,-1.0,-1.0);

glTexCoord2f (1.0,1.0); glVertex3f (-1.0, 1.0,-1.0);

glTexCoord2f (0.0,1.0); glVertex3f (1.0, 1.0,-1.0);

glTexCoord2f (0.0,0.0); glVertex3f (1.0,-1.0,-1.0);

glNormal3f (0.0,0.5,0.0);

glTexCoord2f (0.0,1.0); glVertex3f (-1.0,1.0,-1.0);

glTexCoord2f (0.0,0.0); glVertex3f (-1.0,1.0, 1.0);

glTexCoord2f (1.0,0.0); glVertex3f (1.0,1.0, 1.0);

glTexCoord2f (1.0,1.0); glVertex3f (1.0,1.0,-1.0);

glNormal3f (0.0,-0.5,0.0);

glTexCoord2f (1.0,1.0); glVertex3f (-1.0,-1.0,-1.0);

glTexCoord2f (0.0,1.0); glVertex3f (1.0,-1.0,-1.0);

glTexCoord2f (0.0,0.0); glVertex3f (1.0,-1.0, 1.0);

glTexCoord2f (1.0,0.0); glVertex3f (-1.0,-1.0, 1.0);

glNormal3f (0.5,0.0,0.0);

glTexCoord2f (1.0,0.0); glVertex3f (1.0,-1.0,-1.0);

glTexCoord2f (1.0,1.0); glVertex3f (1.0, 1.0,-1.0);

glTexCoord2f (0.0,1.0); glVertex3f (1.0, 1.0, 1.0);

glTexCoord2f (0.0,0.0); glVertex3f (1.0,-1.0, 1.0);

glNormal3f (-0.5,0.0,0.0);

glTexCoord2f (0.0,0.0); glVertex3f (-1.0,-1.0,-1.0);

glTexCoord2f (1.0,0.0); glVertex3f (-1.0,-1.0, 1.0);

glTexCoord2f (1.0,1.0); glVertex3f (-1.0, 1.0, 1.0);

glTexCoord2f (0.0,1.0); glVertex3f (-1.0, 1.0,-1.0);

glEnd ();

end;

1: begin

glRotatef (angle*1.3,1.0,0.0,0.0);

glRotatef (angle*1.1,0.0,1.0,0.0);

glRotatef (angle*1.2,0.0,0.0,1.0);

gluSphere (quadratic, 1.3,20,20);

end;

2: begin

glRotatef (angle*1.3,1.0,0.0,0.0);

glRotatef (angle*1.1,0.0,1.0,0.0);

glRotatef (angle*1.2,0.0,0.0,1.0);

glTranslatef (0.0,0.0,-1.5);

gluCylinder (quadratic, 1.0,1.0,3.0,32,32);

end;

end;

if env then

begin

glDisable (GL_TEXTURE_GEN_S);

glDisable (GL_TEXTURE_GEN_T);

end;

glFlush;

end;

3. Результат выполнения приложения Ниже представлены результаты выполнения программы:

Рисунок 3. 1 — Результат выполнения программы Ниже представлена последовательность итераций, которая привела к данному результату:

Рисунок 3.2 — Последовательность итераций Таким образом, по результатам работу программы при заданной точности 0,1 мы нашли точку (4;9), в которой функция имеет наименьшее значение в области допустимых решений, заданной вершинами многоугольника A (0,1), B (4,9), C (5,7), D (10,0).

Заключение

В ходе выполнения данного курсовой работы были изучены такие задачи линейного и нелинейного программирования, как метод Франка-Вульфа и решение матричных игр. Для решения задач нелинейного программирования методом Франка-Вульфа была реализована программа. Задача линейного программирования решалась 3 способами, а именно, графически, аналитически и при помощи встроенного средства Microsoft Excel «Поиск решения».

В играх, где нет седловой точки, решение следует искать в смешанных стратегиях. Для определения оптимальных смешанных стратегий в играх m x n следует использовать симплекс-метод, предварительно переформулировав игровую задачу в задачу линейного программирования.

Таким образом, в данной работе также был изучен симплекс метод, который использовался при нахождении минимума и максимума линейной функции. Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.

Матричные игры вида 2 x n и m x 2 можно решать графически. У таких игр всегда имеется решение, содержащее не более двух активных стратегий для каждого из игроков.

Cписок использованных источников

1. Агафонова Н. Н. Гражданское право [Текст]: учеб. пособие для вузов / Н. Н. Агафонова, Т. В. Богачева, Л. И. Глушкова; под. общ. ред. А. Г. Калпина; авт. вступ. ст. Н. Н. Поливаев; М-во общ. и проф. образования РФ, Моск. гос. юрид. акад. — Изд. 2-е, перераб. и доп. — М.: Юристъ, 2002. — 542 с.; 22 см. — (Institutiones; т. 221). — Библиогр.: с. 530−540. — 50 000 экз. — ISBN 5−7975−0223−2 (в пер.).

2. Бахвалов Н. С. Численные методы [Текст]: учеб. пособие для физ.-мат. специальностей вузов / Н. С. Бахвалов, Н. П. Жидков, Г. М. Кобельков; под общ. ред. Н. И. Тихонова. — 2-е изд. — М.: Физматлит: Лаб. базовых знаний; СПб.: Нев. диалект, 2002. — 630 с.: ил.; 25 см. — (Технический университет. Математика). — Библиогр.: с. 622−626. — Предм. указ.: с. 627−630. — 30 000 экз. — ISBN 5−93 208−043−4 (в пер.).

3. Государственный Эрмитаж (Санкт-Петербург). Отчетная археологическая сессия (2002). Отчетная археологическая сессия за 2002 год [Текст]: тез. докл. / Гос. Эрмитаж. — СПб.: Изд-во Гос. Эрмитажа, 2001. — 62 с.: ил.; 22 см. — 300 экз. — ISBN 5−93 572−047−7.