KR101136200B1 - 분할된 도메인들의 중요 샘플링을 위한 시스템, 방법 및 컴퓨터 판독가능 기록 매체 - Google Patents

Abstract

분할된 도메인들의 중요 샘플링을 위한 시스템, 방법 및 컴퓨터 프로그램 제품이 제공된다. 동작에 있어서, 도메인이 복수의 세트로 분할된다. 또한, 복수의 세트 각각에 확률이 할당된다. 또한, 복수의 세트로부터 샘플들이 생성되는데, 샘플들은 대응 세트의 확률에 따라 생성된다.

Description

분할된 도메인들의 중요 샘플링을 위한 시스템, 방법 및 컴퓨터 판독가능 기록 매체{SYSTEM, METHOD, AND COMPUTER-READABLE RECORDING MEDIUM FOR IMPORTANCE SAMPLING OF PARTITIONED DOMAINS}

본 발명은 도메인의 샘플링에 관한 것으로서, 구체적으로는 분할된 도메인들의 중요 샘플링에 관한 것이다.

파티션의 각각의 세트에 대한 확률이 알려지는 분할된 도메인들의 중요 샘플링은 몬테 카를로 및 의사 몬테 카를로(quasi-Monte Carlo) 방법들에 사용된다. 몬테 카를로 방법들은 반복 랜덤 샘플링에 의존하여 그들의 결과들을 계산하는 일종의 알고리즘들이다. 몬테 카를로 방법들은 종종 물리적 및 수학적 시스템들을 시뮬레이션할 때 사용된다. 의사 몬테 카를로 방법들은 몬테 카를로 방법들과 유사하지만, 결정적 샘플들을 대신 사용하며, 이는 수렴도를 향상시킨다.

매우 자주, 컴퓨터 그래픽에서의 텍스처 광원과 같은 소정의 이산 에너지 밀도에 의해 적어도 부분적으로 함수가 정의된다. 지금까지, 분할된(또는 이산된) 도메인들의 중요 샘플링의 샘플링 속도는 충분히 최적화되지 않았다. 따라서, 이들 및/또는 다른 문제들을 해결하는 것이 필요하다.

분할된 도메인들의 중요 샘플링을 위한 시스템, 방법 및 컴퓨터 프로그램 제품이 제공된다. 동작에 있어서, 도메인이 복수의 세트로 분할된다. 또한, 복수의 세트 각각에 확률이 할당된다. 또한, 복수의 세트로부터 샘플들이 생성되는데, 샘플들은 대응 세트의 확률에 따라 생성된다.

도 1은 일 실시예에 따른, 분할된 도메인들의 중요 샘플링을 위한 방법을 나타낸다.
도 2는 다른 실시예에 따른, 허프만 트리(Huffman tree)를 이용하여 샘플들을 열거하기 위한 방법을 나타낸다.
도 3은 다른 실시예에 따른, 낮게 기대되는 트래버설(traversal) 깊이를 갖는 kd-트리들을 구성하고 그러한 kd-트리들에 대한 중요 샘플링을 행하기 위한 방법을 나타낸다.
도 4는 일 실시예에 따른, 내부 노드들이 그들의 자식들의 확률들의 합을 유지하는 확률 트리를 나타낸다.
도 5는 일 실시예에 따른, 샘플 워핑(warping)에 사용될 수 있는 도 4에 대응하는 결정 트리를 나타낸다.
도 6은 일 실시예에 따른, 1d 샘플 워핑이 사용될 때 도 5에 대응하는 각각의 노드에 대한 샘플 인터벌들의 트리를 나타낸다.
도 7은 일 실시예에 따른, 상이한 프로브들에 대한 통계를 나타내는 표를 도시한다.
도 8은 다양한 이전 실시예들의 다양한 아키텍처 및/또는 기능을 구현할 수 있는 예시적인 시스템을 나타낸다.

도 1은 일 실시예에 따른, 분할된 도메인들의 중요 샘플링을 위한 방법(100)을 나타낸다. 도시된 바와 같이, 복수의 세트를 포함하는 분할된 도메인이 생성된다. 동작 102를 참조한다. 일 실시예에서, 분할된 도메인은 도메인을 복수의 세트로 분할함으로써 생성될 수 있다.

본 설명과 관련하여, 분할된 도메인은 임의의 분할된 객체 또는 분할된 객체들의 그룹을 지칭한다. 일 실시예에서, 분할된 도메인은 임의 차원의 분할된 도메인일 수 있다. 또한, 분할된 객체들은 기하 객체들을 분할함으로써 생성될 수 있다.

본 설명과 관련하여, 분할은 복셀화를 포함하며, 세트들은 임의 차원의 공간 내의 그리드 상의 값을 나타내는 부피 요소들(즉, 복셀들)에 대응한다. 예를 들어, 각각의 복셀은 객체 또는 현상의 소정의 측정 가능한 특성, 독립 변수 또는 속성을 나타내는 관련 수치 값(또는 값들)을 갖는 부피의 양자 단위일 수 있다. 그러나, 임의의 복셀은 복셀 또는 복셀들의 그룹을 포함할 수도 있다.

복수의 세트를 포함하는 분할된 도메인이 생성되면, 복수의 세트 각각에 대해 확률이 할당된다. 동작 104를 참고한다. 또한, 복수의 세트 내에서 샘플들이 생성되는데, 샘플들은 대응 세트의 확률에 따라 생성된다. 동작 106을 참고한다.

일 실시예에서, 샘플들은 데이터 트리를 이용하여 생성될 수 있다. 예컨대, 일 실시예에서, 데이터 트리는 허프만 트리를 포함할 수 있다. 이 경우에, 허프만 트리는 (예를 들어, 복수의 세트 각각에 할당된 확률 등을 이용하여) 분할된 도메인 위에 구축될 수 있다.

옵션으로서, 허프만 트리는 단일 도메인 셀로 트래버스 다운(traverse down)될 수 있다. 일 실시예에서, 트래버스 다운은 샘플 워핑을 이용하여 수행될 수 있다. 다른 실시예에서, 트래버스 다운은 액세스할 자식 노드를 확률적으로 선택하기 위하여 허프만 트리의 각각의 내부 노드에서 랜덤 또는 의사 몬테 카를로 샘플을 생성함으로써 수행될 수 있다.

