공간 분할
7편
안 보이는 것을 안 그리는 값도 든다
앞의 여섯 편은 무엇을 판정할지 줄였습니다. 컬링은 무엇을 그릴지 줄입니다. 절두체 판정을 하나씩 할 때와 묶어서 할 때, 구로 먼저 거를 때의 손익, LOD 가 덜컹거리는 횟수를 실측으로 봅니다.
벽은 막고 문은 통과시킨다
앞의 다섯 편은 물체를 추렸습니다. 포털 컬링은 보이는 영역 자체를 잘라 나갑니다. 문을 지날 때마다 시야가 얼마나 좁아지는지, BSP(binary space partitioning)가 왜 축에 갇히지 않는지 실측으로 봅니다.
움직이는 것들에는 트리를 짓지 않는다
앞의 네 편은 구조를 지어 두고 질의를 던졌습니다. 스윕 앤 프룬(sweep and prune)은 한 축으로 줄만 세워 둡니다. 프레임마다 순서가 거의 안 바뀐다는 성질 하나로 어디까지 갈 수 있는지, 대신 무엇을 내주는지 실측으로 봅니다.
공간이 아니라 물체를 나눈다
격자도 쿼드트리도 KD 트리도 공간을 잘라 왔습니다. BVH(bounding volume hierarchy)는 물체를 둘로 갈라 각 무리를 상자로 감쌉니다. 크기가 있는 물체가 왜 여기에만 온전히 담기는지, 상자끼리 겹쳐도 괜찮은 이유를 실측으로 봅니다.
가운데가 아니라 중앙값에서 자른다
쿼드트리는 공간의 한가운데를 자르고 KD 트리(k-d tree)는 점들의 중앙값을 자릅니다. 트리 모양이 분포에서 풀려나는 대신 무엇을 내주는지, 가지치기가 실제로 몇 개를 걷어 내는지 실측으로 봅니다.
빈 곳은 큰 칸 하나로 남긴다
밀도가 고르지 않으면 칸 크기를 하나로 정할 수 없습니다. 붐비는 칸만 넷으로 쪼개는 쿼드트리(quadtree)의 동작과, 격자보다 나은 자리와 나쁜 자리를 실측으로 갈라 봅니다.
좌표를 칸으로, 칸을 배열로
균일 격자를 실제로 만들 때 막히는 자리들입니다. 음수 좌표에서 칸 번호가 어긋나는 이유, 맵 밖을 다루는 공간 해시(spatial hash), 같은 쌍을 두 번 보지 않는 법, 칸마다 리스트를 두지 않고 배열 세 개로 짓는 법.