전처리
Operation을 적용, 즉 메쉬를 구성하는 삼각형들의 정보를 변경하기 위해 CutBoundaryEdiges, PossUnmatchedBdryVerts, KeepTri를 준비한다. 삼각형을 하나씩 처리하지 않고 데이터를 준비 후 일괄 처리하는 이유는 다음과 같다.
- 삼각형을 하나씩 지우면 판단 기준이 변할 수 있음
- 와인딩 넘버(내부/외부 판정)의 일관성 유지
1. 데이터 컨테이너 준비
TArray< int > CutBoundaryEdges [ 2 ]; // 불린 연산 후 새로운 경계가 될 엣지들
TSet < int > PossUnmatchedBdryVerts[ 2 ]; // 다른 메시에 대응하는 정점이 없을 수 있는 절단 경계의 정점들
TArray< bool > KeepTri[ 2 ]; // 먼저 두 메시 모두에서 어떤 삼각형을 삭제할지 결정
// 동일평면 삼각형을 유지할 때 다른 표면을 삭제하는지 확인하는 배열
// 메시 0에만 필요 (동일평면 표면을 보존할 때 참조하는 메시)
TArray< int32 > DeleteIfOtherKept;
if ( NumMeshesToProcess > 1 )
{
DeleteIfOtherKept.Init( -1, CutMesh[ 0 ]->MaxTriangleID() );
}DeleteIfOtherKept는 두 개의 판이 같은 평면에 있을 때 한 쪽 판의 삼각형을 유지하면 다른 쪽 판의 같은 위치 삼각형은 삭제하기 위해 추적용으로 캐슁해두는 컨테이너이다.
2. 각 메쉬별 준비
for ( int MeshIdx = 0; MeshIdx < NumMeshesToProcess; MeshIdx++ )
{
// 현재 처리할 메시와 상대방 메시 설정
TFastWindingTree< FDynamicMesh3 > Winding( &Spatial[ 1 - MeshIdx ] ); // 상대방 메시의 와인딩 트리
FDynamicMeshAABBTree3& OtherSpatial = Spatial[ 1 - MeshIdx ]; // 상대방 메시의 공간 트리
FDynamicMesh3& ProcessMesh = *CutMesh[ MeshIdx ]; // 현재 처리할 메시
int MaxTriID = ProcessMesh.MaxTriangleID();
KeepTri[ MeshIdx ].SetNumUninitialized( MaxTriID ); // 삼각형 유지 여부 배열 크기 설정
}MeshIdx == 0: 메시 0을 처리하면서 메시 1을 기준으로 판정MeshIdx == 1: 메시 1을 처리하면서 메시 0을 기준으로 판정Spatial[ 1 - MeshIdx ]: 0 → 1, 1 → 0으로 상대방 메시를 가리킴
이번에 처리할 메쉬 및 상대방 메쉬, 그리고 KeepTri등을 미리 초기화해둔다. 또한 상대방 메쉬의 TFastWindingTree를 미리 구성해둔다. 삼각형 단위로 상대방 메쉬의 안쪽 / 바깥쪽 에 위치해 있는지 구분하여 잔존 여부를 결정해야 하는데 FWN을 빠르게 계산하기 위해 구성해두는 것이다.
3. 연산별 규칙 설정
// 동일평면 삼각형 처리 규칙
bool bCoplanarKeepSameDir = ( Operation != EBooleanOp::Difference &&
Operation != EBooleanOp::TrimInside &&
Operation != EBooleanOp::NewGroupInside );
// 내부/외부 삼각형 제거 규칙
bool bRemoveInside = 1; // 기본값: 내부 삼각형 제거 (Union 등)
if ( Operation == EBooleanOp::NewGroupOutside ||
Operation == EBooleanOp::TrimOutside ||
Operation == EBooleanOp::Intersect ||
( Operation == EBooleanOp::Difference && MeshIdx == 1 ) )
{
bRemoveInside = 0; // 외부 삼각형 제거
}| 연산 타입 | bCoplanarKeepSameDir | bRemoveInside | 의미 | 비고 |
|---|---|---|---|---|
| Union | true | 1 | 내부 삼각형 제거 동일평면은 같은 방향 유지 | 두 객체를 합치기 → 겹치는 내부 부분 제거 |
| Intersection | true | 0 | 외부 삼각형 제거 | 겹치는 부분만 남기기 → 외부 부분 제거 |
| Difference | false | 메시에 따라 다름 | 복잡한 규칙 적용 | A에서 B를 빼기 → 복잡한 계산 필요 |
4. 법선 벡터 계산 및 필터 설정
// 상대방 메시의 법선 벡터들 계산
FMeshNormals OtherNormals( OtherSpatial.GetMesh() );
OtherNormals.ComputeTriangleNormals();
// 동일평면 판정을 위한 허용 오차 설정
const double OnPlaneTolerance = SnapTolerance;
// 퇴화된 삼각형을 제외하는 필터 설정
IMeshSpatial::FQueryOptions NonDegenCoplanarCandidateFilter
(
OnPlaneTolerance,
[ &OtherNormals ] ( int TID ) -> bool // 퇴화된 삼각형을 매칭에서 제외하는 필터
{
// 관례상, 퇴화된 삼각형의 법선은 영벡터
return !OtherNormals[ TID ].IsZero();
}
);법선 벡터는 빠르게 계산하기 위해 FMeshNormals를 이용한다.
5. KeepTri, DeleteIfOtherKept 채우기
ParallelFor( MaxTriID, [&] ( int TID )
{
if ( !ProcessMesh.IsTriangle( TID ) ) // 유효하지 않은 삼각형은 건너뛰기
{
return;
}
// 1단계: 삼각형 정보 가져오기
FTriangle3d Tri;
ProcessMesh.GetTriVertices( TID, Tri.V[ 0 ], Tri.V[ 1 ], Tri.V[ 2 ] );
FVector3d Centroid = Tri.Centroid();
// 동일평면 케이스를 먼저 확인
// 가장 가까운 상대방 삼각형 찾음
double DSq;
int OtherTID = OtherSpatial.FindNearestTriangle( Centroid, DSq, NonDegenCoplanarCandidateFilter );
if ( OtherTID > -1 ) // // 매칭되는 삼각형이 있을 때만 동일평면으로 고려
{
FVector3d OtherNormal = OtherNormals[ OtherTID ];
FVector3d Normal = ProcessMesh.GetTriNormal( TID );
double DotNormals = OtherNormal.Dot( Normal );
//if (FMath::Abs(DotNormals) > .9) // TODO: do we actually want to check for a normal match? coplanar vertex check below is more robust?
{
// 동일평면 매칭임을 확실히 하기 위해, 정점들도 다른 메시 위에 있는지 확인
bool bAllTrisOnOtherMesh = true;
for ( int Idx = 0; Idx < 3; Idx++ )
{
// 메시 절단 경계에서의 추가 오차를 고려해 약간 더 관대한 허용 오차 사용
if ( OtherSpatial.FindNearestTriangle( Tri.V[ Idx ], DSq, OnPlaneTolerance * 2 ) == FDynamicMesh3::InvalidID )
{
bAllTrisOnOtherMesh = false;
break;
}
}
if ( bAllTrisOnOtherMesh )
{
// 동일평면 삼각형의 경우 첫 번째 메시를 우선시; 다른 메시에서만 삭제
// 완전히 퇴화된 삼각형의 경우에도 삭제를 선호
if ( MeshIdx != 0 || Normal.IsZero() )
{
KeepTri[ MeshIdx ][ TID ] = false;
return;
}
else // 첫 번째 메시이고 유효한 법선을 가진 경우, 매칭되는 삼각형의 방향에 따라 로직 결정
{
bool bKeep = DotNormals > 0 == bCoplanarKeepSameDir;
KeepTri[ MeshIdx ][ TID ] = bKeep;
if ( NumMeshesToProcess > 1 && bKeep )
{
// 이 삼각형을 유지했다면, 삭제될 것으로 예상되는 동일평면 쌍을 기억
// 만약 삭제되지 않는다면 (예: 동일평면이 아니었던 경우) 대신 이것을 삭제
DeleteIfOtherKept[ TID ] = OtherTID;
}
return;
}
}
}
}
// 동일평면 결과를 이미 반환하지 않은 경우; 와인딩 넘버 사용
double WindingNum = Winding.FastWindingNumber( Centroid );
KeepTri[ MeshIdx ][ TID ] = ( WindingNum > WindingThreshold ) != bRemoveInside;
} );삼각형별로 병렬처리된다. 우선 동일 평면 삼각형에 대한 처리가 결정되고 동일 평면 삼각형으로 처리되지 않는 경우 FWN을 통해 잔존 여부가 결정된다.
6. 동일 평면 삼각형 처리
// 매칭된 두 번째 메시 삼각형이 실제로 삭제되지 않았다면 동일평면 삼각형을 유지하지 않음
if ( NumMeshesToProcess > 1 )
{
for ( int TID : CutMesh[0]->TriangleIndicesItr() )
{
int32 DeleteIfOtherKeptTID = DeleteIfOtherKept[ TID ];
if ( DeleteIfOtherKeptTID > -1 && KeepTri[ 1 ][ DeleteIfOtherKeptTID ] )
{
KeepTri[ 0 ][ TID ] = false;
}
}
}두번째 메쉬 처리시에 동일 평면 삼각형을 체크하여 첫번째 메쉬에서의 삼각형을 삭제 처리한다.
7. CutBoundaryEdges, PossUnmatchedBdryVerts 채우기
for ( int MeshIdx = 0; MeshIdx < NumMeshesToProcess; MeshIdx++ )
{
FDynamicMesh3& ProcessMesh = *CutMesh[ MeshIdx ];
for ( int EID : ProcessMesh.EdgeIndicesItr() ) // 모든 엣지를 순회
{
FDynamicMesh3::FEdge Edge = ProcessMesh.GetEdge( EID );
// 경계 엣지가 아닌 경우
if ( Edge.Tri.B == IndexConstants::InvalidID || KeepTri[ MeshIdx ][ Edge.Tri.A ] == KeepTri[ MeshIdx ][ Edge.Tri.B ] )
{
continue;
}
CutBoundaryEdges[ MeshIdx ].Add( EID );
PossUnmatchedBdryVerts[ MeshIdx ].Add( Edge.Vert.A );
PossUnmatchedBdryVerts[ MeshIdx ].Add( Edge.Vert.B );
}
}새로운 경계가 되는 엣지를 판단하는 부분은 다음과 같이 설명된다.
조건 1 : Edge.Tri.B == InvalidID
- 이미 원래 메시의 경계 모서리 (한쪽 면만 있음)
- 불린 연산으로 새로 생긴 경계가 아님
조건 2 : KeepTri[ A ] == KeepTri[ B ]
- 양쪽 삼각형이 모두 유지되거나 모두 삭제됨
- 경계가 생기지 않음
경계 모서리가 되는 경우
KeepTri[A] != KeepTri[B]: 한쪽은 유지, 한쪽은 삭제- 이때 새로운 경계가 생성
이 때 새로운 경계 엣지를 추가하면서 매칭되지 않을 수 있는 정점을 함께 추적해준다. 수치 오차, 메시 절단 과정의 불완전성, 토폴로지 불일치 등과 같은 이유로 매칭되지 않는 정점이 발생할 수 있기 때문이다.
실제 처리
1. 삼각형 삭제 및 리그룹
bool bRegroupInsteadOfDelete = Operation == EBooleanOp::NewGroupInside || Operation == EBooleanOp::NewGroupOutside;
int NewGroupID = -1;
TArray< int > NewGroupTris;
if ( bRegroupInsteadOfDelete )
{
// 리그룹은 첫번째 메쉬에서만 한다
ensure( NumMeshesToProcess == 1 );
NewGroupID = CutMesh[ 0 ]->AllocateTriangleGroup();
}
for ( int MeshIdx = 0; MeshIdx < NumMeshesToProcess; MeshIdx++ )
{
FDynamicMesh3& ProcessMesh = *CutMesh[ MeshIdx ];
for ( int TID = 0; TID < KeepTri[ MeshIdx ].Num(); TID++ )
{
if ( ProcessMesh.IsTriangle( TID ) && !KeepTri[ MeshIdx ][ TID ] )
{
if ( bRegroupInsteadOfDelete )
{
ProcessMesh.SetTriangleGroup( TID, NewGroupID );
NewGroupTris.Add( TID ); // 리그룹화된 삼각형 목록에 추가
}
else
{
ProcessMesh.RemoveTriangle( TID, true, false );
}
}
}
}
if ( bRegroupInsteadOfDelete )
{
FMeshConnectedComponents Components( CutMesh[ 0 ] );
Components.FindConnectedTriangles( NewGroupTris );
for ( int ComponentIdx = 1; ComponentIdx < Components.Num(); ComponentIdx++ )
{
int SplitGroupID = CutMesh[ 0 ]->AllocateTriangleGroup();
for ( int TID : Components.GetComponent( ComponentIdx ).Indices )
{
CutMesh[ 0 ]->SetTriangleGroup( TID, SplitGroupID ); // 새 그룹으로 이동
}
}
}삭제 vs 재그룹화의 차이점
| 구분 | 특징 |
|---|---|
| 삭제 | 삼각형을 메시에서 완전히 제거 메모리에서 사라짐 용도: Union, Intersection, Difference 연산 |
| 리그룹 | 삼각형은 유지하되 다른 그룹으로 분류 여전히 메시에 존재 용도: NewGroupInside, NewGroupOutside 연산 |
리그룹이 0번 메쉬에서만 가능한 이유
- 재그룹화는 하나의 메시 내에서만 의미가 있음
- 두 메시를 합치는 게 아니라 하나의 메시를 분류하는 작업