FMeshSurfacePath.AddViaPlanarWalk()

FMeshSurfacePath에서 평면을 따라 메시 표면에 경로를 생성하는 함수이다. Planar Walk 알고리즘을 구현하여 시작점에서 끝점까지 메시 표면을 따라 최단 경로를 찾는다. 이 함수는 Wrapper함수이며 실제 알고리즘은 WalkMeshPlanar 함수에 구현되어 있다.

Input

---

타입	이름	설명
int	StartTri	시작 삼각형 ID
int	StartVID	시작 정점 ID (-1이면 자동 계산)
FVector3d	StartPt	시작 위치 (3D 좌표)
int	EndTri	끝 삼각형 ID
int	EndVertID	끝 정점 ID (-1이면 자동 계산)
FVector3d	EndPt	끝 위치 (3D 좌표)
FVector3d	WalkPlaneNormal	평면의 법선 벡터
TFunction	VertexToPosnFn	정점 ID → 3D 좌표 변환 함수 (nullptr이면 기본 함수 사용)
bool	bAllowBackwardsSearch	역방향 탐색 허용 여부
double	AcceptEndPtOutsideDist	목표점 허용 거리 임계값
double	PtOnPlaneThresholdSq	정점이 평면 위에 있다고 판단하는 거리 제곱
double	BackwardsTolerance	후진 허용 거리

초기화

---

헬퍼 함수 준비

// 삼각형 정점 위치 설정 헬퍼
auto SetTriVertPositions = [ &VertexToPosnFn, &Mesh ] ( FIndex3i TriVertIDs, FTriangle3d& Tri )
{
    Tri.V[ 0 ] = VertexToPosnFn( Mesh, TriVertIDs.A );
    Tri.V[ 1 ] = VertexToPosnFn( Mesh, TriVertIDs.B );
    Tri.V[ 2 ] = VertexToPosnFn( Mesh, TriVertIDs.C );
};

삼각형의 세 정점 ID를 받아서 실제 3D 좌표로 변환한다.

// 점이 삼각형 내부에 있는지 확인
auto PtInsideTri = [] ( const FVector3d& BaryCoord, double BaryThreshold = FMathd::ZeroTolerance )
{
    return BaryCoord[ 0 ] >= -BaryThreshold &&
           BaryCoord[ 1 ] >= -BaryThreshold &&
           BaryCoord[ 2 ] >= -BaryThreshold;
};

무게중심 좌표가 모두 양수면 삼각형 내부로 판정한다.

데이터 구조 초기화

// 탐색 경로 추적 구조체
struct FWalkIndices
{
    FVector3d Position;     // 현재 위치 (변환된 좌표계)
    int       WalkedFromPt; // 이전 점의 인덱스 (-1이면 시작점)
    int       WalkingOnTri; // 현재 위치한 삼각형 ID
};

struct FIndexDistance
{
	int    Index;
	double PathLength;
	double DistanceToEnd;
	
	bool operator<( const FIndexDistance& Other ) const
	{
		return PathLength + DistanceToEnd < Other.PathLength + Other.DistanceToEnd;
	}
};

TArray< TPair< FMeshSurfacePoint, FWalkIndices > > ComputedPointsAndSources; // 탐색 중 발견한 모든 경로 점
TArray< FIndexDistance >                           UnexploredEnds;           // 우선순위 큐
TSet< int >                                        ExploredTriangles;        // 이미 방문한 삼각형
TSet< int >                                        CrossedVertices;          // 이미 통과한 정점

변수	설명
ComputedPointsAndSources	FMeshSurfacePoint와 FWalkIndice를 페어로 지금까지 지나오면서 발견한 모든 포인트를 기록
UnexploredEnds	우선순위 큐 (PathLength + DistanceToEnd로 정렬)
ExploredTriangles	중복 방문 방지용 삼각형 집합
CrossedVertices	중복 방문 방지용 정점 집합

시작점 설정

