Cutter trace calculation and interference checking play a dominant role in the NC machining of complex surface. In this paper the conceptions of the final movement and the orientation-distance have been proposed. It is proved that the two points with minimal orientation-distance on a pair of smooth surfaces are conjugate points. Thus the conjugate problem between the two surfaces is converted into optimization process of orientation-distance function. Combining minimal orientation-distance principle with five-point optimization method, the minimal orientation-distance algorithm has been proposed to calculate the cutter trace. The cutter trace and the cutter interference are achieved respectively by local and global optimization of the orientation-distance function based on the minimal orientation-distance algorithm and GA. The validity of this new algorithm is also proved by helicoids NC machining.