Abstrakt. Detta dokument introducerar två effektiva algoritmer som beräknar Contour Tree av ett tredimensionellt skalärfält F och dess utökade version med Batti nummer av varje isosurfing. Contour Tree är en grundläggande datastruktur i vetenskaplig visualisering som används för att förbehandla domänen mesh för att möjliggöra optimal beräkning av isoytor med minimal overheadlagring. Contour Tree kan också användas för att bygga användargränssnitt som rapporterar den fullständiga topologiska karakteriseringen av ett skalärfält, som visas i figur 1. Prospekteringstiden för data minskas eftersom användaren förstår utvecklingen av nivåuppsättningskomponenter med föränderligt isovärde. Den Augmented Contour Tree ger ännu mer exakt information segmentering intervallet för skalärfältet i regioner av invariant topologi. Även prospekteringstiden för en enda isoyta förbättras eftersom släktet är känt i förväg. Vår första nya algoritm förstärker varje givet Contour Tree med Batti nummer av alla möjliga motsvarande isocontours i linjär tid med storleken på trädet. Dessutom visar vi hur man kan förlänga det system som infördes genom [3] med beräkningen av Batti-numret utan att öka dess komplexitet. Således förbättrar vi på tiden komplexiteten i vår tidigare strategi [10] från O(m log m) till O(n log n + m), där m är antalet celler och n är antalet hörn i domänen F. Vårt andra bidrag är en ny divide-and-conquer algoritm som beräknar Augmented Contour Tree med förbättrad effektivitet. Tillvägagångssättet beräknar utdata Contour Tree genom att slå samman två mellanliggande Contour Trees och är oberoende av interpolanten. På detta sätt begränsar vi all kunskap om en specifik interpolant till en oberoende funktion som beräknar trädet för en enda cell. Vi har implementerat denna funktion för den trilinjära interpolanten och planerar att ersätta den med högre interpolanter vid behov. Tiden komplexitet är O(n + t log n), där t är antalet kritiska punkter av F. För första gången kan vi beräkna Contour Tree i linjär tid i många praktiska fall där t = O (n 1−ε ). Vi rapporterar om körtiderna för ett parallellt genomförande, som visar god skalbarhet med antalet processorer.
Pascucci m.fl. REF föreslog den första och enda kända parallella algoritmen som beräknar konturträdet för en bitvis trilinjär funktion definierad på ett tredimensionellt strukturerat nät.
Parallel Computation of the Topology of Level Sets
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Computer Science']}