Le sujet de thèse s’inscrit dans le cadre de la lutte contre le cancer. La radiothérapie externe est une technique de traitement de cibles tumorales par des particules radioactives, sous guidage d’un système d’imagerie. L’efficacité de ce traitement à ciblage macroscopique dépend en partie de l’évolution de la cible biologique au cours du traitement, qui se programme sur plusieurs séances. Dans notre travail, nous nous sommes concentrés sur l’évolution temporelle de la cible biologique séance par séance. Le but est d’estimer l’espace couvert par son mouvement, et permettant de prédire le positionnement futur de la cible et corriger ou adapter le plan de traitement. Notre cible biologique microscopique dans le cas du cancer ORL est décrite par la glande parotide qui est sensible aux radiations. L’objectif est de minimiser l’accessibilité des rayons à cet organe lorsque la cible tumorale se trouve dans sa périphérie. Nous avons proposé deux méthodes de reconstruction en 3D de la parotide, à savoir B-Spline de Bézier bi-cubique et Marching cubes. Une fois la reconstruction est effectuée, le volume de la glande parotide, à chaque session est calculé. Une zone de sécurité autour de la glande parotide a été définie. Enfin, une classification des patients a été réalisée en se basant sur le dosage associé au traitement. A un niveau macroscopique, nous avons développé une approche d'aide à la décision pour affiner la position relative du patient sur la table de traitement. Cette approche est basée sur la modélisation par réseaux de neurones et spécifiquement MLP et RBF. La performance entre ces deux techniques a été analysée, suivant les positionnements géométriques des patients. / The thesis subject is defined in the framework of the fight against cancer. External radiation therapy is a technical treatment of tumor targets by radioactive particles, under guidance of an imaging system. The effectiveness of this macroscopic targeting treatment depends in part on the evolution and movement of the biological target during the treatment, which is planned over several sessions. In our work, we focused to the temporal evolution of the biological target session by session. The goal is to estimate the space covered by the target movement in each session, and to predict the future position of the target and thus to correct or adapt the treatment plan. Our microscopic biological target in the case of head and neck cancer is described by the parotid gland which is sensitive to the radiation. The objective is to minimize avoid radiating the parotid, when the tumor is in its periphery. We proposed two 3D reconstruction methods of the parotid, namely B-Spline Bezier bi-cubic and Marching cubes. Once the reconstruction is performed, the volume of the parotid gland, at each session of treatment is calculated. A safety zone around the parotid gland was defined. Finally, a classification of the patients was performed based on the associated dose for the treatment.At a macroscopic level, we have developed a decision-support approach to refine the relative position of the patient on the treatment table. This approach is based on a modeling of Neural Network and especially MLP and RBF. The performance between two neuronal approximation techniques was analyzed, according to the geometrical positioning of patients.

