Алгоритм Ньюэлла

Алгоритм Ньюэлла — это процедура трехмерной компьютерной графики для устранения полигональных циклов при сортировке по глубине, необходимой при удалении скрытых поверхностей . Его предложили в 1972 году братья Мартин Ньюэлл и Дик Ньюэлл , а также Том Санча, когда все трое работали в CADCentre .

На этапе сортировки по глубине удаления скрытых поверхностей, если два многоугольника не имеют перекрывающихся экстентов или крайних минимальных и максимальных значений в направлениях x, y и z, их можно легко отсортировать. Если два полигона, Q и P , имеют перекрывающиеся границы в направлении Z, возможно, потребуется обрезка.

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

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

Проверка на перекрытие Z; подразумевается выбор грани Q из списка сортировки
Крайние значения координат по X двух граней не перекрываются ( минимаксный тест по X)
Крайние значения координат по Y двух граней не перекрываются (минимаксный тест по Y)
Все вершины P лежат глубже плоскости Q.
Все вершины Q лежат ближе к точке обзора, чем плоскость P.
Растеризация . P Q и не перекрываются

Тесты расположены в порядке возрастания вычислительной сложности. Многоугольники должны быть плоскими . Если все тесты неверны, поменяйте порядок P и Q в сортировке, запишите это и повторите попытку. Если происходит попытка переключить порядок полигона второй раз, происходит цикл видимости, и полигоны необходимо разбить. Разделение осуществляется путем выбора одного многоугольника и разрезания его по линии пересечения с другим многоугольником. Вышеуказанные тесты выполняются снова, и алгоритм продолжается до тех пор, пока все полигоны не пройдут вышеуказанные тесты.

Ссылки

Сазерленд, Иван Э .; Спроролл, Роберт Ф .; Шумакер, Роберт А. (1974), «Характеристика десяти алгоритмов скрытой поверхности», Computing Surveys , 6 (1): 1–55, CiteSeerX 10.1.1.132.8222 , doi : 10.1145/356625.356626 , S2CID 14222390 .
Ньюэлл, Мэн ; Ньюэлл, РД ; Санча, Т.Л. (1972), «Новый подход к проблеме затененного изображения», Proc. Национальная конференция ACM , стр. 443–450 .

См. также

Эта компьютерной графике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .