A síntese de imagens é uma ferramenta valiosa na compreensão de diversos fenômenos da natureza. Nos últimos anos várias abordagens têm sido propostas para sintetizar tais fenômenos. A grande maioria de tais abordagens têm se centralizado no desenvolvimento de modelos procedurais. Porém, cada uma destas técnicas simula exclusivamente um fenômeno natural. Um dos métodos de síntese de imagens fotorealísticas mais proeminente é denominado de Traçado de Raios (Ray Tracing). Contudo, apesar de produzir imagens de excelente qualidade, este método é computacionalmente muito oneroso. A síntese de fenômenos naturais utilizando-se o traçado de raios é um desafio. É importante que este problema seja abordado, apesar da sua complexidade, pois a simulaçao fotorealista da natureza é muito importante para os cientistas e pesquisadores desde o surgimento dos computadores. Um algoritmo versátil e rápido para a síntese de fenômenos da natureza através do traçado de raios utilizando campos de altitude é proposto. O algoritmo utiliza uma modificação do algoritmo do Analisador Diferencial Digital de Bresenham para atravesar uma matriz bidimensional de valores de altitude. A determinação das primitivas geométricas a serem interseccionadas por um raio é obtida num tempo ( N ) , sendo N o número de altitudes no campo de altitude. Este trabalho faz uma comparação em termos de velocidade e realismo deste método com outras abordagens convencionais; e discute as implicações que a implementação deste método traz. Finalmente, destaca-se a simplicidade e versatilidade que este método proporciona devido à pequena quantidade de parâmetros necessária para a síntese de fenômenos naturais utilizando o traçado de raios. Para a criação de animações basta a especificação de novos parâmetros num intervalo de tempo diferente. / Visualization is a powerful tool for better undestanding of several natural phenomena. In recent years, several techniques have been proposed. Considerable interest in natural scene synthesis has focused on procedural models. However, these techniques produce synthetic scenes of only one natural phenomenon. Ray tracing is one of the most photorealistic methods of image syntesis. While providing images of excellent quality, ray tracing is a computationally intensive task. Natural scene synthesis is a challenging problem within the realm of ray tracing. It is important to tackle this problem, despite of its complexity, because photorealistic simulation have been important to scientific community since the appearance of computers. A fast and versatile algorithm for ray tracing natural scenes through height fields is presented. The algorithm employs a modified Bresenham DDA to traverse a two dimensional array of values. The objects tested for intersection are located in ( N ) time where N is the number of values in the field. This work compares the speed-up and photorealism achieved in natural scene synthesis using this method with other algorithms and discusses the implications of implementing this approach. As a final point, the simplicity and versatility of synthesizing complex natural scenes from a few parameters and data is especially attractive. Animated sequences require only the additional specifications of time modified parameters or data.

Synthetically generated terrain models are useful across a broad range of applications, including computer generated art & animation, virtual reality and gaming, and architecture. Existing algorithms for terrain generation suffer from a number of problems, especially that of being limited in the types of terrain that they can produce and of being difficult for the user to control. Typical applications of synthetic terrain have several factors in common: first, they require the generation of large regions of believable (though not necessarily physically correct) terrain features; and second, while real-time performance is often needed when visualizing the terrain, this is generally not the case when generating the terrain. In this thesis, I present a new, design-by-example method for synthesizing terrain height fields. In this approach, the user designs the layout of the terrain by sketching out simple regions using a CAD-style interface, and specifies the desired terrain characteristics of each region by providing example height fields displaying these characteristics (these height fields will typically come from real-world GIS data sources). A height field matching the user's design is generated at several levels of detail, using a genetic algorithm to blend together chunks of elevation data from the example height fields in a visually plausible manner. This method has the advantage of producing an unlimited diversity of reasonably realistic results, while requiring relatively little user effort and expertise. The guided randomization inherent in the genetic algorithm allows the algorithm to come up with novel arrangements of features, while still approximating user-specified constraints.

