Real-time interactive simulations based on the virtual environments provide users with a variety of realistic experiences. Immediate visual and force feedbacks are necessary according to the user inputs, and each feedback requires a fast computation with a refresh rate of 30 Hz and 300 – 1,000 Hz, respectively. Dynamic simulation of the deformable models requires lots of computations. Computational complexity for this simulation is typically known as $O(n^{3})$, where n is the degrees of freedom of the model. Despite of the great improvements in the processing hardware, it is still difficult to achieve a high fresh rate for the force rendering, i.e., 300 - 1,000 Hz. Furthermore, the difficulty is further exacerbated in the cutting or fracture simulation due to additional computation burdens and numerical instability problems. Previous approaches such as multi-rate methods, learning-based methods, and order reduction methods address this problem. In this dissertation, the deformable model consists of a single type of regular hexahedrons only. Because the object geometry is not filled with regular hexahedrons only, small gaps between the object boundaries and the hexahedrons are allowed. Additional surface structure is constructed for surface representation, and is approximated from the regular hexahedrons. Features of this modeling method are exploited in the deformation and cutting simulation method. Firstly, parallel computing method of computing the model deformation is introduced. The entire computation is formulated into a node-wise form, taking into account that the element stiffness matrices are the same and the number of hexahedrons around the node is small. Methods to simulate large deformations and anisotropic material properties in the model are also presented. The model boundaries are represented by a triangular mesh, which is approximated by neighboring hexahedral nodes and Moving-least-squares (MLS) approximation functions. A method of grouping the neighboring nodes and computing the corresponding MLS functions is introduced. Two separate ways of updating the surface meshes are introduced; the entire mesh is updated for each visual loop, whereas a few meshes around the tool are locally updated for each haptic loop. This approach dramatically reduces the computational burden for a haptic loop. Second, cutting simulation method is proposed, which faithfully represents a given cutting path but still maintaining the numerical stability condition. The proposed method duplicates the intersected hexahedrons, so the reference size and shape can be maintained. This approach ensures numerical stability condition of the entire model based on the relevant theoretical background. Additional surface meshes and vertices are created to faithfully represent the cutting path. It is important to determine the group of neighboring nodes for each surface vertex, because the two different sides of the cut surface must be properly separated. Besides, the group of surface vertices to be updated should be minimized for the computational efficiency. Methods to deal with such problems are introduced. A few cutting cases including a partial cutting of the model, a curved cutting path, and a concave-shaped model are simulated. Cutting of soft tissues using a surgical knife involves repeated loadings (or deformations) and sudden force drops (or cuttings). This phenomenon is reflected in this dissertation to render a realistic force feedback during the cutting. In the loading section, each contact vertex is mapped to the closest hexahedral node to share the penetration depth and the contact force. Cutting is simulated when the contact force exceeds a threshold. Since the cut surface is generated within the model, the contact force is reduced in the next simulation time step. The computational efficiency of the proposed method is compared with previous methods in the literature. Simulation results show that the proposed deformation simulation method is approximately 10 times faster than the previous methods. The proposed method can simulate the deformation of a model consisting of 32,712 nodes with a refresh rate of more than 500 Hz using a typical PC. Besides, additional computation burdens from the cutting simulation are compared with the previous method. The theoretical range of additional nodes and elements is derived, and the average computation time is compared with a few cutting simulation examples. Both theoretical and simulation results show that the additional computation burden of the proposed method is reduced to about 30 % compared to the previous method. Small gaps between the given object boundaries and the hexahedrons deteriorate the simulation accuracy. This problem is exacerbated as the object size becomes smaller compared to the hexahedron size. This dissertation introduces a method of considering a partial element, which is partially included inside of the object geometry. Additional computations required for the partial elements and the corresponding error reduction are presented. The model constructed in the proposed method is compared with the conventional Finite-element Method (FEM) model, and the differences are verified in terms of the human Just Noticeable Difference (JND).
가상 환경을 이용한 실시간 상호작용 시뮬레이션은 가상 환경을 실제와 유사하게 구성하고, 사용자로 하여금 이와 상호작용 할 수 있도록 한다. 사용자의 조작에 따른 즉각적인 시각 및 햅틱 감각을 제공하는 것이 중요하며, 이를 위해 시뮬레이션은 각각 30 Hz 와 300-1,000 Hz 이상의 빠른 갱신주기로 동작해야 한다. 가상 변형체 모델의 거동을 계산하는데 필요한 계산복잡도는 일반적으로 모델 자유도의 세제곱에 비례하며, 이러한 계산을 1,000 Hz의 빠른 갱신주기로 수행하는 것이 매우 어렵다. 모델의 절개 및 파단 등을 함께 시뮬레이션 하는 경우, 모델의 수치적 불안정성 문제 및 추가적인 계산 등으로 인해 어려움이 가중된다. 다중율 방법(Multi-rate method), 사전 학습 기반 방법(Learning-based method), 특이값 분해(Eigenvalue decomposition) 방법 등 시뮬레이션에 필요한 계산을 줄이기 위한 여러 가지 사전 연구들이 제안되었다. 본 연구에서는 가상 변형체 모델을 단일 정육면체 요소만으로 구성한다. 단일 정육면체 요소만으로 다양한 물체의 형상을 완벽히 채우는 것이 불가능하므로 객체 경계와 육면체 요소 사이의 위치 격차를 허용한다. 물체 경계를 표현하기 위해 별도의 표면 구조를 구성하고, 정육면체 요소에서 계산된 결과로부터 이를 근사하여 물체의 경계를 표현한다. 이렇게 구성한 모델의 변형 및 도구와의 접촉을 시뮬레이션 하는 방법 및 절개를 시뮬레이션 하는 방법을 차례로 제안한다. 첫째로 모델 내 정육면체들이 서로 동일한 크기, 모양, 배치를 갖는 점을 활용하여 모델의 변형 계산을 병렬화하는 방법을 제안한다. 요소 강성행렬이 모두 동일한 점, 노드 주변의 요소 개수 범위가 한정적인 점 등을 활용하여 변형 계산을 각 노드 단위로 재구성하고, 이를 GPU(Graphics Processing Unit)에서 병렬로 계산하는 방법을 설명한다. 모델의 대변형(Large deformation)을 고려하는 방법 및 한 모델 내에서 서로 다른 물성이 혼재된 경우를 다루는 방법을 제시한다. 이 때 모델의 경계를 표현하는 표면 구조는 삼각형 표면 메쉬로 구성하며, 각 꼭짓점 변위를 MLS(Moving-least-squares) 근사 함수를 통해 계산한다. 각 꼭짓점마다 주변 노드 그룹을 결정하는 방법 및 함수 값을 계산하는 방법을 소개한다. 특히, 1,000 Hz의 빠른 계산 갱신주기가 필요한 햅틱 루프에서 도구 주변의 국소 표면 영역을 정의하고 이를 별도로 갱신하여 계산 부담을 크게 줄이는 방법을 제안한다. 둘째로 시뮬레이션 도중에 정의되는 절단 경로를 충실히 반영하면서도 모델의 수치적 안정성을 유지하는 절개 시뮬레이션 방법을 제안한다. 절단 경로에 의해 교차된 정육면체를 복제하여 요소의 기준 모양 및 크기가 유지되도록 시뮬레이션 한다. 각 육면체 요소의 수치적 안정성 조건이 유지되면 자동으로 모델 전체의 수치적 안정성이 보장되며, 이에 대한 이론적 배경을 소개한다. 주어진 절단 경로에 알맞게 절단면을 표현하기 위해 표면 메쉬 및 근사함수를 생성하는 방법을 소개한다. 분리된 양쪽 절단면을 구분하기 위해 주변 노드 그룹을 선정하는 방법 및 도구와의 상호작용 구현 방법을 제시한다. 모델의 부분적인 절개, 굴곡진 절단 경로, 오목한 형상의 모델 등 다양한 절개 사례를 시뮬레이션 한다. 절개 시 발생하는 힘을 사용자에게 제공하기 위한 계산 방법을 제안한다. 수술칼을 사용한 연조직의 절개는 반복적인 하중 구간 및 갑작스런 힘의 강하(절개) 구간이 발생하는데, 이를 시뮬레이션에 반영한다. 하중 구간에서는 접촉된 표면 꼭짓점과 인접한 노드 사이의 연결을 정의하여 침투 깊이 및 접촉힘을 주고받도록 한다. 접촉힘이 임계값을 넘어설 경우 모델 내부에 절단면을 생성하여 접촉힘의 강하 현상을 시뮬레이션 한다. 제안하는 변형 및 절개 시뮬레이션 방법을 기존 문헌에 소개된 방법들과 비교 및 검증한다. 일반적인 사양의 PC에서 32,712 개의 노드로 구성된 모델의 변형 계산이 500 Hz 이상의 갱신 주기로 수행 가능함을 보이며, 동일한 조건에서 기존 방법 대비 약 10 배 우수한 계산 효율을 갖는 것을 보인다. 또한, 절개를 시뮬레이션 할 때 가중되는 계산 부담을 또 다른 기존 방법과 비교한다. 동일한 절단 경로를 표현하기 위해 각 방법에 필요한 추가 계산량을 이론적으로 분석하고, 몇 가지 절개 사례를 시뮬레이션 하여 제안하는 방법이 우수함을 보인다. 제안하는 모델은 모델링 할 객체의 경계와 육면체 요소 사이의 위치 격차로 인해 오차가 발생하며, 이는 객체 형상이 육면체 요소 크기에 비해 얇을수록 두드러진다. 물체 경계에 부분적으로 속하는 소위 부분 육면체 요소(Partial elements)를 고려한 모델의 정확도 향상 방법을 제안하고 이를 검증한다. 제안하는 모델과 전통적인 유한요소법으로 구성한 모델로부터 계산되는 탄성 값의 차이를 인간의 식별 최소차(Just noticeable difference) 관점에서 분석한다.
