The project evaluates how well a haptic device can be used to interact with a visualization of volumetric data. Since the interface to the haptic device require explicit surface descriptions, triangles had to be constructed from the volumetric data. The algorithm used to extract these triangles is marching cubes. The triangles produced by marching cubes are then transmitted to the haptic device to enable the force feedback. Marching cubes was suitable for parallelization and it was executed using OpenCL. Graphs in the report shows how this parallelization ran almost 70 times faster than the sequential CPU counterpart of the same algorithm. Further development of the project would give medical students the opportunity to practice difficult procedures on a simulation instead of a real patient. This would give a realistic and accurate simulation to practice on. / Projektet går ut på att utvärdera hur väl en haptisk utrustning går att använda för att interagera med en visualisering av volumetrisk data. Eftersom haptikutrustningen krävde explicit beskrivna ytor, krävdes först en triangelgenerering utifrån den volymetriska datan. Algoritmen som används till detta är marching cubes. Trianglarna som producerades med hjälp av marching cubes skickas sedan vidare till den haptiska utrustningen för att kunna få gensvar i form av krafter för att utnyttja sig av känsel och inte bara syn. Eftersom marching cubes lämpas för en parallelisering användes OpenCL för att snabba upp algoritmen. Grafer i projektet visar hur denna algoritm exekveras upp emot 70 gånger snabbare när algoritmen körs som en kernel i OpenCL istället för ekvensiellt på CPUn. Tanken är att när vidareutveckling av projektet har gjorts i god mån, kan detta användas av läkarstuderande där övning av svåra snitt kan ske i en verklighetstrogen simulering innan samma ingrepp utförs på en individ.

Background. Being able to modify virtual environments can create immersive experiences for video-game players. Storing data as volumetric scalar fields allows for highly modifiable 3D environments that can be converted into GPU-friendly triangles with isosurface algorithms. Using scalar fields and isosurface algorithms can be more computationally expensive and require more data than the more commonly used polygonal models. Objectives. The aim of this thesis is to explore solutions to modifying real-time 3D environments with isosurface algorithms. This will be done in two parts. First in terms of observing how modern games deal with storing scalar fields, researching which isosurface algorithms are being used and how they are being used in games. The second part is to create an application and limit the data storage required while still running at a real-time speed. Methods. There are two methods to achieve the aim. The first is to research and see which data structures and isosurface algorithms are being used in modern games and how they are utilized. The second method will be done by implementation. The implementation will use the GPU through compute shaders and use marching cubes as isosurface algorithm. It will utilize Christopher Dyken’s Histogram Pyramids for stream compaction. Two different versions will be implemented that differ in terms of what data types will be used for storage. The first using the data type char and the second int. Between these two versions, the runtime speed will be measured and compared on two different hardware configurations. Results. Finding good data on what algorithms games use is difficult. Modern games are using scalar fields in many different ways: Some allow almost complete modification of terrain, others only use it for a 3D environment. For data storage, octrees and chunks are two common ways to store the fields. Dual Contouring appears to be the primary isosurface algorithm being used based on the researched games. The results of the implementation were very fast and usable in real time environments for destruction of terrain on a large scale. The less storage intensive variation of this implementation(char) gave faster results on modern hardware but the opposite(int) was true on older hardware. Conclusions. Modifying scalar field terrain is done at a very large scale in modern games. The choice of using Dual Contouring or Marching Cubes depends on the use-case. For areas where sharp features can be important Dual Contouring is the preferred choice. Likely for these reasons Dual Contouring was found to be a popular choice in the studied games. For other areas, like many types of terrain, Marching Cubes is very fast, as can be seen in the implementation. By using the char version of the implementation, interacting with the environment in real-time is possible at high frame-rates.

Le monde médical dispose de plus en plus de sources d'images différentes, non seulement pour réaliser un diagnostic mais aussi pour évaluer l'efficacité d'un traitement et pour être guidé dans les interventions chirurgicales. Parallèlement, le développement des techniques opératoires s'oriente vers la chirurgie non " à ciel ouvert ", notamment la coelioscopie, qui permet de diminuer les risques liés à l'intervention ainsi que le temps d'hospitalisation du patient. En revanche, elle rend moins intuitive la réalisation de l'acte chirurgical, notamment du fait de la vision réduite à l'utilisation d'une ou plusieurs caméras dans la région d'intérêt. Durant ma thèse, j'ai conçu et mis en oeuvre des nouvelles méthodes informatiques de traitement 3D d'images radiologiques ainsi que de nouvelles utilisations médicales de ces images. Les contributions présentées concernent la visualisation et le traitement des données, la segmentation de structures 3D, la fusion mono et multimodale et l'aide à la réalisation d'interventions. Les applications présentées concernent notamment la planification et la réalisation d'interventions sous coelioscopie et de ponctions mais aussi l'imagerie industrielle. L'utilisation conjointe de différentes modalités d'images permet d'améliorer la visualisation, la manipulation et la compréhension de scènes tridimensionnelles, conduisant à une plus grande compréhension des observations et à une meilleure prise de décision.

abstract: The Dual Marching Tetrahedra algorithm is a generalization of the Dual Marching Cubes algorithm, used to build a boundary surface around points which have been assigned a particular scalar density value, such as the data produced by and Magnetic Resonance Imaging or Computed Tomography scanner. This boundary acts as a skin between points which are determined to be "inside" and "outside" of an object. However, the DMT is vague in regards to exactly where each vertex of the boundary should be placed, which will not necessarily produce smooth results. Mesh smoothing algorithms which ignore the DMT data structures may distort the output mesh so that it could incorrectly include or exclude density points. Thus, an algorithm is presented here which is designed to smooth the output mesh, while obeying the underlying data structures of the DMT algorithm. / Dissertation/Thesis / M.S. Computer Science 2011

