公开(公告)号：KR100894136B1

公开(公告)日：2009-04-20

申请号：KR1020060083354

申请日：2006-08-31

Applicant: 세종대학교산학협력단

Inventor： 강윤식 ,  김상덕 ,  박우찬 ,  양성봉

IPC: G06F17/00 ,  G06T17/00

Abstract: 본 발명은 그래픽 처리 장치(GPU : Graphics Processing Unit)에서 동작되는 레이 트레이싱(Ray-Tracing)을 위한 논스택(Non-Stack) 방식의 케이디 트리(KD-Tree) 탐색 알고리즘에 관한 것으로서, 보다 자세하게는 그래픽 처리 장치에 적용되며, 이진 트리(Binary Tree)의 일종인 케이디 트리의 탐색 알고리즘에서 중복되어 방문하는 노드의 수를 줄여 탐색 알고리즘의 성능을 향상시킬 수 있는 광선 추적을 위한 비 스택 방식의 케이디 트리 탐색 알고리즘을 적용한 영상검출 장치 및 방법에 관한 것이다.
본 발명의 광선 추적을 위한 비 스택 방식의 케이디 트리 탐색 알고리즘을 적용한 영상검출 장치는 영상을 이진트리 형식으로 분할하고 최종 분할된 영역을 단말노드로 하고, 광선 추적을 이용하여 상기 영상에 포함된 물체를 검출하기 위한 케이디 트리 알고리즘을 포함하는 장치에 있어서, 영상에 투과할 광선을 생성하기 위한 광선생성부와 상기 이진트리의 단말노드 방향으로 이동하면서 상기 물체와 상기 광선이 교차하는 트라이앵글을 탐색하기 위한 하향탐색부와 상기 하향탐색부를 통해 탐색을 수행한 이후, 탐색되지 않은 내부노드를 검색하기 위한 상향탐색부 및 상기 하향탐색부에서 검출된 물체 교차점의 컬러를 계산하기 위한 쉐이딩/텍스쳐 매핑부로 이루어짐에 기술적 특징이 있다.
광선 추적, 케이디 트리, 스택, 영상검출

公开(公告)号：KR1020080020198A

公开(公告)日：2008-03-05

申请号：KR1020060083354

申请日：2006-08-31

Applicant: 세종대학교산학협력단

Inventor： 강윤식 ,  김상덕 ,  박우찬 ,  양성봉

IPC: G06F17/00 ,  G06T17/00

CPC classification number: G06F17/30802 ,  G06T9/40

Abstract: An image detection apparatus to which a non-stack type KD search algorithm is applied for tracing ray and a method thereof are provided to reduce time for detecting images by shortening overlapped search or calculation time. An image detection apparatus comprises a ray generator, a downward searching unit(130), an upward searching unit(140), and a shading/texture mapping unit(150). The ray generator generates ray to be projected to an image. The downward searching unit searches a triangle where the ray crosses an object while moving to a terminating node of a binary tree. The upward searching unit is for searching internal nodes not detected after the downward searching unit performs the search operation. The shading/texture mapping unit calculates a color of a crossed point in the object detected by the downward searching unit.

Abstract translation: 提供了一种用于跟踪射线应用非堆叠型KD搜索算法的图像检测装置及其方法，以通过缩短重叠搜索或计算时间来减少检测图像的时间。 图像检测装置包括射线发生器，向下搜索单元（130），向上搜索单元（140）和阴影/纹理映射单元（150）。 射线发生器产生投影到图像的光线。 向下搜索单元搜索射线在物体移动到二叉树的终止节点的同时穿过对象的三角形。 向上搜索单元用于在向下搜索单元执行搜索操作之后搜索未检测到的内部节点。 阴影/纹理映射单元计算由向下搜索单元检测的对象中的交叉点的颜色。