숨겨진 표면 결정

Hidden-surface determination
3차원(3D)
컴퓨터 그래픽스
Activemarker2.PNG
기초
주요 용도
관련 항목

3D 컴퓨터 그래픽에서, 숨겨진 표면 결정(표시 표면 결정, 숨겨진 표면 제거(HSR)라고도 함), 폐색 도태(OC) 또는 가시 표면 결정(Visible-surface decision, VSD)은 특정 시야각에서 어떤 표면과 부분을 볼 수 있는지를 확인하는 과정이다.숨겨진 표면 결정 알고리즘은 3D 컴퓨터 그래픽[citation needed] 분야의 첫 번째 주요 문제 중 하나였던 가시성 문제에 대한 해결책이다.은밀한 표면 결정 과정을 은신이라고 부르기도 하고, 그런 알고리즘을 히더라고[citation needed] 부르기도 한다.라인 렌더링을 언급할 때 이를 은선 제거라고[citation needed] 한다.장면을 정확하게 렌더링하려면 숨겨진 표면 판단이 필요하며, 모델 자체 뒤에 숨겨진 형상을 볼 수 없도록 하여 그래픽의 자연적으로 볼 수 있는 부분만 볼 수 있게 한다.

배경

숨겨진 표면 결정은 사용자에게 보이지 않아야 하는 표면(예를 들어 벽과 같은 불투명한 물체 뒤에 있기 때문에)이 렌더링되지 않도록 하는 과정이다.하드웨어 성능이 향상되었음에도 불구하고 고급 렌더링 알고리즘이 여전히 필요하다.렌더링 엔진의 책임은 넓은 세계 공간을 허용하는 것이며, 세계의 크기가 무한대에 가까워짐에 따라 엔진은 속도를 늦추지 않고 일정한 속도로 유지되어야 한다.이 프로세스를 최적화하려면 사용자에게 표시되지 않는 표면 렌더링을 위해 가능한 한 적은 리소스의 배치를 보장할 수 있어야 한다.

숨겨진 표면 결정을 위한 많은 기술들이 있다.그것들은 근본적으로 분류의 연습이며 보통 분류가 수행되는 순서와 문제가 세분되는 방법에 따라 다르다.많은 양의 그래픽 원형을 분류하는 것은 보통 분할과 정복에 의해 이루어진다.

알고리즘

렌더링 파이프라인을 고려하여 투영, 클리핑 및 래스터화 단계는 다음 알고리즘에 의해 다르게 처리된다.

