This thesis presents a method based on Smoothed Particle Hydrodynamics to simulate sparse particle systems with fluid like properties in real-time. The simulation supports interactions with terrain and objects and is scaled depending on activity of the fluid. We use a carpet method on the GPU to visualize the water surface with translucency, reflection, refraction and added topology. Splash effects and foam are imitated and added as a last step.

This report describes a basic implementation of scene voxelization within the Frostbite engine created by EA Frostbite. The algorithm supports dynamic scenes by voxelizing in real-time using the Graphical Programming Unit. The voxel grid is stored inside a buffer with a binary representation using clip mapping and multiple levels of detail. An ambient occlusion algorithm is implemented to show the benefits of the structure. Results from running the application within the engine is presented, both with figures showing the resulting image and timings for diifferent parts of the algorithm. Several future improvements to make the algorithm more competitive is presented as well.

Depuis quelques années, les grappes équipées de processeurs graphiques GPUs sont devenues des outils très attrayants pour le calcul parallèle haute performance. Dans cette thèse, nous avons conçu des algorithmes itératifs parallèles pour la résolution de systèmes linéaires et non linéaires creux de très grandes tailles sur grappes de GPUs. Dans un premier temps, nous nous sommes focalisés sur la résolution de systèmes linéaires creux à l'aide des méthodes itératives CG et GMRES. Les expérimentations ont montré qu'une grappe de GPUs est plus performante que son homologue grappe de CPUs pour la résolution de systèmes linéaires de très grandes tailles. Ensuite, nous avons mis en oeuvre des algorithmes parallèles synchrones et asynchrones des méthodes itératives Richardson et de relaxation par blocs pour la résolution de systèmes non linéaires creux. Nous avons constaté que les meilleurs solutions développées pour les CPUs ne sont pas nécessairement bien adaptées aux GPUs. En effet, les simulations effectuées sur une grappe de GPUs ont montré que les algorithmes Richardson sont largement plus efficaces que ceux de relaxation par blocs. De plus, elles ont aussi montré que la puissance de calcul des GPUs permet de réduire le rapport entre le temps d'exécution et celui de communication, ce qui favorise l'utilisation des algorithmes asynchrones sur des grappes de GPUs. Enfin, nous nous sommes intéressés aux grappes géographiquement distantes pour la résolution de systèmes linéaires creux. Dans ce contexte, nous avons utilisé la méthode de multi-décomposition à deux niveaux avec GMRES parallèle adaptée aux grappes de GPUs. Celle-ci utilise des itérations synchrones pour résoudre localement les sous-systèmes linéaires et des itérations asynchrones pour résoudre la globalité du système linéaire. / Or the past few years, the clusters equipped with GPUs have become attractive tools for high performance computing. In this thesis, we have designed parallel iterative algorithms for solving large sparse linear and nonlinear systems on GPU clusters. First, we have focused on solving sparse linear systems using CG and GMRES iterative methods. The experiments have shown that a GPU cluster is more efficient that its pure CPU counterpart for solving large sparse systems of linear equations. Then, we have implemented the synchronous and asynchronous algorithms of the Richardson and the block relaxation iterative methods for solving sparse nonlinear systems. We have noticed that the best solutions developed for the CPUs are not necessarily well suited to GPUs. Indeed, the experiments performed on a GPU cluster have shown that the parallel algorithms of the Richardson method are far more efficient than those of the block relaxation method. In addition, they have shown that the computing power of GPUs allows to reduce the ratio between the time of the computation over that of the communication, which favors the use of the asynchronous iteration on GPU clusters. Finally, we are interested in geographically distant clusters for solving large sparse linear systems. In this context, we have used a multisplitting two-stage method using parallel GMRES method adapted to GPU clusters. It uses the synchronous iteration to solve locally the sub-linear systems and the asynchronous one to solve the global sparse linear system.

L'objectif principal est de faire premiers pas vers la conception topologique de structures hétérogènes à comportement non-linéaires. Le deuxième objectif est d’optimiser simultanément la topologie de la structure et du matériau. Il requiert la combinaison des méthodes de conception optimale et des approches de modélisation multi-échelle. En raison des lourdes exigences de calcul, nous avons introduit des techniques de réduction de modèle et de calcul parallèle. Nous avons développé tout d’abord un cadre de conception multi-échelle constitué de l’optimisation topologique et la modélisation multi-échelle. Ce cadre fournit un outil automatique pour des structures dont le modèle de matériau sous-jacent est directement régi par la géométrie de la microstructure réaliste et des lois de comportement microscopiques. Nous avons ensuite étendu le cadre en introduisant des variables supplémentaires à l’échelle microscopique pour effectuer la conception simultanée de la structure et de la microstructure. En ce qui concerne les exigences de calcul et de stockage de données en raison de multiples réalisations de calcul multi-échelle sur les configurations similaires, nous avons introduit: les approches de réduction de modèle. Nous avons développé un substitut d'apprentissage adaptatif pour le cas de l’élasticité non-linéaire. Pour viscoplasticité, nous avons collaboré avec le Professeur Felix Fritzen de l’Université de Stuttgart en utilisant son modèle de réduction avec la programmation parallèle sur GPU. Nous avons également adopté une autre approche basée sur le potentiel de réduction issue de la littérature pour améliorer l’efficacité de la conception simultanée. / High-performance heterogeneous materials have been increasingly used nowadays for their advantageous overall characteristics resulting in superior structural mechanical performance. The pronounced heterogeneities of materials have significant impact on the structural behavior that one needs to account for both material microscopic heterogeneities and constituent behaviors to achieve reliable structural designs. Meanwhile, the fast progress of material science and the latest development of 3D printing techniques make it possible to generate more innovative, lightweight, and structurally efficient designs through controlling the composition and the microstructure of material at the microscopic scale. In this thesis, we have made first attempts towards topology optimization design of multiscale nonlinear structures, including design of highly heterogeneous structures, material microstructural design, and simultaneous design of structure and materials. We have primarily developed a multiscale design framework, constituted of two key ingredients : multiscale modeling for structural performance simulation and topology optimization forstructural design. With regard to the first ingredient, we employ the first-order computational homogenization method FE2 to bridge structural and material scales. With regard to the second ingredient, we apply the method Bi-directional Evolutionary Structural Optimization (BESO) to perform topology optimization. In contrast to the conventional nonlinear design of homogeneous structures, this design framework provides an automatic design tool for nonlinear highly heterogeneous structures of which the underlying material model is governed directly by the realistic microstructural geometry and the microscopic constitutive laws. Note that the FE2 method is extremely expensive in terms of computing time and storage requirement. The dilemma of heavy computational burden is even more pronounced when it comes to topology optimization : not only is it required to solve the time-consuming multiscale problem once, but for many different realizations of the structural topology. Meanwhile we note that the optimization process requires multiple design loops involving similar or even repeated computations at the microscopic scale. For these reasons, we introduce to the design framework a third ingredient : reduced-order modeling (ROM). We develop an adaptive surrogate model using snapshot Proper Orthogonal Decomposition (POD) and Diffuse Approximation to substitute the microscopic solutions. The surrogate model is initially built by the first design iteration and updated adaptively in the subsequent design iterations. This surrogate model has shown promising performance in terms of reducing computing cost and modeling accuracy when applied to the design framework for nonlinear elastic cases. As for more severe material nonlinearity, we employ directly an established method potential based Reduced Basis Model Order Reduction (pRBMOR). The key idea of pRBMOR is to approximate the internal variables of the dissipative material by a precomputed reduced basis computed from snapshot POD. To drastically accelerate the computing procedure, pRBMOR has been implemented by parallelization on modern Graphics Processing Units (GPUs). The implementation of pRBMOR with GPU acceleration enables us to realize the design of multiscale elastoviscoplastic structures using the previously developed design framework inrealistic computing time and with affordable memory requirement. We have so far assumed a fixed material microstructure at the microscopic scale. The remaining part of the thesis is dedicated to simultaneous design of both macroscopic structure and microscopic materials. By the previously established multiscale design framework, we have topology variables and volume constraints defined at both scales.

No description available.

This thesis addresses a number of problems in computer vision, image processing, and geometry processing, and presents novel solutions to these problems. The overarching theme of the techniques presented here is a multi-scale approach, leveraging mathematical tools to represent images and surfaces at different scales, and methods that can be adapted from one type of domain (eg., the plane) to another (eg., the sphere). The main problem addressed in this thesis is known as stereo reconstruction: reconstructing the geometry of a scene or object from two or more images of that scene. We develop novel algorithms to do this, which work for both planar and spherical images. By developing a novel way to formulate the notion of disparity for spherical images, we are able effectively adapt our algorithms from planar to spherical images. Our stereo reconstruction algorithm is based on a novel application of distance transforms to multi-scale matching. We use matching information aggregated over multiple scales, and enforce consistency between these scales using distance transforms. We then show how multiple spherical disparity maps can be efficiently and robustly fused using visibility and other geometric constraints. We then show how the reconstructed point clouds can be used to synthesize a realistic sequence of novel views, images from points of view not captured in the input images, in real-time. Along the way to this result, we address some related problems. For example, multi-scale features can be detected in spherical images by convolving those images with a filterbank, generating an overcomplete spherical wavelet representation of the image from which the multiscale features can be extracted. Convolution of spherical images is much more efficient in the spherical harmonic domain than in the spatial domain. Thus, we develop a GPU implementation for fast spherical harmonic transforms and frequency domain convolutions of spherical images. This tool can also be used to detect multi-scale features on geometric surfaces. When we have a point cloud of a surface of a particular class of object, whether generated by stereo reconstruction or by some other modality, we can use statistics and machine learning to more robustly estimate the surface. If we have at our disposal a database of surfaces of a particular type of object, such as the human face, we can compute statistics over this database to constrain the possible shape a new surface of this type can take. We show how a statistical spherical wavelet shape prior can be used to efficiently and robustly reconstruct a face shape from noisy point cloud data, including stereo data.

