1 |
1
트리의 탐색을 위해 쇼트 스택을 관리하는 처리부; 및상기 쇼트 스택의 데이터를 저장하는 저장부를 포함하고,상기 처리부는 상기 쇼트 스택이 빈 경우 상기 쇼트 스택을 채우기 위해 상기 트리의 루트 노드 및 상기 쇼트 스택에서 최후로 팝된 노드의 사이에 있는 중간 노드에서부터 상기 트리의 탐색의 재시작을 수행하고, 상기 중간 노드를 가리키는 링크를 상기 저장부 내에 저장함으로써 상기 중간 노드를 특정하고, 그리고 고정된 크기의 버퍼를 관리하고,상기 저장부는 상기 버퍼의 데이터를 저장하고, 그리고상기 버퍼는 상기 쇼트 스택을 저장하고, 상기 중간 노드를 가리키는 링크를 저장하는 전자 장치
|
2 |
2
제1항에 있어서,상기 트리는 분할된 공간이 중첩되는 가속 구조체인 전자 장치
|
3 |
3
제1항에 있어서,상기 트리는 바운딩 볼륨 하이어아키즈(Bounding Volume Hierarchies; BVH)인 전자 장치
|
4 |
4
삭제
|
5 |
5
제1항에 있어서,상기 처리부는 상기 쇼트 스택이 풀일 때 상기 링크를 상기 저장부 내에 저장하는 전자 장치
|
6 |
6
삭제
|
7 |
7
제1항에 있어서,상기 링크는 복수 개의 링크들에 포함되는 전자 장치
|
8 |
8
제7항에 있어서,상기 처리부는 상기 버퍼 중 상기 쇼트 스택을 저장하는 제1 영역의 크기 및 상기 복수 개의 링크들을 저장하는 제2 영역의 크기를 가변적으로 조정하는 전자 장치
|
9 |
9
제7항에 있어서,상기 처리부는 상기 트리의 탐색 중 푸쉬되는 노드들의 개수의 최대 값에 기반하여 상기 복수 개의 링크들의 개수를 결정하는 전자 장치
|
10 |
10
제7항에 있어서,상기 처리부는 상기 트리의 탐색 중 푸쉬되는 노드들의 개수의 최대 값 및 상기 쇼트 스택의 크기에 기반하여 상기 복수 개의 링크들의 개수를 결정하는 전자 장치
|
11 |
11
전자 장치가 쇼트 스택을 사용하여 트리를 순회하는 방법에 있어서,처리부에 의한, 상기 쇼트 스택으로부터 노드를 팝하는 단계; 및상기 처리부에 의한, 상기 트리가 빈 경우 상기 트리의 루트 노드 및 상기 쇼트 스택에서 최후로 팝된 노드의 사이에 있는 중간 노드로부터 상기 쇼트 스택을 채우기 위한 상기 트리의 탐색을 재시작하는 단계; 및상기 처리부에 의한, 고정된 크기의 버퍼를 관리하는 단계를 포함하되,상기 중간 노드는 상기 전자 장치의 저장부 내에 저장된 링크에 의해 특정되고,상기 버퍼의 데이터는 상기 전자 장치의 저장부 내에 저장되고, 그리고상기 쇼트 스택 및 상기 중간 노드를 가리키는 링크는 상기 버퍼 내에 저장되는 트리를 순회하는 방법
|
12 |
12
삭제
|
13 |
13
삭제
|
14 |
14
삭제
|
15 |
15
삭제
|
16 |
16
삭제
|
17 |
17
삭제
|
18 |
18
삭제
|
19 |
19
삭제
|
20 |
20
제11항의 방법을 수행하는 프로그램을 수록한 컴퓨터 판독 가능 기록 매체
|