CPU 레이트레이서에 3D 파일을 불러서 CPU로 렌더링을 하려고 하니까,
샘플 모델을 이루는 삼각형들이 15000개나 되서 이걸 레이가 충돌할 때마다 O(n) 으로 하나하나 충돌하는지 아닌지 확인하려고 하니 속도가 오질라게 느리더라고
그래서 어찌어찌 인터넷에서 KD트리를 활용해서 광선 충돌이 되는 영역의 탐색을 최적화 하는 방법을 구현해서
기존에는 218초~230초 정도 되는걸 같은 설정에서는 14~16초로 줄어들게 했음.
그래서 거의 같은 렌더링 시간으로 샘플 수를 높여서 렌더링할 수 있게 됨 개굿.
위에는 KD트리를 적용하지 않았을 때, 픽셀 당 샘플 수 2개로 230초 정도 걸림. 밑에껀 KD트리를 적용한 후에 픽셀 당 샘플 수를 32개로 정했는데 270초밖에 안나옴.
KD트리를 적용 안하고 32 샘플링을 했으면 렌더링하는 데 1시간 정도 걸렸을 듯.
일단 KD트리만 적용해서 보자는 심정으로 무대뽀로 코딩을 해서, 리팩터링 하면 처리시간이 더 줄어들면 줄어들었지 늘지는 않을 듯 싶음. ㅇㅇ
실제 렌더러에서도 메모리 소모를 확 늘리면서 렌더속도를 확 높이는 것들이 많은데, 이 KD트리도 메모리 소모가 많아지나요 ? 또 실시간 뷰포트 표시에도 이 KD 트리 쓸 수 있을까요 ( 폴리곤에 RAY충돌 판정으로 셰이딩을 한두가지 넣어서 뷰포트표시해야 되는 경우가 있어서요. ) ?
일단 자료구조를 만들어야 하니까, 메모리 소모는 있겠죠 글고 실시간 렌더러에서 KD트리는... 일단 다이나믹한 예제에서도 사용할 수 있는 그런게 있다고는 들었는데 대개 정적인 (움직이지 않는) 물체에들에 대해서만 바인딩해서 쓰는게 좋을 것 같다고 생각해요.
https://users.cs.duke.edu/~pankaj/publications/papers/bkd-sstd.pdf
이런 쪽으로 봐야 될까요?
그리고 보통 게임에서는 쿼드트리를 많이 쓰는데 kd트리랑 쿼드트리가 효율차이가 나는 건지 아니면 각자 쓰는 주특기영역(?)이 다른 건가요?
쿼드트리는 2D 영역에 대해서만 스케일링 되지 않나요? 아마 주특기 영역이 다를텐데, 쿼드트리나 옥트리 같은건 고정 사이즈로 된 그리드영역에 대한 자료구조를 만드는거고, KDTree 는 BSP (Binary Space Partioning) 을 확장해서 만든거라고 보면 될 거라서 그리드라는 개념도 없고, 그냥 분할분할할 뿐... 이라고 보면 될텐데. 아마 쿼드트리는 RTS 같이 평평한 곳에서 길찾기에 주된 목적을 두면 KD보단 효율이 좋을 것이고, KD는 아예 컬링이나 렌더링부분쪽으로 특화라고 보면 될 것 같기도 하네요... 저도 완전히는 잘 모르겠지만.
폴리곤 ray 충돌계산이 느린게 (1) 판정 알고리즘이 비효율적이라 그런건지, (2) 자료구조가 비효율적이라 그런건지 대략 2가지로 조사해 가면서 개발해야 되겠네요. 저는 주로 (1)번만 연구했는데, (2)번이 이렇게 많은 영향을 주는 건 노이ㄴ 님 글 보고 처음 알았네요. ( 사실 (1)도 잘 모르지만요 )
KDTree 는 탐색시간 O(n) 을 최악 O(log2(n)) 으로 줄여줄 수 있음요. 1024번 할 걸 10번하면 끝나게 되니깐유...