Алгоритм сканирующей прямой Уоткинса. Алгоритм Варнока

Алгоритм сканирующей прямой Уоткинса

Данный алгоритм опериру­ет в экранной плоскости. Изображение представляет собой набор мно­гоугольников, являющихся ортогональными проекциями плоских  граней трехмерных объектов. Для решения поставленной задачи (удаления невидимых линий и поверхностей) сцена последовательно рассекается плоскостями, перпендикулярными экрану (в терминах проекции эти секущие плоскости представляют собой так называемые сканирующие прямые). Таким образом, сканирующие  прямые параллельны оси  X (гори­зонтальны). Все сканирующие прямые обрабатываются алгоритмом одним способом, сле­довательно, достаточно рассмотреть одну такую прямую.

Алгоритм Уо­ткинса состоит из двух основных частей: нахождения так  называемых пробных интервалов и определения видимости.

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

Пример 1.7. Многоугольникам, изображенным на рис.1.67, припи­сываются следующие отрезки сканирующей прямой (здесь s_ij – отрезок номер j i-го многоугольника, образованный пересечением Fi с задан­ной сканирующей прямой): F₁ приписаны s₁₁ и s₁₂; F₂ приписан  s₂₁; F₃ приписан s₃₁.

Следует отметить, что изолированные (не перекрывающиеся в плос­кости XY) отрезки видимы. Отрезки s₂₁ и s₃₁ перекрываются в  плос­кости XY. В этом случае необходимо сформировать пробные интервалы. Пробным интервалом будем  называть отрезок сканирующей  прямой, на котором видимость не изменяется. Для нахождения пробных интервалов необходимо рассмотреть проекции граней на плоскость XZ,  поскольку только такая проекция позволит выяснить взаимное расположение гра­ней в пространстве.

Пример  1.8. Рассмотрим  проекции  граней,  изображенных   на рис.1.68.

Здесь интервалы 1-8 являются пробными  интер­валами.  Таким образом,  пробный интервал – это  часть сканирующей прямой, для которой  справедливо:   число отрезков,   содержащих пробный  интервал, постоянно и строго больше 1; проекции на плоскость  XZ граней,  соответствующих этим  отрезкам, не  пересекаются. Дру­гими словами, внутри пробного интервала никакие два  ребра  проекций не пересекаются и никакие две грани  не проникают друг в друга в объектном пространстве.

Вопрос о том, какой  из сегментов проекций видим на  пробном интервале, разрешается с помощью следующего теста: видим тот сегмент, минимальная z-координата которого в