This dissertation presents a novel method for a real-time and stable cutting simulation of deformable objects using meshless method. Three major issues in the meshless cutting simulation, i.e. real-time computa-tion, topology change management, and contact and intersection processing are addressed in this dissertation.
Element-free Galerkin (EFG) method is employed as a numerical model of the deformable object. The multi-resolution technique is introduced to improve the computational performance of the conventional EFG. Two different resolutions of uniformly placed simulation nodes, i.e. sparse and dense nodes, are employed for one deformable object. In this approach, first we define the surface layer as a region extended from the surface to certain depth into the internal part of the object. Deformation of the surface layer is precisely computed using the dense nodes placed in this region which is called active nodes. The deformation of the other dense nodes placed in the internal part of object that is called passive nodes is computed by interpolating the displacement field computed using the sparse nodes. The multi-resolution approach reduces tremendous computation by replacing the computation required to compute deformation of the passive nodes with that of the sparse nodes while maintaining details of the deformation near the surface.
Topology change of the meshless object arisen in the cutting procedure is managed using visibility cri-terion. Topological relation among simulation nodes is defined as an undirected graph which connects the nearby nodes placed inside of the support. This graph is called connectivity graph. The connectivity graph is refined by testing intersections between the edges of the graph and the cut surface, and related variables with the intersected edge such as neighbor node relation, shape function values are locally updated. Our approach utilizes the BVH to accelerate the computation of the intersection test. The real-time reconstruction algorithm of the BVH is proposed to prevent the performance degradation of the intersection test in case where pieces of the object are completely cut out from the object. Performing the reconstruction operations only in the region related to the cutting, the algorithm removes unnecessary operations in the reconstruction process.
The surface of the meshless object is represented as a triangular mesh for the fast visual rendering and efficient contact handling. The algorithm for adaptively re-meshing the intersected surface mesh with the cut surface is presented. The interaction with other objects is managed by modeling the contact force using Signorini’s contact law. The mapping matrix that relates the displacement and force between the surface and simulation nodes is defined using MLS shape functions. The contact force is computed by solving linear com-plementary problem (LCP) formulated by the mapping matrix and Signorini’s contact law. The proposed method allows precise handling of the contact while guaranteeing non-penetration.
This dissertation explores the performance of the proposed method by quantitatively comparing the stability of the proposed method with the previous FEM and XFEM cutting simulation method. The simula-tion results prove superior performance of the proposed method in the stability compared to FEM. In terms of computational performance, the proposed method allows 7fps in the cutting simulation of deformable objects composed of 51,200 surface triangles and 24,104 simulation nodes. This simulation result implies one order of performance improvement compared to the previous meshless cutting simulation.
실시간 절개 시뮬레이션은 가상환경 및 컴퓨터 그래픽스 분야에서 주로 적용 되고 있다. 절개 시뮬레이션에서 발생하는 위상변화를 안정적으로 처리하는 것이 어렵기 때문에 실제 적용분야에서 시뮬레이션을 하는데 어려움이 있었다. 본 연구에서는 무요소법을 이용하여 변형체의 절개 시뮬레이션을 빠르고 안정적으로 구현할 수 있는 방법을 제안하였다.
Element-Free Galerkin (EFG) 방법을 이용하여 변형체의 거동을 수치적으로 모델화하고, 실시간 시뮬레이션에서의 계산성능을 향상시키기 위해서 다해상도 기법을 도입하였다. 고해상도의 절점과 저해상도 절점을 하나의 변형체 모델에서 혼합하여 사용하였다. 먼저 변형체의 표면으로부터 변형체의 내부로 일정 깊이까지의 영역을 표면 층으로 정의하고 나머지 영역을 내부 층으로 정의하였다. 표면 층에서의 변형은 고해상도의 절점을 이용하여 정확히 계산하여 고품질의 그래픽 렌더링을 할 수 있도록 하고, 내부 층에서의 변형은 저해상도 절점을 이용하여 빠르게 계산할 수 있도록 한다.
절개 시뮬레이션에서 발생하는 변형체의 위상 변화는 기존의 visibility criterion을 이용하여 처리한다. 이를 위해 먼저 절점들 사이의 연결관계를 undirected graph로 정의하고 절개 시뮬레이션에서는 절개 면과 교차하는 graph의 edge를 제거하여 절점들 사이의 연결관계를 업데이트 한다. 이때 graph의 edge들과 절개면 사이의 겹침을 빠르게 검사하기 위해서 bounding volume hierarchy (BVH)를 사용한다. 변형체가 절개 되었을 때 BVH를 실시간으로 재 구성할 수 있는 방법을 제안하여 절개 이후에도 시뮬레이션의 성능이 저하되지 않도록 한다. 제안하는 BVH 재 구성방법은 필요한 계산을 절개 영역 근처에서만 수행 함으로써 기존 방법의 성능을 향상시켰다.
그래픽 렌더링과 외부 물체와의 접촉을 처리하기 위해서 본 연구에서는 삼각메쉬로 구성된 별도의 표면모델을 사용한다. 변형체가 절개 될 때 표면모델을 re-mesh하는 방법과 외부 물체와의 접촉이 발생하였을 때 Signorini’s contact law를 이용하여 접촉을 해결하는 방법을 제안한다. 표면모델과 절점들 사이의 변위관계를 나타내는 mapping matrix를 정의하고 Signorini’s contact law를 적용하여 linear complementary problem (LCP)을 구성한다. 이러한 LCP를 해결함으로써 시뮬레이션에서 변형체 사이에 접촉이 발생하였을 때 겹침이 없이 접촉을 해결할 수 있도록 한다.
본 논문에 제안하는 방법을 성능을 검증하기 위해서 기존의 FEM, XFEM, Meshless 방법을 이용한 절개 시뮬레이션과 제안하는 방법의 성능을 시뮬레이션의 안정성과 계산효율성 측면에서 비교하였다. 안정성 측면에서 기존 FEM 절개 시뮬레이션 대비 월등한 성능을 보였고 계산성능 측면에서도 51,200의 삼각형과 24,104개의 절점으로 구성된 변형체에 대해서 약 7fps의 성능을 보였다.
