схеме: рассматривается каждая грань сформированного тетраэдра и
если эта грань является гранью фронта, то она удаляется из фронта;
если же эта грань не является гранью фронта, она добавляется в него.
6. Если остались еще не удаленные точки
F
или (что эквивалентно)
фронт не пуст (т.е. область еще не исчерпана полностью), осуществля-
ется переход к п. 1, иначе процесс окончен.
Таким образом, массив
F
используется сразу для нескольких це-
лей: для оценки телесного угла, для контроля правильности построе-
ния и размещения новых узлов. Также массив
F
удобно использовать
для индикации процесса выполнения. Отношение числа удаленных во
время работы алгоритма точек
F
к начальному числу существующих
точек
F
фактически показывает, какая часть области уже исчерпана.
Вернемся к вопросу нахождения координат нового узла для постро-
ения тетраэдра, поставленному в п. 4 описанного алгоритма. Пусть
заданы три узла:
g
1
, g
2
, g
3
.
1. На первом шаге необходимо найти
~r
c
— радиус-вектор барицен-
тра треугольника (как среднее арифметическое координат его узлов) и
единичную нормаль
~n
к плоскости грани (через нормированное век-
торное произведение).
2. Далее определяется первое приближение для расстояния от бари-
центра до искомой точки
p
:
H
= min(
H
1
, H
2
)
, где
H
1
определяется из
максимально допустимого объема тетраэдра:
H
1
= 3
V
max
/S
(заметим,
что площадь грани
S
фактически найдена на предыдущем шаге, ведь
результат векторного произведения двух ребер как раз равен удво-
енной площади грани), а
H
2
находится из принципа максимальной
приближенности формы тетраэдра к правильной:
H
2
=
√
S
.
3. Проверяется точка с радиус-вектором
~p
=
~r
c
+
~nH
, и если те-
траэдр
(
g
1
, g
2
, g
3
, p
)
удовлетворяет всем требованиям, переходят к п. 6,
иначе — к п. 4.
4. Проверяется точка
~p
=
~r
c
−
~nH
, и если тетраэдр
(
g
1
, g
2
, g
3
, p
)
удовлетворяет всем требованиям, переходят к п. 6, иначе — к п. 5.
5. Полагают
H
:= 0
,
75
H
и переходят к п. 3.
6. Искомый узел найден
3
.
Пример работы алгоритма.
Проиллюстрируем описанный алго-
ритм примером. Пусть требуется построить тетраэдрическую сетку
в области, представляющей собой куб, внутри которой расположено
включение в виде произвольно ориентированного куба меньшего раз-
мера (данная область моделирует ячейку композитного материала).
Возьмем размеры внешнего куба
8
×
8
×
8
, размеры внутреннего —
3
Заметим, что в 99% случаев искомая точка находится во время 1-й или 2-й
итерации данного алгоритма.
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2008. № 2
101
