Bridson 포아송 디스크 샘플링의 부모 점 기반 각도 제외 최적화
- Robert Bridson의 2007년 알고리즘은 최소 거리 $r$을 지키는 점 배치를 위해 공간을 한 변 $r/\sqrt{d}$ 격자로 나누고, 활성 점 주변의 반지름 $r$에서 $2r$ 고리에서 후보를 뽑음
- 후보 점마다 격자 셀만 검사하면 충돌 검사를 빠르게 처리할 수 있고, 한 활성 점에서 유효 후보를 $k=30$회 안에 찾지 못하면 그 점을 활성 목록에서 제거함
- 2차원에서는 새 점 $q$의 부모 점 $p$를 저장해, $p$와 너무 가까워질 수밖에 없는 각도 원뿔을 후보 샘플링 범위에서 제외할 수 있음
- 제외 원뿔의 반각 $\beta$는 고리의 안쪽 또는 바깥쪽 경계와의 교점 중 더 작은 각도로 정하며, $p$와 $q$의 거리가 $\sqrt{3}r$를 넘을 때 경계점이 바깥 원에서 안쪽 원으로 바뀜
- 글의 100회 평균 실험은 한 변 $\ell=100$, $r=1$ 격자에서 부모 점 최적화와 기본 Bridson 알고리즘이 생성한 점 수를 $k$ 값별로 비교함
Hacker News opinions
Observable의 poisson-distribution-generator랑 spheredisksample 노트북도 같이 보면 도움 됨.
이런 문제는 진짜 난수보다 사람이 랜덤하다고 느끼는 배치를 만들려는 점이 재밌음. blue noise가 바로 떠올랐고, 예전에 포아송 디스크 샘플링을 쓰는 시스템 만들면서 한참 찾았었음.
Casey Muratori가 게임에서 잔디를 랜덤 배치하며 blue noise를 쓴 글도 있음. 줄무늬를 피하려는 결정론적 잔디 배치 글도 더 흥미로움.
이걸 저불일치 수열로 쓸 수 있는지 궁금함.
저불일치 수열은 보통 원하는 개수만큼 점을 하나씩 늘려 생성하려는 용도임. 포아송 디스크 샘플링은 영역 전체를 대략 정해진 밀도로 채우는 방식이라, 만들 수는 있어도 다른 대안보다 잘 맞지는 않을 듯.
생성된 점들이 종종 선처럼 보여서 그래픽에서는 앨리어싱을 낼 것 같은데, 저불일치 수열을 쓰지 않는 이유가 뭘까.
예전에 만든 디버그 UI 중에는 이게 가장 만족스러웠음. 포아송 디스크 배치를 눈으로 보면 알고리즘 상태가 꽤 잘 읽힘.
p와 q가 그림에서 뒤바뀐 줄 알고 한참 헷갈렸음. 이미 확정된 p, q가 있고, 이름 없는 세 번째 점이 q의 고리 안에서 p와 너무 가까워지는 방향을 제외하는 그림이더라.
셰이더에서 픽셀별로 구현할 방법은 못 찾았음. Bridson 방식은 active 목록이 필요해서, 결국 셀을 해싱하고 각 셀 내부를 지터링했음.
글에서 GPU 구현체인 PixelPie도 링크함. active 목록 문제를 GPU에서 다루는 방법으로 참고할 만함.