Este trabalho descreve uma nova visão sobre um dos algoritmos mais importantes da Computação Gráfica, o algoritmo para a poligonização de isosuperfícies Marching Cubes (MC). Esta visão permite o estudo das situações onde são gerados triângulos de baixa qualidade, uma das grandes deficiências do MC, e serve como suporte à proposta de modificações no algoritmo. Neste trabalho também são propostas três modificações ao MC, com objetivo de gerar triângulos de boa qualidade e manter as características mais atraentes do MC, ou seja, a sua simplicidade, eficiência e robustez. O funcionamento do MC é analisado a partir da decomposição das células de amostragem em Grupos de Arestas. Os Grupos de Arestas permitem o estudo do modo como os triângulos são construídos no interior de cada célula de amostragem, e possibilitam identificar onde e como são gerados triângulos de baixa qualidade. As situações onde triângulos de baixa qualidade são gerados são resolvidas através da proposta de três modificações no algoritmo MC, sendo elas: (1) um critério para conduzir a construção da tabela de triangulações, (2) o reposicionamento das arestas ativas e (3) o deslocamento dos vértices de intersecção sobre as arestas ativas. A primeira modificação é a proposta de um novo critério para conduzir a construção da tabela de triangulações do MC. O critério tem como objetivo o aumento da qualidade da malha gerada, através do uso de triangulações que não resultem nos grupos de arestas que têm maior probabilidade de gerar triângulos de baixa qualidade. A segunda modificação propõe o reposicionamento das arestas ativas. Os grupos de arestas mostram que a posição das arestas ativas influencia a qualidade dos triângulos, o que motiva a criação de um procedimento que reposicione as arestas ativas em relação ao comportamento da isosuperfície. Este procedimento resulta na maximização da distância entre os vértices de intersecção e na melhora na qualidade da malha gerada. A terceira modificação propõe o deslocamento dos vértices de intersecção ao longo das arestas ativas. O movimento dos vértices é controlado por um parâmetro que oferece a oportunidade de comprometer a qualidade de aproximação (distância entre a malha gerada e a isosuperfície) em razão da qualidade da malha. O conjunto de modificações propostas resulta no algoritmo Macet (Marching Cubes with Edge Transformations). O Macet é simples e eficiente, gera malhas com qualidade de aproximação igual ou superior à do MC e onde os triângulos de baixa qualidade ainda têm qualidade comparável ou superior aos métodos disponíveis atualmente. / This work sheds a new light on one of the most important algorithms of Computer Graphics, the isosurface polygonization algorithm Marching Cubes (MC). The analysis described here allows the study of situations where low quality triangles are generated, one of the well-know MC drawbacks, and also supports the proposal of extensions for the algorithm. In this work three extensions for MC are also proposed, all with purpose of increase the quality of the resulting triangulations and keep the simplicity, efficiency and robustness of MC. The MC is studied with the breaking of its sampling cells in Edge Groups. The Edge Groups allow the study of how triangles are generated inside each sampling cell, and make possible to identify where and how low quality triangles are generated. The low quality triangle generation is tackled through the proposal of three modifications to the MC algorithm, namely: (1) a new rule to create the look-up table, (2) the warping of active edges and (3) the displacement of cut vertices along active edges. The first modification is the proposal of a new rule to create the triangulations of the MC look-up table. This rule aims the mesh quality improvement through the creation of triangulations that are based on edge groups with fewer chances of generate low quality triangles. The second modification is the proposal of the active edge warping. The edge groups analysis shows that active edges position have a high impact on the triangle quality, which motivates the proposal of a procedure that warps the active edges in response to the isosurface behavior. This procedure results in the maximization of the distance between cut edges, and, consequently, in the overall mesh quality improvement. The third modification is the proposal of the cut vertex displacement along active edges. The vertex displacement is controlled by a user-defined parameter which results in a tradeoff between approximation quality (the distance between the mesh and the “real” isosurface) and the mesh quality. The set of modifications results in the proposal of the Macet (Marching Cubes with Edge Transformations) algorithm. Macet is simple and efficient, and results in high quality meshes with the same (or higher) MC approximation quality.

