TFastWindingTree

FWN을 빠르게 계산하기 위해 사용하는 클래스. 테일러 전개를 통한 근사값을 이용해 삼각형들을 그룹으로 처리하여 빠르게 FWN을 계산한다.

Input

template< class TriangleMeshType >
class TFastWindingTree
{
	TMeshAABBTree3< TriangleMeshType >* Tree;
};

Output

struct FWNInfo
{
    FVector3d Center;
    double R;
    FVector3d Order1Vec;
    FMatrix3d Order2Mat;
};
 
TMap< int, FWNInfo > FastWindingCache;

생성되는 FastWindingCache는 테일러 전개를 이용하기 위한 계수들의 구조체인 FWNInfo맵이다.

Property

프로퍼티	설명
FastWindingCacheMeshChangeStamp	FWN을 구축하는 메쉬의 변경 여부를 추적하기 위한 TimeStamp

Algorithm

Build

Tree의 Node의 를 재귀 탐색하면서 하면서 FastWindingCache를 생성

1. FMeshTriInfoCache 생성

FMeshTriInfoCache TriCache = FMeshTriInfoCache::BuildTriInfoCache( *Tree->Mesh );

각 삼각형을 처리하기 위해 우선적으로 FMeshTriInfoCache를 생성한다.

2. 트리의 재귀 순회

int build_fast_winding_cache( int IBox, int Depth, int TriCountThresh, TOptional< TSet< int > >& TriHash, const FMeshTriInfoCache& TriCache )
{
    if ( idx < Tree->TrianglesEnd )
    {
        // 리프 노드: 삼각형 개수만 반환
        int num_tris = Tree->IndexList[ idx ];
        return num_tris;
    }
    else
    {
        // 내부 노드: 자식들 처리
        if ( iChild1 < 0 )
         {
            // 1개 자식
            int num_child_tris = build_fast_winding_cache( iChild1, Depth + 1, TriCountThresh, TriHash, TriCache );
            
            return num_child_tris;
        }
        else 
        {
            // 2개 자식
            int num_tris_1 = build_fast_winding_cache( iChild1, Depth + 1, TriCountThresh, TriHash,    TriCache );            
            int num_tris_2 = build_fast_winding_cache( iChild2, Depth + 1, TriCountThresh, child2_hash, TriCache );
 
            bool build_cache = ( num_tris_1 + num_tris_2 > TriCountThresh );
 
            if ( build_cache ) 
            {
                // 충분한 삼각형이 있으면 캐시 생성
                collect_triangles( iChild1, TriHash.GetValue() );  // 모든 하위 삼각형 수집
                collect_triangles( iChild2, TriHash.GetValue() );
                
                make_box_fast_winding_cache( IBox, TriHash.GetValue(), TriCache );
            }
 
            return ( num_tris_1 + num_tris_2 );
        }
    }
}

트리의 노드를 재귀 순회 하면서 FastWindingCache를 생성한다.

3. 테일러 전개를 위한 계수 계산

void make_box_fast_winding_cache( int IBox, const TSet< int >& Triangles, const FMeshTriInfoCache& TriCache )
	{
		check(FastWindingCache.Find(IBox) == nullptr);
 
		// construct cache
		FWNInfo cacheInfo;
		FastTriWinding::ComputeCoeffs
		(
    		*Tree->Mesh, 
    		Triangles, TriCache, 
    		cacheInfo.Center, 
    		cacheInfo.R, 
    		cacheInfo.Order1Vec, 
    		cacheInfo.Order2Mat
        );
 
		FastWindingCache.Add( IBox, cacheInfo );
	}

FastTriWinding::ComputeCoeffs()를 통해 계산된 계수들은 FWNInfo에 캐슁된다.
각 계수들은 다음과 같은 의미를 가진다.

P : 전개 중심점
R : 전개 반지름 (모든 정점 중 P로부터 최대 거리)
Order1 : 1차 계수 벡터 = $\sum (면적 \times 법선)$
Order2 : 2차 계수 행렬 = $\sum (면적 \times 외적행렬 (중심점차이, 법선))$

중심점 P의 계산

// 면적 가중 중심점 계산 (Expansion Center)
FVector3d P = FVector3d::Zero();
double sum_area = 0;
 
for ( int tid : Triangles )
{
    double Area = TriCache.Areas[ tid ];
    sum_area += Area;
    P += Area * TriCache.Centroids[ tid ];  // 면적 × 중심점
}
 
P /= sum_area;  // P = 면적 가중 평균 중심점

반지름 R, 1차 계수 벡터 Order1, 2차 계수 벡터 Order2의 계산

FVector3d Order1;
FMatrix3d Order2;
double RSq;
 
for ( int tid : Triangles )
{
    Mesh.GetTriVertices( tid, P0, P1, P2 );
    TriCache.GetTriInfo( tid, n, a, c ); // 법선, 면적, 중심점
 
    Order1 += a * n; // 1차 계수: 면적 × 법선 벡터
 
    FVector3d dcp = c - P; // 삼각형 중심점 - 전개 중심점
    Order2 += a * FMatrix3d( dcp, n ); // 2차 계수: 면적 × 외적 행렬
 
    // 반지름 R 계산 (최대 거리)
    double MaxDistSq = FMath::Max3( DistanceSquared( P0, P ), DistanceSquared( P1, P ), DistanceSquared( P2, P ) );
    RSq = FMath::Max( RSq, MaxDistSq );
}
 
R = FMath::Sqrt( RSq );

FastWindingNumber

미리 계산된 테일러 전개를 위한 계수를 통해 FWN을 계산하여 반환

