[ 일부 번역 ] CLIPPING USING HOMOGENEOUS COORDINATES

원문 : 10.1.1.162.1859.pdf

주의 : 번역이 개판이므로 이상하면 원문을 참조하십시오.

주의 : 허락받고 번역한 것이 아니므로 언제든지 내려갈 수 있습니다.

주의 : 가독성을 높이기 위해서 발음이 비슷하거나 잘 알려진 용어는 한글로 표기합니다.

주의 : 이 글은 일부만 번역되어 있으므로 나머지는 원문을 참조하십시오. 

---

CLIPPING USING HOMOGENEOUS COORDINATES

James F. Blinn

Caltech/JPL

Martin E. NewWell

XEROX/PARC

Abstract

클리핑^clipping은 주어진 라인 세그먼트가 출력 화면의 경계 내에서 얼마나 많이 그려지는 지를 판단하는 과정이다. 동차 좌표들^{homogeneous coordinates}은 개체를 표현하고 변환하기 위한 편리한 수학적 장치이다. 그러나 동차 좌표들에 의해 표현되는 공간은 단순한 유클리드 3 차원 공간^{Euclidean 3-space}이 아니다. 사실 그것은 "projective plane" 이라 불리는 위상적인 형태^{topological shape}과 비슷하다. 클리핑 문제는 보통 유클리드 공간과 동차 좌표계에 의해 표현되는 공간의 차이를 무시하고 해결된다. 결론을 말하자면, 이는 그림 생성을 하는 데 에러를 유발하는데, 그 그림에서는 라인이 보여야 함에도 불구하고 안 보이는 것처럼 표시된다. 이 논문은 이러한 경우들에 대해 설명하고 라인 세그먼트들을 올바로 잘라내기 위한 기법들을 기술한다.

1. INTRODUCTION

동차 좌표들은 컴퓨터 그래픽스에서 개체를 표현하고 변환하기에 편리한 수학적 장치로서 오랫동안 사용되어 왔다[ 3 ]. 그러나 동차 좌표들에 의해 제공되는 표현과 연산의 일관성에도 불구하고, 그것들은 보통 완벽하게 사용되지 않는다. 이는 이 기술의 사용법을 명확하게 명시적으로 알려 주는 문서의 부족에 기인한다. Sutherland 와 Hodgman [ 4 ] 은 Polygon Clipping 이라는 논문의 부록으로 이 주제에 대해 약간 다루고 있다. 그 논문은 3 차원 개체를 표현하기 위해 동차 좌표계를 사용하는 방법에 대해 기술하며, 동차 표현이 일관적인 방식으로 변환과 클리핑을 완수하는 방법에 대해서 보여 준다. 그것은 대체로 [ 4 ] 의 부록에 대한 반복이며 거기에 기술된 아이디어의 확장이다.

독자가 동차 좌표계 표현들에 대한 약간의 지식을 가지고 있다고 생각하지만, 다음 절들에서는 이 논문의 뒤에서 사용되는 기본적인 기술과 용어들을 리뷰하고 소개하는 내용을 포함하겠다.

1.1 Homogenous Coordinates

