라인 클리핑

컴퓨터 그래픽에서 라인 클리핑은 관심 영역 밖의 라인 또는 라인 일부를 제거하는 과정이다.일반적으로, 보기 영역 밖에 있는 선이나 부분은 제거된다.

라인 클리핑에는 두 가지 공통 알고리즘이 있다.코헨-서덜랜드와 량-바르스키.

라인 컷팅 방식은 다양한 부분으로 구성된다.주어진 선 세그먼트에 대해 테스트를 수행하여 뷰 볼륨 외부에 있는지 여부를 확인한다.이후 하나 이상의 자르기 경계로 교차로 계산이 이루어진다.^[1]

교차로와 관련하여 선의 끝점을 처리하여 선의 어느 부분이 클리핑 볼륨 내부 또는 외부에 있는지 결정한다.

코언-서덜랜드

컴퓨터 그래픽에서 코언-서덜랜드 알고리즘(Danny Cohen과 Ivan Sutherland의 이름을 따서 명명)은 라인 자르기 알고리즘이다.알고리즘은 2D 공간을 9개 영역으로 나누는데, 그 중 중간 부분(뷰포트)만 보인다.

1967년 대니 코헨의 비행 시뮬레이션 작업은 이반 서덜랜드와 함께 만들어진 코헨-서덜랜드 컴퓨터 그래픽 2차원 및 3차원 라인 클리핑 알고리즘의 개발로 이어졌다.

량-바르스키

Liang-Barsky 알고리즘은 자르기 상자의 범위를 설명하는 선과 불평등의 파라메트릭 방정식을 사용하여 선과 자르기 상자 사이의 교차점을 결정한다.이러한 교차점을 통해 선의 어느 부분을 그려야 하는지 알 수 있다.이 알고리즘은 코헨-서덜랜드보다 훨씬 더 효율적이지만, 코헨-서덜랜드는 사소한 것을 훨씬 더 빨리 받아들이고 거부하기 때문에 클립으로 자르는데 필요한 대부분의 선이 클립 창에 완전히 들어가거나 빠져 있는 경우 그 대신 고려되어야 한다.

사이러스벡

량-바르스키 선 자르기 알고리즘과 매우 유사하다.차이점은 량-바르스키가 직사각형 클립 창에 최적화된 단순화된 사이러스-벡 변형이라는 점이다.

사이러스-벡 알고리즘은 주로 2차원의 볼록 폴리곤 또는 3차원의 볼록 폴리곤에 대해 파라메트릭 형태의 선을 클리핑하는 것을 목적으로 한다.^[2]

니콜-리-니콜

Nicholl-Lee-Nicholl 알고리즘은 Cohen-Sutherland 알고리즘에서 일어날 수 있는 것처럼 단일 라인 세그먼트를 여러 번 클리핑할 가능성을 줄이는 고속 라인 클리핑 알고리즘이다.클리핑 창은 클리핑할 선의 초기 지점 위치에 따라 여러 가지 다른 영역으로 나뉜다.

빠른 클리핑

이 알고리즘은 코헨-서덜랜드와 유사하다.시작 위치와 끝 위치는 9개 영역 그리드의 어느 부분을 차지하느냐에 따라 분류된다.큰 스위치 문장이 그 경우에 대한 전문 처리기로 이동한다.이와는 대조적으로, 코헨-서덜랜드는 같은 사건을 다루기 위해 여러 번 반복해야 할 수도 있다.^[3]

O(lg N) 알고리즘

이 알고리즘은 암묵적 형태 p: axx + by + c = 0에서 주어진 선에 대해 정점을 분류한다. 폴리곤은 볼록한 것으로 가정하고 정점은 시계방향 또는 시계반대방향으로 순서가 정해지기 때문에 이진수색을 적용할 수 있으며 O(lg N) 런타임 복잡성으로 이어질 수 있다.^[4]

스칼라

이 알고리즘은 균일한 좌표와 이중성을 기반으로 한다.^[5]직사각형 창에 대한 선 또는 선 세그먼트 클리핑과 볼록한 다각형에 사용할 수 있다.알고리즘은 선 p: 도끼 + by + c = 0으로 주어진 반공간을 기준으로 클리핑 윈도우의 정점을 분류하는 것에 기초한다.분류 결과에 따라 선 p와 교차하는 가장자리가 결정된다.알고리즘은 간단하고 구현이 용이하며 볼록한 창으로도 확장 가능하다.선 또는 선 세그먼트 p는 교차 제품을 사용하여 동종 좌표로 직접 주어진 r₁, r 지점에서₂ 계산할 수 있다.

p = r₁ × r₂ = (x₁, y₁, w₁) × (x₂, y₂, w₂)

또는 로서

p₂ = r₁ × r = (x₁, y₁, 1) × (x₂, y₂, 1) × (x, y, 1)

참고 항목

• 클리핑(컴퓨터 그래픽)

참조