A síntese de imagens é uma ferramenta valiosa na compreensão de diversos fenômenos da natureza. Nos últimos anos várias abordagens têm sido propostas para sintetizar tais fenômenos. A grande maioria de tais abordagens têm se centralizado no desenvolvimento de modelos procedurais. Porém, cada uma destas técnicas simula exclusivamente um fenômeno natural. Um dos métodos de síntese de imagens fotorealísticas mais proeminente é denominado de Traçado de Raios (Ray Tracing). Contudo, apesar de produzir imagens de excelente qualidade, este método é computacionalmente muito oneroso. A síntese de fenômenos naturais utilizando-se o traçado de raios é um desafio. É importante que este problema seja abordado, apesar da sua complexidade, pois a simulaçao fotorealista da natureza é muito importante para os cientistas e pesquisadores desde o surgimento dos computadores. Um algoritmo versátil e rápido para a síntese de fenômenos da natureza através do traçado de raios utilizando campos de altitude é proposto. O algoritmo utiliza uma modificação do algoritmo do Analisador Diferencial Digital de Bresenham para atravesar uma matriz bidimensional de valores de altitude. A determinação das primitivas geométricas a serem interseccionadas por um raio é obtida num tempo ( N ) , sendo N o número de altitudes no campo de altitude. Este trabalho faz uma comparação em termos de velocidade e realismo deste método com outras abordagens convencionais; e discute as implicações que a implementação deste método traz. Finalmente, destaca-se a simplicidade e versatilidade que este método proporciona devido à pequena quantidade de parâmetros necessária para a síntese de fenômenos naturais utilizando o traçado de raios. Para a criação de animações basta a especificação de novos parâmetros num intervalo de tempo diferente. / Visualization is a powerful tool for better undestanding of several natural phenomena. In recent years, several techniques have been proposed. Considerable interest in natural scene synthesis has focused on procedural models. However, these techniques produce synthetic scenes of only one natural phenomenon. Ray tracing is one of the most photorealistic methods of image syntesis. While providing images of excellent quality, ray tracing is a computationally intensive task. Natural scene synthesis is a challenging problem within the realm of ray tracing. It is important to tackle this problem, despite of its complexity, because photorealistic simulation have been important to scientific community since the appearance of computers. A fast and versatile algorithm for ray tracing natural scenes through height fields is presented. The algorithm employs a modified Bresenham DDA to traverse a two dimensional array of values. The objects tested for intersection are located in ( N ) time where N is the number of values in the field. This work compares the speed-up and photorealism achieved in natural scene synthesis using this method with other algorithms and discusses the implications of implementing this approach. As a final point, the simplicity and versatility of synthesizing complex natural scenes from a few parameters and data is especially attractive. Animated sequences require only the additional specifications of time modified parameters or data.

A síntese de imagens é uma ferramenta valiosa na compreensão de diversos fenômenos da natureza. Nos últimos anos várias abordagens têm sido propostas para sintetizar tais fenômenos. A grande maioria de tais abordagens têm se centralizado no desenvolvimento de modelos procedurais. Porém, cada uma destas técnicas simula exclusivamente um fenômeno natural. Um dos métodos de síntese de imagens fotorealísticas mais proeminente é denominado de Traçado de Raios (Ray Tracing). Contudo, apesar de produzir imagens de excelente qualidade, este método é computacionalmente muito oneroso. A síntese de fenômenos naturais utilizando-se o traçado de raios é um desafio. É importante que este problema seja abordado, apesar da sua complexidade, pois a simulaçao fotorealista da natureza é muito importante para os cientistas e pesquisadores desde o surgimento dos computadores. Um algoritmo versátil e rápido para a síntese de fenômenos da natureza através do traçado de raios utilizando campos de altitude é proposto. O algoritmo utiliza uma modificação do algoritmo do Analisador Diferencial Digital de Bresenham para atravesar uma matriz bidimensional de valores de altitude. A determinação das primitivas geométricas a serem interseccionadas por um raio é obtida num tempo ( N ) , sendo N o número de altitudes no campo de altitude. Este trabalho faz uma comparação em termos de velocidade e realismo deste método com outras abordagens convencionais; e discute as implicações que a implementação deste método traz. Finalmente, destaca-se a simplicidade e versatilidade que este método proporciona devido à pequena quantidade de parâmetros necessária para a síntese de fenômenos naturais utilizando o traçado de raios. Para a criação de animações basta a especificação de novos parâmetros num intervalo de tempo diferente. / Visualization is a powerful tool for better undestanding of several natural phenomena. In recent years, several techniques have been proposed. Considerable interest in natural scene synthesis has focused on procedural models. However, these techniques produce synthetic scenes of only one natural phenomenon. Ray tracing is one of the most photorealistic methods of image syntesis. While providing images of excellent quality, ray tracing is a computationally intensive task. Natural scene synthesis is a challenging problem within the realm of ray tracing. It is important to tackle this problem, despite of its complexity, because photorealistic simulation have been important to scientific community since the appearance of computers. A fast and versatile algorithm for ray tracing natural scenes through height fields is presented. The algorithm employs a modified Bresenham DDA to traverse a two dimensional array of values. The objects tested for intersection are located in ( N ) time where N is the number of values in the field. This work compares the speed-up and photorealism achieved in natural scene synthesis using this method with other algorithms and discusses the implications of implementing this approach. As a final point, the simplicity and versatility of synthesizing complex natural scenes from a few parameters and data is especially attractive. Animated sequences require only the additional specifications of time modified parameters or data.