The report describes the thesis project with the aim of fusing an arbitrary sequence of stereo measurements into a global 3D representation in real-time. The proposed method involves an octree-based signed distance function for representing the 3D environment, where the geomtric data is fused together using a cumulative weighted update function, and finally rendered by incremental mesh extraction using the marching cubes algorithm. The result of the project was a prototype system, integrated into a real-time stereo reconstruction system, which was evaluated by benchmark tests as well as qualitative comparisons with an older method of overlapping meshes. / <p>Examensarbetet är utfört vid Institutionen för teknik och naturvetenskap (ITN) vid Tekniska fakulteten, Linköpings universitet</p>

Detta arbete undersöker om de existerande algoritmerna Marching cubes och Perlin noise kan användas för att procedurellt generera terräng. Implementationen av dessa algoritmer genererar en terräng som representeras som en tredimensionell volym, för att lösa problem som kan uppkomma när terrängen representeras av ett tvådimensionellt höjdfält. Vidare parallelliseras kombinationen av dessa algoritmer och anpassas för körning på GPU, där experiment visade att parallelliseringen gav prestandaökning och således kortare genereringstider. / <p>Det finns övrigt digitalt material (t.ex. film-, bild- eller ljudfiler) eller modeller/artefakter tillhörande examensarbetet som ska skickas till arkivet.</p><p>There are other digital material (eg film, image or audio files) or models/artifacts that belongs to the thesis and need to be archived.</p>

[pt] A extração e visualização de isosuperfícies de campos escalares são importantes para inspeções e análises de modelos em diversas áreas. Uma isosuperfície é representada por uma malha de triângulos que aproxima um conjunto de nível do volume de dados. O foco deste trabalho é a extração e visualização de isosuperfícies de modelos de reservatório de petróleo, representados por malhas de hexaedros levemente côncavos. Para uma melhor representação das isosuperfícies, optou-se pela substituição de triângulos planares por superfícies curvas. Para assegurar a extração de superfícies contínuas e suaves, este trabalho propõe o uso de envelopes para determinação das normais. A técnica proposta é implementada em GPU com uso de subdivisão adaptativa das superfícies. / [en] The extraction and visualization of isosurfaces of scalar fields are important for inspections and analysis of models in several areas. An isosurface is represented by a mesh of triangles that approximates a level set of a data volume. The main focus of this work is the extraction and visualization of isosurfaces of black oil reservoir models, represented by hexahedral meshes with slightly concave cells. For a better representation of the isosurfaces, we have opted to replace planar triangles for curved patches. To ensure the extraction of continuous and smooth surfaces, this work proposes the use of envelopes to determine normals. The proposed technique is implemented in GPU with the usage of adaptive subdivision of patches.

La fissuration à chaud est un défaut majeur rencontré en solidification des alliages d'aluminium. Elle est liée à l'incapacité du liquide de s'écouler dans les zones où des porosités sont présentes, ne permettant pas de les refermer avant qu'elles gagnent en volume. Pour comprendre la fissuration à chaud, il est crucial de développer nos connaissances du comportement mécanique de la zone pâteuse. Pour cela, il est très utile d'effectuer des expériences de microtomographie aux rayons X et des simulations mécaniques sur des volumes élémentaires représentatifs. Dans cette thèse, nous proposons de coupler les deux approches en initialisant une simulation par éléments finis grâce à des données de microtomographie issues d'un test de traction isotherme d'un alliage d'aluminium-cuivre à l'état pâteux. Cette approche originale nous donne directement accès à la réalité expérimentale et permet des comparaisons des évolutions numérique et expérimentale de l'éprouvette. Nous expliquons dans un premier temps comment obtenir la représentation numérique à l'aide de l'algorithme des marching cubes et de la méthode d'immersion de volume. Nous présentons ensuite notre modèle numérique qui s'appuie sur une résolution monolithique des équations de Stokes. Une fois le champ de vitesse obtenu dans l'ensemble des phases solide, liquide et gazeuse, nous utilisons une méthode level set dans un formalisme eulérien afin de faire évoluer la morphologie de notre échantillon numérique. Malgré la simplicité du modèle, les résultats expérimentaux et numériques montrent un accord raisonnable en ce qui concerne la propagation de l'air à l'intérieur de l'échantillon.

Visualization of volumetric data has always been useful in big va- riety of ways, for example computer tomography (CT) and magnet resonance tomography (MRT) are two major applications of this sorts of algorithms. Since volumetric data has no limitation regarding the shape of the object that ordinary mesh algorithms has we can fully reconstruct anything using the Marching cubes algorithm. New tech- niques allow us to implement this algorithm by new and exible means. Here we will use the latest of DirectX technology to run marching cubes in realtime using compute shaders. / kristoffer.swe@gmail.com

Conversion of discrete volumetric data to boundary representation is quite common operation. Standard approach to resolve this problem is to use well-known Marching cubes algorithm, which although simple and robust, generates low-quality output that requires subsequent post-processing. This master's thesis deals with uncommon algorithms used for isosurface extraction from volumes. The reader will be acquainted with fundamental principles of Hierarchical Iso-Surface Extraction method, that was independently implemented and tested in this work.