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

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

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

Это алгоритм «разделяй и властвуй» с временем выполнения, равным $O\; (np)\; \{\backslash \; displaystyle\; O\; (np)\}$, где n - количество многоугольников, а p - количество пикселей в области просмотра.

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

• Краткое описание алгоритма Варнока

.