GPU상에서 동작하는 Ray Tracing을 위한 효과적인 k-D tree 탐색 알고리즘

강윤식,박우찬,서충원,양성봉 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol. No.

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%의 성능 향상이 있음을 보여 준다.

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.

센서 네트워크에서 스트림 데이터 질의의 효율적인 처리를 위한 다중 질의 색인 기법

이민수(Lee Minsoo),김연정(Kim Yearn Jeong),윤혜정(Yoon Hyejung) 한국멀티미디어학회 2007 멀티미디어학회논문지 Vol.10 No.11

센서 네트워크는 스스로 감지하고 계산하고 무선으로 서로 통신할 수 있는 기능을 갖춘 센서들로 이루어진 네트워크이다. 센서 네트워크의 특정들로는 네트워크가 자체적으로 관리가 되어야 한다는 것과 배터리 전원이여서 전력의 효율성을 크게 고려해야 한다는 것이 있다. 센서 네트워크에서 생성되는 많은 양의 연속적인 데이터에 대하여 여러 개의 질의들을 동시에 처리해야 하는 경우에 전력의 효율성을 극대화시켜야 한다. 본 연구에서는 센서 네트워크에서 감시 목적의 미리 정의된 다중 질의들에 대해 색인을 두어 다중 질의 처리 성능을 높이고 메모리와 전력을 효율적으로 사용할 수 있는 기법을 제안한다. 공간 색인 기법 중에서 이진 탐색트리에 기반한 데이터 구조로서 각 레벨별로 차원이 반복되어 각 차원을 분할시키는 k-d 트리와, 공간을 계층적 구조로 자르며 겹침 관계를 줄인 R-트리의 변형인 R+-트리를 기반으로 하여 이들의 응용 및 융합을 통해 다중 질의를 색인하는 새로운 트리인 SMILE 트리를 제안한다. 질의들에 대한 SMILE 트리를 구성하여 센서 네트워크에서 생성되는 스트림 데이터에 대하여 관련된 질의를 탐색하도록 하면 질의를 순차 탐색하는 것과 비교하여 경우에 따라서는 평균 탐색시간을 약 50% 정도로 줄일 수 있다. A sensor network consists of a network of sensors that can perform computation and also communicate with each other through wireless communication. Some important characteristics of sensor networks are that the network should be self administered and the power efficiency should be greatly considered due to the fact that it uses battery power. In sensor networks, when large amounts of various stream data is produced and multiple queries need to be processed simultaneously, the power efficiency should be maximized. This work proposes a technique to create an index on multiple monitoring queries so that the multi-query processing performance could be increased and the memory and power could be efficiently used. The proposed SMILE tree modifies and combines the ideas of spatial indexing techniques such as k-d trees and R+-trees. The k-d tree can divide the dimensions at each level, while the R+-tree improves the R-tree by dividing the space into a hierarchical manner and reduces the overlapping areas. By applying the SMILE tree on multiple queries and using it on stream data in sensor networks, the response time for finding an indexed query takes in some cases 50% of the time taken for a Linear search to find the query.

GPU를 이용한 대량 삼각형 교차 알고리즘

경민호,곽종근,최정주 (사)한국컴퓨터그래픽스학회 2011 컴퓨터그래픽스학회논문지 Vol.17 No.3