This research presents a novel framework for automatic chroma keying and the optimizations for real-time and stereoscopic 3D processing. It first simulates the process of human perception on isolating foreground elements in a given scene by perceptual analysis, and then predicts foreground colours and alpha map based on the analysis results and the restored clean background plate rather than direct sampling. Besides, an object level depth map is generated through stereo matching on a carefully determined feature map. In addition, three prototypes on different platforms have been implemented according to their hardware capability based on the proposed framework. To achieve real-time performance, the entire procedures are optimized for parallel processing and data paths on the GPU, as well as heterogeneous computing between GPU and CPU. The qualitative comparisons between results generated by the proposed algorithm and other existing algorithms show that the proposed one is able to generate more acceptable alpha maps and foreground colours especially in those regions that contain translucencies and details. And the quantitative evaluations also validate our advantages in both quality and speed.

Memoria (licenciado en ciencias jurídicas y sociales) / No autorizada por el autor para ser publicada a texto completo / Así, el objetivo principal de la presente investigación es realizar un estudio respecto a las razones que esgrime la Free Software Foundation (FSF) al momento de considerar una licencia libre como incompatible con la GNU GPL. En conjunto con lo anterior son objetivos especifico de la presente investigación: presentar los aspectos relevantes de cada licencia, principalmente los derechos que concede y las condiciones que impone a los usuarios del software licenciado y exponer las razones esgrimidas por la FSF para considerar la licencia como incompatible, presentado una 8 opinión acerca de dichas razones y exponiendo otros elementos de incompatibilidad no considerados por la FSF en su análisis, si es que existen. Para lograr los anteriores objetivos, será necesario comenzar con un capítulo dedicado a la propiedad intelectual, en general, centrándonos particularmente en la rama del derecho de autor: su concepto, el objeto de su protección, los titulares de dicho derecho, el contenido de éste y cuál es su duración

[pt] A reconstrução de superfícies é um problema que recebe bastante atenção em Computação Gráfica dada a importância de suas aplicações. Uma solução comum é representar essas superfícies por malhas triangulares. Neste trabalho é proposta uma estrutura de tetraedros com cúbicas definidas em seu interior que são utilizadas para aproximar a superfície. Essas cúbicas, chamadas de TetraQuads, são superfícies implícitas de grau 3 definidas como interpolação de quádricas posicionadas nos vértices dos tetraedros. Esses elementos foram idealizados de forma que seja rápido o processamento para visualização dessa estrutura pelo hardware gráfico. Os objetos definidos dessa maneira carregam mais informações do ponto de vista da geometria diferencial que uma malha triangular. Por esse motivo, têm uma modelagem mais complexa a ser resolvida. Esse problema é discutido ao apresentar os passos para reconstrução de superfícies por TetraQuads a partir de nuvens de pontos. / [en] Surface reconstruction is a problem that receives a lot of attention in Computer Graphics due to the importance and the number of its applications. A common solution is to represent these surfaces through triangular meshes. This work introduces an alternative structure of tetrahedrons with cubics defined in its interior, which are used to approximate the surface. Those cubics, called TetraQuads, are third-degree implicit surfaces defined as an interpolation of quadrics positioned at the tetrahedrons vertices. These elements are constructed for an efficient visualization by the graphics hardware. Objects defined in this manner contain more information from the differential geometry point of view than a triangle mesh, which entails a more complex modeling problem. This problem is discussed throughout the steps of surface reconstruction from point clouds through TetraQuads.

This thesis deals with an echo state network and with acceleration of its learning by implementing the echo state network on a graphics processor. The theoretical part consists of the description of neural networks and some selected types of neural networks, on which is based the echo state network. After that, there are some other algorithms described used for time series analysis and last but not least, the tools that were used in the practical part of the thesis were briefly described. The practical part describes the creation of the accelerated version of the echo state network. After that, there is described the creation of input data sets of real financial indexes, on which the echo state network and the other algorithmns were then tested. By analyzing this accelerated version it was found that its learning speed did not reach the theoretical expectations. The accelerated version works slower, but with greater precision. By analyzing the results of the measurement of the other algorithmns it was found that the highest precision is achieved by solutions based on the neural network principle.