Search

Efficient collision detection is critical in 3D geometric modeling. In this paper, we first implement three parallel triangle-triangle intersection algorithms on a GPU and then compare the computational efficiency of these three GPU-accelerated parallel triangle-triangle intersection algorithms in an application that detects collisions between triangulated models. The presented GPU-based parallel collision detection method for triangulated models has two stages: first, we propose a straightforward and efficient parallel approach to reduce the number of potentially intersecting triangle pairs based on AABBs, and second, we conduct intersection tests with the remaining triangle pairs in parallel based on three triangle-triangle intersection algorithms, i.e., the Möller's algorithm, Devillers' and Guigue's algorithm, and Shen's algorithm. To evaluate the performance of the presented GPU-based parallel collision detection method for triangulated models, we conduct four groups of benchmarks. The experimental results show the following: (1) the time required to detect collisions for the triangulated model consisting of approximately 1.5 billion triangle pairs is less than 0.5 s; (2) the GPU-based parallel collision detection method speedup over the corresponding serial version is 50x - 60x, and (3) Devillers' and Guigue's algorithm is comparatively and comprehensively the best of the three GPU-based parallel triangle-triangle intersection algorithms. The presented GPU-accelerated method is capable of efficiently detecting the potential collisions of triangulated models. Overall, the GPU-accelerated parallel Devillers' and Guigue's triangle-triangle intersection algorithm is recommended when performing practical collision detections between large triangulated models. [ABSTRACT FROM AUTHOR]

Spatial interpolations are commonly used in geometric modelling in life science applications such as medical image processing. In large-scale spatial interpolations, it is always needed to find a local set of data points for each interpolated point using the k Nearest Neighbor (kNN) search. To improve the efficiency of kNN, the uniform grid is commonly employed to fastly locate neighbours, and the size of grid cell could strongly affect the efficiency of kNN search. In this paper, we evaluate effects of the size of uniform grid cell on the efficiency of kNN search which is implemented on the CPU and GPU. We employ the Standard Deviation of points' coordinates to measure the spatial distribution of scattered points. For irregularly distributed scattered points, we perform several series of kNN search in two- and three-dimensions. Benchmark results indicate that: for both the sequential version implemented on the CPU and the parallel version implemented on the GPU, with the increase of the Standard Deviation of points' coordinates, the relatively optimal size of the grid cell decreases and eventually converges. Moreover, relationships between the Standard Deviation of scattered points' coordinates and the relatively optimal size of grid cell are fitted. [ABSTRACT FROM AUTHOR]

Mesh quality is a critical issue in numerical computing because it directly impacts both computational efficiency and accuracy. Tetrahedral meshes are widely used in various engineering and science applications. However, in large-scale and complicated application scenarios, there are a large number of tetrahedrons, and in this case, the improvement of mesh quality is computationally expensive. Laplacian mesh smoothing is a simple mesh optimization method that improves mesh quality by changing the locations of nodes. In this paper, by exploiting the parallelism features of the modern graphics processing unit (GPU), we specifically designed a parallel adaptive Laplacian smoothing algorithm for improving the quality of large-scale tetrahedral meshes. In the proposed adaptive algorithm, we defined the aspect ratio as a metric to judge the mesh quality after each iteration to ensure that every smoothing improves the mesh quality. The adaptive algorithm avoids the shortcoming of the ordinary Laplacian algorithm to create potential invalid elements in the concave area. We conducted 5 groups of comparative experimental tests to evaluate the performance of the proposed parallel algorithm. The results demonstrated that the proposed adaptive algorithm is up to 23 times faster than the serial algorithms; and the accuracy of the tetrahedral mesh is satisfactorily improved after adaptive Laplacian mesh smoothing. Compared with the ordinary Laplacian algorithm, the proposed adaptive Laplacian algorithm is more applicable, and can effectively deal with those tetrahedrons with extremely poor quality. This indicates that the proposed parallel algorithm can be applied to improve the mesh quality in large-scale and complicated application scenarios. [ABSTRACT FROM AUTHOR]