Maritime network plays an important role in civilian and academic applications. However, traditional maritime communication technologies cannot provide broadband services that can satisfy users' need. In this thesis, we proposed a buoy-based maritime mesh network and analyzed the maritime communication characteristics. Then we proposed a link-state-aware routing protocol to address link blockage problem when routing packets and built a simulator to evaluate the network performance. There are several parts of my work. Firstly, we simulated ocean water field. Jerry Tessendorf proposed a method to create ocean surface based on Phillips spectrum which is a wind-driven, semi-empirical oceanography model. We implemented this algorithm in MATLAB and adjusted a key parameter in this algorithm. Secondly, we proposed a link-state-aware routing protocol. Link stability is related to sea state and instant nodes elevation. In link-state-aware routing protocol, the transmitter will send predicted elevation information to receiver, and receiver will decide if the link is stable in next several seconds based on sea states and node elevation information. Finally, we simulated this mesh network in network simulator 3 (NS3). This simulator will enable users to assess the network performance in various sea states. We also need to build a new mobility model, a new propagation model and implement a collision-free access method (spatial TDMA) model in simulation. / Master of Science / Due to burst growth of network coverage, seamless broadband connectivity has been realized in both our daily life and industrial operations. However, wireless communication coverage fades away when moving just several miles away from the coast. Current marine communication technologies cannot provide stable and broadband service, so we proposed a buoy-based maritime mesh network. In this thesis, we built a network simulator which integrates with several new models after analyzed the dynamic ocean wave motion and maritime communication link characteristics.

Delaunay refinement is a mesh triangulation method with the goal of generating well-shaped triangles to obtain a valid Delaunay triangulation. In this thesis, an approach of using this method for meshing continuous height field terrains is presented using Perlin noise as the height field. The Delaunay approach is compared to grid-based meshing to verify that the theoretical time complexity O(n log n) holds and how accurately and deterministically the Delaunay approach can represent the height field. However, even though grid-based mesh generation is faster due to an O(n) time complexity, the focus of the report is to find out if Delaunay refinement can be used to generate meshes quick enough for real-time applications. As the available memory for rendering the meshes is limited, a solution for providing a cohesive mesh surface is presented using a hole filling algorithm since the Delaunay approach ends up leaving gaps in the mesh when a chunk division is used to limit the total mesh count present in the application. The methods were implemented in the programming language C++ using the open source library libnoise to generate the Perlin noise and the off-the-shelf solution CGALmesh provided a Delaunay refinement implementation. The video game engine Unity was used to render the output meshes created by the Delaunay and grid approach by interfacing with C++ via a Windows DLL. The time complexity of Delaunay refinement was verified to hold, although it was not possible to draw any conclusions regarding the Delaunay refinement's impact on the mesh's accuracy due to the test parameters used. It was also found that the CGALmesh implementation failed to provide a deterministic generation which is a significant drawback compared to the grid-based approach. Disregarding this, the Delaunay approach was found to be suitable for real-time applications as the generation time took less than 1 second, and is promising for volumetric terrain mesh generation. / Delaunay-raffinemang är en trianguleringsmetod med målet att generera reguljära trianglar för att uppnå en giltig Delaunay-triangulering. I denna avhandling presenteras en metod användandes Delaunay-raffinemang för att skapa polygonytor av kontinuerliga höjdfältsterränger, där Perlin noise används som höjdfält. Delaunay-metoden jämförs med en rutnätsbaserad metod för att verifiera att tidskomplexiteten O(n log n) gäller och hur exakt och deterministiskt som Delaunay-metoden förhåller sig till att representera höjdfältet. Även fast rutnätsmetoden är snabbare på grund av en O(n) tidskomplexitet är rapportens fokus att ta reda på om Delaunay-raffinemang är snabb nog för att användas i realtidsapplikationer för att generera polygonytor. Eftersom det tillgängliga minnet för att rendera polygonytorna är begränsat presenteras en lösning för att få sammanhängande ytor genom en hålutfyllningsalgoritm då Delaunaymetoden lämnar hål i ytan när chunk-uppdelning används för att begränsa det totala antalet polygonytor i applikationen. Metoderna implementerades i programmeringsspråket C++ användades biblioteket libnoise för att generera Perlin noise och den färdiga lösningen CGALmesh användes som implementation av Delaunay-raffinemang. Datorspelsmotorn Unity användes för att rendera polygonytorna som skapades av Delaunay- och rutnätsmetoden genom ett C++-gränssnitt via en Windows DLL. Tidskomplexiteten av Delaunay-raffinemang gällde, men det var inte möjligt att dra några slutsatser gällande hur exakt metoden förhållde sig till höjdfältet på grund av testparametrarna som användes. Ytterligare visade det sig att CGALmesh-implementationen var oförmögen att deterministiskt generera ytorna vilket är en stor nackdel jämfört med rutnätsmetoden. Bortsett från detta så visade sig Delaunay-metoden användbar för realtidsapplikationer då generingstiden tog mindre än 1 sekund, och metoden har dessutom potential för volymetrisk terränggenerering.

