Vi studerar problemet med att sönderdela en volym som avgränsas av en slät yta till en samling Voronoiceller. Till skillnad från det dubbla problemet med att anpassa Delaunay meshing, var en principiell lösning på detta problem för generiska släta ytor fortfarande svårfångad. VoroCrust utnyttjar idéer från αshapes och kraftskorpan algoritm för att producera oviktade Voronoi celler som överensstämmer med ytan, vilket ger den första bevisbart korrekta algoritmen för detta problem. Med tanke på ett ε-prov på den avgränsande ytan, med en svag σ-parsitet skick, arbetar vi med bollar med radien δ gånger den lokala funktionen storlek centrerad på varje prov. De hörn av denna förening av bollar är Voronoi platser, på båda sidor av ytan. De facetter som är gemensamma för celler på motsatta sidor rekonstruerar ytan. För lämpliga värden på ε, σ och σ bevisar vi att ytrekonstruktionen är isotopisk till den avgränsande ytan. Med ytan skyddad, kan den slutna volymen ytterligare sönderdelas i en isotopisk volym maska fett Voronoi celler genom att generera ett begränsat antal platser i dess inre. Jämfört med toppmoderna metoder baserade på klippning, VoroCrust celler är fulla Voronoi celler, med konvexitet och fettstyrka garantier. Jämfört med kraftskorpan algoritm, VoroCrust celler inte filtreras, är oviktade, och erbjuder större flexibilitet i meshing den slutna volymen med antingen strukturerade rutnät eller slumpmässiga prover. licensierad under Creative Commons License CC-BY Mesh generation är ett grundläggande problem i beräkningsgeometri, geometrisk modellering, datorgrafik, vetenskaplig beräkning och tekniska simuleringar. Intresset för polyhedralmaskor har ökat som ett alternativ till tetrahedral- eller hexdominantmaskor [48]. Polyhedra är mindre känslig för stretching, vilket möjliggör representation av komplexa geometrier utan överdriven förfining. Dessutom har polyhedral celler fler grannar även vid hörn och gränser, som erbjuder bättre approximationer av gradienter och lokala flöden fördelningar. Även jämfört med hexahedra behövs färre polyhedralceller för att uppnå önskad noggrannhet i vissa tillämpningar. Detta kan vara mycket användbart i flera numeriska metoder [18], t.ex. finita element [42], finita volymer [39], virtuella element [17] och Petrov-Galerkin [41]. Särskilt noggrannheten hos ett antal viktiga lösare, t.ex. approximationen av tvåpunktsflödet för bevarandelagar [39], har stor nytta av ett lyktigt nät som är ortogonalt till dess dubbla såsom naturligt tillfredsställt av Voronoi maskor. Sådana lösare spelar en avgörande roll inom hydrologi [51], beräkningsvätskans dynamik [22] och frakturmodellering [20]. VoroCrust är den första bevisligen korrekta algoritmen för att generera en volymetrisk Voronoi mesh vars gräns överensstämmer med en jämn avgränsande yta, och med kvalitetsgarantier. En överensstämmande volymmaska uppvisar två önskvärda egenskaper samtidigt: 1) en sönderdelning av den slutna volymen och 2) en rekonstruktion av den avgränsande ytan. Konformerande Delaunay meshing är välstuderad [28], men Voronoi meshing är mindre mogen. En vanlig praktisk metod för polyhedral meshing är att dubblera en tetrahedral mesh och klipp, dvs skär och trunkera, varje cell vid den avgränsande ytan [35, 43, 47, 52, 55]. Tyvärr, klippning offrar de viktiga egenskaperna konvexitet och anslutenhet av celler [35], och kan kräva dyra konstruktiva solid geometri verksamhet. Att begränsa en Voronoi mesh till ytan innan filtrering dess dubbla Delaunay fasetter är en annan metod [7, 33, 56], men filtrering kräver extra kontroller komplicera dess genomförande och analys; se även Figur 4. En intuitiv strategi är att lokalt spegla Voronoi platser på vardera sidan av ytan [34, 57], men vi är inte medvetna om några robusta algoritmer med approximativa garantier i denna kategori. I motsats till dessa metoder utmärker sig VoroCrust genom sin enkelhet och robusthet när det gäller att producera äkta oviktade Voronoi-celler och utnyttja etablerade bibliotek, t.ex. Voro+++ [50], utan ändringar eller specialfall. VoroCrust kan ses som en principiell spegelteknik, som delar ett antal nyckelfunktioner med power crust-algoritmen [13]. Power crust-litteraturen [7, 8, 10, 12, 13] utvecklade en rik teori för approximering på ytan, nämligen paradigmet ε-sampling. Kom ihåg att algoritmen för kraftskorpan använder ett ε-prov av oviktade punkter för att placera viktade platser, så kallade poler, nära den underliggande ytans mittaxel. Ytrekonstruktion är insamling av facetter som separerar kraftceller av poler på insidan och utsidan av den slutna volymen. Abdelkader m.fl.
Förutsatt tillgång till den lokala funktionen storlek med en ε-provtagning ges som insats, starka teoretiska garantier för produktionen kvalitet fastställdes REF.
Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm
{'venue': 'LIPIcs : Leibniz international proceedings in informatics', 'journal': 'LIPIcs : Leibniz international proceedings in informatics', 'mag_field_of_study': ['Computer Science', 'Medicine', 'Mathematics']}