ㅁㄴㅇㄹ
들루네 알고리즘을 사용한 자동 2D 메쉬 생성 및 셀카 모델링 본문
개요
이 프로젝트는 컴퓨터 그래픽스 과제로 시작하게된 프로젝트이다. 과제 내용은 다음과 같은데 지금까지 배운 내용으로 본인의 사진을 찍어서 알아서 메쉬를 만들고 Opengl을 사용해 렌더링해보라는 것이다. 얼마나 정교하게 사진이랑 비슷하게 렌더링 하는지에 따라서 점수를 주는것 같다.
문제는 과제를 내준 시점에서 Vertex Shader에 관한 내용은 거의다 배웠지만 Fragment Shader에 관한 내용은 거의 못배웠다는 것이다. 라이팅, 백페이스 컬링정도까진 배우긴했는데 텍스쳐링을 못배웠다. 따라서 메쉬를 만들어서 Texture 씌워서 렌더링하는 짓은 못하고 폴리곤 하나 하나에다 색을 알아서 입혀야한다.
물론 사진으로부터 직접 폴리곤의 색을 본인이 결정하는건 웬만한 Artist적인 감각이 없으면 못할것이라고 생각한다. 사실 그래서 교수님께서 사진을 불러와서 폴리곤을 그리면 알아서 색을 입혀주는 툴을 주셨는데 (아마 과제 목적은 뷰포트 변환부터 로컬 변환까지 본인이 잘 이해하고 프로그램을 작성할 수 있는지 확인하는 것이 아닌가 싶다.) 정교한 렌더링을 위해서 툴에서 점을 찍는건 쉬운데 삼각형을 만드는건 되게 고된 일이고 (심지어 반시계방향으로 직접 만들어야한다.) 점만 내가 찍어주고 삼각형 메쉬를 쉽게 만들수 있는 방법이 없을까 고심하던 도중 괜찮은 알고리즘을 하나 발견하여 직접 프로젝트에 적용하고 렌더링하면서 느낀 생각을 정리하고자 글을 작성하게 됬다.
기반 이론
이 프로젝트에서 중점이 되는 이론은 들루네 삼각분할 (Delaunay triangulation)이다. 들루네 삼각분할은 평면위의 점들을 삼각형으로 연결하여 공간을 분할할 때, 각 삼각형의 외접원 안에 다른 삼각형들의 정점이 들어오지 않게 공간을 분할하는 방법이다.
a 와 같이 정점이 여러개 주어져 있을때 b의 경우 어떠한 삼각형의 외접원도 자기 자신의 정점을 제외한 다른 삼각형들의 정점을 포함하지 않는다. 그러나 c의 경우 특히 둔각삼각형을 하나 잡고 외접원을 그려보면 다른 삼각형들의 정점을 포함한다. 따라서 c는 들루네 삼각분할이 아니다.
들루네 삼각분할에서 만들어진 삼각형은 들루네 삼각분할을 만족하지 않는 다른 분할보다 비교적 균일한 메쉬를 만들어낸다. 어떠한 오브젝트를 모델링할 때 메쉬가 균일하지 않고 둔각삼각형의 형태와 같이 길게 쭉 늘어져있으면 객체를 모델링할 때 왜곡현상이 심하게 나타나리란건 직관적으로 추측해 볼 수 있다. 따라서 들루네 삼각분할은 어떠한 메쉬를 만들어 내기에 적합한 알고리즘이라고 생각하여 해당 알고리즘을 통해 폴리곤을 생성해보기로 결정 하였다.
들루네 삼각분할을 생성하는 알고리즘의 의사코드는 다음과 같다.
1. 먼저 Big Triangle이라고 하는 거다란 삼각형을 하나 만든다. 이러한 삼각형의 좌표는 해당 좌표계에서 쓸수 있는 가장 큰 값들을 사용하여 만든다. (예를 들면 10 * 10 좌표계가 있다고 가정하면 –10, -10, 10, -10, 0, 10의 좌표값을 사용해 삼각형을 만든다.)
2. 정점을 찍되, 현재까지 만들어진 삼각형들 중에서 해당 정점이 외접원 안에 들어가는지 확인한다. (지금은 big triangle 하나뿐이므로 첫 정점은 무조건 big triangle의 외접원 안에 들어감)
3. 해당 정점을 포함하는 외접원을 가지는 삼각형들의 edge를 모두 집합에 넣되, 중복된다면 뺀다.
4. 외접원 안에 정점이 들어가게 되는 삼각형을 모두 삼각형 집합에서 뺀다. (이를 bad triangle이라고 하며, big trangle도 당연히 빠지게 된다.)
5. 이제 아까 넣어놨던 edge들과 입력받은 정점 하나를 가지고 삼각형을 만든다. (여기서 cross poduct 검사를 해서 만약에 직선이라면 넣지 않는다.)
6. 정점이 모두 끝날떄까지 반복한다.
7. 이제 big triangle을 구성했던 맨 처음 3개의 정점들을 포함하는 삼각형들을 제외하고 나머지 삼각형들을 결과로 출력한다.
어떠한 정점이 주어진 삼각형의 외접원에 있는지 검사는 행렬식을 통해서 검사하는데 이부분의 자세한 알고리즘은 생략한다. 들루네 삼각분할의 구현은 다른분의 소스코드를 참고했는데 이분이 잘 구현하신게 있어서 나도 그냥 의사코드만 분석하고 가져다 썼다. 구현하신분의 블로그 링크를 남긴다.
https://www.secmem.org/blog/2019/01/11/Deluanay_Triangulation/
작업 과정
먼저 사진들으로부터 정점을 찍고 해당 점의 좌표값을 input으로 아까 위에서 얻은 소스코드를 통해 삼각형들을 만든다.
정교한 모델링을 하고싶어서 점을 한 2000개정도 찍어줬는데 저기서 점들끼리 직접 드래그 하면 삼각형도 만들어 주지만 2천개를 일일이 하나씩 다 이어주기에는 어지럽기때문에 들루네 알고리즘의 도움을 받을 것이다.
여기서 점들의 좌표는 사진의 pixel이 기준이 되는데 현재 사진이 512 * 512 이므로 Point도 512 * 512 좌표로 나온다. 이러한 좌표를 기준으로 위에서 얻은 소스코드에서 input.txt를 입력으로 넣어주면 알고리즘이 알아서 삼각형을 다 만들어준다.
여기서 문제가 하나 더 생기는데 들루네 분할이 삼각형을 만들어주는건 좋았지만 삼각형의 색을 어떻게 자동으로 만들어주어야 하는지가 문제가 된다. 이부분은 파이썬으로 구현해보고자 했는데 먼저 삼각형을 이루는 정점에 위치하고 있는 픽셀의 rgb값을 받아 세 정점 픽셀의 rgb값을 평균을 내어 삼각형의 색을 결정해보기로 했다. 코드는 다음과 같다.
from PIL import Image
import numpy as np
# image 크기는 512 * 512
# 사진을 열어서 2차원 배열 형태로 픽셀을 저장
im = Image.open('origin.jpg')
im_matrix = np.array(im)
# 현재 정점 2144개
cnt = 0
sum_r = 0
sum_g = 0
sum_b = 0
output_line = ""
f = open("CCW_Triangle.txt", 'r')
while True:
line = f.readline()
cnt += 1
if not line: break
print("vertex")
print(line)
# 기존의 정점 위치 좌표는 그대로 출력함
output_line += line
str_lst = line.split()
param1, param2 = int(str_lst[0]), int(str_lst[1])
# print(im_matrix[param1][param2])
# 세 정점의 평균 rgb를 계산하기 위해 rgb변수에다 저장
# rgb값은 앞서 그림을 2차원 행렬로 변환하여 들어가져있으며 opengl은 top-left가 0,512이나
# 그림파일의 경우 top-left가 0,0이기때문에 opengl 좌표를 그림파일 좌표로 변환하여 rgb값을 탐색
r = im_matrix[512-param2][param1][0]
g = im_matrix[512-param2][param1][1]
b = im_matrix[512-param2][param1][2]
sum_r += r
sum_g += g
sum_b += b
if cnt % 3 == 0 :
# 정점이 3개씩 삼각형을 이루므로 3의 배수마다 rgb 평균값을 계산하고 출력 및 rgb 다시 0으로 초기화하여 계속 계산
r = round(sum_r / 3)
g = round(sum_g / 3)
b = round(sum_b / 3)
print("color interpolation")
print(r,g,b)
sum_r = 0
sum_g = 0
sum_b = 0
output_line += str(r) + " " + str(g) + " " + str(b) + "\n"
f.close()
f = open("Wireframe.txt", "w")
f.write(output_line)
f.closepython의 pillow 알고리즘을 사용하면 사진의 특정좌표에 있는 rgb 픽셀값을 쉽게 얻어올 수 있다. opengl의 좌표는 top-left가 0, 512이지만, 사진의 경우 top-left가 0,0 이라는 점에만 주의해주면 된다. 이렇게 삼각형 색깔까지 전부다 정해줬고 이제 Opengl을 통해 렌더링 해주기만 하면 과제를 마칠수 있게 된다.
작업 결과
렌더링 이미지
렌더링이 어느정도 되긴했는데 폴리곤을 엄청나게 많이 만들어주었음에도 불구하고, 막 모자이크된것처럼 흐려보이고 여기저기 각져보인다. 그래픽스에서 말하는 흔히 flat-shading처럼 보이고 있는데 이는 폴리곤들의 색깔이 모두 동일하게 결정이 되고있기 때문이다. 텍스쳐를 사용한다면 텍스쳐링 단계에서 폴리곤이 전부 동일한 색을 가지는게 아니라 텍스쳐의 좌표를 기준으로 여러가지 보간작업이 들어가서 하나의 폴리곤에도 여러가지 색이 들어가 상당히 부드럽게 렌더링이 되는데 지금은 텍스쳐를 사용할수 없는 상황이므로 어쩔수없다.