Este trabalho descreve uma nova visão sobre um dos algoritmos mais importantes da Computação Gráfica, o algoritmo para a poligonização de isosuperfícies Marching Cubes (MC). Esta visão permite o estudo das situações onde são gerados triângulos de baixa qualidade, uma das grandes deficiências do MC, e serve como suporte à proposta de modificações no algoritmo. Neste trabalho também são propostas três modificações ao MC, com objetivo de gerar triângulos de boa qualidade e manter as características mais atraentes do MC, ou seja, a sua simplicidade, eficiência e robustez. O funcionamento do MC é analisado a partir da decomposição das células de amostragem em Grupos de Arestas. Os Grupos de Arestas permitem o estudo do modo como os triângulos são construídos no interior de cada célula de amostragem, e possibilitam identificar onde e como são gerados triângulos de baixa qualidade. As situações onde triângulos de baixa qualidade são gerados são resolvidas através da proposta de três modificações no algoritmo MC, sendo elas: (1) um critério para conduzir a construção da tabela de triangulações, (2) o reposicionamento das arestas ativas e (3) o deslocamento dos vértices de intersecção sobre as arestas ativas. A primeira modificação é a proposta de um novo critério para conduzir a construção da tabela de triangulações do MC. O critério tem como objetivo o aumento da qualidade da malha gerada, através do uso de triangulações que não resultem nos grupos de arestas que têm maior probabilidade de gerar triângulos de baixa qualidade. A segunda modificação propõe o reposicionamento das arestas ativas. Os grupos de arestas mostram que a posição das arestas ativas influencia a qualidade dos triângulos, o que motiva a criação de um procedimento que reposicione as arestas ativas em relação ao comportamento da isosuperfície. Este procedimento resulta na maximização da distância entre os vértices de intersecção e na melhora na qualidade da malha gerada. A terceira modificação propõe o deslocamento dos vértices de intersecção ao longo das arestas ativas. O movimento dos vértices é controlado por um parâmetro que oferece a oportunidade de comprometer a qualidade de aproximação (distância entre a malha gerada e a isosuperfície) em razão da qualidade da malha. O conjunto de modificações propostas resulta no algoritmo Macet (Marching Cubes with Edge Transformations). O Macet é simples e eficiente, gera malhas com qualidade de aproximação igual ou superior à do MC e onde os triângulos de baixa qualidade ainda têm qualidade comparável ou superior aos métodos disponíveis atualmente. / This work sheds a new light on one of the most important algorithms of Computer Graphics, the isosurface polygonization algorithm Marching Cubes (MC). The analysis described here allows the study of situations where low quality triangles are generated, one of the well-know MC drawbacks, and also supports the proposal of extensions for the algorithm. In this work three extensions for MC are also proposed, all with purpose of increase the quality of the resulting triangulations and keep the simplicity, efficiency and robustness of MC. The MC is studied with the breaking of its sampling cells in Edge Groups. The Edge Groups allow the study of how triangles are generated inside each sampling cell, and make possible to identify where and how low quality triangles are generated. The low quality triangle generation is tackled through the proposal of three modifications to the MC algorithm, namely: (1) a new rule to create the look-up table, (2) the warping of active edges and (3) the displacement of cut vertices along active edges. The first modification is the proposal of a new rule to create the triangulations of the MC look-up table. This rule aims the mesh quality improvement through the creation of triangulations that are based on edge groups with fewer chances of generate low quality triangles. The second modification is the proposal of the active edge warping. The edge groups analysis shows that active edges position have a high impact on the triangle quality, which motivates the proposal of a procedure that warps the active edges in response to the isosurface behavior. This procedure results in the maximization of the distance between cut edges, and, consequently, in the overall mesh quality improvement. The third modification is the proposal of the cut vertex displacement along active edges. The vertex displacement is controlled by a user-defined parameter which results in a tradeoff between approximation quality (the distance between the mesh and the “real” isosurface) and the mesh quality. The set of modifications results in the proposal of the Macet (Marching Cubes with Edge Transformations) algorithm. Macet is simple and efficient, and results in high quality meshes with the same (or higher) MC approximation quality.

