внутренних телесных углов. В то время как вычисление
планарных
и
двугранных
углов тривиально, вычисление
телесных
углов предста-
вляет собой куда более трудоемкую задачу (особенно если учесть, что
каждый телесный угол в данном случае может быть сформирован раз-
личным числом граней). Отметим, однако, что эту проблему можно
частично обойти, если на каждом этапе изымать не один тетраэдр,
а сразу целый слой. Недостатком этого варианта является довольно
существенное снижение качества тетраэдров [7].
Цель данной статьи — предложить достаточно простой и эффек-
тивный способ решения этих проблем. Предлагаемый метод основан
на использовании вспомогательного массива узлов и иллюстрируется
на примере разработанного алгоритма.
Вариант метода исчерпывания с использованием вспомога-
тельного массива узлов.
Рассмотрим вариант алгоритма исчерпыва-
ния с использованием вспомогательного массива узлов, предназначен-
ный для построения сеток, близких к равномерным, в произвольных
областях (предполагается, что граница области уже триангулирована).
Пусть необходимо построить сетку с желаемой средней длиной
ребра, равной
h
(эту величину часто называют шагом триангуля-
ции). В качестве исходных данных алгоритм требует два массива:
массив, описывающий триангуляцию границы (фактически, началь-
ный фронт, представляемый в виде списка треугольников-граней)
и массив вспомогательных точек
F
. Этот массив формируется так:
заданная область помещается в суперобласть (параллелепипед), кото-
рая равномерно заполняется вспомогательными точками
F
с шагом
h
F
=
h/n
,
n
= 10
. . .
15
(т.е. плотность их размещения должна быть
на порядок больше плотности размещения узлов триангуляции). От-
метим, что поскольку координаты этих узлов можно легко вычислять
(
r
ijk
= (
ih
F
, jh
F
, kh
F
)
), для этого массива не требуется большого
объема. Фактически, множество
F
будет описываться трехмерным
массивом однобитных булевых переменных (TRUE — точка суще-
ствует, FALSE — точка удалена). Таким образом, хранение восьми
миллионов элементов
F
потребует около одного мегабайта оператив-
ной памяти. После формирования множества
F
из него удаляются
все точки, лежащие вне заданной области. Оставшиеся точки будут
представлять своего рода объемное растровое изображение задан-
ной области. Именно с помощью множества
F
в этом алгоритме и
решаются проблемы, рассмотренные выше.
Введем контрольную величину
V
max
, обозначающую максималь-
но допустимый объем тетраэдра, и положим ее равной
0
,
15
h
3
(объем
правильного тетраэдра с ребром
h
плюс допуск 25%). Для оценки
аппроксимационных качеств будем использовать отношение объема
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2008. № 2
99