A Volume Preserving Model for Biomechanically-based - SEE-KID

Transcrição

A Volume Preserving Model
for Biomechanically-based
Muscle Volume Deformation
Michael Lacher
September 10, 2001
ii
Eidesstattliche Erklärung
Ich erkläre, dass ich die Diplomarbeit selbstständig verfasst, andere als die
angegebenen Quellen und Hilfsmittel nicht verwendet und mich auch sonst
keiner unerlaubten Hilfe bedient habe.
Hagenberg, im September 2001
Michael Lacher
iv
ABSTRACT
v
Abstract
This thesis uses 3D reconstructions of MR image data to simulate extra-ocular
muscles at different activation levels.
Traditionally, MR image data has been used to generate static 3D models
of muscles and organs. It is desirable to display such models of extra-ocular
muscles in the SEE-KID project, an ongoing work to create an interactive eye
motility diagnostics and surgery system, at the Department of Software Engineering for Medicine at the Polytechnic University in Hagenberg. However, in
this program the current length and activation of a muscle varies as the user
rotates the eye or changes the insertion points of muscles. Because of this, a
static muscle model is inappropriate.
To overcome this flaw, this thesis uses multiple reconstructions of the same
muscle, at different activations, to build a dynamic model of the muscle. This
model can then be used to generate a muscle volume and surface representation
for any given activation and length.
The model consists of two main parts. The first is the path of the muscle,
which is stored as a set of cubic Hermite splines. The second part is a radius
function which defines the muscle surface around this path. Using this method
both the muscle volume and surface are stored by the same function. Numeric
integration and scaling of the radius function is then used to ensure the volume
is preserved during the interpolation of the dynamic representation.
This thesis also contains the optimized rendering of the resulting muscle
volume. It employs OpenGL as a rendering platform to achieve a broad compatability with existing systems.
vi
KURZFASSUNG
vii
Kurzfassung
Diese Arbeit verwendet 3D-Rekonstruktionen von MR-Bilddaten um Augenmuskeln in verschiedenen Aktivierungszuständen zu simulieren.
MR-Bilddaten werden bereits jetzt in der Medizin verwendet um statische
3D-Modelle von Muskeln und Organen zu konstruieren. An der Abteilung für
Software Engineering für Medizin der Fachhochschule Hagenberg entstand der
Wunsch derartige Modelle von Augenmuskeln im SEE-KID Projekt darzustellen, einem längerwährenden Projekt zur Entwicklung eines interaktiven Augenfehlstellungsdiagnose und -operationssystems. Jedoch verändert sich die
aktuelle Länge und Aktivierung der Muskeln in diesem Programm wenn der
Benutzer das Auge rotiert oder die Insertionspunkte der Muskeln verändert.
Aus diesem Grund ist ein statisches Modell nicht verwendbar.
Um diesem Problem entgegenzuwirken, verwendet diese Arbeit mehrere Rekonstruktionen des selben Muskels bei unterschiedlichen Aktivierungszuständen
um ein dynamisches Modell des Muskels zu erstellen. Dieses Modell kann dann
benutzt werden um eine Volums- und Oberflächenrepräsentation für eine beliebige Aktivierung und Länge zu erzeugen.
Das Modell besteht im Wesentlich aus zwei Teilen. Der erste ist der Pfad des
Muskels welcher als eine Menge von kubischen Hermite-Splines gespeichert wird.
Der zweite Teil ist eine Radiusfunktion, welche die Muskeloberfläche rund um
diesen Pfad definiert. Mittels dieser Methode werden sowohl die Oberfläche des
Muskels als auch sein Volumen über die selbe Funktion definiert. Numerische
Integration und Skalierung der Radiusfunktion werden benutzt um das Volumen
während der Interpolation der dynamischen Repräsentation konstant zu halten.
Diese Arbeit umfasst ebenfalls die optimierte Darstellung des berechneten
Muskelsvolumens. OpenGL wird als Renderplattform eingesetzt um eine breite
Kompatibilität mit existierenden Systemen zu verwirklichen.
viii
ACKNOWLEDGEMENTS
ix
Acknowledgements
I want to thank all those who made this work possible. First of all I want to
express my gratitude towards Michael Buchberger who was my guide through
this work and also, with infinite patience, explained to me the medical details
of the eye and its mechanics as well as the internal details of the SEE-KID
project. Next I want to thank Herwig Mayr, who not only made this work
possible in the beginning but also took the task of correcting and grading it.
Furthermore I want to thank all the colleagues at the FORTE institude, you
were great people to work with.
Also I want to express my thanks to all my friends during the 4 years of
study at the Polytechnic University in Hagenberg, namely Martin “Scorpion”
Brandhuber, Elisabeth “Shiva” Fischer, Andreas “Sir Galahad” Fischl, Klaus
“drake” Gutenbrunner, Rolf “Buddha tm” Hornasek, Christoph “Murdock”
Huter, Thomas “Bommel” Kerbl, Anita “LaVic” Oberer, Peter “calia” Peltzner,
Thomas “Heani” Reitz, Klemens “Klemens” Wallner, Thomas “White Baron”
Weihs and Christian “Wicky” Wickhoff. You made these years a time of fun
and joy.
Next in line, I want to thank all the guys from the Gryps project. The work
I did for this project helped me a great deal with this work. Also this work
gave me a wonderful hobby over the last two years. I thank you guys, and I
am proud to be part of the team and also of what we achieved in the last two
years.
Of course my thanks also go to my parents and my whole family, whithout
whom I could not be here, and whom I am really proud of.
Last, but not least I want to say thank you and greetings to my old highschool buddies, Reinhold Kainhofer, Alexander Soucek and Tobias Triffterer
whom I see way too little in these days.
Mucki
^l^
O^m!
^
T
u, h r_dst
_Ts tm
if YA
ldj
s^
hlTt Yt
j
b_
ld Tr
u T ARL if m^
_ rC
ls
^
if T w_îl C_d. _it shlt b
C_
lR t T T A^
es if T m
^ jC
_ _in Crî_
tj AdR
fl îd
în
_ m
^ td p_C
trs. m^
eTt T
ub
în îprDs
_ if T A^
es if T îR^
Cn
w_îl pAR iR î
l
if T îRt if _hl
_ j, T
u Alt f_d T_s tm
în in^
wl
îb
l w^
ult if YA
ldj,
frwR
i^
b
l _in TO d^
elO AR
C.
_ bd
_ T jd hîlT îd î_
ljmD
if T îR^
Cn
pAR, f
eîm!
^
t^l
s, l
_ b^
rr_în if T j
eL if YA
ldj
x
ACKNOWLEDGEMENTS
Contents
1 Introduction
1.1 The SEE-KID Project . . . . . . . . . . . . . . . . .
1.2 A Dynamic Eye Muscle Model . . . . . . . . . . . .
1.2.1 Aspects of a Muscle Model . . . . . . . . . .
1.2.1.1 Volume Rendering . . . . . . . . . .
1.2.1.2 Volume Preserving Transformations
1.2.2 Historic Development of Muscle Models . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
2
2
3
5
6
2 Basic Notions
2.1 3D Graphics . . . . . . . . . . . . . .
2.1.1 3D Pipeline . . . . . . . . . .
2.1.2 Transformation and Lighting
2.2 Mathematics . . . . . . . . . . . . .
2.2.1 Splines . . . . . . . . . . . . .
2.3 Medical Terms . . . . . . . . . . . .
2.3.1 Bulbus and Orbita . . . . . .
2.3.2 Muscle Models . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
10
10
12
13
13
14
14
16
3 Muscle Volume Deformation
3.1 Input Data . . . . . . . . . . . . . .
3.2 Coping With the Amount of Data .
3.3 Muscle Model . . . . . . . . . . . . .
3.4 Volume Preserving Transformations
3.5 Rendering . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
19
19
21
25
27
29
4 System Design
4.1 Mathematical Model . . . . . . . . . . . . . . . . .
4.2 Muscle Volume Deformation . . . . . . . . . . . . .
4.2.1 Transforming Input Data . . . . . . . . . .
4.2.2 Dynamic Muscle Volume Generation . . . .
4.2.3 Render Optimization of the Muscle Volume
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
31
31
31
34
37
5 Implementation
5.1 Input Data . . . . . . . . . . . . . .
5.2 Coping With the Amount of Data .
5.3 Muscle Model . . . . . . . . . . . . .
5.4 Volume Preserving Transformations
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
39
39
42
43
43
xi
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
xii
CONTENTS
5.5
Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6 Testing and User Reports
51
6.1 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.1.1 Verifying the Results . . . . . . . . . . . . . . . . . . . . . 51
7 Conclusion
55
7.1 Goals Achieved . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
7.2 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Literature
57
List of Figures
1.1
Comparison of conventional and pulley models . . . . . . . . . .
2.1
2.2
2.3
2.4
2.5
Rendering pipeline in DirectX 8.0
3D memory layout . . . . . . . .
Eye, overview . . . . . . . . . . .
String model . . . . . . . . . . .
Change of effect in string model .
3.1
3.2
3.3
3.4
3.5
3.6
3.7
Marching cube algorithm . . . . . . . . . . .
Marching cube classes . . . . . . . . . . . . .
Optimization of the marching cube algorithm
Intersecting planes . . . . . . . . . . . . . . .
Muscle model . . . . . . . . . . . . . . . . . .
Modified Hill-type model . . . . . . . . . . . .
Nearest neighbor vs. weighted interpolation of
4.1
4.2
Muscle model with visualization . . . . . . . . . . . . . . . . . . 32
Path and surface of the muscle . . . . . . . . . . . . . . . . . . . 34
5.1
5.2
5.3
Process of recreating muscle volume . . . . . . . . . . . . . . . . 44
Concept of the dynamic muscle . . . . . . . . . . . . . . . . . . . 45
One piece for calculating the volume . . . . . . . . . . . . . . . . 47
6.1
6.2
6.3
Dynamic muscle model . . . . . . . . . . . . . . . . . . . . . . . . 52
Dynamic muscle model with overlay of input model . . . . . . . . 53
Dynamic muscle model with overlay of MR images . . . . . . . . 53
xiii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
actual
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
12
15
17
17
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
volume
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
22
23
25
26
26
28
Chapter 1
Introduction
Whatever you can do, or dream you
can, begin it. Boldness has genius,
power and magic in it.
Johann Wolfgang von Goethe
With the advent of new, optimized graphics cards and powerful processors, three-dimensional graphics have entered the consumer market. It is now
possible to perform highly sophisticated visualizations on consumer machines,
which, a few years before, were only possible with specialized hardware. This
change of technology affects not only home users, but also business, research
and especially medical applications. It is now possible, to have complex tools
for evaluating data at a low cost and therefore providing these capabilities to a
wide range of people. This thesis concentrates on the volume preserving transformation of three-dimensional muscle models, specifically of the extra-ocular
muscle system. It will be shown that it is possible to perform such calculations
in an interactive manner on consumer machines.
This thesis was developed closely together with [Pirklbauer, 2001], which
covers the reconstruction of the three-dimensional muscle model from MR image
data.
1.1
The SEE-KID Project
This thesis does not stand alone, but is part of the SEE-KID project, a
Software Engineering Environment for Knowledge-based Interactive EyeMotility Diagnostics. This is an ongoing project at the department of Software
Engineering for Medicine of the Polytechnic University of Upper Austria, in
connection with the Austrian Ministry of Science and medical partners in
Austria, Switzerland and the United States of America.
1
2
CHAPTER 1. INTRODUCTION
The main goal of this project is to create a three-dimensional model and visualization of the human eye, which can be used to simulate eye muscle surgery.
This system can be used to evaluate possible operation strategies for a given
pathological case, as well as education and training purposes. Additionally all
cases are stored in a knowledge base, so the computer can aid the surgeon by
using this best practices database.
For more detailed information of the SEE-KID project we refer to [Buchberger and Mayr, 2000].
1.2
A Dynamic Eye Muscle Model
Currently, muscles in the SEE-KID environment are visualized as lines. While
this is suitable for displaying muscle paths and modifying insertion points, some
problems do not become apparent when only the path is drawn. In connection
with the oblique muscles there might be problems with certain insertion points,
because the muscle volumes of the musculus obliquus and one of the musculi
recti might intersect. It would therefore be desirable to display the volume of
muscles, instead of their path only. This thesis shows how eye muscles can be
visualized, by displaying activation-dependent muscle volumes. This information is important to surgeons, giving them a better preview of the results of a
treatment, and one can detect proximity problems, when two muscle volumes
would intersect each other in the simulation. This thesis presents a model that
provides a dynamic three-dimensional muscle model from a set of input images.
This model can be used to display the muscle in all states of activation with
desirable accuracy.
1.2.1
Aspects of a Muscle Model
Computer graphics have been used in industry and research from the early
stages of this field of computer research. The possibility to display and modify
graphical models on the computer without the need for a real prototype was
immediately recognized to be, both, cost and time effective. This is one reason
why the development of computer graphics was driven towards better methods
for displaying technical models and modifying them. One part of this area is the
simulation and testing of volumetric models. To be able to do this, a number of
different methods have been developed. They can be split into two categories:
• volume rendering: the storage of volumetric information and subsequent
visualization,
• volume preserving transformations: the modification of volumes in a physically meaningful manner.
1.2. A DYNAMIC EYE MUSCLE MODEL
3
In the following, a few of the most common methods are presented, along with
reasons why we did not choose to implement them in this thesis.
1.2.1.1
Volume Rendering
The difference between volume rendering and normal rendering does not lie in
the actual result that is displayed on the screen. Both methods usually display
the surface of the model. However, normal rendering methods do not store
any information about the volume of the model, they only store a definition of
the surface. Volume rendering methods, define the volume of the model, and
derive the surface from this definition. These methods are generally slower and
therefore used only when the volume data is changing frequently, or when the
definition of the surface is known only via the volume.
Most of the volume rendering methods are based on the idea of voxels. A
voxel is an acronym for “Volume Pixel” and is a logic extension of a normal pixel
into three dimensions. While a pixel is assumed to be a small rectangular area
of a two-dimensional image, a voxel is a small cuboid, and defines the smallest
possible unit in a three dimensional image. A voxel is normally a parallelepiped
and they are evenly spaced and distributed over the whole space. Each volume
in space can then be defined by voxels which lie totally or partially inside the
model. One of the major flaws of voxel models can be seen right now already:
it is an approximative model, and the error is proportional to the size of the
voxels.
Let si , i ∈ {x, y, z} be the length of a voxel in each dimension. Then the
error is e = 0.5 ∗ sx ∗ sy ∗ sz for each voxel which is partially contained in
the model in the worst case. The error per voxel scales linear to the volume
of the voxel, so if the side length is halved, in each dimension, the error is
reduced to one eighth. This however also increases the number of voxels in the
model and hence the number of partially contained voxels. In effect, the error
reduces only by 50% in the worst case. It is still possible to achieve any desired
maximum error, but the number of voxels in the model grows inversely cubic
to the accuracy. This way, accuracy is limited by memory and performance
constraints of the computer used to calculate the model.
To actually visualize an octree model, one needs to draw all contained voxels.
The simplest approach would be to transform each voxel into a cuboid surface
and render the resulting triangles. While this algorithm is reasonable, it lacks
performance, drawing the surfaces of all voxels, also those contained inside
the volume which cannot be visible, additionally it draws the surfaces of the
volume exactly as they are, which results in a rather jaggy outline of the object.
The second problem diminishes with rising accuracy, but the amount of hidden
voxels is then too big to allow suitable performance. One solution would be to
use extremely small voxels, so that each voxel, in essence, corresponds to one
pixel on the output screen. As a consequence there is no need to calculate the
surface of the voxel, as it will be rendered as one pixel anyway.
4
Neither of the two methods can generate correct surface normals. Surface
normals would have to be reverse engineered from the resulting set of surfaces/pixels. Without surface normals however, a useful lighting of the model
is not possible. While this may not be a problem in technical design, it is a
severe drawback when trying to achieve realistic imaging. To accommodate for
this flaw, there exists another method for generating the surfaces that actually
arose from the area of image recognition: the marching cubes algorithm. This
algorithm basically reconstructs a surface by analyzing voxels that lie on the
border of a volume. For a detailed description see Ch. 3.1. This algorithm
calculates surface normals and also smoothes out edges, introduced through
partially contained voxels. The speed of this algorithm depends on the amount
of time needed to decide if a given voxel is part of the model or not.
The direct solution of storing a list of all voxels contained in the object
leads to a linear complexity problem of classifying a voxel with respect to the
model. This can be reduced to logarithmic complexity by storing voxels in a
more efficient way in a tree structure. Each node in the tree has a maximum
of eight childs, representing a cuboid, which is partially or completely inside
the model. The leaves correspond to the actual voxels, while the internal nodes
are aggregations of those voxels. The cuboid of each internal node is split into
halves along each axis, and the resulting eight cuboids are its children, leading
to a fully expanded octreee strcture. To classify a voxel one needs to perform
the following steps:
1. See if the voxel is contained in the root node. If not then it is not part of
the model.
2. Make the root node the active node.
3. If the active node is a leaf, then the voxel is part of the model. Stop the
algorithm.
4. Determine the child that would contain the voxel.
5. If this child exists, then make the child the active node and continue with
Step 3, otherwise the voxel is not part of the model.
Steps 3 to 5 have to be performed at most k times where k is the depth of
the tree and
k ≤ log8 n
(1.1)
where n is the number of voxels in the model. Another optimization can be
achieved when using these trees to store the voxel information. Groups of eight
leaves which all lie inside the model and are all sons of the same internal node
can be removed and their parent becomes a leaf instead. This process can be
repeated until no further leaves classify for this optimization. If the original
voxels on the inside are needed for any reason (e.g. computing the volume),
then their presence or attributes can be easily derived from the parent nodes.
1.2.1.2
5
Volume Preserving Transformations
Due to the fact that most applications in computer graphics only render surfaces, they also store surface models only. As long as only non-deformable
transformations are applied, this is not a problem, because the volume is not
changed by them. If however, a model changes its shape, because it is bent
or stretched, these models cannot accurately calculate the result since they do
not know the volume of the object. If the volume and its distribution across a
model are known, then volume preserving transformations can be built. So, for
example, when a model is stretched into one direction, it would automatically
shrink in other directions. This way the model behaves much more realistic,
compared to pure surface representation.
Finite Element Method (FEM)
One of the basic methods used in the field of volume preserving transformations
is the finite element method. The basic idea is to describe a complex system
as the aggregation of small parts each of which can be simulated easily. There
are different types of elements which can compose the complex system, but the
most commonly used is a linear spring. The length of a linear spring is a linear
function of the force applied to it. For a one-dimensional spring,
f =K ∗u
(1.2)
where f is the force applied to the spring, K is the spring constant (a value
describing the stiffness of the spring) and u is the length of the spring.
This approach can be generalized in 3 dimensions by constructing “brick
elements”, elastic cuboids that behave like springs in each dimension. The
calculation now becomes
f~ = K ∗ ~u
(1.3)
where both force and displacement are three-dimensional vectors and K is a
3x3 stiffness matrix. In our case, the elements of the FEM model correspond
to the voxels in the initial configuration. As force is applied to the elements,
they are deformed so that each element still represents the same volume. It
is clear that the volume of the complete model is preserved as long as each
element preserves its volume. However, because the modules changed their
shape, they are now not necessarily parallelepipeds anymore. This breaks the
octree algorithm, and therefore a fast rendering of the object can no longer be
achieved with this method. Either a different rendering algorithm is used, or the
model is resampled into a suitable voxel space to be displayed. This combined
with the fact that FEM is slow because it has to perform the calculations for
each of the elements makes it not very suitable for real-time performance.
One advantage of the method is, however, that more calculations can be
done than only the preserving of the volume. [Zhu et al., 1997] uses the FE
6
method to build a dynamic muscle model by replacing the linear elements f~ =
K ∗ ~u with the second-order differential equation
M
∂~u
∂ 2 ~u
+C
+ K(~u)~u = f~(~u, t)
2
∂t
∂t
(1.4)
Using this representarion M describes the Mass, C the dampening and K the
stiffness of the elements. The equation is then evaluated to generate the displacement, movement and acceleration for the dynamics model. This method
is useful as it calculates and performs the volume preserving transformation in
the same step. This system is computationally even more intensive than the
static model, because solving the differential equation takes more time. Also,
this method is applicable only for voxel models. Other models would have to
be transformed into a voxel model before applying FEM.
In this thesis, the two main reasons for not using FEM are:
• The dynamic muscle model is not part of this thesis, but rather provided
by the SEE-KID project.
• The static case can be calculated using simpler methods, providing better
performance.
1.2.2
Historic Development of Muscle Models
The development of muscle models can be split into two separate areas. One
deals with the development of mathematical models, which describe the eye
and eye motility, the other provides improvement in visualizing these models,
using computer graphics or conventional models.
The first muscle model was the string model of [Krewson, 1950]. In this
model, muscles are modeled as strings, which are always pulled tight and take
the shortest path from the insertion point to their origin in the orbita. This
model is an acceptable approximation for gaze directions near the primary
position, but for other gaze directions, the point of tangency of the muscle
exhibits a very big side-slip.
Using the string model for simulating eye positions produces unwanted effects, because the muscles change the direction in which they apply their forces
in certain gaze directions. In the tape model, [Robinson, 1975] proposed to
limit the side-slip of the point of tangency and therefore stabilized the movement of the eye in extreme positions. The limitation of the side-slip was made
even greater in the restricted tape model ([Kusel and Haase, 1977]), which can
ensure a stable point of tangency for all possible gaze directions.
The tape models assume that muscles are held in place by intermuscular
membranes, which fix the muscle at the point of tangency more or less stable
to the globe. New models, however, use pulleys to describe this behavior; for
7
a reference see [Miller and Demer, 2000]. Pulleys are rings or sleeves of elastic
material which are affixed on the orbital wall. Thus, a pulley can be modeled
as a ring guiding the muscle at the point of tangency, which is connected to the
orbital wall by a series of springs. Fig. 1.1 illustrates this behavior.
Figure 1.1: Comparison of conventional and pulley models [Miller and Demer,
2000]
In the past, the globe and oculomotor system has been modeled with socalled ophtalmotropes. These are physical models, using a wooden sphere to
represent the globe and “rubber” muscles. With the advent of computer technology, the modeling of the human eye was moved more and more to the computer, because more complex and accurate models could be built. All these,
so-called biomechanical models aim at the simulation of the oculomotor system in an anatomically meaningful manner. While this is suitable for research
and education, these models do not lend themselves to easy parameterization.
Therefore it is difficult or impossible to use them for physicians to model different pathologies or to simulate surgeries.
The SEE-KID project tries to build a virtual reality environment that can
be used to display any given pathology and therefore needs to be very dynamic.
It uses a graphical model in which the anatomy of the human eye and orbita are
modeled as separate entities, all of them controlled by a mathematical model.
8
The display is less realistic to improve rendering speed and allow interactive behavior of the system. We are, however, continually improving the visual quality
of the model, to provide a better environment for the surgeon or student.
Chapter 2
Basic Notions
The known is finite, the unknown
infinite; intellectually we stand on an
islet in the midst of in illimitable ocean
of inexplicability. Our business in
every generation is to reclaim a little
more land.
Thomas Henry Huxley
As this thesis is interesting for medical applications as well as for 3D modeling purposes, the readers are expected to come from a variety of fields. To
facilitate the understanding of this thesis, this chapter contains basic knowledge needed to understand the techniques presented lateron. The information
presented here does not contain anything directly related to the problems discussed in this thesis. If you already have expertise in one or more of the areas
presented here, you may skip them without problems.
This chapter gives an overview over the basic concepts of three-dimensional
computer graphics. This is especially important as the description of the render
optimizations, later in this thesis, depends heavily on a basic understanding of
current render architecture. If the rendering part of this thesis is of no interest,
then you may skip this section.
The next section gives an overview of splines and the mathematical concepts needed; finally the last section contains the necessary medical background
needed to understand the problem area of this thesis.
9
10
2.1
CHAPTER 2. BASIC NOTIONS
3D Graphics
In the last few years, development in the area of interactive 3D graphics have
revolutionized the development, as well as the complexity, of visualizations on
the entertainment market as well as on the scientific market. The increased
power of computer hardware and newly developed techniques allow an increasingly realistic level of detail combined with short response times for true interactive presentations. The SEE-KID project utilizes some of these advanced
techniques to render calculated muscle volumes in a realistic and interactive
way.
This section is intended to give an overview of the current development
in this area and how it can be used to generate high performance computer
graphics. It covers only essential parts used to deal with the problem field of
the presented paper. If a more detailed overview of this topic is required, see
[Eberly, 2001].
2.1.1
3D Pipeline
The system layout of typical 3D rendering pipelines has changed to reflect the
development in the field of graphics. One of the most important improvements
was emphasizing the graphics-processing chip as a standalone processing unit
on consumer systems. A fully programmable CPU on the graphics controller
now handles more workload of the rendering process. This not only increases
the performance, but also makes the system more flexible.
In the beginning, the only task of the graphics controller was to hold a memory buffer with the data that is to be displayed and transfer it to the screen. The
CPU performed the whole process of rendering. This allowed great flexibility
but also meant a great deal of work because most of the things needed to be reprogrammed by the individual developer. Due to the fact that many parts of a
3D rendering engine are very similar for each implementation, 3D programming
libraries, like OpenGL, were developed to simplify the construction of graphics
applications. After these standards were accepted by the industry, the “rendering pipeline” evolved as a common model for 3D applications. This model
partitions the whole rendering process into a series of encapsulated steps, each
with defined input and output, allowing different components in the computer
to take over the workload of these parts.
Soon afterwards, hardware manufacturers began implementing parts of the
3D rendering pipeline in hardware to accelerate performance. Due to the way
the pipeline was designed, it could only perform one operation out of a number
possible for each step. This was easy to implement in hardware because each
step consisted of a fixed number of functions, each of which was implemented
in hardware. While this system allowed cheap hardware acceleration and supported the mainstream of applications, it was not suitable for special needs.
2.1. 3D GRAPHICS
11
Those had to be implemented in software, without any acceleration at all. Accounting this problem, nVidia, in cooperation with Microsoft, has developed a
new pipeline layout and accompanying chipset, which is fully programmable.
In this design the Pipeline mainly consists of two parts, the transformation and
the rasterizer. The transformation part is in essence a 4-element vector computer, specialized for transforming 4 dimensional vectors with 4x4 matrices.
Thus it has all the possibilities needed to transform 3D geometry and perform
lighting calculations. The rasterizer takes the output of the transformation and
convertes the geometry into pixels on the screen. It is optimized for standard
arithmetical operations and blending functions.
Figure 2.1: Rendering pipeline in DirectX 8.0 [Microsoft, 2001]
Both parts have their own assembly language that let the user program
almost any effect for these parts. Because they are programmed in assembler
they can be compiled to run on the normal CPU as well as on special hardware. State of the art graphics accelerators combine the flexibility of a fully
programmable design with the simplicity of the 3D pipeline. Fig. 2.1 shows
how the rendering pipeline is implemented in DirectX 8.0 from Microsoft. This
design already incorporates the new programmable pipeline, but also allows
programs to use the older fixed function pipeline layout.
12
2.1.2
Transformation and Lighting
In the context of 3D computer graphics, hardware processing, as opposed to
software processing, means that the computation is not performed by the CPU
but by some specially designed chip on the graphics controller.
While the most important performance optimization in interactive graphics,
(“do only draw as much as you absolutely need to”) is also true for hardware
transformation and lighting, there are several other aspects of program design
which can greatly increase rendering speed. The most important aspect is the
layout of the data in memory. See Fig. 2.2 for the following explanations.
Figure 2.2: 3D memory layout
With software processing it was most important to place the data in a
memory part that was quickly accessible by the CPU. This was normally an
area in the main memory which was cacheable by the CPU (1). Because the
memory was easily accessible by the CPU it could be set up for read/write
access without performance penalty. Also the layout of data in memory can be
set up in any way suitable for the application, although aligning the data in a
serial manner can increase performance through caching effects.
The next step in hardware acceleration was to implement the rasterization
part of the fixed function pipeline on the graphics chip. In this scenario the best
memory location for the geometry data is still the cacheable main memory, but
the transformed geometry needs to be sent to the controller and, thus, should
either be stored directly in memory on the graphics controller or in memory
which is quickly accessible by the controller (2). The same is true for textures.
For best performance textures are created directly in video memory on the
graphics controller. But as this memory is typically limited, they are created
in Accelerated Graphics Port (AGP) memory (3) and are sent to the card as
needed.
2.2. MATHEMATICS
13
The next step is hardware-accelerated transformation and lighting. In this
case, the graphics controller performs all steps of the 3D rendering. Thus also
the input data needs to be set up in a memory area that is quickly accessible
by the graphics controller. This method brings one major problem: These
memory areas typically have very slow read access. Therefore they are not
suitable for storing data with which the application is working. Because the
video and AGP memory is limited, the geometry data should not be interleaved
with application data. This way, if applications need dynamically generated or
deformed geometry, they have to maintain two copies of the data. One in system
memory, where it can be processed and modified by the program as needed, and
one in video or AGP memory. The second copy is most often referred to as the
vertex buffer. It contains only the corner points of all the polygons that define
the geometry to render, along with color information and texture coordinates
for that point. These vertex buffers usually have write-only access for the CPU
and are synchronized with the system memory copy each time the geometry
changes. To save additional space and processing time, vertices that are used
more often are stored only once and referred to by indices. This is especially
important as the chipsets often implement a post-transformed vertex cache.
Hereby, the transformed vertices are stored in a cache and, if the same vertex is
retransformed, then the cached copy is used instead of transforming the vertex
again. This way a properly ordered vertex buffer can greatly increase rendering
performance.
2.2
Mathematics
As this thesis is presenting a method which tries to be not only accurate but
also optimized for computerized calculation, it is necessary to keep a simple
mathematical formulation. Especially symbolic computation is not suitable,
thus numerical methods must be used. Due to this, most calculations in this
thesis do not require complex mathematical subjects.
However a method for representing arbitrary curves in three-dimensional
space is needed. Splines are an excellent way to represent curves and need little
computational effort. Their definition by a few parameters makes it easy to
store and manipulate them. The basics needed for this thesis are laid out in
this section. For a more detailed explanation we recommend [Mortenson, 1999]
and [Jordan and Smith, 1996].
2.2.1
Splines
Splines are a way to approximate functions whose exact definition is unknown.
They are normally defined be a series of conditions. This thesis uses cubic
Hermite Splines to define the muscle path. Hermite splines are defined by 4
parameters: start- and endpoint, and additionally the tangents (i.e. the first
14
derivative) in these points [Mortenson, 1999]. If we name these parameters
p0 , p1 , t0 , t1 respectively, we can use the following representation:
h(0) := p0
(2.1)
0
h (0) := t0
(2.2)
h(1) := p1
(2.3)
0
h (1) := t1
(2.4)
To calculate h, we define h(x) := ax3 + bx2 + cx + d. This leads to the
following correlation of the coefficients with the parameters:

 
p0
0 0
 p1   1 1

 
 t0  =  0 0
