13

Part IV · Multi-pass Chapter 13 of 18 Build 2025.31550

Neighborhood Operation

“점이 자신만 알아도 되는 연산은 쉽고, 이웃을 알아야 하는 연산은 spatial hash라는 자료구조를 요구한다.”

이 챕터에서 정복할 CG 개념

왜 이게 중요한가

GPU의 본질은 "thread가 다른 thread의 결과를 모른다"는 가정 위에 있다. point i가 자기 자신의 attribute만 읽으면 의존이 없고 dispatch는 최대 병렬도로 돈다. 그러나 흥미로운 update 식의 대부분이 이웃을 요구한다 — RD의 Laplacian, smoothing의 평균, boids의 alignment, SPH의 density kernel, mesh ARAP는 모두 "점 i 주변의 점 집합"을 본다. 단순 해법은 모든 다른 점을 다 보는 brute force지만 N=10,000에서 10⁸으로 폭발한다. 게임·실시간 시뮬레이션이 이 한계를 넘는 길은 uniform grid나 KD-tree를 GPU 위에서 한 cook에 짓고 다음 cook에 쿼리하는 패턴이다. POP은 이 흐름의 입구를 Neighbor POP과 Proximity POP으로 캡슐화해 보여준다.

POP에서의 노출 지점

Nebr attribute의 데이터 타입은 wiki에서 정수형으로 적시되지만 정확한 GLSL 타입(int / uint)은 명시되지 않는다 — wiki 미확정 — 실험 필요. 본 챕터는 셰이더 안에서 uint 캐스팅을 명시적으로 한다.

이론

Per-point는 쉽다, neighborhood는 자료구조다

Per-point는 output[i] = f(input[i]). GPU에 그대로 매핑, thread N개. Neighborhood는 output[i] = g(input[i], neighbors_of(i)). neighbors_of(i)가 자료구조에 의존한다.

Brute force는 for each j != i: if distance(i, j) < r: accumulate. 점당 O(N), 전체 O(N²). N=1,000은 10⁶로 한 frame에 끝나지만 N=100,000은 10¹⁰으로 무너진다.

Uniform grid (spatial hash)

공간을 cell size = 2r의 균등 격자로 나누고 점을 binning한다. 점 i의 이웃 후보는 자기 cell + 인접 26개(3D, 3×3×3) cell에만 존재. 점 분포가 고르다면 점당 탐색량은 O(평균 cell 점 수 × 27)로 N에 거의 무관.

GPU에서의 binning은 두 패스다(GPU Gems 3 Ch.32 Le Grand):

pass 1 (binning):
    c = cell_hash(position[i])
    slot = atomicAdd(bucket_count[c], 1)
    bucket_index[c, slot] = i