다른 예로서, 데이터 트리는 kd 트리를 포함할 수 있다. 이 경우, kd 트리는 복수의 세트 각각에 할당된 확률을 이용하여 분할된 도메인 위에 구축될 수도 있다. 또한, kd 트리는 휴리스틱(heuristic)(예컨대, 중간 분할 예측자(mid-split predictor), 엔트로피 예측자 또는 하이브리드 예측자 등)을 이용하여 구축될 수 있다. 다른 옵션으로서, kd 트리의 구축은 최소 비용 함수를 찾기 위한 검색 공간의 축소를 포함할 수 있다.

이와 같이, 각각의 셀에 할당된 확률들을 갖는 임의 차원의 복셀화된 도메인이 주어지는 경우, 임의 수의 양호하게 분포된 샘플들이 그들의 확률에 따라 복셀 셀들 내에 인출(drawing)될 수 있다. 복셀 셀들 내의 샘플들 및 도메인 위의 샘플들 양자는 전체적으로 양호하게 분포될 수 있다. 옵션으로서, 적은 수의 예측되는 트래버설 단계들을 갖는 도메인 셀들을 선택하기 위하여, 허프만 트리가 사용될 수 있다. 이 경우에, 도메인 셀들 내의 샘플들은 적절한 저-불일치(low-discrepancy) 시퀀스를 이용하여 열거될 수 있다.

본 설명과 관련하여, 저 불일치 시퀀스는, N의 모든 값에 대해, 그의 시퀀스들(x₁,..., x_N)이 작은 불일치를 갖는 특성을 갖는 임의의 시퀀스를 지칭한다. 예컨대, 저 불일치 시퀀스는 홀튼(Halton) 또는 소볼(Sobol) 시퀀스 등을 포함할 수 있다. 다른 옵션으로서, 적은 수의 예측되는 계산 단계들을 갖는 도메인 셀들을 선택하기 위하여, kd 트리가 사용될 수 있다.

이제, 전술한 프레임워크가 사용자의 요망에 따라 구현되거나 구현되지 않을 수 있는 다양한 옵션 아키텍처 및 특징과 관련하여 더 많은 예시적인 정보가 설명될 것이다. 아래의 정보는 예시적인 목적으로 설명되는 것이며, 어떠한 식으로도 제한적인 것으로 해석되지 않아야 한다는 점에 특히 유의해야 한다. 아래의 특징들 중 임의의 특징은 설명되는 다른 특징들을 배제하거나 배제하지 않고 옵션으로서 포함될 수 있다.

도 2는 다른 실시예에 따른, 허프만 트리를 이용하여 샘플들을 열거하기 위한 방법(200)을 나타낸다. 옵션으로서, 본 방법(200)은 도 1의 기능과 관련하여 구현될 수 있다. 그러나, 물론, 방법(200)은 임의의 원하는 환경에서 수행될 수도 있다. 전술한 정의들은 본 설명 동안에 적용될 수 있다는 점에도 유의해야 한다.

도시된 바와 같이, 허프만 트리가 세트들에 할당된 확률들을 이용하여 분할된 도메인 위에 구축된다. 동작 202를 참고한다. 허프만 트리가 구축된 후, 허프만 트리는 단일 도메인 세트로 트래버스 다운된다. 동작 204를 참고한다.

일 실시예에서, 허프만 트리를 단일 도메인 세트로 트래버스 다운하는 것은 샘플 워핑에 의해 달성될 수 있다. 다른 실시예에서, 허프만 트리를 단일 도메인 세트로 트래버스 다운하는 것은 다음에 방문할 자식 노드를 확률적으로 선택하기 위해 각각의 내부 노드에서 랜덤 또는 의사 랜덤 샘플을 인출함으로써 달성될 수 있다.

도메인의 하나의 세트가 허프만 트리의 리프(leaf) 레벨에 도달하면, 다음 시퀀스 샘플이 이 세트 내에 열거된다. 동작 206을 참고한다. 일 실시예에서, 다음 시퀀스 샘플은 홀튼 시퀀스 샘플을 포함할 수 있다. 다른 실시예에서, 다음 시퀀스 샘플은 소볼 시퀀스 샘플을 포함할 수 있다.

세트 내의 시퀀스 샘플의 열거에 관한 더 많은 정보는 모든 목적을 위해 본 명세서에 그 전체가 참고 문헌으로 포함되는, "COMPUTER GRAPHICS WITH ENUMERATING QMC SEQUENCES IN VOXELS"라는 제목으로 2008년 9월 30일자로 출원된 미국 특허 출원 번호 12/241,928에서 발견될 수 있다.

어느 시퀀스에서나, 확률 트리들의 리프 레벨에 대응하는 복셀들 내에 직접 의사 몬테 카를로 포인트들을 열거함으로써 분포 특성들이 얻어질 수 있다. 다음 시퀀스 샘플이 세트 내에 열거되면, 충분한 수의 샘플들이 인출되었는지가 결정된다. 동작 208을 참고한다.

충분한 수의 샘플들이 인출되지 않은 경우, 충분한 수의 샘플들이 인출될 때까지, 트리가 다시 트래버스되고, 시퀀스 샘플들이 열거된다. 이 경우에, 충분한 샘플들의 수는 샘플들을 열거하는 시스템 또는 시스템의 운영자에 의해 결정될 수 있다.

도 3은 다른 실시예에 따른, 낮게 예상되는 트래버설 깊이를 갖는 kd 트리들을 구축하고 그러한 kd 트리들에 대한 중요 샘플링을 행하기 위한 방법(300)을 나타낸다. 옵션으로서, 본 방법(300)은 도 1-2의 기능과 관련하여 구현될 수 있다. 그러나, 물론, 방법(300)은 임의의 원하는 환경에서 수행될 수도 있다. 다시, 전술한 정의들은 본 설명 동안에 적용될 수 있다.

동작에 있어서, 세트들에 할당된 확률들을 이용하여, 분할된 도메인 위에 kd 트리가 구축될 수 있다. 먼저, 전체 도메인 영역이 스택 위로 푸시될 수 있다. 동작 302를 참조한다. 이어서, 스택이 비어 있는지를 결정한다. 동작 304를 참조한다.