Z버퍼링
래스터라이징 중에 각 픽셀의 깊이/Z 값(또는 안티앨리어싱의 경우 샘플이지만 픽셀이라는 용어가 사용되는 경우 일반성을 잃지 않고)을 기존 깊이 값과 비교하여 점검한다.현재 픽셀이 Z-버퍼의 픽셀 뒤에 있으면 픽셀이 거부되고 그렇지 않으면 음영 처리되며 깊이 값이 Z-버퍼의 픽셀을 대체한다.Z-버퍼링은 역동적인 장면을 쉽게 지원하며 현재 그래픽 하드웨어에서 효율적으로 구현되고 있다.이것이 현행 기준이다.Z-버퍼링 사용 비용은 픽셀당 최대 4바이트를 사용하며 래스터화 알고리즘이 각 래스터화 샘플을 Z-버퍼와 대조해 확인할 필요가 있다는 것이다.Z-버퍼는 정밀 오차(Z-싸움이라고도 함)로 인해 아티팩트에 시달릴 수 있다.
탐지 범위 버퍼(C-버퍼) 및 표면 버퍼(S-버퍼)
Z버퍼보다 빠르고, 퀘이크 1 시대의 게임에서 흔히 사용된다.픽셀당 Z 값을 저장하는 대신 화면의 라인당 이미 표시된 세그먼트 목록을 저장한다.그런 다음 새로운 다각형은 그것들을 숨길 수 있는 이미 표시된 세그먼트에 대해 절단된다.S-버퍼는 변형되지 않은 다각형을 표시할 수 있고, C-버퍼는 가장 먼 곳에서부터 다각형을 표시해야 한다.C-버퍼 기법은 픽셀을 두 번 이상 그릴 필요가 없기 때문에 공정이 약간 빠르다.이것은 폴리곤에 대한 정렬을 제공하는 BSP(이진 공간 분할) 트리와 함께 일반적으로 사용되었다.
정렬된 활성 에지 목록
퀘이크 1에서 사용된 이 제품은 이미 표시된 폴리곤의 가장자리 목록을 저장하고 있었다(스캔라인 렌더링 참조).폴리곤은 가장 먼 곳에서부터 표시된다.새로운 폴리곤은 이미 표시된 폴리곤의 가장자리에 고정되어 새로운 폴리곤을 만들어 추가 에지를 저장한다.S/C/Z-버퍼보다 구현이 훨씬 어렵지만 해상도가 높아지면 확장이 훨씬 잘 된다.
화가의 알고리즘
폴리곤은 중추를 기준으로 정렬하고 다시 앞쪽으로 끌어당긴다.이는 비슷한 크기의 폴리곤이 매끄러운 메쉬를 형성하고 백페이스 컬링이 켜져 있는 장면에 적용하면 거의 유물이 생성되지 않는다.여기서 비용은 분류 단계와 시각적 유물이 발생할 수 있다는 사실이다.이 알고리즘은 서로 교차하는 표면과 같은 다양한 공통 구성에서 다각형을 처리할 수 없기 때문에 일반 장면의 설계에 의해 깨진다.
BSP(Binary Space Partitioning)
폴리곤 경계에 해당하는 평면을 따라 씬(scene)을 나눈다.소분할은 BSP 트리가 통과될 때 장면의 어느 지점에서나 명확하지 않은 깊이 순서를 제공하는 방식으로 구성된다.여기서 단점은 BSP 트리가 값비싼 사전 공정을 통해 만들어진다는 점이다.역동적인 기하학으로 구성된 장면에 덜 적합하다는 뜻이다.이점은 데이터가 미리 정렬되어 있고 오류 없이 이전에 언급한 알고리즘을 사용할 수 있다는 것이다.BSP는 HSR에 대한 해결책이 아니며 단지 보조책일 뿐이라는 점에 유의한다.
레이 트레이싱
광선을 시각에서 장면으로 추적하여 광선의 경로를 시각으로 모형화하려는 시도.숨겨진 표면 제거 알고리즘은 아니지만, 각 뷰레이를 따라 가장 가까운 표면을 찾아 숨겨진 표면 제거 문제를 암묵적으로 해결한다.사실상 이것은 픽셀 단위로 모든 지오메트리를 분류하는 것과 같다.
워녹 알고리즘
화면을 더 작은 영역으로 나누고 삼각형을 정렬하십시오.모호성이 있는 경우(즉, 폴리곤은 이 영역 내에서 심층 범위와 겹친다) 추가 분할이 발생한다.한계에서 하위 분할은 픽셀 레벨까지 발생할 수 있다.

도태 및 가시 표면 결정

가시 표면 결정(VSD) 관련 영역은 도태되며, 일반적으로 렌더링 파이프라인에서 VSD 이전에 발생한다.원시 요소 또는 원시 요소들의 집합은 전체적으로 거부될 수 있으며, 이것은 일반적으로 잘 설계된 시스템의 하중을 감소시킨다.

파이프라인에서 초기에 도태할 때의 이점은 눈에 보이지 않는 물체 전체를 가져오거나 변형하거나 래스터화하거나 음영처리할 필요가 없다는 것이다.다음은 Culling 알고리즘의 몇 가지 유형:

뷰-프러스텀 컬링

뷰잉 좌절은 가상 카메라가 볼 수 있는 볼륨을 기하학적으로 표현한 것이다.당연히 이 볼륨 외부의 물체는 최종 이미지에서는 보이지 않으므로 폐기된다.종종 사물이 시야의 경계선 위에 놓여 있다.이 물체들은 클리핑이라는 과정에서 이 경계를 따라 조각조각 잘려나가고, 좌심 밖에 놓여 있는 조각들은 그릴 곳이 없어 버려진다.