t1
3 2
0
1
1
1
By calculating the inverse of the matrix,
the parameters:
  
a
2 −2 1
 b   −3 3 −2
 =
 c   0
0
1
d
1
0
0

a
1
 b
1 

0  c
0
d




(2.5)
we can get the coefficients from

1
p0


1   p1
0   t0
0
t1




(2.6)
The reason, why hermite splines are used instead of cubic polynomials is
that continuity is achieved more easily with splines. Simple continuity is given
when end- and start points of two splines are the same. If the tangents in the
end and start point are the same then the first derivations are continuous.
2.3
Medical Terms
Special conditions of the extra-ocular muscle system, with respect to skeletal
muscles, have strong influence on the way the underlying work of this thesis
was designed and on the algorithms chosen. It is therefore vital to have a basic
background in the anatomy of the eye and its surrounding structures. Equally
important is an overview of historic developments of models that are used to
describe the rotation of the eye together with forces of the muscles.
2.3.1
Bulbus and Orbita
Fig. 2.3 shows an overview of the right eye. It depicts an orbital cut showing
the bulbus, muscles and the orbita. The oculomuscular apparatus consists of
six muscles. Four of them are straight muscles:
2.3. MEDICAL TERMS
15
Figure 2.3: Eye, overview
• musculus rectus superior,
• musculus rectus inferior,
• musculus rectus medialis,
• musculus rectus lateralis.
All originate at the anulus tendineus communis, a small ring of sinews at the
end of the orbita. From there the muscle follows a straight path to the bulbus
and inserts before the equatorial plane of the eye. Their functions are to turn
the bulbus up-, down-, in- and outward respectively.
In addition there are two diagonal muscles:
• musculus obliquus superior,
• musculus obliquus inferior.
Like the straight muscles, the m. obl. superior also has its origin at the anulus
tendineus communis, but follows the orbita wall to a muscular trochlea. From
there, it takes a straight path to the insertion point, directly behind the m.
rec. superior. The m. obl. inferior has its insertion point behind the m. rec.
lateralis. From there it leads to its origin in the front part of the orbita, near
the nasal bone, passing across the m. rec. inferior. At the junction of the m.
rec. inferior and the m. obl. inferior, both muscles are connected by a sinew:
the ligamentum Lockwood.
16
The whole system is embedded in a soft, fatty tissue. This is for stabilizing
the bulbus and the muscles. Additionally, the muscles are held in place by
connective tissues and intermuscular membranes. They are especially important
in the area of the point of tangency, where the muscle leaves the bulbus. There
they keep the point of tangency in place and ensure that the force of the muscle
affects the bulbus in the same direction, regardless of the current gaze position
(cf. Ch. 2.3.2).
2.3.2
Muscle Models
The modeling of the oculomuscular system has greatly improved over the last
years. The first model used for describing eye muscles was the string model
by [Krewson, 1950]. In the beginning, a simple string model was used. Each
muscle was assumed to be a thin, elastic string and its insertion on the bulbus
was modeled as a single point. These strings are always pulled tight, and
therefore take the shortest path from the insertion point to their origin in the
orbita
In this model, force of a muscle is applied at the insertion point, where the
muscle leaves the bulbus. When I denotes the insertion point, M the center of
the bulbus and U the origin of the muscle in the orbita, then the muscle lies in
the plane defined by
r~I := I − M
(2.7)
r~U := U − M
(2.8)
The normal vector of this plane
m
~ :=
r~I × r~U
|r~I × r~U |
(2.9)
is the rotation axis, around which the bulbus is rotated by this muscle (Fig. 2.4).
While the accuracy of this model is acceptable while the bulbus is in or near
primary position (not rotated), it becomes less accurate in positions that are
rotated far out of the primary position. Because the muscle takes the shortest
path from the origin to the insertion point, the point of tangency moves on the
bulbus, and in extreme cases the muscle can “flip over” and reverse its effect
(for instance start turning eye outward instead of inward). Fig. 2.5 gives a
schematic overview of this problem.
To accommodate for this flaw, [Robinson, 1975] suggests a tape model in
which the movement of the point of tangency is limited. To achieve this, the
model limits the angle α by which the point of tangency can move from the
original position. If T denotes the insertion point in primary position and Tstring
is the point of tangency in the string model, then
αmax := ∠T ITstring
(2.10)
2.3. MEDICAL TERMS
17
Figure 2.4: String model
Figure 2.5: Change of effect in string model
18
is the maximum possible angle the insertion point can move. Robinson limits
this angle by multiplying αmax with the amount of rotation from the primary
position :
α := αmax ∗ |sin |
(2.11)
Due to this limitation in the tape model, the unreel strain from the point of
tangency to the insertion point does not follow a great circle but some arbitrary
circle on the bulbus.
The tape model therefore prohibits muscles from “flipping over”, but the
point of tangency still moves on the bulbus and in tertiary gaze positions,
rotated very far from the primary position, the effects continue to differ from
anatomical expectations. To resolve this, [Kusel and Haase, 1977] proposed the
restricted tape model. This model reduces the angle α again so that
αrestricted :=
α
10
(2.12)
With this restriction, the point of tangency stabilizes throughout the complete
physiologic field of vision.
Chapter 3
Biomechanically-based Muscle
Volume Deformation
Don’t tell people how to do things. Tell
them what to do and let them surprise
you with their results.
George S. Patton
In this chapter the general layout of the system is presented. The main
emphasis lies on giving the reader a structural overview over the different components, and how they work together. An overview of the algorithms used is
given in chapter Ch. 4 and the implementation details are covered in chapter
Ch. 5.
3.1
Input Data
Besides the path of a muscle, which is already defined by the SEE-KID application, the most important information about a muscle, for this thesis, is its
volume and the distribution of its volume. We also need to know how the distribution of the volume changes with changes in muscle activation. While it is the
topic of this thesis to calculate the shape of the muscle at different activations,
starting information is still needed, so that the system does initially know how
the muscle looks like.
To provide this information, the system uses a three-dimensional representation of MR images for calculating the basic parameters of the muscles. This
data, constructed from a set of MR images, each representing a slice of the
muscle, defines the surface and thus the volume of the model. Only a short
overview of how these models are created is given here, for a more detailed
19
20
CHAPTER 3. MUSCLE VOLUME DEFORMATION
discussion see [Pirklbauer, 2001].
The basic method used for constructing three-dimensional models is the
marching cube algorithm. The idea of this algorithm is to generate a continuous surface of the muscle by analyzing the relationship of neighboring points in
space. Each point is classified as either inside or outside of the volume. Surfaces
are created completely between points, situated on opposite sides. This process fills an area in 3D-space with a large number of small cubes, determining
which corners of the cubes lie inside or outside of the volume. According to a
predefined set of rules, this information can be used to generate a continuous
surface, which approximates the surface of the original volume with an accuracy
inversely proportional to the size of the cubes.
To achieve this goal, the marching cube algorithm creates a series of planes,
intersecting the object. They are all parallel to each other and evenly spaced.
Then, for each plane, the parts that lie inside and outside of the object are
determined. In our case this is done by assigning an MR image to each of the
planes. Pixels of the image with a certain color are defined to be inside while
others are outside. The value of the points between the planes is assumed to
be of the same value as the nearest pixel. The result of this step is a volume
representation where each pixel represents a small cube either (partially) inside
or outside of the original object.
Figure 3.1: Marching cube algorithm [Pirklbauer, 2001]
To determine the surface of the object, the algorithm assigns each possible
group of eight neighboring pixels to the corners of a group. See Fig. 3.1 for a
detailed representation of this step. Because the cube has eight corners and each
corner has to be in one of the two states, 28 = 256 possible cube configurations
exist. Each of these configurations defines if and how the surface passes through
the cube. This number is quite high, but it can be shown that by rotation and
3.2. COPING WITH THE AMOUNT OF DATA
21
inversion of the corners, each of the different cubes can be mapped to one of 15
classes, as shown in Fig. 3.2. To generate the surface, the algorithm performs
the following steps:
1. Determine the state of the corners from the pixel values.
2. Find a transformation T that transforms the actual cube, matching one
of the 15 predefined classes.
3. Build a set of triangles, representing the surface passing through this cube.
4. Transform the triangles using the inverse transformation T −1 from step
2.
5. Add triangles to the set that contains the already constructed surface.
After performing these steps for all possible cubes, the result is a set of triangles,
describing the surface of the object. It is obvious from the above layout that for
k images of size m × n, the asymptotic runtime of this algorithm is O(k ∗ m ∗ n).
It is therefore desirable to keep the images as small as possible.
The implementation of the marching cubes algorithm performs another optimization to produce a smoother surface [Pirklbauer, 2001]. It is not only
classifying the corners of a cube as inside or outside, but also determines how
far inside or outside each corner is by evaluating the specific color value of each
pixel. Pixels with color values near a given threshold are assumed to be nearer
to the surface then pixel values far from the threshold. The algorithm is then
moving the corner points of the surface parts inside or outside, depending on
the ratio of the distances of the corners of the cube. This is especially important
when the area of the muscle crossection is getting rapidly smaller from one MR
image to the next. Fig. 3.3 illustrates such a case and shows the difference of
the two methods using a two-dimensional example.
3.2
Coping With the Amount of Data
Our input data is represented using DXF files, and each triangle is stored as a
single primitive within the file. While this representation is interchangable and
easy to generate, it is very insufficient in terms of memory usage and render
speed. Additionally, the data structure does not contain any connectivity or
volume information. Since the last two points are very important for our thesis,
the input data needs to be transformed into a more suitable representation.
The first step is to find connectivity information. For this purpose a simplified boundary representation method is used. Because the surface is built
from triangles only, there is no need to store edge information but only triangles
and corners. In order to build a usable data structure, the input file is transformed into a list of triangles. Corner points of two or more triangles, which
22
Figure 3.2: Marching cube classes [Pirklbauer, 2001]
3.2. COPING WITH THE AMOUNT OF DATA
23
Figure 3.3: Optimization of the marching cube algorithm
are within a certain limit of spatial proximity, are welded together. The boundary representation is then transformed into an indexed triangle list. In this
form, connectivity information can still be gained from the list, but at a higher
cost. However, this representation is ideal for current rendering hardware. It
also provides a good starting point for creating exactly the data structure we
need. A copy of this representation is kept so that the original DXF model can
be displayed in the program for comparison with the dynamically generated
muscle.
When the input data has been transformed into a data structure that can be
quickly displayed, restoration of the volume information is still needed. Before
deciding how to do this, another constraint from the thesis should be taken
into consideration: The volume needs to be dynamically transformed, and this
transformation should be volume preserving. The way the surface is defined
now it fits neither one of the two conditions. Given two volume models of the
same muscle in two different activation states, the actual goal is to generate a
new model in an intermediary state by interpolating between the states. The
two surface representations do however not contain any topology information.
The positions of the triangles of one surface are not connected in any way
with the position of the triangles on the other surface. Thus, identification of
matching points before each interpolation step would have to be done.
To overcome this flaw the final model needs to contain topological data as
well as volume information. The following information can be identified as vital
for interpolation:
• position and orientation of the muscle in space,
24
• length of the muscle,
• activation of the muscle,
• volume of the muscle.
The first two points are very important to distinguish muscle movement
and muscle volume deformation in a set of input models. This distinction is
especially important since the interpolation of position and volume works in an
entirely different way. Activation cannot be extracted from the input model
itself but has to be supplied from some external source (e.g. from the physician
who took the MR data). The volume does not only contain the current volume
of a muscle, but also information on how the volume is distributed along the
muscle.
A set of one or more connected Hermite splines is used to represent position,
orientation and length of the muscle. Let P (d) : R 7→ R3 be this path. To
calculate the path, the muscle is devided into several slices. These parts are all
perpendicular to the longest axis of the muscle. The slices are spaced evenly and
are positioned in a way so that all the points in one slice belong to triangles of
one MR image from the marching cube algorithm. The path is then calculated
by repetitive cubic regression, so that the mean square error is below a certain
threshold.
Once the muscle path is established, a function
R(d, φ) : R × R 7→ R
(3.1)
defines the radius of the muscle with respect to the path. Hereby d is the
distance along the path and φ is the angle around the path. Thus, for each
d, R defines the radii of a set of points, all of them contained in a plane that
also contains P (d). The intuitive idea would be to make these planes normal
to the tangent of the path P 0 (d). With this method however, some points on
the surface cannot be correctly categorized. Fig. 3.4 shows how planes can
intersect in this model. Because of this property, one can get problems with
exactly defining the volume and also with specifying the exact function in the
first place. To improve the situation, all planes need to be parallel to the cuts
used for generating the path. This way, the planes itself are parallel and cannot
intersect and also the function can easily be derived from the indexed triangle
list.
This representation is now easy to interpolate because each radius of each
model can be mapped one-to-one to a radius on another model. Furthermore,
the transformation of the muscle
R model can be forced to be volume preserving
by ensuring that the integral R(d, φ) is equal in the dynamic model and in
the input models.
3.3. MUSCLE MODEL
25
Figure 3.4: Intersecting planes
3.3
Muscle Model
This thesis only covers the area of calculating muscle shapes for a given activation and length, and the visualization of the resulting muscle volume. It is not,
however, concerned with the calculation of the current activation and length
of the muscle. The actual length changes are given by the SEE-KID system,
which uses a feedback-driven muscle simulation to determine the length and
activation of each muscle.
When a muscle is activated it contracts and changes its length. If however,
the length of the muscle is fixed, then an activation of the muscle does not
result in a length change, but instead the muscle exacts a force onto the two
fixing points. This force is called tetanic force. The tetanic force of a muscle
depends on its length and activation. The length, at which with for maximum
activation the muscle generates maximum force is called the optimum length l0 .
The force at this length is the maximum tetanic force f0 .
The output of the muscle simulation is the force of the muscle for a given
time in units of f0 . The forces are then transformed into rotations by the
biomechanical model, and the rotations are in turn evaluated into passive length
changes of all 6 extra-ocular muscles. The passive length changes are then
fed back into the muscle simulation and are used with the new activation to
calculate the updated forces of the muscles. This iteration stops when the forces
of the muscles reach an equilibrium at which time the eye has reached a stable
position. Fig. 3.5 shows this cycle and its components.
The muscle simulation is based on a Hill-type model, which is depicted in
26
Figure 3.5: Muscle model [Buchberger and Mayr, 2000]
Figure 3.6: Modified Hill-type model [Cheng et al., 1999]
3.4. VOLUME PRESERVING TRANSFORMATIONS
27
Fig. 3.6. It extends this model, however, and tries to specialize it for extraocular
muscles. To do so, it mainly changes the contractile element. It adapts the forcelength and force-velocity relationships, based on work by [Miller and Demer,
2000]. While [Miller and Demer, 2000] only uses a static model, this simulation
uses a dynamic model to incorporate the time component.
Three pieces of information are actually taken as input from the SEE-KID
system for this thesis:
• current activation of the muscle,
• current length of the muscle,
• current path of the muscle.
These data are used to calculate the new muscle shape for any given activation. This may be done once the equilibrium is reached or during the iteration,
depending on the goal of the visualization. This thesis does not actively change
any of these values, so the visualization can be performed anytime without
disturbing the iteration process.
3.4
One of the key points in generating correct, realistic interpolations of muscle
volumes, and therefore also one of the main features in this thesis, is the preservation of the muscle volume during the transformation. This is necessary so
that the user always has a plausible picture of the muscle, and how it affects
its environment. This leads to the following three border conditions of this
problem:
• Volume must be preserved during transformations.
• Volume information has to be derived from input models only.
• The algorithm for transformation must be suitable for interactive rendering.
A good method to improve calculation speed would be to precalculate functions for the distribution of the muscle volume, and other parameters that help
building a correct model at runtime. The second aspect, however, prohibits this
way of optimization as it would require user input from a person with in-depth
understanding of the subject, or alternatively would require extensive preprocessing of the input images. Neither of them is suitable for the application, and
therefore the program has to take its information from the input models.
This, however, leads to another problem, which is not initially apparent.
The process of creating the input models is using the marching cube algorithm.
28
For this algorithm to work, it needs to identify each pixel on the input images as
either inside or outside of the muscle volume. It does this by assigning threshold
values to them, which classify pixels within a certain color range as inside. While
this is a common technique, it leads to problems in this application. The border
of the muscle in the image is not sharp, but is blurry, and actually is a short
gradient of colors. Depending on the threshold, the marching cube algorithm
classifies more or less pixels as inside and therefore is changing the volume.
This is not necessarily a problem using a static image, as it only makes the
muscle grow or shrink by a small percentage value. Because the different input
models used in this thesis are from different sets of input images, it is easily
conceivable that the image sets vary lightly in brightness and contrast. Furthermore, the image sets will use different threshold values during the marching
cube steps. It can therefore not be proven, and it is actually very unlikely, that
all input models have the same volume to start with. And, as the program has
no ability to decide which model has the most correct volume, it cannot prefer
one model.
There are multiple ways to accommodate, all however have to make a tradeoff between accuracy and visual quality. The first would be to make the transformation really volume preserving, taking the volume of one of the two input
models used in the current interpolation step. This could for example be the
one nearest in activation to the current dynamic model. While this is correctly
preserving the volume during transformations, at least during continuous segments of activation, it produces visual artifacts when the reference volume is
switched from one model to the next. Fig. 3.7 illustrates this behavior.
Figure 3.7: Nearest neighbor vs. weighted interpolation of actual volume
To provide a better visual quality, especially during animation of the activation state, this thesis is interpolating the muscle volume linearly between the
input images. This way the transformation is not actually volume preserving,
but it provides better visual quality and is equally correct for all input images.
3.5. RENDERING
29
An alternative method would be to calculate the average volume of all input
models, and use this as volume for the dynamic model. While this prevents
jumps in volume, and is volume preserving, a result that has exactly the same
activation as one of the input models does not have to have the same volume
as the input model.
Therefore the steps during the transformation are as follows:
1. Determine the path of the muscle for the current activation.
2. Determine the distribution of the volume for the current activation.
3. Build a muscle volume, using the interpolated path and the interpolated
distribution.
4. Determine the volume for the current activation from the input models.
5. Determine the actual volume of the interpolated distribution.
6. Apply a scale operation to make the volume of the interpolated distribution the same as the desired distribution.
The scaling in step 6 is uniform. This way it can be ensured that the distribution as well as the volume is exact. The way the volume is defined and
stored also ensures that it does not change by modifying the muscle path. This
partitioning into three independent subproblems allows the independent calculation of each feature and combination afterwards. This way the algorithm
for each subproblem can be kept simple and therefore guarantees acceptable
performance.
3.5
Rendering
As this thesis provides a basic mechanism for interpolation of static muscle
images, it is desirable to keep its output at a generic level. This way it can be
used by different systems without any problems. However, it is also the goal
of this thesis to build a system that is capable of interactive rendering, and
therefore needs to optimize the rendering process itself. Since optimizations in
computer graphics are based mainly on extensive knowledge about the model to
render together with its intrinsic properties, generic usability is being restricted.
To provide good trade-off between speed and generality, this thesis takes
over the complete rendering of the model, but uses the OpenGL generic render
platform, which is widely used in professional visualization. Thus, it is possible to specialize the rendering process, and still use OpenGL as the primary
platform. The only thing that needs to be done by the application is to set up
OpenGL correctly and set a suitable world transformation, so that the model
is rendered at the correct location on the screen.
30
To give the calling application the possibility to customize how the model
should be displayed, only the most important render states are set by this
thesis. Everything regarding image quality can be set by the calling application.
Furthermore, each part of the model is developed as its own class, and each such
class has its own rendering method. Therefore, the application allows the user
to choose which parts to draw, and how detailed to visualize them. The parts
which can be selected for display are:
• Input models: The copy of the indexed triangle list, saved during the
input process of the DXF file.
• Parameters: The muscle path, with its tangents, for each input model
and the dynamic model.
• Muscle Volume: The muscle volume (i.e. transformed radii) for the dynamic model.
• Input Images: The images used for the marching cube algorithm.
The first and last part exists only for input models, while the third part exists
only for the dynamic (i.e. output) model. The parameters exist for both models.
For input models, the user can select which input model, or which combination
of input models, to draw.
The input images are projected into three-dimensional space, so that they lie
in the planes they were assumed to be in during the marching cube algorithm.
This way the result can be directly compared against the original input images.
The user can select if he wants all input images to be displayed or only specific
images. In the latter case, he can also choose which of them he wants to display.
Chapter 4
System Design
I am always doing that which I can not
do, in order that I may learn how to do
it.
Pablo Picasso
4.1
Mathematical Model
We use the data from the SEE-KID muscle simulation system as input for the
muscle visualization. To get this data, we need an interface to this system. To
this end, we incorporate our muscle into the iteration process. Fig. 4.1 shows
how our work fits into this process, and which components are used to get the
data outlined Ch. 3.3.
4.2
Muscle Volume Deformation
This chapter describes the algorithm used to generate the parameterized representation of the muscle volume, how this model is transformed, interpolated,
and how the results are rendered in an efficient way.
4.2.1
Transforming Input Data
As laid out in Ch. 3.2, the input data is transformed via various steps to a representation that stores, both, path and muscle volume. This section describes,
how this transformation is actually done in the program. For the actual implementation see Ch. 5.2. In the following, the algorithms used and a sketch how
31
32
CHAPTER 4. SYSTEM DESIGN
Figure 4.1: Muscle model with visualization
they interact are presented.
The first step is the generation of the boundary representation from the
input files. For this the DXF files are read and stored in a list of points.
Although the DXF file format is not specified this way, the file structure can
be transformed into a grammar, suitable for parsing with recursive descent
or similar methods. This method was chosen because it allows easier error
handling and is generally more stable than normal processing.
In this case the complete geometry is stored as a sequence of planar quadrangles. Most or all of these quadrangles are degenerated, however, and are
actually triangles. Because the DXF format represents, both, triangles and
quadrangles as quadrangles, the geometry is stored as a list of points containing consecutive groups of 4 points, whereby each group defines one primitive
(i.e. a triangle or a quadrangle). After the whole file has been parsed, each
primitive is analyzed and a triangle structure is generated for it. In this process
quadrangles are split into two triangles.
Each triangle contains references to each of its corner points; likewise each
point has a list of references to the triangles it is a corner of. The corner points
are stored in a separate list. Subsequently the list of points is analyzed and
points whose distance is below a certain threshold are welded together. The
welding replaces all points that are to be welded together with a new point,
which is the geometric average of these points. It can be shown that, because
of the way the marching cube algorithm works, points are either equal to each
other, or have a spatial distance which is higher or equal to 0.5∗ δ where δ is the
smallest distance between two pixels in the stack of images used [Pirklbauer,
2001]. Due to this, as long as the threshold for the welding is smaller than
0.5 ∗ δ, the resulting set of triangles will describe the same (intended) volume
as the triangles in the DXF file.
4.2. MUSCLE VOLUME DEFORMATION
33
The boundary representation can be transformed in linear time into an
indexed triangle list. This list actually just eliminates the references from the
points to the triangles. Neighboring triangles can still be identified by searching
through the list of triangles and looking for references to the same corner points.
This is slow, but this lookup is not needed anymore in the processing of these
points. Because the model can be stored with a small amount of memory, and a
linear traversal over the primitives can be used to display them all, this method
of storing geometry is widely used in today’s rendering applications. A copy of
the indexed triangle list is kept, so that it can be displayed for comparison with
the dynamically generated model.
The next step is to calculate the muscle path. We build an isothetic parallelepiped that bounds the muscle exactly and find the longest dimension of it.
The muscle is then cut into equally spaced slices along this dimension. The cuts
are spaced evenly and positioned in a way so that each slice contains points,
which are defined by exactly one input image into the marching cube algorithm
(i.e. the cuts lie exactly between the planes where the images for the marching
cube algorithm would be). The center of gravity of each slice is calculated and
the resulting set of points is approximated by a series of Hermite splines. The
algorithm is generating splines by using cubic regression on the points, starting
with one spline and recursively splitting and adding splines until the whole set
of splines satisfies a least mean square threshold. The splines are generated
in a way so that c1 continuity 1 can be guaranteed over the whole path. The
complete path is then defined to be a function P (d) : R 7→ R3 , where P (0) is
the beginning of the muscle and P (1) is the end.
After the complete path is established, the radius function R(d, φ) is defined. Actually the function is specified at some points only, and the rest is
interpolated. The number of points can be chosen in the program. The more
points are used, the more accurate is the result, but it also gets computationally
more expensive. Fig. 4.2 shows the path and surface of a muscle. A grid-like
distribution of the points is used, where the grid is aligned to d and φ. The grid
is spaced evenly in both directions. The maximum useful grid resolution along
d is to use one step for every image used for the marching cube algorithm. The
maximum useful resolution along φ is so that the radii are defined for each pixel
on the circumference of the muscle in the images used for the marching cube
algorithm. To achieve a good rendering performance however, the program uses
lower values. By default it uses a 20 by 20 point grid, which gives good visual
and calculatory performance.
As the points defined by the radii are not coincident with the points of the
original DXF model, they are specified to be the averages of the original points.
For this process, a weighted contribution of the original points to the radii is
defined by using a biquadratic filter. The virtual point is then the weighted
average of the contributing points. Let ~v be the vector describing the direction
of the current radius and L be the ray extending from P (d) in the direction of
1
c1 continuity: the first derivative is continuous
34
Figure 4.2: Path and surface of the muscle
~v . Let δX be the distance of a point X in the original model M to the line L
in grid units. Then
S := {X ∈ M |δ < 1}
(4.1)
is the set of all points which lie within a radius of one unit around L. Then the
radius is the sum of the distances of X to P (d) weighted by their respective δ
values:
P
|X − P (d)| ∗ δX
R(d, φ) = X∈S P
(4.2)
X∈S δX
4.2.2
Dynamic Muscle Volume Generation
Once all of the input models are processed, they are assigned values for their
activation. Currently this assignment has to be set by the user, as the program
cannot automatically identify the activation. Then, the complete set of input
models, along with their activation values can be used to interpolate the muscle at any given activation in between. Not only activation is changing when
interpolating the muscle, but length too. This is for two reasons. First, the
length of the muscle changes with activation because it results in a contraction
of the muscle. The second method is passive length change. This is the length
change imposed on all muscles when one is activated, because of the mechanical
properties of the eye. The eye muscles are always working in pairs, and when
one muscle contracts, the other muscle is extended and vice versa. Both, the
35
activation and the length of a muscle are given by the SEE-KID application
and are calculated by the dynamic muscle model.
The length change and the activation can be handled as separate problems.
This way the interpolation of the muscle is easier. First the muscle is interpolated from the input images and the length change is disregarded. Afterwards
the muscle length is adapted and the muscle is scaled in the process to keep
the volume the same. The interpolation is done purely on the parameter basis.
After this has been finished, the render model is rebuilt from the parameter set.
The process of interpolating the muscle volume without length changes can
be split into the following steps:
1. identifying the input models used for interpolation,
2. interpolating the muscle path,
3. interpolating the radii,
4. generating the render model from the parameters.
The first step consists of defining weighting factors for the different input
models, depending on their activation relative to the desired activation A. Let
wM be the weight associated with an input model M . This thesis uses interpolation of the nearest neighbors, so the process starts by finding two models
M and N with activations AM , AN respectively, for which AM ≤ A ≤ AN and
there is no model O for which AM < AO < AN . Then a weight is assigned to
each of the two neighbors that depends inversely linear on the distance from
the desired activation. The weights are defined to be
|AM − A|
|AM − AN |
|AM − A|
1−
|AM − AN |
1−
(4.3)
(4.4)
for models M and N respectively. This way they blend linearly into each other.
The next step is to interpolate the muscle path. Linear interpolation is used
for the path. So if PM (d) is the muscle path in model M and PN (d) is the path in
model N, then the resulting path is P (d) = PM (d) ∗ wM + PN (d) ∗ wN . The way
the paths are defined, however, leads to a problem when solving this equation.
Two paths may not have the equal number of spline segments. If they do, the
interpolation is simple: Just interpolate all of the spline segments linearly as
outlined before. If the number is different, then we have to split spline segments
somewhere during the interpolation. They can be split immediately, as long as
the splitting results in the same path. For this we need to find a splitting
operation so that it is possible to cut out a new spline from an existing one
such that all points of the new spline are also points of the old spline. This is
problematic when the new spline would contain points from two original splines
36
so the new set of splines has to be created in such a way that this cannot happen.
If such cases occur then the splines on both sides are split so that each side has
the same number of splines and the splines are in the same places with respect
to the d parameter. This configuration can be achieved by recursively splitting
larger splines into two halves when the corresponding part of the other spline
set also consists of multiple splines.
As all spline segments are normalized so that the start point is S(0) and
the end point is S(1) for any spline segment S, what actually needs to be done
is scale and move the old segment so that S(0) is now the start point of the
new segment and S(1) is the corresponding end point. To do this the spline
segment is transformed to the corresponding third-degree polynomial function
FS (x) := ax3 + bx2 + cx + d. Now this function is moved and scaled to get
FSn ew (x) := FS (x ∗ (h − l) + l) where h and l is the high and low value of the
part we want to cut out.
After splitting both paths, they can be linearly interpolated. As laid out
in Ch. 2.2.1, the polynomial for the path is a direct function of the parameters
of the spline. Thus linearly interpolating the spline parameters is equivalent
to interpolating the polynomial. Accordingly, the interpolation of the complete
path can be performed by linearly interpolating the spline segments.
The method for interpolating the radii and thus the muscle volume is more
difficult because the actual volume has to stay the same. The only thing done
in the interpolation step is to modify the distribution of the volume along the
muscle path. The change of the distribution is actually given by the input
models. The different radii functions describe how the volume is distributed
along the path for this step. The actual distribution is interpolated linearly
between the input models. After the distribution has been established, the
radius function is scaled, so that the volume stays exact. Because the input
models do not all have the exact same volume because of errors in the MR
images, approximations from the marching cube algorithm, and generating the
radii functions, the actual condition used for the volume preserving step is:
Z 1
Z 1
Z 1
R(d, φ) =
RM (d, φ) ∗ wM +
RN (d, φ) ∗ wN
(4.5)
0
0
0
Because interpolation of the path is performed according to the MR images,
the above steps automatically perform the active length change. Passive length
change, however, still needs to be taken into account. This is done in two steps.
First the scaling factor along the path is determined to achieve the new length.
This factor is used to scale the radii function, in order for the muscle volume
to stay exact. After this has been done, two transformation matrices are built.
The first scales the path in order to perform the length change. The second
is a rotation that takes into account the change of the insertion and point of
tangency of the muscle, and rotates the render model for representation.
After all these steps have been performed, the render model is rebuilt. The
static architecture of the render model is already generated when the program
37
starts up. What is done actually is that the render function is evaluated and
the resulting points are written into the pre-generated geometry. Furthermore,
the program defines the distribution of sinew and muscle parts, and updates
the texture distribution in the model accordingly.
4.2.3
Render Optimization of the Muscle Volume
As laid out in Ch. 2.1.2, it is important for render performance to choose the
right memory location for the render model. The data structures for the render
model are stored in AGP or video card memory when available. This results
in good write access but very slow read access. Generally it is desirable to
keep the number of operations on this data to a minimum for two reasons: The
first is the previously mentioned slow access, the second is to avoid conflicts
with the graphics card. The actual rendering process is asynchronous to our
program execution. In the normal case, the CPU sets up the render models in
the memory and then informs the graphics card what is to be rendered and in
what manner. The call returns instantaneous and the graphics card then reads
and displays the data asynchronously. While the models are rendered, the CPU
calculates the data for the next iteration of this process.
The access to the data for the render model has to be synchronized however.
Otherwise the integrity of the render model could not be guaranteed and the
results of the rendering process would be undefined. To avoid this problem, the
CPU can lock the memory where the display models reside. As long as the lock
is active the graphics card will not access the memory. If the memory is still
used by the graphics card, then the CPU waits until the lock can be achieved.
If the graphics card needs the memory and it is still locked by the CPU then
the graphics card waits until the resource is free again. These lockdowns are
extremely inefficient because either the CPU or the graphics card is in a busy
waiting loop. To avoid this, the program should access the memory with the
render models as rarely and as short as possible.
However, the render optimization of the model is a difficult and computationally expensive task. To optimize the model every time new data is generated
would slow down render performance significantly. Due to this, it should be
done beforehand and the data should be updated after the new model is calculated without breaking the optimization. This implies requirements concerning
the data structure for the render model:
• Triangle and point definition must be separate.
• Optimization should be independent of actual point location.
• Update of new point values does not involve any dependencies to triangle
definitions.
Additionally we define the following requirements for the layout and usage of
the data in memory:
38
• Triangles are rendered sequentially concerning their location in memory.
• Points referenced by the triangles are used sequentially concerning their
location in memory.
• Each point is stored only once.
• Both structures (triangles and points) take up the least possible space in
memory.
This thesis uses an indexed triangle list for the render model. This list has
already been used for other purposes in this thesis, and it is widely accepted as
a suitable data structure to store triangle information in 3D rendering. It keeps
the point and triangle definitions separate and thus allows us to exchange the
points with new values without having to watch out for any dependencies. The
optimizations, namely the three last points in the list, are independent of the
actual point location, although the topological dependencies of the old and new
point set have to be the same. This means that our interpolation must produce
the same number of points for each dynamically generated model. Furthermore
the points have to be in a specific order, which must be fulfilled by each model.
With our method of defining the radii function and the mode of interpolation,
these conditions are easily met. In fact this mode of operation is inherent to
the algorithm and data structures used, which is why it was chosen.
The condition of sequential usage can be achieved by choosing a suitable
method of storing and rendering the vertices and triangles. In this thesis triangles are enumerated at first radially and then move down the muscle path
from d = 0 to d = 1. The points are enumerated in a similar fashion. In the
usual case it is not possible to achieve exact sequential use of both points and
triangles. Normally the triangles are stored in exact sequential sequence and
the points are then stored as sequentially as possible. The reason for this is
that the most recently used points are in the cache of the CPU or graphics card
and can therefore be accessed more quickly than other points.
Chapter 5
Implementation
It is not enough to have knowledge, one
must also apply it. It is not enough to
have wishes, one must also accomplish.
Johann Wolfgang von Goethe
The last two chapters explained what this thesis is trying to achieve, and
laid out the general algorithms and techniques used to achieve these goals. This
chapter now covers the actual implementation chosen for this thesis. No source
code is used during these explanations, however. Wherever code is necessary,
pseudocode is used to explain the concepts.
5.1
Input Data
The process of creating the input models is not part of this thesis. Their creation
is described in [Pirklbauer, 2001] and the finished DXF files are then imported
by this thesis as input models. The DXF format was chosen because it is a
widely accepted format for transferring two- and three-dimensional geometry
data. The description of the DXF format presented here covers only the aspects
important for this work. For a complete definition see [Pohl and Eriksdottar,
1991].
Although the DXF file format is a serial format, the importer is implemented
as a parser, using an attributed grammar to define the file format. There are,
however, certain peculiarities about the DXF format, which make it necessary
to deviate from the standard implementation of parsers. The main problem
is that the basic entity in a DXF file is a pair of values, called a group. The
first value is an integer determining the type of the second value. The possible
types for the second values are text, integer and floating-point numbers. It
39
40
CHAPTER 5. IMPLEMENTATION
would theoretically be possible to build a grammar that can deal with these
pairs, but since there are 999 values for the type part, the grammar would
become extremely long. Also, the complete file consists only of such pairs, so
it is practical to have the scanner return these pairs as basic entity.
The file is split into 4 sections:
1. Header: Global settings, coordinate frame, colors;
2. Tables: defines layers, line styles, general styles;
3. Blocks: defines groups of graphical elements that can be used in the
entities section;
4. Entities: contains the actual graphical elements.
The files read with our application do not contain blocks, and the header
and tables sections are minimal. The complete definition of the geometry is
contained in the entities section as a series of SOLID entities. Each of those
entities defines a quadrangle, where the 3rd point and 4th point are possibly
the same. As no other entities are expected, but the parser should not break
on slightly non-conform files, other entities are skipped instead of throwing exceptions. In the following we list the grammar used for the parser. This is not
a complete reproduction, only the parts important for the following explanations are printed (<number>-<value> denotes one group, words in all caps are
terminal symbols).
Dxf = { Section } Eof .
Eof = 0-EOF .
Section = 0-SECTION [ Header | Tables | Blocks | Entities ]
0-ENDSEC .
Header = 2-HEADER { Headerfield } .
HeaderField = 9-Identifier HeaderFieldType-value
... exact definition of header fields is skipped
Tables = 2-TABLES { Table } .
Table = 0-TABLE [ VPort | LType | Layer | Style | View |
DimStyle | Ucs | AppID ] 0-ENDTAB .
VPort = 2-VPORT 70-count { VPortFieldType-value } .
... exact view port definition and other tables are skipped
Blocks = 2-BLOCKS { Entity } .
Entities = 2-ENTITIES { Entity } .
Entity = 0-EntityType 8-Identifier
{ EntityGeneralAttributeType-value }
[ Line | Point | Arc | Trace | Solid | Text |
Shape | Block | EndBlk | Insert |AttDef | Attrib |
5.1. INPUT DATA
41
PolyLine | Vertex | SeqEnd | 3DFace | ViewPort |
Dimension ] .
SOLID = 10-x1 20-y1 30-z1
11-x2 21-y2 31-z2
12-x3 22-y3 32-z3
13-x4 23-y4 33-z4 .
.. rest of the entities is skipped
The actual processing of the file is simple. The program keeps a list of points,
and each SOLID entity appends all 4 points to this list. Because SOLID is the
only type of entity in the file, and each SOLID has 4 points, no information
about which point belongs to which solid needs to be stored. After the whole
file has been processed, the list is traversed again. Each group of 4 points is
taken and stored in a boundary representation list, as described in Ch. 4.2.1.
To weld the vertices, they are first sorted by a spatial sorting algorithm.
As the distance between two points is either 0 or greater than 0.5 ∗ δ, a
comparison that maintains a topological order can be conceived where all
points with distance 0 are next to each other in the list. To do this the
comparison operator p ≺ q is used, where p and q are both three element
vectors with values p = [p1 p2 p3 ] , q = [q1 q2 q3 ]. It is defined
as follows:
δ
δ
δ
< q2 − 4 ∨
p ≺ q :⇔ p3 < q3 − 4 ∨ |p3 −
q3 | < 4 ∧ p2 (5.1)
|p3 − q3 | < 4δ ∧ |p2 − q2 | < 4δ ∧ p1 < q1 − 4δ
This order effectively groups all vertices in cubes with length 0.5 ∗ δ. The
contents of each group are the vertices that are to be welded in the later process.
As each group is now a continuous part of the list of vertices, the welding process
can be achieved in linear time. Starting with the first point, the algorithm
traverses the list until he finds a vertex whose distance to the first point is
greater than 0.5 ∗ δ. All points between the first and this one are erased, and
the references to their triangles are added to the first point. Then these triangles
are traversed and the references to the delete points are replaced with references
to the first point. After the complete list of the points has been traversed, all
vertices are welded, and the data structure is updated.
The complexity of the complete algorithm depends on the sorting algorithm
used. The sorting algorithm provided by the C++ STL is used in this thesis,
which has asymptotic runtime of O(n log2 n). Therefore the complete algorithm
has a complexity of O(n log2 n).
The transformation of the boundary representation into an indexed triangle
list can also be done in linear time. The first step is to transform the vertices.
This process is trivial, as only the references to the triangles from the vertex
data need to be striped. During this traversal the index of the points in the
original representation is also stored. The second step is to generate the index
list with the triangles. For this an iteration over all triangles is performed and
the index of each point is determined by reading the index written in step one.
Each triangle has three indices and they are written consecutively into the index
42
list.
5.2
Coping With the Amount of Data
After the file has been imported and the vertices welded, the parameters for
the input image are calculated. The first parameter is the muscle path P (d).
To get the path the muscle is devided into a series of slices along the z-axis.
Because the images used for generating the input images are coronal cuts 1 and
the image axes x and y are mapped to x and y in 3D space, the muscle always
has its longest extents along the z-axis. The identification of the slices is easy,
as a cut can be performed every δ units, starting at −0.5∗δ. This way each slice
contains exactly the points which were defined by one image in the marching
cube algorithm. In the ideal case (i.e. the model contains no noise) these points
form a ring whose borders are two star shaped polygons around the center of
gravity. When the ring is closed on both sides with a flat surface, the center
of gravity can be calculated by splitting the resulting body into pyramids and
tetrahedrons and calculating their centers of gravity.
The result is a list of points, each of them the center of gravity of one slice.
Now a set of splines is constructed, which approximate these points with a least
mean square distance. To accomplish this the best fitting spline is calculated
with normal cubic regression. The points are defined to be equally spaced
along the spline, which is an acceptable approximation in this case. When
pi , i ∈ {0..n} are the points and ui , i ∈ {0..n} are the locations along the spline
S(u) := au3 + bu2 + cu + d, then the error is minimized:
:=
n
X
(S(ui ) − pi )2
(5.2)
i=0
After the regression, the average error n is compared to a previously defined
threshold. If the criterion is met we stop, otherwise the list of points is split into
two halves and regression is performed on each one. This process is repeated
recursively until the criterion is met on each small spline segment. The process
can be proven to stop because when the amount of points for one segment is
4 or less then the regression produces a spline where is zero. The complete
curve is made continuous by making the start and end points and tangents of
two consecutive splines equal.
After creating the muscle path it can be used to calculate the radii. The
radius function is determined by a number of control points. These control
points represent where rays, starting along the path and extending radially,
intersect with the surface of the muscle. Finding these intersection points is the
first step in calculating the radii function. The control points are not necessarily
coincident with any known point of the surface, so interpolation of the known
surface points is needed.
1
coronal cut: the plane which the image lies in, is normal to the optical nerve
5.3. MUSCLE MODEL
43
First the ray of each of the control points is expressed as the parameters d
and φ which give the distance along the path, and the angle around the path.
Then all points from the input model are examined and their set of parameters
d and φ is determined. Now the weighted average of all points which have a
distance of less than one in grid units is calculated. The distance of the resulting
point to the path is taken as the radius for the current ray. This way all rays
are processed until the function is completely defined.
5.3
Muscle Model
The visualization of the muscle and the interpolation of a new muscle volume
are independent. Therefore the new muscle can be interpolated whenever the
muscle model dictates a change. The design of this thesis was chosen in a
way to support this. To initiate the calculation of a new muscle volume, the
muscle model informs the dynamic muscle that the innervation has changed.
The muscle volume is then recalculated acording to the steps laid out in the
next section. Fig. 5.1 shows a diagram of the process of recreating a muscle
volume.
5.4
Fig. 5.2 shows the conceptual layout of a dynamic muscle in the program. Each
muscle has a set of input images. Additionally it has an extra instance of
the MuscleParameters class that stores the parameters for the current state.
The DynamicModel class is the output model of the muscle, i.e. the transformed parameters, ready for display. Each input has its own instance of the
MuscleParameter class along with a copy of the DXF model and the input images. Also each input model has a defined activation.
As laid out in Ch. 3.4 the process of determining the interpolated dynamic
muscle model consists of the following steps:
1. Determine the path of the muscle for the current activation.
2. Determine the distribution of the volume for the current activation.
3. Build a muscle volume, using the interpolated path and the interpolated
distribution.
4. Determine the volume for the current activation from the input models.
5. Determine the actual volume of the interpolated distribution.
6. Apply a scale operation to make the volume of the interpolated distribution the same as the desired distribution.
44
Figure 5.1: Process of recreating muscle volume
5.4. VOLUME PRESERVING TRANSFORMATIONS
Figure 5.2: Concept of the dynamic muscle
45
46
The first part of the process is to identify the two input models, which should
be used for the interpolation. The nearest neighbors in each direction are used
for interpolation. After this has been established, the process can be started
with interpolating the muscle path. Problems arise when the actual splines in
one input path cover different areas of the complete curve in both sets. To avoid
this, the input paths are modified so that they contain the same set of points
as in the original state, but have the same number of splines and cover the
same areas. The path chosen to be modified is the one with - originally - fewer
splines. Let the path to be modified be Ps and the path after the modification
be Pd . Because of the way the splines are generated, it can be shown that each
spline in Pd is contained completely in one spline in Ps . To calculate the new
splines the following process is used for each of the target splines in the path:
1. Calculate the area where the spline is, relative to the path. This is a
continuous area [m, n], where 0 ≤ m < n ≤ 1.
2. Determine which spline S(u) in Ps contains the target spline.
3. Get the modified area of the spline [m0 , n0 ] so that it is relative to the
source spline.
4. Build a new spline S 0 (u) so that S 0 (0) = S(m0 ) ∧ S 0 (1) = S(n0 ) and
∀p∈S p ∈ S 0 .
Points one to three are straightforward, and point 4 is also easy, because
S 0 (u) := S((u − m0 ) ∗ (n0 − m0 )). This is actually just scaling and moving
of the parameter u and the result set is unchanged. Now the splines can be interpolated linearly between the two paths. This is done by linearly interpolating
the end points and tangents of the splines at the end points.
The distribution of the volume is determined by interpolating the radius
function between the two input models. Because the radius function is defined
by a set of points, they are interpolated to get the definition of the new radius
function. Now the new muscle volume can be calculated. This is done by
first cutting the volume into slices along the parameter d. Each slice is then
cut along parameter φ. The final pieces can be built from a 4-sided pyramid
and a tetrahedron. Fig. 5.3 illustrates this. In the illustration the height ht is
r3 ∗sin α and hb is r2 ∗sin α. The base area of the pyramid is Ap = d∗(r1 +r3 )/2
and the base area of the tetrahedron is At = r4 ∗ d/2. Therefore the volume of
the piece is
d ∗ r2 ∗ (r1 + r3 ) ∗ sin α d ∗ r4 ∗ r3 ∗ sin α
d ∗ sin α
+
=
∗(r2 ∗ (r1 + r3 ) + r3 ∗ r4 ) .
6
6
6
(5.3)
As d and sin α is constant for each slice it makes sense to pull them and the
division out and precalculate this term for each slice to speed up the calculation.
The volumes of these pieces can be calculated and then added together to
produce the final volume.
5.5. RENDERING
47
Figure 5.3: One piece for calculating the volume
After the calculation of the current volume, the radii are scaled. It needs to
be taken into account, though, that the change in volume is the square of the
change in radii. Therefore the radii are scaled by
r
Vdesired
.
(5.4)
Vcurrent
5.5
Rendering
While the interpolation of two muscle volumes is only performed when the
muscle changes, the rendering has to be performed every time the screen is
redrawn. This is the case whenever the user rotates or moves the camera, or
when other viewing parameters change. Also the display has to be updated
after the muscle volume has changed. Due to these facts, the rendering is the
operation the program will spend the most time in. In order to enable the
program to work in an interactive manner the rendering process needs to be
optimized for speed.
The first part in this optimization is to find a suitable data structure. The
following conditions must be met:
• The data structure must be of minimal size for our needs.
48
• The data must be directly usable for rendering without any further transformation.
• The memory layout should be in a way to maximize cache efficiency.
The first point means, that no additional information can be stored in the
data structure. No lists or graphs are usable for its representation as they need
additional storage for pointers and are more complex to traverse. The second
point limits the represenation to data types, which are directly usable by the
rendering mechanism. OpenGL can handle almost any numeric datatype for the
vertex data, but in this application only floating point numbers are reasonable.
In order to improve speed and maintain portability with other systems, single
precision floating point numbers are used for the definition of the vertices. They
offer sufficient precision for the display of the data and provide a considerable
speedup over double precision values. To allow the system fast access and
traversal of the vertices, they are stored as a vector of vertices in one continuous
memory block.
Information
Position
Surface normal
Texture coordinates
Sum
Representation
3 float values
3 float values
2 float values
Size
12 octets
12 octets
8 octets
32 octets
Table 5.1: Vertex format for dynamic model
Tab. 5.1 shows the elements we need to store per vertex in the dynamic
model. The amount of memory needed is nearly optimal in terms of memory
bandwidth. The typical memory bus width in a PC is 64 bits. This means
that the whole vertex can be transferred in four bus cycles or in one burst
transfer. The memory buses of the newest graphics cards and also of upcoming
motherboards use a 128 bit bus width and can therefore transfer the vertex in
two bus cycles. This means that even if it were possible to process the vertex
in only two CPU cycles, this would not stall the pipeline because of memory
transfer bottlenecks.
When the CPU is reading data from the main memory it normally does
not only read the data currently requested, but reads ahead some data. The
complete block that was read is stored in the CPU’s cache memory. This is
done mainly because access to the cache is much faster than access to the main
memory area. Because of this read-ahead, it is helpful to order the vertices
in memory in ascending order of their usage. In this case, when the system
reads ahead and transfers extra bytes from memory, the data will be readily
available when the next vertex is transformed. This way the number of cache
hits is increased, and this greatly speeds up performance. If the vertices were
unordered, the extra bytes would be wasted and would have to be transferred
again later. This would cost twice, since the data has to be transferred again
5.5. RENDERING
49
over the bus, and the CPU always has slow access to the vertices.
The other data structure needed is the triangle index list. This list defines
how the geometry looks like by assigning vertices to triangles. It consists of
three values per triangle. Each value is the index of a vertex in the vertex list.
To save memory the indices are defined to be 16 bit integers. This imposes a
limit of 216 = 65536 vertices per model, but this is more than enough for our
application.
These two lists can already be pre-computed for the models, so no additional
transformations have to be performed before the rendering. This not only saves
computing power, but also allows to store the lists in AGP or video memory.
These memories have normal speed for write access, but are very slow for CPU
read access. This means that lists can only be stored there, but not used for
anything else afterwards. The advantage is that, although the CPU has very
slow read access, the graphics card does not. The graphics card actually has
much faster read access to AGP and even more so to video memory than to
conventional system memory.
As the indexed triangle list described above is a very common method to
store geometry data, OpenGL, like most graphics subsystems, can use the data
as it is, To render the geometry, the application only needs to tell OpenGL
where the data is and how much of it it wants to have rendered.
To efficiently implement the complete render process, the rendering and
recreation of the dynamic model is split up into 3 steps.
1. The first step is only performed once, at the start of the program. At this
time the capabilities of the system are evaluated and it is decided which
is the best memory location for our model. There are three possibilities:
• If transformation and lighting has to be done by the CPU, the data
structure is allocated in the main memory.
• If the graphics card can do transformation and lighting, but there
is not enough space in video memory for the geometry, the data
structure is allocated in AGP memory.
• If the graphics card can do transformation and lighting and enough
video memory is available, the data structure is allocated in video
memory.
After this is done the triangle list is built. The topology of the vertices
does not change in our model, so this can be done without knowing the
exact location of the vertices.
2. The second step is to fill in the actual values for the vertices. This is
done each time when a new render model has been built. It is done by
iterating over all points in the render model and storing their position,
the surface normal and the texture coordinates into the memory already
50
reserved. Again, to utilize caching best, this is done in a strictly forward
manner, filling the list in one go from beginning to end.
3. The third step is the actual rendering. This is done every time the display
needs an update. This occurs after a part of the display has been occluded
by another window and is now visible, or the user has changed the camera
or the model has changed. Only very little work has to be done for this
step, as the rendering is completely performed by OpenGL.
Chapter 6
Testing and User Reports
If something can go wrong it will.
Murphy’s Law (Edward A. Murphy)
6.1
Testing
One problem of this thesis is the verification of the results. The generated muscle volume cannot be compared directly to the real muscle, as it is unavailable.
To be able to judge the quality of the result at all, two methods are used,
• comparing the result to the original input models,
• comparing the result to the original MR images.
The two methods are similar, however the first is used to verify the volumetric proberties of the dynamic model, while the second method is used to
verify the correct shape of the muscle with respect to the MR images.
6.1.1
Verifying the Results
Both methods are based on a visual test procedure, which is built into the visualization client. Fig. 6.1 shows a generated muscle model. The correctness
can now be checked with respect to the input model by overlaying the input
model onto the dynamic model. This is depicted in Fig. 6.2. The input model is
displayed semitransparent and it can be seen how the dynamic model approximates the input model along the surface. The light areas show where the DXF
model is bigger than the dynamic model and vice versa. The picture also shows
51
52
CHAPTER 6. TESTING AND USER REPORTS
how small errors in the input model are filtered by the process of generating
the radii function.
Figure 6.1: Dynamic muscle model
The second method is based on comparing the dynamic model directly to
the MR images. This way it can be made sure that the cross section of the
muscle has the right shape. To this end, the client can display each MR image
at exactly the location where it was assumed to be during the marching cube
step. The intersectin of this plane and the dynamic model can then be examined
and compared to the muscle on the MR image. Fig. 6.3 shows one MR image
from the set used for this and the previous two pictures.
6.1. TESTING
Figure 6.2: Dynamic muscle model with overlay of input model
Figure 6.3: Dynamic muscle model with overlay of MR images
53
54
CHAPTER 6. TESTING AND USER REPORTS
Chapter 7
Conclusion
A mind once stretched by a new idea
never regains its original dimension.
Oliver Wendell Holmes
In the end I want to summarize the contents of this thesis, and show which
problems were solved, and what is still to do. Furthermore, I want to give an
outlook on the future possibilities in this area.
7.1
Goals Achieved
The main goal of this thesis was the generation of a muscle volume at any given
activation by interpolating from a set of input models. The input models are
generated by a separate program, not part of this thesis, and imported via a
DXF file format. The key problems solved in this thesis are:
• importing the input models from DXF file,
• calculating the muscle path from the input models,
• calculating the muscle volume from the input models,
• interpolating the muscle path,
• interpolating the muscle volume,
• preserving the volume,
• generating the render model from the volume and optimizing it.
The import algorithm is built as a parser, based on a grammar. After the
input models are read, they are optimized for rendering and the later processing.
55
56
CHAPTER 7. CONCLUSION
Welding vertices being close to each other enables this. Furthermore the vertices
are sorted to speed up the rendering of the input model and the later processing.
After the input models are read, the parameters are calculated for each
of them. First the muscle path is calculated by approximating the centers of
gravity of slices along the muscle. The approximation uses cubic regression and
a recursive subdivision scheme to achieve a least mean square threshold over
the complete path. This path is then used to define the volume of the muscle
as a radius function around the path. The radii are generated by analyzing the
input model and using a biquadratic filter to assign points of the input model
to them.
The interpolation of the muscle path needs to split both input paths so that
they have the same number of spline segments. Then linear interpolation of
the segments is used to interpolate the complete path. After the path has been
established, the volume is interpolated by linear interpolation of the radii function. During this step, the length of the muscle is also changed to accommodate
for active and passive length change. When the muscle volume interpolation
is finished, the generated volume is scaled to preserve the muscle volume. The
scaling affects only the radii function and not the length, which was set to the
correct value in the previous step.
The interpolated muscle volume is then used to generate a new render model.
The model is already optimized during the startup of the program. The regeneration only changes the position of the points that make up the geometry. The
render model is optimized for render speed by aligning the data in memory and
uses the optimal memory location.
7.2
Open Problems
The main objective of this thesis was to show that the volume preserving transformation of the muscle volume can be done wit a performance that allows for
interactive rendering. Therefore some minor parts are not implemented in full
detail and the whole system is not designed for user friendliness. There are
several points which could be improved in this system, when it is used for a
commercial product.
First the import of input models should be made more generic. The DXF
parser is working per se, but is skipping many of the entities possible in a DXF
file, because they are not used by the application generating them in our case.
It might even be desirable to build the marching cubes algorithm directly into
the application so that a new muscle can be generated from a set of MR images,
which is taken directly from the patient.
The second issue is of a more functional nature. The interpolation of the
dynamic model uses the nearest neighbors only. Path and radii functions are
interpolated linear, but if more input models were used, then the result might
LITERATURE
57
get more accurate. A possible solution here would be to use a method similar
to B-splines for the interpolation of the muscle volume. Also the method used
for determining the desired volume of the muscle, as outlined in Ch. 3.4, should
be selectable by the user and not fixed.
If even more accuracy in the volume preserving step is required, then the
radii function can be modeled as an actual function instead of specifying control points only. This might be done by specifying it as a parametric surface
(e.g. NURBS patches). This way the volume could be expressed exactly as
the integral of the function; however, the computational effort would be much
bigger. With dynamic tessellation, this method would also generate a smoother
surface, which would adapt itself to the screen resolution and size of the muscle
volume. Nonetheless, new problems would arise when scaling and interpolating
the muscle volume.
58
LITERATURE
Literature
[Buchberger and Mayr, 2000] M. Buchberger and H. Mayr. SEE-KID: Software Engineering
Environment for Knowledge-based Interactive Eye Motility Diagnostics. Proc. International
Symposium on Telemedicine 2000, Gothenburg, Sweden., pages 67–79, 2000. 1.1, 3.5
[Cheng et al., 1999] E. Cheng, J. Loeb, and I.Brown. Muscle Model for Matlab. User’s
manual, Canadian Institutes of Health Research Group in Sensory-Motor Systems, 1999.
3.6
[Eberly, 2001] D. H. Eberly. 3D Game Engine Design. Academic Press, 2001. 2.1
[Jordan and Smith, 1996] D. W. Jordan and P. Smith. Mathematische Methoden für die
Praxis. Spektrum Akademischer Verlag GmbH, 1996. 2.2
[Krewson, 1950] W. E. Krewson.
The
Trans.Amer.Opthalmol, 48, 1950. 1.2.2, 2.3.2
action
of
the
extraocular
muscles.
[Kusel and Haase, 1977] R. Kusel and W. Haase. Versuch einer mathematischen Darstellung
der Augenmuskelwirkung. Berichte der Deutschen Opthalmologischen Gesellschaft, 45:453–
458, 1977. 1.2.2, 2.3.2
[Microsoft, 2001] Microsoft.
Directx 8.0 programmer’s reference.
[Website,
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dx8 c/hh/dx8 c/
graphics understand 7d0z.asp, accessed July 25, 2001], 2001. 2.1
[Miller and Demer, 2000] J.M. Miller and J.L. Demer. Clinical applications of computer models for strabismus. Technical report, Upper Austrian Polytechnic University, Department
of Software Engineering for Medicine, 2000. 1.2.2, 1.1, 3.3
[Mortenson, 1999] M. E. Mortenson. Mathematics for computer graphics applications. Industrial Press, Inc., 2nd edition, 1999. 2.2, 2.2.1
[Pirklbauer, 2001] F. Pirklbauer. 3D-Rekonstruktion extraokulärer Augenmuskeln aus MRBilddaten. Diploma thesis, Polytechnic University, Hagenberg, Austria, Europe, 2001. 1,
3.1, 3.1, 3.1, 3.2, 4.2.1, 5.1
[Pohl and Eriksdottar, 1991] M. Pohl and H. Eriksdottar. Die wunderbare Welt der Grafikformate. Wolfram’s Fachverlag, 1991. 5.1
[Robinson, 1975] D.A. Robinson. A quantitative analysis of extraocular muscle cooperation
and squint. Invest Ophthalmol, 14, 1975. 1.2.2, 2.3.2
[Zhu et al., 1997] Q.H. Zhu, Y. Chen, and A. Kaufman. Real-time Biomechanically-based
Muscle Volume Deformation using FEM. Technical report, Center for Visual Computing,
State University of New York at Stony Brook, Stony Brook, NY 11794-4400 USA, 1997.
1.2.1.2
59

A Volume Preserving Model for Biomechanically-based - SEE-KID

Transcrição

Documentos relacionados

Projektergebnisse Effects of maternal undernutrition during

Complete Article - Journal of Morphological Science

P04 Lentivirus-mediated stem cell therapy for Duchenne muscular

Diagram of grion muscle

Diagram of grion muscle

Max Creatine 250g Brazil

The low-level laser therapy on muscle injury recovery

N.1,-01-20881_2010_4_29_32_23 - BJVP

Pectoral Muscle Detection in Mammograms Based on the Shortest

Complete Article