곡면 기하학을 위한 공간 가속 와인딩 넘버 (Spatially Accelerated Winding Numbers)

일반화된 와인딩 넘버 (Generalized Winding Number, GWN)는 비밀폐형 (non-watertight), 중첩형 (overlapping), 중첩된 경계 표현 (nested boundary representations)을 포함하여 곡면 기하학 (curved geometry) 상에서 견고한 포함 관계 쿼리 (containment queries)를 지원하는 스칼라 필드 (scalar field)입니다. 쿼리는 샘플에 대해 쉽게 병렬화할 수 있지만, 크고 복잡한 모델에 대해 매개변수 곡선 (parametric curves) 및 곡면 (surfaces) 상에서 직접 평가하는 것은 여전히 비용이 많이 듭니다. 최첨단 (state-of-the-art)의 빠른 GWN 접근 방식은 공간 인덱스 (spatial index)를 활용하여 GWN을 근사하며, 일반적으로 멀리 떨어진 기하학적 프리미티브 (geometric primitives) 클러스터에 대한 GWN 기여도를 근사하는 테일러 전개 (Taylor expansion)와 결합됩니다. 그러나 이러한 방법들은 삼각형 메쉬 (triangle meshes)나 포인트 클라우드 (point clouds)와 같은 이산적 입력 (discrete inputs)에서만 작동하며, 곡면 입력에 적용될 경우 경계 근처에서 포함 관계 오류 (containment errors)를 유발할 수 있습니다. 본 연구에서는 계층 노드에 미리 계산된 모멘트 데이터 (moment data)를 효율적으로 저장하는 경계 볼륨 계층 구조 (Bounding Volume Hierarchy, BVH)를 통해, 2D의 임의적인 NURBS 곡선 집합과 3D의 트리밍된 NURBS 패치 (trimmed NURBS patches)에 대한 빠른 GWN 평가 지원을 확장합니다. 계층 구조를 쿼리할 때, 멀리 떨어진 클러스터에 대해서는 근사치를 사용하고 근처의 NURBS 프리미티브에 대해서는 직접 평가를 병행함으로써, 쿼리 지점 근처의 기하학적 특징을 보존하면서도 하선형 복잡도 (sub-linear complexity)를 달성합니다. 성능 향상의 핵심은 전처리 단계 동안 NURBS 프리미티브에 대한 적응형 세분화 (adaptive subdivision) 전략을 사용하는 것으로, 이를 통해 직접 평가와 동일한 포함 결정 정확도를 유지하면서도 더 나은 공간 분할 (spatial partitions)을 생성합니다. 우리는 대규모 2D 및 3D 데이터셋 전체에 걸쳐 우리 방식의 성능과 정확도를 입증합니다.