В компьютерной графике , линия отсечения является процесс удаления линий или участков линий за пределами области , представляющей интерес. Как правило, удаляется любая линия или часть, выходящая за пределы области просмотра.
Существует два распространенных алгоритма обрезки линий: Коэн – Сазерленд и Лян – Барски.
Метод обрезки линий состоит из различных частей. Тесты проводятся на данном отрезке линии, чтобы определить, находится ли он за пределами области просмотра. После этого выполняются расчеты пересечения с одной или несколькими границами отсечения. [1]
Определение того, какая часть линии находится внутри или вне объема отсечения, выполняется путем обработки конечных точек линии относительно пересечения.
Коэн-Сазерленд [ править ]
В компьютерной графике алгоритм Коэна – Сазерленда (названный в честь Дэнни Коэна и Ивана Сазерленда) представляет собой алгоритм отсечения строк. Алгоритм делит 2D-пространство на 9 областей, из которых видна только средняя часть (область просмотра).
В 1967 году работа Дэнни Коэна по моделированию полета привела к разработке алгоритмов двух- и трехмерной обрезки линий компьютерной графики Коэна – Сазерленда, созданных с Иваном Сазерлендом.
Лян-Барский [ править ]
Алгоритм Лянга – Барского использует параметрическое уравнение линии и неравенства, описывающие диапазон отсекающего прямоугольника, для определения пересечений между линией и отсекающим прямоугольником. С помощью этих пересечений он знает, какую часть линии следует провести. Этот алгоритм значительно более эффективен, чем Коэн-Сазерленд, но Коэн-Сазерленд делает тривиальные приемы и отклонения намного быстрее, поэтому вместо этого следует учитывать, если большая часть строк, которые вам нужно обрезать, будут полностью внутри или вне окна отсечения .
Сайрус-Бек [ править ]
Очень похож на алгоритм обрезки линий Лянга – Барского. Разница в том, что Лян-Барски - это упрощенный вариант Сайруса-Бека, который был оптимизирован для прямоугольного окна клипа.
Алгоритм Сайруса-Бека в первую очередь предназначен для отсечения линии в параметрической форме от выпуклого многоугольника в 2-х измерениях или против выпуклого многогранника в 3-х измерениях. [2]
Николл-Ли-Николл [ править ]
Алгоритм Николла – Ли – Николла - это быстрый алгоритм отсечения линии, который снижает вероятность многократного отсечения одного отрезка линии, как это может происходить в алгоритме Коэна-Сазерленда. Окно обрезки разделено на несколько различных областей в зависимости от положения начальной точки линии, которая будет обрезана.
Быстрая обрезка [ править ]
Этот алгоритм имеет сходство с алгоритмом Коэна – Сазерленда. Начальная и конечная позиции классифицируются по той части сетки из 9 областей, которую они занимают. Большой оператор switch переходит к специализированному обработчику для этого случая. Напротив, Коэну – Сазерленду, возможно, придется повторить несколько итераций для обработки одного и того же случая. [3]
Алгоритм O (lg N ) [ править ]
Этот алгоритм классифицирует вершины заданной строки в неявной форме p : ax + by + c = 0. Поскольку многоугольник предполагается выпуклым, а вершины упорядочены по часовой стрелке или против часовой стрелки, можно применить двоичный поиск и получить O (lg N ) сложность выполнения. [4]
Скала [ править ]
Этот алгоритм основан на однородных координатах и двойственности . [5] Его можно использовать для обрезки линии или отрезка линии в прямоугольном окне, а также в выпуклом многоугольнике. Алгоритм основан на классификации вершины окна отсечения относительно полупространства, заданного линией p : ax + by + c = 0. Результат классификации определяет ребра, пересекаемые линией p . Алгоритм прост, легко реализуем и расширяем до выпуклого окна. Отрезок или отрезок p можно вычислить по точкам r 1 , r 2. задается в однородных координатах непосредственно с использованием векторного произведения как
- p = r 1 × r 2 = ( x 1 , y 1 , w 1 ) × ( x 2 , y 2 , w 2 )
или как
- p = r 1 × r 2 = ( x 1 , y 1 , 1) × ( x 2 , y 2 , 1).
См. Также [ править ]
Ссылки [ править ]
- ^ Renka, RJ (2014-10-19). «Отсечение линии» (PDF) . Департамент компьютерных наук и инженерии, Университет Северного Техаса . Проверено 12 января 2016 .
- ^ Сайрус, М., Бек, Дж .: Обобщенное двух- и трехмерное вырезание , компьютеры и графика, Vol. 3, № 1. С. 23–28, 1978.
- ^ Марк С. Собков, Пол Посписил и Йи-Хонг Ян. Быстрый алгоритм обрезки двумерных линий с помощью линейного кодирования // Computer & Graphics, Vol. 11, No. 4, pp. 459–467, 1987.
- ^ Скала, В .:Алгоритм обрезки строк O (lg N ) в E2, Компьютеры и графика, Pergamon Press, Vol. 18, No. 4, 1994.
- ^ Скала, В .: Новый подход к обрезке линий и сегментов в однородных координатах , Визуальный компьютер, ISSN 0178-2789, Vol. 21, № 11, стр. 905–914, Springer Verlag, 2005.
