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

Видимость полигона в заданном окне просмотра: а) полигон заполняет область просмотра, б) полигон частично и в) полностью виден, г) полигон невидим.

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

Это алгоритм «разделяй и властвуй» со временем выполнения $O(np)$ ^{[ сомнительно – обсудить ]}, где n — количество полигонов, а p — количество пикселей в области просмотра.

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

Уорнок выразил свой алгоритм в словах и изображениях, а не в программном коде, в качестве основы своей докторской диссертации, в которой также описывались протоколы затенения наклонных поверхностей и другие функции, которые сейчас являются основой трехмерной компьютерной графики. Вся диссертация занимала всего 26 страниц из «Введения в библиографию».

Ссылки

^ Уорнок, Джон (1969). «Алгоритм скрытой поверхности для компьютерных полутоновых изображений» . Университет Юты. Алгоритм был докторской диссертацией Уорнока. , 32 страницы
Также: http://www.codersnotes.com/notes/warnock-subdivision-for-deferred-lighting/warnock.pdf.
^ Дэйнтит, Джон; Райт, Эдмунд (2009). Оксфордский словарь вычислительной техники . Издательство Оксфордского университета. ISBN 978-0-19-923400-4 . , 608 страниц

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

Краткое изложение алгоритма Варнока

[1] Уорнок, Джон (1969). «Алгоритм скрытой поверхности для компьютерных полутоновых изображений» . Университет Юты. Алгоритм был докторской диссертацией Уорнока. , 32 страницы
Также: http://www.codersnotes.com/notes/warnock-subdivision-for-deferred-lighting/warnock.pdf.

[2] Дэйнтит, Джон; Райт, Эдмунд (2009). Оксфордский словарь вычислительной техники . Издательство Оксфордского университета. ISBN 978-0-19-923400-4 . , 608 страниц

[1]

[2]