Mesh Slicing

VR 수술 시뮬레이션을 위한 실시간 메쉬 절단 알고리즘

2025.12 | 개발 기간 3주

GitHub

기술 스택

UnityC#Meta QuestDFSComputational Geometry

프로젝트 개요

이 프로젝트는 VR 수술 시뮬레이션에서 조직을 정밀하게 절개할 수 있는 메쉬 절단 알고리즘을 개발하는 것이 목표였습니다. 기존의 Unity Asset Store에 있는 솔루션들은 과일을 자르거나 오브젝트를 파괴하는 용도로 설계되어 있어, 수술처럼 정밀한 부분 절개가 불가능했습니다.

수술 시뮬레이션에서는 조직을 완전히 분리하는 것이 아니라, 메쉬의 연결 상태를 유지하면서 특정 부분만 절개할 수 있어야 합니다. 이를 위해 기존 솔루션을 사용할 수 없었고, 직접 알고리즘을 설계하고 구현해야 했습니다.


해결해야 할 문제

기존 솔루션의 한계

Unity Asset Store에는 Easy Slice, Mesh Cutter 등 여러 메쉬 절단 Asset이 존재합니다. 하지만 이들은 모두 "완전 절단(Complete Cut)"만 지원합니다. 즉, 메쉬를 자르면 두 개의 독립된 오브젝트로 완전히 분리됩니다.

  • Easy Slice: 평면 기반 절단, 오브젝트가 두 조각으로 완전 분리
  • Mesh Cutter: 다양한 절단 형태 지원, 하지만 역시 완전 분리만 가능
  • 부분 절개 불가능: 메쉬 연결 상태를 유지하면서 절개하는 기능 없음

수술 시뮬레이션의 요구사항

실제 수술에서는 조직을 완전히 분리하지 않고, 메스로 절개선을 만들어 특정 부분만 열어야 하는 경우가 많습니다. 이를 시뮬레이션하기 위해서는:

  • 조직을 부분적으로 절개할 수 있어야 함
  • 절개된 부분과 절개되지 않은 부분이 여전히 연결되어 있어야 함
  • 절개선의 형태(직선, 곡선 등)에 따라 정밀하게 절개되어야 함
  • 실시간으로 처리되어야 함 (VR 환경에서 90 FPS 이상 유지)

결론

기존 Asset들은 게임이나 파괴 효과에는 적합하지만, 수술처럼 정밀한 절개가 필요한 시뮬레이션에는 사용할 수 없었습니다. 따라서 새로운 알고리즘을 직접 개발해야 했습니다.


개발 과정 - 4번의 시도

완벽한 솔루션을 찾기까지 4번의 시도와 실패를 거쳤습니다. 각 시도마다 문제점을 파악하고 개선하는 과정을 통해 최종 솔루션에 도달했습니다.

1

Ray-based Approach (World Space)

실패 - 15 FPS

접근 방법:

  • VR 컨트롤러의 위치에서 Ray를 쏴서 메쉬의 Triangle과 교차점을 찾음
  • Unity의 Physics.Raycast로 Triangle Index 수집
  • World Space에서 직접 계산 시도

문제점:

  • 좌표계 변환 오류: World Space와 Local Space를 혼동하여 Ray의 위치와 방향이 정확하지 않았습니다
  • 심각한 성능 저하: 모든 Triangle에 대해 World Space에서 계산하니 15 FPS로 떨어짐 (목표: 90 FPS)
  • 부정확한 결과: 좌표 변환 문제로 인해 엉뚱한 위치가 절단됨

배운 점:

Unity에서 메쉬 데이터는 Local Space에 저장되어 있으므로, World Space의 Ray를 Local Space로 변환해야 정확한 계산이 가능하다는 것을 알게 되었습니다.

2

Edge-based Approach

부분 성공 - 25 FPS

접근 방법:

  • Triangle 대신 메쉬의 Edge(모서리)와 Ray의 교차점을 검사
  • Local Space에서 계산하도록 개선
  • 교차된 Edge를 기준으로 메쉬 분리 시도

문제점:

  • Edge 검출의 한계: 모든 케이스를 처리할 수 없었습니다 (예: Edge가 아닌 Triangle 내부를 지나가는 경우)
  • 복잡한 예외 처리: 다양한 절단 케이스를 처리하기 위해 조건문이 너무 많아짐
  • 여전히 낮은 성능: 25 FPS로 개선되었지만 목표인 90 FPS에는 크게 못 미침

배운 점:

좌표계 변환은 올바르게 했지만, Edge 기반 접근은 근본적으로 한계가 있었습니다. 메쉬의 기본 단위는 Triangle이므로, Triangle 기반으로 접근해야 한다는 것을 깨달았습니다.

3

Triangle-based Approach (Unity Raycast)

발전 - 55 FPS

접근 방법:

  • Unity의 Physics.Raycast로 Triangle Index를 직접 수집
  • Local Space에서 Ray 계산하여 정확도 향상
  • RaycastHit.triangleIndex로 교차된 Triangle 마킹

개선점:

  • Unity 내장 함수 활용: Physics.Raycast의 최적화된 충돌 검사 활용
  • 성능 향상: 55 FPS 달성 (목표의 61% 수준)
  • 안정적인 동작: 메쉬 변형 없이 정확한 위치에서 절단

발견한 문제:

Ray 방향과 메쉬 법선 벡터가 거의 평행할 때 일부 Triangle을 놓치거나 중복 감지하는 문제가 발생했습니다. 또한 교차된 Triangle들이 서로 연결되어 있는지(같은 절개선에 속하는지) 판단할 수 없었습니다. 100개의 Triangle이 교차되었다면, 이것이 하나의 긴 절개선인지, 여러 개의 작은 절개선인지 알 수 없었습니다.

배운 점:

Triangle 검출은 성공했지만, Ray 기반 방식의 근본적 한계와 "그룹화(Grouping)" 문제가 남아있었습니다. 인접한 Triangle들을 하나의 그룹으로 묶는 알고리즘이 필요했습니다.

4

DFS Flood-fill Algorithm

성공 - 90+ FPS

핵심 아이디어:

교차된 Triangle들을 DFS(Depth-First Search)로 탐색하여 서로 인접한 Triangle들을 하나의 연결된 그룹으로 묶는다. 또한 Front Ray와 Back Ray 두 개를 사용하여 양방향에서 검사함으로써 Ray 방향과 법선이 평행할 때의 감지 누락 문제를 해결한다.

알고리즘 단계:

  1. Front Ray와 Back Ray로 교차하는 모든 Triangle을 찾아서 마킹
  2. 마킹된 Triangle 중 아직 방문하지 않은 Triangle에서 DFS 시작
  3. 현재 Triangle과 Edge를 공유하는 인접 Triangle 중 마킹된 Triangle을 찾음
  4. 인접 Triangle을 재귀적으로 방문하면서 같은 그룹으로 묶음
  5. 더 이상 인접한 마킹 Triangle이 없으면 하나의 그룹 완성
  6. 방문하지 않은 마킹 Triangle이 있으면 2번으로 돌아가 새로운 그룹 생성

결과:

  • 완벽한 그룹화: 연결된 절개선들을 정확하게 하나의 그룹으로 묶음
  • 목표 성능 달성: 90+ FPS 달성 (VR 환경에서 안정적)
  • 부분 절개 지원: 메쉬 연결 상태를 유지하면서 절개 가능
  • 100% 정확도: 모든 테스트 케이스에서 정확한 결과

왜 DFS를 선택했나:

BFS(Breadth-First Search)도 가능했지만, DFS가 스택 기반이라 메모리 효율이 좋고 재귀로 구현하기 쉬웠습니다. 또한 절개선은 보통 길고 연속적이므로 깊이 우선 탐색이 더 자연스러웠습니다.


최종 솔루션

4번의 시도를 통해 얻은 교훈을 모두 결합하여 완성된 알고리즘입니다.

핵심 기술 4가지

1. Unity Physics.Raycast + Dual Ray System

