Accelerating Geometric Operations for Freeform Models

Abstract

We introduce compact hierarchical data structures for freeform geometric models, which are constructed in a preprocessing stage. Using these data structures, we develop efficient geometric algorithms which demonstrate interactive speed. The performance improvement is often in the range of 100 ∼ 1000 times speed up when compared with the conventional algorithms which are based on on-line recursive subdivisions of freeform curves and surfaces. For planar freeform curves, we represent the recursive subdivision structure for a G1-biarc approximation as a prebuilt hierarchical data structure. Circular arcs are considerably easier to deal with than the original curves due to the simple geometrical properties of circles. Using simple tests for circular arcs we can eliminate many redundant curve segments from further consideration in many geometric computations. For the remaining curve segments, we analyze the topological structure of the solution space and efficiently compute accurate solutions numerically or using a sequence of osculating circles to the given curves. We propose new data structures for geometric operations on freeform surfaces. For the distance related computations, we employ a bounding volume hierarchy(BVH) of NURBS surfaces using Coons patches. The BVH of freeform surfaces is represented as a hierarchy of Coons patches providing very tight approximation to the surfaces. The BVH for each Coons patch can be represented very compactly using the bilinear structure of the Coons Patch. Using the Coons BVH, we can accelerate distance-related computations (collision detection, minimum distance computation, and Hausdorff distance computation) on freeform surfaces to an interactive speed. For geometric computations related to surface normals, we build hierarchical data structures for both the unit normal vector field and a special distance function, called the support distance function, which describes the signed distance of each surface point from the origin along the surface normal direction at the point. Using the special hierarchical data structure we can trim out the majority of redundant surface patches by considering the upper envelope of the support distance function defined on the Gaussian sphere. In the final stage, we compute the precise exact 1D or 2D manifold by numerically tracing the solution space. We demonstrate the effectiveness of our compact hierarchical data structure by solving several non-trivial geometric problems such as collision detection for ten thousands NURBS models colliding each other, minimum distance computation between fairly complex models, Hausdorff distance computation for freeform surfaces in close proximity and convex hull computation for freeform surfaces. The experimental results show considerable performance improvement over the conventional algorithms in computing time as well as efficient memory usage.

_x0013_ 본 논문에서는 자유형상을 위한 저용량의 계층적 전처리 자료구조를 소개하고 이를 활용하여 자유형상의 여러 기한연산들을 가속화하는 알고리즘을 제시한다. 이러한 전처리 자료구조를 이용한 가속화 알고리즘은 기존의 재귀적 분할을 기반으로 하는 기하연산의 성능을 100 ∼ 1000배 가량 향상시킨다. 본 논문에서는 평면곡선의 전처리 자료구조로 평면곡선의 재귀적인 G1-biarc 근사를 사용한다. 원호들은 곡선을 잘 근사할 뿐만 아니라 곡선에 비해 훨씬 간단한 기하학적인 성질을 가지고 있다. 본 논문에서는 이러한 원호의 기하학적 성질을 활용하여 기하연산의 결과에 영향을 미치지 않는 많은 부분곡선들을 효율적으로 제거하는 방법을 제시한다. 그리고 불필요한 부분을 제거한 뒤 남은 작은 곡선 구간들에 대해서 이들이 가지는 해공간의 위상적 구조를 분석하여 해의 유일성을 확인하고 연속적인 접촉원을 이용하여 정확한 해를 수치적으로 구하는 알고리즘을 제시한다. 자유곡면의 기하연산 가속화를 위해서 본 논문은 새로운 자료구조를 소개한다. 거리와 관련된 기하연산의 가속화를 위해 본 논문은 Coons 곡면을 이용한 NURBS 곡면의 BVH(Bounding Volume Hierarchy)를 도입한다. 자유곡면의 BVH는 곡면을 잘 근사하는 계층적인 Coons 곡면들로 이루어져 있으며 각각의 Coons 곡면의 BVH는 Coons 곡면의bilinear structure를 이용하여 효율적으로 표현이 가능하다. 본 논문에서는 이러한 Coons BVH를 이용하여 거리와 관련된 자유곡면의 기하연산들 (충돌감지, 최단거리 계산, Hausdorff 거리 계산) 을 가속화 시킨다. 법선벡터와 관련된 기하연산들을 가속화하기 위해서 본 논문은 단위 법선 벡터장과 곡면상의 각점과 원점사이의 법선 방향에 대한 거리를 나타내는 support distance function이라고 하는 특수한 거리 함수에 대한 BVH들을 사용한다. 법선벡터와 관련된 기하연산들은 공통적으로 가우스사상(Gaussian Map)에서 support distance function의 상위막(Upper Envlope)을 구한다. 법선벡터장의 BVH와 support distance function의 BVH를 활용하여 상위막에 기여하지 않는 부분곡면들을 효율적으로 제거하고 남은 부분곡면들로부터 정확한 1차원 또는 2차원 다양체를 수치적 추적(Numerical Tracing)으로 구한다. 본 논문에서는 제안한 저용량의 계층적 자료구조의 효율성을 보이기 위해서 기존의 방법으로는 수행시간이 너무 오래걸려 해결하기 어렵다고 여겨지는 여러 가지 문제들(만개의 자유 낙하하는 자유곡면들 사이의 충돌감지, 복잡한 자유 곡면 사이의 최단거리 계산, 매우 가까이 있는 자유곡면 사이의 Hausdorff 거리 계산, 자유곡면의 Convex Hull 계산)을 해결하는 알고리즘을 제시한다. 기존의 알고리즘과 비교실험 결과 제안된 알고리즘이 기존의 알고리즘에 비해 상당한 수행성능향상을 보였으며 훨씬 효율적인 메모리 사용을 하였음을 확인할 수 있었다.