1. 트리의 재귀 순회

double branch_fast_winding_num( int IBox, FVector3d P ) const
{
    double branch_sum = 0;
    int idx = Tree->BoxToIndex[ IBox ];
 
    if ( idx < Tree->TrianglesEnd ) // 🍃 리프 노드: 정확한 solid angle 계산
    {
        int num_tris = Tree->IndexList[ idx ];
        
        for ( int i = 1; i <= num_tris; ++i )
        {
            FVector3d a, b, c;
            
            int ti = Tree->IndexList[ idx + i ];            
            Tree->Mesh->GetTriVertices( ti, a, b, c );
            
            double angle = VectorUtil::TriSolidAngle( a, b, c, P );  // 정확한 계산
            branch_sum += angle / FMathd::FourPi;
        }
    }
    else // 🌳 내부 노드: 캐시 사용 또는 재귀 호출
    {
        if ( iChild1 < 0 ) 
        {
            // 1개 자식
            iChild1 = (-iChild1) - 1;
            bool contained = Tree->box_contains( iChild1, P );
 
            if ( contained == false && can_use_fast_winding_cache( iChild1, P ) )
            {
                // ⚡ 캐시 사용 (빠른 근사)
                branch_sum += evaluate_box_fast_winding_cache( iChild1, P );
            }
            else
            {
                // 🔄 재귀 호출 (정확한 계산)
                branch_sum += branch_fast_winding_num( iChild1, P );
            }
        }
        else
        {
            // 2개 자식: 각각 처리
            // ... 유사한 로직
        }
    }
    return branch_sum;
}

메쉬를 이루는 TMeshAABBTree3의 노드를 재귀 순회 하면서 FWN을 계산한다. 이 때 테일러 전개를 통한 근사값으로 계산할 것인지 각 삼각형에 대해 정확하게 계산할 것인지 분기하게 된다.

2. 테일러 전개를 통한 근사값으로 FWN을 계산할지 여부

bool can_use_fast_winding_cache( int IBox, const FVector3d& Q ) const
{
    const FWNInfo* cacheInfo = FastWindingCache.Find( IBox );
    if ( !cacheInfo )
    {
        return false;  // 캐시가 없음
    }
 
    double dist_qp = Distance( cacheInfo->Center, Q );
    
    if ( dist_qp > FWNBeta * cacheInfo->R ) // 충분히 멀리 있음
    {
        return true;   
    }
    
    return false; // 너무 가까움
}

FWNBeta : 안전 계수 ( 기본값 : 2.0 )
cacheInfo->R : 삼각형 그룹의 반지름

점 Q의 거리가 충분히 멀면 테일러 전개를 통한 근사값으로 FWN을 계산한다. 반대로 가깝다면 직접 삼각형 그룹과의 거리를 정확하게 계산한다.

3. 테일러 전개를 통한 근사값 계산

1 / 2차 근사 분기

double evaluate_box_fast_winding_cache( int IBox, const FVector3d& Q ) const
{
    const FWNInfo& cacheInfo = FastWindingCache[ IBox ];
 
    if ( FWNApproxOrder == 2 )
    {
        // 2차 근사 (더 정확)
        return FastTriWinding::EvaluateOrder2Approx( cacheInfo.Center, cacheInfo.Order1Vec, cacheInfo.Order2Mat, Q );
    }
    else
    {
        // 1차 근사 (더 빠름)
        return FastTriWinding::EvaluateOrder1Approx( cacheInfo.Center, cacheInfo.Order1Vec, Q );
    }
}

1차 근사 공식 함수

inline double EvaluateOrder1Approx( const FVector3d& Center, const FVector3d& Order1Coeff, const FVector3d& Q )
{
    FVector3d dpq = Center - Q;
    double len = dpq.Length();
    
    return ( 1.0 / FMathd::FourPi ) * Order1Coeff.Dot( dpq / ( len * len * len ) );
}

$W (Q) \approx \frac{1}{4 π} \sum Area \cdot Normal \cdot \frac{P - Q}{∣ P - Q ∣ ^{3}}$

2차 근사 공식 함수

inline double EvaluateOrder2Approx(const FVector3d& Center, const FVector3d& Order1Coeff, const FMatrix3d& Order2Coeff, const FVector3d& Q )
{
    FVector3d dpq = Center - Q;
    
    double len  = dpq.Length();
    double len3 = len * len * len;
    
    double fourPi_len3 = 1.0 / ( FMathd::FourPi * len3 );
 
    // 1차 항
    double Order1 = fourPi_len3 * Order1Coeff.Dot( dpq );
 
    // 2차 Hessian 계산
    double c = -3.0 / ( FMathd::FourPi * len3 * len * len );
    
    FMatrix3d hessian
    (
        fourPi_len3 + c * dpq.X * dpq.X, c * dpq.X * dpq.Y,               c * dpq.X * dpq.Z,
        c * dpq.Y * dpq.X,               fourPi_len3 + c * dpq.Y * dpq.Y, c * dpq.Y * dpq.Z,
        c * dpq.Z * dpq.X,               c * dpq.Z * dpq.Y,               fourPi_len3 + c * dpq.Z * dpq.Z
    );
 
    double Order2 = Order2Coeff.InnerProduct( hessian );
 
    return Order1 + Order2;
}

$W (Q) \approx 1 차항 + \frac{1}{2} (x - P)^{T} H (x - P)$

전개 중심점 $P$ 에서 멀리 떨어진 점 $Q$ 에 대해 근사 계산을 수행하여 계산 속도를 향상시킨다.

Cryun's WIKI

탐색기