Generation and optimization of physics-based graphics simulations

Simulations of physical phenomena are used in many fields, from the study of liquids and solids in material science, to the exploration of diffusion phenomena, and to creating animations and graphics. Such simulations are compute-intensive. Their usefulness is often limited by the speed and accuracy that can be achieved, by memory limitations, and by the difficulty of coding. The research work presented in this dissertation addresses these limitations and offers improvements, touching on all three aspects of physical simulation: a direct use case, the speed of the simulation, and the ease of writing the simulation.The work started with a direct use case for physics simulation: a detailed simulation of the spread of COVID-19 within moving crowds. It integrated an ecological model of diffusion and immunity to simulate the disease spread, with a force model to calculate the crowd movement. The interactive simulation was the first to model disease spread within the field of computer graphics.The model was insightful, however the simulations were slow and computationally expensive, particularly in 3D. This obstacle led to a second study, which investigated speeding up 3D simulations via memory access optimization. That study focused on the simulation of elastic solids. Usually, methods of optimizing simulations for speed make solver-specific or scenario-specific optimizations. In contrast, the technique presented in this dissertation’s second study is a general acceleration method that can be used to speed up any simulation of elastic solids. This is accomplished by rearranging the data of the elastic solid meshes to make the ordering of the vertices and faces cache-efficient. The rearranged data can then be used in any solver, resulting in a faster simulation run.The work done to optimize the simulations brought to the fore the complications inherent in programming efficient physical simulations. The programmer is required to have intricate knowledge of the internal workings of the computer. The simulation code must be written in a low-level language (usually C++). The necessity of low-level programming results in bloated and repetitive code, with plenty of room for bugs to hide. The final part of this dissertation describes a solution to this hurdle for grid-based fluid simulations: a domain-specific language called Spade. In Spade, users specify the parameters of a simulation in a high-level specification file, which is then automatically compiled into optimized C++ code. The resulting simulations are based on the sparse grid representation, which has recently emerged as an indispensable component of fluid simulation pipelines due to its impact on memory savings and performance. In Spade, the complexities of maximizing computational efficiency (through leveraging cache coherency and parallelization) are handled behind the scenes, allowing the developer to focus on defining the grid, data, and the core algorithm.