| 1 |
1
폴리곤 모델에 대한 하우스도르프 거리 산출 방법에 있어서,
(a) 폴리곤 모델 와 가 주어질 때, 상기 에서 상기 로의 하우스도르프 거리 를 계산하는 단계로서,
(a1) 상기 내의 트라이앵글들 중 상기 에 기여하지 않는 트라이앵글들을 선별제거하는 단계;
(a2) 상기 내의 트라이앵글들 중, 상기 (a1) 단계의 수행 결과 남은 트라이앵글 에서 상기 로의 하우스도르프 거리 에 기여하지 않는 트라이앵글들을 선별제거하고, 그 결과 남은 트라이앵글을 기초로 상기 의 상위 바운드 및 하위 바운드를 업데이트하는 단계;
(a3) 상기 업데이트된 의 상위 바운드 및 하위 바운드를 기초로 의 상위 바운드 및 하위 바운드를 업데이트하는 단계; 및
(a4) 상기 (a1) 내지 (a3) 단계의 수행 결과 남은 트라이앵글 를 상기 의 상위 바운드와 하위 바운드의 차이가 소정 값 이하일 때까지 분할하는 단계를 포함하는 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 2 |
2
제1항에 있어서,
(b) 상기 에서 상기 로의 하우스도르프 거리 를 계산하는 단계; 및
(c) 상기 와 상기 의 최대값을 양방향(two-sided) 하우스도르프 거리 로 취하는 단계를 더 포함하는 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 3 |
3
제2항에 있어서,
상기 (b) 단계에서 하우스도르프 거리 를 계산함에 있어서,
상기 (a) 단계에서 계산된 를 의 하위 바운드의 초기값으로 하는 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 4 |
4
제2항에 있어서,
상기 (a1) 단계 및 상기 (a2) 단계의 수행 결과 남은 트라이앵글들 쌍들의 정보를 캐쉬하고, 상기 (b) 단계에서 하우스도르프 거리 를 계산함에 있어 상기 정보를 재사용하는 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 5 |
5
제1항에 있어서, 상기 (a1) 단계는,
상기 의 상위 바운드가 상기 의 하위 바운드보다 작게 되는 트라이앵글 를 상기 에 기여하지 않는 트라이앵글들로서 선별하여 제거하는 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 6 |
6
제1항에 있어서, 상기 (a1) 단계는,
트라이앵글들 의 집합을 둘러싸는 바운딩 볼륨에서 상기 내의 어떤 포인트로의 하우스도르프 거리가 상기 의 하위 바운드보다 작게 되는 바운딩 볼륨에 포함되는 트라이앵글들 를 상기 에 기여하지 않는 트라이앵글들로서 선별하여 제거하는 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 7 |
7
제6항에 있어서,
상기 바운딩 볼륨은 SSV(swept sphere volume)인 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 8 |
8
제1항에 있어서,
상기 (a2) 단계에서 상기 의 상위 바운드는 다음 수학식과 같이 정의되는 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 9 |
9
제8항에 있어서,
상기 내에서 상기 에 가장 가까운 트라이앵글 를 찾기 위하여 상기 내의 트라이앵글들을 파티션하여 클러스터하고 각 클러스터를 바운딩 볼륨으로 둘러싼 뒤, 와 클러스터된 바운딩 볼륨 간에 최단 거리 질의를 수행하는 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 10 |
10
제1항에 있어서, 상기 (a4) 단계는,
상기 트라이앵글 를 복수 개의 서브-트라이앵글로 분할하고, 상기 서브-트라이앵글에 대하여 상기 (a1) 내지 (a3) 단계를 반복하여 수행하는 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 11 |
11
제10항에 있어서,
상기 트라이앵글 를 복수 개의 서브-트라이앵글로 분할함에 있어서, 상기 트라이앵글 의 에지를 따라 바깥쪽의 서브-트라이앵글들 및 안쪽의 서브-트라이앵글 로 분할하는 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 12 |
12
제11항에 있어서, 상기 (a4) 단계는,
(a41) 상기 의 상위 바운드에 대하여, ≤을 만족하는 상기 내의 트라이앵글들의 집합 을 찾는 단계-여기서, 는 상기 의 상위 바운드를 나타내고, 는 상기 내의 트라이앵글을 나타내며, 는 유클리디안 거리 연산자를 나타냄;
(a42) 상기 트라이앵글 를 상기 에지를 따라 상기 서브-트라이앵글들 및 로 분할하는 단계;
(a43) 상기 집합 을 사용하여 에서 상기 로의 하우스도르프 거리의 상위 바운드 및 하위 바운드를 계산하는 단계; 및
(a44) 미리 정하여진 종료 조건을 만족할 때까지 상기 (a42) 단계 내지 (a43) 단계를 반복하는 단계를 포함하는 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 13 |
13
제12항에 있어서,
상기 (a42) 단계는,
상기 에지 상에 상기 의 버텍스들이 사영되는 상기 내의 트라이앵글과 동일한 트라이앵글에 사영되는 새로운 버텍스를 추가하고 상기 추가된 버텍스를 기준으로 상기 트라이앵글 를 분할하는 것을 특징으로 하는 하우스도르프 거리 산출 방법
|
| 14 |
14
제1항 내지 제13항 중 어느 한 항에 기재된, 폴리곤 모델에 대한 하우스도르프 거리 산출 방법을 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체
|
