I propose a particle-based technique for simulating incompressible uid that includes adaptive re nement of particle sampling. Each particle represents a mass of uid in its local region. Particles are split into several particles for ner sampling in regions of complex ow. In regions of smooth ow, neghboring particles can be merged. Depth below the surface and Reynolds number are exploited as our criteria for determining whether splitting or merging should take place. For the uid dynamics calculations, I use the hybrid FLIP method, which is computationally simple and e cient. Since the uid is incompressible, each particle has a volume proportional to its mass. A kernel function, whose e ective range is based on this volume, is used for transferring and updating the particle's physical properties such as mass and velocity. In addition, the particle sampling technique is extended to a fully adaptive approach, supporting adaptive splitting and merging of uid particles and adaptive spatial sampling for the reconstruction of the velocity and pressure elds. Particle splitting allows a detailed sampling of uid momentum in regions of complex ow. Particle merging, in regions of smooth ow, reduces memory and computational overhead. An octree structure is used to compute inter-particle interactions and to compute the pressure eld. The octree supporting eld-based calculations is adapted to provide a ne spatial reconstruction where particles are small and a coarse reconstruction where particles are large. This scheme places computational resources where they are most needed, to handle both ow and surface complexity. Thus, incompressibility can be enforced even in very small, but highly turbulent areas. Simultaneously, the level of detail is very high in these areas, allowing the direct support of tiny splashes and small-scale surface tension e ects. This produces a nely detailed and realistic representation of surface motion.

This work presents an approach to effectively integrate into one unified modular fire simulation framework the major processes related to fire, namely: a burning process, chemical combustion, heat distribution, decomposition and deformation of burning solids, and rigid body simulation of the residue. Simulators for every stage are described, and the modular structure enables switching to different simulators if more accuracy or more interactivity is desired. A “Stable Fluids” based three gas system is used to model the combustion process, and the heat generated during the combustion is used to drive the flow of the hot air. Objects, if exposed to enough heat, ignite and start burning. The decomposition of the burning object is modeled as a level set method, driven by the pyrolysis process, where the burning object releases combustible gases. Secondary deformation effects, such as bending burning matches and crumpling burning paper, are modeled as a proxy based deformation. Physically based simulation, done at interactive rates, enables the user to ef- ficiently test different setups, as well as interact and change the conditions during the simulation. The graphics card is used to generate additional frames for real-time visualization. This work further proposes a method for controlling and directing high resolution simulations. An interactive coarse resolution simulation is provided to the user as a “preview” to control and achieve the desired simulation behavior. A higher resolution “final” simulation that creates all the fine scale behavior is matched to the preview simulation such that the preview and final simulations behave in a similar manner. In this dissertation, we highlighted a gap within the CG community for the simulation of fire. There has not previously been a physically based yet interactive simulation for fire. This dissertation describes a unified simulation framework for physically based simulation of fire and burning. Our results show that our implementation can model fire, objects catching fire, burning objects, decomposition of burning objects, and additional secondary deformations. The results are plausible even at interactive frame rates, and controllable.

Tornado simulations in the visual effects industry have always been an interesting problem. Developing tools to provide more control over such effects is an important and challenging task. Current methods to achieve these effects use either particle systems or fluid simulation. Particle systems give a lot of control over the simulation but do not take into account the fluid characteristics of tornadoes. The other method which involves fluid simulation models the fluid behavior accurately but does not give control over the simulation. In this thesis, a novel method to model tornado behavior is presented. A tool based on this method was also created. The method proposed in this thesis uses a hybrid approach that combines the flexibility of particle systems while producing interesting swirling motions inherent in the fluids. The main focus of the research is on providing easy-to-use controls for art directors to help them achieve the desired look of the simulation effectively. A variety of controls is provided which include the overall shape, path, rotation, debris, surface, swirling motion, and interaction with the environment. The implementation was done in Houdini, which is a 3D animation software whose node based system allows an algorithmic approach to the problem and integrates well with the current tools. The tool allows the user to create animations that reflect the visual characteristics of real tornadoes. The usefulness of the tool was evaluated among participants who had some experience in 3D animation software. The results from the simulation and evaluation feedback reveal that the tool successfully allowed the users to create tornadoes of their choice efficiently.