스택이 비어 있지 않은 경우, 스택으로부터 도메인 영역이 팝핑(popping)된다. 동작 306을 참고한다. 이어서, 도메인 영역이 리프 크기보다 큰지를 결정한다. 동작 308을 참고한다.

도메인 크기가 리프 크기보다 큰 경우, 휴리스틱을 이용하여 분할 축 및 분할 평면이 발견된다. 동작 310을 참고한다. 이 경우, 분할 평면은 각각의 내부 노드에서 발견될 수 있다.

일 실시예에서, 각각의 내부 노드에서의 분할 평면의 발견은 중간 분할 예측자, 엔트로피 예측자 또는 하이브리드 예측자 중 적어도 하나로부터 추론되는 비용 함수의 최소치의 발견을 포함할 수 있다. 일 실시예에서, 각각의 내부 노드에서의 분할 평면의 발견은 (예를 들어, 비닝(binning) 등에 의한) 검색 공간의 축소를 포함할 수 있다.

휴리스틱을 이용하여 분할 축 및 분할 평면이 발견되면, 내부 노드가 생성되고, 분할 축 및 분할 평면이 저장된다. 동작 312를 참고한다. 이어서, 자식 도메인 영역들이 스택 위로 푸시된다. 동작 314를 참고한다.

동작 308에서 도메인 영역이 리프 크기보다 크지 않은 것으로 결정되는 경우, 리프 노드가 생성된다. 동작 316을 참고한다. 이어서, 다시 스택이 비어 있는지를 결정한다.

스택이 비어 있는 경우, kd 트리를 트래버스하여 샘플을 취득한다. 동작 318을 참조한다. 이어서, 충분한 수의 샘플들이 취득되었는지를 결정한다. 동작 320을 참고한다.

충분한 수의 샘플들이 인출되지 않은 경우, 충분한 수의 샘플들이 인출될 때까지 트리가 다시 트래버스된다. 이 경우, 충분한 샘플들의 수는 샘플들을 열거하는 시스템 또는 시스템의 운영자에 의해 결정될 수 있다.

이와 같이, 분할된 도메인들을 샘플링하는 데 사용될 수 있는 kd 트리들이 생성될 수 있다. 복셀 확률들에 대응하는 샘플들을 생성하기 위해, 샘플 생성 스테이지에서 적은 수의 예상되는 트래버설 단계들을 갖는 kd 트리들이 생성될 수 있다. 더욱이, 다양한 실시예에서, 상이한 휴리스틱을 이용하여, 트리들을 생성하고, 샘플링을 수행할 수 있다. 일 실시예에서, 엔트로피 기반 휴리스틱이 사용될 수 있다.

또한, 다른 실시예에서, 의사 몬테 카를로 또는 저 불일치 시퀀스들에 기초하여 복셀들 내의 샘플들이 열거될 수 있다. 이 경우, 전술한 바와 같이, 허프만 트리를 이용하여 복셀들을 선택할 수 있다. 결과적으로, 복셀 선택을 위한 트래버설 단계들의 예상 수가 가능한 한 적을 수 있다.

어느 경우에나, 분할된 도메인에 걸쳐 양호하게 분포된 샘플 포인트들이 생성되어, 적분 추정의 수렴도가 높아질 수 있다. 일 실시예에서, 이러한 기술들은 렌더러들(예컨대, 광선 추적 기반 렌더러 등)에서의 이미지 기반 조명과 관련하여 이용될 수 있으며, 환경 맵들이 광원으로 사용된다. 추가 응용들은 복셀 셀들에 기초하는 다차원 파티클 맵들, 부피 데이터 가시화 및 일반적으로 다차원 분할된 도메인들의 적분의 계산을 포함할 수 있다.

각각의 복셀에 대한 확률 또는 근사 확률이 알려지는 분할된 도메인들의 중요 샘플링은 종종 몬테 카를로 또는 의사 몬테 카를로 기술들에 사용되는 표준 기술이다. 매우 자주, 컴퓨터 그래픽에서의 텍스처(환경) 광원과 같은 소정의 이산 에너지 밀도에 의해 적어도 부분적으로 함수가 정의된다. 이산 도메인들의 중요 샘플링의 샘플링 속도는 확률 트리들을 이용하여 예상되는 트래버설 깊이를 최소화함으로써 최적화될 수 있다. 다양한 실시예에서, 다양한 기술들을 이용하여, 영역들의 확률들에 기초하여 또는 이들 사이의 공간 접속을 통합함으로서 이산 도메인으로부터 샘플링을 수행할 수 있다.

일 실시예에서, 누적 분포 함수(CDF)를 이용하여, 이벤트의 이산 세트로부터 선택할 수 있다. 예컨대, i= 1,..., n에 대해, p_i가 i 번째 이벤트의 확률을 나타내는 경우, 대응하는 CDF는 i = 1,..., n에 대해 c₀ = 0 및 c_i := c_{i -1} + p_i로서 귀납적으로 구축된다.

그러면, 샘플링은 간단하며,

인 경우에 의사 난수

이 i 번째 이벤트로 맵핑된다. 또한, 이진 검색과 연계하여 사용되는 CDF들도 리스케일링이 필요하지 않은 중간 분할 구성 및 특수화된 트래버설을 이용하는 1d 트리로서 볼 수 있다. CDF들의 수치 정밀도는 이벤트들의 수의 증가에 따라 점점 더 불안정해질 수 있는 누적 합계에 의해 제한된다. 이벤트들이 k 차원 도메인들(예를 들어, 그리드 내의 복셀들)에 대응하는 경우, k개의 새로운 의사 난수들이 복셀 내의 계층화를 위해 사용될 수 있다.

다른 실시예에서는, 확률 트리를 이용하여, 이벤트들의 이산 세트로부터 샘플링할 수 있다. 확률 트리는 각각의 노드에서 모든 자식이 확률들을 할당받는 트리이다. 즉, 각각의 노드는 모든 자식에 대해 1로 합계된다. 리프에 대한 확률은 트래버설 시에 만나는 모든 확률의 곱이다.

