메타볼로 표현된 물체의 충돌탐지와 변형 = Collision Detection and Deformation of an Object Represented as Metaballs

국문 초록 (Abstract)

애니메이션에서 충돌탐지와 변형은 필수적이다. 그래픽스에서는 물체를 표현하기 위해 다각형 프리미티브를 사용하거나 음함수 곡면(implicit surface)을 사용한다. 물체가 다각형으로 표현된 경우 충돌탐지는 계산 복잡도(computational complexity)가 커진다. 이는 바운딩 볼륨(bounding volume) 교차영역에서 다각형 교차문제로 계산되기 때문이다. 이에 반해 음함수 곡면으로 표현된 물체는 충돌 탐지가 상대적으로 쉬워진다. 또한 좀더 복잡한 형태의 물체(multi-body)의 충돌 탐지도 쉬워진다.
지금까지 사용되는 구(spheres)와 변형가능한(deformable) superqudrics와 같은 음함수 곡면의 충돌탐지는 내부/외부(inside/outside) 함수를 이용하여 표현된다. 그러나 이러한 방법은 바운딩 볼륨의 교차 영역에서 추출된 샘플포인트를 이용하여 표현되기 때문에 샘플 포인트의 정확도에 따라 충돌탐지 결과가 달라진다.
그러나 음함수 곡면를 표현하기 위해 사용되는 필드함수와 같이 특별한 형태를 갖는 함수의 연관성을 이용하면 물체와 물체의 충돌탐지를 좀더 쉽게 계산 할 수 있다. 따라서 본 논문에서는 메타볼(metaball)을 표현하기 위한 6차 필드함수를 이용하여 서로 인접한 볼들과의 충돌탐지를 정형화된 함수로 표현할 수 있음을 보여 준다.
일반적으로 물체의 변형은 물체를 구성하는 점들의 위치(postion)를 이동하여 새로운 점들로 물체를 표현한다. 이때 물리적 현상을 반영하기 위해 물체의 이동을 속도와 힘을 이용한다. 음함수 곡면으로 표현된 물체가 서로 충돌했을 때 변형은 충돌 때 상호간에 가해진 힘에 의해 표현된다. 따라서 변형은 두 물체가 서로 영향을 미치는 영역을 변형구간으로 선택하게 되는데 변형구간의 선택과 변형을 표현하는 함수에 따라 변형의 모양이 결정된다.
그러나 음함수 곡면은 중심에서 감소하는 필드함수로 표현되는데 이 함수를 이용하여 변형을 표현할 수 있다. 본 논문에서는 변형 구간을 메타볼의 필드함수를 이용하여 필드값의 영향력이 미치는 구간을 변형구간으로 표현한다. 또한 필드값의 영향력을 이용하여 변형 모양을 거리에 관한 함수로 표현하여 정형화된 형태의 변형함수를 제시한다. 제안된 변형은 메타볼의 필드함수를 사용하기 때문에 변형을 표현하기 위해 임의의 함수를 선택할 필요가 없다. 그리고 메타볼의 영향력을 사용하여 좀 더 쉬운 충돌탐지를 계산할 수 있다.
메타볼의 필드 참의 영향력을 이용하여 생성된 충돌탐지와 변형함수는 새로운 변수(factor)를 사용하지 않고 필드함수만으로 충돌과 변형을 표현할 수 있다. 또한 물질의 재질에 따라 물체의 변형을 표현하였다. 이때의 변형도 마찬가지로 주어진 함수를 이용할 수 있다. 논문에서는 이러한 방법을 사용하여 표현되는 물체의 변형을 이미지로 생성하여 포함하였다.

다국어 초록 (Multilingual Abstract)

Collision detection and deformation is necessary in animations. In graphics, we use polygon primitives or implicit surfaces to represent an object. When an object is represented as polygons, collision detection has large computational complexity. This is caused by being computed as polygon culling problems in the culling region of a bounding volume. On the other hand, the collision detection of an object represented by implicit surfaces is easily appied to a relatively complicated multi-body.
However, the previous collision detection of implicit surfaces such as spheres or deformable superqudrics was represented using inside/outside functions. In this method, it is represented using the sample points extracted in the culling region of a bounding volume, so the results of collision detection vary according to the accuracy of sample points.
We can compute an object and its collision detection more easily, if we use relationships between special-formed functions such as field functions used to represent implicit surface. Therefore, in this thesis, we present that we can represent collision detection between abutted metaballs as formalized functions by using six-degree field functions to represent metaballs.
In general, deformation of an object is accomplished by moving points comprised by an object and representing an object with newly-made points. To consider physical phenomena, we use the moving speed of an object and its applied force. When objects represented as implicit surfaces crash each other, deformation is represented as the force which is applied to both objects while crashing. Therefore, deformation selects the area, which two objects influence each other, as a deformation range and so the shape of deformation depends on both the selection of a deformation depends on both the selection of a deformation range and the function which represent deformation.
Implicit surfaces are represented as the function which decreases from center and we can represent deformation range as the range which field values influence by using field functions. Also, we present a formalized deformation function which represents the shape of deformation as the function related to distance by using the influence of field values. Proposed deformation does not have to select an arbitrary function to represent deformation because we use the field functions of metaballs. And, we can compute collision detection more easily by using the influence of metaballs.
The collision detection and deformation function generated by using the influence of field values of metaballs can represent collision and deformation not by using new factors but by using only field functions. Also, we represent the deformation of and object according to the quality of matters, At this time, we can use given functions for deformation, too.

목차 (Table of Contents)

• 그림 차례 = iii
• 이미지 차례 = iv
• 국문 초록 = v
• 1. 서론 = 1
• 1.1 연구배경 = 6
• 1.2 연구 내용 및 논문의 구성 = 8
• 2. 관련연구 = 11
• 2.1 메타볼과 필드함수 = 11
• 2.2 메타볼 모델링 = 20
• 2.3 메타볼 렌더링 = 22
• 2.4 충돌과 변형 모델 = 25
• 2.4.1 층돌 관련 연구 = 26
• 2.4.2 변형 관련 연구 = 28
• 3. 문제정의와 연구의 내용 = 36
• 3.1 문제정의 = 36
• 3.2 볼륨 체의 그래프 표현 = 40
• 4. 충돌 탐지 = 46
• 4.1 두 메타볼의 충돌 검사 = 47
• 4.2 세 메타볼의 충돌 검사 = 51
• 4.2.1 좌표변환 = 53
• 4.2.2 초기 값 결정 = 56
• 4.3 일반화된 메타볼 충돌 검사 = 62
• 5. 물체의 변형 = 65
• 5.1 두 메타볼의 변형 = 65
• 5.1.1 surface 교차 영역 변형 = 71
• 5.1.2 확장영역 변형 = 73
• 5.2 변형의 확장 = 81
• 6. 결론 = 91
• 참고 문헌 = 93