This work presents an approach to effectively integrate into one unified modular fire simulation framework the major processes related to fire, namely: a burning process, chemical combustion, heat distribution, decomposition and deformation of burning solids, and rigid body simulation of the residue. Simulators for every stage are described, and the modular structure enables switching to different simulators if more accuracy or more interactivity is desired. A "Stable Fluids" based three gas system is used to model the combustion process, and the heat generated during the combustion is used to drive the flow of the hot air. Objects, if exposed to enough heat, ignite and start burning. The decomposition of the burning object is modeled as a level set method, driven by the pyrolysis process, where the burning object releases combustible gases. Secondary deformation effects, such as bending burning matches and crumpling burning paper, are modeled as a proxy based deformation. Physically based simulation, done at interactive rates, enables the user to ef- ficiently test different setups, as well as interact and change the conditions during the simulation. The graphics card is used to generate additional frames for real-time visualization. This work further proposes a method for controlling and directing high resolution simulations. An interactive coarse resolution simulation is provided to the user as a "preview" to control and achieve the desired simulation behavior. A higher resolution "final" simulation that creates all the fine scale behavior is matched to the preview simulation such that the preview and final simulations behave in a similar manner. In this dissertation, we highlighted a gap within the CG community for the simulation of fire. There has not previously been a physically based yet interactive simulation for fire. This dissertation describes a unified simulation framework for physically based simulation of fire and burning. Our results show that our implementation can model fire, objects catching fire, burning objects, decomposition of burning objects, and additional secondary deformations. The results are plausible even at interactive frame rates, and controllable.

No description available.

Creating realistic virtual hair consists of several major areas: creating the geometry, moving the hair strands realistically and rendering the hair. In this thesis, a background survey covering each one of these areas is given. A node-based, procedural hair system is presented, which utilizes the capabilities of modern GPUs. The hair system is implemented as a plugin for Autodesk Maya, and a user interface is developed to allow the user to control the various parameters. A number of nodes are developed to create effects such as clumping, noise and frizz. The proposed system can easily handle a variety of hairstyles, and pre-renders the result in real-time using a local shading model.

This thesis presents a method for simulating fluids on a view dependent grid structure to exploit level-of-detail with distance to the viewer. Current computer graphics techniques, such as the Stable Fluid and Particle Level Set methods, are modified to support a nonuniform simulation grid. In addition, infinite fluid boundary conditions are introduced that allow fluid to flow freely into or out of the simulation domain to achieve the effect of large, boundary free bodies of fluid. Finally, a physically based rendering method known as photon mapping is used in conjunction with ray tracing to generate realistic images of water with caustics. These methods were implemented as a C++ application framework capable of simulating and rendering fluid in a variety of user-defined coordinate systems.

This thesis describes methods for collision detection and collision response, implemented in a complete collision framework for both rigid and deformable bodies. The framework is intended to act as a base for new technologies regarding muscle and facial simulation for feature film production, at the visual effects studio MPC. Specifically, we implement sweep and prune as a first step in our collision detection for fast pruning of pairs, followed by optimized spatial hashing to decrease the amount of triangle intersection tests. Further, we use a constraint-based method for collision response based on iterative constraint anticipation, which provides several advantages in terms of accuracy compared to penalty- or impulse-based methods.

This thesis deals with design, implementation and analysis of the model for dynamic changes in the terrain. Present state of terrain deformation in OpenSceneGraph environment is described and available relevant software called TDS, which allows terrain adaptation to new inserted objects is presented. Special emphasis is placed on design of model for physically based terrain deformations that are caused by moving object or by bomb explosion. The results of simulation tests are presented and on the base of model analysis, the optimizations, which significantly improve final algorithm, are designed and realized.

