тетраэдра к наибольшему из произведений длин тройки ребер, выхо-
дящих из одного узла: чем это отношение больше, тем более тетраэдр
близок к правильному и тем лучше его аппроксимационные качества.
Алгоритм состоит из следующей последовательности действий:
1. Формируется множество узлов
G
, состоящее из вершин фрон-
та (т.е. изначально в него входят все существующие узлы сетки); для
каждого узла
G
проводится оценка телесного угла. Эта оценка сводит-
ся к нахождению числа существующих (т.е. не удаленных) точек
F
,
находящихся от данного узла на расстоянии не более, чем
√
2
h
(что
требует существенно меньших затрат ресурсов, чем прямое вычисле-
ние телесных углов).
2. Находится вершина
g
1
2
G
с наименьшим оценочным значе-
нием телесного угла и выбирается такая грань
(
g
1
, g
2
, g
3
)
фронта, для
которой сумма оценок телесных углов для
(
g
1
, g
2
, g
3
)
минимальна.
3. Формируется множество
G
1
узлов
G
, находящихся от каждой
из вершин выбранной грани на расстоянии не более чем
√
3
h
(это
множество может оказаться и пустым). Для каждого узла
g
4
2
G
1
рас-
сматривается тетраэдр
(
g
1
, g
2
, g
3
, g
4
)
, причем тетраэдр отбрасывается,
если не выполняется хотя бы одно из следующих условий:
— cтрого внутри этого тетраэдра нет ни одной удаленной точки
F
(существование таких точек на гранях допускается);
— внутри этого тетраэдра нет других существующих узлов сетки,
за исключением самих вершин этого тетраэдра;
— этот тетраэдр не пересекается никаким существующим ребром
сетки (считается, что тетраэдр пересекается ребром, не являющимся
ребром этого тетраэдра, если у него с этим ребром есть хотя бы одна
общая точка, не являющаяся вершиной этого тетраэдра)
2
;
— объем этого тетраэдра не больше максимально допустимого
V
max
.
Из всех тетраэдров
(
g
1
, g
2
, g
3
, g
4
)
выбирают тетраэдр наилучшего ка-
чества [1] и переходят к п. 5; если же тетраэдров, удовлетворяющих
указанным условиям, не оказалось, переходят к п. 4.
4. Находится точка
p
внутри еще не исчерпанной области, для ко-
торой тетраэдр
(
g
1
, g
2
, g
3
, p
)
удовлетворяет всем условиям, указанным
в п. 3 и в шаре
B
(
p,
2
h/n
)
нет ни одной удаленной точки
F
(это пре-
дотвращает размещение узла
p
слишком близко от граней и вершин
существующих тетраэдров). Вариант алгоритма поиска узла
p
рассмо-
трен ниже.
5. Удаляются все вершины
F
, попавшие внутрь (и на границы)
сформированного тетраэдра. Затем фронт обновляется по следующей
2
Может показаться, что из условия 3 следует условие 2, но на самом деле это не
так. Например, существующий тетраэдр может оказаться целиком внутри проверяе-
мого тетраэдра.
100
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2008. № 2