Unity의 Physics.Raycast를 활용하여 Ray와 메쉬의 교차점을 빠르게 찾습니다. RaycastHit.triangleIndex를 통해 정확히 어떤 Triangle이 Ray와 교차했는지 알 수 있습니다. Front Ray와 Back Ray 두 개를 동시에 사용하여 양방향에서 검사함으로써 Ray 방향과 법선이 평행할 때의 감지 누락 문제를 해결했습니다. Local Space로 변환된 Ray를 사용하여 오브젝트의 회전, 크기, 위치에 관계없이 정확한 교차 검사가 가능합니다.

2. DFS Flood-fill 그룹화

교차된 Triangle들을 DFS로 탐색하여 연결된 그룹으로 묶습니다. 각 Triangle은 최대 3개의 인접 Triangle을 가지므로, 재귀 깊이가 제한적이어서 스택 오버플로우 위험이 적습니다. 방문한 Triangle은 HashSet에 저장하여 중복 방문을 방지하고, O(n) 시간 복잡도로 모든 Triangle을 그룹화할 수 있습니다.

3. Local Space 좌표 변환

Unity의 메쉬 데이터는 Local Space에 저장되므로, World Space의 Ray를 Local Space로 변환해야 정확한 계산이 가능합니다. Transform.InverseTransformPoint()와 InverseTransformDirection()을 사용하여 Ray의 원점과 방향을 변환합니다. 이를 통해 오브젝트의 회전, 크기, 위치에 관계없이 정확한 절단이 가능합니다.

4. Cap Mesh 생성 (Arc-Length 기반)

절단면에 뚜껑(Cap)을 씌워서 메쉬의 내부가 보이지 않도록 합니다. 절개선의 경계 정점들을 Arc-Length(호의 길이) 순서로 정렬한 후, Triangulation 알고리즘으로 삼각형을 생성합니다. 이 과정에서 Constrained Delaunay Triangulation을 사용하여 자연스럽고 균일한 삼각형 분포를 만들어냅니다.

핵심 알고리즘 코드

Dual Ray System

csharp
private void CastFrontRay()
{
    Ray frontRay = new Ray(_katanaRay.position, _katanaRay.forward);
    RaycastHit frontHit;

    if (Physics.Raycast(frontRay, out frontHit, _katanaRayLength, _sliceTargetLayer))
    {
        HasFrontHit = true;
        ProcessHit(frontHit, FrontHitDic, FrontHitPoints);
    }
}

private void CastBackRay()
{
    Vector3 backRayStartPoint = _katanaRay.position + _katanaRay.forward * _katanaRayLength;
    Vector3 backDirection = -_katanaRay.forward;
    Ray backRay = new Ray(backRayStartPoint, backDirection);
    RaycastHit backHit;

    if (Physics.Raycast(backRay, out backHit, _katanaRayLength, _sliceTargetLayer))
    {
        HasBackHit = true;
        ProcessHit(backHit, BackHitDic, BackHitPoints);
    }
}

private void ProcessHit(RaycastHit hit, Dictionary<int, Vector3> hitDataDict, 
                       List<Vector3> hitPointsList)
{
    GameObject hitObject = hit.collider.gameObject;
    int triIndex = hit.triangleIndex; // Triangle 인덱스 추출

    if (!HitTriangles.Contains(triIndex)) 
        HitTriangles.Add(triIndex);

    if (!hitDataDict.ContainsKey(triIndex))
    {
        hitDataDict[triIndex] = hit.point;
        hitPointsList.Add(hit.point);
    }
}

DFS Flood-fill 그룹화

csharp
// 교차된 Triangle들을 DFS로 그룹화
void GroupTriangles(int startTriangle, HashSet<int> visited, List<int> group)
{
    // 현재 Triangle 방문 처리
    visited.Add(startTriangle);
    group.Add(startTriangle);
    
    // 인접한 Triangle들 탐색
    foreach (int neighbor in GetNeighbors(startTriangle))
    {
        // 마킹되었고 아직 방문하지 않은 Triangle만 재귀 탐색
        if (IsMarked(neighbor) && !visited.Contains(neighbor))
        {
            GroupTriangles(neighbor, visited, group);
        }
    }
}