3 차원에서 개체를 표현하고 변환하는 것은 보통 유클리드 좌표계에서 해석적으로 수행된다. 그러므로 3 차원 좌표 ( X, Y, Z ) 는 3 차원에서의 한 점을 표현하기에 충분하다. 회전이나 스케일과 같은 변환은 3x3 행렬에 의해서 표현된다. 이 행렬과 위치 벡터를 곱하는 것은 변환된 위치 벡터를 산출한다. 특정 점들( 특히 무한대에 있는 점들 )과 특정 변환들( 특히 이동 및 원근 투영 행렬 )은 이 방식으로 표현될 수 없다. "동차 좌표"라 불리는 표현은 모든 점과 변환들을 망라할 수 있게 개발되어 왔다. In the scheme, each point is represented in a redundant manner by 4 coordinates. 이 논의에서 그 4 개의 좌표들은 소문자 ( x, y, z, w ) 로 명명될 것이다. 그 redundancy 는 다음과 같은 규칙을 가진다. 점에 대한 동차 표현의 모든 요소들에 ( 0 이 아닌 ) 값을 곱하는 것은 같은 점에 대한 다른 동차 표현이다. 동차 표현으로부터 전통적인 표현^[각주:1]을 얻기 위해서는 redundancy 가 제거되어야 하는데, w=0 이 아닐 때 w 로 모든 요소들을 나눔으로써 수행된다. 이는 여전히 같은 점을 의미하지만, w 의 값이 1 이다. 처음 3 개의 요소들은 그 점에 대한 전통적 요소들이며, 대문자 ( X, Y, Z ) 로 표현된다.

w=1 인 모든 동차 점들은 이미 전통적인 형태로 되어 있는 것과 같다. 사실 그렇게 해야 하는 좋은 이유가 있지 않은 한, 모델링되는 개체의 점들은 보통 w=1 로 지정되어 초기화된다. 그러나 이러한 개체들에 특정 변환이 수행되면 w=1 이 아닌 점들이 생성된다. 나누기 연산은 4 차원 공간에서 한 점을 w=1 인 면에 원점을 통과하는 라인을 따라 투영하는 것으로 생각될 수 있다. 우리는 이를 y=z=0 인 ( x, y, z, w ) 부분 공간에서 설명함으로써 보여 준다. 남아 있는 x 와 w 좌표는 figure 1 과 같이 보이게 된다.

같은 실제 점 ( X, Y, Z ) 를 표현하는 모든 동차 좌표 ( x, y, z, w ) 들은 원점과 ( X, Y, Z, 1 ) 을 통과하는 라인 상에 놓여 있다.

1.2. Homogeneous Transformations

동차 좌표 ( x, y, z, w ) 로 표현되는 점 P 는 4x4 행렬 M 을 곱함으로써 이미지의 점 P'=( x', y', z', w' ) 로 변환된다.

그 점의 3D 이미지 상에서의 행렬의 효과를 해석하기 위해서, M 을 다음과 같이 분할하자 :

r 로 표기된 3x3 부분 행렬은 회전과 스케일링을 표현한다. t 로 표기된 1x3 부분 행렬은 이동을 표현한다. p 로 표기된 3x1 부분 행렬은 원근을 표현한다. 점과 마찬가지로 ( 0 이 아닌 ) 동차 변환 행렬의 곱은 같은 변환을 표현한다. 그러므로 s 로 표기된 1x1 부분 행렬은 w 요소가 점에 대해서 가지는 의미처럼 행렬들에 대해 같은 의미를 가진다.

1.3. Line Segments

라인 세그먼트들은 여기에서 매개변수 형식^{parametric form}으로 표현될 것이며, 두 개의 끝점인 P₁=( x₁, y₁, z₁, w₁ ) 과 P₂=( x₂, y₂, z₂,w₂ ) 의 가중치 합으로서 표현된다.

매개변수 "a" 는 0 부터 1 의 범위를 가지기 때문에, 생성된 점은 P₁ 에서 P₂ 까지 선형적으로 움직인다. 이 세그먼트에서 전통적인 점들의 좌표들을 찾기 위해서, 라인 상의 각 점은 w=1 면에 투영된다. 이것이 figure 2 에 나와 있다.

