Список примеров

Разбиение 3D-объекта на многогранники Вороного

Содержание

• Постановка задачи
• Разбиение Вороного методом обхода граней
• Код разбиения 3D-объекта
• Источники

Постановка задачи

Приводится код разбиения 3D-объекта на части, основанный на методе построения многогранников Вороного посредством обхода граней.
Разбиение Вороного конечного множества точек (атомов) S пространства – это такое разбиение, при котором каждая область этого разбиения образует множество точек, более близких к одному из атомов множества S, чем к любому другому атому этого множества. Результатом разбиения являются многогранники Вороного.
Можно сказать, что многогранник Вороного – это область пространства, находящаяся ближе к одному из атомов, чем к остальным [1].
Рассматривается задача разбиения пространства, ограниченного поверхностью 3D-объекта, на n частей.
Для получения разбиения внутри объекта задаются, например случайным образом, n точек (атомов). Далее используются идеи метода получения многогранника Вороного посредством обхода граней.
В случае пространства, ограниченного поверхностью 3D-объекта, результатом разбиения являются части объекта. Это либо части, ограниченные куском поверхности объекта и плоскостями разбиения, либо многогранник Вороного, образованный плоскостями разбиения. Пример такого разбиения сферы по 12 случайно заданным атомам приведен на рис. 1.

Рис. 1. Сфера, поделенная на 12 частей

Для задания массива атомов arrTms использован следующий код:

-- Радиус сферы
r = 50.0
nTms = 12
-- Массив атомов, по которым строятся многогранники Вороного
arrTms = #()
kr = 0.8 * r
-- Затравка датчика случайных чисел
seed 1.0
for k = 1 to nTms do (
 x = random -kr kr
 y = random -kr kr
 z = random -kr kr
 append arrTms [x, y, z]
)

Неизменная затравка датчика случайных чисел обеспечивает при каждом запуске и постоянном числе атомов один и тот же результат.
Все атомы находятся внутри сферы с радиусом 0.8 * r, где r – это радиус разбиваемой на части сферы.
В качестве объекта разбиения может быть использован и иной 3D-объект. В этом случае для генерации атомов разбиения можно употребить конструктор системы частиц Particle Cloud (облако частиц), подав ему в качестве эмиттера ссылку ob на разбиваемый объект, например:

nTms = 12
ob = teapot radius:40
-- Object-base formation (formation:3)
-- Use Total (quantityMethod:1)
-- Необходимо для последующего формирования массива атомов задать viewPercent:100
pCld = pCloud emitter:ob formation:3 quantityMethod:1 \
 total_number:nTms viewPercent:100 pos:ob.Pos isHidden:true
-- Заносим координаты частиц в массив атомов
arrTms = for i = 1 to nTms collect (particlePos pCld i)

Разбиение Вороного методом обхода граней

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

A_ix + B_iy + C_iz – D_i = 0 (i = 1, 2, 3).

Где x, y, и z – это координаты искомой точки, а коэффициенты A_i, B_i, C_i и D_i задают три плоскости Вороного между центральным атомом i₀, для которого строится многогранник Вороного, и тремя текущими атомами из его окружения. Через координаты атомов коэффициенты выражаются следующим образом:

A_i = (x₀ – x_i) / 2,
B_i = (y₀ – y_i) / 2,
C_i = (z₀ – z_i) / 2,
D_i = A_i² + B_i² + C_i².

Перед началом расчета составляется список ближайших соседей атома, из которых будут определяться геометрические соседи. Количество соседей в списке должно несколько превышать максимально возможное число граней многогранников Вороного. Список сортируется по возрастанию расстояния от центрального атома.
Алгоритм (приведен в [1]).

1. Найти первую грань многогранника Вороного атома i₀. Перебирая все атомы системы, находим атом i₁, ближайший к i₀. Плоскость P₁ Вороного этих атомов является образующей плоскостью (дает ненулевую грань многогранника Вороного атома i₀). Плоскость перпендикулярна отрезку, соединяющему атомы i₀ и i₁, и проходит через его центр. Точка p пересечения плоскости P₁ с отрезком, соединяющим i₀ и i₁ (рис. 2), принадлежит грани многогранника Вороного.
   

   Рис. 2. Начало поиска первой грани многогранника атома i₀

2. Перебирая всех оставшихся соседей, находим атом i₂, плоскость Вороного P₂ которого пересекает плоскость P₁ по линии P₁P₂, ближайшей к уже известной точке p (рис. 3).
   

   Рис. 3. Найдена первая грань многогранника атома i₀

3. Находим атомы i₃ и i_e, плоскости Вороного P₃ и P_e которых пересекают линию P₁P₂ в точках V₁ и V_e, ближайших к точке q (рис. 4), где q – это основание перпендикуляра из точки p к линии P₁P₂.
   

   Рис. 4. Найдены две вершины V₁ и V_e первой грани многогранника атома i₀

   Точки V₁ и V_e являются вершинами искомого многогранника.
4. Перебирая оставшихся соседей, находим атом i₄, плоскость Вороного P₄ которого пересекает прямую P₁P₃ в точке V₂, ближайшей к вершине и V₁ (рис. 5).
   

   Рис. 5. Найдена очередная вершина первой грани многогранника атома i₀

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