// 모든 그룹 생성
List<List<int>> CreateAllGroups()
{
    HashSet<int> visited = new HashSet<int>();
    List<List<int>> allGroups = new List<List<int>>();
    
    foreach (int triangle in markedTriangles)
    {
        if (!visited.Contains(triangle))
        {
            List<int> group = new List<int>();
            GroupTriangles(triangle, visited, group);
            allGroups.Add(group);
        }
    }
    
    return allGroups;
}

좌표 변환

csharp
// World Space Ray를 Local Space로 변환
public Ray WorldToLocalRay(Ray worldRay, Transform meshTransform)
{
    // Ray 원점을 Local Space로 변환
    Vector3 localOrigin = meshTransform.InverseTransformPoint(worldRay.origin);
    
    // Ray 방향을 Local Space로 변환 (크기 무시)
    Vector3 localDirection = meshTransform.InverseTransformDirection(worldRay.direction);
    
    return new Ray(localOrigin, localDirection.normalized);
}

전체 알고리즘 흐름

  1. 좌표 변환: World Space의 Ray를 메쉬의 Local Space로 변환
  2. Dual Ray 교차 검사: Front Ray와 Back Ray로 Triangle 교차 검사 수행, 교차된 Triangle 마킹
  3. 그룹화: 마킹된 Triangle들을 DFS로 탐색하여 연결된 그룹으로 분류
  4. 경계 추출: 각 그룹의 경계 Edge 추출 (한쪽 Triangle만 마킹된 Edge)
  5. Cap Mesh 생성: 경계 정점을 정렬하고 Triangulation하여 절단면 뚜껑 생성
  6. 메쉬 분리: 각 그룹을 별도의 메쉬로 분리하되, 필요시 원본 메쉬와 연결 상태 유지
  7. 물리 적용: 분리된 메쉬에 Rigidbody와 Collider 추가하여 물리 시뮬레이션 가능하게 함

핵심 성공 요인

Unity Physics.Raycast를 활용한 Dual Ray System과 DFS Flood-fill의 결합이 핵심이었습니다. 양방향 Ray 검사로 감지 누락을 방지하고, 효율적인 그룹화를 통해 실시간 성능(90+ FPS)과 정확도(100%)를 모두 달성할 수 있었습니다.

특히 Local Space에서의 계산과 Arc-Length 기반 Cap Mesh 생성이 시각적 품질과 안정성을 크게 향상시켰습니다.


기술 상세 설명

Unity Physics.Raycast + Dual Ray System

Unity의 내장 Physics 시스템을 활용하여 Ray와 메쉬의 교차를 검사합니다. RaycastHit 구조체는 충돌한 정확한 Triangle의 인덱스를 제공하므로, 이를 활용하여 절단할 Triangle들을 수집할 수 있습니다.

핵심 구현:

  • Front Ray와 Back Ray 두 개를 동시에 쏴서 감지 누락 방지
  • triangleIndex로 정확한 Triangle 식별
  • Dictionary로 중복 Triangle 제거
  • Local Space 변환으로 정확도 향상

Ray 기반 방식의 한계와 해결: Ray 방향과 메쉬 법선이 거의 평행할 때 일부 Triangle을 놓치는 문제가 있었습니다. 이를 해결하기 위해 Front Ray와 Back Ray를 동시에 사용하여 양방향에서 검사하는 방식으로 안정성을 크게 향상시켰습니다.

DFS vs BFS 선택 이유

Triangle 그룹화를 위해 DFS와 BFS 중 DFS를 선택한 이유:

  • 메모리 효율: DFS는 스택 기반으로 현재 경로만 메모리에 유지. BFS는 큐에 모든 레벨의 노드를 저장
  • 구현 간결성: 재귀로 구현하면 코드가 매우 간결하고 이해하기 쉬움
  • 절개선 특성: 절개선은 보통 길고 연속적이므로 깊이 우선 탐색이 자연스러움
  • 캐시 효율: 인접한 Triangle을 연속적으로 방문하므로 CPU 캐시 히트율이 높음