Computing triangle-triangle intersections has been a fundamental task required for many 3D geometric problems. We propose a novel robust GPU algorithm to efficiently compute intersections in a large triangle set. The algorithm has three stages:k-d tree construction, triangle pair generation, and exact intersection computation. All three stages are executed on GPU except, for unsafe triangle pairs. Unsafe triangle pairs are robustly handled by CLP(controlled linear perturbation) on a CPU thread. They are identified by floating-point filtering while exact intersection is computed on GPU. Many triangles crossing a split plane are duplicated in k-d tree construction, which form a lot of redundant triangle pairs later. To eliminate them efficiently, we use a split index which can determine redundancy of a pair by a simple bitwise operation. We applied the proposed algorithm to computing 3D Minkowski sum boundaries to verify its efficiency and robustness. 삼각형간의 교차 계산은 많은 3차원 기하 문제들을 해결하는데 있어서 기본적으로 요구되는 연산 과정이다. 본 논문에서는 대량의 삼각형 집합 안에서의 교차 계산을 효율적이며 강인하게 처리할 수 있는 GPU 알고리즘을 제안한다. 이알고리즘은 k-d 트리의 구성, 삼각형쌍 생성, 정확한 교차 계산을 모두 GPU에서 처리한다. 여기서 사용되는 k-d 트리에서는 분할 과정 중에 삼각형들의 복사가 많이 발생한다. 이렇게 복사된 삼각형들로 인하여 중복된 삼각형쌍들이 많이생성되는데,이러한중복삼각형쌍들을효율적으로제거하기위하여분할인덱스를도입하였다.분할인덱스는간단한논리곱연산만으로중복여부를효과적으로판단할수있다.수치적강인성을높이기위하여는부동소숫점필터링을통해불안전한삼각형쌍들을분리하고, CLP(controlled linear perturbation)를이용하여CPU쓰레드에서처리하도록하였다. 제안한 알고리즘은 기존의 민코스키합 알고리즘의 합삼각형 교차계산에 적용하여 효율성과강인성을입증하였다

Cloud-Enabled Data Center Organization using K-D Tree

Sandip Roy,Rajesh Bose,Tanaya Roy,Debabrata Sarddar 보안공학연구지원센터 2015 International Journal of Database Theory and Appli Vol.8 No.3

An efficient load balancing algorithm in the field of cloud computing is absolutely essential in order to have a cloud network with graceful performance satisfying user expectation. Inspite of the existence of handful lightly loaded data centers, numerous heavily overloaded data centers may lead to a performance degradation of overall cloud network. Proper workload distribution may improve the overall performance of the cloud system. Now a day’s eminent cloud division rules are highly demanding algorithm for distributing workloads among various cloud server nodes deployed in cloud-enabled data centers scattered over the geographical regions. For the researcher, cloud division rule and optimal cloud server node searching are the most demanding jobs in load balancing leading towards more efficient cloud network and improve users’ satisfaction. This paper presents an expeditious cloud division rule based on geographical location of the cloud-enabled data centers distributed over earth surface and builds a two-dimensional space partition k-d tree to partition them in order to search intended cloud server node efficiently. Our proposed organization scheme can be utilized for active monitoring load balancing algorithm to improve the resource utilization for high performance in present cloud computing environment.

고정밀지도기반 자율주행을 위한 실시간 동적 라이다 데이터 추출 알고리즘

이재민(Jaemin Lee),한헌수(Hernsoo Hahn),한영준(Youngjoon Han) 한국자동차공학회 2021 한국자동차공학회 부문종합 학술대회 Vol.2021 No.6

The real-time LiDAR data-based object detection and classification algorithm for local path planning of autonomous driving is a important technology for autonomous driving. In general, the time complexity of these algorithms increases explosively as the number of LiDAR points increases. This paper proposes an algorithm for extracting dynamic point cloud data by efficiently removing static point cloud data on high Definition point map from LiDAR point cloud data received in real time. First, the proposed algorithm extracts local point cloud data from its current location from a high definition point map. At the same time, point cloud data is obtained from LiDAR sensors. Second, voxel grid filtering is applied on each of the acquired point cloud data and then a K-D tree is built. Finally, after the filtered local point map data is set to the target cloud data and the filtered LiDAR point cloud data to the input cloud data, removes static points of the input cloud data using nearest neighbor search algorithm from the target cloud data. This paper has been validated by self-driving experiments using IPG CarMaker simulator, solving the problem of recognizing frequently occurring road areas on uphill or downhill as obstacle, and effectively detecting dynamic objects that affect autonomous driving such as cars and pedestrians. It is expected that the proposed algorithm can be applied to indoor and outdoor security systems as well as autonomous vehicle, robot, and drone fields that use LiDAR.

Efficient point cloud data processing in shipbuilding: Reformative component extraction method and registration method

Sun, Jingyu,Hiekata, Kazuo,Yamato, Hiroyuki,Nakagaki, Norito,Sugawara, Akiyoshi Society for Computational Design and Engineering 2014 Journal of computational design and engineering Vol.1 No.3

