평면 보행 알고리즘

개요

---

3D 메시를 평면으로 자를 때, 그 자른 선을 따라가는 알고리즘이다. 평면과 메시가 교차하는 경로를 삼각형 단위로 탐색하여 시작점부터 끝점까지의 최단 경로를 찾는다.

항목	설명
입력	시작점, 끝점, 자를 평면
출력	메시 표면을 따라 평면과 교차하는 경로
핵심	평면이 지나가는 곳을 따라 삼각형을 하나씩 건너다님
방법	A* 알고리즘 기반 우선순위 탐색

동작 순서

---

1. 시작 삼각형에서 출발
2. 평면이 삼각형의 어느 모서리/정점을 지나가는지 찾기
3. 그 지점으로 이동하고, 옆 삼각형으로 넘어가기
4. 끝점에 도달할 때까지 2~3 반복

의사 코드

---

초기화

Initialize( StartPoint, EndPoint, Plane ):
    ComputedPoints    = []    // 발견한 경로점들
    UnexploredQueue   = []    // 우선순위 큐 (Heap)
    ExploredTriangles = Set() // 방문한 삼각형
    CrossedVertices   = Set() // 지나간 정점
 
    // 시작점 추가
    startIndex = AddPoint( StartPoint, StartTriangle )
    UnexploredQueue.Push( startIndex, distance=0 )

프로퍼티	설명
ComputedPoints	지금까지 지나온 모든 지점 기록
UnexploredQueue	다음에 탐색할 후보들 (A* 우선순위)
ExploredTriangles	이미 확인한 삼각형 (중복 방지)
CrossedVertices	이미 지나간 정점 (중복 방지)

경로 탐색

FindPath():
    while UnexploredQueue is not empty:
        // 가장 유망한 후보 선택
        currentIndex = UnexploredQueue.PopMin()
        currentPoint = ComputedPoints[ currentIndex ]
        currentTriangle = currentPoint.Triangle
 
        // 목적지 도달 확인
        if currentTriangle contains EndPoint:
            return BuildPath( currentIndex )
 
        // 이미 방문한 삼각형은 skip
        if currentTriangle in ExploredTriangles:
            continue
        ExploredTriangles.Add( currentTriangle )
 
        // 평면이 현재 삼각형과 교차하는 지점 찾기
        crossingPoints = FindPlaneCrossings( currentTriangle, Plane )
 
        // 각 교차점에 대해
        for each point in crossingPoints:
            newPathLength = currentPathLength + Distance( currentPoint, point )
            priority = CalculatePriority( point, newPathLength, EndPoint )
 
            newIndex = AddPoint( point, nextTriangle )
            UnexploredQueue.Push( newIndex, priority )

평면 교차 찾기

FindPlaneCrossings( Triangle, Plane ):
    crossings = []
    vertices = Triangle.GetVertices()
 
    // 각 정점의 평면까지 거리 계산
    for i = 0 to 2:
        distance[ i ] = SignedDistance( vertices[ i ], Plane )
        sign[ i ] = Sign( distance[ i ] )
 
    // 1. 정점 교차 확인
    for i = 0 to 2:
        if Abs( distance[ i ] ) < Epsilon:
            // 정점이 평면 위에 있음
            crossings.Add( VertexPoint( vertices[ i ] ) )
 
            // 인접 삼각형들로 이동 가능
            for each neighborTri in GetNeighborTriangles( vertices[ i ] ):
                if PlaneCrossesTriangle( neighborTri, Plane ):
                    crossings.Add( point, neighborTri )
 
    // 2. 엣지 교차 확인
    for i = 0 to 2:
        j = (i + 1) % 3
 
        // 두 정점이 평면의 반대편에 있는가?
        if sign[ i ] * sign[ j ] < 0:
            // 교차점 위치 계산 (선형 보간)
            t = distance[ i ] / ( distance[ i ] - distance[ j ] )
            crossingPoint = (1 - t) * vertices[ i ] + t * vertices[ j ]
 
            crossings.Add( EdgePoint( crossingPoint, t ), oppositeTriangle )
 
    return crossings

경로 복원

BuildPath( endIndex ):
    path = []
    currentIndex = endIndex
 
    // 끝점에서 시작점까지 거꾸로 따라감
    while currentIndex >= 0:
        point = ComputedPoints[ currentIndex ]
        path.Add( point )
        currentIndex = point.PreviousIndex
 
    // 순서 뒤집기 (시작 → 끝)
    path.Reverse()
 
    // 경로 정제 (필요시)
    RefinePath( path )
 
    return path

복잡도

---

항목	복잡도
시간	O(T log T)
공간	O(T)
T	메시 삼각형 수

실제 성능

• 대부분의 경우 전체 메시의 작은 부분만 탐색
• A* 휴리스틱으로 불필요한 탐색 배제
• 최악의 경우: 복잡한 메시에서 우회 경로 필요 시