원문 : http://www.cemyuksel.com/cyCodeBase/soln/poisson_disk_sampling.html
소스 코드 : https://github.com/cemyuksel/cyCodeBase/
논문 : http://www.cemyuksel.com/research/sampleelimination/
주의 : 번역이 개판이므로 이상하면 원문을 참고하세요.
주의 : 허락받고 번역한 것이 아니므로 언제든 내려갈 수 있습니다.
푸아송 디스크 샘플링은 컴퓨터 그래픽스와 다른 분야들에서 다양한 용도로 사용됩니다. 여기에서 필자는 cySampleElimination 코드 릴리스를 사용하여 모든 샘플링 문제를 위해 푸아송 디스크 샘플 집합을 생성하는 방법에 대해서 설명하고자 합니다.
1. What is Poisson Disk Sampling?
푸아송 디스크 샘플 셋( set )에서 두 개의 샘플들은 서로 가까워지지 않습니다. 가장 가까운 거리가 푸아송 디스크 반지름( radius )로 정의되는데, 이는 두 개의 가장 가까운 샘플들 사이의 거리의 절반입니다. 일반 랜덤( regular random ) 샘플링과 비교했을 때, 푸아송 디스크 샘플 셋들은 샘플링 영역( domain ) 전체에서 더 많은 균일한( uniform ) 샘플 분포( distribution )을 제공합니다.
|
위의 그림은 1000 개의 랜덤 샘플들과 1000 개의 푸아송 디스크 샘플들을 비교한 것입니다. 푸아송 디스크 샘플 점들은 샘플링 영역에서 더 고르게 분포되어 있으며, 너무 가까워지는 샘플 점들이 존재하지 않음을 알 수 있습니다. 하지만 랜덤 샘플들은 클러스터( cluster )를 생성하며, 샘플 사이에 상대적으로 큰 빈 공간들이 존재합니다. 이는 이 예제에서 사용된 특정 랜덤 넘버 생성기에 국한된 것은 아닙니다. 균일한( uniform ) 랜덤 샘플들은 고른 샘플 배치 확률( probability )을 제공하지만, 샘플링 영역에 대한 고른 커버리지( coverage )를 제공하지는 않습니다.
푸아송 디스크 샘플 셋들은 샘플 점들에 대한 훌륭한 분포를 제공하는 것 외에, 몬테 카를로( Monte Carlo ) 샘플링을 사용해 우수한 수렴( convergence ) 특성을 제공합니다. 같은 개수의 푸아송 디스크 샘플들은 일반적으로 랜덤 샘플링에 비해 더 적은 노이즈를 생성합니다.
2. Generating Poisson Disk Sample Sets
푸아송 디스크 샘플 셋들을 사용할 때 문제는 그것들을 생성하는 것이 눈에 띄게 어렵다는 것입니다. 왜냐하면 이 샘플들은 독립적으로 생성될 수가 없기 때문입니다; 각 샘플은 다른 샘플의 위치에 의존합니다. ( dart throwing 과 같은 ) 단순한 알고리즘들은 계산 비용이 비쌉니다. 계산적으로 효율적인 알고리즘들은 복잡하며 특정 샘플링 영역에 국한됩니다. 고차원( high-dimensional ) 샘플링은 6 차원이나 7 차원이 넘어 가는 것들에 대해서는 경험적으로 불가능합니다.
푸아송 디스크 샘플 셋을 생성하는 데 있어서 이런 모든 문제들은 필자가 2015 년에 소개한 weighted sample elimination 알고리즘에 의해 해결되었습니다. 이 알고리즘의 세부사항에 대해서는 다음 링크에서 찾아보실 수 있습니다: http://www.cemyuksel.com/research/sampleelimination/.
이 솔루션( solution )의 나머지 부분에서, 필자는 weighted sample elimination 알고리즘에 대한 기본 정보를 제공할 것이고 cySampleElimination 코드 릴리스에서 모든 차원의 샘플링 도메인을 위한 푸아송 디스크 샘플 셋들을 생성하기 위해서 소스 코드를 사용하는 방법에 대해서 설명할 것입니다.
3. Weighted Sample Elimination
Weighted sample elimination 은 푸아송 디스크 샘플 셋들을 생성하기 위한 간단한 알고리즘입니다. 이것의 추가적인 이점은 푸아송 디스크 반지름 속성을 지정할 필요가 없다는 것입니다. 그것의 입력은 ( 랜덤하게 생성된 ) 샘플 집합이며, 결과 샘플 셋이 푸아송 디스크 속성을 가지도록 이런 샘플들의 일부분을 제거합니다. 다시 말해, weighted sample elimination 알고리즘은 큰 집합의 입력 샘플들을 받아서 더 작은 집합의 출력 샘플들을 반환합니다. 새로운 샘플들을 생성하는 것이 아닙니다. 주어진 입력 집합으로부터 그냥 하위 집합을 선택하는 것입니다.
입력 샘플들은 모든 차원의 모든 샘플링 영역을 위해서 생성될 수 있습니다. 제공된 입력 샘플이 많을수록 더 좋은 품질의 푸아송 디스크 샘플 셋들을 얻을 수 있습니다만, 특정 비율을 넘어 서게 되면 결과가 나빠질 수 있습니다. 입력 집합의 크기를 출력 집합의 크기의 3 배를 넘도록 하는 것을 권장합니다. 필자는 일반적으로 출력 집합 크기보다 5 배 정도 큰 입력 집합을 사용합니다. 이것은 계산 속도와 샘플링 품질 사이의 좋은 균형을 제공합니다. 말하자면, 출력 샘플 집합 크기를 고려하지 않고 매우 작은 입력 샘플 집합을 사용하는 것은 좋지 않은 생각입니다. 예를 들어, 단지 10 개의 샘플들을 생성하려고 하는데, 50 개의 입력 샘플들을 사용하면 샘플 분포가 좋지 않을 것입니다. 이 경우에는, 입력 샘플 집합 크기보다 더 많은 샘플들을 사용해서 시작하는 것이 좋다고 생각합니다.
4. Using cySampleElimination
cySampleElimination 코드 릴리스는 어떠한 유형의 샘플 클래스 유형에 대해서도 사용가능한 템플릿 클래스를 포함하고 있습니다. 물론 cyPoint 코드 릴리스에 있는 클래스( 2D 를 위해 Point2, 3D 를 위해 Point3, 4D 를 위해 Point4, 임의의 차원을 위해 Point )들을 사용하도록 설계되어 있습니다.
첫 번째로 할 일은 입력 샘플들을 생성하는 것입니다. 1000 개의 출력 샘플들을 만들기 원한다고 가정합시다. 그러므로 우리는 5000 개의 입력 샘플들을 생성하는 것으로부터 시작할 것입니다. 이 샘플들을 생성하는 방법은 온전히 여러분과 여러분의 샘플링 문제에 달려 있습니다. 아래에 Point3f 를 사용해서 3D 에서 랜덤 샘플을 생성하는 간단한 코드를 삽입했습니다.
모든 샘플 값들은 0 에서 1 사이라는 점에 주의하세요. 이것은 중요합니다. 샘플링 영역이 다르다면 그것의 차원을 지정할 필요가 있습니다. 아래에서 이에 대해 다루겠습니다. 지금은 모든 샘플 값들을 0 에서 1 사이로 한다고 가정합니다.
Weighted sample elimination 을 사용하려면, 먼저 WeightedSampleElimination 클래스의 인스턴스를 생성할 필요가 있습니다.
여기에서 템플릿 파라미터들은 샘플 클래스 타입( 이 경우에는 Point3f ), 부동 소수점 타입( float 혹은 double ), 포인트 타입의 차원성( 이 경우 3 ), 샘플 인덱스를 위한 타입( 이 경우 int )을 정의합니다. 2 십억 개가 넘는 샘플들을 가지고 작업하지 않는 이상에는 샘플 인덱스 타입은 int 가 적절할 것입니다.
생성자는 기본 파라미터들을 설정할 것입니다. 원한다면 수정해도 좋습니다. 아래에서 파라미터들에 대해서 설명하겠습니다. 지금은 기본값만으로도 충분하다고 간주하겠습니다. 푸아송 디스크 샘플 셋을 생성하려면, WeightedSampleElimination 클래스의 Eliminate() 메서드를 호출할 필요가 있습니다.
됐습니다. 출력 점들은 푸아송 디스크 속성들을 가지게 될 것입니다. 우리가 푸아송 디스크 반지름을 지정할 필요가 없다는 것을 기억하십시오. 제거 기법은 몇 개의 파라미터들을 더 받을 수 있으며, 아래에서 설명하도록 하겠습니다.
5. Progressive sampling
샘플들이 하나씩 생성되는 것이 기대되는데 일단 원하는 속성에 도달하면 새로운 샘플들을 생성하는 것을 중지해야 하는 샘플링 문제가 있습니다. 이는 점진적( progressive ) 샘플링( 혹은 순응 샘플링( adaptive sampling ) ) 이라 불립니다. 이 Eliminate() 메서드는 progressive 인자를 true 로 설정함으로써 점진적 샘플을 쉽게 생성할 수 있게 해 줍니다.
이 경우 출력 집합에 있는 샘플들이 정렬되는데, 이 순서대로 샘플들이 생성되는 경우에, 시퀀스( sequence )에 있는 각 샘플들은 푸아송 디스크 샘플 셋이 됩니다. 아래의 애니메이션은 예제 시퀀스을 보여 줍니다.
Progressive Samples
6. Sampling Arbitrary Volumes
위에서 언급했듯이, 우리 예제 샘플 점들은 0 에서 1 사이의 값을 가집니다. 만약 다양한 영역을 샘플링하기 원한다면, 그 영역의 경계를 지정해야 합니다. 예를 들어, 샘플링 영역이 3D 로 된 박스라고 가정합시다. 여기에서 최소 경계는 (-2, -1, 0 ) 이고 최대 경계는 (2, 1, 1 )입니다. 이 경계들을 다음과 같이 설정할 수 있습니다.
이 경계들은 박스 모양의 영역을 지정한다는 것에 주목하십시오. 3D 상의 임의의 부피를 샘플링하고자 한다면, 그 경계들은 도움이 되지 않습니다. 대신에 Eliminate() 메서드의 d_max 인자를 직접 지정해야 합니다. d_max 인자는 요구된 출력 샘플 개수를 위해 샘플링 영역 내의 두 샘플들 간의 최대 거리를 지정합니다. 이 값은 2D 와 3D 에서는 잘 정의되어 있으며, 더 높은 차원에서는 근사계산될 수 있습니다. GetMaxPoissonDiskRadius() 메서드는 이 파라미터를 설정하는데 도움이 됩니다. d_max 인자는 이 메서드가 반환하는 반지름 값의 두 배여야 합니다.
GetMaxPoissonDiskRadius() 메서드의 파라미터들은 차원, 출력 샘플 크기, 샘플링 영역의 부피입니다. 만약 부피가 ( 기본값인 ) 0 으로 주어진다면, 그 부피는 경계들을 사용해서 계산됩니다. 그렇지 않으면 경계들은 완전히 무시됩니다.
7. Sampling Surfaces in 3D
Eliminate() 메서드의 마지막 인자는 3D 에서 서피스( surface )( 혹은 고차원 공간에서의 저차원 매니폴드( manifold ) )를 샘플링하기 위해서 사용될 수 있습니다. 먼저 입력 점들이 원하는 서피스 상에서 생성되어야 합니다. 그리고 나서 Eliminate() 메서드를 호출할 때, 올발른 d_max 인자와 샘플링 영역의 차원성을 지정해야 합니다. 우리 예제에서는 3D 상의 서피스를 샘플링하고 있기 때문에, 샘플링 영역은 2D 로 간주되어야 합니다.
이 경우에 area 값은 샘플링 영역의 전체 서피스 면적을 저장합니다.
WeightedSampleElimination 오브젝트가 3D 샘플러로서 생성( 3D 샘플 상에서 동작 )되었지만, 샘플링 영역을 2D 에 대한 차원성으로 지정했다는 것에 주목하십시오. 그 이유는 우리가 서피스를 샘플링하기 원했기 때문입니다. 즉, d_max 가 지정되고 점진적 샘플링이 사용되지 않았다면, 차원성을 지정하는 마지막 인자는 사용되지 않는다는 것입니다.
스탠포드 토끼 모델 상에 생성된 샘플들.
8. Tiling
가끔 샘플 셋을 생성한 다음에 어떤 영역에서 반복( tiling )시키고 싶을 때가 있습니다. 또한 파워 스펙트럼( power spectrum )을 활용하는 통계적 분석( statistical analysis )를 사용했을 때, 생성된 샘플 셋이 반복적이어야만 하는 경우가 있습니다. 반복 작업은 추가적인 계산을 포함합니다; 그러므로 그것은 기본값으로 꺼져 있습니다. SetTiling() 메서드를 사용해서 타일링을 켤 수 있습니다.
타일링이 꺼져 있다면, weighted sample elimination 은 샘플링 영역의 경계들 근처에서 더 많은 출력 샘플 집합들을 생성할 것입니다. 그러므로 박스 모양의 샘플링 영역을 위해서는, 샘플링 문제가 타일링을 포함하고 있지 않다고 해도, 타일링을 켜 두는 것이 좋습니다.
9. Adaptive Sampling
가끔은 영역의 다양한 영역에서 다양한 샘플링 밀도( density )를 가져야 할 때가 있습니다. Weight 함수를 적절하게 수정함으로써 이를 달성할 수 있습니다. 커스텀 weight 함수를 사용할 수 있다고 언급하는 것 외에 더 세부적인 정보를 제공하지는 않겠습니다. 이 커스텀 weight 함수는 더 듬성듬성하게( sparsely ) 샘플링되야 하는 영역보다 더 큰 값들을 반환해야 합니다. 그리고 더 조밀하게( denser ) 샘플링 분포가 생겼으면 하는 영역보다는 더 작은 값을 반환해야 합니다. 가장 듬성듬성하게 샘플링되는 영역을 위해서 커스텀 d_max 인자를 제공할 필요도 있습니다.
밀도( density ) 맵을 사용해서 생성된 샘플들.
10. Additional Parameters
기본 weight 함수는 세 개의 파라미터들을 가지고 있습니다; alpha, beta, gamma. alpha 파라미터는 weight 함수를 위해 사용되는 지수( exponent )입니다. 그것의 기본값은 8 입니다. 아마도 이 파라미터를 수정할 일은 없을 것입니다.
beta 파라미터는 weight limiting 의 양을 지정합니다. Weight limiting 은 더 높은 품질의 샘플 셋들을 제공할 수 있는 기법이지만, 공격적인( aggressive ) weight limiting 은 가끔 가깝게 배치된 샘플이 몇 개 밖에 생성되지 않도록 만들 수가 있습니다. 이것은 보통 원하지 않는 결과입니다. 기본적으로 weight limiting 은 0.65 로 설정되어 있는 beta 파라미터에 의존합니다. beta 파라미터의 ㄱ밧은 0 에서 1 까지입니다. 값이 커질수록 더 공격적인 weight limiting 이 제공되며 값이 작아질수록 weight limiting 의 요과가 줄어듭니다. beta 를 0 으로 설정하는 것은 weight limiting 을 끄는 것과 동일합니다.
마지막으로 gamma 파라미터는 weight limiting 의 한계를 입력 셋 크기와 출력 셋 크기의 상대적인 비율에 의존해 설정하기 위해 사용됩니다.
원래 논문에서의 이런 파라미터들의 세부사항들을 찾아 볼 수 있습니다. weighted sample elimination 에 대한 추가적인 정보를 원하신다면, 해당 프로젝트 페이지를 참고하시기 바랍니다: http://www.cemyuksel.com/research/sampleelimination/.
'Graphics' 카테고리의 다른 글
| [ 번역 ] Deinterleaved Texturing for Cache-Efficient Interleaved Sampling (0) | 2019.10.16 |
|---|---|
| [ 번역 ] Adaptive Screen Space Ambient Occlusion (0) | 2019.10.16 |
| [ 번역 ] What is Implicit modelling? (0) | 2019.10.06 |
| Reflection Vector & HLSL reflect() (0) | 2019.10.04 |
| [ 기고 ] Normal Blur Sub-Surface Scattering (0) | 2019.09.09 |
| [ 번역 ] Color Fundamentals: Shading (0) | 2018.11.29 |
| Texture Size 와 MipMap Level (4) | 2018.06.02 |
| [ 번역 ] 실제 이미지에서 specular 와 diffuse 분리하기 (0) | 2017.09.03 |
| [ 질문 공유용 ] dead-end detection 에 대한 질문 (0) | 2017.05.04 |
| [ 번역 ] Terrain Synthesis from Digital Elevation Models (0) | 2017.04.15 |