Sturm sequence를 이용한 메타볼 렌더링에 관한 연구 = (A) study on rendering of metaball using sturm sequence

국문 초록 (Abstract)

모델링 분야에서 물체를 표현하는 방법은 여러 가지가 있다. 메타볼 모델은 적은 양의 데이터로 물체를 잘 표현할 수 있는 장점을 가지고 있어 복잡한 곡면을 모델링하는데 있어 널리 사용된다. 메타볼의 모델링 성능은 필드함수에 의해 좌우되는데, 자연스러운 연결 형태를 표현하려면 고차 다항식의 필드함수를 사용하여야 한다. 그러나 5차 이상의 고차 다항식은 광선과 isosurface와의 교차검사에 있어서 분석적 방법을 쓸 수 없기 때문에, 정확하면서도 견고한 교차검사 방법을 필요로 한다.
본 논문에서는 물방울의 연결 형태와 같이 매우 자연스러워야 하는 물체를 표현하는데 좋은 성능을 갖는 6차의 다항식의 필드함수를 소개하고, 이 필드함수에 대해 Sturm sequence를 이용하여 교차 검사를 하는 방법을 제안한다. Sturm sequence 방법은 함수의 나눗셈과 evaluation을 포함하므로, 계산 오차는 필드함수의 계수들에 민감해진다. 대부분의 함수들이 ill-conditioned이므로 다항식의 모양을 안정화시키는 방법이 필요하다[4]. 본 논문에서는 이러한 필드함수의 모양을 안정화시키는 방법을 제안한다. 그리고 구간 내에서의 Min-Max test를 적용하여 광선추적알고리즘을 가속화시키는 방법도 소개한다. 이 방법을 이용하면 근이 존재하지 않는 구간을 빠르게 판별함으로써 광선과 isosurface사이의 교차 판별을 위한 불필요한 계산을 줄여 속도를 가속화시킬 수 있다.

다국어 초록 (Multilingual Abstract)

There are many methods of representing objects in the field of modeling. Metaball model is useful for modeling of complicated surfaces because it can well represent objects with a few. The modeling capability of metaballs depends on the field function, and the higher degree of functions can expect the smoother surfaces. However, the intersection between the ray and isosurfaces can't be solved analytically for the degree five or more polynomials. Therefore it is required the precise and robust method for the intersection test of ray/isosurface.
In this paper, it is introduced the field function, the degree six polynomial that is suitable for representing the smooth surfaces, and proposed the method of ray/isosurface intersection test using Sturm sequence. The polynomials representing isosurface are frequently ill-conditioned to be adapted by Sturm sequence. This paper propose the method for generalizing the shape of polynomials, and apply the Min-Max test to raytracing algorithm for accelerating the speed. By employing Sturm sequence method and Min-Max test, ray/isosurface intersection can be solved very fast and precisely.

목차 (Table of Contents)

• 초록
• 1. 서론 = 1
• 2. 메타볼 모델 = 3
• 2.1 메타볼의 정의 = 3
• 2.2 Field Function = 5
• 2.2.1 기존의 필드함수들 = 5
• 2.2.2 제안 필드 함수 = 7
• 3. 메타볼의 렌더링 방법 = 12
• 3.1 기존의 방법들 = 14
• 3.2 Sturm Theorem = 15
• 3.3 Sturm sequence를 이용한 렌더링 방법 = 17
• 4. Min-Max test를 이용한 광선 추적의 가속화 = 22
• 5. 실험 결과 = 26
• 5.1 필드함수의 성능 비교 = 26
• 5.2 렌더링 알고리즘의 성능 비교 = 28
• 6. 결론 = 31
• 참고 문헌
• 영문 초록