Алгоритм Ньюэлла — это процедура трехмерной компьютерной графики для устранения полигональных циклов в сортировке глубины, необходимой при удалении скрытых поверхностей . Он был предложен в 1972 году братьями Мартином Ньюэллом и Диком Ньюэллом , а также Томом Санча, когда все трое работали в CADCentre .
На этапе сортировки глубины удаления скрытых поверхностей, если два полигона не имеют перекрывающихся экстентов или экстремальных минимальных и максимальных значений в направлениях x, y и z, то их можно легко отсортировать. Если два полигона, Q и P , имеют перекрывающиеся экстенты в направлении Z, то возможно, что необходимо сокращение.
В этом случае алгоритм Ньюэлла проверяет следующее:
Тесты даны в порядке возрастания вычислительной сложности. Полигоны должны быть плоскими . Если все тесты ложны, то поменяйте порядок P и Q в сортировке, запишите, что сделали это, и попробуйте снова. Если есть попытка поменять порядок полигона во второй раз, есть цикл видимости, и полигоны должны быть разделены. Разделение выполняется путем выбора одного полигона и разрезания его по линии пересечения с другим полигоном. Вышеуказанные тесты снова выполняются, и алгоритм продолжается до тех пор, пока все полигоны не пройдут вышеуказанные тесты.