Regular grids are ubiquitous across computation mathematics, appearing in areas such as the numerical solution of differential equations, rendering in computer graphics, and mesh generation. In this dissertation we present two methods utilizing a regular background grid. We also discuss miscellaneous smaller contributions.
The first is a hybrid Lagrangian/Eulerian advection and projection method for fluid simulations which employs a regular grid both for Eulerian advection and for sub-grid-cell representation of irregular computational domains using a variation of the Marching Cubes algorithm. This method uses a Chorin splitting of the advection and pressure terms in the (incompressible) Euler equations. We present a novel backward semi-Lagrangian method using quadratic B-splines for velocity interpolation during the advection step. We additionally use B-spline interpolation over a regular grid in a variational technique for the pressure projection step.
The second is a method for creating volumetric meshes to represent the interior of self-intersecting input surfaces with emphasis on efficiency and the minimization of costly exact or adaptive arithmetic. Standard approaches assume that the input surface is free of self-intersection, but in practice surface meshes have some amount of self-intersection. Our approach generates an embedded hexahedron mesh where each hexahedral element is a copy of a background grid cell. Regions of self-intersection are resolved by using multiple copies of the grid cells, with connectivity determined by the behavior of the input surface. While sufficiently high resolution is occasionally required to correctly resolve self-intersections, we present a topology preserving coarsening method to reach the desired lower resolution.
The first of the smaller contributions is a computation of the eigenstructure of the Hessian for a surface tension energy density model used in an updated-Lagrangian method for simulating mid-to-extreme surface tension forces. The second is a proof using B-spline techniques of the simplified form of the inertia tensor from the Affine Particle-in-Cell (APIC) method.
