Direct volume visualization of geometrically unpleasant meshes [Elektronische Ressource] / vorgelegt von Martin Kraus

Sujets

• Informatik

Informations

• Publié par: universitat_stuttgart
• Publié le: 01 janvier 2003
• Nombre de lectures: 37
• Langue: English
• Poids de l'ouvrage: 9 Mo

Extrait

Direct Volume Visualization of
Geometrically Unpleasant Meshes
Von der Fakultat¨ Informatik, Elektrotechnik und
Informationstechnik der Universitat¨ Stuttgart
zur Erlangung der Wurde¨ eines Doktors der
Naturwissenschaften (Dr. rer. nat.) genehmigte Abhandlung
Vorgelegt von
Martin Kraus
aus Erlangen
Hauptberichter: Prof. Dr. T. Ertl
Mitberichter: Prof. Dr. R. Westermann
Prof. Dr. N. Max
Tag der mundlichen¨ Prufung:¨ 24. April 2003
Institut fur¨ Visualisierung und Interaktive Systeme
der Universitat¨ Stuttgart
20032
David: You’re O.K.?
George: Yeah. Not fair, you know?
You get used to one thing and then ...
David: I know, it’s not.
Dialog from the movie PleasantvilleContents
List of Abbreviations and Acronyms 5
Abstract and Chapter Summaries (in English and German) 7
1 Introduction 31
1.1 Outline of This Thesis . . . . . . . . . . . . . . . . . . . . . . . 32
1.2 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 33
2 Direct Volume Visualization 35
2.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2 Visualization Pipeline . . . . . . . . . . . . . . . . . . . . . . . . 37
2.3 Volume Rendering Algorithms . . . . . . . . . . . . . . . . . . . 39
2.4 Ray Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.1 Volume Rendering Integral . . . . . . . . . . . . . . . . . 41
2.4.2 Pre- and Post-Classification . . . . . . . . . . . . . . . . 42
2.4.3 Numerical Integration . . . . . . . . . . . . . . . . . . . 43
2.5 Pre-Integrated Classification . . . . . . . . . . . . . . . . . . . . 48
2.5.1 Ray Integration with Pre-Integrated Classification . . . . . 48
2.5.2 Accelerated Approximative Pre-Integration . . . . . . . . 51
2.5.3 Applications to Volume Rendering Algorithms . . . . . . 52
2.6 Classification of Meshes . . . . . . . . . . . . . . . . . . . . . . 53
2.6.1 Structured . . . . . . . . . . . . . . . . . . . . . 53
2.6.2 Unstructured Meshes . . . . . . . . . . . . . . . . . . . . 54
2.6.3 Hybrid and Hierarchical Meshes . . . . . . . . . . . . . . 54
2.7 Interpolation in Meshes . . . . . . . . . . . . . . . . . . . . . . . 55
2.7.1 Nearest-Neighbor Interpolation . . . . . . . . . . . . . . 55
2.7.2 Linear, Bilinear, and Trilinear Interpolation . . . . . . . . 55
2.7.3 Interpolation in Simplices . . . . . . . . . . . . . . 57
2.7.4 Higher-Order Interpolation . . . . . . . . . . . . . . . . . 58
2.8 Geometrically Unpleasant Meshes . . . . . . . . . . . . . . . . . 59
34 CONTENTS
3 Non-Uniform Meshes 61
3.1 Pre-Integrated Cell Projection . . . . . . . . . . . . . . . . . . . 61
3.1.1 Projected Tetrahedra Algorithms . . . . . . . . . . . . . . 62
3.1.2 Pre-Integrated Classification for Projected Tetrahedra . . . 63
3.2 Hardware-Assisted Resampling . . . . . . . . . . . . . . . . . . . 77
3.3 Ray Casting . . . . . . . . . . . . . . . . . . 79
4 Non-Convex and Cyclic Meshes 85
4.1 Convexification of Non-Convex Meshes . . . . . . . . . . . . . . 85
4.2 Edge Collapses invex . . . . . . . . . . . . . . 88
4.2.1 Edge Collapses in Convex Meshes . . . . . . . . . . . . . 88
4.2.2 Edge in Convexified Meshes . . . . . . . . . . 89
4.3 Cell Sorting for Non-Convex and Cyclic . . . . . . . . . 95
4.3.1 Cell Sorting for Convex, Acyclic Meshes . . . . . . . . . 96
4.3.2 Cell for Convex, Cyclic . . . . . . . . . . 98
4.3.3 Cell Sorting for Non-Convex, Cyclic Meshes . . . . . . . 101
4.4 Cell Projection for Cyclic Meshes . . . . . . . . . . . . . . . . . 104
4.4.1 Rendering of Cyclic Occlusions of Polygons . . . . . . . 104
4.4.2 of Cyclic, Convex Polyhedral Cells . . . . . . 109
5 Non-Simplicial and Non-Adaptive Meshes 111
5.1 Texture-Based Pre-Integrated Volume Rendering . . . . . . . . . 112
5.2 Topology-Guided Downsampling . . . . . . . . . . . . . . . . . . 113
5.2.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.3 Adaptive Volume Textures . . . . . . . . . . . . . . . . . . . . . 124
5.3.1 Adaptive Texture Mapping in Two Dimensions . . . . . . 124
5.3.2 Volume Rendering with Adaptive Volume Textures . . . . 133
6 Geometrically Unpleasant Meshes in General 135
6.1 Proposed Solutions . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.2 Problem-Solving Strategies . . . . . . . . . . . . . . . . . . . . . 138
6.2.1 Understanding the Problem . . . . . . . . . . . . . . . . . 138
6.2.2 Simplifying the . . . . . . . . . . . . . . . . . . 140
6.2.3 Solving the Problem . . . . . . . . . . . . . . . . . . . . 141
6.3 Further Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Color Plates 145
Bibliography 151Peggy Jane: Hey, M.S., how you doin’?
Jennifer: Cool, P.J., how you
Peggy Jane: Cool. Cool.
Jennifer: Cool.
Dialog from the movie Pleasantville
List of Abbreviations and Acronyms
triangle MAD multiply & add
tetrahedron MB megabyte
2D two-dimensional MHz megahertz
3D three-dimensional MPVO meshed polyhedra
a. answer visibility ordering
BFS breadth-first search MPVOC MPVO cyclic
BSP binary space partitioning MPVONC MPVO non-convex
CPU central processing unit MPVONCC MPVOvex cyclic
CT computer tomography MR magnetic resonance
CTA CT angiography M.S. Mary Sue
def. definition O.K. “oll korrect”
depend. dependent orig. impl. original implementation
DFS depth-first search pixel picture element
d.h. das heißt (that is) P.J. Peggy Jane
Dr. rer. nat. Doctor rerum naturalium Prof. Dr. Professor Doctor
(Doctor of Science) PT projected tetrahedra
e.g. exempli gratia q. question
(for example) RGB red, green, and blue
et al. et alii, et aliae, et alia RGBA red, blue, and alpha
(and others) texel texture element
etc. et cetera (and so forth) voxel volume
HIAC high accuracy XMPVO extended MPVO
i.e. id est (that is) z.B. zum Beispiel
KB kilobyte (for example)
5
6 LIST OF ABBREVIATIONS AND ACRONYMSDavid: I thought the books were blank?
Will: They were.
Jennifer: O.K. This was not my fault.
When they asked me what it was about,
I didn’t remember
because I read it like back in tenth grade.
When I told them what I did remember,
that’s when the pages filled in.
David: The pages filled in?
Jennifer: Uh-huh, but only up until the part with the raft,
’cause that’s as far as I read.
Tommy: Do you know how it ends?
David: Yeah, I do.
Margaret: So how does it end?
Dialog from the movie Pleasantville
Abstract and Chapter Summaries
(in English and German)
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Chapter Summaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Zusammenfassung (Abstract in German) . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Kapitelzusammenfassungen (Chapter Summaries in German) . . . . . . 19
Abstract
Interactive volume visualization (i.e., the visualization of scalar data defined on
volumetric meshes in real time) is not only difficult to achieve for large meshes
but it is also complicated by particular geometric features of volumetric meshes,
e.g., non-uniform cells, non-convex boundaries, or visibility cycles.
This thesis addresses several of these geometric features and their unpleasant
consequences with respect to direct volume visualization, which is one of the most
successful techniques for interactive volume visualization. In order to overcome,
or at least alleviate, these difficulties, several new algorithmic solutions are pre-
sented: pre-integrated cell projection and hardware-assisted ray casting for non-
78 ABSTRACT AND CHAPTER SUMMARIES
uniform meshes, edge collapses in non-convex meshes, cell sorting and cell pro-
jection for non-convex and cyclic meshes, as well as texture-based pre-integrated
volume rendering, topology-guided downsampling, and adaptive volume textures
for non-simplicial volumetric meshes (i.e., non-tetrahedral meshes).
As this work cannot cover all geometrically unpleasant features of volumetric
meshes, particular emphasis is put on a description of the development of the
proposed algorithms. In fact, most of the presented techniques are (or may be
interpreted as) generalizations, adaptations, or extensions of existing methods.
The intention of explaining these origins is to motivate new solutions for those
geometrically unpleasant features of meshes that were out of the scope of this
work.
Chapter Summaries
The following summaries give a rather detailed overview of the contents of each
chapter. The form of these summaries is as compact as possible in order to facili-
tate a quick orientation. Note that section headings are set in italics.
Chapter 1: Introduction
The primary goal of Chapter 1 is to introduce and motivate the subject of this
thesis.
Direct volume visualization is often complicated by large data sets, high res-
olution output images, or the need for real-time interactive frame rates. Because
of these difficulties, research on direct volume visualization usually focuses on
“appropriate” meshes, in contrast to “geometrically unpleasant” meshes, which
include any mesh with an exceptional or (for any reason) “difficult” geometric
sh