Data Structure CG

Union-Find로 UV Chart 만들기

Triangle을 노드, UV가 이어진 공유 edge를 연결로 보면 UV Chart는 그래프의 연결 요소가 된다.

Mesh의 triangle마다 UV가 주어져 있어도, 그 triangle들이 어떤 UV Chart에 속하는지는 따로 찾아야 한다. 여기서는 3D에서 edge를 공유하는 두 triangle의 UV가 이어지는지 검사하고, 이어진 triangle들을 하나의 Chart로 묶는다.

이 묶기 작업에 잘 맞는 자료구조가 Union-Find, 또는 **Disjoint Set Union(DSU)**이다. 코드에서는 TDisjointSet과 Merge()라는 이름을 사용한다.

Triangle을 노드로 보면 Chart는 연결 요소다

각 triangle을 그래프의 노드로 생각하자. 두 triangle이 같은 3D edge를 공유하고, 그 edge의 양 끝 UV 좌표도 양쪽 triangle에서 일치하면 두 노드 사이에 연결을 둔다.

UV edge까지 이어짐:

T0 ─── T1 ─── T2       T3 ─── T4

UV Chart A             UV Chart B

이 그래프에서 서로 연결을 따라 도달할 수 있는 노드들의 묶음이 **connected component(연결 요소)**다. 위 예에서는 {T0, T1, T2}와 {T3, T4}가 각각 Chart다.

연결은 직접 한 번만 이어져도 충분한 것이 아니다. T0와 T2 사이에 직접 edge가 없어도 T0 ↔ T1, T1 ↔ T2가 이어졌다면 세 triangle은 같은 Chart다. 이 전이 관계를 효율적으로 관리하는 것이 Union-Find의 역할이다.

먼저 같은 3D edge를 찾아야 한다

Triangle의 각 변을 순회하면서 양 끝점의 원래 위치 인덱스로 edge key를 만든다.

Triangle A가 기록한 edge: (17, 32)
Triangle B가 기록한 edge: (32, 17)

두 표기가 같은 edge를 가리키도록 인덱스를 정렬해 (min, max) 형태로 정규화한다.

if (A > B)
    std::swap(A, B);

TEdgeKey Key{A, B};

원래 위치 인덱스를 쓰는 이유는 렌더링 vertex와 기하학적 정점이 항상 일대일이 아니기 때문이다. UV seam에서 같은 3D 위치가 서로 다른 UV를 가지면 GPU용 vertex가 복제될 수 있다. 렌더링 vertex index로만 비교하면 그런 두 정점이 서로 다른 위치라고 오인한다. 원래 위치 인덱스는 3D상 같은 정점인지를 확인하고, 별도로 저장된 corner UV는 텍스처상 같은 위치인지를 확인하는 데 쓴다.

각 key에 그 edge를 사용하는 triangle과 해당 triangle 안의 edge 방향을 기록하면, 대략 다음과 같은 표가 만들어진다.

Edge (0, 1) → T3, T7
Edge (1, 5) → T7, T8
Edge (2, 6) → T10

한 edge에 triangle이 두 개 붙어야 양쪽 UV를 비교할 수 있다. 하나만 붙은 edge는 mesh의 경계다. 셋 이상 붙었다면 일반적인 manifold surface의 edge가 아니므로 이 구현은 이를 non-manifold 입력으로 보고 오류 처리한다.

공유 edge의 UV를 방향에 맞춰 비교한다

공유 edge의 key가 같다고 해서 UV까지 이어진 것은 아니다. 두 triangle에서 같은 원래 정점에 해당하는 UV를 찾아 비교해야 한다.

같은 3D edge: A ───────── B

Triangle 0: A → uvA0, B → uvB0
Triangle 1: A → uvA1, B → uvB1

두 endpoint 모두 허용 오차 안에서 일치해야 UV edge가 이어졌다고 본다.

$$ \|uv_{A0}-uv_{A1}\|_\infty \leq \epsilon \quad\land\quad \|uv_{B0}-uv_{B1}\|_\infty \leq \epsilon $$

예를 들어 코드의 비교 허용 오차가 1.0e-6이면 그보다 작은 부동소수점 차이는 같은 UV로 취급한다. UV가 정점 단위가 아니라 triangle corner 단위로 저장되어 있다면, edge의 양 끝 UV를 가져올 때 triangle의 corner 순서와 원래 위치 인덱스를 함께 맞춰야 한다. edge key를 정렬한 순서가 두 triangle의 winding 순서와 같다고 가정하면 안 된다.

두 endpoint가 모두 일치하면 두 triangle을 합친다. 어느 한쪽이라도 다르면 그 공유 edge는 UV seam이다.

3D에서는 같은 edge

Triangle 0: A → (0.2, 0.4), B → (0.5, 0.4)
Triangle 1: A → (0.7, 0.4), B → (1.0, 0.4)

→ UV가 끊겼으므로 Seam

Union-Find로 집합을 합친다

처음에는 triangle마다 독립된 집합이 있다고 본다.

{T0}  {T1}  {T2}  {T3}  {T4}

UV가 이어진 공유 edge를 발견할 때마다 Merge를 호출한다.

Charts.Merge(T0, T1);
Charts.Merge(T1, T2);
Charts.Merge(T3, T4);

결과는 다음과 같다.

{T0, T1, T2}       {T3, T4}

Union-Find의 기본 연산은 두 가지다.

  • Find(x): 원소 x가 속한 집합의 대표자(root)를 찾는다.
  • Merge(a, b): a와 b가 속한 두 집합을 합친다.

구현은 보통 경로 압축(path compression)과 union by rank/size를 써서 연산을 매우 빠르게 만든다. 원소가 $N$개일 때 여러 연산의 상각 시간은 실용적으로 거의 상수에 가깝고, 이 작업에서는 각 공유 edge를 한 번 검사하며 연결된 triangle 집합을 합칠 수 있다.

전체 흐름 

모든 triangle의 edge 수집
       ↓
원래 위치 인덱스로 edge key 정규화
       ↓
같은 3D edge를 공유하는 triangle 쌍 찾기
       ↓
공유 edge의 양 끝 UV 비교
       ↓
UV 연속 → Merge
UV 불연속 → Seam 기록
       ↓
각 triangle에 Find 결과를 부여

마지막 단계에서 Find(TriangleIndex)를 구하면 각 triangle의 집합 대표자를 얻는다. 그 대표자를 Chart 식별자로 쓸 수 있다. 다만 대표자 index 자체는 내부 구현에 따라 달라질 수 있으므로, 저장이나 표시용으로 연속된 번호가 필요하면 대표자들을 한 번 더 순회해 0, 1, 2, ...로 다시 매긴다.

대표자를 기준으로 triangle들을 모으면 Chart의 triangle 목록도 만들 수 있다.

for (TriangleIndex = 0; TriangleIndex < TriangleCount; ++TriangleIndex)
{
    Root = Charts.Find(TriangleIndex);
    TrianglesByChart[Root].push_back(TriangleIndex);
}

Chart와 Seam을 한 문장으로

UV Chart는 UV가 이어지는 공유 edge를 따라 연결된 triangle들의 집합이다. Seam은 3D에서는 공유하지만 UV endpoint가 일치하지 않아 두 집합을 합치지 않는 edge다.

이렇게 얻은 Chart와 Seam 정보는 다음 단계의 표면 격자 구성에 쓰인다. 「Mesh의 UV를 Simulation Grid로 매핑하기」에서는 triangle을 UV texel에 대응시키고, UV에서 떨어진 seam 양쪽 이웃을 다시 연결하는 방법을 살펴본다.

© 2025 - 2026 Yeonha Kim