Thesis (Ph. D.)--Ohio State University, 2009. / Title from first page of PDF file. Includes vita. Includes bibliographical references (p. 161-162).

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.

Webben används i allt större utsträckning som en riktig applikationsplattform, mycket tack vare HTML5. Detta ställer högre krav på webbapplikationens prestanda på klientsidan, då nya tekniker möjliggör mer avancerade applikationer. Parallellisering är en metod för att öka prestandan i applikationer, som dessutom tar nytta av de parallella arkitekturer som idag är vanliga. Web workers – ett nytt API för JavaScript – tillåter en enkel form av parallellisering för webbapplikationer. Dock har web workers en del begränsningar som minskar antalet möjliga strategier. Detta arbete syftar till att utvärdera hur valet av parallelliseringsstrategi påverkar prestandan hos en JavaScript-implementation av marching squares – en algoritm med goda möjligheter för parallellisering. Tre olika strategier implementeras, och utvärderas därefter genom prestandamätning. Resultaten visar att en strategi som använder så lite och så optimerad kommunikation som möjligt ger bättre prestanda än en strategi med mer kommunikation. Vidare arbete för att bland annat utvärdera vinsterna av delat minne föreslås.

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.

No description available.

Typescript (photocopy). / Digitized by Kansas Correctional Industries / Department: Music.