Este trabalho descreve uma nova visão sobre um dos algoritmos mais importantes da Computação Gráfica, o algoritmo para a poligonização de isosuperfícies Marching Cubes (MC). Esta visão permite o estudo das situações onde são gerados triângulos de baixa qualidade, uma das grandes deficiências do MC, e serve como suporte à proposta de modificações no algoritmo. Neste trabalho também são propostas três modificações ao MC, com objetivo de gerar triângulos de boa qualidade e manter as características mais atraentes do MC, ou seja, a sua simplicidade, eficiência e robustez. O funcionamento do MC é analisado a partir da decomposição das células de amostragem em Grupos de Arestas. Os Grupos de Arestas permitem o estudo do modo como os triângulos são construídos no interior de cada célula de amostragem, e possibilitam identificar onde e como são gerados triângulos de baixa qualidade. As situações onde triângulos de baixa qualidade são gerados são resolvidas através da proposta de três modificações no algoritmo MC, sendo elas: (1) um critério para conduzir a construção da tabela de triangulações, (2) o reposicionamento das arestas ativas e (3) o deslocamento dos vértices de intersecção sobre as arestas ativas. A primeira modificação é a proposta de um novo critério para conduzir a construção da tabela de triangulações do MC. O critério tem como objetivo o aumento da qualidade da malha gerada, através do uso de triangulações que não resultem nos grupos de arestas que têm maior probabilidade de gerar triângulos de baixa qualidade. A segunda modificação propõe o reposicionamento das arestas ativas. Os grupos de arestas mostram que a posição das arestas ativas influencia a qualidade dos triângulos, o que motiva a criação de um procedimento que reposicione as arestas ativas em relação ao comportamento da isosuperfície. Este procedimento resulta na maximização da distância entre os vértices de intersecção e na melhora na qualidade da malha gerada. A terceira modificação propõe o deslocamento dos vértices de intersecção ao longo das arestas ativas. O movimento dos vértices é controlado por um parâmetro que oferece a oportunidade de comprometer a qualidade de aproximação (distância entre a malha gerada e a isosuperfície) em razão da qualidade da malha. O conjunto de modificações propostas resulta no algoritmo Macet (Marching Cubes with Edge Transformations). O Macet é simples e eficiente, gera malhas com qualidade de aproximação igual ou superior à do MC e onde os triângulos de baixa qualidade ainda têm qualidade comparável ou superior aos métodos disponíveis atualmente. / This work sheds a new light on one of the most important algorithms of Computer Graphics, the isosurface polygonization algorithm Marching Cubes (MC). The analysis described here allows the study of situations where low quality triangles are generated, one of the well-know MC drawbacks, and also supports the proposal of extensions for the algorithm. In this work three extensions for MC are also proposed, all with purpose of increase the quality of the resulting triangulations and keep the simplicity, efficiency and robustness of MC. The MC is studied with the breaking of its sampling cells in Edge Groups. The Edge Groups allow the study of how triangles are generated inside each sampling cell, and make possible to identify where and how low quality triangles are generated. The low quality triangle generation is tackled through the proposal of three modifications to the MC algorithm, namely: (1) a new rule to create the look-up table, (2) the warping of active edges and (3) the displacement of cut vertices along active edges. The first modification is the proposal of a new rule to create the triangulations of the MC look-up table. This rule aims the mesh quality improvement through the creation of triangulations that are based on edge groups with fewer chances of generate low quality triangles. The second modification is the proposal of the active edge warping. The edge groups analysis shows that active edges position have a high impact on the triangle quality, which motivates the proposal of a procedure that warps the active edges in response to the isosurface behavior. This procedure results in the maximization of the distance between cut edges, and, consequently, in the overall mesh quality improvement. The third modification is the proposal of the cut vertex displacement along active edges. The vertex displacement is controlled by a user-defined parameter which results in a tradeoff between approximation quality (the distance between the mesh and the “real” isosurface) and the mesh quality. The set of modifications results in the proposal of the Macet (Marching Cubes with Edge Transformations) algorithm. Macet is simple and efficient, and results in high quality meshes with the same (or higher) MC approximation quality.

