INTRODUCTION

Traveltime map generation is a computationally expensive step in 3-D Kirchhoff depth imaging. Most approaches proposed are either based on ray tracing equation or on eikonal equation (, , , ). Popovici and Sethian proposed a fast-marching finite-difference eikonal solver in the Cartesian coordinates, which is very efficient and stable. The high efficiency is based on the heap-sorting algorithm. A similar idea has been used previously by Cao and Greenhalgh in a slightly different context. The remarkable stability of the method results from a specially choosing order of finite-difference evaluation, which resembles the method used by (). Alkhalifah and Fomel implemented the fast-marching algorithm in the polar coordinates, which is more accurate than its Cartesian implementation. However, the polar implementation requires velocity to be transformed from the Cartesian to the polar coordinates for each source location, which makes it inefficient. The spatial variation of grid size in the polar coordinates also makes it more difficult to handle strong velocity variation. We present a new scheme based on the tetragonal eikonal equation. Because of the specialty of the tetragonal coordinates we have chosen, this new algorithm is more accurate than the Cartesian implementation. Meanwhile, it is free of the problems associated with the polar implementation. We first derive the tetragonal coordinates eikonal equation and explain why it is more accurate than the Cartesian fast-marching eikonal solver. Then we show how to derive the same approach from Fermat's Principle using a variational formulation, which is important for extending the fast-marching method to unstructured grids. We present 2-D and 3-D results, from simple to complex model, to support our explanation.