Как разбить многогранник на тетраэдры в MATLAB? - PullRequest
Новая
       45

Как разбить многогранник на тетраэдры в MATLAB?

3 голосов
/ 03 декабря 2009

У меня есть многогранник со списком вершин (v) и поверхностей (s). Как разбить этот многогранник на серию тетраэдров?

Мне бы особенно хотелось узнать, есть ли для этого какие-либо встроенные команды MATLAB.

Ответы [ 3 ]

3 голосов
/ 03 декабря 2009

Я не уверен, что ОП хотел «меш» (добавлены точки Штейнера) или тетраэдризацию (разбиение на тетраэдры, без точек Штейнера). для выпуклого многогранника добавление точек Штейнера (например, «центральной» точки) не требуется.

Переполнение стека не позволит мне прокомментировать сообщение gnovice (WTF, SO?), Но доказательство утверждения «поверхности выпуклого многогранника являются ограничениями в тесселяции Делоне» довольно простое: по определению, симплекс или subsimplex является членом тесселяции Делоне тогда и только тогда, когда существует n-сфера, описывающая симплекс, который строго не содержит точек в наборе точек. для поверхностного треугольника постройте наименьшую описывающую сферу и «надуйте» ее наружу, от многогранника, к «бесконечности»; в конечном итоге это не будет содержать никакой другой точки. (На самом деле предел описывающей сферы - это полупространство; таким образом, выпуклая оболочка всегда является подмножеством тесселяции Делоне.)

подробнее о DT см. Okabe, et. al, 'Пространственные тесселяции' , или любая из работ Shewchuk

(мой тезис был на эту тему, но я помню об этом меньше, чем должен был ...)

3 голосов
/ 03 декабря 2009

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

Если у вас нет треугольной сетки, то сначала вы должны триангулировать. Триангуляция Делоне может помочь.

Если есть дыры или пещеры, это может быть сколь угодно сложным.

2 голосов
/ 03 декабря 2009

Я бы предложил попробовать встроенную функцию DELAUNAY3 . Пример, приведенный в ссылке на документацию, напоминает ответ Аарона в том смысле, что он использует вершины плюс центральную точку многогранника для создания трехмерной тесселяции Делоне, но shabbychef указывает, что вы все еще может создать тесселяцию, не включая лишнюю точку. Затем вы можете использовать TETRAMESH для визуализации результирующих тетраэдрических элементов.

Ваш код может выглядеть примерно так (при условии, что v - это N-на-3 матрица значений координат вершины): 

v = [v; mean(v)];  %# Add an additional center point, if desired (this code
                   %#   adds the mean of the vertices)
Tes = delaunay3(v(:,1),v(:,2),v(:,3));  %# Create the triangulation
tetramesh(Tes,v);                       %# Plot the tetrahedrons

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

ПРИМЕЧАНИЕ: Согласно документации, DELAUNAY3 будет удален в будущем выпуске, а DelaunayTri эффективно займет свое место (хотя в настоящее время кажется, что определение ограниченных ребер все еще ограничено только двумерные триангуляции). Для полноты картины вы можете использовать DelaunayTri и визуализировать выпуклую оболочку (т.е. многогранную поверхность): 

DT = DelaunayTri(v);  %# Using the same variable v as above
tetramesh(DT);        %# Plot the tetrahedrons
figure;               %# Make new figure window
ch = convexHull(DT);  %# Get the convex hull
trisurf(ch,v(:,1),v(:,2),v(:,3),'FaceColor','cyan');  %# Plot the convex hull
...