Interactive cutting of finite elements based deformable objects in virtual environments [Elektronische Ressource] / vorgelegt von Lenka Jeřábková

Sujets

• Informatik

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2007
• Nombre de lectures: 15
• Langue: English
• Poids de l'ouvrage: 3 Mo

Extrait

Interactive Cutting of Finite Elements
based Deformable Objects in Virtual
Environments
Von der Fakultät für
Mathematik, Informatik und Naturwissenschaften
der Rheinisch-Westfälischen Technischen Hochschule Aachen
zur Erlangung des akademischen Grades
einer Doktorin der Naturwissenschaften genehmigte Dissertation
vorgelegt von
Ing.
ˇLenka Jerábková
aus Zlín, Tschechische Republik
Berichter: Prof. Christian Bischof, Ph.D.
Prof. Dr.-Ing. Matthias Teschner
Tag der mündlichen Prüfung: 14.November 2007
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfügbar.ABSTRACT
Thereisawiderangeofvirtualreality(VR)applicationsthatbenefitfromphysically
based modeling, such as assembly simulation, robotics, training and teaching (e.g.,
medical, military, sports) and entertainment. The dynamics of rigid bodies is well
understoodandseveralopensourceaswellascommercialphysicsenginessupporting
articulated rigid bodies and particle systems are available. On the other hand,
the simulation of deformable bodies is an objective of current research. The main
application areas of deformable objects simulation in computer graphics and VR are
the simulation of cloth and medical simulation. The challenge of VR applications is
the real time simulation requirement. The raising computational power of the last
decades allowed for adapting selected methods known from engineering sciences for
interactive simulation. The simulation of cutting is especially challenging though,
as most methods suffer from both performance and stability issues. Although a
number of approaches have been presented over the last decade, the problem has
not been solved satisfyingly, yet.
This thesis presents methods for an interactive simulation of finite elements based
deformable objects as used, e.g., in VR surgical simulators. The main objectives
of such simulators are stability and performance of the employed methods allowing
for an interactive object manipulation including topological changes in real time. A
novel method for interactive cutting of deformable objects in virtual environments
is presented. The key to this method is the usage of the extended finite elements
method (XFEM). The XFEM can effectively model discontinuities within an FEM
mesh without creating new mesh elements and thus minimizing the impact on the
performance of the simulation. The XFEM can be applied to advanced constitutive
models used for the interactive simulation of large deformations. Moreover, an
analysis of mass lumping techniques, showing that the stability of the simulation
is guaranteed even when small portions of the material are cut is presented. TheXFEM based cutting surpasses the currently most widely used remeshing methods
in both, performance and stability and is suitable for interactive VR simulation.
Further, a software architecture for physical simulation of deformable objects in VR
applications is proposed. The framework is suitable for the creation of complex VR
applications as, e.g., a virtual surgical trainer. It uses thread level task paralleliza-
tion for the concurrent execution of visualization, collision detection, haptics and
deformation. Moreover, a parallelization approach for the deformation algorithm,
which is the most computationally intensive part is proposed. The presented so-
lution based on OpenMP requires only minimal changes to the source code while
achieving a speedup comparable to the results of more sophisticated approaches.
The presented framework benefits from the current developments in the computing
industry and allows an optimal utilization of multicore CPUs.ZUSAMMENFASSUNG
Es gibt eine breite Skala von Anwendungen der virtuellen Realität (VR), die von
Methoden der physikalisch basierten Modellierung profitieren können. Als Beispiele
können Montagesimulation, Robotik, Training und Lehre (z.B. in der Medizin, im
Militär oder im Sport) und Unterhaltung genannt werden. Die Dynamik von Fest-
körpern und Partikeln wurde in der Vergangenheit gut erforscht und wird zur Zeit
von mehreren Open Source als auch kommerziellen Softwarepaketen unterstützt.
Im Gegensatz dazu ist die Simulation deformierbarer Objekte Gegenstand aktueller
Forschung. Die Hauptanwendungsgebiete für die Simulation deformierbarer Objekte
in Computergraphik und VR ist die Stoff- und Kleidungssimulation sowie die medi-
zinischenAnwendungen.DieEchtzeit-AnforderungvonVRAnwendungenstellteine
große Herausforderung dar. Dank steigender Rechenleistung in den letzten Dekaden
ist es möglich bestehende Methoden aus den Ingenieurswissenschaften zu überneh-
men oder für interaktive Simulation zu adaptieren. Die Simulation vom Schneiden
ist dennoch besonders anspruchsvoll, da die meisten Methoden zu Performanz- oder
Stabilitätsproblemen führen. Obwohl in den letzten Jahren verschiedene Lösungs-
ansätze präsentiert wurden, wurde das Problem nicht zufriedenstellend gelöst.
Diese Arbeit präsentiert Methoden für eine interaktive Simulation deformierbarer
Objekte, basierend auf der Methode der finiten Elemente, die z.B. in einem virtuel-
lenChirurgieSimulatorVerwendungfinden.DieHauptzieleeinessolchenSimulators
sind die Stabilität und Effizienz der eingesetzten Methoden um eine interaktive Ma-
nipulationeinschließlichtopologischerVeränderungeninEchtzeitzuermöglichen.In
der vorliegenden Arbeit wird eine innovative Methode zum Schneiden deformierba-
rer Objekte in virtuellen Umgebungen präsentiert. Diese Methode basiert auf der
erweiterten Methode der finiten Elemente (engl. extended finite elements method,
XFEM). Mit Hilfe von XFEM können Diskontinuitäten in einem FE-Netz effizient,
ohne die Erzeugung neuer Elemente, modelliert werden, wodurch der Einfluss aufSimulationsleistung minimiert wird. Die XFEM kann mit verschiedenen Materialm-
odellen kombiniert und somit auch für die interaktive Simulation großer Deforma-
tionen eingesetzt werden. Des Weiteren wird die Analyse verschiedener Methoden
der Diagonalisierung der Massenmatrix präsentiert und gezeigt, dass die Stabilität
der Simulation unabhängig von Lage und Menge des abgeschnittenen Materials ge-
währleistet ist. Die XFEM basierte Methode übertrifft die zur Zeit am häufigsten
eingesetzten remeshing Methoden sowohl in Effizienz als auch in der Stabilität und
ist somit für interaktive VR Simulation besonders geeignet.
WeiterhinwirdeineSoftwarearchitekturzurSimulationdeformierbarerObjektevor-
geschlagen. Das Rahmenwerk eignet sich zur Erstellung komplexer VR Anwendun-
gen wie, z.B., eines virtuellen chirurgischen Trainers. Die nebenläufige Ausführung
von Visualisierung, Kollisionserkennung, Kraftrückkopplung und Deformation wird
mittels Thread-Level Parallelisierung realisiert. Außerdem wurde ein Parallelisie-
rungsansatz für den Deformationsalgorithmus, welcher den rechenintensivsten Teil
derAnwendungdarstellt,entworfenundrealisiert.DiepräsentierteaufOpenMPba-
sierte Lösung erfordert minimale Änderungen des Quellcodes, während gleichzeitig
ein Speedup erreicht wird, der vergleichbar mit den Ergebnissen anspruchsvollerer
Ansätzeist.DasvorgestellteRahmenwerkprofitiertvondergegenwärtigenEntwick-
lungderComputerindustrieundermöglichteineoptimaleAusnutzungvonMulticore
CPUs.DANKSAGUNG
Ich möchte mich an dieser Stelle bei allen bedanken, die dazu beigetragen haben,
dass ich mich während meiner Zeit in Aachen wohl gefühlt und mich nicht nur
beruflich, sondern auch persönlich, weiterentwickelt habe.
An erster Stelle gilt mein Dank dem Leiter der VRGruppe am Rech en- und Kom-
munikationszentrum der RWTH Aachen, Dr. Torsten Kuhlen, dafür, dass er mich in
seiner Gruppe aufgenommen und während der gesamten Zeit unterstützt hat. Für
tatkräftige Unterstützung, fruchtbare Diskussionen und Anregungen danke ich allen
meinen Kollegen, studentischen Hilfskräften und Diplomanden, insbesondere Ingo
Assenmacher, Gereon Frey und Nguyen Huu Hoa. Für Einblicke in die Untiefen der
Methode der finiten Elemente danke ich Jakub Jeřábek, Dr. Rostislav Chudoba und
Dr. Thomas Fries. Für die Zusammenarbeit an der Parallelisierung meines Codes
bedanke ich mich bei Christian Terboven und Samuel Sarholz.
Des Weiteren danke ich Prof. Christian Bischof dafür, dass er mir die Möglichkeit
zur Promotion an seinem Institut eröffnete und mir die Teilnahme an zahlreichen
internationalen Konferenzen ermöglicht hat. Mein herzlicher Dank gilt auch Prof.
Matthias Teschner, der sich als Zweitgutachter zur Verfügung gestellt hat.
Abschließend möchte ich mich bei meinen Eltern, meinem Bruder Jakub und mei-
nem Freund Ingo für das Vertrauen, die Geduld und die Liebe, die sie mir immer
geschenkt haben, bedanken.CONTENTS
1 Introduction 3
1.1 Related Work: VR in Medicine . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Soft Tissue Deformation . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Performance Optimizations . . . . . . . . . . . . . . . . . . . 7
1.1.3 Cutting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Contributions and Outline . . . . . . . . . . . . . . . . . . . . . . . . 11<