Geometry Kernel based on G1-continuous Circular Arcs

Abstract

We discuss some technical issues in the design and analysis of geometry kernel for planar geometric models designed with G1-continuous arc splines. In particular, we mainly focus on numerical instability in computing the intersection for planar curves, and how the usage of G1-continuous arc splines can alleviate some of the instability problems inherent to geometric computations using floating-point arithmetic. With arc spline models higher numerical stability, we further present algorithms for some essential operations of geometry kernel that require finding precise intersection points. As an effort to improve the computational efficiency, we also present the data structures for the geometry kernel that is tailored to modeling with G1-continuous arc splines. The presented data structures greatly simplify the bounding volume computation for planar curves through monotone segmentation and simplification of case analysis. Considering the 8-DOP bounding volume of planar curves, the BVH construction can be made with ease based on the support distances of each bounding volume. Finally, we consider applications of the aforementioned algorithms and data structures to the classical problems, such as convex hull and offset computations.

본 논문에서는 G1-연속 원호 스플라인으로 구성된 평면 모델에 대한 기하 커널의 설계 및 분석에서 몇 가지 기술적인 문제를 논의한다. 특히 평면 곡선에서의 교차점 계산이 수치적으로 불안정할 수 있는 점을 보이며, G1-연속 원호 스플라인의 사용이 이러한 컴퓨터 프로그래밍 고유의 불안정성을 완화할 수 있는 방법에 주로 초점을 맞춘다. 이에 더해, 원호 스플라인 모델의 더 높은 수치적 안정성을 토대로, 정밀한 교차점을 찾아야 하는 기하 커널의 일부 필수 연산에 대한 알고리즘을 제시한다. 또한, 계산 효율성을 향상시키기 위한 노력의 일환으로 G1-연속 원호 스플라인 모델링에 맞게 구상된 기하 커널에 대한 데이터 구조를 제시한다. 제시된 데이터 구조는 각 곡선 조각들이 단조롭게 변화하게끔 분할한 후, 분석된 케이스들을 간단화시켜 평면 곡선에 대한 경계 볼륨 계산 역시 간단하게 만들 수 있다. 평면 곡선의 8-DOP 경계 볼륨을 사용하면, 각 경계 볼륨의 지지 거리 사이의 비교를 통해 경계 볼륨 계층의 상위 노드를 쉽게 계산할 수 있다. 마지막으로 볼록 껍질 및 오프셋 계산과 같은 기존의 문제들에 본 논문에서 소개하는 알고리즘과 데이터 구조를 적용하는 방법을 제시한다.