일 실시예에서, 트래버설 단계들의 예상 수와 관련하여 최적의 확률 트리는 그리디 허프만 코드 알고리즘을 이용하여 구축될 수 있다. 이 알고리즘은 단일 이벤트들의 확률들에 대응하는 노드들에서 시작된다. 이어서, 최저 확률들을 갖는 2개의 노드가 노드들의 풀로부터 연속 선택되어 제거된다. 이러한 노드들에 대한 부모 노드가 생성되고, 2개의 자식의 확률들의 합을 할당받는다.

이러한 부모 노드가 노드들의 풀 내에 삽입된다. 알고리즘은 풀 내에 하나의 노드 리프만이 존재할 때 종료되는데, 이는 트리의 루트 노드이다. 옵션으로서, 최저 확률을 갖는 노드들의 선택은 우선 순위 큐를 이용하여 효율적으로 구현될 수 있다. 허프만 트리 구축 알고리즘을 위한 의사 코드가 일 실시예에 따라 표 1에 나타나 있다.

(트래버설 단계들의 예상 수에 대응하는) 허프만 코드의 평균 코드 워드 길이 l(p₁,..., p_n)은

에 의해 한정되며, 여기서

엔트로피이다.

확률 트리의 분기 인자가 최대 b인 경우(즉, 각각의 노드가 최대 b개의 자식을 가짐), 유사한 결과가 적용된다. 이어서, 허프만 알고리즘은 최저 확률들을 갖는 b개의 노드를 선택한다. 결과적으로, log₂는 log_b로 교체되어, log₂(b)의 상수 인자에 의해 예상 트래버설 깊이가 감소된다.

kd 트리는 모든 분할 평면이 축 정렬되는 k 차원의 데이터에 대한 공간 분할 트리이다. 옵션으로서, kd 트리는 이진 트리일 수 있다. 트리의 각각의 노드에서, 정확히 1 차원이 대응 축을 따르는 특정 위치에서 분할될 수 있으며, 이는 노드 내에 저장될 수 있다. 확률 kd 트리의 경우, 이러한 위치는 좌측 자식의 확률에 대응할 수 있다.

일반적으로, kd 트리들은 공간 연결이 유지되는 일반 확률 트리들의 제한이다. 그러나, 그러한 공간 연결이 이용될 수도 있다. kd 트리 구성의 한 버전은 중간 분할 트리이다. 중간 분할 트리를 이용하는 경우, 중간에서 최장축이 분할된다. 표 2는 일 실시예에 따라 최장 크기의 축을 따라 최소 x₀ = (x₀ ⁽⁰⁾,..., x₀ ^(k-1)) 및 최대 x₁ = (x₁ ⁽⁰⁾,..., x₁ ^(k-1))(i = 0,..., k-1에 대해 x₀ ⁽ⁱ⁾<x₁ ⁽ⁱ⁾)에 의해 정의되는 k 차원 영역을 분할하기 위한 알고리즘을 나타낸다.

중간 분할 kd 트리에 대해, 예상 트래버설 깊이 l(p₁,..., p_n)은 log₂(n)≤l(p₁,..., p_n)<log₂(n) + 1에 의해 경계가 정해진다. p_i = 1/n(i = 1,..., n)에 대해, 이들 경계는 전술한 바와 같이 H(p₁,..., p_n)≤l(p₁,..., p_n)≤H(p₁,..., p_n) + 1과 동일하다는 점에 유의해야 한다. 따라서, 결과적인 확률 트리는 최적에 가깝다. 영역들이 0의 확률을 갖는 경우, 이들 영역은 트리 생성으로부터 제거될 수 있으며, 대응 트리들은 더 얕다.

상이한 기술들이 중요 샘플링을 위해 주어진 확률 트리를 사용하도록 구현될 수 있다. 확률 트리 내의 리프들이 k 차원 복셀들에 대응하는 경우, 적어도 k개의 의사 난수들이 샘플링에 사용될 수 있다. 더욱이, 트리는 확률적 방식으로 트래버스될 수 있다. 즉, 자식이 그의 확률에 따라 선택될 수 있다. 일부 예들에서는, 자식 결정에 대해 하나의 의사 난수를 사용하는 간단한 접근법이 옵션이 아닐 수 있는데, 이는 의사 난수들의 생성이 비용이 많이 들고, 최대 d개의 수가 필요하기 때문이며, 여기서 d는 트리의 최대 리프 깊이를 나타낸다.

또 하나의 접근법은 완전한 트래버설에 대해 하나의 의사 난수만을 사용하는 것이다. 각각의 트래버설 단계에 대해, 좌측 및 우측 자식의 확률들 p_i 및 p_r(p_i + p_r = 1)은 트래버스할 자식을 선택하는 데 사용된다. 이 경우, ξ∈[0, 1)은 현재 샘플을 나타낼 수 있다. ξ<p_l인 경우, 좌측 자식이 선택되고, 샘플은 ξ' = ξ/p_l로 리스케일링된다. 그렇지 않은 경우, 우측 자식이 선택될 수 있으며, 샘플은 ξ' = (ξ-p_l)/p_r로 리스케일링될 수 있다.

다음 트래버설 단계에서, ξ'∈[0, 1)은 의사 랜덤 샘플로서 사용된다. 이러한 스킴을 사용하여, k + 1 차원들에서 계층화되는 샘플의 한 성분이 트래버설을 위해 사용될 수 있으며, 나머지 k개의 성분은 복셀 내에서 양호한 계층을 산출한다. 이 경우, 각각의 리스케일링 이벤트에서 소정량의 정밀도가 손실될 수 있다.

수치 정밀도를 향상시키기 위하여, 둘 이상의 의사 난수가 사용될 수 있다(예를 들어, kd 트리에 대해 k개, 차원마다 하나, 기타 등등). 이어서, 의사 난수가 리스케일링되는 각각의 노드의 분할 축이 결정될 수 있다.

일부 예들에서, 트리 트래버설로부터 복셀 샘플링을 분리하는 것은 단위 하이퍼큐브에서 완전한 도메인으로의 맵핑을 스크램블할 수 있다. 즉, 맵핑은 임의적일 수 있으며, 샘플들의 공간 근접성을 유지하지 않을 수 있다. 환경 맵의 샘플링과 관련하여, 포인트 세트의 계층화 특성들은 픽셀에 적용되지만, 환경 맵에는 전적으로 적용되지 않는다.

