Obj file의 manifold/non-manifold 구분

mesh 데이터를 이용한 무언가를 진행할 때, 보통 mesh가 manifold한지, 아닌지 구분하는 작업이 필요하고 non-manifold mesh라면 해당 vertex와 face를 제거하든지 해서 전처리를 한 뒤에 사용하게 된다. 

 

특히, 캐드에서나 3D graphic tool에서 non-manifold mesh를 그대로 사용한다면, 냅다 오류가 나거나 구멍이 뚫려있는 mesh를 볼 수 있다.

 

그래서 가장 대표적으로 mesh를 저장하는 데이터 포맷인 obj file에 대해서 mesh가 manifold한지 판단하는 방법 및 코드를 정리해보고자 한다.

 

Manifold

먼저, 지금까지 내가 공부하고 그리고 직관적으로 해석한 바로 manifold mesh가 뭔지 정리해보자면,

• mesh의 모든 edge를 2개 이상의 face가 포함하면 안된다. (이게 제일 중요. )
  
  
• 모든 face들이 이웃한 face와 normal vector 방향이 정렬되어 있어야 한다.
  - 예를 들어, sphere mesh의 모든 face는 일반적으로 바깥쪽으로 normal vector를 갖고 있는데, 일부 face가 내부로 향하는 normal vector를 갖고 있을 경우, non-manifold.

 

non-manifold 예시 그림을 몇가지 들자면 아래와 같다.

 

 

더 깊이 내려가면 틀린 설명일 수 있으나 (boundary가 어쩌구...closed/open fan이 어쩌구..), 연구할 때는 보통 일반적으로 1차적으로 다듬어진 mesh 데이터를 사용하게 되고, 문제가 있는지 없는지 검사하는 수준에서 manifold 체크를 하기 때문에 위와 같은 이해로 충분하다고 생각한다. (경험에 의하면...)

 

OBJ file

obj file에서 manifold 검사를 어떻게 하느냐? 복잡해보이지만 obj file 포맷 자체가 일정 규칙을 갖고 있기 때문에 아주 단순하게 확인할 수 있다.

 

규칙이라 함은,  obj file의 face는 "normal vector를 기준으로 counter-clockise 방향으로 ordering이 되어있다" 라는 것이다.

 

이 하나의 규칙으로 인해 구현 상 아주 간단해진다.

 

이해를 돕기 위해 예시를 들면, 6개의 face로 구성된 사각뿔 mesh가 있고 모든 face는 바깥을 향하도록 설정되어 있다고 하자.

각 face를 obj file 규칙에 맞추어 vertex id로 표현하면 다음과 같을 것이다.

face 0 : 0 1 2    ----    edge 01 12 20

face 1 : 0 2 3    ----    edge 02 23 30

face 2 : 0 3 4    ----    edge 03 34 40

face 3 : 0 4 1    ----    edge 04 41 10

face 4 : 4 2 1    ----    edge 42 21 14

face 5 : 4 3 2    ----    edge 43 32 24

 

이 때 각 face를 구성하는 vertex로 만들 수 있는 edge를 순서대로 같이 적어보면 깔끔한 결과를 얻을 수 있는데, 순서까지 같이 고려한다면 (01과 10을 다른 것으로 본다면) 중복된 edge가 단 하나도 없다. 

 

즉, obj file에 저장된 face 별로 directed edge를 만들었을 때, manifold mesh라면 중복되는 directed edge가 없어야 한다.

 

예를 들어, face 4가 조건 2 (normal 방향)에 어긋나 clock wise로 ordering되어 있다고 가정해보면,

 

face 4 : 1 2 4    ----   edge 12 24 41 같이  edge 12, 24, 41 모두 중복이다.  반대로 non-manifold인게 확인이 된다.

 

따라서 obj file에서는 단순히 face를 구성하는 vertex id 들로 directed edge를 전부 만들어보고 중복이 있는지 검사하면 manifold 여부를 판별할 수 있다.. easy~

 

간단히 코드로 구현해보면 다음과 같다.

 

def remove_non_manifolds(faces):    
    edges_set = set()
    mask = np.ones(len(faces), dtype=bool)
    # 1 2 
    for face_id, face in enumerate(faces):        
        faces_edges = []
        non_manifold = False
        for i in range(3):            
            cur_edge = (face[i], face[(i + 1) % 3])            
            if cur_edge in edges_set:
                non_manifold = True
                break
            else:
                faces_edges.append(cur_edge)
        if non_manifold:
            mask[face_id] = False
        else:
            for idx, edge in enumerate(faces_edges):
                edges_set.add(edge) 
    return faces[mask]