w=1 인 두 끝점들을 사용해 정의된 세그먼트들에 대해, 모든 보간된 w 값들은 1 이며 그 라인 세그먼트와 그것의 투영은 동일하다. 양수 ( figure 2 에 나온 것처럼 ) w 값을 가진 두 끝점들을 사용해 정의된 세그먼트들에 대해, 유사한 라인이 나타난다. 하지만 w 의 값이 서로 다른 부호를 가진 두 끝점들로 정의된 세그먼트들에 대해서는 특이한 상황이 발생한다. 4 차원에서의 선형 보간에 의해 생성된 세그먼트는 매우 이상하다. 각 점들을 w=1 에 투영함으로써 생성된 세그먼트는 4 차원 공간 세그먼트가 w=0 을 통과하는 곳의 점에서 무한대를 통과할 것이다. 이는 아래에서 P₁ 과 -P₂ 를 사용해 설명되고 있다. 그 끝점들은 같은 figure 2 에서 보이는 것과 같은 투영된 점들을 표현한다. 그러나 투영된 라인 세그먼트는 P₁ 에서 시작해 P₂ 와 멀어지는 방향으로 진행한다. 그리고 무한대를 통과하고 다른 쪽에서 다시 p₂ 를 만나게 된다. 이것이 figure 3 에 나와 있다.

라인 세그먼트는 figure 2 의 예에서의 점들의 집합에 대한 complement^[각주:2]로 구성된다. 그것은 점 ( X₁, Y₁, Z₁ ) 과 ( X₂, Y₂, Z₂ ) 를 연결하는 다른 방식을 설명한다. 그것은 figure 2 의 "내부^interior 라인 세그먼트" 와 반대되는 "외부^external 라인 세그먼트" 라고 불릴 것이다. 이러한 종류의 라인들은 실용적인 응용프로그램들에서 원근 변환들의 결과나 커브들을 정의하기 위해 공통적으로 사용되는 기법들의 결과로서 나타날 수 있다. 클리핑 알고리즘에서 문제를 발생시킬 수 있는 부분이 이 외부 라인 세그먼트들이다.

2. CLIPPING

클리핑은 라인 세그먼트에서 화면 경계를 벗어나는 부분을 제거하는 연산이다. 우리는 단순한 클리핑 알고리즘을 설명하는 것으로부터 시작할 것이다. 이 알고리즘은 w>0 인 영역에 대해서만 올바르게 동작할 것이다. so we will initially concern ourselves with this region.

계산을 단순화하기 위해서 경계들을 -1<X<+1 과 -1<Y<+1 로 자르는 것이 편하다. 원하는 개체 윈도우를 이 영역으로 매핑하기 위해서 viewing 변환이 조정될 수 있다. 그래서 클리핑 경계들은 다음과 같은 평면들이다.

동차 표현에서 이들은 다음과 같이 된다 :

혹은 네 개의 동차 평면들이다.

figure 4 에서 xw 평면에서 left 와 right 경계를 살펴 보자.

x=-1 과 x=+1 사이의 w=1 평면상의 영역은 동차 나누기가 수행된 이후에 X 에서의 가시 영역을 표현한다. 빗금친 선으로 표현된 영역의 모든 점들은 이 영역에 투영하며, 그러므로 가시적이다. 만약 다음과 같은 조건을 가진다면 점은 가시적이다.

빗금친 영역의 모든 점들은 이 조건을 만족한다는 것을 기억하라.

만약 라인 세그먼트가 부분적으로는 스크린 안쪽이고 부분적으로는 스크린의 바깥쪽이면, 그것은 동차 클리핑 평면들 중의 하나를 뚫고 갈 것이다. 우리는  교차점을 찾을 필요가 있다. 이는 라인 세그먼트의 매개변수 정의의 "a" 값으로 표현될 수 있다.

라인 세그먼트가 x+z=0 평면을 가로지른다고 가정하자. 이 상황에서 "a" 의 값은 다음과 같다.

w₁+x₁ 의 크기는 P₁ 점에서 x+w=0 평면까지의 거리에 대한 비율이다. 그러므로 그것은 x+w=0 경계에 대해 P₁ 의 변환된 상대 좌표로 해석될 수 있다. 이러한 이유로 그것은 "경계 좌표^{Boundary Coordinate}"라고 불린다. 모든 점에 대해 각 클리핑 경계에 대한 경계 좌표가 존재한다.

