Обрезка линий

В компьютерной графике обрезка линий — это процесс удаления ( обрезки ) линий или частей линий за пределами интересующей области ( окна просмотра или объема просмотра ). Обычно любая часть линии, находящаяся за пределами области просмотра, удаляется.

Существует два распространенных алгоритма отсечения строк: Коэна-Сазерленда и Ляна-Барски .

Метод обрезки строк состоит из нескольких частей. Тесты проводятся на заданном сегменте линии, чтобы выяснить, находится ли он за пределами области обзора или объема. Затем пересечений с одной или несколькими границами отсечения. выполняются расчеты ^[1] Определение того, какая часть линии находится внутри или за пределами объема отсечения, осуществляется путем обработки конечных точек линии с учетом пересечения.

Коэн – Сазерленд

В компьютерной графике алгоритм Коэна-Сазерленда (названный в честь Дэнни Коэна и Ивана Сазерленда) представляет собой алгоритм обрезки строк. Алгоритм делит 2D-пространство на 9 областей, из которых видна только средняя часть (окно просмотра).

В 1967 году работа Дэнни Коэна по моделированию полета привела к разработке алгоритмов двух- и трехмерного отсечения линий компьютерной графики Коэна-Сазерленда, созданных вместе с Иваном Сазерлендом.

Лян–Барский

Алгоритм Ляна – Барски использует параметрическое уравнение линии и неравенства, описывающие диапазон рамки отсечения, для определения пересечений между линией и рамкой отсечения. Благодаря этим пересечениям он знает, какую часть линии следует нарисовать. Этот алгоритм значительно более эффективен, чем алгоритм Коэна-Сазерленда, но алгоритм Коэна-Сазерленда выполняет тривиальные приемы и отклонения гораздо быстрее, поэтому вместо этого следует учитывать, что большинство строк, которые вам нужно обрезать, будут полностью находиться в окне обрезки или за ее пределами .

Сайрус-Бек

Очень похоже на алгоритм отсечения линий Ляна – Барски. Разница в том, что Лян-Барски представляет собой упрощенный вариант Сайруса-Бека, оптимизированный для прямоугольного окна клипа.

Алгоритм Сайруса-Бека в первую очередь предназначен для отсечения линии в параметрической форме от выпуклого многоугольника в 2 измерениях или от выпуклого многогранника в 3 измерениях. ^[2]

Николл – Ли – Николл

Алгоритм Николла-Ли-Николла представляет собой быстрый алгоритм отсечения линий, который снижает вероятность многократного отсечения одного сегмента линии, как это может произойти в алгоритме Коэна-Сазерленда. Окно обрезки разделено на несколько различных областей в зависимости от положения начальной точки обрезаемой линии.

Быстрая обрезка

Этот алгоритм имеет сходство с алгоритмом Коэна – Сазерленда. Начальная и конечная позиции классифицируются по тому, какую часть сетки из 9 зон они занимают. В этом случае большой оператор переключателя переходит к специализированному обработчику. Напротив, Коэну-Сазерленду, возможно, придется повторить несколько раз, чтобы обработать один и тот же случай. ^[3]

Алгоритм O ( lgN )

Этот алгоритм классифицирует вершины по заданной линии в неявной форме p : ax + by + c = 0. Поскольку предполагается, что многоугольник выпуклый, а вершины упорядочены по часовой стрелке или против часовой стрелки, можно применить двоичный поиск, который приводит к результату O. (lg N ) сложность времени выполнения. ^[4]

Шкала

Этот алгоритм основан на однородных координатах и двойственности . ^[5] Его можно использовать для обрезки линий или сегментов прямоугольного окна, а также выпуклого многоугольника. Алгоритм основан на классификации вершины окна отсечения по полупространству, заданному линией p : ax + by + c = 0. Результат классификации определяет ребра, пересекаемые линией p . Алгоритм прост, легко реализуем и расширяем также до выпуклого окна. Линия или сегмент линии p может быть вычислен из точек r ₁ , r _2, заданных в однородных координатах, непосредственно с использованием векторного произведения как

п знак равно р ₁ × р ₂ знак равно ( Икс ₁ , y ₁ , ш ₁ ) × ( Икс ₂ , y ₂ , ш ₂ )

или как

п знак равно р ₁ × р ₂ знак равно ( Икс ₁ , y ₁ , 1) × ( Икс ₂ , y ₂ , 1).

См. также

Вырезка (компьютерная графика)

Ссылки

^ Ренка, Р.Дж. (19 октября 2014 г.). «Обрезка линий» (PDF) . Департамент компьютерных наук и инженерии Университета Северного Техаса . Проверено 12 января 2016 г.
^ Сайрус, М., Бек, Дж.: Обобщенное двумерное и трехмерное отсечение , Компьютеры и графика, Том. 3, № 1, стр. 23–28, 1978.
^ Марк С. Собков, Пол Поспишил и Йи-Хонг Ян. Алгоритм быстрого двумерного отсечения строк посредством кодирования строк // Computer & Graphics, Vol. 11, № 4, стр. 459–467, 1987.
^ Скала, В .: O (lg N Алгоритм отсечения строк ) в E2, Компьютеры и графика, Pergamon Press, Vol. 18, № 4, 1994.
^ Скала, В.: Новый подход к отсечению линий и отрезков линий в однородных координатах , The Visual Computer, ISSN 0178-2789, Vol. 21, № 11, стр. 905–914, Springer Verlag, 2005.

[1] Ренка, Р.Дж. (19 октября 2014 г.). «Обрезка линий» (PDF) . Департамент компьютерных наук и инженерии Университета Северного Техаса . Проверено 12 января 2016 г.

[2] Сайрус, М., Бек, Дж.: Обобщенное двумерное и трехмерное отсечение , Компьютеры и графика, Том. 3, № 1, стр. 23–28, 1978.

[3] Марк С. Собков, Пол Поспишил и Йи-Хонг Ян. Алгоритм быстрого двумерного отсечения строк посредством кодирования строк // Computer & Graphics, Vol. 11, № 4, стр. 459–467, 1987.

[4] Скала, В .: O (lg N Алгоритм отсечения строк ) в E2, Компьютеры и графика, Pergamon Press, Vol. 18, № 4, 1994.

[5] Скала, В.: Новый подход к отсечению линий и отрезков линий в однородных координатах , The Visual Computer, ISSN 0178-2789, Vol. 21, № 11, стр. 905–914, Springer Verlag, 2005.

[1]

[2]

[3]

[4]

[5]