Clipping and Sutherland-Hodgman algorithm from wikipedia 번역

https://en.wikipedia.org/wiki/Clipping_(computer_graphics)

Clipping (computer graphics)
컴퓨터 그래픽스 맥락에서, Clipping은 정의된 관심 영역 내에서 렌더링 연산을 선택적으로 활성화 또는 비활성화하는 방법이다. 수학적으로, clipping은 constructive geometry 용어를 사용하여 설명될 수 있다. rendering algorithm은 오직 clip region과 scene model 사이에 교차하는 픽셀들 만을 그린다. view volume (일명, frustum) 밖에 있는 Lines and surfaces들은 제거된다.

Clip 영역(regions)들은 흔히 render performance를 개선시키기 위해 명시된다. 잘 선택된 clip은 사용자가 볼 수 없는 픽셀과 관련된 계산을 생략하여 renderer가 시간과 에너지를 절약하도록 한다. 그려질 픽셀들은 clip region안에 있다고 말해진다. 그려지지 않을 픽셀들은 clip region밖에 있다. 좀 더 비공식적으로, 그려지지 않을 픽셀들은 "clipped" 되었다고 말한다.

목차
1. Clipping in 2D graphics
2. Clipping in 3D graphics
      2.1 Near clipping
      2.2 Occlusion clipping (Z- or depth clipping)
3. 비디오 게임에서 clipping의 중요성
4 알고리즘들
5 See also
6 Furthre reading
7 참조

Clipping in 2D graphics
2차원 그래픽스에서, clip region은 한 윈도우 또는 frame의 영역 내에서만 픽셀이 그려지도록 정의될지도 모른다. clip regions은 또한 미적인 또는 예술적인 목적을 위해 픽셀 렌더링을 선택적으로 제어하기 위해 사용될 수 있다. 많은 구현에서, final clip region은 한 개 이상의 application-defined shapes의 합성물일 뿐만 아니라, 어떤 시스템 하드웨어 제약이다.

한 예제 프로그램에서, 한 이미지 편집 프로그램을 고려해라. 한 사용자 프로그램은 그 이미지를 한 viewport에 렌더링할지도 모른다. 그 사용자가 그 이미지의 더 작은 부분을 보기 위해 줌하고 스크롤할 때, 그 프로그램은 viewport밖에 있는 픽셀들이 렌더링되지 않도록 clip boundary를 설정할 수 있다. 게다가, GUI widges, overlays, other windows or frames는 원래 이미지로부터 어떤 픽셀들을 보기 어렵게 할 것이다. 이 의미에서, clip region은 applicaiton-defined "user clip"과 시스템 소프트웨어에 의해 부과된 "device clip"과 hardward 구현의 혼합물이다. 소프트웨어는 연산 시간, 에너지, 메모리를 절약하기 위해 이 clip 정보를 이요할 수 있고, 보이지 않는 픽셀과 관련된 작업을 피한다.

Clipping in 3D graphics
3차원 그래픽스에서, clipping의 용어는 많은 관련된 특징들을 묘사하기 위해 사용될 수 있다. 일반적으로 "clipping"은 사각형의 도형과 작동하는 plane에서의 연산을 가리키고, "culling"은 선택적으로 scene model elements를 처리하는 일반적인 방법들을 말한다. 이 용어는 rigid하지 않고, 정확한 사용은 많은 sources 사이에서 다양하다.

Scene model elements는 geometric primitives를 포함한다: points or vertices; line segments or edges; polygons or faces; and more abstract model objects such as curves, splines, surfaces, and even text. 복잡한 scene models에서, 개별 elements는 viewport 내에서 visibility를 포함한 이유로 비활성화(clipped)되어질 지도 모른다 (frustum culling); orientation을 포함하여 (backface culling), 다른 scene 또는 model elements의 가림에 의해서 (occlusion culling, depth- or "z" clipping). 그러한 clipping을 효율적으로 탐지하고 수행하는 정교한 알고리즘들이 존재한다. 많은 최적화된 clipping methods들은 GPU에 의해 제공되는 특정한 하드웨어 가속 로직에 의존한다.

clipping의 개념은 추상적인 algebraic geometry의 방법을 사용하여 더 높은 차원에 확장될 수 있다.

Near clipping
정점들의 사영 & 2D clipping을 넘어서, near clipping은 3D primitive를 정확히 rasterize하기 위해 요구된다; 이것은 왜냐하면 정점들이 eye뒤에서 사영될지도 모르기 때문이다. Near clipping은 사용된 모든 정점들이 유효한 2D 좌표를 갖도록 보장한다. far-clipping과 함께, 그것은 또한 depth-buffer values의 overflow를 방지하는 것을 돕는다. 비디오 게임에서 어떤 early texture mapping hardware는 (forward texture mapping을 사용하여) near clipping과 UV coordinates과 관련된 복잡성의 문제를 겪는다.