Det finns flera olika metoder och tekniker för tredimensionell rendering, alla med olika för- och nackdelar som lämpar sig för olika applikationer. Voxelbaserad rendering har använts flitigt inom vetenskapliga områden, främst inom det medicinska för visualisering av volymetrisk data. Tekniken används nu inom flera olika områden för tredimensionell rendering, t.ex. i datorspel, i matematiska applikationer och vid geologisk rekonstruktion. I den här rapporten kommer voxelbaserad rendering med Marching Cubes-algoritmen undersökas för att se hur den lämpar sig för realtidsapplikationer. Området behandlas dels teoretiskt, men även praktiskt då en implementering av Marching Cubes gjordes för att genomföra några tester för att se hur prestandan påverkades. Av testerna framkom det tydligt att algoritmen lämpar sig väl för realtidsapplikationer och dagens grafikkort. Viss optimering krävs dock för att kunna utnyttjas på bästa sätt. / There are lots of different methods and techniques for three-dimensional rendering, everyone with different advantages and disadvantages that suits different applications. Voxel-based rendering has been used frequently within the scientific area, mainly within medicin for visualization of volumetric data. The technique is now used within many different areas for three-dimensional rendering, e.g. in computer games, in mathematical applications and in geological reconstruction. In this report voxel-based rendering with Marching Cubes algorithm will be researched to see how it suits for real-time applications. The area will partly be dealt with theoretically, but also practically as an implementation of Marching Cubes was done to run some tests to see how the performance was affected. From the tests it appeared cleary that the algorithm is well suited for real-time applications and today's graphics card. Though some optimization is needed to fully take advantage of it.

Volumetric visualization is something that has become more interesting during recent years. It has been something that was not feasible in an interactive environment due to its complexity in the 3D space. However, today's technology and access to the power of the graphics processing unit (GPU) has made it feasible to render volumetric data interactively. This thesis explores the possibilities to create and render large volumetric terrain using an implementation of Marching Cubes on the GPU. With the advent of general-purpose computing on the GPU (GPGPU) it has become far easier to implement tradition CPU tasks on the GPU. By utilizing newly available functions in DirectX it is possible to create an easier implementation on the GPU using global buffers. Three implementations are created inside the Unity game engine using compute shaders. The implementations are then compared based on creation time, render times and memory consumption. Then a deeper analysis of the time distribution is presented which suggests that Unity introduces some overhead since copying buffers from GPU to CPU is time consuming. It did however improve render times due to its culling and optimization techniques. The system could be used in applications such as games or medical visualization. Finally some future improvements for culling and level of detail (LOD) techniques are discussed. / Volumetrisk visualisering är en teknik som har fått mer uppmärksamhet dom senaste åren. Det har varit någonting som inte har varit rimligt att göra i en interaktiv miljö på grund av dess komplexitet i 3D rymden. Med dagens teknik och tillgänglighet till grafikkortet (GPU) är det nu möjligt att rendera volumetrisk data i en interaktiv miljö. Den här uppsatsen utforskar möjligheterna till att skapa och rendera stora terräng landskap genom en implementering av Marching Cubes på GPU:n. Med framkomsten av general-purpose computing på grafikkortet(GPGPU) har det blivit lättare att programmera på GPU:n. Genom att använda nya funktioner tillgängliga i DirectX är det möjligt att skapa en enklare implementering på GPU:n som använder sig av globala buffrar. Tre implementeringar har skapats i spelmotorn Unity som använder compute shaders. Implementeringarna är sedan jämförda baserad på tid för generering av terräng, renderings tid samt minnes konsumption. Detta följs av en djupare analys av tidsdistribueringen för skapandet som pekar på att Unity håller tillbaka systemets hastiget pga kopierande av minne från GPU:n till CPU:n. Renderingstiden blev dock bättre med hjälp av den inbyggda culling-teknikerna och optimerings tekniker. Detta system skulle kunna appliceras inom spel eller medicinsk visualisering. Slutligen diskuteras framtida förbättringar för culling-tekniker och level of detail (LOD) tekniker.

No description available.