고전적인 몬테 카를로 샘플링의 경우, 이것은 일반적으로 문제가 되지 않는데, 이는 임의성이 동일하게 유지되기 때문이다. 그러나, 의사 몬테 카를로 시퀀스들에 대해, 이것은 성능 저하 및 더 많은 아티팩트로 이어질 수 있다.

소정 포인트 세트들의 계층화 특성들을 이용할 수 있도록 하기 위하여, 그러한 특성들은 [0, 1)^k로부터의 값들을 중요 샘플링 스킴에 의해 표현되는 변환된 도메인으로 맵핑하는 동안에 유지될 수 있다. 일반적인 확률 트리들과 달리, kd 트리들은 샘플링 동안 이동될 수 있는 공간 연결의 부분들을 유지한다. 포인트들의 계층화 특성들을 계속 유지하면서 중요 샘플링을 위해 kd 트리들을 트래버스하기 위한 하나의 인기 있는 알고리즘은 샘플 워핑이다.

샘플 워핑 알고리즘은 스마트 리스케일링에 의한 복셀 내의 트래버싱 및 계층화 양자를 위해 오리지널 포인트 세트를 사용한다. 이진 kd 트리에 대한 샘플 워핑 알고리즘의 일례가 표 3에 나타나 있다.

표 3에 나타낸 알고리즘은 리프에 대한 위치들이 저장되도록 구현된다. 다른 실시예에서, 내부 노드들은 분할 축에 대한 위치만을 저장할 수도 있으며, 이는 원하는 범위로 직접 변환하는 데 사용될 수 있다.

그러나, k>1인 경우, 맵핑은 불연속적일 수 있으며, 소정의 유용한 특성들(예를 들어, 최소 거리 등)이 유실될 수 있다. 또한, 리스케일링 프로세스는 트리가 깊은 경우에 심각한 비트 손실을 겪을 수 있다. 일반적으로, 알고리즘들은 일반 해상도의 복셀화를 양호하게 수행하며, 진보적인 의사 몬테 카를로 적분에 유용하다.

일부 예에서는, 확률 트리들의 리프 레벨에 대응하는 복셀들 내에 직접 의사 몬테 카를로 포인트들 또는 저 불일치 시퀀스들을 열거함으로써 매우 양호한 분포 특성들이 얻어질 수 있다. 일 실시예에서, 홀튼 또는 소볼 저 불일치 시퀀스 알고리즘들이 그러한 작업(전술한 모든 샘플링 작업을 포함함)에 이용될 수 있다.

먼저, 복셀이 그의 확률에 따라 선택될 수 있다. 이것은 트래버설 차원들에 대해 계층화된 랜덤 샘플링을 이용함으로써 가능하다. 복셀이 선택된 후, 복셀에 대한 다음 의사 몬테 카를로 포인트가 생성된다. 이것은 상기 개수의 이전 생성 샘플들의 저장을 필요로 할 수 있다.

이러한 스킴의 결과는 전체 도메인에 걸쳐 매우 밀도 높은 의사 몬테 카를로 샘플 세트를 생성한 후에 거절 샘플림과 유사하게 그들의 확률에 따라 영역들을 선택적으로 박화(thin out)하는 것과 비교될 수 있다. 이러한 알고리즘은 kd 트리만이 아니라 임의의 확률 트리 상에서 이용될 수 있다. 예를 들어, 알고리즘은 소정의 경우에 예상 트래버설 단계들의 수와 관련하여 최적일 수 있는 허프만 트리 상에서 이용될 수 있다. 이것은 알고리즘이 트리 노드 영역들의 공간 연결에 의존하지 않기 때문에 가능하다. 따라서, 다음 샘플을 생성할 복셀을 선택하는 것이 이론적으로 가능한 정도로 빠르게 된다.

그러나, 트래버설 차원들에 걸쳐 계층화를 수행하기 위하여, 샘플들의 수 또는 각각의 패스에 대한 샘플들의 수가 미리 알려져야 한다. 또한, 일부 예에서는, 추가적인 샘플 성분들을 생성하는 것이 필요한 전 기능(full-featured) 의사 몬테 카를로 추정기 내에 이러한 스킴을 통합하기가 어려울 수 있다. 도메인의 샘플링은 전체 시스템의 작은 부분만을 나타낼 수도 있으므로, 소정 인스턴스들(즉, 의사 몬테 카를로 또는 저 불일치 시퀀스의 인덱스들)이 이전에 사용되었을 수 있다.

이어서, 복셀 내에 다음 샘플을 열거하기 위해 상이한 사례가 이용될 때, 상관 아티팩트들이 나타날 수 있다. 또한, 이후에 추가 샘플 성분들을 생성하기 위해 어떤 사례를 이용해야 할지가 불명확할 수 있다.

임의 서브트리 T에 대해, T_l은 좌측 자식 서브트리로, T_r은 우측 자식 서브트리로 각각 정의될 수 있다. E[T]로 표시되는 T에 대한 트래버설 단계들의 예상 수는 E[T] = 1 + p_l?E[T_l] + p_r?E[T_r]로서 귀납적으로 나타낼 수 있으며, 여기서 p_l 및 p_r은 서브트리들의 확률들이다.

매우 보편적인 도메인 크기 및 차원들에 대해 역추적(backtracking)을 통한 모든 가능한 분할에 대한 포괄적인 귀납적 검색이 가능할 수 있다. 동적 프로그래밍은 예상되는 트래버설 길이의 모든 가능한 서브트리를 저장하기 위해 표를 이용하여 해결될 최적 kd 트리를 찾는 것을 가능하게 한다. 리프 레벨에서 시작하여, 표 내의 E[T_l] 및 E[T_r]를 탐색하면서, 모든 가능한 분할 평면에 대해 반복하여 E[T] = 1 + p_l ?E[T_l] + p_r?E[T_r]의 최소치를 찾음으로써 예상 수의 트래버설 단계들이 평가될 수 있는데, 이는 이들이 이미 계산되었기 때문이다.

