Polygon-based Vector Voronoi Diagram Implementation

서지정보

· 발행기관 : 한국컴퓨터게임학회
· 수록지 정보 : 한국컴퓨터게임학회 논문지 / 36권 / 2호
· 저자명 : Cheung Woon JHO

목차

ABSTRACT
1. Introduction
2. Polygon Based Voronoi Algorithm
2.1 Generate a Voronoi diagram for a set of
2.2 Create a Voronoi diagram for a line
3. Conclusion
Reference
국문초록
결론 및 향후 연구

초록

2차원 평면에서 점들의 집합에 대한 보로노이 다이어그램을 구현하는 경우는 비사실적 렌더링이나 스타일화 된 렌더링에 매우 자주 사용하는 기법이다. 하지만 기존의 연구들의 구현 방법을 살펴보면 픽셀기반의 이미지 공간에서 보로노이 셀을 계산하는 방식이 활용된다. 벡터기반의 보로노이 다이어그램의 구현은 셀들이 만나서 이루는 경계부분을 직접적으로 표현할 수 있는 방식이다. 픽셀 기반의 방법의 경우 보로노이 셀간의 경계는 이미지 형태로 먼저 만든 후 에지 추출 영상 처리를 통해 얻을 수 있으며 해상도에 따라 정확도가 결정되며 벡터 기반의 방법보다 부정확할 수 밖에 없다. 즉, 픽셀 기반의 보로노이 다이어그램 생성 방법은 보로노이 셀 영역을 위주로 계산하게 되고 명확한 경계에 대한 데이터를 명시적으로 가지고 있지 않는다. 이와는 대조 적으로 벡터 기반의 보로노이 다이어그램 생성 방법은 보로노이 다이어그램의 경계선 데이터를 직접 포함하 고 있으므로 정확도가 높은 표현 방법이라고 할 수 있다. 다만 픽셀기반의 구현 방법이 좀 더 직관적이고 쉬 운 구현 방법이라는 점 때문에 기존의 연구들은 픽셀기반의 구현을 사용하고 있다. 본 연구에서는 점에 직접 폴리곤 지오메트리를 사용하여 3차원 공간에서 보로노이 다이어그램을 계산하는 방법을 제안한다. 유클리드 거리와 맨해튼 거리를 모두 사용할 수 있으며 선분에 대한 보로노이 다이어그램의 확장에도 사용할 수 있도 록 제안하였다.

영어초록

Implementing a Voronoi diagram for a set of points on a two-dimensional plane is a technique very often used for non-realistic or stylized rendering. However, looking at implementation methods of existing studies, a method of calculating Voronoi cells in a pixel-based image space is used. The implementation of the vector-based Voronoi diagram is a method that can directly express the boundary where cells meet. In the case of the pixel-based method, the boundary between Voronoi cells can be obtained through edge extraction image processing after first making it in the form of an image, and the accuracy is determined by the resolution, which is inevitably less accurate than the vector-based method. That is, the pixel-based Voronoi diagram generation method mainly calculates the Voronoi cell area and does not explicitly have data on clear boundaries. In contrast, the vector-based Voronoi diagram generation method can be said to be a highly accurate expression method because it directly includes the boundary line data of the Voronoi diagram. However, because the pixel-based implementation method is a more intuitive and easy implementation method, existing studies are using the pixel-based implementation method. In this study, we propose a method for calculating Voronoi diagrams in 3D space using polygon geometry directly at points. Both the Euclidean distance and the Manhattan distance can be used, and it is proposed to be used for the extension of the Voronoi diagram for line segments.

참고자료

· 없음