UCLA

The level set method is one of the most useful algorithms for scientific computing problems that require computations over complex geometric domains. By representing geometry in terms of implicit functions defined over regular Cartesian grids, level set methods automatically capture a wide range of dynamic shapes and topology changes. They have gained wide adoption for problems in fluid dynamics, image processing, chip manufacturing, combustion, computer animation and many more. Dynamic changes in the geometry are automatically resolved by advecting the implicit function throughout a flow domain. However, it is typically necessary for the function describing the level set to have some important properties that the advection process does not preserve. One such property is that the gradient of the implicit function should have unit norm. Given this requirement, much research has been done on replacing an implicit function with a new function that preserves the old zero isocontour while satisfying the unit norm gradient constraint. This process is called redistancing and its solution satisfies the eikonal equation.

Many methods currently exist to solve this problem. Fast marching and fast sweeping are the most popular redistancing methods due to their efficiency and relative simplicity. However, these methods require propagation of information from the zero-isocontour outwards, and this data dependence complicates efficient implementation on today's multiprocessor hardware. Recently an interesting alternative view has been developed that utilizes the Hopf-Lax formulation of the solution to the eikonal equation. In this approach, the signed distance at an arbitrary point is obtained without the need of distance information from neighboring points. We extend the work of Lee et al. to redistance functions defined via interpolation over a regular grid. The grid-based definition is essential for practical application in level set methods. We demonstrate the effectiveness of our approach with GPU parallelism on a number of representative examples.

In addition, we show how our method can be modified to solve the problem of oblique projection. This problem arises in the simulation of elastoplastic materials. An elastoplastic material has a region of allowed (or feasible) stress, and during simulation the stresses can leave the region. A projection is necessary to return the stress back to the feasible region. As we will show, this projection is not always a right angle projection. The shape of the allowed stress region changes depending on the material being simulated. While some closed form solutions exist for determining the projection, in general this problem is difficult. We provide a parallel solution for finding the oblique projection needed for an arbitrary region of allowed stress that generalizes the Hopf-Lax approach to redistancing.