습도, 고저차, 식생 분포의 요소를 가진 여러 바이옴을 가진 섬을 만들어 보려고 합니다.
하나하나 만들기엔 너무 노가다라 절차적 생성 기법으로 한번 비벼볼 계획입니다.
처음엔 섬을 특정한 청크 단위로 바이옴을 나눠보기로 했습니다.
그런데 마인크래프트처럼 n*n 범위의 정사각형으로 나누기엔 핏이 안맞을 것 같다는 생각을 했습니다.
그도 그럴것이 마인크래프트의 맵이 사실상 무한한 형태라...
제가 구현하고 싶은 것은 좁디 좁은 섬입니다.
비교 대상과의 스케일 차이가 너무 커서 같은 방법으로 나누기엔 너무 분포의 모양새가 안살 것 같다는 우려를 하는데...
그러다 아주 좋은 슬라이드를 발견했습니다. 보로노이 다이어그램을 통해 만드는 것 같더라고요?
설명할 여유가 없어 이미지로 설명을 대체합니다.
보로노이 다이어그램으로 만들게 된다면 바이옴을 다각형 폴리곤 형태로 이쁘장하게 나눌 수 있을 것입니다.
보로노이 다이어그램을 이용해 바이옴을 나누는 방법
원리 설명 하기 전 용어 정리 한번 합시다.
가장자리 (edge) : 보로노이 다이어그램의 폴리곤을 이루는 선
모서리 (corner) : 보로노이 다이어그램의 폴리곤을 이루는 정점 (vertex)
맵을 표현하기 위해 두 가지 그래프를 사용할 것입니다.
1. 각각의 폴리곤을 나타내는 노드와 인접한 폴리곤 사이의 가장자리가 저장된 인접성 그래프.
폴리곤의 중심을 이으면 델로네 삼각분할이 만들어집니다.
그렇기 때문에 폴리곤끼리의 인접성이 필요한 작업을 쉽게 수행할 수 있습니다.
ex) 길찾기
2. 폴리곤의 모서리가 저장된 노드와, 두 모서리 사이의 가장자리가 저장된 형태 그래프.
가장자리가 저장되어있기 때문에, 폴리곤의 형태를 사용하는 작업을 쉽게 수행할 수 있습니다.
ex) 폴리곤 경계 그리기
이 두 그래프는 서로 연관되어있습니다.
폴리곤의 중심을 이어 만든 델로네 삼각분할을 이루는 삼각형은
보로노이 다이어그램의 가장자리와 대응하고, 폴리곤의 중심은 델로네 삼각분할의 모서리와 대응합니다.
사진에서 폴리곤 A, B는 인접해있습니다.
그렇기 때문에 인접성 그래프엔 A와 B 사이의 빨간 간선이 있습니다.
두 폴리곤이 인접해있기 위해선 둘 사이에 가장자리(edge)가 존재해야 합니다.
사진에 있는 파란색 가장자리는 보로노이 형태 다이어그램의 모서리 (corner) 1, 2를 잇습니다.
여기서 인접성 그래프의 모든 간선은 보로노이 형태 다이어그램의 정확히 한 모서리와 대응되어있습니다.
이 델로네 삼각분할에선 삼각형 ABC가 3개의 폴리곤을 연결하는데, 이는 모서리 2로도 표현할 수 있습니다.
그러므로, 델로네 삼각분할의 가장자리는 보로노이 다이어그램의 폴리곤을 나타낼 수 있습니다. (그 역도 성립합니다).
밑의 사진에서 이 두 그래프의 더 넓은 관계를 볼 수 있는 예시를 볼 수 있습니다.
보로노이 폴리곤의 중심이 빨간 점, 모서리가 파란 점, 가장자리가 흰 선으로,
델로네 삼각분할은 검은 선으로 나타내져있습니다.
이 쌍대성은 두 그래프를 이처럼 동시에 나타낼 수 있다는 것을 의미합니다.
두 그래프의 데이터를 합치는 데엔 여러 접근 방법이 있는데,
그 중 간선를 공유하는 방법이 있습니다.
보통 그래프 자료구조에선 간선 하나마다 두 개의 노드를 가리킵니다.
여기선 두 개의 간선(가장자리)을 두 개의 그래프로 분리해 나타내는 대신
하나의 간선이 인접한 폴리곤 두개와 그 가장자리를 이루는 두 모서리를 나타내도록 할 수 있습니다.
요약 : 먼저 보로노이 다이어그램을 생성한 후, 폴리곤을 이루는 가장자리에서 해당 가장자리가 포함된 인접한 폴리곤 두 개와,
가장자리를 이루는 두 점(모서리)를 유도할 수 있도록 해야함.
'이론' 카테고리의 다른 글
| 동적으로 섬 생성하기 - 4 (지형 생성 해보기) (0) | 2021.03.27 |
|---|---|
| 동적으로 섬 생성하기 - 3 (노이즈를 사용한 지형 생성) (0) | 2021.03.26 |
| 동적으로 섬 생성하기 - 2 (바이옴 분할의 시각화) (2) | 2021.03.25 |