그러므로 양수 값은 점이 클리핑 평면의 가시적 측면에 존재한다는 것을 의미한다. 예를 들어 라인 (1-a )P₁ + aP₂ 가 왼쪽 경계를 가로지르고 있다면, a=BL₁/(BL₁-BL₂) 이다. 다른 경계들에 대해서 비슷한 표현식이 적용된다.

3. THE HOMOGENEOUS PERSPECTIVE TRANSFORM

외부 라인 세그먼트들은 원근 변환을 사용할 때 나타난다. 원근 투영은 기본적으로 눈의 앞쪽에서 x 와 y 를 z 로 나누는 작업을 한다. 동차 원근 변환은 동차 나누기에 z 나누기를 합침으로써 동차 나누기를 현명하게 사용한다( 이는 반드시 수행되어야만 한다). 가장 단순한 형태는 눈을 ( 0, 0, -1 ) 에 두는 것이다. 그리고 나서 원근 투영을 수행하기 위해서 X 와 Y 를 Z+1 로 나뉜다. 통차 좌표 항에서는 x/w 와 y/w 가 z/(w+1)=(z+w)/w 에 의해 나뉘어야 한다. 이것이 다음과 같이 행렬 형식으로 표현될 수 있다.

이 변환의 효과는 "view cone" radiating 의 경계들을 눈으로부터 같은 직교 투영을 위해 사용되는 동일한 정사영의^orthographic 클리핑 경계로 바꾸는 것이다. z/w=0 인 점들은 변하지 않는다. -1<z/w<0 인 점들이 커지는 반면, z/w>0 인 점들은 작아진다. figure 5 를 참조하라.

원근 그림들에서 view cone 에 대해 효율적으로 잘라 내는 과정은 먼저 동차 원근 변환을 적용하고 이전에 정의된 같은 경계들로 잘라냄으로써 수행된다. 물론 이러한 원근 변환에 대한 해석은 비스듬한^oblique viewing 평면에 투영하는 것과 같은 특별한 viewing 효과들을 수행하기 위해서 후^post-원근 변환들을 사용하는 것도 설명한다. 그러한 투영은 전통적인 원근 투영 후에 클리핑 영역에 대한 투영에서 요청된 일부분을 이동하는 것으로 생각할 수 있다. 그러한 두 변환들의 조합이 비스듬한 viewing cone 의 경계들을 위에서 사용한 같은 클리핑 평면들로 올바르게 매핑하는 결과를 산출한다고 입증될 수 있다.

비록 점의 z 좌표가 원근 투영 후에 즉각적으로 유용하지 않은 것처럼 보일지라도, 그것은 가려진 라인/서피스 계산과 깊이 단서^{depth cueing}를 위해 필요하다. This transform has the important property that it includes z such that straight lines remain straight. Examining the zw plane we see that the transformation is merely a skew along the w axis, figure 6. 

원래 w=1 평면에서 정의된 그 개체들은 변환후에 왜곡된다는 것에 주목하라. 그리고 그것들은 새로운 w=1 평면으로 다시 투영된다. eyepoint 는 ( 0, 0, -1, 0 ) 으로 변환되며, 점은 무한대로 음의 z 방향으로 멀어진다. 양의 z 방향으로 무한하게 먼 점들은 z/w=1 에 투영된다. figure 6 에서 사선으로 칠해진 세 개의 영역에서의 변환의 효과에 주목하라. 일반적으로 z 에서 영역들에 대한 변환들은 다음과 같다 :

눈 뒤에 있는 점들은 "wrapped around" 되며, 이제 z/w > 1 에 존재한다.