Mesh-based numerical methods such as the Finite Element Method (FEM) and Finite Difference Method (FDM) are widely used in various fields of science and engineering. However, the shortcomings of mesh-based methods are becoming increasingly obvious mainly due to the distorted or broken elements when analyzing the problems of large deformation or crack propagation. To overcome the above problems, meshfree methods such as the Meshless Local Petrov–Galerkin (MLPG) and Radial Point Interpolation Method (RPIM) were proposed, which can eliminate or partially eliminate the difficulties triggered by mesh-dependence. In geotechnics, the numerical modeling of deformations and failures of soil and rock masses is one of the most important approaches to understand and prevent geohazards, such as landslides and ground subsidence. In this paper, a local RPIM-based meshfree software package GeoMFree 3D is specifically developed for analyzing the deformations and failures of soil and rock masses. To enhance the computing capability of GeoMFree 3D , (1) effective memory storage strategies are adopted to solve the memory requirement bottleneck; and (2) parallel computing strategies are utilized and heterogeneously implemented on multi-core CPU and many-core GPU to improve the computational efficiency. To demonstrate the performance of GeoMFree 3D , three simple verification examples and one application case are presented in this paper. The verification examples indicate that the computational accuracy and efficiency of the package GeoMFree 3D is acceptable. Furthermore, the application case indicates that GeoMFree 3D is capable of analyzing the displacements of complex rock slopes. GeoMFree 3D is currently under intensive development, plans for future work on the development of GeoMFree 3D are also introduced. [ABSTRACT FROM AUTHOR]

The Smoothed Finite Element Method (S-FEM) proposed by Liu G.R. can achieve more accurate results than the conventional FEM. Currently, much commercial software and many open-source packages have been developed to analyze various science and engineering problems using the FEM. However, there is little work focusing on designing and developing software or packages for the S-FEM. In this paper, we design and implement an open-source package of the parallel S-FEM for elastic problems by utilizing the Julia language on multi-core CPU. The Julia language is a fast, easy-to-use, and open-source programming language that was originally designed for high-performance computing. We term our package as juSFEM. To the best of the authors' knowledge, juSFEM is the first package of parallel S-FEM developed with the Julia language. To verify the correctness and evaluate the efficiency of juSFEM, two groups of benchmark tests are conducted. The benchmark results show that (1) juSFEM can achieve accurate results when compared to commercial FEM software ABAQUS, and (2) juSFEM only requires 543 s to calculate the displacements of a 3D elastic cantilever beam model which is composed of approximately 2 million tetrahedral elements, while in contrast the commercial FEM software needs 930 s for the same calculation model; (3) the parallel juSFEM executed on the 24-core CPU is approximately 20 × faster than the corresponding serial version. Moreover, the structure and function of juSFEM are easily modularized, and the code in juSFEM is clear and readable, which is convenient for further development. [ABSTRACT FROM AUTHOR]

Summary: An effective strategy for accelerating the calculation of convex hulls is to filter the input points by discarding interior points. In this paper, we present such a straightforward preprocessing approach by discarding the points locating in a convex polygon formed by 16 extreme points. Extreme points of a planar point set do not alter when all points are rotated with the same angle in the plane. Four groups of four extreme points with min or max x or y coordinates can be found for the original point set and three rotated point sets. These 16 extreme points are used to form a planar convex polygon. We discard those points locating in the convex polygon and calculate the desired convex hull of the remaining points. The proposed preprocessing algorithm is evaluated on two computational platforms. Experiments show that, when employing the proposed preprocessing algorithm on the computational platform 1, it achieves speedups of approximately 4 ×∼5× on average and 5 ×∼6× in the best cases over the cases where the proposed approach is not used, while on the computational platform 2, the speedups are approximately 6 ×∼9× on average and 9 ×∼14× in the best cases. Moreover, more than 99% input points can be discarded in most cases. [ABSTRACT FROM AUTHOR]

In numerical modeling, mesh quality is one of the decisive factors that strongly affects the accuracy of calculations and the convergence of iterations. To improve mesh quality, the Laplacian mesh smoothing method, which repositions nodes to the barycenter of adjacent nodes without changing the mesh topology, has been widely used. However, smoothing a large-scale three dimensional mesh is quite computationally expensive, and few studies have focused on accelerating the Laplacian mesh smoothing method by utilizing the graphics processing unit (GPU). This paper presents a GPU-accelerated parallel algorithm for Laplacian smoothing in three dimensions by considering the influence of different data layouts and iteration forms. To evaluate the efficiency of the GPU implementation, the parallel solution is compared with the original serial solution. Experimental results show that our parallel implementation is up to 46 times faster than the serial version. [ABSTRACT FROM AUTHOR]

This paper focuses on evaluating the computational performance of parallel spatial interpolation with Radial Basis Functions (RBFs) that is developed by utilizing modern GPUs. The RBFs can be used in spatial interpolation to build explicit surfaces such as Discrete Elevation Models. When interpolating with large-size of data points and interpolated points for building explicit surfaces, the computational cost would be quite expensive. To improve the computational efficiency, we specifically develop a parallel RBF spatial interpolation algorithm on many-core GPUs, and compare it with the parallel version implemented on multi-core CPUs. Five groups of experimental tests are conducted on two machines to evaluate the computational efficiency of the presented GPU-accelerated RBF spatial interpolation algorithm. Experimental results indicate that: in most cases, the parallel RBF interpolation algorithm on many-core GPUs does not have any significant advantages over the parallel version on multi-core CPUs in terms of computational efficiency. This unsatisfied performance of the GPU-accelerated RBF interpolation algorithm is due to: (1) the limited size of global memory residing on the GPU, and (2) the need to solve a system of linear equations in each GPU thread to calculate the weights and prediction value of each interpolated point. [ABSTRACT FROM AUTHOR]

