ADVANCING FRONT GENERIRANJE MREŽE
Avtor: Radovan Dražumerič
Generiranje mreže trikotnikov v ravnini po metodi advancing front
Predstavitev računalniškega programa za generiranje mreže trikotnikov po metodi Advancing front
Abstract
This method is based on a simple idea:
The initial data for the method are the domain boundary, and some mesh parameters. Although the idea is simple the algoritmic details of this method are complex.
In the Advancing front method nodes and elements are added simultaneously, with smooth mesh point placement. The method is boundary confirming (the initial front is boundary). It can fail when there are large variations in grid spacing. The need to search for nearby nodes and edges and the complex intersection checking mean that the Advancing front method is slow.
Za 2D območje, popisano z množico točk lomljenke je potrebno izdelati program, ki bo postavljal trikotnike v notranjost z uporabo algoritma s postavljanjem naprej.
Generiranje mreže trikotnikov v ravnini po metodi Advancing front
Slika 1: Potek metode Advancing front
Izhodiščni podatki metode so:
- ograja območja mreženja,
- parametri mreženja.
Med parametre mreženja spadata željena (povprečna) dolžina stranic trikotnikov - d in faktor raztegnitve mreže v določeni smeri (pomemben vpliv ima pri podolgovatih območjih).
Podano ograjo območja nadomestimo z lomljenko na naslednji način:
· Izračun dolžine ograje - l:
(1)
kjer i predstavlja zaporedno številko segmenta in n število segmentov podane ograje.
· Določitev števila segmentov lomljenke - Ns:
(2)
kjer d predstavlja željeno dolžino stranic trikotnikov.
· Določitev lege točk lomljenke na podani ograji območja:
a) Za določitev vsake naslednje (j - te) točke lomljenke je potrebno poiskati točko (i - to) na podani ograji tako, da velja:
(3)
b) Lego j - te točke lomljenke določimo na naslednji način:
(4)
Določitev lege novega trikotnika
Optimalno lego vrha novega trikotnika določimo po empirični enačbi (5), ki skrbi, da je velikost trikotnikov čimbolj enotna in tako prepreči neugodne vplive na kakovost nadaljnega mreženja.
(5)
Pomen oznak v enačbi (5) je prikazan na sliki 2.
Slika 2: Določitev vrha novega trikotnika
Kontrola okolice novega trikotnika
Po določitvi optimalne lege vrha novega trikotnika je potrebno kontrolirati bližnjo okolico tega trikotnika (notranjost kroga s središčem v vrhu novega trikotnika in s polmerom d1).
Če je vrh preblizu meje območja, lahko v nadaljevanju pride do zelo slabe kvalitete mreženja. Zato je v tem primeru potrebno za vrh izbrati že obstoječo točko na meji območja, ki je najbližja prvotnemu vrhu novega trikotnika. Primera izbire že obstoječe točke na meji območja sta prikazana na sliki 3.
Slika 3: Primera izbire točke na meji območja za vrh novega trikotnika
Pri vsakem novo izbranem vrhu je zopet potrebno kontrolirati stanje v območju za mreženje. Postopek ponavljamo toliko časa, dokler ne najdemo ustrezne točke za vrh novega trikotnika.
Čeprav je osnovna ideja enostavna, so detajli metode zelo kompleksni. Glavne značilnosti metode so:
· Metoda je splošno uporabna za poljubne oblike območja mreženja.
· Metoda je zelo občutljiva na geometrijske lastnosti, predvsem slaba diskretizacija ograje ali napačna izbira novih elementov privede do slabe kvalitete mreženja.
· Velik vpliv na kvaliteto mreženja ima izbira vrednosti parametrov mreženja (željena dolžina segmentov, faktor raztegnitve).
· Metoda je zaradi obsežnega kontroliranja ustreznosti lege za vsak nov element posebej zelo počasna.
Predstavitev računalniškega programa za generiranje mreže trikotnikov po metodi advancing front
Vnos podatkov se izvaja preko tekstovne datoteke. Podatki, ki jih je potrebno zapisati v vhodno datoteko so naslednji:
- željena dolžina stranic trikotnikov - d ,
- faktor raztegnitve mreže v vertikalni smeri,
- število točk ograje območja,
- točke ograje območja.
Območja za mreženje morajo biti enkrat povezana, orientacija ograje je lahko poljubna.
Slika 4: Vhodna datoteka
Program je napisan v programskem jeziku Fortran, pri grafičnem delu uporablja grafično knjižnico Phigs.
Zgradbo glavnega programa za mreženje 2D območja po metodi Advancing front prikazuje slika 5.
Slika 5: Zgradba programa za mreženje 2D območij po metodi Advancing front
Rezultati programa za mreženje po metodi Advancing front:
- izris končne mreže trikotnikov 2D območja,
- izpis vseh točk območja v tekstovno datoteko.
Slika 6: Primer grafičnega prikaza mreže trikotnikov 2D območja
Vpliv oblike območja
Vpliv na kvaliteto mreženja ima oblika danega območja. Iz slik 7 in 8 je razvidno, da je metoda primernejša za simetrična območja. Ostri prehodi v ograji območja predstavljajo motnjo in poslabšajo kvaliteto mreženja.
Slika 7: Mreženje simetričnega območja
Slika 8: Mreženje nesimetričnega območja
Vpliv parametrov mreženja
Na kvaliteto mreženja ima velik vpliv tudi ustrezna izbira parametrov mreženja. Vpliv izbire željene dolžine segmentov je prikazan na slikah 9 in 10, vpliv faktorja raztegnitve mreže pa na slikah 11 in 12.
Slika 9: Neustrezna izbira dolžine segmentov
Slika 10: Ustreznejša izbira dolžine segmentov
Slika 11: Faktor raztegnitve mreže v vertikalni smeri je enak ena
Slika 12: Faktor raztegnitve mreže v vertikalni smeri je enak dva
Za metodo mreženja Advancing front je značilno, da kljub enostavni osnovni ideji vsebuje kompleksne detajle, ki se odražajo predvsem pri oblikovanju kriterijev za izbiro točk novih elementov. Zato je potrebno pri programiranju tem detajlom nameniti največ pozornosti in tako zagotoviti čimvišjo kvaliteto mreženja tudi pri neugodnih oblikah območij.
Metoda je zaradi obsežnega kontroliranja pri postavljanju novih elementov počasna, kvaliteta in rezultati mreženja pa so precej nepredvidljivi. Zato je kljub univerzalnosti uporabnost metode vprašljiva.
Pri uporabi lahko kvaliteto mreženja nekoliko izboljšamo z izbiro ustrezne kombinacije parametrov mreženja.
[1] Technical Watch Report: Mesh generation methods, Advancing front
[2] Emulacija knjižnice PHIGS, Laboratorij LECAD, marec 1997
[3] Bronštejn, Semendjajev, Musiol, Mühlig: Matematični priročnik, Tehniška založba Slovenije, Ljubljana 1997
Medvode, 29. 8. 1999, Radovan Dražumerič
Download arhiva s programom in izvorno kodo