Vatti 클리핑 알고리즘
Vatti clipping algorithmVatti 클리핑[1] 알고리즘은 컴퓨터 그래픽스에서 사용됩니다.임의의 수의 임의 형상 피사체 폴리곤을 임의의 수의 임의 형상 클립 폴리곤으로 클리핑할 수 있습니다.서덜랜드와 달리...Hodgman 및 Weiler-Atherton 폴리곤 클리핑알고리즘은 서브젝트 또는 클립으로 사용할 수 있는 폴리곤의 종류를 제한하지 않습니다.복잡한(자체 교차) 폴리곤이나 구멍이 있는 폴리곤도 처리할 수 있습니다.이 알고리즘은 일반적으로 2D 공간에서만 적용할 수 있습니다.
묘사
클리핑은 피사체 폴리곤과 클립 폴리곤의 상호작용으로 정의됩니다.클리핑에는 보통 서브젝트와 클립 폴리곤의 교차점(오버랩 영역)을 찾는 작업이 포함되지만 클리핑 알고리즘은 다른 부울 클리핑 작업에도 적용할 수 있습니다.다양한 차이에서는 클리핑 폴리곤이 서브젝트에서 중복되는 영역을 제거하고 결합에서는 서브젝트 또는 클립 중 하나로 커버된 영역을 반환합니다.폴리곤 및 xor. 여기서 클리핑은 피사체 폴리곤 또는 클립 폴리곤으로 커버된 영역을 반환합니다(제목 폴리곤과 클립 폴리곤 모두 커버된 영역을 제외).
Vatti 알고리즘은 가장 낮은 가장자리에서 시작하여 맨 위를 향해 작업하는 순서 있는 방식으로 대상 폴리곤 모서리와 클리핑 폴리곤 모서리를 모두 처리합니다. 이는 개념적으로 Bentley-Ottmann 알고리즘과 유사합니다.이 스위프 라인 접근법은 문제 공간을 참여하는 폴리곤의 모든 정점을 통과하는 가상의 수평선인 스캔 라인으로 나눕니다.이러한 스캔 라인은 스캔 빔의 윤곽을 나타냅니다. 즉, 인접한 스캔 라인 사이의 공간입니다.이러한 스캔 빔은 가장 낮은 스캔 빔부터 차례로 처리되며, 알고리즘은 이러한 스캔 빔 내의 교차점을 솔루션 폴리곤에 추가합니다.
「 」를 참조해 주세요.
레퍼런스
- ^ Bala R. Vatti. "폴리곤 클리핑의 일반적인 솔루션", ACM의 통신, Vol 35, 제7호(1992년 7월) 페이지 56-63.
외부 링크