Mesh cleaning is the procedure of removing duplicate nodes, sequencing the indices of remaining nodes, and then updating the mesh connectivity for a topologically invalid Finite Element mesh. To the best of our knowledge, there has been no previously reported work specifically focused on the cleaning of large Finite Element meshes. In this paper we specifically present a generic and straightforward algorithm, MeshCleaner, for cleaning large Finite Element meshes. The presented mesh cleaning algorithm is composed of (1) the stage of compacting and reordering nodes and (2) the stage of updating mesh topology. The basic ideas for performing the above two stages efficiently both in sequential and in parallel are introduced. Furthermore, one serial and two parallel implementations of the algorithm MeshCleaner are developed on multi-core CPU and/or many-core GPU. To evaluate the performance of our algorithm, three groups of experimental tests are conducted. Experimental results indicate that the algorithm MeshCleaner is capable of cleaning large meshes very efficiently, both in sequential and in parallel. The presented mesh cleaning algorithm MeshCleaner is generic, simple, and practical. [ABSTRACT FROM AUTHOR]

This paper presents an efficient parallel Adaptive Inverse Distance Weighting (AIDW) interpolation algorithm on modern Graphics Processing Unit (GPU). The presented algorithm is an improvement of our previous GPU-accelerated AIDW algorithm by adopting fast k-nearest neighbors ( kNN) search. In AIDW, it needs to find several nearest neighboring data points for each interpolated point to adaptively determine the power parameter; and then the desired prediction value of the interpolated point is obtained by weighted interpolating using the power parameter. In this work, we develop a fast kNN search approach based on the space-partitioning data structure, even grid, to improve the previous GPU-accelerated AIDW algorithm. The improved algorithm is composed of the stages of kNN search and weighted interpolating. To evaluate the performance of the improved algorithm, we perform five groups of experimental tests. The experimental results indicate: (1) the improved algorithm can achieve a speedup of up to 1017 over the corresponding serial algorithm; (2) the improved algorithm is at least two times faster than our previous GPU-accelerated AIDW algorithm; and (3) the utilization of fast kNN search can significantly improve the computational efficiency of the entire GPU-accelerated AIDW algorithm. [ABSTRACT FROM AUTHOR]

This paper presents an alternative GPU-accelerated convex hull algorithm and a novel S orting-based P reprocessing A pproach (SPA) for planar point sets. The proposed convex hull algorithm termed as CudaChain consists of two stages: (1) two rounds of preprocessing performed on the GPU and (2) the finalization of calculating the expected convex hull on the CPU. Those interior points locating inside a quadrilateral formed by four extreme points are first discarded, and then the remaining points are distributed into several (typically four) sub regions. For each subset of points, they are first sorted in parallel; then the second round of discarding is performed using SPA; and finally a simple chain is formed for the current remaining points. A simple polygon can be easily generated by directly connecting all the chains in sub regions. The expected convex hull of the input points can be finally obtained by calculating the convex hull of the simple polygon. The library Thrust is utilized to realize the parallel sorting, reduction, and partitioning for better efficiency and simplicity. Experimental results show that: (1) SPA can very effectively detect and discard the interior points; and (2) CudaChain achieves 5×-6× speedups over the famous Qhull implementation for 20M points. [ABSTRACT FROM AUTHOR]

General purpose computing on Graphics Processor Units (GPGPU) can significantly reduce computational cost by performing massively parallel computing. The benefits of GPGPU have been exploited in mesh generation and mesh optimization. Mesh smoothing is one of the most popular approaches that are capable of improving mesh quality by repositioning nodes in meshes without altering the topology of meshes. In this paper, specifically aiming at Laplacian-based mesh smoothing, a generic paradigm for exploiting the power of GPU-acceleration is developed to improve the computational efficiency. The data layouts for representing mesh data structures on the GPU are first discussed; and then a practical solution to dealing with the data dependencies in the iterative smoothing procedure is introduced. Two forms of iteration in Laplacian smoothing (LS) are also analyzed, including the form that needs to swap intermediate nodal coordinates and the other form that does not swap data. In addition, the standard LS is implemented to demonstrate the effectiveness of the presented paradigm. Experimental results show that: on single and double precision, the GPU implementations developed using the data structures represented by aligned array-of-structures layout achieve the best efficiency. It is also demonstrated that the form that needs to swap intermediate nodal coordinates is always slower than the one that does not swap data. [ABSTRACT FROM AUTHOR]