La quête de performance a été une constante à travers l’histoire des systèmes informatiques. Il y a plus d’une décennie maintenant, le modèle de traitement séquentiel montrait ses premiers signes d’épuisement pour satisfaire les exigences de performance. Les barrières du calcul séquentiel ont poussé à un changement de paradigme et ont établi le traitement parallèle comme standard dans les systèmes informatiques modernes. Avec l’adoption généralisée d’ordinateurs parallèles, de nombreux algorithmes et applications ont été développés pour s’adapter à ces nouvelles architectures. Cependant, dans des applications non conventionnelles, avec des exigences d’interactivité et de temps réel, la parallélisation efficace est encore un défi majeur. L’exigence de performance en temps réel apparaît, par exemple, dans les simulations interactives où le système doit prendre en compte l’entrée de l’utilisateur dans une itération de calcul de la boucle de simulation. Le même type de contrainte apparaît dans les applications d’analyse de données en continu. Par exemple, lorsque des donnes issues de capteurs de trafic ou de messages de réseaux sociaux sont produites en flux continu, le système d’analyse doit être capable de traiter ces données à la volée rapidement sur ce flux tout en conservant un budget de mémoire contrôlé La caractéristique dynamique des données soulève plusieurs problèmes de performance tel que la décomposition du problème pour le traitement en parallèle et la maintenance de la localité mémoire pour une utilisation efficace du cache. Les optimisations classiques qui reposent sur des modèles pré-calculés ou sur l’indexation statique des données ne conduisent pas aux performances souhaitées. Dans cette thèse, nous abordons les problèmes dépendants de données sur deux applications différentes : la première dans le domaine de la simulation physique interactive et la seconde sur l’analyse des données en continu. Pour le problème de simulation, nous présentons un algorithme GPU parallèle pour calculer les multiples plus courts chemins et des diagrammes de Voronoi sur un graphe en forme de grille. Pour le problème d’analyse de données en continu, nous présentons une structure de données parallélisable, basée sur des Packed Memory Arrays, pour indexer des données dynamiques géo-référencées tout en conservant une bonne localité de mémoire. / A busca por desempenho tem sido uma constante na história dos sistemas computacionais. Ha mais de uma década, o modelo de processamento sequencial já mostrava seus primeiro sinais de exaustão pare suprir a crescente exigência por performance. Houveram "barreiras"para a computação sequencial que levaram a uma mudança de paradigma e estabeleceram o processamento paralelo como padrão nos sistemas computacionais modernos. Com a adoção generalizada de computadores paralelos, novos algoritmos foram desenvolvidos e aplicações reprojetadas para se adequar às características dessas novas arquiteturas. No entanto, em aplicações menos convencionais, com características de interatividade e tempo real, alcançar paralelizações eficientes ainda representa um grande desafio. O requisito por desempenho de tempo real apresenta-se, por exemplo, em simulações interativas onde o sistema deve ser capaz de reagir às entradas do usuário dentro do tempo de uma iteração da simulação. O mesmo tipo de exigência aparece em aplicações de monitoramento de fluxos contínuos de dados (streams). Por exemplo, quando dados provenientes de sensores de tráfego ou postagens em redes sociais são produzidos em fluxo contínuo, o sistema de análise on-line deve ser capaz de processar essas informações em tempo real e ao mesmo tempo manter um consumo de memória controlada A natureza dinâmica desses dados traz diversos problemas de performance, tais como a decomposição do problema para processamento em paralelo e a manutenção da localidade de dados para uma utilização eficiente da memória cache. As estratégias de otimização tradicionais, que dependem de modelos pré-computados ou de índices estáticos sobre os dados, não atendem às exigências de performance necessárias nesses cenários. Nesta tese, abordamos os problemas dependentes de dados em dois contextos diferentes: um na área de simulações baseada em física e outro em análise de dados em fluxo contínuo. Para o problema de simulação, apresentamos um algoritmo paralelo, em GPU, para computar múltiplos caminhos mínimos e diagramas de Voronoi em um grafo com topologia de grade. Para o problema de análise de fluxos de dados, apresentamos uma estrutura de dados paralelizável, baseada em Packed Memory Arrays, para indexar dados dinâmicos geo-localizados ao passo que mantém uma boa localidade de memória. / The quest for performance has been a constant through the history of computing systems. It has been more than a decade now since the sequential processing model had shown its first signs of exhaustion to keep performance improvements. Walls to the sequential computation pushed a paradigm shift and established the parallel processing as the standard in modern computing systems. With the widespread adoption of parallel computers, many algorithms and applications have been ported to fit these new architectures. However, in unconventional applications, with interactivity and real-time requirements, achieving efficient parallelizations is still a major challenge. Real-time performance requirement shows up, for instance, in user-interactive simulations where the system must be able to react to the user’s input within a computation time-step of the simulation loop. The same kind of constraint appears in streaming data monitoring applications. For instance, when an external source of data, such as traffic sensors or social media posts, provides a continuous flow of information to be consumed by an online analysis system. The consumer system has to keep a controlled memory budget and deliver a fast processed information about the stream Common optimizations relying on pre-computed models or static index of data are not possible in these highly dynamic scenarios. The dynamic nature of the data brings up several performance issues originated from the problem decomposition for parallel processing and from the data locality maintenance for efficient cache utilization. In this thesis we address data-dependent problems on two different applications: one on physically based simulations and another on streaming data analysis. To deal with the simulation problem, we present a parallel GPU algorithm for computing multiple shortest paths and Voronoi diagrams on a grid-like graph. Our contribution to the streaming data analysis problem is a parallelizable data structure, based on packed memory arrays, for indexing dynamic geo-located data while keeping good memory locality.