Алгоритм разбиения области Варнока

Алгоритм работает в пространстве изображенияи анализирует область на экране дисплея (окно) на наличие в них видимых элементов. Если в окне нет изображения, то оно просто закрашивается фоном. Если же в окне имеется элемент, то проверяется достаточно ли он прост для визуализации. Если объект сложный, то окно разбивается на более мелкие, для каждого из которых выполняется тест на отсутствие и/или простоту изображения. Рекурсивный процесс разбиения может продолжаться до тех пор пока не будет достигнут предел разрешения экрана.

Можно выделить 4 случая взаимного расположения окна и многоугольника (рис.):

· многоугольник целиком вне окна,

· многоугольник целиком внутри окна,

· многоугольник пересекает окно,

· многоугольник охватывает окно.

Рис. 18: Соотношения между окном экрана (сплошная рамка) и многоугольником (штриховая рамка)

 

В четырех случаях можно сразу принять решение о правилах закраски области экрана:

· все многоугольники сцены - внешние по отношению к окну. В этом случае окно закрашивается фоном;

· имеется всего один внутренний или пересекающий многоугольник. В этом случае все окно закрашивается фоном и затем часть окна, соответствующая внутреннему или пересекающему окну закрашивается цветом многоугольника;

· имеется единственный охватывающий многоугольник. В этом случае окно закрашивается его цветом.

· имеется несколько различных многоугольников и хотя бы один из них охватывающий.