이러한 기술의 메모리 요구 및 계산 노력은 O(r₁ ²,..., r_k ²)이며, 여기서 r_i는 차원 i를 따른 해상도이다. 일부 예들에서, 이것은 적은 해상도들 및 적은 차원들에 대해서만 가능할 수 있다. 따라서, 분할은 도메인 크기 및 확률로부터 도출되는 국지적 정보만을 이용하는 것에 기초하여 결정될 수 있다.

일 실시예에서, 양 자식들은 중간 분할 예측자 휴리스틱을 이용하여 구축될 수 있다. 값 E[T]는 중간 분할 kd 트리에 대해 분석적으로 표현될 수 있으므로,

(m(T)는 T 내의 리프들의 수)가 계산될 수 있다.

이 값들을 실제로 예상되는 트래버설 깊이에 대한 예측자로서 사용할 경우, 식 1로 표시되는 바와 같이, 확률 및 도메인 크기만을 이용하여 분할 평면을 선택하기 위해 휴리스틱이 제공될 수 있다.

일부 예들에서는, 수학식 1에 표시된 휴리스틱을 이용하여, 중간 분할 휴리스틱보다 다소 양호한 kd 트리들을 생성할 수 있다. 다른 옵션으로서, 더 간단한 휴리스틱이 사용될 수 있다. 수학식 2는 일 실시예에 따른 다른 휴리스틱의 예를 나타낸다.

다른 실시예에서는, 서브트리들의 엔트로피에 기초하는 휴리스틱이 사용될 수 있다. 예를 들어, 양 자식들에 대해 허프만 트리들이 생성되는 경우, 예상되는 트래버설 깊이는 수학식 3으로 표시된 바와 같이 추정될 수 있으며, 여기서 H(T_l) 및 H(T_r)은 각각 좌측 및 우측 서브트리 내의 리프들의 엔트로피이다.

서브트리 내의 확률들의 분포에 따라, 예상 트래버설 깊이에 대한 개선은 노력할 가치가 없을 수 있다. 특히, 영역 내에 거의 동일한 분포가 존재하는 경우, 중간 분할이 최적에 가까울 수 있다.

영역의 엔트로피는 더 비싼 휴리스틱이 얼마나 유망한지에 대한 매우 강력한 척도를 제공한다. 최대 엔트로피

와 H(T)의 비교에 기초하는 기준이 적용될 수 있다. 예를 들어, 더 비싼 엔트로피 예측자 휴리스틱은

인 경우에 적용될 수 있으며(c<1은 사용자에 의해 제어되는 임계 인자임), 달리는 간단한 중간 분할을 수행할 수 있다. 이와 같이, 수행이 가장 유망한 경우에 노력이 투입될 수 있다. 다른 실시예에서, 최적의 kd 트리는 다운 샘플링된 이미지의 버전에 대해 구축될 수 있으며, 결과적인 트리의 최고 레벨들에 대해 더 간단한 휴리스틱이 이용될 수 있고, 이어서 전 해상도(full-resolution) 입력으로 스위칭될 수 있다.

도메인의 임의의 영역들에 대한 확률 및 엔트로피를 평가하기 위하여, SAT(summed-area table)가 사용될 수 있다. 옵션으로서, 그러한 SAT는 현재의 그래픽 처리 유닛(GPU)들의 스캔 프리미티브(scan primitive)를 이용하여 병렬로 빠르게 구축될 수 있다.

대부분의 예들에서, 엔트로피는 한 세트의 확률들(p_i)에 대해 정의되며,

이다. 도메인의 임의의 영역들에 대해, 확률들은 상수 인자

을 이용하여 재정규화될 수 있다. SAT는 다음과 같은 이유로 엔트로피 값들에 대해 사용될 수 있다.

값들

및

모두는 그들 각각의 SAT들로부터 검색될 수 있다.

리스케일링에 의해 1의 샘플 수가 모든 트래버설 단계에 사용되는 경우, 정밀도 손실을 고려해야 한다. 일례로, 이진 트리에서의 확률 중간 분할이 고려될 수 있으며, 양 자식들은 모든 노드에서 0.5의 확률을 갖는다. 1의 의사 난수를 갖는 트래버설은 트래버설 단계당 정확히 1비트의 비트 손실을 유발할 수 있다.

예를 들어, 일반적인 환경 맵은 1024 x 1024의 해상도를 가질 수 있으며, 약 20 깊이의 트리를 제공할 수 있다. 이러한 시나리오에서는, 트래버설 동안에 적어도 20개의 비트가 손실될 수 있으며, 이는 본질적으로 2배 정밀도를 단일 정밀도의 부동 소수점 수로 감소시킬 수 있다.

샘플 워핑 알고리즘이 이용되는 경우에 유사한 정밀도 문제가 고려되어야 한다. 이러한 시나리오에서는, kd 트리의 각각의 차원에 대해 1의 샘플 수가 사용될 수 있으며, 트래버싱으로부터 남겨진 비트들이 샘플들을 리프 내에 배치하는 데 사용될 수 있으며, 이는 리프에서의 정밀도를 감소시킨다. 물론, 복셀들에서 실제 도메인으로의 맵핑에 대해(예를 들어, 경도/위도 환경 맵 등에 대해) 적절한 추가 정보의 경우, 비트 손실의 예상은 더 복잡할 수 있다.

그러나, 2배 정밀도 부동 소수점은 샘플 워핑 알고리즘이 성공적으로 사용될 수 있을 만큼 충분히 정밀할 수 있다. 예상되는 트래버설 단계들의 수를 줄이는 것은 평균 비트 손실을 줄일 수 있다.

일 실시예에서, 행/열 SAT가 사용될 수 있다는 점에 유의해야 한다. 행/열 SAT를 사용하는 경우, 확률/엔트로피 평가마다 평가 작업들이 감소될 수 있는데, 이는 각각의 축이 전체 엔트로피 예측자 휴리스틱 계산 동안에 트래버스되기 때문이다.

또한, 리프 확률들은 일반적으로 작고, 정확한 값들에 종속되지 않으므로, 부동 소수점 수들에 대한 빠르고 근사적인 log₂ 구현이 이용될 수 있다.