Occlusion clipping (Z- or depth clipping)
3D 컴퓨터 그래픽스에서, "Z"는 종종 viewport origin의 중심으로 한 좌표계에서, depth axis를 말한다: "Z"는 "depth"와 혼용되어서 사용되고, 개념적으로 "virtual screen"안으로 가는 거리와 일치한다. 이 좌표계에서, "X"와 "Y"는 그러므로 사용자의 스크린 또는 viewport에 놓여진 전통적 cartesian coordinate system을 말한다. 이 viewport는 viewing frustum의 geometry에 의해 정의되고, field of view를 파라미터화한다.

Z-clipping or depth clipping은 스크린을 기준으로 그것들의 depth를 기반으로 어떤 scene objects를 선택적으로 렌더링하는 기법을 말한다. 대부분의 그래픽스 툴킷들은 프로그래머가 "near" and "far" clip depth를 명시하도록 하고, 그러한 두 평면들 사이에 있는 오브젝트들의 부분만이 보여진다. 창조적인 프로그래머는 scene에서 3D object의 내부의 시각화를 렌더링하기 위해 이 방법을 사용할 수 있다. 한 비디오 게임 프로그래머는 game logic을 가속하기 위해 clipping information을 사요할 수 있다. 예를들어, 다른 게임 entities를 가리는 tall wall or building은 그 scene의 후방에 있는 items들을 좌표변환하고 텍스쳐링하는데 소비되는 GPU 시간을 아낄 수 있따; 그리고 잘 통합된 소프트웨어 프로그램은 플레이어에 의해 보이지 않는 오브젝트에 대해 게임 로직을 최적화하여 CPU 시간을 절약하기 위해 이 같은 정보를 사용할 수 있다.

Importance of clipping in video games
좋은 clipping 전략은 게임 프레임률과 시각적 퀄리티를 최대화하기 위해 비디오 게임 개발에서 중요하다. 매년 더 빨라진 GPU에도 불구하고, 폴리곤을 transform, texture, and shape하는 것은 연산적으로 여전히 비싸다. 특히 많은 텍스쳐와 오늘날 흔한 쉐이딩 패스들과함께. 그러므로, 게임 개발자들은 각 비디오 프레임마다 그려질 수 있는 폴리곤들의 특정한 "예산" 안에 살아야만 한다.

게임의 시각적 퀄리티를 최대화하기 위해, 개발자들은 하드웨어 제한보다는 오히려 미적인 선택이 polygon budge을 지배하도록 하는 것을 선호한다. 그러므로 성능을 아끼거나 그래픽스 파이프라인 가속을 이용하는 최적화들은 그 플레이어들의 경험을 개선한다.

Clipping 최적화는 현재 scene의 렌더링을 가속화할 수 있고, 렌더러 타임의 사용과 하드웨어 능력 내에서 메모리를 실속있게 한다. 프로그래머들은 종종 clipper를 가속하기 위해 똑똑한 heuristics를 고안하는데, 가끔씩 100%의 정확성으로 어떤 폴리곤들이 camera의 field of view에 있는지를 결정하기 위해 line casting or ray casting을 사용하는 것이 연산적으로 비싸기 때문이다. octrees, R* trees, and bounding volume hierarchies와 같은 공간적으로 인지간으한 자료구조들은 scenes을 렌더링되고 렌더링 되지 않은 지역들로 분할하기 위해 사용된다 (이것은 renderer가 적절한 곳에서 전채 트리 노드들을 거부하거나 받아들이도록 한다).

viewpoint geometry를 기반으로 Occlusion 최적화하는 것은 scene이 reflective surfaces를 포함한다면 artifacts가 생길지도 모른다. reflection mapping인 흔한 기법은 선택적으로 main view frustum의 viewpoint로부터 존재하는 occlusion estimates를 사용할 수 있다; 또는 만약 성능이 허락한다면, 새로운 occlusion map은 별개의 camera position으로부터 연산될 수 있다.

역사적인 이유 때문에, 몇 비디오 게임들은 동일한 로직과 하드웨어 가속과 함께 occlusion test로 충돌 탐지 최적화를 사용했다. 결과적으로 비전문가들도 정확하지 않게 충돌탐지를 언급하기 위해 "clip"이라는 용어를 사용했다 (그것의 반의어는 "no clipping"이다).

Algorithms

