발산 정리로 터무니없이 빠르게 부피 계산하기(2018)

단순·폐쇄·삼각형 분할된 3D 메시의 부피를 표면 적분으로 바꿔, 모든 삼각형을 한 번씩 순회하는 계산법을 유도함 발산이 1인 벡터장 F(x,y,z)=〈x,0,0〉 을 선택하면 부피 적분을 메시 표면의 삼각형별 적분 합으로 변환할 수 있음 각 삼각형의 두 변 벡터를 Δ₁, Δ₂로 두면 부피는 V = 1/6 Σ (Δ₁×Δ₂)ₓ(T₀ₓ+T₁ₓ+T₂ₓ)라는 폐쇄형 공식으로 계산됨 수치 적분이나 미분 없이 삼각형당 덧셈 7회와 곱셈 3회만 수행하며, 전체 계산량은 삼각형 수 n에 대해 O(n), 약 11n 부동소수점 연산임 CPU만 사용하는 $35 Raspberry Pi에서도 60fps로 프레임마다 약 3,000만 개 삼각형의 부피를 계산할 수 있다는 추산이며, 게시 후 같은 계산법을 다르게 유도한 기존 논문도 확인됨 발산 정리에서 삼각형 공식까지 부피를 영역 R에서 상수 1을 적분한 V = ∭R 1 dV로 정의하고, 발산이 1인 벡터장 F(x,y,z)=〈x,0,0〉을 선택함 div F = ∂x/∂x + 0 + 0 = 1이므로 V = ∭R div F dV가 됨 발산 정리를 적용하면 메시 표면 S에 대한 V = ∬S F·dS로 바뀜 표면을 구성하는 각 삼각형 Tᵢ의 꼭짓점을 Tᵢ₀, Tᵢ₁, Tᵢ₂로 두고, 두 변을 Δ₁=Tᵢ₁−Tᵢ₀, Δ₂=Tᵢ₂−Tᵢ₀로 정의함 삼각형은 r(u,v)=Tᵢ₀+uΔ₁+vΔ₂로 매개화됨 rᵤ×rᵥ=Δ₁×Δ₂이며 이 값은 삼각형 전체에서 일정함 F의 y·z 성분이 0이므로 외적에서는 x 성분만 계산하면 됨 삼각형 위의 x좌표 적분은 ∬Tᵢ x dA = 1/6(Tᵢ₀ₓ+Tᵢ₁ₓ+Tᵢ₂ₓ)로 정리됨 최종 공식은 V = 1/6 Σᵢ (Δᵢ₁×Δᵢ₂)ₓ(Tᵢ₀ₓ+Tᵢ₁ₓ+Tᵢ₂ₓ)이며, 1/6은 루프 밖에서 한 번만 곱할 수 있음 이 유도는 단순·폐쇄·삼각형 분할 메시를 전제로 하며 다른 메시로의 일반화는 다루지 않음 연산량과 기존 연구 렌더링 결과를 샘플링하는 단순 계산법과 달리, 최종 알고리듬에는 수치 적분이나 수치 미분이 없고 삼각형을 순회하는 루프 하나만 필요함 삼각형당 내부 계산은 덧셈 7회와 곱셈 3회임 n개 삼각형에는 덧셈 8n−1회와 곱셈 3n+1회가 필요해 총연산량은 약 11n, 시간 복잡도는 O(n) 임 CPU만 사용하는 $35 Raspberry Pi를 기준으로, 60fps 애플리케이션에서 프레임마다 약 3,000만 개 삼각형을 측정할 수 있다고 추산함 게시 후 Cha Zheng...