화가의 알고리즘

Painter's algorithm
화가 슐레미엘의 알고리즘과 혼동하지 마십시오.
Amiga에서 화가의 알고리즘을 사용하여 렌더링되는 프랙탈 풍경

화가의 알고리즘(깊이 정렬 알고리즘 및 우선 순위 채우기)은 3D 컴퓨터 그래픽에서 가시 표면 측정을 위한 알고리즘으로, 픽셀 단위, 행 단위 또는 영역 단위가 아닌 다각형 단위로 작동합니다.[1][2][3] 화가의 알고리즘은 이미지 내의 다각형을 깊이별로 정렬하고 각 다각형을 가장 먼 물체부터 가장 가까운 물체까지 순서대로 배치하여 이미지를 만듭니다.[4][5]

화가의 알고리즘은 처음에는 1972년 마틴 뉴웰, 리처드 뉴웰, 톰 산차가 모두 CADCentre에 근무하면서 히든 표면 결정 문제를 해결하기 위한 기본적인 방법으로 제안되었습니다.[4] "화가의 알고리즘"이라는 이름은 많은 화가들이 더 가까운 부분보다 장면의 먼 부분을 먼저 그림으로써 시작하여 먼 부분의 일부 영역을 덮는 기술을 말합니다.[6][7] 마찬가지로 화가의 알고리즘은 한 장면의 모든 다각형을 깊이에 따라 정렬한 다음 가장 가까운 순서로 그립니다.[8] 멀리 있는 물체의 보이지 않는 영역을 페인트칠하는 비용으로 일반적으로 보이지 않는 부분에 페인트칠을 하여 가시성 문제를 해결합니다.[9] 알고리즘이 사용하는 순서를 '깊이 순서'라고 하며 장면 부분까지의 숫자 거리를 존중할 필요가 없습니다. 이 순서의 본질적인 특성은 오히려 한 물체가 다른 물체의 일부를 가린다면 첫 번째 물체는 그것이 가린 물체 뒤에 그려지는 것입니다.[9] 따라서 유효한 순서는 객체 사이의 폐색을 나타내는 방향 비순환 그래프의 위상 순서로 설명될 수 있습니다.[10]

먼 산을 먼저 칠하고, 그 다음에 가까운 초원을 칠하고, 마지막으로 나무를 칠합니다. 일부 트리는 목초지의 일부보다 시점에서 더 멀리 떨어져 있지만, 순서(산, 목초지, 나무)는 유효한 깊이 순서를 형성합니다. 순서에 있는 개체가 나중 개체의 일부를 가리는 경우가 없기 때문입니다.

알고리즘.

개념적으로 화가의 알고리즘은 다음과 같이 작동합니다.

  1. 각 다각형을 깊이별로 정렬
  2. 각 다각형을 가장 먼 다각형에서 가장 가까운 다각형으로 배치

의사코드

폴리곤을 각 폴리곤에 대해 깊이별로 정렬합니다. p가 커버하는 각 픽셀에 대해: 픽셀에 페인트 p.color

시간 복잡도

화가 알고리즘의 시간-복잡성은 다각형을 순서화하는 데 사용되는 정렬 알고리즘에 크게 의존합니다. 가장 최적의 정렬 알고리즘을 사용한다고 가정할 때, 화가의 알고리즘은 O(n log n + m*n)의 최악의 복잡도를 갖는데, 여기서 n은 다각형의 수이고 m은 채울 픽셀의 수입니다.

공간복잡도

화가 알고리즘의 최악의 경우 공간 복잡도는 O(n+m)이며, 여기서 n은 다각형의 수이고 m은 채워야 할 픽셀의 수입니다.

이점

화가의 알고리즘을 사용하는 데 유리한 두 가지 주요 기술적 요구 사항이 있습니다.

기본 그래픽 구조

