| 1 |
1
중앙처리장치(CPU)에서 다수의 스레드에 의해 병렬적으로 수행되는, 두개의 다각형 집합의 충돌을 검사하기 위한, 부하분산을 이용한 병렬형 충돌검사 방법에 있어서,상기 다각형 집합에 대한 경계볼륨 계층구조(BVH)를 이용하여, 경계볼륨 순회트리(BVTT)를 방문하는 단계;상기 BVTT를 방문할 때, 트리의 노드가 내부노드이고, 노드 안의 두 경계볼륨(BV)이 중첩된 경우에는, 재귀적으로 상기 내부노드(부모노드가 됨)의 자식노드를 방문하는 단계;상기 BVTT를 방문할 때, 트리의 상기 노드가 단말노드이고, 상기 단말노드 안에 있는 충돌단위가 중첩하는 경우에는, 상기 단말노드 안의 상기 충돌단위를 저장하는 단계; 및방문할 자식노드의 수를 예측하는 단계를 포함하는 병렬형 충돌검사 방법
|
| 2 |
2
제1항에 있어서, 상기 두개의 다각형 집합이 충돌하지 않는 경우에는, 해당 노드를 컬링하는 단계를 더 포함하는 병렬형 충돌검사 방법
|
| 3 |
3
제1항에 있어서, 방문할 자식노드의 수를 예측하는 단계는, 노드가 얼마나 깊게 중첩되어 있는지를 상기 BV의 침투깊이를 통하여 판단하는 것을 특징으로 하는 병렬형 충돌검사 방법
|
| 4 |
4
제3항에 있어서, 상기 BV의 넓이에 대한 침투깊이가 상대적으로 큰 경우에는, 방문할 자식노드가 많은 것으로 판단하여, 왼쪽 자식노드를 인큐하는 것을 특징으로 하는 병렬형 충돌검사 방법
|
| 5 |
5
제4항에 있어서, 상기 침투깊이의 상대적인 값은, 다음의 수학식을 이용하여 결정하는 것을 특징으로 하는 병렬형 충돌검사 방법
|
| 6 |
6
제4항 또는 제5항에 있어서, 상기 왼쪽 자식노드는, 상기 부모노드를 방문한 스레드 이외의 스레드가 방문하는 것을 특징으로 하는 병렬형 충돌검사 방법
|
| 7 |
7
제6항에 있어서, 상기 부모노드를 방문한 스레드는, 오른쪽 자식노드를 재귀적으로 방문하는 것을 특징으로 하는 병렬형 충돌검사 방법
|
| 8 |
8
CPU에서 다수의 스레드에 의해 병렬적으로 수행되는, 두개의 다각형 집합의 거리를 계산하기 위한, 부하분산을 이용한 병렬형 거리계산 방법에 있어서,상기 다각형 집합에 대한 BVH를 이용하여, BVTT를 방문하는 단계;상기 BVTT를 방문할 때, 트리의 노드가 내부노드인 경우, 노드 안의 두 BV의 유클리디언 최단거리를 계산하여 소정의 상한보다 작은 경우, 재귀적으로 상기 내부노드(부모노드가 됨)의 자식노드를 방문하는 단계; 상기 BVTT를 방문할 때, 트리의 노드가 단말노드인 경우, 상기 단말노드 안에 있는 모델간의 거리를 계산하고, 계산된 거리가 상기 소정의 상한보다 작은 경우에는, 상기 소정의 상한을 계산된 거리로 갱신하는 단계; 및방문할 자식노드의 수를 예측하는 단계를 포함하는 병렬형 거리계산 방법
|
| 9 |
9
제8항에 있어서, 재귀적으로 방문할 자식노드의 수를 예측하는 단계는, 소정의 가중치를 준 (는 유클리디언 최단거리를 구하는 연산이고, A, B는 상기 두개의 다각형 집합임)의 추정치를 계산하여, 노드 의 유클리디언 최단거리인 가 상기 추정치보다 작으면, 노드 의 자식노드 중에 유클리디언 최단거리가 되는 것이 있다고 판단하여, 왼쪽 자식노드를 스택에 푸쉬하는 것을 특징으로 하는 병렬형 거리계산 방법
|
| 10 |
10
제9항에 있어서, 상기 추정치는, 다음 수학식을 이용하여 구하는 것을 특징으로 하는 병렬형 거리계산 방법
|
