Математические модели представления компьютерной графики

УДК 004.92 М.А. Прилепко

Омский государственный технический университет, г. Омск

МАТЕМАТИЧЕСКИЕ МОДЕЛИ ПРЕДСТАВЛЕНИЯ КОМПЬЮТЕРНОЙ ГРАФИКИ

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

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

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

Геометрическое моделирование - это математическое моделирование геометрических объектов, то есть объектов, заданных в пространстве своими формой, составом и размерами.

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

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

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

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

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

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

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

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

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

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

Рис. 1. Классификация математических моделей компьютерной графики

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

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

Описание нулевой степени характерно для точек. Набором точек, заданных с достаточной плотностью, можно представить поверхность любой сложности и формы. Набором пространственных элементов (вокселей) представляются и твердотельные объекты. Описанием таких наборов могут служить трехмерные матрицы, элементы которых указывают на принадлежность объекту элементов пространства, поставленных в соответствие элементам матрицы. Такие модели называют рецепторными. Многочлен первой степени в зависимости от числа аргументов описывает в пространстве прямую линию или плоскость. Отрезки прямых линий используются для представления поверхностей объектов в каркасных моделях, участки плоскости - в поверхностных. В твердотельных моделях примитивами могут служить полупространства, ограниченные плоскостями. Использование для описания моделей многочленов более высокой, чем первая, степени дает криволинейные примитивы. В каркасных моделях это кривые линии, в поверхностных - криволинейные поверхности, в твердотельных - участки пространства, ограниченные криволинейными поверхностями. Отображаемые объекты редко состоят из одного примитива, как правило, они являются составными. С другой стороны, объекты могут быть весьма простыми, например, точечные. Ясно, что объекты различной сложности приходится описывать по-разному. Форма описания объектов, принятая в моделях, является еще одним важным признаком их классификации. По этому признаку выделяются табличные, аналитические и кусочно-аналитические модели.

В табличных моделях для описания объектов используют наборы пространственных координат элементов, характерных для этих объектов. Табличное описание может применяться в моделях со всеми перечисленными разновидностями топологических свойств. Аналитические модели описывают объекты с помощью аналитических выражений (уравнений). Применяются они для объектов простой формы, например, ограниченных поверхностями второго порядка. Кусочно-аналитические модели сочетают аналитическую и логическую формы описания действий. Они включают аналитическое описание примитивов и сведения об их связях в объекте. Для описания «стыковки» примитивов в таких моделях применяют, например, операции над множествами, булевские функции, Я-функции [2].

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

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

операций называется конструктивным представлением объемной геометрии (Constructive Solid Geometry - CSG representation). Дерево называется деревом CSG (CSG tree) (Рис. 2).

Дерево CSG обладает следующими преимуществами:

- структура данных проста, а их представление компактно, что облегчает обработку;

- объемное тело, описываемое деревом CSG, всегда является корректным, то есть его внутренний объем однозначно отделен от внешнего. Примером некорректного объемного

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

- представление CSG всегда может быть преобразовано к соответствующему представлению B-Rep. Это позволяет взаимодействовать с программами, ориентированными на использование B-Rep;

- параметрическое моделирование легко реализуется изменением параметров соответствующих примитивов.

Рис. 2. Пример дерева CSG

Есть у этого дерева и недостатки:

- поскольку дерево CSG хранит историю применения булевских операций, в процессе моделирования могут использоваться только они. Это требование жестко ограничивает диапазон моделируемых объектов. Более того, оно исключает использование удобных функций локального изменения, таких как поднятие и скругление;

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

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

Вторая структура содержит сведения о границах объема (вершинах, ребрах, гранях и их соединении друг с другом) - это представление называется граничным представлением (boundary representation - B-rep), а структура данных - структурой B-rep (B-rep data structure) (рис. 3). Многие структуры B-rep строятся по-разному в зависимости от того, какой элемент считается основным при сохранении сведений о связности.

Рис. 3. Объемное тело в представление В-гер

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

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

Таблицы представления В-Яер Таблица 1

Таблица граней Таблица ребер Таблица вершин

Грань Ребра Ребро Вершины Вершина Координаты

F1 E1, E5, Еб Е1 V1, V2 V1 Х1, У1, Z1

F2 Е2, Еб, Е7 Е2 V2, V3 V2 Х2, У2, Z2

F3 Е3, Е7, Eg Ез V3, V4 V3 Хз, Уз, Z3

F4 Е4, Е8, Е5 Е4 V4, V1 V4 Х4, У4, Z4

F5 Е1, Е2, Е3, Е4 Е5 V1, V5 V5 Х5, У5, Z5

Еб V2, V5 V6 Хб, Уб, Z6

Е7 V3, V5

Е8 V4, V5

Структура данных B-Rep выглядит очень простой и компактной. Однако она не используется в развитых системах твердотельного моделирования из-за перечисленных ниже недостатков:

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

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

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

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

Есть две распространенные структуры данных, которые позволяют избежать перечисленных проблем при сохранении граничного представления объемного тела - это структура полуребер (half-edge data structure) и структура крыльевых ребер (winged-edge data structure).

Третья структура представляет объем в виде комбинации элементарных объемов (например, кубов). Можно придумать множество моделей разложения, выбирая разные элементарные объемы, но ни одна из них не может точно описать объемное тело [4].

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

Библиографический список

Е. А. Никулин. - СПб. : БХВ-Петербург, 2003.