Restricted Power Diagrams on the GPU

Simple item page
dc.contributor.authorBasselin, Justineen_US
dc.contributor.authorAlonso, Laurenten_US
dc.contributor.authorRay, Nicolasen_US
dc.contributor.authorSokolov, Dmitryen_US
dc.contributor.authorLefebvre, Sylvainen_US
dc.contributor.authorLévy, Brunoen_US
dc.contributor.editorMitra, Niloy and Viola, Ivanen_US
dc.date.accessioned2021-04-09T07:59:00Z
dc.date.available2021-04-09T07:59:00Z
dc.date.issued2021
dc.description.abstractWe propose a method to simultaneously decompose a 3D object into power diagram cells and to integrate given functions in each of the obtained simple regions.We offer a novel, highly parallel algorithm that lends itself to an efficient GPU implementation. It is optimized for algorithms that need to compute many decompositions, for instance, centroidal Voronoi tesselation algorithms and incompressible fluid dynamics simulations. We propose an efficient solution that directly evaluates the integrals over every cell without computing the power diagram explicitly and without intersecting it with a tetrahedralization of the domain. Most computations are performed on the fly, without storing the power diagram. We manipulate a triangulation of the boundary of the domain (instead of tetrahedralizing the domain) to speed up the process. Moreover, the cells are treated independently one from another, making it possible to trivially scale up on a parallel architecture. Despite recent Voronoi diagram generation methods optimized for the GPU, computing integrals over restricted power diagrams still poses significant challenges; the restriction to a complex simulation domain is difficult and likely to be slow. It is not trivial to determine when a cell of a power diagram is completely computed, and the resulting integrals (e.g. the weighted Laplacian operator matrix) do not fit into fast (shared) GPU memory. We address all these issues and boost the performance of the state-of-the-art algorithms by a factor 2 to 3 for (unrestricted) Voronoi diagrams and ax50 speed-up with respect to CPU implementations for restricted power diagrams. An essential ingredient to achieve this is our new scheduling strategy that allows us to treat each Voronoi/power diagram cell with optimal settings and to benefit from the fast memory.en_US
dc.description.number2
dc.description.sectionheadersGeometry and Transformations
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume40
dc.identifier.doi10.1111/cgf.142610
dc.identifier.issn1467-8659
dc.identifier.pages1-12
dc.identifier.urihttps://doi.org/10.1111/cgf.142610
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf142610
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectTheory of computation
dc.subjectComputational geometry
dc.subjectComputing methodologies
dc.subjectParallel algorithms
dc.titleRestricted Power Diagrams on the GPUen_US
dcterms.typeJournalArticle
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
v40i2pp001-012.pdf
Size:
11.18 MB
Format:
Adobe Portable Document Format
Download
Collections
40-Issue 2