좌표계 변환의 중요성

Unity에서 메쉬의 정점 데이터는 Local Space에 저장됩니다. 예를 들어 1m 크기의 Cube는 정점이 (-0.5, -0.5, -0.5)부터 (0.5, 0.5, 0.5)까지 분포합니다. 하지만 VR 컨트롤러의 위치는 World Space로 제공됩니다.

따라서 World Space의 Ray를 Local Space로 변환하지 않으면:

  • 오브젝트가 회전되어 있으면 Ray 방향이 틀어짐
  • 오브젝트의 크기가 조절되어 있으면 교차점 위치가 부정확함
  • 오브젝트가 이동되어 있으면 Ray가 완전히 빗나감

Transform.InverseTransformPoint()와 InverseTransformDirection()을 사용하면 이러한 모든 변환(이동, 회전, 크기)을 한 번에 역변환하여 Local Space에서 정확한 계산이 가능합니다.

Cap Mesh 생성 - Arc-Length 정렬

절단면에 뚜껑을 씌우려면 경계 정점들을 올바른 순서로 정렬해야 합니다. 단순히 정점의 좌표로 정렬하면 엉뚱한 순서가 나올 수 있습니다.

Arc-Length 정렬 방법:

  1. 절개선의 시작점을 임의로 선택
  2. 현재 정점에서 가장 가까운 이웃 정점을 찾음
  3. 해당 정점으로 이동하고, 이동 거리를 누적 (Arc-Length)
  4. 모든 정점을 방문할 때까지 반복
  5. Arc-Length 순서대로 정렬된 정점 리스트 완성

이렇게 정렬된 정점들을 Ear Clipping이나 Delaunay Triangulation으로 삼각형화하면 자연스러운 Cap Mesh가 생성됩니다.


프로젝트 성과

90+

FPS

VR 환경에서 안정적인 프레임레이트 달성

100%

정확도

모든 테스트 케이스에서 정확한 절단

3주

개발 기간

4번의 시도를 통한 최적화

성능 비교

시도방법FPS정확도
Attempt #1Ray (World Space)1540%
Attempt #2Edge-based2560%
Attempt #3Triangle (Unity)5585%
FinalDual Ray + DFS90+100%

핵심 배움

  • Computational Geometry의 실전 적용: 이론적으로만 알던 알고리즘들을 실제 VR 환경에서 구현하고 최적화하는 경험을 얻었습니다.
  • 좌표계 변환의 중요성: Unity의 Transform 시스템을 깊이 이해하게 되었고, World Space와 Local Space의 차이가 얼마나 중요한지 배웠습니다.
  • 알고리즘 선택이 성능에 미치는 영향: 같은 문제를 푸는 여러 방법 중 어떤 것을 선택하느냐에 따라 성능이 6배 이상 차이날 수 있다는 것을 경험했습니다.
  • 실패를 통한 학습: 4번의 실패가 있었기에 최종 솔루션이 완성될 수 있었습니다. 각 실패에서 얻은 교훈이 다음 시도의 밑거름이 되었습니다.

향후 계획

  • Soft Body Physics 통합: 현재는 Rigidbody를 사용하지만, 실제 조직의 탄성과 변형을 시뮬레이션하기 위해 Position Based Dynamics를 통합할 예정입니다.
  • 실시간 조직 변형: 절개뿐만 아니라 조직을 당기거나 늘릴 때 실시간으로 변형되는 시뮬레이션을 구현할 계획입니다.
  • 햅틱 피드백: VR 컨트롤러에 햅틱 피드백을 추가하여 조직의 저항감과 절개 순간의 촉감을 전달할 예정입니다.
  • 다양한 절개 도구: 메스뿐만 아니라 가위, 전기 소작기 등 다양한 수술 도구를 지원하도록 확장할 계획입니다.

© 2026 Trout. Built with Next.js & TypeScript.