In CAD/CAM/CAE and Computer graphics research, point sets and triangular meshes are being widely used to represent the shape of an object. For the efficient processing of geometric shape represented by an unorganized set of points or triangles (called point set and triangle soup, respectively), it is crucial to have the connectivity information among the geometric elements. This thesis is made of two parts. The first part deals with the connectivity information construction (neighbor finding in this case) among unorganized points. The second part explains the topological information construction among unorganized triangles.
Neighbors of a point in a point set have been defined in various ways in the literature. In this thesis, we pursue a method to find directionally balanced neighbors while considering distance from the query point as well. To find neighbors in a point set, mesh structures and neighborhood graphs are commonly used. However, though meshes are very popular in the field of computer graphics, neighbor relations encoded in a mesh are often distorted. Likewise, neighborhood graphs, such as the minimum spanning tree (MST), relative neighborhood graph (RNG), and Gabriel graph (GG), are also imperfect as they usually give too few neighbors for a given point. In this paper, we introduce a generalization of the Gabriel graph, named the Elliptic Gabriel Graph (EGG), which takes an elliptic influence region instead of the circular region in GG. In order to determine the appropriate aspect ratio a of the elliptic influence region of EGG, this paper uses the relation between the aspect ratio a and the average valence of the result. Analytic and empirical test results are included.
Triangle soup, commonly given as STL file format, lacks of topological information, which tells the connectivity between triangles. The proposed topology construction algorithm for a triangle soup consists of the following steps: (1) vertex merging, (2) internal edge linking, (3) multi-disk vertex splitting, and (4) boundary gap stitching. Typical triangle soup comes in the form of an STL file, and topology construction work encounters non-manifold cases for various causes, which should be converted to 2-manifold models for many downstream processes such as rapid prototyping and tool path generation. The proposed algorithm uses a light-weight vertex-based data structure (adapted from a corner table structure), and does not need to construct a full non-manifold topology information. The efficiency of the proposed algorithm is shown by empirical tests on practical examples.
CAD/CAM/CAE 및 컴퓨터 그래픽스 분야에서, 점 집합 및 삼각형 메쉬는 물체의 형상을 표현하기 위해서 널리 사용되고 있다. 구조화되지 않은 점 집합 또는 삼각형 집합 (각각, point set과 triangle soup으로 불림)으로 표현되는 기하학적 형상의 효율적인 처리를 위해서는, 기하 요소들간의 연결관계(connectivity information)를 가지는 것이 중요한 일이다. 본 논문은 크게 두 개의 파트로 구성되어있다. 첫 번째 파트는 구조화되지 않은 점 들간의 연결관계(즉, 이웃점 찾기)에 대해서 다룬다. 두 번째 파트는 구조화되지 않은 삼각형들간의 위상정보 구성에 대해서 다룬다.
점 집합에서의 이웃점군은 기존 문헌들에서 다양하게 정의되어 왔다. 본 논문에서는 질의점으로부터의 거리뿐만 아니라 방향까지 고려한 균형 잡힌 이웃점군을 계산하는 방법을 추구한다. 점 집합에서 이웃점군을 찾기 위해서 흔히 메쉬 구조나 인접성 그래프가 사용된다. 비록 메쉬가 컴퓨터 그래픽스 분야 등에서 널리 사용되지만, 메쉬에 내포된 이웃 관계는 종종 왜곡이 된다. 이와 유사하게, MST(minimum spanning tree), RNG(relative neighborhood graph), GG(Gabriel graph)와 같은 인접성 그래프들도 완전하지는 못한데, 이는 너무 적은 개수의 이웃점들을 주기 때문이다. 본 논문에서는 GG(Gabriel graph)의 일반화된 개념인 EGG(Elliptic Gabriel Graph)를 제안한다. 이것은 GG에서의 원형(circular) influence region 대신에 타원형(elliptic) influence region을 가진다. EGG의 타원형 influence region의 종횡비를 결정하기 위해서, 종횡비와 이웃점군의 평균 개수(valence) 사이의 관계를 분석하였다. 분석 및 실험 결과를 제시하였다.
흔히 STL 파일 포맷으로 주어지는 triangle soup은 삼각형들간의 연결관계를 알려주는 위상정보를 가지고 있지 않다. 본 논문에서 제안하는 triangle soup에 대한 위상정보 구성 알고리즘은 다음의 단계로 이루어진다: (1) 꼭지점 병합, (2) 내부 모서리 연결, (3) 멀티디스크 꼭지점 분할, 및 (4) 경계모서리 붙이기. Triangle soup에 대한 위상정보 구성 작업은 다양한 이유로 인한 비 다양체 요소(non-manifold cases)들을 처리해야 하는 데, 이들은 쾌속조형과 공구경로생성 등 다양한 분야의 후속 작업들을 위해서는 다양체(manifold)로 변환 되어야 한다. 제안된 알고리즘은 코너테이블(corner table)을 변형한 꼭지점에 기반한 경량의 자료구조를 이용하며, 비 다양체 위상정보를 모두 구성하지 않고도 다양체 위상정보를 구성할 수 있는 특성을 지닌다. 실제적인 예제들에 대한 실험 결과로 제안된 알고리즘의 효율성을 보였다.