이제 라인 세그먼트들 상의 원근 투영의 효과와 그것들이 잘려지는 방식을 고려해 보자. 완전히 눈의 앞쪽에 존재하는 세그먼트들에 대해서는 별 일이 발생하지 않는다. 그러나 한 점은 눈의 앞에 있고 한 점은 눈의 뒤에 있는 상황을 고려해 보자( 임의의 viewing 위치가 허용될 때 일어날 수 있다 ). 원근 변환 이후에 이는 외부 라인 세그먼트가 된다. 그것은 어떤 Z<1  에서 시작해서, 눈을 지나 ( 음의 무한대 Z 에서 ) 음의 Z 방향으로 진행한다. 그리고 양의 Z 로 wrapped around 되며, 어떤 Z>1 에서 끝난다. figure 7 을 참조하라.

두 끝점들이 w=1 평면에 다시 투영되면, 두 끝점은 모두 X 와 Y 에 대해 스크린의 가시 영역 내에 존재할 가능성이 매우 크다. 그럼에도 불구하고 눈 뒤의 점은 매우 명백히 비가시적이라는 것이 진실이다. 더우기 이러한 점들은 내부 라인 세그먼트보다는 외부 라인 세그먼트로 연결될 것이다. 이 경우는 눈 앞쪽에서 시작한 두 개의 정상적인 가시 점들과 구분되기 어렵다( 외부 라인 세그먼트의 끝점들이 z/w=1 평면에 걸쳐 있는 알아낼 수 있는 방법이 없다 ). 이러한 문제들은 w=1 로 다시 투영되기 전에 동차 좌표계에서 모든 세그먼트들을 잘라 냄으로써 해결할 수 있다. 이전의 경우에, 눈을 지나는 라인은 눈을 지나기 전에 화면의 X 가장자리에서 잘려나갈 것이다. figure 8 을 참조하라.

문제를 일으키는 외부 라인 세그먼트 부분들은 left, right, bottom, top 명면들 중의 하나에 의해 잘려 나간다.

X, Y 클리핑 과정은 종종 Z 에서의 클리핑 연산에 의해 보강된다. 이는 주로 Z 좌표의 범위를 제한하기 위한 목적으로 수행된다. 눈과 z=0 평면( 예를 들어 화면 ) 사이의 점들은 실 세계의 매우 적은 영역을 취한다. 하지만 원근 투영 이후에 그것들은 -∞ 에서 0 의 범위로 늘어 난다. 무한대 z 좌표를 가진 점들을 표현할 필요성을 없애기 위해, 우리는 그것들을 어떤 값으로 자르는 것이 아니라 "near" 클리핑 평면을 사용해 z/w 로 잘라낼 수 있다. 첨언하면, Z 에서의 가시 영역을 0<Z<+1 로 정의함으로써 클리핑을 X, Y 클리핑으로 표준화될 수 있다. 실제로 원하는 near 경계와 far 경계의 위치는 z 좌표의 스케일과 이동으로서  변환 행렬에 포함될 수 있다. 그러므로 우리는 두 개의 새로운 클리핑 평면과 두 개의 경계 좌표들을 가지게 된다.

점은 z 클리핑 평면에 대해 두 값이 모두 양수일 때 가시적이다.

The main point of this section is, then, that for our first exposure to external line segments, those formed by the perspective transform, the original clipping algorithm works correctly for lines which remain in the w>0 region and for those which dip into the w<0 region due to the perspective transformation. 그러나 클리핑은 동차 나누기 전에 수행되어야 한다. Z 클리핑을 추가하는 것은 원근 투영 이후에 Z 값의 범위를 제한하는데 유용하지만, 그것은 눈 뒤의 라인 세그먼트를 올바로 제거하기 위해서 꼭 필요한 것은 아니다.

5. RATIONAL PARAMETRIC CURVES

하략...

1. conventional representation, 유클리드 3 차원 좌표계 표현, 이 논문에서 대문자로 된 ( X, Y, Z ) [본문으로]
2. 집합에서의 complement 를 의미하는 듯. http://en.wikipedia.org/wiki/Complement_(set_theory) [본문으로]