내부 노드들은, 단일 "분할 평면"만이 저장되고, 다음 자식에 대한 결정이 CDF들과 유사하게 비교 이하로 단순화되는 방식으로 리스케일링될 수 있다. 각각의 노드에 대해 가능한 샘플들의 인터벌이 공지되므로, 이러한 인터벌 내의 분할 평면은 수학식 4에 나타난 바와 같이 자식들의 확률들에 따라 계산될 수 있으며, s는 분할 위치를 나타내고, [I₀, I₁)은 현재 노드에서 가능한 샘플들의 인터벌을 나타내며, p_l 및 p_r은 (정규화되지 않은) 자식들의 확률들을 나타낸다.

이어서, 각각의 리프는 샘플을 [0, 1)로 정확하게 리스케일링하기 위하여 I₀ 및 인자 I/(I_l - I₀)을 저장할 수 있다. 이와 같이, 전체 트래버설에 대해 샘플 차원마다 단일 감산 및 승산만이 수행된다.

다른 옵션으로서, 축을 따라 비용 함수에서의 단조가 취해질 수 있다. 그렇지 않을 수도 있지만, 국지적 최소가 전체적 최소보다 나쁘지 않을 수 있다. 중간 분할에서 시작하여, 비용 함수들이 상승하기 시작할 때까지 좌측 또는 우측으로 계속 진행한 후에, 발견된 최소를 취함으로써, 최소 검색이 더 일찍 중지되게 할 수 있다. 그러나, 일 실시예서는, 비용 함수 평가들의 수를 줄이기 위하여 비닝이 이용될 수도 있다.

도 4는 일 실시예에 따른, 내부 노드들이 그들의 자식들의 확률들의 합을 유지하는 확률 트리(400)를 나타낸다. 도 5는 일 실시예에 따른, 샘플 워핑에 사용될 수 있는 도 4에 대응하는 결정 트리(500)를 나타낸다. 도 6은 일 실시예에 따른, 1d 샘플 워핑이 사용되는 도 5에 대응하는 각각의 노드에 대한 샘플 인터벌들의 트리(600)를 나타낸다. 고속 샘플 워핑 기술을 위해, 분할 평면들은 이러한 이터벌들의 중심에 설정될 수 있다.

도 7은 일 실시예에 따른, 상이한 프로브들에 대한 통계를 나타내는 표(700)이다. 옵션으로서, 표(700)는 도 1-6의 기능 및 아키텍처와 관련하여 고찰될 수 있다. 그러나, 물론, 표(700)는 임의의 원하는 환경과 관련하여 고찰될 수 있다. 또한, 전술한 정의들이 본 설명 동안에 적용될 수 있다는 점에 유의해야 한다.

표(700)는 크기 64 x 32의 상이한 프로브들에 대한 통계를 나타낸다. 이 예에서, 사용되는 랜덤 이미지는 균일한 랜덤 픽셀들로 구성되는 반면, 계층화된 이미지는 배경보다 훨씬 밝은 소정의 랜덤 픽셀들을 포함한다. 비교를 위해, 표(700)는 이미지 기반 조명 등을 위해 일련의 높은 동적 범위 이미지들에 대한 다양한 트리 구축 알고리즘들을 이용한 통계를 나타낸다. 옵션으로서, 환경 맵이 HDR 비디오이고, 단일의 렌더링된 이미지의 셔터 시간이 비디오의 다수 프레임에 걸칠 때에는, 3d 트리들이 사용될 수 있다. 이어서, 환경 광선들은 조명이 가장 기여하는 순간들을 특징화할 것이다.

도 8은 다양한 이전 실시예들의 다양한 아키텍처 및/또는 기능이 구현될 수 있는 예시적인 시스템(800)을 나타낸다. 도시된 바와 같이, 통신 버스(802)에 접속되는 적어도 하나의 호스트 프로세서(801)를 포함하는 시스템(800)이 제공된다. 시스템(800)은 또한 주 메모리(804)를 포함한다. 랜덤 액세스 메모리(RAM)의 형태를 가질 수 있는 주 메모리(804) 내에 제어 논리(소프트웨어) 및 데이터가 저장된다.

시스템(800)은 또한 그래픽 프로세서(806) 및 디스플레이(800), 즉 컴퓨터 모니터를 포함한다. 일 실시예에서, 그래픽 프로세서(806)는 복수의 쉐이더(shader) 모듈, 래스터화 모듈 등을 포함할 수 있다. 상기 모듈들의 각각은 그래픽 처리 유닛(GPU)을 형성하기 위해 단일 반도체 플랫폼 상에 위치할 수도 있다.

본 설명에서, 단일 반도체 플랫폼은 유일한 반도체 기반 집적 회로 또는 칩을 지칭한다. 단일 반도체 플랫폼이라는 용어는 온칩 동작을 모방하고 통상의 중앙 처리 유닛(CPU) 및 버스 구현의 이용을 통해 실질적인 개량을 제공하는 향상된 접속성을 갖는 다중 칩 모듈들을 지칭할 수도 있다. 물론, 다양한 모듈들이 사용자의 요구에 따라 개별적으로 또는 반도체 플랫폼들의 다양한 조합 내에 위치할 수도 있다.

시스템(800)은 보조 저장 장치(810)도 포함할 수 있다. 보조 저장 장치(810)는 예를 들어 하드 디스크 드라이브 및/또는 플로피 디스크 드라이브, 자기 테이프 드라이브, 컴팩트 디스크 드라이브 등을 나타내는 이동식 저장 드라이브를 포함한다. 이동식 저장 드라이브는 공지된 방식으로 이동식 저장 유닛으로부터 판독하고 그에 기록한다.

컴퓨터 프로그램들 또는 컴퓨터 제어 논리 알고리즘들이 주 메모리(804) 및/또는 보조 저장 장치(810)에 저장될 수 있다. 그러한 컴퓨터 프로그램들은 실행 시에 시스템(800)이 다양한 기능을 수행하게 할 수 있다. 메모리(804), 저장 장치(810) 및/또는 임의의 다른 저장 장치는 컴퓨터 판독 가능 매체들의 가능한 예들이다.

일 실시예에서, 다양한 이전 도면들의 아키텍처 및/또는 기능은 호스트 프로세서(801), 그래픽 프로세서(806), 호스트 프로세서(801) 및 그래픽 프로세서(806) 양자의 능력들의 적어도 일부를 수행할 수 있는 집적 회로(도시되지 않음), 칩셋(즉, 관련 기능 등을 수행하기 위한 유닛으로 동작하고 팔리도록 설계된 집적 회로들의 그룹) 및/또는 그러한 문제를 위한 임의의 다른 집적 회로와 관련하여 구현될 수 있다.

