Разработка системы моделирования наблюдения за группировкой кораблей (стр. 1 из 4)

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

1. Конструкторская часть

1.1 Постановка задачи

1.1.1 Обоснование выбора алгоритмов

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

Программное обеспечение должно позволять:

Загружать модели из проприетарного формата.

Моделировать построение морской группировки войск.

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

Обеспечивать квазиреалистичное изображение.

Моделировать ситуацию в квазиреальном времени.

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

Оценивать эффективности работы в условиях конкретной системы.

1.1.2 Анализ алгоритмов удаления невидимых линий

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

Алгоритм Робертса.

Алгоритм Робертса представляет собой первый из известных алгоритмов удаления невидимых линий. Этот математически элегантный метод работает в объектном пространстве. Модификации алгоритма, использующие предварительную пространственную сортировку вдоль оси z и простые габаритные или минимаксные тесты, позволяют добиться почти линейной зависимости роста объема вычислений от роста числа объектов.

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

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

Реализация алгоритма Робертса подразделяется на следующие этапы:

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

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

Определение нелицевых граней, удаление их из списка граней и соответствующих ребер - из списка ребер.

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

Формирование списка протыканий также на основании сравнений охватывающих оболочек объектов.

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

Формирования списка возможных ребер, соединяющих точки протыкания, для пар объектов, связанных отношением протыкания.

Проверка видимости полученных ребер по отношению ко всем объектам сцены в соответствии с действиями этапов 3 и 6.

Визуализация изображения.

Алгоритм Варнока.

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

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

Кратко опишем оригинальную версию алгоритма, предложенного Варноком.

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

Возможны четыре различных случая:

Рис.1. Соотношение проекции грани с подокном

Проекция грани полностью накрывает область;

Проекция грани пересекает область, но не содержится в ней полностью;

Проекция грани целиком содержится внутри области;

Проекция грани не имеет общих внутренних точек с рассматриваемой областью.

Очевидно, что в последнем случае грань вообще никак не влияет на то, что видно в данной области.

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

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

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

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

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

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

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

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

Рис.2. Способы разбиения окна

Разбиение, показанное на рис.5.17, а, получается с использованием прямоугольной объемлющей оболочки многоугольника. Заметим, что оболочки при этом могут быть неквадратными. Этот способ можно рекурсивно применить к любому многоугольнику, который полностью охвачен каким-нибудь окном или оболочкой. Если в окне содержится только один многоугольник и если он целиком охвачен этим окном, то его легко изобразить, не проводя дальнейшего разбиения. Такой способ разбиения полезен, в частности, при минимизации числа разбиений для простых сцен. Однако с ростом сложности сцены его преимущество сходит на нет.