WikiDer > Алгоритм Варнока

Warnock algorithm
Видимость многоугольника в заданном окне просмотра: a) многоугольник заполняет область просмотра, b) многоугольник частично и c) полностью видим, d) многоугольник невидим.
Четыре шага разделения окна просмотра для простой сцены

В Алгоритм Варнока это алгоритм скрытой поверхности изобретен Джон Варнок который обычно используется в области компьютерная графика.[1] Он решает проблему рендеринга сложного изображения путем рекурсивного разделения сцены до тех пор, пока не будут получены области, которые легко вычислить. Другими словами, если сцена достаточно проста для эффективных вычислений, она визуализируется; в противном случае он делится на более мелкие части, которые также проверяются на простоту.[2]

Это разделяй и властвуй алгоритм с участием время выполнения из , где п количество многоугольников и п количество пикселей в области просмотра.

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

использованная литература

  1. ^ Варнок, Джон (1969). «Алгоритм скрытой поверхности для компьютерных полутоновых изображений». Университет Юты. Алгоритм был докторской диссертацией Уорнока., 32 стр.
    Также: http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD753671&Location=U2&doc=GetTRDoc.pdf
  2. ^ Дейнтит, Джон; Райт, Эдмунд (2009). Оксфордский словарь по вычислительной технике. Издательство Оксфордского университета. ISBN 978-0-19-923400-4., 608 стр.

внешние ссылки