Введение
В компьютерной графике, отсечение линий – это процесс удаления (отсечения) линий или частей линий, находящихся за пределами области видимости (видового окна или объема видимости). Обычно, любая часть линии, выходящая за пределы области просмотра, удаляется. Существуют два распространенных алгоритма отсечения линий: Коэн — Сазерленд и Лян — Барски. Метод отсечения линий состоит из нескольких этапов. Для заданного отрезка линии проводятся проверки, чтобы определить, находится ли он за пределами области видимости или объема. Затем выполняются вычисления точек пересечения с одной или несколькими границами отсечения. Определение того, какая часть линии находится внутри, а какая – снаружи объема отсечения, осуществляется путем анализа конечных точек линии относительно этих пересечений.
In computer graphics, line clipping is the process of removing (clipping) lines or portions of lines outside an area of interest (a viewport or view volume). Typically, any part of a line which is outside of the viewing area is removed. There are two common algorithms for line clipping: Cohen–Sutherland and Liang–Barsky. A line clipping method consists of various parts. Tests are conducted on a given line segment to find out whether it lies outside the view area or volume. Then, intersection calculations are carried out with one or more clipping boundaries. Determining which portion of the line is inside or outside of the clipping volume is done by processing the endpoints of the line with regards to the intersection.
Коэн Сазерленд
В компьютерной графике алгоритм Коэна — Сазерленда (названный в честь Дэнни Коэна и Ивана Сазерленда) — это алгоритм отсечения линий. Алгоритм делит двумерное пространство на 9 областей, из которых видна только центральная область (область видимости). В 1967 году работа Дэнни Коэна в области авиасимуляции привела к разработке алгоритмов отсечения линий для двух- и трехмерной компьютерной графики, созданных совместно с Иваном Сазерлендом.
Лиан Барски
Алгоритм Лянга — Барски использует параметрическое уравнение прямой и неравенства, описывающие границы области отсечения, для определения точек пересечения прямой с этой областью. По этим точкам пересечения определяется, какая часть прямой должна быть отрисована. Этот алгоритм значительно эффективнее алгоритма Коэна — Сазерленда, однако алгоритм Коэна — Сазерленда гораздо быстрее определяет и отбрасывает тривиальные случаи, поэтому его следует рассмотреть, если большинство отсекаемых прямых полностью находятся внутри или снаружи области отсечения.
Сайрус Бек
Очень похож на алгоритм обрезки линий Лянга — Барски. Отличие заключается в том, что алгоритм Лянга — Барски является упрощенной версией алгоритма Сайруса — Бека, оптимизированной для прямоугольной области отсечения. Алгоритм Сайруса — Бека предназначен главным образом для отсечения линии, заданной в параметрической форме, относительно выпуклого многоугольника в двух измерениях или выпуклого многогранника в трех измерениях.
Николл Ли Николл
Алгоритм Nicholl–Lee–Nicholl — это быстрый алгоритм обрезки линий, который снижает вероятность многократной обрезки одного и того же сегмента линии, что может происходить в алгоритме Cohen–Sutherland. Окно обрезки разделяется на несколько различных областей в зависимости от положения начальной точки обрезаемой линии.
Быстрая обрезка
Этот алгоритм имеет сходство с алгоритмом Коэна — Сазерленда. Начальные и конечные точки классифицируются в зависимости от того, в какой области девятизонной сетки они находятся. Оператор множественного выбора переходит к специализированному обработчику для данного случая. В отличие от этого, алгоритму Коэна — Сазерленда может потребоваться несколько итераций для обработки одного и того же случая.
Алгоритм O{\displaystyle O}
Этот алгоритм классифицирует вершины относительно данной прямой, заданной в неявном виде: p: ax + by + c = 0. Поскольку предполагается, что многоугольник выпуклый, а вершины упорядочены по часовой или против часовой стрелки, можно применить двоичный поиск, что обеспечивает логарифмическую сложность времени выполнения – O(lg N).