백페이스 도태

주요 기사: 백페이스 도태

3D 물체로는 물체 표면의 일부가 카메라를 향하고, 나머지는 카메라와 반대쪽을 향하고 있다. 즉 물체 뒤쪽에 있는 물체 앞쪽에 방해된다.만약 물체가 완전히 불투명하다면, 그 표면들은 절대 그릴 필요가 없다.이들은 정점 구불구불한 순서에 따라 결정된다. 카메라를 마주할 때 그려진 삼각형이 투영 평면에서 시계방향으로 정점을 이루면 카메라에서 표면이 멀어지면 시계 반대 방향으로 전환된다.

우연히, 이것은 또한 시야 카메라가 그 안에 있을 때 물체를 완전히 투명하게 만들 수 있다. 왜냐하면 물체의 모든 표면이 카메라로부터 멀리 떨어져 있고 렌더러에 의해 도태되기 때문이다.이를 방지하려면 물체를 양면으로 설정하거나(즉, 백페이스 도르기가 수행되지 않음) 별도의 내부 표면을 가져야 한다.

기부금 도태

종종 물체는 너무 멀리 떨어져 있어서 최종 이미지에 크게 기여하지 못한다.이 물체들은 스크린 투영이 너무 작으면 버려진다.클리핑 평면을 참조하십시오.

폐색 도태

참고 항목: Z-버퍼링 § Z-컬링

다른 불투명한 물체보다 전적으로 뒤처져 있는 물체는 도태될 수 있다.이것은 중간에서 높은 깊이의 복잡성을 가진 큰 장면의 렌더링을 빠르게 하기 위한 매우 인기 있는 메커니즘이다.다음과 같은 몇 가지 유형의 폐색 도태 접근법이 있다.

  • 잠재적으로 보이는 세트(PVS) 렌더링은 장면을 영역으로 나누고 이를 위해 가시성을 사전 계산한다.이러한 가시성 세트는 런타임에 인덱싱되어 고품질 가시성 세트(복잡한 오크러더 상호 작용에 대한 설명)를 신속하게 얻는다.
  • 포털 렌더링은 장면을 셀/섹터(룸)와 포털(도어)으로 나누고, 포털에 대해 어떤 섹터가 보이는지 클리핑하여 계산한다.

한송 장의 논문 "임의적 모델의 쌍방향 표시를 위한 효과적인 폐색 도태"는 [1]폐색 도태 접근법을 설명한다.


분열시켜 정복하다.

VSD 문학에서 인기 있는 주제는 분열과 정복이다.워녹 알고리즘은 화면을 나누는 것을 개척했다.빔추적은 가시적 볼륨을 빔으로 나누는 레이트레이싱 접근법이다.다양한 스크린 공간 분할은 타일링 또는 스크린 공간 BSP 클리핑과 같이 영역별로 고려되는 원시 요소 수를 줄이는 데 접근한다.타일링은 다른 기술에 대한 사전 처리로 사용될 수 있다.Z-버퍼 하드웨어는 일반적으로 거친 "hi-Z"를 포함할 수 있는데, 이 "hi-Z"에 대해 원시 형질을 래스터화하지 않고 조기 기각할 수 있으며, 이는 폐색 도태의 일종이다.

경계 볼륨 계층 구조(BVHs)는 장면의 공간을 세분화하는 데 종종 사용된다(예: BSP 트리, 팔진 트리, kd 트리).이를 통해 가시성 결정을 계층적으로 수행할 수 있다. 효과적으로 트리의 노드가 보이지 않는 것으로 간주되면 모든 하위 노드도 보이지 않으며, 더 이상의 처리가 필요하지 않다(모두 렌더러에 의해 거부될 수 있음).노드를 볼 수 있다고 간주할 경우 각 노드를 평가할 필요가 있다.이 횡단보도는 효과적으로 나무 산책로로서, 보이지 않는/폐쇄 또는 잎 노드에 도달하는 것이 각각 정지할지 또는 재발할지 여부를 결정한다.

참고 항목

원천

  1. ^ "Occlusion Culling with Hierarchical Occlusion Maps". www.cs.unc.edu.