This research project explores the application of NVIDIA Tensor Core hardware acceleration in two-dimensional surface mesh generation. Two algorithms are implemented: the "DeWall" [1] recursive partitioning algorithm and the "Blelloch" [2] sequential subdivision algorithm. This project has no dependencies besides the standard CUDA libraries.
The final project report is available here.
There are several parts to this project:
test.m
is a MATLAB program that can: 1) generate the point cloud points.dat consumed by the CUDA C++ program, 2) generate its own triangulation using built-in MATLAB functions, 3) visualize both connected meshes.
main.cu
is a CUDA C++ program that generates a triangulation of points.dat in connections.at using either of the above algorithms based on which invocation is uncommented in the int main()
block. This program can also evaluate algorithm speed for the Delaunay triangulation triangle circumcircle test over varying subject vertex batch sizes.
profiler_mesh.cu
writes the mesh generation performance statistics to profile_[name]_mesh.csv.
profiler_circles.cu
writes the circumcircle test performance statistics to profile_[algorithm]_circles.csv.
points.dat generated by test.m
consists of line-separated float32
-precision point coordinates. E.g.:
0.5896637 0.2792488
0.02373974 0.3423939
0.8318902 0.6773078
0.7433259 0.5579324
0.005031899 0.01892785
0.6223523 0.2441547
...
connections.dat generated by main.cu
consists of line-separated triangle definitions represented by triplets of zero-indexed integer vertex indices. E.g.:
6471 15759 18792
1900 7510 21888
13548 19843 35938
6585 31578 30122
1039 12257 15872
9781 10206 10854
...
[1] P. Cignoni, C. Montani and R. Scopigno, "DeWall: A fast divide and conquer Delaunay triangulation algorithm in Ed," Computer-Aided Design, vol. 30, no. 5, pp. 333-341, 1998.
[2] G. E. Blelloch, Y. Gu, J. Shun and Y. Sun, "Parallelism in Randomized Incremental Algorithms," in SPAA '16: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, Pacific Grove, 2016.