워녹 알고리즘

주어진 뷰포트의 폴리곤 가시성: a) 폴리곤은 뷰포트를 채우고, b) 폴리곤은 부분적으로 채우며, c) 완전히 보이는 폴리곤, d) 폴리곤은 보이지 않는다.

단순 씬(scene)에 대한 뷰포트 분할의 4단계

워녹 알고리즘은 존 워녹이 발명한 숨겨진 표면 알고리즘으로 컴퓨터 그래픽 분야에서 주로 사용된다.^[1]계산하기에 사소한 영역을 얻을 때까지 장면을 재귀적으로 세분화하여 복잡한 이미지를 렌더링하는 문제를 해결한다.즉, 씬(scene)이 효율적으로 계산될 수 있을 정도로 단순하면 렌더링되고, 그렇지 않으면 씬(scene)^[2]이 더 작은 부분으로 분할되어 단순성을 테스트한다.

이것은 런타임 $O{\displaystyle }$(${\displaystyle n}$ $){\displaystyle O($np$)}$의 분할 및 정복 알고리즘이며$,$ 여기서 n은 다각형의 수, p는 뷰포트의 픽셀 수입니다.

입력은 다각형과 뷰포트의 목록이다.폴리곤 목록이 단순하면 뷰포트에 폴리곤을 그리는 것이 가장 좋은 예다.단순은 하나의 폴리곤(그 다음 폴리곤 또는 그 부분이 뷰포트의 적절한 부분에 그려진다) 또는 하나의 픽셀 크기인 뷰포트로 정의된다(그 다음 해당 픽셀은 관찰자와 가장 가까운 폴리곤의 색상을 얻는다).연속 단계는 뷰포트를 4개의 동일한 크기의 사분면으로 나누고 각 사분면에 대한 알고리즘을 재귀적으로 호출하는 것이며, 폴리곤 목록은 사분면에 보이는 다각형만 포함하도록 수정된다.

워녹은 자신의 알고리즘을 소프트웨어 코드가 아닌 단어나 그림으로 표현했는데, 이 논문은 현재 3차원 컴퓨터 그래픽의 핵심이 되고 있는 경사면 및 기타 특징들을 음영하는 프로토콜을 기술하기도 했다.논문 전체가 소개부터 서지학까지 26페이지에 불과했다.

참조

외부 링크

• Warnock 알고리즘 요약

이 컴퓨터 프로그래밍 관련 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.

• v
• t