Abstract: The wall distance of Cartesian grids is an essential parameter for the proper wall treatment using ghost cells and is also one of the critical factors governing the efficiency of the flow field simulation after mesh adaptation. This paper proposes a triangular parameterization method that converts the problem of computing the minimum distance between spatial points and discretized triangular meshes on the surface into a constrained one-dimensional extremum problem. This simplification only requires symbolic judgments and a small number of addition, subtraction and multiplication operations to obtain the minimal distance, yielding significant improvements in the accuracy and efficiency compared to existing methods. Meanwhile, a KDT (K-dimensional tree) data structure based on the nested enclosing box concept is developed to optimize the backtracking of data points far from the surface in the KDT nearest neighbor search algorithm. The application of this method to three-dimensional geometries such as spheres, missiles, and DPW6 demonstrates that the error between the computed wall distance and the resolved one is within one millionth. Moreover, the computational costs of using a single core for billion-scale grids are comparable to those of parallel computation using existing methods.