화가 알고리즘
화가 알고리즘(painter's algorithm)은 3차원 컴퓨터 그래픽스에서 가시도 문제의 가장 단순한 해결책 가운데 하나이다. 3차원 화면을 2차원 틀에 투영할 때 어느 다각형을 보이게 할지 숨겨야 할지를 결정해야 할 상황이 놓인다.
화가 알고리즘은 화가가 그림을 그릴 때 먼 곳에서부터 순서대로 그려가면서 가까운 것을 그릴 때에 이전에 그린 먼 곳의 일부를 덮어버리는 기술로 정의된다. 화가 알고리즘에서는 심도에 따라 한 화면의 모든 다각형을 정렬한 다음 이들을 먼 곳으로부터 가까운 곳으로까지 순서대로 그려나간다. 일반적으로 보이지 않는 부분들 이상을 그려나가므로, 먼 물체의 보이지 않은 부분을 그려나감으로써 가시도 문제를 해결할 수 있다.
이 알고리즘은 다각형을 고리 모양으로 덮거나 뚫어버리는 등의 상황에서 실패로 이어질 수 있다. 오른쪽 그림처럼 고리 모양으로 덮어버리면 다각형 A, B, C는 서로를 덮어버리게 되어 어느 다각형이 다른 다각형 위에 있을지를 결정하지 못하게 된다. 이 경우 문제가 되는 다각형들은 잘라내어 정렬해야 한다. 1972년에 제안된 뉴웰 알고리즘은 이러한 다각형들을 잘라내는 방식을 제공한다. 이뿐 아니라 수많은 방식들이 계산기하학 분야에서 제안되고 있다.
하나의 다각형이 다른 다각형과 교차하는 경우 다각형을 뚫어버리는 경우가 일어날 수 있다. 고리 모양으로 덮어쓰는 상황에서 이 문제는 다각형을 잘라내서 해결할 수 있다.
기본적으로 화가 알고리즘은 비효율적이라 할 수 있다. 완성된 장면에 다각형이 막혀있는 상황에서도, 보이는 부분의 모든 다각형의 각 지점마다 강제로 렌더링해버린다. 다시 말해, 세세한 장면에서 화가 알고리즘을 사용하면 컴퓨터 하드웨어에 큰 부하를 걸리게 할 수 있다.
가장 가까운 물체를 먼저 그리고 먼 물체를 나중에 그리는 역 화가 알고리즘이 쓰이기도 하는데, 여기에는 이미 그린 그림의 일부에 적용해서는 안 된다는 규칙을 동반한다. 컴퓨터 그래픽 시스템에서 이것은 매우 효율적인데, 그 까닭은 근처에 있는 물체로 인해 가려진 더 먼 화면의 일부에 대하여 빛깔(빛, 텍스처링 따위)을 계산할 필요가 없기 때문이다. 그러나 역 알고리즘은 일반 버전과 동일한 문제의 다수를 앉고 있다.
이러한 문제로 인해 Z 버퍼 기법이 개발되었다. 화소 단위로 겹치는 부분을 해결하는 것으로, 심도를 고려한 순서를 결정할 필요를 줄였다. 이러한 시스템에서도 알고리즘 변종을 이용하는 경우도 있다. Z 버퍼는 일반적으로 하드웨어의 고정 심도 버퍼 레지스터에 의지하지만 라운딩 오차 때문에 겹치는 문제를 해결하지 못할 수도 있다. 이를 예방하기 위해 일부 그래픽 엔진들은 화가 알고리즘이 제공하는 순서대로 다각형의 모서리 부분을 그려낸다. 다시 말해 일부 화소들을 실제로 두 번 그려내지만 이러한 일들은 특정 이미지의 극히 조그마한 부분들에만 일어나므로 부정적인 성능 저하 현상은 무시할만한 수준이다.
참고 문헌[편집]
- Foley, James; Andries van Dam; Feiner, Steven K.; John F. Hughes (computer scientist); Hughes, John F. (1990). 《Computer Graphics: Principles and Practice》. Reading, MA, USA: Addison-Wesley. 1174쪽. ISBN 0-201-12110-7.
같이 보기[편집]
외부 링크[편집]
위키미디어 공용에 화가 알고리즘 관련 미디어 분류가 있습니다.
