© Strojni{ki vestnik 49(2003)11,524-537 © Journal of Mechanical Engineering 49(2003)11,524-537 ISSN 0039-2480 ISSN 0039-2480 UDK 004.021:519.61/.64 UDC 004.021:519.61/.64 Izvirni znanstveni ~lanek (1.01) Original scientific paper (1.01) Hiter algoritem za poenostavljanje in obnovitev trikotni{kih mre` za prenos rezultatov MKE preko svetovnega spleta A Fast Triangular-Mesh Decimation-and-Undecimation Algorithm for Transferring FEM Results via the Web Sebastian Krivograd - Gorazd Hren - Borut @alik - Anton Jezernik Prispevek opisuje učinkovit algoritem za poenostavljanje grafičnega prikaza trikotniskih mrež, dobljenih na primer pri analizah po metodi končnih elelementov (MKE). Dobljene mreže ohranjajo vse ključne značilnosti izvirnih mrež, pri čemer pa potrebujejo mnogo manj podatkov. Zato je metoda idealna za izmenjavo mrež prek ozkih komunikacijskih kanalov, kakršen je na primer svetovni splet. V uvodu najprej poudarjamo, da MKE, kot približna numerična metoda, običajno ustvarja količinsko izredno obsežne rezultate. V nadaljevanju podajamo kratek pregled znanih metod za poenostavljanje mrež, nato pa opišemo metodo z odstranjevanjem vozlišč Za pospešitev iskanja najprimernejših vozlišč, ki jih je mogoče umakniti, uporabljamo sekljalno preglednico s hevristiko. Prispevek končujemo z analizo časovne in prostorske zahtevnosti ter praktičnim primerom uporabe metode pri zmanjšanju količine podatkov za prenos rezultatov po MKE prek spleta. Praktični rezultati potrjujejo teoretično časovno zahtevnost. © 2003 Strojniški vestnik. Vse pravice pridržane. (Ključne besede: geometrija računalniška, poenostavljanje mrež, metode končnih elementov, svetovni splet) This paper describes a fast algorithm for the decimation of triangular meshes, illustrated by transferring the results of a finite-element method (FEM) analysis. The obtained meshes preserve all the key characteristics of the original meshes with considerable less data, which makes the algorithm very useful for data exchange over the web. First, the FEM is briefly described as an approximate and numerical method that mostly results in an excessive quantity of data. A brief overview of the possible approaches to data reduction for triangular meshes is given, and the solution with node elimination is presented. To speed up the search for the nodes to be removed, a hash table is applied, organized heuristically and suitable for engineering data. Finally, the paper presents an analysis of a time-and-space complexity analysis and a practical example with a reduction of FEM data results, enabling efficient transfer over the web. The practical results obtained during the testing of the FEM results’ transfer confirm the theoretical estimation of linear time complexity. © 2003 Journal of Mechanical Engineering. All rights reserved. (Keywords: computational geometry, mesh decimation, finite element methods, world wide web) 0 UVOD Inženirji pri svojem delu uporabljamo različne numerične metode za izvajanje analiz in preračunov komponent, kakršna je na primer metoda končnih elementov (MKE). MKE je približna numerična metoda za reševanje problemov, ki jih je mogoče opisati s sistemom diferencialnih enačb. Osnovna zamisel je razdelitev telesa na končno število elementov, omejenih z vozlišči, ki so povezani v celotni sestav z enačbami stanj in robnimi pogoji. Vrednosti v vozliščih so posledica globalnih sprememb telesa Matrika sistema je sestavljena iz linearnih enačb, ki jih je mogoče z uporabo računalnika preprosto rešiti, je pa po obsegu zelo velika Linearne probleme lahko rešimo v enem zagonu, pri nelinearnih pa je treba upoštevati spremembe geometrije in lastnosti materiala med obremenitvijo. Rešujemo jih iterativno dokler ni dosežen predpisani zaključni kriterij. Pri trdnostnih preračunih so rezultati izraženi kot pomiki in 0 INTRODUCTION Many computational methods, such as the finite-element method (FEM), are well developed, implemented and used in daily engineering activities. The FEM is actually an approximate mathematical method for solving problems that can be solved with differential equations. The main idea is to break a problem into a large number of elements, determined by nodes, which are then connected via global state information and boundary conditions. The global problem is transformed as linear equations into a matrix form, which can be easily solved by a computer. The result is a change of the global state for each node. Linear problems, like structural problems, can be solved with a single solver run. Non-linear problems, where a change of the geometry of the material properties during the load application has to be con- 1 BnnBjfokJ][p)l]Olf|ifrSO | | ^SSfiflMffiC | stran 524 Krivograd S., Hren G., @alik B., Jezernik A.: Hiter algoritem - A Fast Algorithm napetosti v posameznem vozlišču mreže elementov. V slikovni obliki so pomiki in napetosti predstavljeni z barvnimi razredi za upodabljanje porazdelitve in koncentracij napetosti in deformacij po strukturi. Računalniški prikaz rezultatov v sistemih za preračune je zelo kakovosten. V prispevku ne bomo govorili o vedno aktualni problematiki optimalnega generiranja mrež, pač pa o možnostih prenašanja in predstavljanja rezultatov izračunov prek spleta. Pri sočasnem inženiringu oziroma sodelovanju udeležencev proizvodnega postopka se velikokrat pojavi problem prenašanja rezultatov med inženirji ali drugimi udeleženci zaradi vrednotenja rezultatov. Za izmenjavo podatkov obstaja nekaj utečenih poti: - vsi udeleženci imajo in znajo uporabljati enak sistem za analize po MKE (kar je redko), - mogoča je neposredna sprememba podatkov med različnimi sistemi za MKE (večinoma drago), - obstajajo nevtralne oblike, ki jih lahko različni sistemi uvažajo ali izvažajo (izguba informacij), - rezultate lahko izmenjujemo v obliki zaslonskih slik (zelo omejene možnosti predstavitve, posebej pri 3D analizah, nezmožnost geometrijskih preoblik, lastne nastavitve barv in pogledov). Pri tem poudarjamo, da je izmenjava podatkov mogoča med mnogimi sistemi (model MKE z mrežo elementov in robnimi pogoji), le redko pa je mogoča izmenjava rezultatov Vsekakor lahko trdimo, da glavni problem pri pošiljanju podatkov o modelih MKE prek spleta (še posebej pri rezultatih) pomeni količina podatkov. Celo preproste mreže MKE lahko vsebujejo nekaj tisoč vozlišč in v vsakem vozlišču je več vrednosti. Število teh vrednosti je odvisno od števila prostostnih stopenj uporabljenih elementov. Pri nelinearnih problemih se število podatkov še bistveno poveča. Prav velika količina podatkov, ki ustvarjajo rezultate, je glavna ovira pri prenosu le-teh prek računalniškega omrežja. Inženirjem so v večini primerov zanimivi dovolj natančni rezultati deformacij in zgostitev napetosti v kritičnih območjih, medtem ko so drugi podatki manj pomembni. Prav v takšnih primerih se izkaže naš algoritem, ki razumno zmanjša količino potrebnih podatkov za vizualizacijo rezultatov analize po MKE. Poenostavljanje trikotniških mrež lahko opravimo na več načinov glede na to, katere elemente odstranjujejo iz mreže: - Poenostavljanje vozlišč. Poenostavljanje vozlišč je najpogostejše in temelji na Schroederjevem poenostavitvenem postopku [1]. Vozlišča najprej ovrednotimo in jih nato odstranimo iz mreže, glede na njihovo pomembnost. Pregled metod najdemo v [2]. - Poenostavljanje robov. V tem primeru odstranjujemo pred tem ovrednotene robove [3]. Ena najboljših metod s poenostavljanjem robov temelji na najmanjši vsoti kvadratov napak, ki sta jo predlagala Gerland in Heckberg [4]. sidered, are solved in more than one step, mostly iteratively, using the results of the last run as the start value for the next run, until certain exit condi-tions are fulfilled. In this paper we will present the sharing and presentation of results over the web. With today’s concurrent engineering and the need for coopera-tion between production participants, problems arise when one is trying to share results with other people, in some cases other engineers, looking for comments or evaluating results. The existing possibilities for sharing results are as follows: - Both participants have the same FEM system and know how to use it (this is a rare situation). - Using a direct translation program between two different systems, produced by FEM systems’ providers (this is usually expensive). - Using neutral meta-files that different systems can export and import (this can result in information loss). - Sending screen shots represents a very limited visu-alisation capability, especially for 3D models. It should be pointed out that many systems can share pre-processing data (a FEM model with mesh and boundary conditions) and a few results. The major bottleneck when transferring data via the web is the quantity of data. Even a simple FEM mesh can result in a few thousand nodes and in every node we have a few values of the results, depending on the type of elements and the number of DOF in the nodes. If we consider non-linear problems, which are solved in more than one step, the quantity of data increases significantly. Usually, at the nodes, the sca-lar values are given. Frequently, a huge amount of obtained data slows the computer-supported analy-sis and increases the time and network capacity needed for data transfer. Usually, engineers are look-ing for sufficiently accurate results in their areas of interest and the remaining data are less significant. Therefore, these less important data can be elimi-nated without significantly damaging the investiga-tion. At this point our algorithm makes an apearance and dracstically reduces the quantity of results. Many approaches to triangular-mesh decimation have been developed. Roughly, they can be divided according to the elements they are taking from the mesh: - Node decimation methods are the most frequently used and are based on the Schroeder simplification algorithm [1]. The nodes are evaluated, and they are incrementally removed from the mesh according to their importance. There are various techniques proposed, and they differ in terms of how the nodes are evaluated and what type of triangulation is required [2]. - Edge decimation methods eliminate edges, according to the evaluation [3]. One of the best edge decimation methods, based on a quadratic error matrix, was proposed by Garland and Heckberg [4]. | lgfinHi(s)bJ][M]lfi[j;?n 0311 stran 525 I^BSSIrTMlGC Krivograd S., Hren G., @alik B., Jezernik A.: Hiter algoritem - A Fast Algorithm - Poenostavljanje trikotnikov. V tem primeru naj bi algoritem odstranjeval trikotnike, vendar praktične izvedbe tega postopka niso znane. V prispevku predstavljen algoritem temelji na dveh postopkih poenostavljanja trikotniških mrež. Franc in Skala ([5] in [6]) sta uporabila vzporedni algoritem s sekljalno preglednico, s čimer sta pospešila iskanje vozlišč, ki jih je treba odstraniti. Njuna metoda temelji na kombinaciji odstranjevanja vozlišč in robov, tako da najprej izbereta najprimernejše vozlišče in nato poiščeta med robovi, ki se stikajo v njem, najkrajšega, ki ga odstranita. Naš algoritem uporablja metodo za poenostavljanje vozlišč, kakor jo je predstavil Schroeder [1], za pospešitev pa sekljalno preglednico. Vsebuje tudi inverzno metodo, to je možnost obnovitve izvorne trikotniške mreže. 1 ALGORITEM POENOSTAVLJANJA Algoritem za poenostavljanje trikotniških mrež sestoji iz naslednjih korakov: 1. ovrednotenje vseh vozlišč glede na izbran kriterij in njihova razvrstitev v sekljalno preglednico; 2. izbira najprimernejšega vozlišča z uporabo sekljalne preglednice (na primer vozlišče v na sliki 1a); 3. odstranitev vozlišča iz trikotniške mreže; 4. odstranitev vseh trikotnikov, ki so se stikali v odstranjenem vozlišču (slika 1b); 5. omreženje področja, iz katerega smo odstranili trikotnike (slika 1c); 6. ponovno ovrednotenje neposrednih sosedov odstranjenega vozlišča (vozlišča v, vk, v, v, v na sliki 1c); 7. vračanje na korak 2, dokler ni izpolnjen končni kriterij. 1.1 Ovrednotenje vozlišč Pred postopkom poenostavljanja moramo ovrednotiti vsa vozlišča. Ovrednotenje lahko opravimo na več načinov, na primer: - Triangle decimation methods eliminate one or more triangles. However, the approaches using this possibility have not yet been reported. The presented algorithm combines two approaches during mesh decimation. Franc and Skala ([5] and [6]) used a hash table in a parallel environment for speeding up the search for the most suitable node to be removed. They combined node and edge removal: first, the most suitable node is selected, and then from the edges incident to that node, the shortest one is contracted. Our algorithm uses the pure node decimation proposed by Schroeder [1], introducing the hash table as the acceleration technique. The undecimation in our algorithm represents an additional feature that enables an incremental reconstruction possibility for the original mesh, which makes it very suitable for engineering applications. 1 THE DECIMATION ALGORITHM The algorithm for triangular-mesh decimation consists of the following steps: 1. 2. 3. 4. 5. 6. 7. Evaluation of all the nodes according to a chosen evaluation criterion and arranging them into a hash table. Selecting the most suitable node using the hash table (for example, node vi in Fig. 1a). Removing the node from the triangular mesh. Removing all the triangles incident on the removed node (Fig. 1b). Triangulating the area from where the triangles have been removed (see Fig. 1c). Re-evaluation of the nodes incident on the removed node (nodes v , m, vn in Fig. 1c). Returning to step 2 until the termination criterion is met. 1.1 Evaluation of nodes Before the decimation process starts, the nodes have to be evaluated. The evaluation can be done using different criteria, for example: a) b) Sl. 1. Poenostavljanje vozlišč Fig. 1. Node decimation c) 1 BnnBjfokJ][p)l]Olf|ifrSO | | ^SSfiflMlGC | stran 526 Krivograd S., Hren G., @alik B., Jezernik A.: Hiter algoritem - A Fast Algorithm - Ustvarimo vektor v., ta povezuje vozlišče v, ki ga želimo ovrednotiti, in njegovo sosednje vozlišče v (slika 2a). Zatem izračunamo kot med tem vektorjem in ravnino XY (y j). Povprečna vrednost vseh kotov y , ki so določeni z vozliščem v, je faktor ovrednotenja ev tega vozlišča. - Faktor ovrednotenja evi vozlišča v je povprečna vrednost razlik skalarnih vrednosti fi med izbranim vozliščem v in njegovimi sosedi (sl. 2b). 1.2 Izbira vozlišča za odstranitev Odstranjeno vozlišče naj bi povzročilo najmanj šo napako v predstavitvi podatkov. Zaradi tega bi morali vedno odstraniti iz trikotniške mreže vozlišče z najmanjšim faktorjem ovrednotenja evi. Po tem opravilu se faktor ovrednotenja ev spremeni vsem vozliščem, ki so neposredni sosedi brisanega vozlišča, zato moramo ta vozlišča ponovno ovrednotiti. V naslednjem koraku ponovno potrebujemo vozlišče z najmanjšim faktorjem ovrednotenja ev. Iskanje vozlišča z najmanjšim faktorjem ovrednotenja bi lahko najlažje opravili z iskanjem skozi celotno množico vozlišč. Na žalost ta metoda deluje s časovno zahtevnostjo O(n2) in zelo upočasni algoritem. Druga možnost, da najprej uredimo vsa vozlišča glede na njihov faktor ovrednotenja ev in nato glede na spremenjene faktorje spreminjamo njihove položaje, deluje v pričakovani časovni zahtevnosti O(n log n). Z uporabo sekljalne preglednice dosežemo nespremenljivo časovno zahtevnost O(1). V tem primeru moramo omejiti zahtevo po izbiri vozlišča, ki ima najmanjši faktor ovrednotenja ev. Sedaj ne zahtevamo več, da vedno uporabimo vozlišče z najmanjšim faktorjem ovrednotenja ev, ampak se zadovoljimo z vozliščem, ki ima dovolj majhen faktor ovrednotenja tako, kakor pojasnjujemo v nadaljevanju. Število vstopov m v sekljalno preglednico določimo z naslednjo hevristično formulo: - Vector vi,j connecting the examined node vi and its neighbouring node vj is formed (see Figure 2a). The angle between this vector and the xy plane is calculated (gi,j). The average value of all angles gi,j defined by node vi is used as the evaluation value evi. - The average difference of the scalar values fi between the examined node vi and the neighbouring nodes is used as the evaluation value evi (Figure 2b). 1.2 Selection of a node to be removed The removed node should cause the smallest possible change in the data representation. Therefore, the node with the smallest evaluation value evi should be selected and removed from the mesh. After this, the evaluation values evi of the neighbouring nodes have to be estimated again. For the next iteration step, the algorithm again needs the node with the smallest evi. Walking through the set of remaining nodes, and selecting the one with the smallest evi is an easy way to perform the task. Unfortunately, this method works in O(n2) time and slows down the algorithm significantly. The second possibility is first sorting all the nodes according to evi and then adjusting their position in the sorted array according to the changed evi, which works, as expected, in O(n log n) time. The constant expected time complexity can be achieved by introducing a hash table. However, the condition of selecting the node with the smallest evi has to be relaxed slightly. The nodes are organised in the hash table according to their evaluation values evi. The number of entries m into the hash table has been determined by the following heuristic: k >0 (1), a) b) Sl. 2. Ovrednotenje vozlišč Fig. 2. The evaluation of nodes Krivograd S., Hren G., @alik B., Jezernik A.: Hiter algoritem - A Fast Algorithm kjer k pomeni uporabniško podano stalnico. Ker je v večini tehničnih uporab faktor ovrednotenja evi porazdeljen po eksponentnem zakonu, izračunamo meje intervalov dj, 0 < j < m, v sekljalni preglednici z naslednjo enačbo: where k is the constant given by the user. As in engineering applications, the distribution of the evi often follows the exponential law. The boundaries of the intervals dj, 0 < j < m, in the hash table are determined by the following equation: dj = evsum - evln •ln (1 + Dev - j ¦ evD 0