The fast construction of extension velocities in level set methods

Level set techniques are numerical techniques for tracking the evolution of interfaces. They rely on two central embeddings; first, the embedding of t he interface as the zero level set of a higher dimensional function, and se cond, the embedding (or extension) of the interface's velocity to this high er dimensional level set function. This paper applies Sethian's Fast Marchi ng Method, which is a very fast technique for solving the eikonal and relat ed equations, to the problem of building fast and appropriate extension vel ocities for the neighboring level sets. Our choice and construction of exte nsion velocities serves several purposes. First, it provides a way of build ing velocities for neighboring level sets in the cases where the velocity i s defined only on the front itself. Second, it provides a subgrid resolutio n not present in the standard level set approach. Third, it provides a way to update an interface according to a given velocity field prescribed on th e front in such a way that the signed distance function is maintained, and the front is never re-initialized; this is valuable in many complex simulat ions. In this paper, we describe the details of such implementations, toget her with speed and convergence tests and applications to problems in visibi lity relevant to semi-conductor manufacturing and thin film physics. (C) 19 99 Academic Press.