Cryun's WIKI

FMeshBoolean.Compute()

4 min read

전처리

메시 복사 및 변환

FDynamicMesh3 CutMeshB( *Meshes[ 1 ] );
if (Result != Meshes[ 0 ] )
{
    *Result = *Meshes[ 0 ];
}
FDynamicMesh3* CutMesh[ 2 ]{ Result, &CutMeshB };

연산을 수행할 두 메쉬를 FDynamicMesh3로 변환한다. CutMesh는 연산 편의상 포인터를 캐슁해두는 용도이다.


좌표계 정규화

FAxisAlignedBox3d CombinedAABB( CutMesh[ 0 ]->GetBounds( true ), Transforms[ 0 ] );
FAxisAlignedBox3d MeshB_AABB  ( CutMesh[ 1 ]->GetBounds( true ), Transforms[ 1 ] );
 
CombinedAABB.Contain( MeshB_AABB );
 
double ScaleFactor = 1.0 / FMath::Clamp( CombinedAABB.MaxDim(), 0.01, 1000000.0 );
for ( int MeshIdx = 0; MeshIdx < 2; MeshIdx++ )
{
    FTransformSRT3d CenteredTransform = Transforms[ MeshIdx ];
    CenteredTransform.SetTranslation( ScaleFactor * ( CenteredTransform.GetTranslation() - CombinedAABB.Center() ) );
    CenteredTransform.SetScale( ScaleFactor * CenteredTransform.GetScale() );
    MeshTransforms::ApplyTransform( *CutMesh[ MeshIdx ], CenteredTransform, true );
}
 
ResultTransform = FTransformSRT3d( CombinedAABB.Center() );
ResultTransform.SetScale( FVector3d::One() * ( 1.0 / ScaleFactor ) );

두 메쉬의 경계( Bound )를 모두 포함하는 AABB ( CombinedAABB )를 생성한다. 생성한 CombinedAABB를 기준으로 두 메쉬의 트랜스폼을 정규화한다.



교차점 검출

AABB Tree 구축

FDynamicMeshAABBTree3 Spatial[ 2 ]{ CutMesh[ 0 ], CutMesh[ 1 ] };
Spatial[ 0 ].SetTolerance( SnapTolerance );
Spatial[ 1 ].SetTolerance( SnapTolerance );

두 메쉬간에 교차점을 검출하기 위해 TMeshAABBTree3를 준비한다.


교차점 검출

MeshIntersection::FIntersectionsQueryResult Intersections = Spatial[ 0 ].FindAllIntersections
( 
    Spatial[ 1 ], 
    nullptr, 
    IMeshSpatial::FQueryOptions(), 
    IMeshSpatial::FQueryOptions(),
    [ this ] ( FIntrTriangle3Triangle3d& Intr )
    {
        Intr.SetTolerance( SnapTolerance );
        return Intr.Find();
 
        // TODO: if we revisit "thick" tri tri collisions, this is where we'd call:
        // 	ThickTriTriIntersection(Intr, SnapTolerance);
    }
);

TMeshAABBTree3의 FindAllIntersections를 통해 두 메쉬의 교차점을 검출한다. 검출된 교차점 정보는 FIntersectionsQueryResult에 담긴다.



메시 절단

하나의 메쉬에서만 연산이 이루어지는지 체크

bool bOpOnSingleMesh = Operation == EBooleanOp::TrimInside     || 
                       Operation == EBooleanOp::TrimOutside    || 
                       Operation == EBooleanOp::NewGroupInside || 
                       Operation == EBooleanOp::NewGroupOutside;

위 4가지 타입의 연산의 종류는 하나의 메쉬에서만 연산이 이루어진다.


교차점을 따른 메시 분할

FMeshMeshCut Cut( CutMesh[ 0 ], CutMesh[ 1 ] );
 
Cut.bTrackInsertedVertices = bCollapseDegenerateEdgesOnCut;
Cut.bMutuallyCut = !bOpOnSingleMesh;
Cut.SnapTolerance = SnapTolerance;
 
Cut.Cut( Intersections );

FMeshMeshCut을 이용해 메쉬를 교차선을 따라 분할한다.



퇴화 엣지 제거

bCollapseDegenerateEdgesOnCut프로퍼티를 통해 허용된 경우에만 제거한다. 교차선을 통해 메쉬를 절단하면 교차점 부근에서 매우 짧은 엣지들이 생성된다. 이런 짧은 엣지들은 후속 연산에서 수치적으로 불안정성을 야기하기도 하고 불필요한 코스트가 들어가므로 제거하는편이 좋다. 내용이 길어 실제 코드에 대한 설명은 퇴화 엣지 제거에서 한다.



Operation 적용

두 메쉬간의 EBooleanOp 연산을 한다. 이를 통해 삼각형을 삭제하거나 리그룹하는 결과를 가지게 된다. 마찬가지로 내용이 길어 코드에 대한 설명은 Operation 적용에서 한다.



정점 매칭

Operation 적용까지 마치면 두 메쉬의 경계에서 서로 거의 같은 위치에 있으면서 다른 정점들이 생성된다. 이 정점들을 통합하여 좀 더 매끄럽게 다듬는 후처리 과정을 진행한다. 이 부분은 정점 매칭에서 설명한다.



후처리

마지막 후처리를 통해 연산을 마무리한다.

그래프 뷰

백링크