• Line clipping algorithms:
• Cohen-Sutherland
• Liang-Barsky
• Fast-clipping
• Cyrus-Beck
• NIcholl-Lee-Nicholl
• Skala
• O(lg N) Algorithm
• Polygon clipping algorithms:
• Greiner-Hormann
• Sutherland-Hodgman
• Weiler-Atherton
• Vatti
• Rendering Methodologies
• Painter's algorithm

See also

• Boolean operations on polygons
• Bounding Volume
• Clip Space
• Hidden surface determination
• Pruning (decision trees)
• Visibility (geometry)

~~~ 생략

https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm

Sutherland-Hodgman algorithm
Sutherland-Hodgman algorithm은 폴리곤을 clipping하는데 사용된다. 그것은 convex clip polygon의 각 line을 차례대로 확장하고 보이는 side에 있는 subject polygon으로부터 정점들만을 선택하여 작동한다.

목차
1. 설명
2. 슈도 코드
3. See also
4. 참조
5. 외부 링크들

Description
그 알고리즘은 subject polygon에 있는 모든 정점들의 input list로 시작한다. 다음으로 그 clip polygon의 한 side는 양 방향으로 무한히 확장되고, 그 subject polygon의 경로를 가로지른다. input list의 정점들은 만약 그것들이 확장된 clip polygon line의 visible side에 놓여있다면 output list로 삽입되고, 새로운 정점들이 output list에 추가되는데, 그 list에서, 그 subject polygon path는 확장된 clip polygon line을 가로지른다.

이 프로세스는 각 clip polygon side에 대해 반복되고, 다음을 위해 input list로서 한 스테이지의 output list를 사용한다. 그 clip polygon의 모든 sides가 처리되었따면, 정점들의 최종 생성된 리스트는 전적으로 visible한 새로운 single polygon을 정의한다. 만약 그 subject polygon이 clipping polygon 밖에서 concave했다면, 그 새로운 polygon이 coincident (즉, 중첩된) edges를 가질지도 모른다는 것에 주목해라 - 이것은 렌더링에 대해서는 수용가능하지만, 쉐오두를 연산하는 것 같은 다른 프로그램에 대해서는 수용가능하지 않다.

Weiler-Atherton algorithm은 나눠진 폴리곤들의 한 집합을 반환하여 이것을 극복하지만, 좀 더 복잡하고 연산적으로 더 비싸다. 그래서 Sutherland-Hodgman은 많은 렌더링 프로그램을 위해 사용된다. Sutherland-Hodgman은 또한 viewing space에 정의되는 planes의 boundaries를 기반으로 polygon paths를 clipping하여 3D space로 확장될 수 있다.

Pseudo code
clip polygon에서 edges의 한 list와 subject polygon의 정점들의 한 list가 주어진다면, 다음의 절차는 clip polygon에 대해 subject polygon을 clip한다.

List outputList = subjectPolygon;
for (Edge clipEdge in clipPolygon) do
     List inputList = outputList;
     outputList.clear();
     Point S = inputList.last;
     for(Point E in inputList) do
          if(E inside clipEdge) then
               if(S not inside clipEdge) then
                    outputList.add(ComputeIntersection(S,E,clipEdge));
               end if
               outputList.add(E);
          else if (S inside clipEdge) then
               outputList.add(ComputeIntersection(S,E,clipEdge));
          endif
          S = E;
     done
done

clipped polygon의 정점들은 그 알고리즘이 종료될 때 outputList에서 발견되어질 것이다. 만약 한 점이 polygon의 remainder로서 edge의 같은 side에 있다면, 그 점이 한 edge 안(insdie)에 있다고 정의된다는 것에 주목해라. 만약 그 clip polygon의 정점들이 일관되게 반시계 방향으로 리스트되어 있다면, 이것은 그 점이 그 line의 왼쪽에 있는지를 테스트하는 것과 같다 (left는 inside를 의미하고, 반면에 right는 outside를 의미한다), 그리고 외적을 사용하여 간단히 구현될 수 있다.

ComputeIntersection은 명확성을 위해서 여기에서 생략된 함수인데, 선분의 교차와 infinite edge를 반환한다. 만약 그러한 교차가 존재한다고 알려진다면 그것이 호출되고, 그러므로 간단하ㅣ 두 lines이 무한히 길다고 다룰 수 있다는 것에 주목해라.

External Link 필요한 거 번역
https://www.cs.drexel.edu/~david/Classes/CS430/Lectures/L-05_Polygons.6.pdf
Sutherland-Hodgman Polygon-Clipping Algorithm

• Divide and Conquer
• idea
• Clip single polygon using single infinite clip edge
• 4번 반복
• 특성:
• 2D convex n-gons는 임의의 n-gons를 clip할 수 있다.
• 3D convex polyhedra는 임의의 polyhedra를 clip할 수 있다.