Adaptive meshes in computer graphics and model-based simulation

Abstract

Monet luonnonlait voidaan ilmaista matemaattisesti joko yhtenä yhtälönä tai yhtälöjärjestelmänä. Erityisesti differentiaaliyhtälöiden ratkaisu on tärkeä esimerkiksi mekaniikassa, biologiassa tai kemiassa esiin tuleva ongelma. Useimmissa tapauksissa ratkaisu tällaisiin yhtälöihin on tuntematon, joten se täytyy löytää käyttäen tietokonekoodia. Koska tietokoneet toimivat rajoitetulla tarkkuudella ja tietomäärällä, tietokoneella saatu ratkaisu on vain approksimaatio yhtälön ratkaisulle. Tämän epätarkan tiedon käyttö tietokoneavusteisessa tekniikassa voi johtaa laitteen toimintahäiriöihin. Onkin tärkeää saada kuva, kuinka hyvin tietokoneella saatu tulos edustaa tarkkaa ratkaisua. Turchyn kehitti väitöstyössään uuden tekniikan arvioida elementtimenetelmäratkaisulla laskettujen approksimaatioiden tarkkuutta. Edelliseen lähestymistapaan verrattuna uusi tekniikka mahdollistaa virheen laskemisen laajemmassa luokassa tuloksia.Objektit tietokoneessa ovat edustettuina erilaisten geometristen alkiokokoelmien, esimerkiksi tetraedrin kolmioiden, avulla. Tällaista kokoelmaa kutsutaan verkoksi. Erityinen ominaisuus työssä esitellyssä virheenarviointimenetelmässä on erityisesti rakennettujen verkkojen käyttö. Verkon muokkaamisprosessia kutsutaan verkon adaptaatioksi. Verkon adaptaatiota käytetään virheen suuruuden arvioimisen lisäksi muillakin alueilla, kuten tietokonegrafiikassa.

This work presents improvements to mesh generation algorithms employed in computer graphics and numerical solution of boundary value problems of elliptic type. The first part of the thesis concerns creation of the meshes with various polygonal complexity, which are used in computer graphics to create an image of a given object. This work contributes to the analysis of the sliding window progressive meshes algorithm. Several improvements to the algorithm are suggested to solve its major problems. The first problem is the cache-coherent access to the mesh vertices; it is solved with help of heuristics-based reordering of triangles. The second problem is the excessive size of resulting datasets. It is demonstrated that the datasets can be reduced using optimization of mesh connectivity, via hierarchical data structures, and with help of special mesh operators that remove several vertices at a time.The second part of the thesis is focused on the a posteriori error estimation for finite element approximations in terms of linear functionals. Here the role of mesh generation is two-fold. First, the error value estimated with help of estimator naturally suggests mesh refinement strategy. Second, the estimator requires solving an additional adjoint problem on a mesh that does not coincide with the mesh used to solve the main problem. In order to relief the requirements for the adjoint mesh, a new method to estimate the error is developed and tested; the method not only accepts anisotropic adjoint meshes, but also does not require extra regularity of the adjoint problem solution