A height field is a set of height distance values sampled at a finite set of sample points in a two-dimensional parameter domain. A height field usually contains a lot of redundant information, much of which can be removed without a substantial degradation of its quality. A common approach to reducing the size of a height field representation is to use a piecewise polygonal surface approximation. This consists of a mesh of polygons that approximates the surfaces of the original data at a desired level of accuracy. Polygonal surface approximation of height fields has numerous applications in the fields of computer graphics and computer vision. Triangular mesh approximations are a popular means of representing three-dimensional surfaces, and multiresolution analysis (MRA) is often used to obtain compact representations of dense input data, as well as to allow surface approximations at varying spatial resolution. Multiresolution approaches, particularly those moving from coarse to fine resolutions, can often improve the computational efficiency of mesh generation as well as can provide easy control of level of details for approximations. This dissertation concerns the use of wavelet-based MRA methods to produce a triangular-mesh surface approximation from a single height field dataset. The goal of this study is to obtain a fast surface approximation for a set of height data, using a small number of approximating elements to satisfy a given error criterion. Typically, surface approximation techniques attempt to balance error of fit, number of approximating elements, and speed of computation. A novel aspect of this approach is the direct evaluation of wavelet coefficients to assess surface shape characteristics within each triangular element at a given scale. Our approach hierarchically subdivides and refines triangles as the resolution level increases. / Ph. D.

This work deals with design and implementation of simple demonstration aplication for simulation of a water flow on irregular terrain. The work examines essential building blocks of the simulation. It also suggests approaches that can be used to optimize and/or extend used method.

Real-time rendering of large-scale terrains is a difficult problem and remains an active field of research. The massive scale of these landscapes, where the ratio between the size of the terrain and its resolution is spanning multiple orders of magnitude, requires an efficient level of detail strategy. It is crucial that the geometry, as well as the terrain data, are represented seamlessly at varying distances while maintaining a constant visual quality. This thesis investigates common techniques and previous solutions to problems associated with the rendering of height field terrains and discusses their benefits and drawbacks. Subsequently, two solutions to the stated problems are presented, which build and expand upon the state-of-the-art rendering methods. A seamless and efficient mesh representation is achieved by the novel Uniform Distance-Dependent Level of Detail (UDLOD) triangulation method. This fully GPU-based algorithm subdivides a quadtree covering the terrain into small tiles, which can be culled in parallel, and are morphed seamlessly in the vertex shader, resulting in a densely and temporally consistent triangulated mesh. The proposed Chunked Clipmap combines the strengths of both quadtrees and clipmaps to enable efficient out-of-core paging of terrain data. This data structure allows for constant time view-dependent access, graceful degradation if data is unavailable, and supports trilinear and anisotropic filtering. Together these, otherwise independent, techniques enable the rendering of large-scale real-world terrains, which is demonstrated on a dataset encompassing the entire Free State of Saxony at a resolution of one meter, in real-time.