그러나, 다양한 이전 도면들의 아키텍처 및/또는 기능은 범용 컴퓨터 시스템, 회로 보드 시스템, 오락 전용의 게임 콘솔 시스템, 주문형 시스템 및/또는 임의의 다른 원하는 시스템과 관련하여 구현될 수도 있다. 예컨대, 시스템(800)은 데스크탑 컴퓨터, 랩탑 컴퓨터, 및/또는 임의의 다른 타입의 논리의 형태를 취할 수 있다. 그러나, 시스템(800)은 개인용 휴대 단말기(PDA) 장치, 이동 전화 장치, 텔레비전 등을 포함하지만, 이에 한정되지 않는 다양한 다른 장치의 형태를 취할 수도 있다.

또한, 도시되지 않았지만, 시스템(800)은 통신을 위해 네트워크(예컨대, 전기 통신 네트워크, 근거리 네트워크(LAN), 무선 네트워크, 인터넷과 같은 광역 네트워크(WAN), 피어 대 피어 네트워크, 케이블 네트워크 등)에 결합될 수 있다.

위에서 다양한 실시예가 설명되었지만, 이들은 제한이 아니라 예시적으로 제공되었음을 이해해야 한다. 따라서, 바람직한 실시예의 넓이 및 범위는 전술한 예시적인 실시예들 중 어느 것에 의해서도 한정되지 않아야 하며, 아래의 청구항들 및 그들의 균등물들에 따라서만 정의되어야 한다.

801: 중앙 프로세서
802: 버스
804: 주 메모리
806: 그래픽 프로세서
808: 디스플레이
810: 보조 저장 장치

Claims (20)

1. 도메인을 복수의 세트로 분할하는 단계;
   상기 복수의 세트의 각각에 확률을 할당하는 단계;
   상기 복수의 세트로부터, 대응하는 세트의 확률에 따라 샘플들을 생성하는 단계 - 상기 샘플들은 데이터 트리를 이용하여 생성되고, 상기 데이터 트리는 허프만 트리(Huffman tree)를 포함함 - ; 및
   저 불일치 시퀀스(low discrepancy sequence)를 이용하여 상기 샘플들을 열거하는(enumerating) 단계
   를 포함하는 방법.
2. 삭제
3. 삭제
4. 삭제
5. 제1항에 있어서, 상기 허프만 트리는 상기 분할된 도메인 상에 구축되는 방법.
6. 제5항에 있어서, 상기 허프만 트리는 상기 복수의 세트의 각각에 할당된 확률을 이용하여 상기 분할된 도메인 상에 구축되는 방법.
7. 제6항에 있어서, 상기 허프만 트리를 단일 도메인 세트로 트래버스 다운(traverse down)하는 단계를 더 포함하는 방법.
8. 제7항에 있어서, 상기 트래버스 다운은 샘플 워핑(sample warping)을 이용하여 수행되는 방법.
9. 제7항에 있어서, 액세스할 자식 노드를 그의 확률에 따라 선택하기 위하여 허프만 트리의 각각의 내부 노드에서 랜덤 또는 의사 몬테 카를로 샘플(random or quasi-Monte Carlo sample)을 생성함으로써 상기 트래버스 다운이 수행되는 방법.
10. 제7항에 있어서, 충분한 수의 샘플들이 생성되었는지를 결정하는 단계를 더 포함하는 방법.
11. 제10항에 있어서, 상기 저 불일치 시퀀스는 홀튼 시퀀스(Halton sequence) 또는 소볼 시퀀스(Sobol sequence) 중 하나를 포함하는 방법.
12. 제1항에 있어서, 상기 데이터 트리는 kd 트리(kd-tree)를 포함하는 방법.
13. 제12항에 있어서, 상기 kd 트리는 상기 분할된 도메인 상에 구축되는 방법.
14. 제13항에 있어서, 상기 kd 트리는 상기 복수의 세트의 각각에 할당된 확률을 이용하여 상기 분할된 도메인 상에 구축되는 방법.
15. 제14항에 있어서, 상기 kd 트리는 휴리스틱(heuristic)을 이용하여 구축되는 방법.
16. 제15항에 있어서, 상기 휴리스틱은 중간 분할 예측자(mid-split predictor), 엔트로피 예측자 또는 하이브리드 예측자 중 하나를 포함하는 방법.
17. 제15항에 있어서, 상기 kd 트리의 구축은 최소 비용 함수를 찾기 위한 검색 공간을 줄이는 단계를 포함하는 방법.
18. 제1항에 있어서, 적은 수의 트래버설(traversal) 단계들을 갖는 도메인 세트들을 선택하는 단계를 더 포함하는 방법.
19. 컴퓨터 프로그램 제품을 저장한 컴퓨터 판독가능 기록 매체로서,
    상기 컴퓨터 프로그램 제품은,
    도메인을 복수의 세트로 분할하기 위한 컴퓨터 코드;
    상기 복수의 세트의 각각에 확률을 할당하기 위한 컴퓨터 코드;
    상기 복수의 세트로부터, 대응하는 세트의 확률에 따라 샘플들을 생성하기 위한 컴퓨터 코드 - 상기 샘플들은 데이터 트리를 이용하여 생성되고, 상기 데이터 트리는 허프만 트리를 포함함 - ; 및
    저 불일치 시퀀스를 이용하여 상기 샘플들을 열거하기 위한 컴퓨터 코드
    를 포함하는 컴퓨터 판독가능 기록 매체.
20. 도메인을 복수의 세트로 분할하고, 상기 복수의 세트의 각각에 확률을 할당하고, 상기 복수의 세트로부터, 대응하는 세트의 확률에 따라 샘플들을 생성하고 - 상기 샘플들은 데이터 트리를 이용하여 생성되고, 상기 데이터 트리는 허프만 트리를 포함함 - , 저 불일치 시퀀스를 이용하여 상기 샘플들을 열거하기 위한 프로세서
    를 포함하는 장치.

Images