Метод Ньюэлла для вычисления плоского уравнения вогнутого многоугольника - улучшения?

Question

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

Есть ли какие-либо улучшения в методе Ньюэлла, которые помогают в выборе правильной отправной точки? Или есть альтернативный алгоритм, который не имеет этой проблемы?

Answer 1

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

Answer 2

Только что натолкнулся на это после некоторого поиска в Google для алгоритма Плоскости Ньюэлла. Я также заинтересован в использовании алгоритма, но мое чтение различной литературы заставляет меня думать, что это метод «трех точек», который терпит неудачу в случае вогнутого угла, тогда как метод Ньюэлла будет работать правильно. Вот соответствующий отрывок:

Эта методика, впервые предложенная Ньюэллом (Сазерленд и др. , 1974), работает для вогнутых многоугольников и многоугольников, содержащих коллинеарные вершины, а также для неплоских многоугольников, например многоугольников, полученных в результате расположение возмущенных вершин ...

---

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

1. Три точки однозначно определяют плоскость тогда и только тогда, когда они не коллинеарны; и

2. если три точки выбраны вокруг «вогнутого» угла, нормальное результирующей плоскости будет указывать в направлении, противоположном ожидаемый.

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

Источник: Филиппо Тампиери. «Метод Ньюэлла для вычисления плоского уравнения многоугольника». In Graphics Gems III, Academic Press, 1992, pp. 231–232.