Please use this identifier to cite or link to this item:
https://doi.org/10.1109/TVCG.2016.2525724
Title: | Flip to Regular Triangulation and Convex Hull | Authors: | Gao, M Cao, TT Tan, TS |
Issue Date: | 1-Feb-2017 | Publisher: | Institute of Electrical and Electronics Engineers (IEEE) | Citation: | Gao, M, Cao, TT, Tan, TS (2017-02-01). Flip to Regular Triangulation and Convex Hull. IEEE Transactions on Visualization and Computer Graphics 23 (2) : 1056-1069. ScholarBank@NUS Repository. https://doi.org/10.1109/TVCG.2016.2525724 | Abstract: | Flip is a simple and local operation to transform one triangulation to another. It makes changes only to some neighboring simplices, without considering any attribute or configuration global in nature to the triangulation. Thanks to this characteristic, several flips can be independently applied to different small, non-overlapping regions of one triangulation. Such operation is favored when designing algorithms for data-parallel, massively multithreaded hardware, such as the GPU. However, most existing flip algorithms are designed to be executed sequentially, and usually need some restrictions on the execution order of flips, making them hard to be adapted to parallel computation. In this paper, we present an in depth study of flip algorithms in low dimensions, with the emphasis on the flexibility of their execution order. In particular, we propose a series of provably correct flip algorithms for regular triangulation and convex hull in 2D and 3D, with implementations for both CPUs and GPUs. Our experiment shows that our GPU implementation for constructing these structures from a given point set achieves up to two orders of magnitude of speedup over other popular single-threaded CPU implementation of existing algorithms. | Source Title: | IEEE Transactions on Visualization and Computer Graphics | URI: | https://scholarbank.nus.edu.sg/handle/10635/225178 | ISSN: | 1077-2626 1941-0506 |
DOI: | 10.1109/TVCG.2016.2525724 |
Appears in Collections: | Staff Publications Elements |
Show full item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
Flip_to_Regular_Triangulation_and_Convex_Hull.pdf | Accepted version | 1.98 MB | Adobe PDF | CLOSED | None |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.