Лекция 5. Трехмерное моделирование

1. Модели и структуры трехмерных пространственных данных

2. Построение поверхностей на основе триангуляционной сети

1. Модели и структуры трехмерных пространственных данных

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

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

Для применения операций над пространственными объектами они объединя­ются в слои или пространства. Каждый слой имеет набор своих характеристик.

Простейшее и наиболее общее из всех пространств называется множественно- ориентированным. К числу основных отношений, применяемых в этом простран­стве, относятся отношения объединения, пересечения, включения и членства.

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

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

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

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

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

Вышеописанные операции являются статическими. Динамические операции изменяют объекты, над которыми они работают. Основные динамические опера­ции: создание, удаление, обновление. Разновидностями операции «создать» явля­ются воспроизведение, порождение, разделение, соединение. К операциям «обно­вить» относятся перемещение, поворот, масштабирование, отражение.

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

1. 1. Аналитические модели представления поверхностей

Под аналитической моделью поверхности (АМП) будем понимать ее математическое описание, например в виде функции двух аргументов или в виде уравне­ния

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

где - параметры, которые изменяются в определенном диапазоне, а функции определяют форму поверхности.

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

В качестве примера можно представить аналитическое описание сферической поверхности, которая в декартовой системе координат имеет вид

а в параметрической форме записи:

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

,

- опорные точки-ориентиры, 0< < 1; 0 < < 1, и - коэффициенты бинома Ньютона, рассчитываемые по формуле

Для бикубического сплайна Безье, когда т = 3, п = 3, необходимо задание 16 точек-ориентиров . При этом коэффициенты , равны 1,3,3,1. Здесь можно рассмотреть и другие методы.

1.2. Векторные полигональные модели

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

Рис. Базовые элементы векторно-полигональной модели

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

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

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

1.3. Сеточные модели

Эти модели описывают координаты отдельных точек поверхности следующим спо­собом. Каждому узлу сетки с индексами приписывается значение высоты , а индексам отвечают определенные значения плановых координат отде­льных точек объекта. Расстояние между соседними узлами сетки вдоль оси равно , а вдоль оси равно . На рис. представлена равномерная сеточная модель рельефа, для которой шаги и . имеют постоянные значения независимо от места расположения узлов сетки. Значения и назовем шагом сетки, а саму мо­дель - шаговой моделью поверхности рельефа (ШМР).

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

С помощью ШМР в декартовой системе координат может быть описана только поверхность, для которой каждому значению плановых координат , соответствует только одно значение высоты . Следовательно, даже поверхность в декартовой системе координат не может быть описана ШМР. Однако для описания поверхности можно использовать полярные координаты, в этом случае, на­пример, поверхности второго порядка могут быть также описаны ШМР.

Рис. Равномерная сеточная модель

1.4. Алгоритмы триангуляции

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

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

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

способа триангуляции;

- для набора из >3 точек, из которых являются внутренними точками (т. е. находятся внутри выпуклой оболочки, построенной по внешним точ­кам), и условия, что неколлинеарных точек не может быть менее трех, число образуемых треугольников в результате триангуляции будет равно + + 2. Имеется ряд алгоритмов машинной триангуляции: выпуклое обминание, три­ангуляция с минимальным краем, «жадная» триангуляция и т. д. В настоящее вре­мя в практических приложениях наиболее широко используется триангуляция Делоне.