Popis implementace a datového rozhraní
Knihovna MDT slouží k mapování dat mezi trojúhelníkovými sítěmi MKP. Pro každý uzel cílové sítě je nalezen odpovídající prvek zdrojové sítě, do kterého uzel padne nebo kterému je nejblíže, a stanoví plošné souřadnice uzlu v tomto prvku. Ty se následně využijí (jako bázové funkce) pro mapování veličin z uzlů lokalizovaného prvku zdrojové sítě do vyšetřovaného uzlu sítě cílové. Obě sítě musí být diskretizací téhož geometrického modelu.
Na vstupu se očekává popis zdrojové i cílové sítě, tj. jejich geometrie (souřadnice uzlů), konektivita (čísla uzlů jednotlivých prvků) a příslušnost prvků k jednotlivým regionům. Číslování se předpokládá spojité začinající od 1. Na výstupu jsou pak pro uzly jednotlivých regionů cílové sítě uvedeny nejbližší prvek (příslušný regionu) zdrojové sítě, čísla jeho uzlů a plošné souřadnice cílového uzlu promítnutého do roviny tohoto prvku. V současné verzi se vstup i výstup realizují přes datové soubory.
Formát vstupního souboru:
počet_uzlů počet_prvků
číslo_uzlu souřadnice_x souřadnice_y souřadnice_z
číslo_prvku číslo_regionu počet_uzlů_prvku čísla_uzlů_prvku
Formát výstupního souboru:
číslo_regionu počet_uzlů
číslo_uzlu_cílové_sítě číslo_prvku_zdrojové_sítě čísla_uzlů_prvku plošné_souřadnice
Datové struktury
Struktura nodes_list (alias LIST)
Slouží pro seznam uzlů, které jsou v OCTANTu. Tato struktura umožnuje přidávání uzlů do seznamu aniž bychom dříve znali počet uzlů v seznamu.
Struktura LIST obsahuje 2 parametry:
• long nodenum - číslo uzlu
• struct nodes_list *next - ukazatel na další část seznamu
Struktura octant (alias OCTANT)
OCTANT je pomyslná krychle, na které je rozdělen prostor, kde se síť nachází
Struktura OCTANT obsahuje 5 parametrů:
• int terminal - určuje jestli je OCTANT terminální či nikoliv (1- je Terminal; 0-není Terminal);
• double coordinates[4] - určuje souřadnice (0. pozice - délka hrany, 1. pozice - x středu, 2. pozice - y středu, 3. pozice - z středu)
• int num_of_nodes - počet uzlů v OCTANTu
• LIST *nodes_list - určuje čísla uzlů nacházející se v OCTANTu
• struct octant *parent - ukazatel na mateřský OCTANT
• struct octant *childs[8] - pole ukazatelů na potomky OCTANTu
Variabilní parametry
Parametry pro debug a ladění výkonu knihovny:
• MAX_NODE_NUM - počet uzlů nacházejících se v oktantu (doporučené hodnoty 10-100)
• NUM_OF_VALUES - počet hodnot různých veličin uložených v uzlech
• OCT_RESIZE - zvětšení octree (1.1 odpovídá zvětšení na 110% tedy zvětšení o 10%)
• INVESTIGATED_AREA_RESIZE – zvětšení oblasti ve které jsou hledány nejbližší uzly, pokud dosud nebyly žádné nalezeny (1.5 odpovídá zvětšení o 0.5 velikosti oblasti na každou stranu)
• MAX_NODE_VISIT – počet uzlů pro které je u všech prvků jim příslušících porovnávána nejměnší záporná plošná souřadnice
Přehled funkcí:
int main()
HLAVNÍ FUNKCE
Stručný popis: Alokuje globální proměnné. Ověří si soubor zdrojové
sítě funkcí verify_FILE a otevře ho. Načte z něj všechna data
pomocí funkcí create_1D_FIELD a zavře ho. Poté zavolá funkce
establish_conectivity_1 a establish_conectivity_2 a uloží jejich
návratová pole. Pomocí funkce zjistí meze prostoru zdrojové sítě
find_OCTREE_BOUNDRY a může dále vytvořit první OCTANT funkcí
create_first_OCTANT. Funkcí grow_octree_of_OCTANTS pak načítá do
OCTANTu uzly a nechává ho růst. Ověří si soubor cílové sítě
funkcí verify_FILE a otevře ho. Načte z něj všechna data pomocí
funkcí create_1D_FIELD a zavře ho. Nakonec zavolá funkci
locate_nodes_in_octant aby lokalizovala mapované prvky v uzlech
zdrojové sítě. Na závěr otevře soubor new_mesh.txt a uloží pro něj
data pro mapování.
int verify_FILE (FILE *g)
FUNKCE PRO KONTROLU SOUBORU
Požaduje 1 parametr: ukazatel na soubor již otevřený funkcí main
Vrací: 0 - pokud soubor sítě neexistuje; 1 - pokud soubor sítě existuje;
double* create_1D_FIELD(FILE *g, long n)
FUNKCE PRO ALOKACI 1D POLE TYPU DOUBLE A NAČTENÍ HODNOT DO POLE
Požaduje 2 parametry: velikost pole a ukazatel na soubor již otevřený funkcí main
Vrací: ukazatel na pole
long* create_1D_FIELD (FILE *g, long n)
FUNKCE PRO ALOKACI 1D POLE TYPU LONG A NAČTENÍ HODNOT DO POLE
Požaduje 2 parametry: velikost pole a ukazatel na soubor již otevřený funkcí main
Vrací: ukazatel na pole
double* find_OCTREE_BOUNDRY (double field[], long nodes)
FUNKCE PRO ZJIŠTENÍ MIN. A MAX. SOUŘADNICE VŠECH UZLŮ
Požaduje 2 parametry: 1d_pole uzlů a počet uzlů (obojí zdrojové sítě)
Vrací: ukazatel na pole maximálních a minimálních hodnot
Stručný popis: Projde souřadnice všech uzlů a do pole o velikosti 6 si
uloží maximální a minimální hodnoty jednotlivých souřadnic x, y a z.
void create_first_OCTANT (OCTANT *octant, double boundry[])
FUNKCE PRO VYTVOŘENÍ PRVNÍHO OCTANTU
Požaduje 2 parametry: OCTANT, a pole max. a min. souřadnic
Stručný popis: Najde největší rozdíl max. a min. souřadnic a zvětší ho hodnotou OCT_RESIZE (aby uzle nepadaly mimo octree) a uloží ho jako hranu OCTANTu. Poté vypočte souřadnice jeho středu a nastaví OCTANT jako terminal a všechny další parametry OCTANTu na nulové hodnoty.
void grow_octree_of_OCTANTS (OCTANT *octant, double field[], long nodes)
FUNKCE PRO TVORBU OCTREE
Požaduje 3 parametry: OCTANT, a pole a počet uzlů (zdrojové sítě)
Stručný popis: Prochází postupně všechny uzly, a když najde koncový OCTANT, do kterého uzel spadá, uloží ho do seznamu LIST (pomocí funkce add_to_LIST). Pokud ale při ukládání nového uzlu do seznamu v OCTANTu překročí seznam velikost MAX_NODE_NUM zavolá funkci divide_OCTANT.
void divide_OCTANT (OCTANT *parent, double field[])
FUNKCE PRO ROZDĚLENÍ OCTANTU MEZI POTOMKY
Požaduje 2 parametry: OCTANT, který chceme dělit a 1d_pole uzlů
Stručný popis: Vytvoří 8 OCTANTů potomků. Všem potomkům se uloží délka poloviční hrany rodiče. Souřadnice středů OCTANTů se vypočtou tak, aby nevznikly 2 stejné OCTANTy. Potomci se nastaví jako terminal (tedy koncové OCTANTy ve stromu) a odkazy na jejich potomky se nastaví na hodnotu NULL. Jednotlivé uzly rodiče se roztřídí podle souřadnic mezi potomky a pomocí funkce add_to_LIST se přidají do jejich seznamů uzlů. Seznam uzlů rodiče se poté vymaže funkcí delete_LIST
long *establish_conectivity_1 (long nodes_maped, long ELEMENT_field_maped[], long triangEL)
FUNKCE PRO ALOKOVÁNÍ A VYPLNĚNÍ POLE POŘADÍ V POLI KONEKTIVITY
Požaduje 3 parametry: počet uzlů, pole prvků a počet prvků (cílové sítě)
Vrací: pole pořadí uzlů v poli konektivity (podrobněji v komentáři ve zdrojovém kódu)
Stručný popis: Nejdříve projde všechny pole prvků a zjistí, kolikrát jsou jednotlivé uzly využity. Poté podle využití jednotlivých uzlů vyplní postupně pole pořadí.
long *establish_conectivity_2 (long list_of_positions[], long ELEMENT_field_maped[], long nodes_maped, long triangEL)
FUNKCE PRO ALOKOVÁNÍ A VYPLNĚNÍ POLE KONEKTIVITY
Požaduje 4 parametry: Pole pořadí v poli konektivity, počet uzlů, pole prvků a počet prvků (cílové sítě)
Vrací: pole konektivity
Stručný popis: Alokuje si pole aktuálního pořadí v poli konektivity. Poté prochází jednotlivé prvky a ukládá je do úseků patřící příslušným uzlům. Zároveň si v poli aktuálního pořadí posouvá odkazy na úseky v poli konektivity tak, aby se nepřepisovaly již dříve zapsané prvky.
long* locate_nodes_in_octant(OCTANT *octant, double field_maped[], long nodes_maped, long nodes_orig, double field_orig[], long list_of_positions[], long nodes_to_elements_list[], long element_field_orig[], long nodes_to_elements_size)
FUNKCE PRO NALEZENÍ NEJBLIŽSÍHO PRVKU ZDROJOVÉ SÍTĚ
Požaduje 9 parametrů: octant, pole uzlů zdrojové sítě, počet uzlů
cílové sítě, počet uzlů zdrojové sítě, pole uzlů zdrojové sítě, obě pole konektivity, pole prvků zdrojové sítě, délka hlavního pole konektivity
Vrací: Pole, kde pozice označuje mapovaný uzel a hodnota prvek, ve kterém se uzel nachází, (nebo je mu nejblíže)
Stručný popis: Každý uzel cílové sítě lokalizuje v příslušném OCTANTu pomocí funkce search. Pokud funkce search vrátí hodnotu 1(tzn. že prvek byl lokalizován) ukončí se hledání. Pokud ne, a funkce investigate_surrounding_area vrátí nesouvislé okolí (hodnota 0), zkontroluje se, zda nebyl překročen MAX_NODE_VISIT. Když limit překročen nebyl, poloměr koule se zvětší o INVESTIGATED_AREA_RESIZE a pokračuje se v hledání.
double *get_point_from_node_field (long point_num, double node_field[])
FUNKCE PRO EXTRAKCI BODU Z POLE UZLŮ
Požaduje 2 parametry: pole uzlů a číslo bodu
Vrací: bod (pole se souřadnicemi x, y a z)
double *create_vector_from_point1_to_point2 (double point1[], double point2[])
FUNKCE PRO VYTVOŘENÍ VECTORU ZE DVOU BODŮ
Požaduje 2 parametry: 2 body (ve formátu předchozí funkce)
Vrací: vektor (pole se směrnicemi x, y a z)
double get_skalar_of_vectors(double vector1[], double vector2[])
FUNKCE PRO SKALÁRNÍ SOUČIN VEKTORŮ
Požaduje 2 parametry: 2 vektory (ve formátu předchozí funkce)
Vrací: skalární součin
double *create_vector_NORMAL_to_line_across_point (double point_on_line[], double point_off_line[], double line_vector[])
FUNKCE PRO VYTVOŘENÍ NORMÁLOVÉHO VECTORU PŘÍMKY PROCHÁZEJÍCÍHO DANÝM BODEM MIMO PŘÍMKU
Požaduje 3 parametry: bod na přímce, bod, kterým normála povede a směrový vektor přímky (ve formátu předchozích funkcí)
Vrací: normálový vektor
double *get_area(double point_on_line[], double point_on_line2[], double point_off_line[], double line_vector[])
FUNKCE PRO VYPOČTENÍ PLOCHY TROJÚHELNÍKA
Požaduje 4 parametry: 2 body trojúhelníka, třetí bod trojúhelníka, a směrový vektor úsečky mezi prvními dvěma body (ve formátu předchozích funkcí)
Vrací: plochu trojúhelníku
void add_to_LIST (LIST **ppl, long node)
FUNKCE PRO PŘIDÁNÍ HODNOTY DO SEZNAMU TYPU LIST
Požaduje 2 parametry: adresu seznamu a hodnotu, kterou přidáváme
Stručný popis: Vytvoří novou strukturu typu LIST. Uloží do ní přidávanou hodnotu a ukazatel na původní část seznamu LIST. Do příslušného OCTANTu pak uloží ukazatel na novou strukturu LIST (původní část seznamu tedy zůstává neměnná, další hodnoty se přidávají "na začátek").
void delete_LIST (LIST **ppl)
FUNKCE PRO SMAZÁNÍ SEZNAMU
Požaduje 1 parametr: adresu seznamu
Stručný popis: Postupně projde všechny články seznamu a smaže je, aniž by nějakou vynechal.
int search(OCTANT *octant)
FUNKCE ROZŠIŘOVÁNÍ OKOLÍ A HLEDÁNÍ DALŠÍCH BLÍZKÝCH BODŮ
Požaduje 1 parametr: octant
Vrací: 1 - pokud přímo funkce locate_node_in_element najde prvek, do kterého uzel spadá, nebo 0 - pokud se prvek, do kterého by uzel spadal, přímo nenajde
Stručný popis: Prochází octree a hledá koncový OCTANT, který se překrývá s původním OCTANTem zvětšeným o INVESTIGATED_AREA_RESIZE. Toto prohledávání probíhá rekurzivně. Až najde koncový (terminální) OCTANT, zkusí, jestli jeho uzly patří do pomyslné koule zvětšeného okolí. Ty, které do ní spadají, otestuje funkcí locate_node_in_element.
int locate_node_in_element(long maped_node_num)
FUNKCE NA LOKALIZACI UZLU V PRVCÍCH
Požaduje 1 parametrů: uzel zdrojové sítě (vše ostatní jsou z důvodu rekurzivity nadřazené funkce globální proměnné)
Vrací: 1 - pokud přímo najde prvek, do kterého uzel spadá, nebo 0 - pokud prvek nepatří do žádného prvku v okolí uzlu
Stručný popis: Nejdříve načte všechny okolní prvky. Poté je postupně prochází a hledá, do kterého mapovaný uzel spadá. U každého prvku postupně vypočte pomocí funkcí pro práci s vektory: 1) normálový vektor každé strany a 2) vektor z bodu, nacházejícího se na dané straně, do mapovaného bodu. Pokud jsou skalární součin těchto dvou vektorů pro všechny strany trojúhelníka kladné, nachází se bod uvnitř trojúhelníku (tedy prvku). V tomto případě vrátí hodnotu 1 a uloží si příslušný prvek. Dále také počítá plošné souřadnice na prvcích a ukládá si nejmenší nalezenou zápornou souřadnici (největší a zároveň menší než nula). Pokud nenajde prvek, v kterém by se uzel přímo nacházel, vrátí hodnotu 0.
long* search_list_for_closest(LIST *pl, double field_orig[], double x_maped, double y_maped, double z_maped, int nodes)
FUNKCE PRO VYTVOŘENÍ TŘÍDĚNÉHO SEZNAMU NEJBLIŽŠÍCH UZLŮ ZDROJOVÉ SÍTĚ V LISTU UZLŮ
Požaduje 6 parametrů: LIST uzlů, pole uzlů zdrojové sítě, souřadnice mapovaného uzlu, pole pro uložení nejbližšího uzlu, počet uzlů v LISTu uzlů
vrací: pole seznam uzlů seřazený od nejbližšího po nejvzdálenější
Stručný popis: Prochází seznam typu LIST a načítá si souřadnice uzlů v seznamu. Z nich vypočte vzdálenost od mapovaného bodu. Do jednoho pole si postupně uloží čísla uzlů a do druhého na stejné pozice jejich vzdálenosti od mapovaného bodu. Poté se obě pole paralelně seřadí od nejmenší vzdálenosti k největší. Řazení probíhá systémem: Prohoď větší hodnotu na aktuální pozici za menší hodnotu na další pozici, nebo pokračuj beze změny.
void investigate_surrounding_area (long compact_area_list[], long current_orig_node, long list_of_positions[], long nodes_to_elements_list[], long element_field_orig[], long end_of_field, long nodes)
FUNKCE NA VYŠETŘENÍ SOUVISLOSTI OKOLÍ (TEDY ZDA JE PRVEK OBKLOPEN ZE VŠECH STRAN UZLY)
Požaduje 7 parametrů: pole souvislosti okolí, zkoumaný uzel, obě pole konektivity, konec pole konektivity, pole prvků a počet uzlů zdrojové sítě
Stručný popis: Zkoumá všechny okolní prvky, které uzel využívají, a
spočítá všechny uzly těchto prvků. Pokud se každý uzel opakuje alespoň
2 krát, pak je okolí souvislé. Nakonec se uloží do pole souvislosti, zda je okolí kolem bodu souvislé, nebo není.
