We recently published a paper on fast parallel 3D Delaunay triangulation in the International Journal for Numerical Methods.
The paper describe how we designed a library able to compute up to 65 million tetrahedra per second*.
*on an AMD EPYC 7551 (2×32 core)
765097
5EDSYLQV
items
1
petit-chicago-author-date
0
default
asc
3193
https://www.hextreme.eu/wp-content/plugins/zotpress/
%7B%22status%22%3A%22success%22%2C%22updateneeded%22%3Afalse%2C%22instance%22%3A%22zotpress-8eb167bf61013cbacb0fdf09103b9022%22%2C%22meta%22%3A%7B%22request_last%22%3A0%2C%22request_next%22%3A0%2C%22used_cache%22%3Atrue%7D%2C%22data%22%3A%5B%7B%22key%22%3A%225EDSYLQV%22%2C%22library%22%3A%7B%22id%22%3A765097%7D%2C%22meta%22%3A%7B%22lastModifiedByUser%22%3A%7B%22id%22%3A6974057%2C%22username%22%3A%22coupletm%22%2C%22name%22%3A%22%22%2C%22links%22%3A%7B%22alternate%22%3A%7B%22href%22%3A%22https%3A%5C%2F%5C%2Fwww.zotero.org%5C%2Fcoupletm%22%2C%22type%22%3A%22text%5C%2Fhtml%22%7D%7D%7D%2C%22creatorSummary%22%3A%22Marot%20et%20al.%22%2C%22parsedDate%22%3A%222018%22%2C%22numChildren%22%3A3%7D%2C%22bib%22%3A%22%3Cdiv%20class%3D%5C%22csl-bib-body%5C%22%20style%3D%5C%22line-height%3A%201.35%3B%20padding-left%3A%201em%3B%20text-indent%3A-1em%3B%5C%22%3E%5Cn%20%20%3Cdiv%20class%3D%5C%22csl-entry%5C%22%3E%3Cspan%20style%3D%5C%22font-variant%3Asmall-caps%3B%5C%22%3EMarot%3C%5C%2Fspan%3E%2C%20C%26%23xE9%3Blestin%2C%20Jeanne%20%3Cspan%20style%3D%5C%22font-variant%3Asmall-caps%3B%5C%22%3EPellerin%3C%5C%2Fspan%3E%20et%20Jean-Francois%20%3Cspan%20style%3D%5C%22font-variant%3Asmall-caps%3B%5C%22%3ERemacle%3C%5C%2Fspan%3E.%20%26%23xAB%3B%26%23xA0%3BOne%20machine%2C%20one%20minute%2C%20three%20billion%20tetrahedra%26%23xA0%3B%26%23xBB%3B%2C%20%3Ci%3EInternational%20Journal%20for%20Numerical%20Methods%20in%20Engineering%3C%5C%2Fi%3E%2C%20n%3Csup%3Eo%3C%5C%2Fsup%3Eja%2C%202018.%20%26lt%3B%3Ca%20href%3D%27https%3A%5C%2F%5C%2Fdoi.org%5C%2F10.1002%5C%2Fnme.5987%27%3Ehttps%3A%5C%2F%5C%2Fdoi.org%5C%2F10.1002%5C%2Fnme.5987%3C%5C%2Fa%3E%26gt%3B.%3C%5C%2Fdiv%3E%5Cn%3C%5C%2Fdiv%3E%22%2C%22data%22%3A%7B%22itemType%22%3A%22journalArticle%22%2C%22title%22%3A%22One%20machine%2C%20one%20minute%2C%20three%20billion%20tetrahedra%22%2C%22creators%22%3A%5B%7B%22creatorType%22%3A%22author%22%2C%22firstName%22%3A%22C%5Cu00e9lestin%22%2C%22lastName%22%3A%22Marot%22%7D%2C%7B%22creatorType%22%3A%22author%22%2C%22firstName%22%3A%22Jeanne%22%2C%22lastName%22%3A%22Pellerin%22%7D%2C%7B%22creatorType%22%3A%22author%22%2C%22firstName%22%3A%22Jean-Francois%22%2C%22lastName%22%3A%22Remacle%22%7D%5D%2C%22abstractNote%22%3A%22This%20paper%20presents%20a%20new%20scalable%20parallelization%20scheme%20to%20generate%20the%203D%20Delaunay%20triangulation%20of%20a%20given%20set%20of%20points.%20Our%20first%20contribution%20is%20an%20efficient%20serial%20implementation%20of%20the%20incremental%20Delaunay%20insertion%20algorithm.%20A%20simple%20dedicated%20data%20structure%2C%20an%20efficient%20sorting%20of%20the%20points%20and%20the%20optimization%20of%20the%20insertion%20algorithm%20have%20permitted%20to%20accelerate%20reference%20implementations%20by%20a%20factor%20three.%20Our%20second%20contribution%20is%20a%20multi-threaded%20version%20of%20the%20Delaunay%20kernel%20that%20is%20able%20to%20concurrently%20insert%20vertices.%20Moore%20curve%20coordinates%20are%20used%20to%20partition%20the%20point%20set%2C%20avoiding%20heavy%20synchronization%20overheads.%20Conflicts%20are%20managed%20by%20modifying%20the%20partitions%20with%20a%20simple%20rescaling%20of%20the%20space-filling%20curve.%20The%20performances%20of%20our%20implementation%20have%20been%20measured%20on%20three%20different%20processors%2C%20an%20Intel%20core-i7%2C%20an%20Intel%20Xeon%20Phi%20and%20an%20AMD%20EPYC%2C%20on%20which%20we%20have%20been%20able%20to%20compute%203%20billion%20tetrahedra%20in%2053%20seconds.%20This%20corresponds%20to%20a%20generation%20rate%20of%20over%2055%20million%20tetrahedra%20per%20second.%20We%20finally%20show%20how%20this%20very%20efficient%20parallel%20Delaunay%20triangulation%20can%20be%20integrated%20in%20a%20Delaunay%20refinement%20mesh%20generator%20which%20takes%20as%20input%20the%20triangulated%20surface%20boundary%20of%20the%20volume%20to%20mesh.%22%2C%22date%22%3A%222018%22%2C%22language%22%3A%22en%22%2C%22DOI%22%3A%2210.1002%5C%2Fnme.5987%22%2C%22ISSN%22%3A%221097-0207%22%2C%22url%22%3A%22https%3A%5C%2F%5C%2Fonlinelibrary.wiley.com%5C%2Fdoi%5C%2Fabs%5C%2F10.1002%5C%2Fnme.5987%22%2C%22collections%22%3A%5B%22GT3V7MWE%22%5D%2C%22dateModified%22%3A%222021-08-04T12%3A10%3A57Z%22%7D%7D%5D%7D
Marot, Célestin, Jeanne
Pellerin et Jean-Francois
Remacle. « One machine, one minute, three billion tetrahedra »,
International Journal for Numerical Methods in Engineering, n
oja, 2018. <
https://doi.org/10.1002/nme.5987>.