2.2.Выбор необходимых структур данных

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

Введем следующие обозначения:

S - вершины; s1,s2,... - отдельные вершины;

A - ребра; a1,a2,... - отдельные ребра;

F - грани; f1,f2,... - отдельные грани.

Количественная информация об объекте, как правило, задается координатами вершин (табл.2.1) - дескриптором вершин -S(X,Y,Z).

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

S(S) - наборы вершин, связанных с данной вершиной ребрами;

S(A) - наборы ребер, в состав которых входит данная вершина;

S(F) - наборы граней, в состав которых входит данная вершина;

A(S) - пары вершин, ограничивающих данное ребро;

A(A) - наборы ребер, имеющих общую вершину с данным ребром;

A(F) - пары граней, для которых данное ребро является общим;

F(S) - наборы вершин данной грани;

F(A) - наборы ребер данной грани;

F(F) - наборы граней, смежных с данной гранью.

Топологические отношения, определенные таким образом, будем называть неупорядоченными. Один из вариантов представления этих отношений для моделируемого объекта (рис.2.1) приведен в табл.2.2. В каждой из строк этой таблицы приведены три соответствующих топологических отношения. Например, вершина s5 представлена следующими отношениями:

s5(S) = {s6, s1, s2, s3}; s5(A) = {a3, a6, a9, a12}; s5(F) = {f2, f4, f6, f7};

Табл.2.2.Неупорядоченные топологические отношения для моделируемого объекта

S

S

A

F

s1

s2

s5

s4

a1

a6

a11

f1

f2

f6

s2

s1

s3

s7

s5

a1

a4

a7

a9

f1

f2

f3

f4

s3

s6

s2

s7

s5

a2

a4

a10

a12

f3

f4

f5

f7

s4

s7

s6

s1

a5

a8

a11

f1

f5

f6

s5

s6

s1

s2

s3

a3

a6

a9

a12

f2

f4

f6

f7

s6

s3

s5

s4

a2

a3

a8

f5

f6

f7

s7

s4

s2

s3

a5

a7

a10

f1

f3

f5

A

S

A

F

a1

s1

s2

a6

a11

a4

a7

a9

f1

f2

a2

s3

s6

a4

a10

a12

a3

a8

f5

f7

a3

s5

s6

a6

a9

12

a2

a8

f6

f7

a4

s2

s3

a1

a7

a9

a2

a10

a12

f3

f4

a5

s4

s7

a8

a11

a7

a10

f1

f5

a6

s1

s5

a1

a11

a3

a9

a12

f2

f6

a7

s2

s7

a1

a4

a9

a5

a10

f1

f3

a8

s4

s6

a5

a11

a2

a3

f5

f6

a9

s2

s5

a1

a4

a7

a3

a6

a12

f2

f4

a10

s3

s7

a2

a4

a12

a5

a7

f3

f5

a11

s1

s4

a1

a6

a5

a8

f1

f6

a12

s3

s5

a2

a4

a10

a3

a6

a9

f4

f7

F

S

A

F

f1

s1

s2

s4

s7

a1

a5

a7

a11

f2

f5

f3

f6

f2

s1

s2

s5

a1

a6

a9

f1

f6

f4

f3

s2

s3

s7

a4

a7

a10

f4

f1

f5

f4

s2

s3

s5

a4

a9

a12

f3

f2

f7

f5

s3

s4

s6

s7

a2

a5

a8

a10

f7

f1

f6

f3

f6

s1

s4

s5

s6

a3

a6

a8

a11

f7

f2

f5

f1

f7

s3

s5

s6

a2

a3

a12

f5

f6

f4

Неупорядоченные топологические отношения могут взаимно преобразовываться друг в друга согласно схеме, приведенной на рис.2.2. Например, из отношений s1(A) = {a1, a6, a11} и s2(A) = {a1, a4, a7, a9} следует, что a1(S) = {s1,s2}. Из тех же геометрических соображе­ний можно сделать вывод о том, что в двух отношениях si(A) и sj(A) для одной и той же модели не может быть больше одного повто­ряющегося ребра. Это может ис­пользоваться для проверки пра­вильности представления инфор­мации в модели в качестве одного из условий.

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

1-ый уровень - каркасные модели - модели, позволяющие определение длин ребер объекта.

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

3-ий уровень - твердотельные (объемные) модели - модели, позволяющие опреде­ление объема объекта.

Модель низшего уровня - каркасная, для обеспечения требуемого свойства должна включать информацию о ребрах, то есть топологическую информацию о том, какие вершины объекта соединены друг с другом. Это может быть обеспечено включением в структуру данных одного из неупорядоченных топологических отношений S(S) или A(S). Или же, согласно рис.2.2, в модели могут присутствовать отношения S(A), которые можно преобразовать либо в S(S), либо в A(S).

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

(2.1)

где - площадь проекции много­угольника на координатную плос­кость;

- угол между плоскостью многоугольника и координатной плоскостью, на которую он спроекти­рован.

При использовании плоскости XOY в качестве плоскости проециро­вания

(2.2)

где - направляющий косинус нормали плоскости многоугольника, определяемый как

(2.3)

где - проекции нормали на координатные оси.

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

(2.4)

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

Исходя из (2.4), проекции нормали составят

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

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

(2.6)

В выражении (2.6) площадь многоугольника берется по абсолютной величине, что позволяет использовать произвольное направление обхода вершин многоугольника. Следует также заметить, что при i=n, i должно принимать значение 1, а неn+1. То есть, набор вершин многоугольника, задаваемый, например, отношениемF(S),должен быть упорядочен в соответствии с одним из двух возможных направлений обхода и быть кольцевой структурой.