This dissertation presents self-intersection detection and resolution techniques in lattice-based deformation. The lattice-based deformation indirectly deforms an object by warping the space in which the object is embedded. This approach allows efficient simulation of high resolution deformable objects by adjusting a few number of control points of the lattice. A mapping function defined by the control points determines the deformed shape of the object by mapping from parameter space to world space. Different points in parameter space may be mapped to the same point in world space according to configurations of the lattice. The self-intersection due to the non-injective mapping causes visual anomalies such as surface infiltration and distortion, which deteriorate the visual realism in interactive applications such as computer games and medical simulation. Thus, an accurate and efficient method is required to detect and resolve the self-intersection problem in simulation of the lattice-based deformation.
This dissertation derives a geometrically intuitive sufficient condition for ensuring that the mapping function is a homeomorphism (injective, onto, and continuous invertible) and there is no self-intersection. The mapping functions are defined by linear and quadratic B-Spline functions with the control points of hexahedral and cylindrical lattice cells. In a hexahedral lattice cell, the sufficient condition is satisfied if each trilinear function of the 27 hexahedrons derived from the lattice structure has a positive Jacobian determinant. The positivity is satisfied if the 32 tetrahedrons derived from the hexahedron have positive volumes. In a cylindrical lattice cell, the sufficient condition is satisfied if each trilinear function of the nine prism-shaped pentahedrons derived from the cell has a positive Jacobian determinant. The positivity is satisfied if the 12 tetrahedrons derived from the pentahedron have positive volumes.
The self-intersection detection algorithm has linear complexity. It requires 256(l-1)(m-1)(n-1) mixed triple product evaluations in a 3D hexahedral lattice structure, and 48mn-72n evaluations in a cylindrical lattice where m and n are the number of control points along the longitudinal and circumferential directions. The proposed techniques convert the self-intersection problem into point-face collision detection and response problems suitable for dynamic simulation. The efficiency and accuracy of the self-intersection detection method is analyzed and compared with the previous methods. The proposed methods provide less conservative conditions for the homeomorphic mapping and better performance in the rotation of the deformable models over the previous methods. Thus, the proposed methods are suitable for dynamic simulation of tubular objects to be modeled as the cylindrical lattices.
To validate the proposed methods in a practical application, the self-intersection detection and resolution techniques are applied to the KAIST-Ewha colonoscopy simulation. This dissertation adopts dynamic cylindrical lattice-based deformation using a mass-spring mechanical structure for realistic simulation of global and local deformations of the colon. The global and local deformations of the colon are important factors providing haptic and visual cues for complete colonoscopy. The global deformation, such as the loop of the sigmoid colon, is not observed but perceived through haptic feeling. The soft tissue of the colon undergoes large local deformations by vigorous manipulation of the colonoscope: collapse and expansion by air control, shortening and lengthening along its longitudinal semilunar folds by jiggling and torque steering, buckling around acute flexures, and twisting at the spiral loop. The local deformations enable identification of the correct advancing directions and the performance of proper skills. In colonoscopy simulation, points on the deformable colon surface may potentially collide with each other under such excessive deformations. To solve the self-intersection problem, the proposed self-intersection detection and resolution algorithms are integrated into the colonoscopy simulation. The results show that the proposed technique allows simulation of excessive deformations of the colon without self-intersection in an efficient and realistic manner.
The lattice-based deformation allows efficient simulation of a complex geometric object, but it does not allow detailed surface deformation of the object. Moreover, imposing a number of position constraints due to contact with other objects is nontrivial since applying the constraints is either underdetermined or overdetermined problem. This dissertation proposes an extended version of the lattice-based deformation to cope with these problems. The extended model enables each surface point to additionally move along the near-normal direction to the surface. The surface point moves along the direction as the parameter changes. This technique is applied to simulation of the polyp deformation in colonoscopic polypectomy simulation, which requires a realistic deformation model of the polyp and efficient treatment of multiple contacts with the snare wire. The dynamic lattice-based deformation is used for global deformation of the polyp, and is extended to handle multiple contacts with the snare wire. The proposed method accurately imposes a number of position constraints as well as improves visual realism such as detailed surface deformation. A line collision detection algorithm reduces the number of intersection tests by projection of the line segments of the snare on the grid surface mesh of the polyp. Experimental results show the optimal search range of the candidate surface points of the polyp for efficient collision detection. The proposed self-intersection detection and resolution techniques are integrated into the extended lattice-based deformation so that detailed surface deformation of the geometric complex object as well as applying a number of position constraints are efficiently computed without self-intersection. The proposed methods allow simulation of realistic deformation of the polyp in an efficient and robust manner while achieving real-time computation.
본 학위논문은 격자를 이용하는 변형 시뮬레이션에서 자체교차를 검사하고 방지하는 방법을 제시한다. 격자를 이용하는 변형 기법은 적은 수의 제어점을 사용하여 많은 수의 삼각형으로 이루어진 물체의 변형을 효과적으로 시뮬레이션 할 수 있다. 격자를 구성하는 제어점에 의해 정의되는 사상함수는 물체의 변형을 결정한다. 이 때, 격자의 형태에 따라 여러 개의 다른 점들이 하나의 점으로 사상되는 현상이 발생할 수 있다. 사상함수가 일대일 대응 조건을 만족하지 못해 발생하는 자체교차는 물체 표면이 뒤틀리거나 파고드는 현상을 야기하여 시뮬레이션의 현실감을 떨어뜨린다. 따라서, 격자를 이용하는 변형 시뮬레이션에서 발생하는 자체교차를 검사하고 방지하는 방법이 요구된다.
본 학위논문에서는 격자를 이용하는 변형에서 이 변형을 정의하는 사상함수가 위상동형사상이 되도록 하는 충분조건을 유도한다. 이 충분조건은 기하학적으로 쉽게 이해할 수 있으며, 이 조건이 만족될 경우 자체교차는 발생하지 않는다. 사상함수는 육면체구조 및 실린더구조의 격자를 기반으로 하여 선형 및 이차 B-Spline 함수에 의해 정의된다. 육면체구조 격자의 경우, 이 구조에서 유도되는 27개의 육면체 각각을 정의하는 선형 사상함수가 양의 자코비안을 갖게 되면, 충분조건은 만족된다. 양의 자코비안은 육면체에서 유도되는 32개의 사면체가 양의 체적을 갖게 되면 만족된다. 실린더구조 격자의 경우, 이 구조에서 유도되는 9개의 프리즘형태의 오면체 각각을 정의하는 선형 사상함수가 양의 자코비안을 갖게 되면, 충분조건은 만족된다. 양의 자코비안은 오면체에서 유도되는 12개의 사면체가 양의 체적을 갖게 되면 만족된다.
자체교차를 검사하는 알고리즘은 선형의 계산 복잡도를 갖는다. 육면체구조 격자의 경우 256(l-1)(m-1)(n-1)의 삼중적 계산이 필요하며, 실린더구조 격자의 경우 48mn-72n의 삼중적 계산이 필요하며, 여기서 m은 실린더구조의 길이방향, n은 원주방향 제어점의 개수이다. 제안된 방법은 자체교차 문제를 사면체의 점과 꼭지점의 충돌검사 및 방지 문제로 변환하여 해결하므로 동역학 시뮬레이션에 적합한 해법을 제시한다. 자체교차 검사 방법은 실험을 통해 분석하고 기존 연구와 비교하여 효율성 및 정확도를 검증하였다. 제안된 방법은 기존 연구에 비해 덜 보수적이며 변형 모델의 회전에 대해 더 좋은 성능을 보여준다. 따라서 제안된 방법은 실린더구조를 사용할 수 있는 튜브 형태의 물체의 변형에 대한 동역학 시뮬레이션에 더욱 적합하다.
본 논문에서 제안하는 자체교차 검사 및 방지를 위한 방법을 검증하기 위하여, 카이스트-이화 대장내시경 시뮬레이션(KAIST-Ewha Colonoscopy Simulation)에 적용하였다. 대장내시경 시뮬레이션은 대장의 진단 및 치료에 필요한 내시경 조작 술기를 연습할 수 있는 시스템이다. 대장의 전체 및 국소 변형을 구현하기 위하여 실린더구조 격자를 질량-스프링의 기계적 구조로 구성하여 동역학적 거동을 시뮬레이션 하였다. 실험 결과를 통해 제안하는 자체교차 검사 및 방지 방법이 대장의 과도한 변형을 효과적이고 현실감 있도록 시뮬레이션 할 수 있음을 검증하였다.
본 학위논문의 후반부에서는 기존의 격자를 이용하는 변형 기법의 한계점을 극복하는 방법에 대해 논한다. 격자를 이용하는 변형 방법은 복잡한 물체의 전체적인 변형 시뮬레이션에 효과적이지만, 물체의 표면의 국소변형은 다루지 않는다. 또한, 주변 물체와의 접촉에 의해 표면점의 위치를 구속해야 하는 경우, 구속조건의 수가 제어점의 수보다 많거나 적을 수 있어 구속조건을 모두 만족시키는 제어점의 위치를 결정하기 어렵다. 본 논문에서는 이를 해결하기 위해, 종래의 격자를 이용하는 변형 기법을 개선하는 방법을 제안한다. 표면점의 특정 파라메터를 변화시킬 때 사상되는 물체 표면점의 움직임을 법선 방향과 유사하게 설정하여 국소변형을 구현하는 것이 본 방법의 핵심이다. 이 방법은 대장내시경적 용종제거 시뮬레이션에서 용종의 변형을 구현하는데 적용하여 방법의 효용성을 검증하였다. 용종제거 시뮬레이션에서는 용종의 현실감 있는 변형이 구현되어야 하고 용종을 제거하기 위해 사용되는 올가미와의 접촉에 의한 다수의 표면점을 구속해야 한다. 제안된 방법을 통해 표면점의 자세한 국소 변형을 시뮬레이션하고 접촉한 표면점의 파라메터를 조절하여 다수의 구속조건을 부가한다. 또한, 올가미와 용종의 충돌을 검사하기 위해 개발된 충돌 검사 알고리즘은 올가미를 구성하는 선분을 용종의 표면에 사영하여 검사에 필요한 표면점의 수를 효과적으로 제한한다. 실험을 통하여 효과적인 충돌 검사를 위한 최적화된 검사 영역을 검증하였다. 개선된 격자를 이용한 변형 기법은 자세한 국소변형 및 다점 접촉에 의한 표면점의 구속을 효과적으로 처리하며, 자체교차 검사 및 방지 방법과 결합되어 보다 현실감 있는 실시간 시뮬레이션을 가능하게 한다.