Первая грань многогранника Вороного атома i₀ найдена. Кроме того, известны атомы, дающие смежные с ней грани.
Для нахождения последующих граней используем, что каждый выявленный при обходе атом дает свою ненулевую грань искомого многогранника атома i₀. Для каждой из них имеется информация, позволяющая начать построение грани. Так, плоскость P₄ содержит вершины V₂ и V₃, определяющие ребро на линии P₁P₄, проходящей в этой плоскости, а также линий P₄P₃ и P₄P₅ (см. рис. 5). Начав обход с одной из этих вершин, следуя процедуре шага 4, мы придем к другой вершине, определив тем самым грань на плоскости P₄. При обходе этой грани выявятся новые атомы, дающие очередные грани на искомом многограннике. Исчерпав все плоскости, мы получим искомый многогранник Вороного.

Код разбиения 3D-объекта

Опираясь на приведенный выше метод обхода граней, используем следующую схему разбиения объекта (приводится схема построения одного куска):

1. Создать массив arrTms атомов разбиения (содержит координаты атомов, число атомов равно nTms).
2. Взять любой атом tm и сформировать массив arrNdx номеров прочих атомов, упорядочив их в этом массиве по возрастанию расстояния до атома tm (номер атома – это его индекс в массиве arrTms).
3. Создать объект prt для будущего куска, взяв для него меш разбиваемого объекта.
4. i = 1.
5. Взять в массиве arrNdx атом iTm = arrNdx[i] и провести плоскость Вороного атомов tm и iTm (плоскость перпендикулярна отрезку, соединяющему атомы, и проходит через его центр) и разбить этой плоскостью prt на две части. Оставить в качестве результата нижнюю часть разбиения. Для разбиения употребить модификатор SliceModifier, задав Slice_Type = 2 (Remove Top, удалить верхнюю часть разбиения).
6. i = i + 1. Если i < nTms – 1 , тогда повторить п. 5.

В результате выполнения приведенного алгоритма получается одна часть разбиения (рис. 6).

Рис. 6. Исходная сфера и первая часть разбиения

Затем этот алгоритм применяется для других атомов, что и дает искомое разбиение 3D-объекта.
Далее следует код, использующий вышеприведенный алгоритм:

fn compareFN v1 v2 coordArr: atmPs: = (
 p1 = coordArr[v1] - atmPs
 p2 = coordArr[v2] - atmPs
 d = (length p1) - (length p2)
 case of (
  (d < 0.): -1
  (d > 0.): 1
  default: 0
 )
)
fn mkArrNdx tm nTms arrTms = (
 -- Формируем и сортируем массив атомов в порядке возрастания их расстояния от атома tm
 arrNdx = for i = 1 to nTms collect i
 qsort arrNdx compareFN coordArr:arrTms atmPs:arrTms[tm]
 -- Первым элементом массива будет сам атом tm, поэтому он удаляется
 deleteItem arrNdx 1
 return arrNdx
)
delete $*
max tool zoomExtents
-- Радиус сферы
r = 50.0
nTms = 12
-- Массив атомов, по которым строятся многогранники Вороного
arrTms = #()
kr = 0.8 * r
-- Затравка датчика случайных чисел
seed 1.0
for k = 1 to nTms do (
 x = random -kr kr
 y = random -kr kr
 z = random -kr kr
 append arrTms [x, y, z]
)
-- Разбиваемый объект
sph = sphere radius:r segments:32
-- Плоскость для построения плоскости Вороного
dvPln = plane isHidden:true
-- Массив частей разбиения
prtS = #()
-- Рабочие модификаторы
xF = XForm()
mSlice = sliceModifier slice_type:2
for tm = 1 to nTms do (
 -- Координаты атома tm
 atmPs = arrTms[tm]
 -- Создаем меш для будущего куска
 prt = editable_mesh pos:atmPs
 prt.Mesh = sph.Mesh
 addModifier prt xF
 prt.XForm.Gizmo.Pos = sph.Pos - atmPs
 -- Формируем и сортируем массив прочих атомов
 -- в порядке возрастания их расстояния от атома tm
 arrNdx = mkArrNdx tm nTms arrTms
 dn = true
 for i = 1 to nTms - 1 do (
  iTm = arrNdx[i]
  vc = arrTms[iTm] - atmPs
  -- Плоскость перпендикулярна отрезку, соединяющему атомы
  dvPln.Dir = vc
  mSlice.Slice_plane.Rotation = dvPln.Rotation
  mSlice.Slice_plane.Pos = vc / 2
  -- Число граней в текущей части объекта до применения модификатора sliceModifier
  fc = prt.Faces.Count
  addModifier prt mSlice
  fc2 = prt.Faces.Count
  if fc2 == 0 do (
   -- Плоскость находится ниже текущей части объекта
   dn = false
   exit
  )
  if fc2 != fc do addModifier prt (cap_holes())
  collapseStack prt
 )
 if dn then
  append prtS prt
 else
  append prtS undefined
)
delete #(dvPln, sph)
-- Раздвигаем и затем возвращаем на место полученные части объекта
animate on
 for k = 1 to nTms do (
  prt = prtS[k]
  if prt != undefined do (
   atmPs = arrTms[k]
   dst = 3 * sqrt (atmPs[1]^2 + atmPs[2]^2 + atmPs[3]^2)
   dx = if atmPs[1] >= 0 then dst else -dst
   dy = if atmPs[2] >= 0 then dst else -dst
   dz = if atmPs[3] >= 0 then dst else -dst
   at time 50 move prt [dx, dy, dz]
   at time 100 move prt [-dx, -dy, -dz]
  )
 )
playAnimation()

Источники

1. Медведев Н. Н. Метод Вороного-Делоне в исследовании структуры некристаллических систем. – Новосибирск: Российская Академия Наук, Сибирское Отделение, 2000. – 214 c.

Список примеров