To survive in the current shipbuilding industry, it is of vital importance for shipyards to have the ship components' accuracy evaluated efficiently during most of the manufacturing steps. Evaluating components' accuracy by comparing each component's point cloud data scanned by laser scanners and the ship's design data formatted in CAD cannot be processed efficiently when (1) extract components from point cloud data include irregular obstacles endogenously, or when (2) registration of the two data sets have no clear direction setting. This paper presents reformative point cloud data processing methods to solve these problems. K-d tree construction of the point cloud data fastens a neighbor searching of each point. Region growing method performed on the neighbor points of the seed point extracts the continuous part of the component, while curved surface fitting and B-spline curved line fitting at the edge of the continuous part recognize the neighbor domains of the same component divided by obstacles' shadows. The ICP (Iterative Closest Point) algorithm conducts a registration of the two sets of data after the proper registration's direction is decided by principal component analysis. By experiments conducted at the shipyard, 200 curved shell plates are extracted from the scanned point cloud data, and registrations are conducted between them and the designed CAD data using the proposed methods for an accuracy evaluation. Results show that the methods proposed in this paper support the accuracy evaluation targeted point cloud data processing efficiently in practice.

Spatial and Temporal Patterns of Minke Whale Distributions off the East Coast of Korea

CHO, Ilhwan,HALPIN, Patrick N.,KIM, Zang Geun 한국수산자원학회 2003 한국수산자원학회지 Vol.6 No.-

Spatial and temporal patterns of minke whale distributions off the east coast of Korea in May and June were defined using a series of statistical analyses and Geographic Information System (GIS). Results from Ripley's K(d) defined that whales were clumped in both months. Results from partial Mantel teats showed that the distance from the shore and the water temperature were significantly related to the whale distributions after accounting for spatial autocorrelations and inter-correlations among explanatory variables. Potential habitat maps from Classification and Regression Tree (CART) and logistic regression models suggested that the potential habitats of minke whales were located over the continental shelves along the shores and moved north from Mar to June, assuming no behavioral difference due to environmental variability. The techniques described here can be directly replicated to ether marine species.

포인트 클라우드 데이터의 공간밀도 기반 고속 노이즈 제거 방법

임경모(Gyeongmo Lim),정민호(Minho Jeong),장의선(Euee S. Jang) 한국정보과학회 2017 한국정보과학회 학술발표논문집 Vol.2017 No.12

데이터 샘플링을 통한 각 기반 공간 분할 병렬 스카이라인 질의처리 기법

정재화 ( Jaehwa Chung ) 한국컴퓨터교육학회 2015 컴퓨터교육학회 논문지 Vol.18 No.5

상호 연관되는 복잡한 데이터 조건이 존재하는 환경에서 스카이라인 질의는 의사결정 시스템 등 폭넓은 애플리케이션 활용 가능성으로 다양한 분야에서 연구되어 왔다. 중앙집중식 환경에서 스카이라인 질의처리 기법이 초기에 제안되었으며 최근 대량의 다차원 데이터에 대해 데이터 공간을 분할하여 맵/리듀스 플랫폼 상에서 병렬적으로 처리하는 기법이 제안되었다. 그러나 현재까지의 기법이 비균등적 실행과 높은 중복 작업으로 효율성이 저하된다는 문제점을 배경으로 본 논문에서는 랜덤 샘플링을 통해 데이터 분포를 추정하여 비균등 분할 문제를 해결하고 각 기반의 데이터 공간을 분할하여 스카이라인 처리 과정에서 중복 작업을 최소화한 새로운 기법 MR-DEAP를 제안한다. 마지막으로 다양한 환경에서의 실험결과 제안된 기법이 다른 각 기반 분할과 그리드 분할 기법보다 우수한 것을 입증하였다. In the environment that the complex conditions need to be satisfied, skyline query have been applied to various field. To processing a skyline query in centralized scheme, several techniques have been suggested and recently map/reduce platform based approaches has been proposed which divides data space into multiple partitions for the vast volume of multidimensional data. However, the performances of these approaches are fluctuated due to the uneven data loading between servers and redundant tasks. Motivated by these issues, this paper suggests a novel technique called MR-DEAP which solves the uneven data loading using the random sampling. The experimental result gains the proposed MR-DEAP outperforms MR-Angular and MR-BNL scheme.