Signed Distance Fields (SDF)는 다양한 분야에서 사용되어 왔고 이제는 그 범위가 더 넓어지고 있다. 이러한 SDF를 계산하는 방법에 있어서 일반적인 GPU 기반 트리 탐색을 수행할 경우 병렬 처리 속도가 생각보다 크게 향상되지 않는 경우가 대부분이다. 본 논문에서는 Shifted ...
Signed Distance Fields (SDF)는 다양한 분야에서 사용되어 왔고 이제는 그 범위가 더 넓어지고 있다. 이러한 SDF를 계산하는 방법에 있어서 일반적인 GPU 기반 트리 탐색을 수행할 경우 병렬 처리 속도가 생각보다 크게 향상되지 않는 경우가 대부분이다. 본 논문에서는 Shifted sort알고리즘을 대안으로 제시하고 트리 탐색에서의 병렬 탐색 효율 저하는 GPU 병렬 처리 하드웨어 아키텍처 내 최소 물리적 스레드 실행 단위인 warp에서의 분기문(if, else 문)으로 인한 warp divergence가 일어나기 때문임을 제시한다. Shifted sort 알고리즘은 warp divergence가 상대적으로 적어 일반적인 트리 탐색에 비해 빠른 계산 속도를 보이지만 shifted sort 알고리즘은 아직 공간 탐색에 대한 연구가 진행되지 않아 kd-tree와 같은 일반적인 트리 탐색처럼 공간을 탐색하는 데 어려움이 있다. 따라서 주어진 메시의 최소단위 face인 삼각형의 중점을 shifted sort 알고리즘의 입력데이터로 사용하여 삼각형에 대한 고속 탐색 실험을 수행함으로써 shifted sort 알고리즘 방식의 SDF 계산 가능성 여부를 테스트하고자 한다. 이후 삼각형에 대한 입력 데이터를 중점, 꼭짓점, 삼각형 세 변의 중점까지 테스트 범위를 확장하고자 한다. Shifted sort 알고리즘을 이용한 SDF 구현은 정확성과 빠른 처리 속도 이 두 가지 특성을 가지고 그 성능을 증명한다. 정확성의 경우 3차원 샘플모델을 reduction SDF 방식과 shifted sort 알고리즘으로 구현한 SDF 방식 이 두 가지 알고리즘을 이용한 SDF의 결과를 비교하여 L2 norm 계산을 통해 두 결과의 오차의 크기에 대해 분석한다. Reduction SDF 방식은 하나의 쿼리와 모든 삼각형과의 거리를 계산한 후, 가장 최소의 거리를 가지고 있는 값을 가지고 거리장을 만든다. 이는 100%에 가까운 정확성을 가지고 있기 때문에 shifted sort 알고리즘으로 구현한 SDF의 결과와의 비교를 통해 제안하는 알고리즘으로 구현한 SDF의 값이 얼마만큼의 정확한 값을 가지는지 알 수 있다. [0, 0.75]3의 범위 내에서 최대로 나올 수 있는 결과와 제안하는 알고리즘으로 구현한 두 값의 비교 결과 모델에 따라 최소 0.0002%부터 최대 0.9%의 오차율을 가지며, 이는 최소 99.1%의 정확성을 가진다. 처리 시간의 경우, 100%의 정확성을 가지고 있는 reduction SDF를 크기가 같은 삼각형으로 이루어져 있는 geosphere 모델을 가지고 SDF를 구현하는데 15467ms가 소요되고, SDF 구현에 주로 사용되는 일반적인 트리 탐색 알고리즘인 kd-tree 탐색에서 SDF를 구현했을 경우 최대 처리시간이 707ms 걸린다. 반면, shifted sort 알고리즘을 이용하여 SDF를 구현한 경우 330ms로 kd-tree 탐색 알고리즘과는 약 2.3배의 시간 차이를 보인다. 이는 100%의 정확성을 가지고 있는 reduction SDF 방식의 최대 처리 시간인 15467ms보다는 약 46배 빠르다. 이후, visual profiler 분석을 통해 일반적인 트리 탐색 알고리즘인 kd-tree와 shifted sort 알고리즘과의 정확한 성능 비교를 제시한다.
Signed Distance Fields (SDF)는 다양한 분야에서 사용되어 왔고 이제는 그 범위가 더 넓어지고 있다. 이러한 SDF를 계산하는 방법에 있어서 일반적인 GPU 기반 트리 탐색을 수행할 경우 병렬 처리 속도가 생각보다 크게 향상되지 않는 경우가 대부분이다. 본 논문에서는 Shifted sort 알고리즘을 대안으로 제시하고 트리 탐색에서의 병렬 탐색 효율 저하는 GPU 병렬 처리 하드웨어 아키텍처 내 최소 물리적 스레드 실행 단위인 warp에서의 분기문(if, else 문)으로 인한 warp divergence가 일어나기 때문임을 제시한다. Shifted sort 알고리즘은 warp divergence가 상대적으로 적어 일반적인 트리 탐색에 비해 빠른 계산 속도를 보이지만 shifted sort 알고리즘은 아직 공간 탐색에 대한 연구가 진행되지 않아 kd-tree와 같은 일반적인 트리 탐색처럼 공간을 탐색하는 데 어려움이 있다. 따라서 주어진 메시의 최소단위 face인 삼각형의 중점을 shifted sort 알고리즘의 입력데이터로 사용하여 삼각형에 대한 고속 탐색 실험을 수행함으로써 shifted sort 알고리즘 방식의 SDF 계산 가능성 여부를 테스트하고자 한다. 이후 삼각형에 대한 입력 데이터를 중점, 꼭짓점, 삼각형 세 변의 중점까지 테스트 범위를 확장하고자 한다. Shifted sort 알고리즘을 이용한 SDF 구현은 정확성과 빠른 처리 속도 이 두 가지 특성을 가지고 그 성능을 증명한다. 정확성의 경우 3차원 샘플모델을 reduction SDF 방식과 shifted sort 알고리즘으로 구현한 SDF 방식 이 두 가지 알고리즘을 이용한 SDF의 결과를 비교하여 L2 norm 계산을 통해 두 결과의 오차의 크기에 대해 분석한다. Reduction SDF 방식은 하나의 쿼리와 모든 삼각형과의 거리를 계산한 후, 가장 최소의 거리를 가지고 있는 값을 가지고 거리장을 만든다. 이는 100%에 가까운 정확성을 가지고 있기 때문에 shifted sort 알고리즘으로 구현한 SDF의 결과와의 비교를 통해 제안하는 알고리즘으로 구현한 SDF의 값이 얼마만큼의 정확한 값을 가지는지 알 수 있다. [0, 0.75]3의 범위 내에서 최대로 나올 수 있는 결과와 제안하는 알고리즘으로 구현한 두 값의 비교 결과 모델에 따라 최소 0.0002%부터 최대 0.9%의 오차율을 가지며, 이는 최소 99.1%의 정확성을 가진다. 처리 시간의 경우, 100%의 정확성을 가지고 있는 reduction SDF를 크기가 같은 삼각형으로 이루어져 있는 geosphere 모델을 가지고 SDF를 구현하는데 15467ms가 소요되고, SDF 구현에 주로 사용되는 일반적인 트리 탐색 알고리즘인 kd-tree 탐색에서 SDF를 구현했을 경우 최대 처리시간이 707ms 걸린다. 반면, shifted sort 알고리즘을 이용하여 SDF를 구현한 경우 330ms로 kd-tree 탐색 알고리즘과는 약 2.3배의 시간 차이를 보인다. 이는 100%의 정확성을 가지고 있는 reduction SDF 방식의 최대 처리 시간인 15467ms보다는 약 46배 빠르다. 이후, visual profiler 분석을 통해 일반적인 트리 탐색 알고리즘인 kd-tree와 shifted sort 알고리즘과의 정확한 성능 비교를 제시한다.
Computer graphics fields that use Signed Distance Fields (SDF) are increasing. Parallel processing speed is not significantly improved when performing a general GPU-based tree search method to calculate SDF. In this paper, we propose an alternative shifted sort algorithm to show that parallel s...
Computer graphics fields that use Signed Distance Fields (SDF) are increasing. Parallel processing speed is not significantly improved when performing a general GPU-based tree search method to calculate SDF. In this paper, we propose an alternative shifted sort algorithm to show that parallel search efficiency degradation in tree search is caused by warp divergence due to branch statement (if statement) in warp, the minimum physical thread execution unit in GPU parallel processing hardware architecture. The shifted sort algorithm has a low warp divergence that is faster than a general tree search algorithm. However, it difficult to search a space like a normal tree search in a kd-tree because the shifted sort algorithm is not applicable to a spatial search. Therefore, we want to test calculating a SDF with a shifted sort method that performs a fast search experiment on the triangle using the center point of the triangle as the minimum unit face of the given mesh representing the input data of the shifted sort. We then extend the test range from the point of the triangle input data to the triangle midpoint and the vertices of the triangles. The shifted sort algorithm demonstrates its performance with accuracy and fast processing speed. In case of accuracy, the SDF method that implements the 3D sample model with the reduction SDF method and the shifted sort algorithm compares the results of the SDF using the two algorithms and analyzes the error magnitudes of the two results through L2 norm calculation. Reduction SDF method calculates the distance between one query and all triangles, and then produces a distance field with the smallest distance. Since this is close to 100% accuracy, we can see how accurate the value of SDF implemented by the proposed algorithm is by comparing with the result of SDF implemented with shifted sort algorithm. According to the comparison result of the two values implemented by the proposed algorithm, the error rate is at least 0.0002% up to 0.9%, which is at least 99.1% accurate. In the case of the processing time, SDF is implemented with a geosphere model consisting of a triangle of the same size. The reduction SDF takes 15467ms. When SDF is implemented in kd-tree search algorithm is 707ms. On the other hand, if the SDF is implemented using the shifted sort algorithm, it takes 330ms. This is about 46 times faster than the maximum processing time of the reduction SDF method of 15467ms and 2.3 times faster than the kd-tree SDF method. Then, we show the accurate performance comparison between the general tree search algorithm kd-tree and the shifted sort algorithm through visual profiler analysis.
Computer graphics fields that use Signed Distance Fields (SDF) are increasing. Parallel processing speed is not significantly improved when performing a general GPU-based tree search method to calculate SDF. In this paper, we propose an alternative shifted sort algorithm to show that parallel search efficiency degradation in tree search is caused by warp divergence due to branch statement (if statement) in warp, the minimum physical thread execution unit in GPU parallel processing hardware architecture. The shifted sort algorithm has a low warp divergence that is faster than a general tree search algorithm. However, it difficult to search a space like a normal tree search in a kd-tree because the shifted sort algorithm is not applicable to a spatial search. Therefore, we want to test calculating a SDF with a shifted sort method that performs a fast search experiment on the triangle using the center point of the triangle as the minimum unit face of the given mesh representing the input data of the shifted sort. We then extend the test range from the point of the triangle input data to the triangle midpoint and the vertices of the triangles. The shifted sort algorithm demonstrates its performance with accuracy and fast processing speed. In case of accuracy, the SDF method that implements the 3D sample model with the reduction SDF method and the shifted sort algorithm compares the results of the SDF using the two algorithms and analyzes the error magnitudes of the two results through L2 norm calculation. Reduction SDF method calculates the distance between one query and all triangles, and then produces a distance field with the smallest distance. Since this is close to 100% accuracy, we can see how accurate the value of SDF implemented by the proposed algorithm is by comparing with the result of SDF implemented with shifted sort algorithm. According to the comparison result of the two values implemented by the proposed algorithm, the error rate is at least 0.0002% up to 0.9%, which is at least 99.1% accurate. In the case of the processing time, SDF is implemented with a geosphere model consisting of a triangle of the same size. The reduction SDF takes 15467ms. When SDF is implemented in kd-tree search algorithm is 707ms. On the other hand, if the SDF is implemented using the shifted sort algorithm, it takes 330ms. This is about 46 times faster than the maximum processing time of the reduction SDF method of 15467ms and 2.3 times faster than the kd-tree SDF method. Then, we show the accurate performance comparison between the general tree search algorithm kd-tree and the shifted sort algorithm through visual profiler analysis.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.