Cotutelle avec l'Université de Poitiers, France / Lors du processus de création d’une image de synthèse photoréaliste, l’objectif principal recherché est de reproduire le transport de la lumière dans un environnement virtuel, en prenant en compte aussi précisément que possible les caractéristiques des objets de la scène 3D. Dans la perception de notre environnement, les détails très fins ont une grande importance sur l’apparence des objets, tels que des rayures sur un morceau de métal, des particules dans du vernis, ou encore les fibres d'un tissu. Il est primordial de pouvoir les reproduire à tout niveau d'échelle. Créer ces détails grâce à des informations géométriques, par exemple un maillage, mène à une trop forte complexité en termes de construction, de stockage, de manipulation et de temps de rendu. Il est donc nécessaire d’utiliser des modèles mathématiques qui permettent d’approcher au mieux les comportements lumineux induits par ces détails. Le travail de cette thèse s'inscrit dans cette problématique de gestion des détails fins par la théorie des microfacettes. En particulier, nous nous sommes intéressés à la notion de masquage-ombrage permettant de calculer la proportion de surface qui est à la fois visible de l’observateur et éclairée. Pour cela, nous étudions le modèle théorique proposé par Smith et par Ashikhmin et al. dans lequel la représentation mathématique est basée sur des contraintes liées à la position des facettes, leur orientation, leur aire et les corrélations entre ces caractéristiques. Nous avons éprouvé le modèle sur plus de 400 maillages 3D reconstruits à partir de surfaces réelles qui ne respectent pas nécessairement les contraintes imposées du modèle. Quelques maillages sont également générés à partir de distributions des orientations de microfacettes de Beckmann et GGX largement utilisées dans les moteurs de simulation académiques et industriels. Pour chacun des maillages, une fonction de masquage de référence est mesurée grâce à un algorithme de tracer de rayons. Nous pouvons ainsi comparer le masquage réel d'une microsurface prenant en compte la donnée dans son entièreté, à son masquage théorique calculé seulement par la distribution de ses micronormales. Cette étude met en évidence un lien entre l'erreur du masquage théorique et certaines caractéristiques de la microsurface, telles que sa rugosité, son anisotropie, ou le non respect des contraintes du modèle. Nous proposons une méthode pour développer un modèle prédictif de l'erreur calculable à partir de ces caractéristiques et sans avoir recours au lourd processus de tracer de rayons. L’analyse montre également le lien entre l'erreur au niveau du terme de masquage et sa répercussion dans le rendu final d'une image de synthèse. La possibilité de prédire l'erreur grâce à un processus rapide permet d'estimer la complexité de l'usage d'une microgéométrie dans un rendu photoréaliste. Nous complétons nos travaux en proposant un facteur correctif au masquage théorique pour les surfaces isotropes, là encore calculable directement à partir des caractéristiques du maillage. Nous montrons le gain de précision que cette correction apporte, tant au niveau du masquage lui-même qu'au niveau des rendus d'images de synthèse. La thèse est conclue avec une discussion présentant les limites actuelles de notre étude et ses perspectives futures. / During the creation process of a photorealistic image, the main goal is to reproduce light transport in a virtual environment by considering as accurately as possible the characteristics of the surfaces from the 3D scene. In the real world, very fine details may have a tremendous impact on the visual aspect. For instance, scratches over metal, particles within varnish, or fibers of a fabric, will visually alter surface appearance. It is therefore crucial to be able to simulate such effects at every level of detail. However, creating such microgeometry for a given 3D mesh is a complex task that results in very high memory requirements and computation time. Mathematical models must be used to approximate as precisely as possible light effects produced by these details. This thesis considers fine details from the microfacet theory, and in particular, the masking-shadowing factor that corresponds to the proportion of microsurfaces that are both visible and illuminated. We study the commonly used theoretical model of Smith and Ashikhmin et al. where the mathematical representation is derived from constraints about microfacets positions, orientations, areas, and correlations between those characteristics. The proposed model has been confronted to more than 400 3D meshes, built from real-world measured surfaces that do not necessarily fulfill the theory constraints. Some of them have also been generated from the widely used Beckmann and GGX distributions. For each mesh, the ground-truth masking effect is measured using ray tracing, and compared with the theoretical masking computed only from the distribution of micronormals. Our study highlights a connection between the theoretical masking's error and some microsurface's characteristics, such as roughness, anisotropy, or non-compliance with required constraints. We provide a method for deriving a predictive model for this error. The mesh characteristics are sufficient to compute this model without requiring heavy ray tracing computation. Our analysis shows how the masking error impacts the rendering process. We also derive a model capable of predicting rendering errors from surface characteristics. With the opportunity to predict the error with a fast computation from a 3D mesh, one can estimate the complexity to use a given microgeometry for a photorealistic rendering. Our study concludes with the formulation of a correction function added to the theoretical masking term for isotropic surfaces. This correction is computed directly from the 3D mesh characteristics without any ray tracing involved. We show gains in the accuracy of the model when corrected with our formula, both for the masking effect itself and its impact on the exactness of the renderings. This thesis is concluded with a discussion about the current limitations of our study and some future perspectives.