입력 삼차원(three dimensional; 3D) 모델에 대한 가속 구조를 생성하기 위한 영상 처리 장치에 있어서,상기 입력 3D 모델 내의 제1 공간을 복수 개의 서브 공간으로 분할하는 분할부;상기 복수 개의 서브 공간 중, 래이의 진행 경로를 포함할 확률이 더 높은 서브 공간을 상기 가속 구조 상에서 탐색 우선순위가 더 높은 자식 노드로 설정하는 판단부; 및상기 복수 개의 서브 공간 중 월드 좌표계(world coordinate system)에서 원점에 더 가까운 서브 공간과, 상기 래이의 진행 경로를 포함할 확률이 더 높은 것으로 판단된 서브 공간이 서로 동일한지의 여부를 식별하는 플래그 비트를 상기 우선순위가 더 높은 자식 노드에 추가하는 플래그 설정부를 포함하고,DFL(depth-first layout)에 기반하여 상기 탐색 우선순위가 더 높은 자식 노드 및 상기 자식 노드의 부모 노드는 메모리의 동일한 캐싱 블록 안에 배열되는, 영상 처리 장치.

제1항에 있어서,상기 판단부는,상기 복수 개의 서브 공간 중, SA(Surface Area)가 더 큰 공간 구조를, 상기 래이의 진행 경로를 포함할 확률이 더 높은 서브 공간으로 판단하는, 영상 처리 장치.

제1항에 있어서,상기 가속 구조는, kd-tree, BVH(Bounding Volume Hierarchy) 및 Grid 중 어느 하나의 데이터 구조(data structure)인, 영상 처리 장치.

제1항에 있어서,상기 우선 순위가 높은 자식 노드는 깊이 우선 트리 탐색(depth first tree traversal)에서 우선적으로 탐색되는 왼쪽 자식 노드(left child node)인, 영상 처리 장치.

삭제

제1항에 있어서,상기 분할부는,상기 제1 공간을 분할하기 위한 분할 축을 지정하고, 상기 분할 축을 따라 상기 제1 공간 내의 복수 개의 프리미티브를 정렬하여 적어도 하나의 분할면 후보를 설정하고, 상기 분할면 후보 중 SAH(surface area heuristic)에 기반한 그리디(Greedy) 알고리즘에 따라 분할면을 선정하여, 상기 분할면을 이용하여 상기 제1 공간을 상기 복수 개의 서브 공간으로 분할하는, 영상 처리 장치.

제1항에 있어서,상기 분할부는, 리프 노드 생성 조건이 만족될 때까지 상기 입력 3D 모델 내에 분할되지 않은 공간에 대해 상기 분할 과정을 회귀적으로(recursively) 반복하는, 영상 처리 장치.

제1항에 있어서,상기 생성된 가속 구조를 저장하는 메모리 및;상기 메모리에 저장된 가속 구조 중 적어도 일부를 이용하여 임의의 시점에서의 영상을 래이 트래이싱 기법에 의해 렌더링하는 래이 트래이서를 더 포함하는, 영상 처리 장치.

입력 삼차원(three dimensional; 3D) 모델에 대한 가속 구조를 생성하기 위한 영상 처리 방법에 있어서,상기 입력 3D 모델 내의 제1 공간을 복수 개의 서브 공간으로 분할하는 단계;상기 복수 개의 서브 공간 중, 래이의 진행 경로를 포함할 확률이 더 높은 서브 공간을 상기 가속 구조 상에서 탐색 우선순위가 더 높은 자식 노드로 설정하는 단계; 및상기 복수 개의 서브 공간 중 월드 좌표계(world coordinate system)에서 원점에 더 가까운 서브 공간과, 상기 래이의 진행 경로를 포함할 확률이 더 높은 것으로 판단된 서브 공간이 서로 동일한지의 여부를 식별하는 플래그 비트를 상기 우선순위가 더 높은 자식 노드에 추가하는 플래그 설정 단계를 포함하고,DFL(depth-first layout)에 기반하여 상기 탐색 우선순위가 더 높은 자식 노드 및 상기 자식 노드의 부모 노드는 메모리의 동일한 캐싱 블록 안에 배열되는, 영상 처리 방법.

제9항에 있어서,상기 탐색 우선순위가 더 높은 자식 노드를 설정하는 단계는,상기 복수 개의 서브 공간 중, SA(Surface Area)가 더 큰 공간 구조를, 상기 래이의 진행 경로를 포함할 확률이 더 높은 서브 공간으로 판단하는, 영상 처리 방법.

제9항에 있어서,상기 가속 구조는, kd-tree, BVH(Bounding Volume Hierarchy) 및 Grid 중 어느 하나의 데이터 구조(data structure)인, 영상 처리 방법.

제9항에 있어서,상기 우선 순위가 높은 자식 노드는 깊이 우선 트리 탐색(depth first tree traversal)에서 우선적으로 탐색되는 왼쪽 자식 노드(left child node)인, 영상 처리 방법.

삭제

제9항에 있어서,상기 분할하는 단계는,상기 제1 공간을 분할하기 위한 분할 축을 지정하는 단계;상기 분할 축을 따라 상기 제1 공간 내의 복수 개의 프리미티브를 정렬하여 적어도 하나의 분할면 후보를 설정하는 단계;상기 분할면 후보 중 SAH(surface area heuristic)에 기반한 그리디(Greedy) 알고리즘에 따라 분할면을 선정하는 단계; 및상기 분할면을 이용하여 상기 제1 공간을 상기 복수 개의 서브 공간으로 분할하는 단계를 포함하는, 영상 처리 방법.

제9항에 있어서,상기 분할하는 단계는, 리프 노드 생성 조건이 만족될 때까지 회귀적으로(recursively) 반복되는, 영상 처리 방법.

제9항에 있어서,상기 생성된 가속 구조를 메모리에 저장하는 단계 및;상기 메모리에 저장된 가속 구조 중 적어도 일부를 이용하여 임의의 시점에서의 영상을 래이 트래이싱 기법에 의해 렌더링하는 단계를 더 포함하는, 영상 처리 방법.

제9항 내지 제12항 및 제14항 내지 제16항 중 어느 한 항의 영상 처리 방법을 수행하는 프로그램을 수록한 컴퓨터 판독 가능 기록 매체.