Вычислительная геометрия, объем тетраэдра со знаком

Question

Я не уверен, что это правильное место, чтобы спросить, но здесь идет ...

Короткая версия: Я пытаюсь вычислить ориентацию треугольника на плоскости, образованной пересечением 3 ребер, без явного вычисления точек пересечения.

Длинная версия: Мне нужно триангулировать PSLG по треугольнику в 3D. Вершины PSLG определяются пересечениями отрезков с плоскостью, проходящей через треугольник, и гарантированно лежат внутри треугольника. Предполагая, что у меня есть точки пересечения, я могу проецировать в 2D и использовать тест на стороне линии точки (или области со знаком треугольника), чтобы определить ориентацию треугольника между любыми 3 точками пересечения.

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

Так как я не могу явно вычислить точки пересечения, мне интересно, есть ли способ выразить то же самое вычисление 2D-ориентации в 3D, используя только исходные точки. Если есть три ребра, ударяющие по треугольнику, это дает мне 9 очков для игры. Предполагая, что то, что я спрашиваю, даже возможно (используя только трехмерные ориентирующие тесты), тогда я предполагаю, что мне нужно сформировать некоторое подмножество всех возможных тетраэдров между этими 9 точками. Мне трудно даже визуализировать это, не говоря уже о том, чтобы перевести его в формулу или код. Я даже не могу найти это в Google, потому что я не знаю, какой может быть стандартная терминология отрасли для такого рода проблем.

Есть идеи, как поступить с этим? Благодарю. Возможно, мне стоит спросить и MathOverflow ...

РЕДАКТИРОВАТЬ: После прочтения некоторых комментариев, одна вещь, которая приходит мне в голову ... Возможно, если бы я мог поместить непересекающиеся тетраэдры между 3 отрезками линии, то ориентация любого из тех, которые пересекли плоскость будет ответ, который я ищу. Кроме случаев, когда края окружают простую треугольную призму, я не уверен, что эта подзадача также разрешима.

РЕДАКТИРОВАТЬ: Запрошенное изображение.

Answer 1

Я отвечаю на это как по МО, так и по расширению комментариев, которые я сделал к МО.

Мне кажется, что никакой вычислительный прием с подписанными томами тетраэдров не избежит проблем точности, которые являются вашей главной задачей.Это потому, что, если у вас есть сильно скрученные сегменты, ориентация треугольника зависит от точного положения плоскости резания.
[изображение удалено;см. ниже]
В приведенном выше примере верхняя плоскость пересекает сегменты в следующем порядке ( a, b, c ) [ccw сверху]: ( красный, синий, зеленый ), а нижняя плоскость пересекается в обратном порядке ( c, b, a ): ( зеленый, синий, красный ).Высота плоскости резания может быть определена вашей последней точностью.

Следовательно, я думаю, что имеет смысл просто пойти дальше и вычислить точки пересечения в плоскости резания, используя достаточную точность, чтобы сделатьТочный расчет.Если координаты конечных точек вашего сегмента и плоские коэффициенты имеют L бит точности, то требуется лишь небольшое увеличение постоянного коэффициента.Хотя я не уверен точно, что это за фактор, он небольшой - возможно, 4. Вам не понадобится, например, L ² бит, потому что вычисления решают линейные уравнения.Так что не будет взрыва в точности, необходимой для точного вычисления.

Удачи!

(Мне не дали опубликовать разъясняющее изображение, потому что у меня нет репутации. См. МО ответ вместо.)

Редактировать : Вы видите ответ МО, но вот изображение:

Answer 2

Насколько я понимаю, у вас есть три линии, пересекающие плоскость, и вы хотите вычислить ориентацию треугольника, образованного точками пересечения, без вычисления самих точек пересечения?

Если так: у вас есть самолет

N·(x - x<sub>0</sub>) = 0

и шесть очков ...

l<sub>1a</sub>, l<sub>1b</sub>, l<sub>2a</sub>, l<sub>2b</sub>, l<sub>3a</sub>, l<sub>3b</sub>

... образуя три линии

l<sub>1</sub> = l<sub>1a</sub> + t(l<sub>1b</sub> - l<sub>1a</sub>)
l<sub>2</sub> = l<sub>2a</sub> + u(l<sub>2b</sub> - l<sub>2a</sub>)
l<sub>3</sub> = l<sub>3a</sub> + v(l<sub>3b</sub> - l<sub>3a</sub>)

Точки пересечения этих линий с плоскостью возникают при определенных значениях t, u, v, которые я назову t _i , u _i , v _я

N·(l<sub>1a</sub> + t<sub>i</sub>(l<sub>1b</sub> - l<sub>1a</sub>) - x<sub>0</sub>) = 0

      N·(x<sub>0</sub> - l<sub>1a</sub>)
t<sub>i</sub> =  ----------------
      N·(l<sub>1b</sub> - l<sub>1a</sub>)
(similarly for u<sub>i</sub>, v<sub>i</sub>)

Тогда конкретные точки пересечения

intersect<sub>1</sub> = l<sub>1a</sub> + t<sub>i</sub>(l<sub>1b</sub> - l<sub>1a</sub>)
intersect<sub>2</sub> = l<sub>2a</sub> + u<sub>i</sub>(l<sub>2b</sub> - l<sub>2a</sub>)
intersect<sub>3</sub> = l<sub>3a</sub> + v<sub>i</sub>(l<sub>3b</sub> - l<sub>3a</sub>)

Наконец, ориентация вашего треугольника

orientation = direction of (intersect<sub>2</sub> - intersect<sub>1</sub>)x(intersect<sub>3</sub> - intersect<sub>1</sub>)

(x является перекрестным произведением) Работайте задним числом, вставляя значения, и вы получите уравнение ориентации, основанное только на N, x ₀ и ваших шести точках.

Answer 3

Давайте назовем ваши треугольные вершины T[0], T[1], T[2], и конечные точки первого отрезка будут L[0] и L[1], вторая - L[2] и L[3], а третья L[4] и L[5]. Я полагаю, вы хотите функцию

int Orient(Pt3 T[3], Pt3 L[6]); // index L by L[2*i+j], i=0..2, j=0..1

, который возвращает 1, если пересечения имеют ту же ориентацию, что и треугольник, и -1 в противном случае. Результат должен быть симметричным при обмене j значениями, антисимметричным при обмене i значениями и T индексами. Пока вы можете вычислить величину с этими симметриями, это все, что вам нужно.

Давайте попробуем

Sign(Product( Orient3D(T[i],T[i+1],L[2*i+0],L[2*i+1]) * -Orient3D(T[i],T[i+1],L[2*i+1],L[2*i+0]) ), i=0..2))

, где произведение должно быть взято по циклическим перестановкам индексов (по модулю 3). Я считаю, что это имеет все необходимые свойства симметрии. Orient3D - это 4-точечный тест ориентации плоскости Шевчука, который, я полагаю, вы используете.

Answer 4

Я бы написал символические векторные уравнения, вы знаете, с точечными и перекрестными произведениями, чтобы найти нормаль треугольника пересечения.Тогда знак точечного произведения этой нормали с начальным треугольником дает ориентацию.Наконец, вы можете выразить это в виде формы (F (p1, ..., p9)), где p1 - p9 - ваши точки, а F () - уродливая формула, включающая точечные и перекрестные произведения разностей (pi-pj),Не знаю, можно ли сделать это проще, но этот общий подход делает свою работу.