Алгоритм 3D пересечения треугольников - Отображение верхней плоскости

Question

Я пытаюсь вычислить самое верхнее пересечение произвольного числа плоскостей, без радости! Я использую Actionscript, но мне просто нужно найти алгоритм, который я могу реализовать.

Проблема:

• рассмотрим 3 вертикальные оси.
• Пользователь вводит 3 точки для каждого треугольника / плоскости так, чтобы точки треугольника лежали на одной из осей.
• Пользователь может ввести произвольное количество треугольников
• Мне нужно найти самый верхний слой этих треугольников и отобразить его на экране, а также координаты взаимодействия.

Вот картинка, поясняющая, что я имею в виду с двумя треугольниками:

Однако, когда мы допускаем более 2 треугольников, я получаю неловкие линии пересечения.

Answer 1

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

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

Я не знаю ActionScript, но быстрый поиск в Интернете по «выпуклым оболочкам, пересекающим плоскости», и такие термины привели меня к этому коду, который (подразумевает) решит вашу проблему:

http://nauful.com/pages/convexhull.html

Надеюсь, это поможет, Гленн

Answer 2

Меня очень интересует ваша проблема, поэтому я описал алгоритм и реализовал его на C ++ (я не знаю AS так хорошо, как C ++).Основная идея алгоритма - итеративный пересчет верхней поверхности при добавлении новых треугольников.

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

Давайте думать о верхней поверхности как о наборе многоугольников.Пока добавляется новый многоугольник, мы должны итеративно пересчитать грани всех многоугольников поверхности.Алгоритм пересчета граней включает в себя следующие шаги:

1. Найти две точки на краю многоугольника и лежащие на линии перехвата многоугольника.Эти точки должны стать новыми вершинами рассматриваемого многоугольника после удаления его покрытых частей.Каждая из этих точек может быть рассчитана как пересечение трех плоскостей: рассматриваемая плоскость многоугольника, новая плоскость многоугольника, одна из рассматриваемых граней многоугольника.Точки, находящиеся не на краю многоугольника, не должны учитываться.
2. Если имеется меньше двух точек перехвата, один из полигонов полностью перекрывает другой.Таким образом, мы должны определить верхний.Рассмотрим любую точку текущего многоугольника, не лежащую на линии перехвата многоугольника.Мы могли бы взять его координаты x и y, вычислить точку внутри новой плоскости многоугольника и сравнить их координаты z.
3. Если есть две точки, набор граней полигона следует изменить.После вычисления точки мы также знаем индексы пересеченных граней.Принимая во внимание точку внутри диапазона индекса, можно определить удаляемую часть граней.
4. Удалите перекрывающиеся грани из многоугольника и вставьте в многоугольник грани, рассчитанные на основе точек перехвата.

Чтобы не заливать эту страницу, я поместил код в pastebin .

Answer 3

Вы можете посмотреть на это как поле высоты на треугольнике B=[(0,0),(0,1),(1,0)].

Поскольку плоскость определяется как высота по углам B, высоту плоскости по внутренней точке B можно рассчитать с помощью барицентрических координат. С учетом:

• самолет с высотой (a,b,c) по углам B
• точка P в B с барицентрическими координатами (x,y,z) [x+y+z=1, x,y,z>=0],

высота плоскости в точке P равна x*a + y*b + z*c.

Естественные барицентрические координаты для точки P=(x,y) в B равны (x,y,1-x-y).

При этом легко вычислить линию пересечения двух плоскостей (a1,b1,c1) и (a2,b2,c2) в барицентрических координатах. Просто выровняйте, где 2 плоскости имеют одинаковую высоту

x*a1 + y*b1 + (1-x-y)*c1 = x*a2 + y*b2 + (1-x-y)*c2
=>
x*(a1-c1-(a2-c2)) + y*(b1-c1-(b2-c2)) + c1-c2 = 0

При 0 <= x,y <= 1 и x+y <= 1, 2 плоскостях это уравнение линии пересечения 2 плоскостей в B.

Я думаю, что есть 2 подхода, которые можно использовать для создания результирующего поля высоты (самый верхний слой):

Итеративное добавление нового треугольника

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

Распространение линии фронта пересечения

1. Начните с одного угла и возьмите плоскость, которая является самой высокой на нем (например, плоскость с максимумом (a_i)). Установите переднюю линию в этот угол.
2. Найдите плоскости, которые пересекают начальную плоскость с линиями пересечения, ближайшими к фронту. Переместите фронт к этим линиям пересечения.
3. Возьмите одну (любую) плоскость, которая находится на линии фронта, и сделайте пересечение с необработанными плоскостями с линиями пересечения, ближайшими к фронту. Переместите фронт к этим линиям пересечения.

Повторяйте 3. пока передняя линия не закроет треугольник B.

Я предпочитаю второй алгоритм.

Answer 4

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