// 시작 삼각형의 정점 정보 가져오기
FTriangle3d CurrentTri;
FIndex3i StartTriVertIDs = Mesh->GetTriangle( StartTri );
SetTriVertPositions( StartTriVertIDs, CurrentTri );
 
// 시작점이 삼각형 내 어디에 있는지 계산
FDistPoint3Triangle3d CurrentTriDist( StartPt, CurrentTri );
 
if ( StartVID != -1 )
{
    // 시작 정점이 명시된 경우: 해당 정점 사용
    int StartVIDIndex = StartTriVertIDs.IndexOf( StartVID );
    CurrentTriDist.TriangleBaryCoords = FVector3d::Zero();
    CurrentTriDist.TriangleBaryCoords[ StartVIDIndex ] = 1.0;
}
else
{
    // 시작 정점 없으면: 가장 가까운 점 계산
    CurrentTriDist.ComputeResult();
}
 
// 첫 번째 점 추가
ComputedPointsAndSources.Emplace
(
    FMeshSurfacePoint( StartTri, CurrentTriDist.TriangleBaryCoords ),
    FWalkIndices( StartPt, -1, StartTri )
);

초기 거리 계산

// 목표까지의 방향과 거리
FVector3d ForwardsDirection = EndPt - StartPt;
double CurrentDistanceToEnd = ForwardsDirection.Length();
 
// 시작점을 첫 탐색 후보로 추가
UnexploredEnds.Add( { 0, 0, CurrentDistanceToEnd } );

메인 탐색 루프

---

루프 구조

