인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

인프런 커뮤니티 질문&답변

themoon007님의 프로필 이미지
themoon007

작성한 질문수

이득우의 꼭 배워야하는 게임 알고리즘

6강 쿼드트리의 최적화

depth 구할 때 floor로 처리하면 -1이 사라지는 과정이 잘 모르겠어요.

해결된 질문

작성

·

307

·

수정됨

-1

결국엔 log(2, x) -1 = floor ( log(2,x) ) 라는 것 같아 보이는데.. 이 수식이 잘 이해가 안 가는 것 같아요....

답변 1

0

이득우님의 프로필 이미지
이득우
지식공유자

질문 감사합니다.
오랜만에 강의 내용을 다시 보았는데, 우선 한정된 슬라이드에서 수식을 넣다보니 효과적으로 전달을 못했네요.
두 식이 동일하다는 의미는 아니고, 정수 값만 가지는 depth값만 보았을 때 두 식은 같은 결과를 산출한다는 의미로 봐주시면 감사하겠습니다.
그런데 제가 다시 보면서 중요한 점을 발견했는데, 수식이 잘못되었네요.
예를 들어 16보다 작고 8보다 큰 반지름 10이 들어온다고 가정 했을 때, 이의 목표 깊이 값은 1이 되어야 합니다. 하지만 위 수식으로 진행하면 2가 나오므로 잘못된 수식으로 보여집니다.
잘못된 자료로 인해 불편을 드려 죄송합니다.

해당 슬라이드 내용은 우선 글로 다시 설명드리겠습니다.


image

L(depth)는 느슨한 트리가 사용하는 해당 뎁스에서의 영역의 크기입니다. 이는 k에 의해 결정되는데 통상 2의 값을 사용합니다. 따라서 루트노드에서는 전체 사각형 변의 두 배인 2W, 첫 번째 뎁스에서는 W의 크기를 가집니다. 이를 통해 해당 뎁스에서 허용가능한 최대 반지름 값 Rmax(depth)가 다음과 같이 결정됩니다.

 

image

그리고 주어진 반지름 R에 대한 최적의 깊이 값을 찾아주는 함수를 depth(R)로 정의하겠습니다.
R과 depth(R), Rmax(depth)사이에는 다음과 같은 규칙이 주어집니다.

 

image두 번째 식에 대입하면 결과는 다음과 같습니다.

imageimage로그를 취해주면 다음과 같이 정리됩니다.

image이 값은 정수만 가지므로 다음과 같이 계산할 수 있습니다.

image

예제의 LQuadtree.cs 의 GetTargetDepth 함수도 수정해야 될 것으로 보여집니다.

[기존 코드]

int targetDepth = Mathf.FloorToInt(Mathf.Log(width / maxHalfValue, 2.0f));

 

[수정해야 할 코드]

int targetDepth = Mathf.FloorToInt(Mathf.Log(width / maxHalfValue, 2.0f) - 1);

해당 영상은 차후에 수정하겠습니다.

감사합니다!

themoon007님의 프로필 이미지
themoon007

작성한 질문수

질문하기