pass 2 (query):
    c = cell_hash(position[i])
    for each neighbor cell c' of c:
        for each j in bucket[c']:
            if i != j and distance(i, j) < r:
                accumulate

atomicAdd가 핵심이다 — Advanced POP의 outputaccess = readwrite가 활성화돼야 한다. 두 패스 분리는 Ch.12의 multi-pass(Passes = 2)로 구현 가능.

Neighbor POP과 boids의 위치

Neighbor POP은 brute-force의 노드 버전이다. spatial hash를 직접 짓지 않아도 이웃 인덱스를 attribute로 제공한다. 내부 가속 구조는 wiki에 명시되지 않는다 — wiki 미확정 — 실험 필요. 점 수가 수천 단위면 Neighbor POP 한 개로 충분.

Craig Reynolds boids의 세 항(separation/alignment/cohesion)은 모두 "점 i의 이웃들의 P와 V"를 입력으로 받는다. 자료구조는 같고 update 식만 다르다.

손작업 (Hands-on)

셋업 — Neighbor POP의 Nebr attribute로 cohesion 흉내

목적: GLSL POP에서 array attribute를 인덱싱해 이웃 평균으로 점을 끌어당긴다. Reynolds cohesion 한 항.

시작 파일

연결:

Point Generator POP1 ─> Neighbor POP1 ─┬─> GLSL POP1 ─> Null POP1
                                        │     ▲
                              Feedback POP1 ──┘   (target = GLSL POP1)

GLSL POP1의 Compute Shader DAT 내용:

// Attribute Class = Point.
// Output Attributes: P.
// 입력 0: Neighbor POP1의 출력. Point attribute P와 array attribute Nebr (크기 8)이 모두 존재.
// 입력 1: Feedback POP1 (직전 frame의 P).
//
// Nebr는 array attribute이므로 cTDArraySize_Nebr가 배열 크기 상수.
// reader 시그니처는 TDIn_Nebr(inputIndex, elementId, arrayIndex).
// Nebr가 정수형으로 저장된다고 가정 — wiki는 정확한 스칼라 타입을 명시하지 않음.
// **wiki 미확정 — 실험 필요**: TDIn_Nebr의 반환 타입이 int인지 uint인지 float인지.
// 안전한 우회: 부호 없는 정수로 캐스팅해 사용.

uniform float u_pull;  // Vectors page에 추가, value = 0.05

void main() {
    const uint id = TDIndex();
    if (id >= TDNumElements()) return;

    // 직전 frame의 자기 위치를 시작점으로
    vec3 self_p = TDIn_P(1u, id);

    // 이웃 인덱스 배열 크기
    const uint K = cTDArraySize_Nebr;

    vec3 acc = vec3(0.0);
    uint counted = 0u;
    for (uint k = 0u; k < K; ++k) {
        // Nebr[k]가 자기 자신을 가리키거나 invalid(예: -1 같은 sentinel)일 수도 있으나
        // Neighbor POP의 출력은 "다른 점들"의 인덱스로 wiki에 명시됨.
        uint nIdx = uint(TDIn_Nebr(0u, id, k));
        // bounds check: TDInputNumPoints(0)을 넘으면 무시
        if (nIdx >= TDInputNumPoints(0u)) continue;
        vec3 np = TDIn_P(0u, nIdx);
        acc += np;
        counted += 1u;
    }

    vec3 centroid = (counted > 0u) ? (acc / float(counted)) : self_p;

    // self_p와 centroid를 u_pull 비율로 보간 — cohesion 한 항만 떼어낸 형태
    P[id] = mix(self_p, centroid, u_pull);
}

이 코드가 GPU에서 실제로 무엇을 하고 있는가: 한 dispatch가 2000개 thread를 띄운다. 각 thread는 직전 frame의 자기 위치를 input 1(Feedback)에서 읽고, 자기 점의 Nebr array attribute에서 이웃 8개의 인덱스를 차례로 꺼낸다. 각 이웃 인덱스로 input 0(Neighbor POP의 출력)에서 그 이웃의 현재 P를 가져와 누적한다. 평균을 내고 자기 위치와 5% 비율로 섞어 출력 P에 쓴다. 매 frame 점이 자기 이웃 평균 쪽으로 조금씩 당겨진다. 충분히 돌리면 점 군집이 응집한다. 외부 Feedback POP이 시간 누적을 담당, GLSL POP은 한 cook의 update 식만 본다.

여기서 중요한 것: 이 코드의 비용은 점당 K=8 thread-내 루프다. brute-force라면 점당 N=2000 루프였다. 노드 한 개(Neighbor POP)가 250배의 차이를 만들었다. Neighbor POP 자체의 비용은 wiki에 명시되지 않지만, 한 번 cook해두면 다운스트림은 K번만 본다.

주의: 위 코드의 TDIn_Nebr 반환 타입 가정은 wiki에 명시되지 않은 부분이다. 실제 실행 시 컴파일 에러가 난다면 int로 캐스팅, 또는 TDInPoint_Nebr 형식의 클래스-prefix reader를 시도해야 한다(Advanced POP 경우). 본 코드는 GLSL POP에 한정.

Spatial hash로 가는 길 — 의사 코드

수만 점 이상에서는 Neighbor POP을 떠나 직접 grid를 짓는다. Advanced POP의 multi-pass + readwrite + Extra Output이 필요하다.

Extra Output A: cell_count[num_cells]                    (uint, readwrite)
Extra Output B: cell_indices[num_cells * MAX_PER_CELL]   (uint, readwrite)
Output:         P[N]                                     (vec3, writeonly)

Pass 1 (init):     cell_count[c] = 0u
Pass 2 (binning):  c = hash_cell(P[i])
                   slot = atomicAdd(cell_count[c], 1u)
                   if (slot < MAX_PER_CELL) cell_indices[c*MAX_PER_CELL + slot] = i
Pass 3 (query):    c = hash_cell(P[i])
                   for each of 27 neighbor cells c':
                       for k in 0..cell_count[c']-1:
                           j = cell_indices[c'*MAX_PER_CELL + k]
                           if (j != i) apply_force(i, j)

각 pass는 Advanced POP의 Passes로 늘어나거나 별도 노드로 분리된다. atomicAdd는 SSBO readwrite 필수. pass 사이 GPU memory barrier 의미는 wiki에 명시되지 않으므로(Ch.12 동일 caveat), 보수적으로는 패스를 별도 노드로 쪼개 데이터 흐름을 그래프에 명시한다.

노드 ↔︎ GLSL 매핑

같은 결과 — "각 점에 대해 이웃 8개의 평균 위치를 attribute로 갖게 한다" — 를 두 방식으로 구성한다.

노드 방식

Point Generator POP1 ─> Neighbor POP1 ─> Math Combine POP (Nebr 인덱스로 P를 ...)

실제로는 Math Combine POP만으로는 array attribute의 인덱스 dereferencing이 어렵다. POP 그래프 안에서 이웃 평균을 내려면 Neighbor POP의 결과를 GLSL POP에 넘기는 것이 자연스러운 경로다. 즉 "노드만으로 이웃 연산을 완결하는 길"은 일반적으로 부재하다 — array attribute의 lookup이 셰이더 영역의 작업이다. 직관과 어긋나는 부분: Neighbor POP은 자료구조만 만들어 주는 노드이고, 그것을 쓰는 일은 셰이더의 책임이다. 같은 두 단계 분업이 GPU Gems의 broad-phase 글들에서도 그대로 등장한다.

GLSL 방식 위 손작업의 코드 그대로. Neighbor POP을 입력으로 받아 cTDArraySize_Nebr로 크기를 알고, TDIn_Nebr(0u, id, k)로 인덱스를 꺼내, TDIn_P(0u, nIdx)로 이웃의 attribute를 가져온다. array attribute가 셰이더 안에서 명시적으로 인덱싱되는 모습이 보인다.

대안: Proximity POP 같은 입력을 Proximity POP에 넣으면 결과가 attribute가 아니라 새 line primitive다. 이웃 인덱스는 primitive의 두 endpoint 인덱스에 인코딩된다. 시각화에는 좋고 셰이더 처리에는 Neighbor POP보다 번거롭다. 어떤 쪽을 쓸지는 다운스트림이 attribute를 원하는가 primitive를 원하는가에 달렸다.

확인 질문 (Self-check)

  1. Neighbor POP의 Number = 8로 두었을 때 셀프 인덱스(점 i 자신의 인덱스)는 Nebr array에 포함되는가, 제외되는가? 셰이더에서 어떻게 그 가정을 검증할 것인가?
  2. Brute-force k-NN의 점당 시간 복잡도는 O(N)이다. uniform-grid spatial hash의 점당 평균 시간 복잡도가 O(1)에 가까워지려면 cell size와 점 분포에 어떤 가정이 필요한가?
  3. Spatial hash의 binning pass에서 atomicAdd를 쓰지 않으면 어떤 race condition이 생기는가? 같은 cell에 떨어진 두 점의 인덱스가 동일 slot을 덮어쓰는 시나리오를 설명하라.
  4. Reynolds boids의 세 항(separation/alignment/cohesion)을 한 GLSL POP에서 모두 구현할 때, alignment를 위해 추가로 필요한 attribute는 무엇인가?
  5. TDIn_Nebr의 반환 타입은 wiki에 명시돼 있지 않다. 실제 컴파일 결과를 확인하는 가장 짧은 검증 셰이더를 어떻게 작성할 것인가?

연결 고리

이 챕터의 한 줄 명제

Per-point 연산은 GPU의 본성이고, neighborhood 연산은 GPU 위에 자료구조를 짓는 일이다 — POP은 그 자료구조의 진입점을 Neighbor POP과 array attribute로 노출하고, 진짜 작업은 spatial hash를 multi-pass로 직접 짓는 셰이더의 영역으로 이어진다.