Vol. 9, No. 1, 2014

Download this article
Download this article For screen
For printing
Recent Issues
Volume 11, Issue 1
Volume 10, Issue 2
Volume 10, Issue 1
Volume 9, Issue 2
Volume 9, Issue 1
Volume 8, Issue 1
Volume 7, Issue 2
Volume 7, Issue 1
Volume 6, Issue 1
Volume 5, Issue 2
Volume 5, Issue 1
Volume 4, Issue 1
Volume 3, Issue 1
Volume 2, Issue 1
Volume 1, Issue 1
The Journal
About the Cover
Editorial Board
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Editorial Login
Author Index
To Appear
ISSN: 2157-5452 (e-only)
ISSN: 1559-3940 (print)
High-order methods for computing distances to implicitly defined surfaces

Robert I. Saye

Vol. 9 (2014), No. 1, 107–141

Implicitly embedding a surface as a level set of a scalar function ϕ : d is a powerful technique for computing and manipulating surface geometry. A variety of applications, e.g., level set methods for tracking evolving interfaces, require accurate approximations of minimum distances to or closest points on implicitly defined surfaces. In this paper, we present an efficient method for calculating high-order approximations of closest points on implicit surfaces, applicable to both structured and unstructured meshes in any number of spatial dimensions. In combination with a high-order approximation of ϕ, the algorithm uses a rapidly converging Newton’s method initialised with a guess of the closest point determined by an automatically generated point cloud approximating the surface. In general, the order of accuracy of the algorithm increases with the approximation order of ϕ. We demonstrate orders of accuracy up to six for smooth problems, while nonsmooth problems reliably reduce to their expected order of accuracy. Accompanying this paper is C++ code that can be used to implement the algorithms in a variety of settings.

implicit surfaces, closest point, level set methods, reinitialisation, redistancing, high-order
Mathematical Subject Classification 2010
Primary: 65D99, 68U05, 35R37
Secondary: 65D17, 65D18, 35R01
Received: 23 January 2014
Revised: 30 April 2014
Accepted: 2 May 2014
Published: 17 May 2014
Robert I. Saye
Lawrence Berkeley National Laboratory and Department of Mathematics
One Cyclotron Road
MS: 50A-1148
Berkeley, CA 94720
United States