화가의 알고리즘은 다른 깊이 정렬 알고리즘보다 구조가 복잡하지 않습니다.[9][11] 그래픽 제작 순서를 지정하는 가장 간단한 방법 중 하나는 화가의 알고리즘에 의해 사용되는 깊이 기반 렌더링 순서와 같은 요소입니다.[8] 이러한 단순성은 정교한 렌더링이 거의 필요하지 않은 기본적인 컴퓨터 그래픽 출력 시나리오에서 유용합니다.[9]

메모리 효율

화가의 알고리즘이 개발된 70년대 초반에는 물리적 기억이 상대적으로 작았습니다.[12] 이를 위해서는 충돌 없이 큰 작업을 수행하기 위해 최대한 효율적으로 메모리를 관리하는 프로그램이 필요했습니다. 화가의 알고리즘은 메모리의 효율적인 사용을 우선시하지만 모든 이미지의 모든 부분을 렌더링해야 하기 때문에 더 높은 처리 능력을 희생합니다.[9]

한계

폴리곤이 겹치면 알고리즘이 실패할 수 있습니다.

알고리즘은 순환 중첩 또는 피어싱 다각형을 포함하여 일부 경우에 실패할 수 있습니다.

순환중복

순환중첩의 경우 오른쪽 그림과 같이 A, B, C는 어떤 다각형이 위에 있는지 판단할 수 없을 정도로 서로 겹쳐집니다. 이 경우, 문제가 되는 다각형들은 정렬이 가능하도록 절단되어야 합니다.[4]

피어싱 다각형

다각형을 뚫는 경우는 하나의 다각형이 다른 다각형과 교차할 때 발생합니다. 순환 중첩과 마찬가지로, 이 문제는 문제가 되는 다각형을 절단함으로써 해결될 수 있습니다.[4]

효율성.

기본 구현에서 화가의 알고리즘은 비효율적일 수 있습니다. 시스템은 완성된 장면에서 폴리곤이 가려지더라도 표시된 집합의 모든 폴리곤에서 각 점을 렌더링하도록 강제합니다. 이는 세부 장면의 경우 화가의 알고리즘이 컴퓨터 하드웨어에 과도하게 세금을 부과할 수 있음을 의미합니다.

변종

확장된 화가의 알고리즘

화가의 알고리즘으로 확장된 알고리즘으로 제안된 뉴웰의 알고리즘은 순환 다각형과 피어싱 다각형을 절단하는 방법을 제공합니다.[4]

역화인 알고리즘

화가 알고리즘의 또 다른 변형에는 역화가 알고리즘이 포함됩니다. Reverse Painter의 알고리즘은 뷰어에 가장 가까운 객체를 먼저 그립니다. 이미 그려진 이미지의 부분(부분적으로 투명하지 않은 경우)에 페인트를 칠하면 안 된다는 규칙을 사용합니다. 컴퓨터 그래픽 시스템에서, 이것은 가까운 물체에 의해 가려지는 먼 장면의 부분에 대한 색상(조명, 텍스처 등을 사용하여)을 계산할 필요가 없기 때문에 매우 효율적일 수 있습니다. 그러나 역 알고리즘은 표준 버전과 동일한 문제를 많이 겪고 있습니다.

기타 컴퓨터 그래픽 알고리즘

화가 알고리즘의 결함으로 인해 Z-buffer 기법이 개발되었는데, 이는 픽셀 단위로 깊이 충돌을 해결하여 깊이 기반 렌더링 순서의 필요성을 줄임으로써 화가 알고리즘의 개발로 볼 수 있습니다.[13] 그러한 시스템에서도 때때로 화가의 알고리즘의 변형이 사용됩니다. Z-buffer 구현은 일반적으로 하드웨어로 구현된 고정밀 깊이-buffer 레지스터에 의존하기 때문에 반올림 오류로 인한 가시성 문제가 발생할 수 있습니다. 이것들은 다각형 사이의 관절에서 겹치거나 틈입니다. 이를 방지하기 위해 일부 그래픽 엔진은 두 다각형의 영향을 받는 모서리를 화가의 알고리즘에 의해 주어진 순서대로 그리는 [citation needed]"오버 렌더링"을 구현합니다. 이는 일부 픽셀이 실제로 두 번 그려지는 것을 의미하지만(전체 화가의 알고리즘에서와 같이) 이미지의 작은 부분에서만 발생하며 성능 효과는 무시할 수 있습니다.