[pt] O Marching Cubes 33 proposto por Chernyaev é um dos primeiros algoritmos de extração de isosuperfície destinados a preservar a topologia do interpolante trilinear. Neste trabalho, abordamos três problemas no algoritmo do Marching Cubes 33, dois dos quais estão relacionados com a sua descrição original. Em particular, resolvemos um problema no procedimento para resolver ambiguidades interiores do Marching Cubes 33, que impede que a isosuperfície seja extraída corretamente para o caso ambíguo 13.5. O algoritmo Marching Cubes é considerado simples, robusto e com baixo custo computacional, características que contribuíram para torná-lo popular entre os algoritmo de extração de isosuperfícies. Porém no que se refere a qualidade da triangulação da malha resultante, não raramente observamos um grande número de triângulos finos (triângulos com ângulos pequenos) e até mesmo degenerados (triângulos com área zero). Buscando unir à coerência topológica uma melhor qualidade na triangulação gerada, propomos uma extensão da tabela de triangulação proposta por Chernyaev, de modo que os vértices da grade passem a fazer parte da triangulação, eliminando assim a possibilidade de geração de triângulos degenerados. Esta nova tabela é utilizada para evitar a criação de triângulos finos, através de pequenas alterações do campo escalar nos vértices da grade. / [en] Chernyaev s Marching Cubes 33 is one of the first isosurface extraction algorithms intended to preserve the topology of the trilinear interpolant. In this work, we address three issues in the Marching Cubes 33 algorithm, two of which are related to its original description. In particular, we solve a problem with the core disambiguation procedure of Marching Cubes 33 that prevents the extraction of topologically correct isosurfaces for the ambiguous configuration 13.5 thus fixing the original formulation of the algorithm. The Marching Cubes algorithm is considered simple, robust and with low computational cost, characteristics that contributed to make it the most popular algorithm for isosurfaces extraction. However, regarding the quality of the resulting mesh, frequently it is possible to observe a large number of badly-shaped triangles (triangles with small angles) and even degenerate (triangles with zero area) ones. Seeking to unite a better triangulation quality of the resulting mesh to the topological consistency, we propose an extension of the triangulation table proposed by Chernyaev, so that the vertices of the grid become part of the triangulation generated, thus eliminating the possibility of generation of degenerate triangles. This new table is used to avoid the creation of badly-shaped triangles via small changes of the scalar field on the vertices of the grid.

We present an implicit approach for constructing smooth isolated or interconnected 3-D inscribed volumes which can be employed for volumetric modeling of various kinds of spongy or porous structures, such as volcanic rocks, pumice stones, Cancellus bones *, liquid or dry foam, radiolarians, cheese, and other similar materials. The inscribed volumes can be represented in their normal or positive forms to model natural pebbles or pearls, or in their inverted or negative forms to be used in porous structures, but regardless of their types, their smoothness and sizes are controlled by the user without losing the consistency of the shapes. We introduce two techniques for blending and creating interconnections between these inscribed volumes to achieve a great flexibility to adapt our approach to different types of porous structures, whether they are regular or irregular. We begin with a set of convex polytopes such as 3-D Voronoi diagram cells and compute inscribed volumes bounded by the cells. The cells can be irregular in shape, scale, and topology, and this irregularity transfers to the inscribed volumes, producing natural-looking spongy structures. Describing the inscribed volumes with implicit functions gives us a freedom to exploit volumetric surface combinations and deformations operations effortlessly / Graduate

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. / Hot tearing is a major defect arising during solidification of aluminium alloys. This defect is associated with the inability of liquid to feed areas where voids have started to appear, not allowing to heal small defects before they grow bigger. To understand hot tearing, it is mandatory to develop a good knowledge of the semi-solid mechanical behaviour. It is thus very useful to carry out X-ray microtomographies experiments and mechanical simulations on representative elementary volumes. In this work, we couple the both approaches by initialising a finite element simulation with the help of microtomography data obtained during an isothermal tensile testing of an aluminium-copper alloy in the mushy state. This innovative approach gives a direct access to the experimental reality and allows comparisons of numerical and experimental evolutions of the sample. We explain in a first time how to get the numerical representation thanks to a marching cubes algorithm and the immersed volume method. Then, we present our numerical model for which we solve the Stokes equations in a monolithic way. Once the velocity computed in all the solid, liquid and gaseous phases, we use a level set method in a Eulerian formalism to obtain the morphological evolution of our numerical sample. Despite the model simplicity, numerical and experimental results show a reasonable agreement concerning the air propagation inside the sample.