파티클 시스템 결과 렌더링

3차원으로 확장 가능한 경계 상자 정의

인접 입자 찾기 알고리즘

struct ParticleHash
{
    uint particleID; // 원래 파티클 인덱스
    uint hashValue;  // 계산된 해시 값
    uint flag;       // 그룹 Flag  
};

1. 위 구조체를 담는 배열을 생성하고, 아래와 같이 해시를 간단히 설정 -> 이후에 해시 생성 방식 변경

    // 파티클 위치 p.position 을 그리드 최소 바운더리 위치를 기준으로 상대 위치로 변환
    float3 relativePos = p.position - minBounds;

    // 상대 위치를 셀 크기로 나누어, 각 축별로 몇 번째 셀에 해당하는지 실수 값으로 계산
    float3 normalizedPos = relativePos / cellSize;

    // floor 연산으로 소수점을 버려 정수 인덱스를 얻음 (이때 음수 인덱스 가능성 있음)
    int3 cellID = int3(floor(normalizedPos));

    uint hashValue = uint(cellID.x) +
        uint(cellID.y) * gridDimX +
        uint(cellID.z) * gridDimX * gridDimY;

    ParticleHashesOutput[index].particleID = index;
    ParticleHashesOutput[index].hashValue = hashValue;
    ParticleHashesOutput[index].flag = 0;

 

2. 생성된 해시를 BitonicSort로 정렬하고(이후에 입자 개수가 많아질경우 Radix Sort 적용), 정렬된 해시 배열을 순회하면서, 이전 위치의 해시값과 지금 위치의 해시값이 다르면, 새로운 그룹으로 설정(flag = 1)

 

3. flag가 설정된 정렬된 해시 배열을 병렬 스캔 진행해서 전역 Prefix Sum 생성

효율적인 Belloch 병렬 스캔 알고리즘 적용(CUDA 예제 참고)

 

1. Pass 1 결과로 LocalScanSum이랑 PartialSum을 얻습니다.

2. Pass2에서는 PartialSum을 인풋으로, 결과를 blockOffsets를 얻습니다.

3. LocalScanSum이랑 BlockOffsets를 이용해서, 최종 PrefixSum을 얻습니다.

4. PrefixSum으로 그룹의 시작과 끝을 저장한 데이터를 출력합니다. 

 

 

참조

https://cg.informatik.uni-freiburg.de/publications/2014_EG_SPH_STAR.pdf

https://developer.nvidia.com/gpugems/gpugems3/part-vi-gpu-computing/chapter-39-parallel-prefix-sum-scan-cuda