참고문헌

  • Foley, James; Feiner, Steven K.; Hughes, John F. (1990). Computer Graphics: Principles and Practice. Reading, MA, USA: Addison-Wesley. p. 1174. ISBN 0-201-12110-7.
  1. ^ Appel, Arthur (1968). Morrel, A. J. H. (ed.). "On calculating the illusion of reality" (PDF). Information Processing, Proceedings of IFIP Congress 1968, Edinburgh, UK, 5-10 August 1968, Volume 2 - Hardware, Applications: 945–950. Archived (PDF) from the original on 2008-07-20.
  2. ^ Romney, Gordon Wilson (1969-09-01). "Computer Assisted Assembly and Rendering of Solids". Archived from the original on November 2, 2020. {{cite journal}}: 저널 인용 요구사항 journal= (도와주세요)
  3. ^ 게리 스콧 왓킨스. 1970. "실시간으로 볼 수 있는 표면 알고리즘입니다. 박사님. 논문." 유타 대학교. 주문번호 : AAI7023061
  4. ^ a b c d e Newell, M. E.; Newell, R. G.; Sancha, T. L. (1972-08-01). "A solution to the hidden surface problem" (PDF). Proceedings of the ACM annual conference on - ACM'72. ACM '72. Vol. 1. Boston, Massachusetts, USA: Association for Computing Machinery. pp. 443–450. doi:10.1145/800193.569954. ISBN 978-1-4503-7491-0. S2CID 13829930. Archived (PDF) from the original on 2020-09-22.
  5. ^ Bouknight, W. Jack (1970-09-01). "A procedure for generation of three-dimensional half-toned computer graphics presentations". Communications of the ACM. 13 (9): 527–536. doi:10.1145/362736.362739. ISSN 0001-0782. S2CID 15941472.
  6. ^ Berland, Dinah (1995). Historical Painting Techniques, Materials, and Studio Practice (PDF). The Getty Conservation Institute.
  7. ^ Wylie, Chris; Romney, Gordon; Evans, David; Erdahl, Alan (1967-11-14). "Half-tone perspective drawings by computer". Proceedings of the November 14-16, 1967, fall joint computer conference on - AFIPS '67 (Fall). Anaheim, California: Association for Computing Machinery. pp. 49–58. doi:10.1145/1465611.1465619. ISBN 978-1-4503-7896-3. S2CID 3282975.
  8. ^ a b Desai, Apurva (2008). Computer Graphics. PHI Learning Pvt. Ltd. ISBN 9788120335240.
  9. ^ a b c d e de Berg, Mark (2008). Computational Geometry (PDF). Springer. Archived (PDF) from the original on 2016-08-03.
  10. ^ de Berg, Mark (1993). Ray Shooting, Depth Orders and Hidden Surface Removal. Lecture Notes in Computer Science. Vol. 703. Springer. p. 130. ISBN 9783540570202..
  11. ^ Warnock, John E. (1969-06-01). "A Hidden Surface Algorithm for Computer Generated Halftone Pictures". Archived from the original on November 8, 2020. {{cite journal}}: 저널 인용 요구사항 journal= (도와주세요)
  12. ^ Freiser, M.; Marcus, P. (June 1969). "A survey of some physical limitations on computer elements". IEEE Transactions on Magnetics. 5 (2): 82–90. Bibcode:1969ITM.....5...82F. doi:10.1109/TMAG.1969.1066403. ISSN 1941-0069.
  13. ^ Nyberg, Daniel (2011). Analysis of Two Common Hidden Surface Removal Algorithms, Painter's Algorithm & Z-Buffering.
Wikimedia Commons에는 Painter의 문제와 관련된 미디어가 있습니다.

외부 링크