http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
GPU상에서 동작하는 Ray Tracing을 위한 효과적인 k-D tree 탐색 알고리즘
강윤식,박우찬,서충원,양성봉,Kang, Yoon-Sig,Park, Woo-Chan,Seo, Choong-Won,Yang, Sung-Bong 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.3
This paper proposes an effective k-D tree traversal algorithm for ray tracing on a GPU. The previous k-D tree traverse algorithm based on GPU uses bottom-up searching from a leaf to the root after failing to find the ray intersected primitive in the leaf node. During the bottom-up search the algorithm decides the current node is visited or not from the parent node. In such a way, we need to visit the parent node which was already visited and the duplicated bounding box intersection tests. The new k-D tree traverse algorithm reduces the brother and parent duplicated visit by using an efficient method which decides whether the brother node is already visited or not during the bottom-up search. Also the algorithm take place bounding box intersection tests only for the nodes which is not yet done. As a result our experiment shows the new algorithm is about 30% faster than the previous. 본 논문은 GPU상에서 작동되는 ray tracing을 위한 효과적인 k-D tree 탐색 알고리즘을 제안한다. 기존의 k-D tree를 위한 GPU 기반 탐색 알고리즘은 임의의 단말노드에서 교차되는 primitive를 찾지 못한 경우. root 노드 방향으로 bottom-up 탐색하여 부모 노드에서 bounding box 교차검사를 이용해 형제 노드의 기 방문 여부를 판단한다. 이러한 방법은 이미 방문한 부모 노드의 방문과 bounding box 교차검사를 중복적으로 수행한다. 본 논문에서 제안하는 알고리즘은 bottom-up 탐색을 수행 할 때 형제노드가 이전에 방문했는지를 확인할 수 있는 효율적인 방법을 제시함으로써 형제노드 및 부모로드의 방문을 생략하도록 하고, 또한 아직 방문하지 않은 노드에 대해서만 bounding box 교차검사를 수행함으로써 중복된 연산을 피한다. 결과적으로 본 논문의 실험은 기존 알고리즘 대비 제안하는 알고리즘이 약 30%의 성능 향상이 있음을 보여 준다.
구역화를 이용한 디지털 격자지형데이터의 단순화 알고리즘
강윤식(Yoon Sig Kang),박우찬(Woo Chan Park),양성봉(Sung Bong Yang) 한국정보처리학회 2000 정보처리학회논문지 Vol.7 No.3
In this paper we introduce a fast simplification algorithm for terrain height fields to produce a triangulated irregular network, based on the greedy insertion algorithm in [1, 4, 5]. Our algorithm partitions a terrain height data into rectangular blocks with the same size and simplifies blocks one by one with the greedy insertion algorithm. Our algorithm references only to the points and the triangles within each current block for adding a point into the triangulation. Therefore, the algorithm runs faster than the greedy insertion algorithm, which references all input points and triangles in the terrain. Our experiment shows that partitioning method runs from 4 to more than 20 times faster, and it approximates test height fields as accurately as the greedy insertion algorithms. Most greedy insertion algorithms suffer from elongated triangles that usually appear near the boundaries. However, we insert the four corner points into each block to produce the base triangulation of the block before the point addition step begins so that elongated triangles could not appear in the simplified terrain.
구역화를 이용한 3차원 격자 데이터의 리파인먼트 단순화
강윤식(Yoon-Sig Kang),양성봉(Sung-Bong Yang) 한국정보과학회 1999 한국정보과학회 학술발표논문집 Vol.26 No.1B
본 논문에서는 grid 형태의 height data의 지형을 greedy insertion algorithm을 이용하여 TIN(Triangulated Irregular Network)의 단순화된 지형정보를 생성해 내는 향상된 알고리즘을 제시한다. greedy insertion algorithm[1]은 전체 terrain을 포함할 수 있는 2개의 base triangle을 생성한 후 maximal local 또는 global error를 갖고 있는 point를 원하는 수의 point또는 threshold에 도달할 때까지 반복적으로 추가하는 방법을 통하여 원하는 resolution의 terrain triangulation을 얻어내고 있다. 이와 같은 greedy insertion algorithm을 소개하고 있는 최근의 논문 중 가장 빠른 수행 성능을 보이고 있는 알고리즘의 경우 전체 n개의 point로 이루어진 grid data로부터 m개의 point를 가지고 있는 triangulation을 생성해 내는데 평균 O((m+n)logm)의 수행 시간이 소요되고 있으나[2], 본 논문에서는 terrain data를 가로 k x 세러 l 개의 sub-block으로 partitioning을 한 후 각 sub-block단위로 greedy insertion algorithm을 적용시켜 simplification을 행함으로 평균 O((m+n)log m+n/k×l)의 수행 성능의 향상과 enlonged triangle들의 억제효과를 보여주고 있다.
GPU상에서 동작하는 Ray Tracing을 위한 효과적인 k-D tree 탐색 알고리즘
강윤식(Yoon-Sig Kang),박우찬(Woo-Chan Park),서충원(Choong-Won Seo),양성봉(Sung-Bong Yang) 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.3·4
본 논문은 GPU상에서 작동되는 ray tracing을 위한 효과적인 k-D tree 탐색 알고리즘을 제안한다. 기존의 k-D tree를 위한 GPU 기반 탐색 알고리즘은 임의의 단말노드에서 교차되는 primitive를 찾지 못한 경우, root 노드 방향으로 bottom-up 탐색하여 부모 노드에서 bounding box 교차검사를 이용해 형제 노드의 기 방문 여부를 판단한다. 이러한 방법은 이미 방문한 부모 노드의 방문과 bounding box 교차검사를 중복적으로 수행한다. 본 논문에서 제안하는 알고리즘은 bottom-up 탐색을 수행 할 때 형제노드가 이전에 방문했는지를 확인할 수 있는 효율적인 방법을 제시함으로써 형제노드 및 부모노드의 방문을 생략하도록 하고, 또한 아직 방문하지 않은 노드에 대해서만 bounding box 교차검사를 수행함으로써 중복된 연산을 피한다. 결과적으로 본 논문의 실험은 기존 알고리즘 대비 제안하는 알고리즘이 약 30%의 성능 향상이 있음을 보여 준다. This paper proposes an effective k-D tree traversal algorithm for ray tracing on a GPU. The previous k-D tree traverse algorithm based on GPU uses bottom-up searching from a leaf to the root after failing to find the ray intersected primitive in the leaf node. During the bottom-up search the algorithm decides the current node is visited or not from the parent node. In such a way, we need to visit the parent node which was already visited and the duplicated bounding box intersection tests. The new k-D tree traverse algorithm reduces the brother and parent duplicated visit by using an efficient method which decides whether the brother node is already visited or not during the bottom-up search. Also the algorithm take place bounding box intersection tests only for the nodes which is not yet done. As a result our experiment shows the new algorithm is about 30% faster than the previous.