FMeshBoolean.Compute().정점 매칭

전처리

1. 데이터 구조 초기화

// 두 메시 모두 처리된 경우 메시 간 정점들을 대응시킴
TMap< int, int > AllVIDMatches; // cutmesh 0에서 cutmesh 1로의 매칭된 정점 ID 매핑
if ( NumMeshesToProcess == 2 )
{
    TMap< int, int > FoundMatchesMaps[ 2 ]; // 메시 1->0과 메시 0->1의 매칭된 정점 ID 매핑
    double SnapToleranceSq = SnapTolerance * SnapTolerance;

데이터 구조 설명

변수	타입	설명
`AllVIDMatches`	`TMap< int, int >`	최종 매칭 결과 ( 메시 0 VID → 메시 1 VID )
`FoundMatchesMaps[ 2 ]`	`TMap< int, int >[ 2 ]`	양방향 매칭 정보 ( `[ 0 ]` : 메시 1 → 0, `[ 1 ]` : 메시 0 → 1 )
`SnapToleranceSq`	`double`	거리 비교 최적화 ( 제곱 거리, √ 연산 회피 )

2. 공간 인덱스 구조 설정

// 이제 경계에 있는 세그먼트들이 메시 간에 1:1 정점 대응관계를 갖도록 보장
for ( int MeshIdx = 0; MeshIdx < 2; MeshIdx++ )
{
    int OtherMeshIdx = 1 - MeshIdx;
    FDynamicMesh3& OtherMesh = *CutMesh[ OtherMeshIdx ];
 
    // 정점 해시 그리드 설정
    TPointHashGrid3d< int > OtherMeshPointHash( OtherMesh.GetBounds( true ).MaxDim() / 64, -1 );
    for ( int BoundaryVID : PossUnmatchedBdryVerts[ OtherMeshIdx ] )
    {
        OtherMeshPointHash.InsertPointUnsafe( BoundaryVID, OtherMesh.GetVertex( BoundaryVID ) );
    }

메쉬별로 이터레이션 하면서 상대편 메쉬의 정점들을 TPointHashGrid3로 구성한다.

3. 엣지들의 옥트리 설정

    // 모서리 옥트리 설정
    FSparseDynamicOctree3 EdgeOctree;
    EdgeOctree.RootDimension = .25;
    EdgeOctree.SetMaxTreeDepth( 7 );
 
    // 엣지의 AABB 계산 람다식
    auto EdgeBounds = [ &OtherMesh ] ( int EID )
    {
        FDynamicMesh3::FEdge Edge = OtherMesh.GetEdge( EID );
        FVector3d A = OtherMesh.GetVertex( Edge.Vert.A );
        FVector3d B = OtherMesh.GetVertex( Edge.Vert.B );
 
        // AABB 계산을 위한 min/max 정렬
        if ( A.X > B.X ) { Swap( A.X, B.X ); }
        if ( A.Y > B.Y ) { Swap( A.Y, B.Y ); }
        if ( A.Z > B.Z ) { Swap( A.Z, B.Z ); }
 
        return FAxisAlignedBox3d( A, B );
    };
 
    // 옥트리에 엣지 추가
    auto AddEdge = [ &EdgeOctree, &OtherMesh, EdgeBounds ]( int EID )
    {
        EdgeOctree.InsertObject( EID, EdgeBounds( EID ) );
    };
 
    // 옥트리에 엣지 갱신
    auto UpdateEdge = [ &EdgeOctree, &OtherMesh, EdgeBounds ]( int EID )
    {
        EdgeOctree.ReinsertObject( EID, EdgeBounds( EID ) );
    };
 
    // 경계 모서리들을 옥트리에 추가
    for ( int EID : CutBoundaryEdges[ OtherMeshIdx ] )
    {
        AddEdge( EID );
    }
 
    TArray< int > EdgesInRange;  // 검색 결과를 담을 배열

엣지들을 FSparseDynamicOctree3를 통해 옥트리로 준비한다.
다음은 옥트리를 생성하는 옵션들에 대한 설명이다.

항목	설명
루트 크기	`RootDimension = 0.25`
최대 깊이	`MaxTreeDepth = 7` ( $2^{7} = 128$ 세분화 )

정점 매칭

1. 매칭 전략 설정

    // OtherMesh VID에서 ProcessMesh VID로의 매핑
    // 여러 경계 정점이 다른 메시 경계의 동일한 정점에 매핑되는 경우 최고의 매칭만 유지하기 위해 사용
    TMap< int, int >& FoundMatches = FoundMatchesMaps[ MeshIdx ];

Key : 상대방 메시의 정점 ID
Value : 현재 메시에서 매칭된 정점 ID

매칭 전략의 핵심

메시 A:  ●₁  ●₂  ●₃
         ↘  ↓  ↙
메시 B:     ○

●₁, ●₂, ●₃ 모두 ○에 가장 가까울 때 가장 가까운 하나만 선택한다.

2. 정점-정점 매칭

    for ( int BoundaryVID : PossUnmatchedBdryVerts[ MeshIdx ] )
    {
        if ( MeshIdx == 1 && FoundMatchesMaps[ 0 ].Contains( BoundaryVID ) )
        {
            continue; // 이전 순회에서 이미 매칭된 정점은 건너뛴다.
        }
 
        FVector3d Pos = CutMesh[ MeshIdx ]->GetVertex( BoundaryVID );
        TPair< int, double > VIDDist = OtherMeshPointHash.FindNearestInRadius( Pos, SnapTolerance, [ &Pos, &OtherMesh ] ( int VID )
        {
            return DistanceSquared( Pos, OtherMesh.GetVertex( VID ) );
        } );
        
        int NearestVID = VIDDist.Key; // ID of nearest vertex on other mesh
        double DSq = VIDDist.Value;   // square distance to that vertex
 
        if ( NearestVID != FDynamicMesh3::InvalidID )
        {
            int* Match = FoundMatches.Find( NearestVID );
            if ( Match )
            {
                double OldDSq = DistanceSquared( CutMesh[ MeshIdx ]->GetVertex( *Match ), OtherMesh.GetVertex( NearestVID ) );
                if ( DSq < OldDSq ) // new vertex is a better match than the old one
                {
                    int OldVID = *Match; // copy old VID out of match before updating the TMap
                    FoundMatches.Add( NearestVID, BoundaryVID ); // new VID is recorded as best match
 
                    // old VID is swapped in as the one to consider as unmatched
                    // it will now be matched below
                    BoundaryVID = OldVID;
                    Pos = CutMesh[ MeshIdx ]->GetVertex( BoundaryVID );
                    DSq = OldDSq;
                }
                NearestVID = FDynamicMesh3::InvalidID; // one of these vertices will be unmatched
            }
            else
            {
                FoundMatches.Add( NearestVID, BoundaryVID );
            }
        }

PossUnmatchedBdryVerts의 정점을 순회하면서 처리한다. 이미 매칭된 정점인 경우 건너뛰며 TPointHashGrid3를 통해 SnapTolerance 반경 내 가장 가까운 정점을 찾는다. 이렇게 찾은 가장 가까운 정점은 기존 매칭( FoundMatches )이 없으면 새로운 매칭을 추가하고 있으면 더 가까운 정점으로 매칭을 교체한다.

3. 정점-모서리 매칭 ( 엣지 분할 )

        // 정점 매칭이 실패한 경우 가장 가까운 모서리를 분할하여 새 정점을 생성
        if ( NearestVID == FDynamicMesh3::InvalidID )
        {
            // vertex had no match -- try to split edge to match it
            FAxisAlignedBox3d QueryBox( Pos, SnapTolerance );
            EdgesInRange.Reset();
            EdgeOctree.RangeQuery( QueryBox, EdgesInRange );
 
            int OtherEID = FindNearestEdge( OtherMesh, EdgesInRange, Pos );
            if ( OtherEID != FDynamicMesh3::InvalidID )
            {
                FVector3d EdgePts[ 2 ];
                OtherMesh.GetEdgeV( OtherEID, EdgePts[ 0 ], EdgePts[ 1 ] );
                // only accept the match if it's not going to create a degenerate edge
                if ( DistanceSquared( EdgePts[ 0 ], Pos ) > SnapToleranceSq && DistanceSquared( EdgePts[ 1 ], Pos ) > SnapToleranceSq )
                {
                    FSegment3d Seg( EdgePts[ 0 ], EdgePts[ 1 ] );
                    double Along = Seg.ProjectUnitRange( Pos );
                    
                    FDynamicMesh3::FEdgeSplitInfo SplitInfo;
                    if ( ensure( EMeshResult::Ok == OtherMesh.SplitEdge( OtherEID, SplitInfo, Along ) ) )
                    {
                        FoundMatches.Add( SplitInfo.NewVertex, BoundaryVID );
                        OtherMesh.SetVertex( SplitInfo.NewVertex, Pos );
                        CutBoundaryEdges[ OtherMeshIdx ].Add( SplitInfo.NewEdges.A );
                        UpdateEdge( OtherEID );
                        AddEdge( SplitInfo.NewEdges.A );
                        // Note: Do not update PossUnmatchedBdryVerts with the new vertex, because it is already matched by construction
                        // Likewise do not update the pointhash -- we don't want it to find vertices that were already perfectly matched
                    }
                }
            }
        }
    }

2. 정점-정점 매칭이 실패한 경우 엣지를 분할하여 새로운 정점을 생성한 후 다시 매칭을 시도한다.

알고리즘

3. 엣지들의 옥트리 설정에서 만든 옥트리를 통해 반경 내 엣지를 검색
쿼리된 엣지들 중에서 가장 가까운 엣지 선택
엣지에서 새로운 정점을 생성하여 분할할 때 엣지 길이가 SnapTolerance 이상인지 확인
엣지 분할
- 투영 위치 계산 ( Seg.ProjectUnitRange(Pos) )
- 모서리 분할 수행 ( SplitEdge )
- 새 정점 위치를 원본 정점 위치로 정확히 이동
데이터 갱신
- 매칭 정보 추가
- 새 경계 모서리 추가
- 옥트리 갱신

4. 최종 스냅 및 통합

    // 매칭된 정점들의 위치를 정확히 일치시킴
    for ( TPair< int, int >& Match : FoundMatches )
    {
        CutMesh[ MeshIdx ]->SetVertex( Match.Value, OtherMesh.GetVertex( Match.Key ) );
 
        // AllVIDMatches 에 메시 0 → 메시 1 방향으로 통일하여 저장
        int VIDs[ 2 ]{ Match.Key, Match.Value }; // just so we can access by index
        AllVIDMatches.Add( VIDs[ 1 - MeshIdx ], VIDs[ MeshIdx ] );
    }
}

Cryun's WIKI

탐색기