Алгоритм Уорнока — это алгоритм скрытой поверхности, изобретенный Джоном Уорноком , который обычно используется в области компьютерной графики . [1] Он решает проблему рендеринга сложного изображения путем рекурсивного подразделения сцены до тех пор, пока не будут получены области, которые легко вычислить. Другими словами, если сцена достаточно проста для эффективного вычисления, то она визуализируется; в противном случае она делится на более мелкие части, которые также проверяются на простоту. [2]
Это алгоритм «разделяй и властвуй» со временем выполнения [ dubious – discussion ] , где n — количество полигонов, а p — количество пикселей в области просмотра.
Входные данные — список полигонов и область просмотра. Лучший вариант — если список полигонов простой, то полигоны рисуются в области просмотра. Простой определяется как один полигон (тогда полигон или его часть рисуется в соответствующей части области просмотра) или область просмотра размером в один пиксель (тогда этот пиксель получает цвет полигона, ближайшего к наблюдателю). Непрерывный шаг — разделить область просмотра на 4 квадранта одинакового размера и рекурсивно вызвать алгоритм для каждого квадранта, при этом список полигонов изменяется таким образом, чтобы он содержал только полигоны, видимые в этом квадранте.
Уорнок выразил свой алгоритм словами и картинками, а не программным кодом, как основу своей докторской диссертации, в которой также были описаны протоколы для затенения наклонных поверхностей и других функций, которые теперь являются основой трехмерной компьютерной графики. Вся диссертация была всего в 26 страницах из Введения в библиографию.
Алгоритм был докторской диссертацией Уорнока., 32 страницы