while ( true )
{
    // 무한 루프 방지 안전장치
    if ( !ensure( IterCountSafety++ < NumTriangles * 2 ) )
    {
        return false;
    }
 
    // 우선순위 큐에서 가장 유망한 경로 선택
    if ( UnexploredEnds.Num() )
    {
        FIndexDistance TopEndWithDistance;
        UnexploredEnds.HeapPop( TopEndWithDistance ); // Heap에서 최소값 꺼내기
 
        CurrentEnd           = TopEndWithDistance.Index;
        CurrentPathLength    = TopEndWithDistance.PathLength;
        CurrentDistanceToEnd = TopEndWithDistance.DistanceToEnd;
    }
    else
    {
        return false; // 탐색 실패
    }

알고리즘 핵심: Best-First Search (Dijkstra 유사)

• PathLength + DistanceToEnd가 가장 작은 경로를 우선 탐색
• Heap 자료구조로 효율적으로 관리

종료 조건 확인

// 현재 위치 정보 가져오기
FMeshSurfacePoint FromPt      = ComputedPointsAndSources[ CurrentEnd ].Key;
FWalkIndices      CurrentWalk = ComputedPointsAndSources[ CurrentEnd ].Value;
 
int TriID = CurrentWalk.WalkingOnTri;
 
FIndex3i TriVertIDs = Mesh->GetTriangle( TriID );
 
SetTriVertPositions( TriVertIDs, CurrentTri );
 
// 종료 조건 1: 목표 정점 도달
if ( EndVertID >= 0 && TriVertIDs.Contains( EndVertID ) )
{
    // 목표 정점을 포함하는 삼각형에 도착!
    CurrentEnd = ComputedPointsAndSources.Emplace
    (
        FMeshSurfacePoint( EndVertID ),
        FWalkIndices( EndPt, CurrentEnd, TriID )
    );
    BestKnownEnd = CurrentEnd;
    break;  // 탐색 종료
}
 
// 종료 조건 2: 목표 삼각형 도달
bool OnEndTri = EndTri == TriID;
if ( !OnEndTri && EndVertID < 0 && EndTri == -1 )
{
    // 목표 삼각형이 명시되지 않았으면 거리로 판단
    CurrentTriDist.Triangle = CurrentTri;
    CurrentTriDist.Point    = EndPt;
    
    double DistSq = CurrentTriDist.GetSquared();
 
    if ( DistSq < AcceptEndPtOutsideDist )
    {
        OnEndTri = true;  // 충분히 가까우면 성공
    }
}
 
if ( OnEndTri )
{
    // 목표 삼각형에 도착!
    CurrentEnd = ComputedPointsAndSources.Emplace
    (
        FMeshSurfacePoint( TriID, CurrentTriDist.TriangleBaryCoords ),
        FWalkIndices( EndPt, CurrentEnd, TriID )
    );
    BestKnownEnd = CurrentEnd;
    break;  // 탐색 종료
}

중복 방문 방지

// 이미 방문한 삼각형은 건너뜀
if ( ExploredTriangles.Contains( TriID ) )
{
    continue;
}
ExploredTriangles.Add( TriID );

삼각형의 평면 교차 검사 및 처리

---

정점별 부호 거리 계산

double SignDist[ 3 ];  // 평면으로부터의 부호 거리
int Side[ 3 ];         // -1: 평면 아래, 0: 평면 위, 1: 평면 위
 
for ( int TriSubIdx = 0; TriSubIdx < 3; TriSubIdx++ )
{
    // 평면까지의 부호 거리 = (정점 - 시작점) · 평면법선
    double SD = ( CurrentTri.V[ TriSubIdx ] - StartPt ).Dot( WalkPlaneNormal );
    SignDist[ TriSubIdx ] = SD;
 
    if ( FMathd::Abs( SD ) <= PtOnPlaneThresholdSq )
    {
        // ✅ 정점이 평면 표면상에 있음 (Vertex Crossing)
        Side[ TriSubIdx ] = 0;
        // ... 정점 교차 처리 (다음 섹션)
    }
    else
    {
        // 평면 위쪽(+) 또는 아래쪽(-)
        Side[ TriSubIdx ] = SD > 0 ? 1 : -1;
    }
}

단일 정점 거리 계산을 통해 정점별 처리를 한다.

평면의 표면상에 위치한 정점의 교차 처리

if ( FMathd::Abs( SD ) <= PtOnPlaneThresholdSq )
{
    Side[ TriSubIdx ] = 0;
 
    int CandidateVertID = TriVertIDs[ TriSubIdx ];
 
    // 이미 통과한 정점이 아니고, 전진 방향이면
    if ( !CrossedVertices.Contains( CandidateVertID ) &&
        ( bAllowBackwardsSearch || ForwardsDirection.Dot( CurrentTri.V[ TriSubIdx ] - StartPt ) >= -BackwardsTolerance ) )
    {
        CrossedVertices.Add( CandidateVertID );
 
        // 이 정점 주변의 모든 삼각형 탐색
        for ( int32 NbrTriID : Mesh->VtxTrianglesItr( CandidateVertID ) )
        {
            if ( NbrTriID != TriID )
            {
                // 이웃 삼각형이 평면과 교차하는지 확인
                FIndex3i NbrTriVertIDs = Mesh->GetTriangle( NbrTriID );
                FTriangle3d NbrTri;
                SetTriVertPositions( NbrTriVertIDs, NbrTri );
 
                int SignsMultiplied = 1;
                for ( int NbrTriSubIdx = 0; NbrTriSubIdx < 3; NbrTriSubIdx++ )
                {
                    if ( NbrTriVertIDs[ NbrTriSubIdx ] == CandidateVertID )
                        continue;
 
                    double NbrSD = ( NbrTri.V[ NbrTriSubIdx ] - StartPt ).Dot( WalkPlaneNormal );
                    int NbrSign = FMathd::Abs( NbrSD ) <= PtOnPlaneThresholdSq ? 0 : NbrSD > 0 ? 1 : -1;
                    SignsMultiplied *= NbrSign;
                }
 
                // 다른 정점들이 평면 양쪽에 있으면 교차함
                if ( SignsMultiplied < 1 )
                {
                    // 이 삼각형도 후보에 추가
                    ComputedPointsAndSources.Emplace
                    (
                        FMeshSurfacePoint( CandidateVertID ),
                        FWalkIndices( CurrentTri.V[ TriSubIdx ], CurrentEnd, NbrTriID )
                    );
                }
            }
        }
    }
}

정점이 평면 위에 있으면 해당 정점을 공유하는 모든 인접 삼각형을 탐색한다. 인접 삼각형들은 평면과 교차하면 ComputedPointsAndSources에 추가된다.

엣지 교차 처리

FIndex3i TriEdgeIDs = Mesh->GetTriEdges( TriID );
 
for ( int TriSubIdx = 0; TriSubIdx < 3; TriSubIdx++ )
{
    int NextSubIdx = ( TriSubIdx + 1 ) % 3;
 
    // ✅ 두 정점이 평면 반대편에 있으면 엣지 교차!
    if ( Side[ TriSubIdx ] * Side[ NextSubIdx ] < 0 )  // 부호가 다름
    {
        int CandidateEdgeID = TriEdgeIDs[ TriSubIdx ];
 
        // 교차점의 위치 계산 (선형 보간)
        double CrossingT = SignDist[ TriSubIdx ] / ( SignDist[ TriSubIdx ] - SignDist[ NextSubIdx ] );
 
        FVector3d CrossingP = ( 1 - CrossingT ) * CurrentTri.V[ TriSubIdx ] + CrossingT * CurrentTri.V[ NextSubIdx ];
 
        // 엣지 정보 가져오기
        const FDynamicMesh3::FEdge Edge = Mesh->GetEdge( CandidateEdgeID );
 
        // 엣지 방향 확인 (삼각형 로컬 순서와 전역 순서가 다를 수 있음)
        if ( Edge.Vert[ 0 ] != TriVertIDs[ TriSubIdx ] )
        {
            CrossingT = 1 - CrossingT;  // 방향 반전
        }
 
        // 반대편 삼각형 찾기
        int CrossToTriID = Edge.Tri[ 0 ];
        if ( CrossToTriID == TriID )
        {
            CrossToTriID = Edge.Tri[ 1 ];
        }
 
        if ( CrossToTriID == -1 )
        {
            // 메시 경계에 도달 - 건너뜀
            continue;
        }
 
        // 전진 방향 확인
        bool bIsForward = ForwardsDirection.Dot( CrossingP - StartPt ) >= -BackwardsTolerance;
        if ( !bAllowBackwardsSearch && !bIsForward )
        {
            continue;  // 후진 방향이고 후진 금지면 건너뜀
        }
 
        // 엣지 교차점을 경로에 추가
        ComputedPointsAndSources.Emplace
        (
            FMeshSurfacePoint( CandidateEdgeID, CrossingT ),
            FWalkIndices( CrossingP, CurrentEnd, CrossToTriID )
        );
    }
}

엣지를 이루는 두 정점이 평면과 교차할 때 교차점을 찾아 ComputedPointAndSources에 추가한다. 교차점은 다음과 같이 계산된다.

두 정점 A, B가 있고 부호 거리가 각각 distA, distB일 때
교차점 P = A + t * (B - A), 여기서 t = distA / (distA - distB)

그냥 총 거리 대비 각각의 거리 비율에 대해 보간한 것이다 .

새 교차점 후보들의 FIndexDistance추가

---

// 새로 발견한 점들을 우선순위 큐에 추가
const FVector3d& PreviousPathPoint = ComputedPointsAndSources[ CurrentEnd ].Value.Position;
 
for ( int32 NewComputedPtIdx = InitialComputedPointsNum; NewComputedPtIdx < ComputedPointsAndSources.Num(); NewComputedPtIdx++ )
{
    const FVector3d& CurrentPathPoint = ComputedPointsAndSources[ NewComputedPtIdx ].Value.Position;
 
    // 경로 길이 = 이전 경로 + 이번 구간
    double PathLength = CurrentPathLength + Distance( PreviousPathPoint, CurrentPathPoint );
 
    // 목표까지 남은 거리
    double DistanceToEnd = Distance( EndPt, CurrentPathPoint );
 
    // 우선순위 큐에 추가 (PathLength + DistanceToEnd로 정렬됨)
    UnexploredEnds.HeapPush( { NewComputedPtIdx, PathLength, DistanceToEnd } );
}

새롭게 추가된 후보 교차점들( ComputedPointsAndSources )의 경로 길이들을 계산하여 UnexploredEnds에 추가한다.

경로( WalkedPath ) 생성

---

// 목표에서 시작점까지 역으로 추적
int TrackedPtIdx = BestKnownEnd;
TArray< int > AcceptedIndices;
 
while ( TrackedPtIdx > -1 )
{
    AcceptedIndices.Add( TrackedPtIdx );
    TrackedPtIdx = ComputedPointsAndSources[ TrackedPtIdx ].Value.WalkedFromPt;
}
 
// 역순이므로 뒤집어서 저장
WalkedPath.Reset();
for ( int32 IdxIdx = AcceptedIndices.Num() - 1; IdxIdx >= 0; IdxIdx-- )
{
    WalkedPath.Emplace
    (
        ComputedPointsAndSources[ AcceptedIndices[ IdxIdx ] ].Key,                // 표면 점
        ComputedPointsAndSources[ AcceptedIndices[ IdxIdx ] ].Value.WalkingOnTri  // 삼각형
    );
}

ComputedPointsAndSources

          시작점(0)
          /      \
      엣지A(1)  정점B(2)
       /   \         \
  정점C(3) 엣지D(4)  엣지E(5)
      |
    목표점(6) ✅

WalkedFromPt

  목표점(6) ← 정점C(3) ← 엣지A(1) ← 시작점(0)
     ↑                                    ↑
    끝점                               시작점

WalkedPath

  시작점(0) → 엣지A(1) → 정점C(3) → 목표점(6)
     ↑                                    ↑
   시작점                               끝점

후처리 (경로 정제)

---

시작점 정제

// 시작점이 삼각형 내부에 있으면 정점/엣지로 스냅
if ( WalkedPath.Num() && WalkedPath[ 0 ].Key.PointType == ESurfacePointType::Triangle )
{
    FMeshSurfacePoint& SurfacePt = WalkedPath[ 0 ].Key;
 
    // 정확한 시작 정점이 지정되었으면 그것 사용
    if ( StartVIDIndex > -1 && SurfacePt.BaryCoord[ StartVIDIndex ] == 1.0 )
    {
        FIndex3i TriVertIDs = Mesh->GetTriangle( SurfacePt.ElementID );
        SurfacePt.ElementID = TriVertIDs[ StartVIDIndex ];
        SurfacePt.PointType = ESurfacePointType::Vertex;
    }
    else
    {
        // 가까운 정점/엣지로 스냅
        RefineSurfacePtFromTriangleToSubElement( Mesh, SurfacePt.Pos( Mesh ), SurfacePt, PtOnPlaneThresholdSq );
    }
 
    // 다음 점과 중복이면 제거
    if ( WalkedPath.Num() > 1 &&
         SurfacePt.PointType == WalkedPath[ 1 ].Key.PointType &&
         SurfacePt.ElementID == WalkedPath[ 1 ].Key.ElementID  )
    {
        if ( SurfacePt.PointType == ESurfacePointType::Edge )
        {
            WalkedPath[ 1 ].Key.BaryCoord = SurfacePt.BaryCoord;  // 더 정확한 좌표 복사
        }
        WalkedPath.RemoveAt( 0 );  // 중복 제거
    }
}

삼각형 내부에 있는 점을 가장 가까운 정점이나 엣지로 정제한다.

끝점 정제

// 끝점도 동일한 방식으로 처리
if ( WalkedPath.Num() && WalkedPath.Last().Key.PointType == ESurfacePointType::Triangle )
{
    FMeshSurfacePoint& SurfacePt = WalkedPath.Last().Key;
    RefineSurfacePtFromTriangleToSubElement( Mesh, SurfacePt.Pos( Mesh ), SurfacePt, PtOnPlaneThresholdSq );
 
    // 중복 제거 로직...
}
 
return true;  // 성공!